CRC并行优化的实现_上_

CRC 并行优化的实现（上） Parallel Optimization of CRC(Ⅰ) 左洪成,吴高奎,李朝海（电子科技大学,四川成都 611731） Zuo Hong- cheng ,Wu Gao- kui,Li Chao- hai(University of Electronic Science and Technology of China,Sichuan Chengdu 611731) 摘 要：该文提出了一种基于前向预测、展开和重定时的高速并行化 CRC的实现方法。首先从简单的理论推导开 始，得到原始的实现结构；然后针对这种结构，结合有反馈结构的 VLSI中各种优化方法，一步步地进行结构分析、 优化，得到几种具体的实现优化；最后进行结果的对比分析，几种优化方法得到多种优化结构，相应地为不同的应 用提供了多种选择以供权衡。 关键词：CRC；循环冗余校验；并行化；有反馈结构的优化；迭代边界 中图分类号：TP316 文献标识码：A 文章编号：1003- 0107(2011)07- 0047- 03 Abstract :This paper presents a high- speed parallel CRC's implementation based on forward prediction,expand and re- timed.Firs t, s tarting from simple theoretical analysis to obtain the realization of the orig inal s tructure;and then for this s tructure,combined with the feedback structure of the various optimization methods, were given to specific types of optimal.Finally,comparing the results of analysis , Several optimization methods to get a variety of optimized structure,corresponding to different applications in a variety of options . Key words: CRC;Cyclic Redundancy Check;Parallel;Optimization of a feedback structure;Iteration Bound CLC number:TP316 Document code: A Art icle ID:1003- 0107(2011)07- 0047- 03 1 引言 在数据的通信的校验方式中，CRC(循环冗余校验)以其简 单的结构、较强的检测能力而得到广泛的应用[1]。传统的实现 方式可以分为软件查 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 和硬件实现两种，本文主要研究 CRC 的硬件实现。DSP算法可以用无休止的程序来描述[2]，算法中 所有计算运行一次称为一次迭代，迭代周期是指算法中运行 一次迭代所需的时间；关键路径定义为 DSP算法中任意两个 寄存器或输入输出之间的最长组合路径，关键路径的运行时 间确定了 DSP算法最小可行的时钟周期及最高速度；迟滞定 义为产生输出的时间与系统接收对应输入的时间之差，一般 按时钟周期数量表示。可见,在迭代结构中，对最高速度起直 接制约的是关键路径(CP)，对模块吞吐率起制约作用的是迭代 边界(IB，Iteration Bound)，而且关键路径的下限是迭代边界，所 以，可以这样说，迭代边界是迭代结构的本质瓶颈所在，结构 的优化首先应该围绕迭代边界展开。 2 优化的关键概念和 CRC理论简介 2.1 关键概念 定义迭代边界为关键环路的环路边界，这个边界是 DSP 程序中迭代或者采样周期的最低限制，与可用的运算资源的 多少无关；关键环路是指具有最大环路边界的环路，而环路边 界是表示环路运行时间的最低限制，如第 l个环路的环路边界 为 tl/ωl。其中，tl是指环路运算时间，ωl是指环路中的延时数 目，可得迭代边界的表达式为： T∞=max{ tlωl } (1) 2.2 CRC理论简介 循环冗余校验码[1]的基本思想是利用线性编码理论，在发 送端根据要传送的 k位二进制信息码，以一定规则产生一个 校验用的 r位监督码(也即 CRC码)，附加在信息码后，组成一 个 n=k+r位的二进制码元序列(即为(n,k)码)，并发送到信道或 后继编码中；接收端对整个数据进行译码，若校验结果为 0，则 说明传送过程中没有发生错误，或错误超过了 CRC的检测范 围而没有检测到，一般后者的概率小得多。 CRC的具体生成过程为：首先根据需要的监督码元长度 选取特定的生成多项式 G(x)，这是一个最高项阶数为 r的多项 式；其次，将发送的 k位码元采用信息多项式 C(x)表示，并将 C(x)左移 r位，得到 C(x)×2r，实际对应着信息位右边留下 r位 空间给监督位；最后将 C(x)×2r模 2除以 G(x)，得到的余数就 是监督码元了。有多种 G(x)可供选取，这要视信息码元的长度 及编码所需的安全度而定。后文的分析选取 CRC- 16进行，其 特征多项式为 G(x)=x16+x15+x2+1。 CRC的译码过程为：首先选取约定的生成多项式 G(x)；其 l∈L 测评与应用 ssessment and ApplicationA 47 2011第 07期 绿色质量观察 次，将接收到的 n位码元序列(对应着信息位和监督位)模 2除 以生成多项式 G(x)，如果余数为零，则传输没有错误或错误太 大而无法识别。由于模 2操作不考虑进位及借位，所以可以简 化为异或操作。余数实际对应着模 2除法中的寄存器位，所 以，监督码元的输出直接选取移位寄存器结构中的寄存器，而 不是一般的串行输出。 CRC的实现是一个很早就被研究过的问题，从最初的软 件实现，到后来的串行硬件实现，再到后来的并行硬件 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ， 都曾被广泛研究，很多的优化方法被引入，但这些算法或来自 数论领域其他的移位寄存器结构，或来自算法推导时得到的 一些特殊结论，却鲜有直接明了的结构分析的优化方法。本节 从原始的并行结构出发，采取 VLSI中广泛使用的优化方法， 一步步地进行结构分析、优化，得到几个不同性能的 CRC- 16 实现结构；这些步骤及优化方法的选取都是根据结构的分析 而来的，有具体的理论根据及实施步骤，所以实现起来难度 较小。 3 CRC结构分析及优化 由前面关于 CRC的理论推导可知，可以利用移位寄存器 结构来完成 CRC编码，从原始的 CRC- 16结构开始，分析其迭 代边界，结合重定时及并行展开，得到速度与吞吐率较优的一 个实现[7]。 3.1 原始结构的 CRC 由上述推导，可得 CRC- 16的实现结构如图 1所示。其 中，xi为寄存器，这里为了体现出与常规寄存器的差别而特意 给出标记，+为异或(XOR)门，y为输入。其迭代边界与关键路 径如式(2)所示。 (2) 由前面关于迭代边界、关键路径及吞吐率的说明可知，该 结构的采样周期已经达到极限，不存在简单的提高速度的方 法[3]。下面首先引入前向预测，然后进行展开以发现模块的并 行特性。 3.2 一阶前向预测 CRC 按图 1所示的标记，有： (3) 则一阶前向预测之后，有式(4)成立，其所对应的结构框图 如图 2所示，所对应的迭代边界与关键路径如式(5)所示。 (4) (5) 可见，迭代边界通过一阶前向预测后减半了，但关键路径 的值有所增加，如图 2的水平虚线所示。下面围绕着减小该关 键路径而进行重定时的操作，首先选取图中割集 A进行重定 时，从左向右的边减少一个延时，从右向左的边增加一个延 时，得到如图 3所示的结构框图。 其次，取图 3所示的割集 B进行重定时，从左向右的边减 少两个延时，从右到左的边增加两个延时；最后，选取图中割 集 C进行重定时，进入边减少一个延时，输出边增加一个延 时，得到如图 4所示的结构图，所对应的 IB及 CP为式(6)。 (6) 综上，经过一阶前向预测及一系列的重定时后，模块的迭 代边界减半，关键路径减半，对应的吞吐率加倍，但是增加了 一些寄存器的资源消耗。 3.3 二阶前向预测 CRC 图 1原始结构的 CRC 图 2一阶前向预测后的结构框图 图 3第一次重定时后的结构框图 图 4第二、三次重定时后的结构框图 图 5为预测而引入的标注 48 图 7二阶预测及重定时后的结构框图 经过上一节的前向预测及重定时，CRC- 16的吞吐率有了 一定的改善，下面继续进行前向预测，以期能得到并行展开的 结构，从而更进一步提升其性能。针对一阶前向预测后的图 2， 进行如图 5所示的标注，得式(7)。为了不引入其他的复杂性，首 先选取割集 A[4]进行重定时，将原有的异或结构搬移到左边。 (7) 对式(7)进行二阶前向预测，则可得式(8)，所对应的结构框 图如图 6所示。 (8) 对图 6依次进行如下的割集重定时： (1)选取割集 B进行重定时。从左向右跨过割集的边减少 两个延时，从右向左跨过割集的边增加两个延时。 (2)选取割集 C进行重定时。将图 6分为 G1和 G2两个子 图，从 G1到 G2的边减少两个延时，从 G2到 G1的边增加两 个延时。其中，G2为割集 C内部子图。 (3)选取割集 D进行重定时。经过前面两步重定时后，割集 D的输入边各有两个延时，这里将输入延时减少一个，则对应 的输出延时增加一个，从而将三个异或门使用两个寄存器 隔开。 (4)选取割集 E进行重定时。这里主要是考虑到资源的复 用，经过重定时后，割集 D的一个输入边将与割集 E的输出共 用一个异或门。 经过前面一系列的割集重定时后，得到如图 7所示的结 构框图，可以得到其迭代边界与关键路径如式(9)所示。 (9) 综上，经过二阶前向预测及一系列的割集重定时后，模块 的迭代边界再次减半，但关键路径由于器件的限制而没能继 续减小，这是由于没有考虑异或门微流水结构的原因。实际 上，经过这一系列优化之后，模块潜在的吞吐率加倍，但是由 于关键路径的限制，这里并没能体现出来，实际的吞吐率与优 化前是相同的；如果不再考虑进一步减小关键路径，那么二阶 前向预测及其后的一系列重定时是没有必要的，这就是资源 与速度的一个平衡及取舍问题。（待续） 参考文献： [1]李宥谋,房鼎益.CRC编码算法研究与实现[J].西北大学学报, 2006,36(1): 895- 898. [2]Parhi.K.K.VLSI数字信号处理系统:设计与实现[M].陈弘毅, 白国强,吴行军,译.北京:机械工业出版社,2004. [3]Tenkasi V.Ramabadran,S.S.Gaitonde.A tutorial on CRC compu- tations[J].IEEE on Micro,1988,8(4):62- 75. [4]何宾.FPGA数字信号处理实现原理及方法[M].北京:清华大 学出版社,2010. [5]Chao Cheng,K.K.Parhi.High- Speed Parallel CRC Implementa- tion Based on Unfolding,Pipelining and Retiming[J].IEEE Trans- actions on Circuits and Systems II:Express Briefs,2006,53 (10): 1017- 1021. [6]G.Campobello,G.Patane,and M.Russo.Paralled CRC realization [J].IEEE Trans.Comput.,2003,52(10):1312- 1319. [7]CHAO CHENG.High- Speed Low- Cost VLSI DSP Algorithms Based on Novel Fast Convolutions and Look- Ahead Pipelining Structures[D].Minnesota:The University ofMinnesota,2007. [8]Kazuhito Ito,Keshab K.Parhi.Determining the minimum iteration period of an algorithm[J]. 图 6二阶前向预测后的结构框图 测评与应用 ssessment and ApplicationA 49