高速ATM中CRC算法与信元定界的FPGA实现

张惠峥

（中国电子科技集团公司第五十四研究所，河北石家庄050081）

0 引言

循环冗余码CRC算法是测控及通信领域中应用广泛的一种算法，ITU-T建议对异步转移模式ATM信元信头采用CRC算法进行误码检测和校正，在同步数字系列SDH传输帧中ATM信元的定界也是通过CRC校验码的计算获得的。CRC校验码的计算一般可分为软件和硬件实现2种方法，由于软件代码的顺序执行的特点，在对速度要求甚高的场合很难满足要求;硬件实现一般采用线性反馈移位寄存器组LSFR方法完成，这种方法简单，但每次只能处理一位二进制数据，这种串行的硬件实现方法也很难满足速度较高的场合。笔者在设计高速ATM接口CRC电路的实践过程中，在查阅大量资料的基础上总结出了一种易于采用FPGA实现的并行CRC算法进行信头误码检测和校正以及信元定界的设计。

1 CRC算法

CRC是一种系统缩短循环码，它是利用除法及余数的原理来做错误检测的。利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码（CRC码），附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”，CRC校验采用的就是多项式编码方法，发送方和接收方用同一个生成多项式g（x），并且g（x）的首位和最后一位的系数必须为1。CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。

CRC校验码的编码方法是用待发送的二进制数据t（x）除以生成多项式g（x），将最后的余数作为CRC校验码。其实现步骤如下:

①设待发送的数据块是m位的二进制多项式t（x），生成多项式为r阶的g（x）。在数据块的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为xrt（x）;

②用生成多项式g（x）去除xrt（x），求得余数为阶数为r-1的二进制多项式y（x）。此二进制多项式y（x）就是t（x）经过生成多项式g（x）编码的CRC校验码;

③用xrt（x）以模2的方式减去y（x），得到二进制多项式xrt′（x）。xrt′（x）就是包含了CRC校验码的待发送字符串。

从CRC的编码规则可以看出，CRC编码实际上是将待发送的m位二进制多项式t（x）转换成了可以被g（x）除尽的m+r位二进制多项式xrt′（x），所以解码时可以用接收到的数据去除g（x），如果余数为零，则表示传输过程没有错误;如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时xrt′（x）可以看做是由t（x）和CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。

2 高速ATM中并行CRC设计实现

采用CRC串行算法一个时钟周期内只能处理一位数据，在某些高速场合只能靠提高时钟频率来达到所需的速度要求，这增加了开发的难度和成本。在基于SDH的ATM网络接口中，数据传输速率是155Mbit/s或更高的速率等级，采用串行方式设计出的电路在高速不能稳定工作，同时高的数据传输速率对FPGA芯片等级也提出了很高的要求。为解决此问题，在进行FPGA设计时，串行传输阶段采用并行的CRC算法来降低设计中对芯片处理速度的要求。目前已采用的CRC并行算法是查表法和基于查表法而导出的一些方法，这些方法均需要存储长度较大的CRC余数表，随着并行度的增加，余数表的长度按指数增加，其实现性亦随之大大降低，因此需要提出新的并行CRC算法，用于实现高速链路上CRC的产生和校正电路。

采用并行处理方法的目的都是要提高处理的速度，以达到更高的数据处理能力。笔者为了从CRC的基本算法中得到并行处理的算法，采用了基于矩阵运算、按位依次展开、Z变换等数学知识进行递推，直接推导出数据的逻辑关系公式。在并行处理时，每次处理的位数可以是固定的。

CRC校验电路设计分为CRC编码、检测和校正2大部分，编码用于对输入数据计算CRC校验码，检测和校正用于验证接收到的数据是否正确，并对检测到的单bit错误进行纠正，其实编码和检测这2个过程一样的，不同的是检测时需要判断得到CRC校验码是否为0，如果是0则表示数据正确，如果不为0则表示数据有错。纠正模块对有错的bit进行纠错，纠正不过来的扔掉。下面分别对CRC并行编码、检测和校正电路的FPGA实现进行详细介绍。

2.1 ATM信头并行CRC编码

每个ATM信元的信头均含有VPI/VCI控制选路及其他重要的信息，网络据此选择路由，并决定目的地址，为此需要对信头进行有效的保护。ITU-T建议采用CRC-8实现对ATM信元信头信息的保护，进行信头误码差错控制（HEC），该算法可以检测到多个bit错误并能纠正单个bit错误。发送端对信头进行CRC编码，接收端对收到的数据进行误码检测与校正。

如图1所示，ATM信元由53个8bit字节组成，其中前5个字节构成信头，后48字节构成信元净荷，被保护的信息是信头前4个字节，位长为k=32，监督位（即HEC字段）为第5个字节，位长为r=8，循环码组长度n=k+r=40，所用生成多项式为:G（x）=x8+x2+x+1。在发送端对信头的前4个字节实施CRC算法生成HEC字段。

在并行方法中，一系列的移位运算合并起来在1个时钟周期内完成。对于一个含有qbit的信息，如果信息的kbit来到后k次移位运算综合起来在1个时钟周期内完成，那么仅需要[q/k]个时钟周期即可计算出余数。并行CRC算法一次读入多位数据，通过当前余数与读入数据的运算，得出新的余数。显然，一个时钟周期处理n位数据的并行算法在计算结果上与串行算法处理n个时钟周期所得的余数应该相同。基于这一点，利用高等数学知识采用递推的方法推导出CRC校验码与输入数据和生成多项式的逻辑关系，然后直接运算得出CRC校验码，算法中CRC码的计算和校验完全由一系列的组合逻辑实现，十分有利于转化为硬件电路。

图1 ATM信元的53字节

这里着眼于介绍CRC的并行算法与FPGA实现，原理和推导过程不再详述，下面直接给出XOR电路的结果。这里的D（*）代表*位数据，Z（*）代表上一次计算的*位CRC值。

在进行FPGA设计时，将并行CRC编码计算做成一个单独的函数，这样发送端和接收端进行CRC计算时都可以调用。

2.2 ATM信头并行CRC检测与校正

在接收端对信头的5个字节实施循环冗余校验来判断信头的正确性，检测方法与发送端的编码算法相似，通过把信头前4个字节的CRC计算结果与HEC字段进行异或，如果为0就表示接收到的码字可能是一个合法的信头，否则表示该信元信头有误。

ITU-T I.432.1建议的信头差错控制工作的2种模式如图2所示。平时，接收端工作于单bit“纠错模式”，如果检测到单个bit错误，接收器纠正这个错误并转到“检错模式”;如果检测到多bit错误，它不可能纠正，只好丢弃这个信元，并转到“检错模式”。在检错模式下，所有检测到错误的信元都被丢弃，接收器工作模式不变;只有收到不含差错的信头时，接收器才回到“纠错模式”。当检测出误码后，只有当接收器处于纠错模式时，而且能够成功地纠正单bit误码，并重新组成正确的信头，才能得到正确的有效信元。当接收器工作于检错模式时，或纠错不成功，或纠错后的信头不容许时，信元都要被丢弃。如果发现信头有误码而不能纠正时，宁可丢掉信元而避免将错误的信元送到网络节点。

图2 信头差错控制工作模式

实现ATM信元信头的单bit纠错功能，常用的方法是查表法，但需要在查找表中存储40个可能的错误伴随式模式，占用芯片的资源较多，而且会对电路的复杂程度和最大工作速度产生较大影响，因此查表法并不是实现纠错功能的理想解决方案。利用A.Maniatopoulos提出的一种通过迭代计算导出的“与平面”逻辑来实现高速ATM信元信头纠错是一种简洁易实现的方法。利用“与平面”逻辑确定错误图样后再与原始数据相异或就实现了信头的单bit纠错功能。

介于目前大部分文献资料对CRC的纠错功能电路实现介绍的比较少，这里把纠错模块进行详细说明，表1是设计的纠错模块的端口说明。

表1 纠错模块的端口说明

纠错模块VHDL语言的主要实现代码如下:

correc-data＜=data xor error;

error（0）:=（not d（7））and d（6）and d（5）and（not d（4））and（not d（3））and（not d（2））and d（1）and（not d（0））;

error（1）:=d（7）and d（6）and（not d（5））and（not d（4））and（not d（3））and d（2）and（not d（1））and（not d（0））;

error（2）:=d（7）and（not d（6））and（not d（5））and（not d（4））and d（3）and d（2）and d（1）and d（0）;

error（3）:=（not d（7））and（not d（6））and（not d（5））and d（4）and d（3）and（not d（2））and（not d（1））and d（0）;

error（4）:=（not d（7））and（not d（6））and d（5）and d（4）and（not d（3））and（not d（2））and d（1）and（not d（0））;

error（5）:=（not d（7））and d（6）and d（5）and（not d（4））and（not d（3））and d（2）and（not d（1））and（not d（0））;

error（6）:=d（7）and d（6）and（not d（5））and（not d（4））and d（3）and（not d（2））and（not d（1））and（not d（0））;

error（7）:=d（7）and（not d（6））and（not d（5））and d（4）and（not d（3））and d（2）and d（1）and d（0）;

3 ATM信元定界

信元定界是接收方为了确定信元的起始边界位置，以便于信元后续处理的正确性。通过对CRC校验码的计算搜寻正确的HEC，也就是判断信头中前4个字节与后1个字节是否长期符合CRC-8的关系，就可实现连续信元流的定界。另外，为防止因误码破坏CRC-8关系而误判为信元失界，对于偶尔的HEC不一致，不作失界处理。

因SDH帧中提供同步信号，如图3所示，接收端一开始对收到的数据逐字节进行符合CRC编码规则的检测，搜寻正确的HEC，工作在搜索状态;一旦找到正确的HEC，立即转到预同步状态，逐信元地核对HEC，只有连续收到δ个含有正确HEC的信元时，才算真正找到了信元边界，进入了信元同步状态，否则仍要回到搜索态。在同步状态下，接收端仍需逐信元进行HEC检测，一旦发现α个连续的含有不正确HEC的信元时，就认为丢失了信元边界，重新回到搜索状态。

δ值决定了抗拒信元伪定界的能力，δ值越大，识别伪定界的能力越强，但δ值太大时意味着真正定界后仍没判为定界，易受误码影响使捕捉时间也越长，为此应合理选择δ值。α值决定了信元伪失界的能力，α值越大，抗误码影响的能力越强，但真正失界时所需进入搜索状态的时间也越长，因而α值也应合理选择。ITU-T I.432建议中规定δ=6，α=7。

图3 信元定界状态图

4 结束语

利用上述方法进行了高速ATM信元信头差错控制与信元定界的电路设计，用VHDL语言编写了可综合逻辑代码，最后在XILINX公司的器件Spartan3系列的XC3S4000上进行设计电路的实现，编译结果显示CRC编码生成、检测与纠错3个模块仅占用了126个逻辑单元。设计的电路正确运行的最高时钟频率为155MHz，数据吞吐量超过1.2Gbit/s。工程应用结果表明，这种设计方式较以往的实现方式具有逻辑直接、精简、速度更快，占用资源更少的优点，可以很方便地在FPGA中实现并稳定可靠，对于类似的并行处理电路也具有很好的借鉴意义。

[1]李永忠.通用并行CRC计算原理及其硬件实现方法[J].西北民族学院学报:自然科学版，2002，23（1）:33-37.

[2]MANIATOPULOS A.Single-bit error-correction circuit for ATM interface[J].IEE Electronics Letters，1995（31）:617-618.

[3]ITU-T I.432.B-ISDN USER-NETWORK INTERFACE PHYSICAL LAYER SPECIFICATION:GENERAL CHARACTERISTICS[S].1999.

[4]杨卫平.ATM接口中信元定界方法分析[J].现代有线传输，1997，25（4）:51-56.