基于TMS320C64x的CRC校验算法分析

CRC（Cyclic Redundancy Check）循环冗余校验码是数据通信领域中常用的一种差错校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢贸然行动。对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。其特征是信息字段和校验字段的长度可以任意选定。

为了完成信号传输过程中误码检测，获得正确无误的传输数据，LTE（Long Term Evolution）系统针对不同的数据传输采用了多种格式的循环冗余码，以适应系统高速率高性能的需求。

LTE系统中的循环冗余码

LTE作为准4G技术，以正交频分复用OFDM（Orthogonal Frequency Division Multiplexing）和多输入多输出MIMO（Multiple-Input Multiple-Out-put）技术为基础，下行采用正交频分（OFDM）多址技术，上行采用单载波频分（SC-FDMA）多址技术，在20 MHz频谱带宽下能够提供下行100 Mb/s与上行50 Mb/s的峰值速率。

LTE TDD（亦称TD-LTE）系统采用了4种格式［2］的CRC：CRC24A、CRC24B、CRC16、CRC8。其生成多项式如下：

其中长度为24的CRC24A和CRC24B主要用于共享信道数据传输［3］，长度为16的CRC16主要用于下行控制信道和广播信道数据传输，长度为8的CRC8主要用于CQI（Control quality information）信息的传输。

循环冗余校验码（CRC）的基本原理

循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个次幂为N-K=R的多项式G（x）。根据G（x）可以生成K位信息的校验码，而G（x）叫做这个CRC码的生成多项式。

校验码的具体生成过程为：假设发送信息用信息多项式C（X）表示，将C（x）左移R位，则可表示成C（x）*2R，这样C（x）的右边就会空出R位，这就是校验码的位置。通过C（x）*2R除以生成多项式G（x）得到的余数就是校验码。

CRC算法分析及选择

CRC的校验原理非常简单，它要求发送方和接收方采用同一个生成多项式g（x），且g（x）的首位和末位的系数必须为l。编码时将待发送的数据t（x）除以g（x），得到的余数作为CRC校验码添加到t（x）的后面；译码时将接收到的数据r（x）除以g（x），如果余数为0，则说明校验正确，否则校验失败，从而判断数据帧是否出错。在工程应用中，常用的CRC校验算法主要有两种：查表生成法和块异或长除法。

这种算法的优点是运算量小、速度快、效率高；缺点是可移植性较差，且要事先计算出余式表，而不同长度的生成多项式的余式表不同，因此余式表会占用系统较大的存储空间，增大系统资源开销。

1.块异或长除法

块异或长除法是依据CRC校验码的产生原理实现的。算法描述如下：

（1）初始化，将寄存器初始化为0。

（2）在信息比特后添加CRC长度个0，终作为CRC添加的空间。

（3）读取一个数据块（块的大小由处理器的字的单位长度决定）。

（4）判断块的位是否为‘1’，若为‘1’则数据块与生成多项式做异或操作。

（5）将数据左移一位，如果当前块的剩余比特等于CRC生成多项式的长度，则转入步骤（3）；否则转入步骤（4）。

（6）如果所有数据都已经操作完毕，则计算结束，寄存器中的值为终求得的CRC。

这种算法的优点是算法简单、容易实现、修改灵活、可移植性好，对任意长度的生成多项式都适用；但因为它只能处理一位数据，因此计算效率低，运算量大。

如前所述，在TD-LTE系统中采用了4种格式的CRC，如果采用查表算法，则需要建立4张查找表，会占用系统较大的存储空间，且程序移植性差；如果采用块异或长除法，则又会出现计算效率低，运算量大的问题。

综上分析，结合项目需求及系统硬件配置，考虑到系统所采用的高效DSP处理器——TMS320C64x（主频可达到1.2 GHz）可以弥补块异或长除法的低效性，系统终采用块异或长除法来实现。

CRC编码规则

CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为（n，k）码。 它的编码规则是：

1.移位

将原信息码（kbit）左移r位（k+r=n）

2.相除

运用一个生成多项式g（x）（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。

非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：

0+0=1+1=0，1+0=0+1=1

即‘异’则真，‘非异’则假。

由此得到定理：a+b+b=a 也就是‘模2减’和‘模2加’直值表完全相同。

有了加减法就可以用来定义模2除法，于是就可以用生成多项式g（x）生成CRC校验码。

生成多项式应满足以下原则

a、生成多项式的位和位必须为1。

b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。

c、不同位发生错误时，应该使余数不同。

d、对余数继续做模2除，应使余数循环。

例子

例如：

g（x）=x4+x3+x2+1，（7，3）码，信息码110产生的CRC码就是：

对于g（x）=x4+x3+x2+1的解释：（都是从右往左数）x4就是第五位是1，因为没有x1所以第2位就是0。

11101 | 110，0000（设a=11101 ，b=1100000）

取b的前5位11000跟a异或得到101

101加上b没有取到的00得到10100

然后跟a异或得到01001

也就是余数1001

余数是1001，所以CRC码是1001， 传输码为：110，1001

标准的CRC码是，CRC-CCITT和CRC-16，它们的生成多项式是：

CRC-CCITT=x^16+x^12+x^5+1 　　CRC-16=x^16+x^15+x^2+1

CRC算法的DSP实现

1.硬件简介

TMS320C6000系列DSP是TI公司1997年2月推向市场的高性能DSP，综合了目前DSP性价比高、功耗低等优点。TMS320C64x系列在TMS320C6000 DSP芯片中处于水平，它不但提高了时钟频率，而且在体系结构上采用了VelociTI甚长指令集VLIW（Very Long Instruction Word）结构［5］，片内有8个独立功能单元的内核，每个周期可以并行执行8条32 bit指令，峰值速度4 800 MIPS，2组共64个32 bit 通用寄存器，32 bit 寻址范围，支持8/16/32/40位的数据访问，片内集成大容量SRAM，可达8 Mbit。由于其出色的运算能力、高效的指令集、大范围的寻址能力，使其特别适用于无线基站、测试仪表等对运算能力和存储量有高要求的应用场合。

2. CRC校验的DSP实现

因为系统采用了4种格式的CRC，如果对每种格式进行单独实现，不仅任务繁琐，而且增加了系统的代码量，更给代码测试和维护增加了难度。因此本实现采用统一实现，即同一个程序，支持系统中的所有CRC格式，仅需在程序头部增添一点格式判断的代码即可。

虽然TMS320C64x DSP处理器的字长为32 bit，但是为了兼容4种格式的CRC，终决定数据的分块长度为半字，即16 bit，这样做的目的就是为了支持CRC24，因为TMS320C64x DSP的寄存器在用作逻辑移位寄存器使用时，其有效长度为40 bit。

根据LTE协议，输入数据按大端模式输入。为了处理方便，每次读入半字都将其倒序，采用低端对齐的方式进行CRC除法，因此，CRC多项式也必须经过倒序。生成的CRC也是倒序的，需要再次倒序，然后进行加扰［2］（如果必要的话），添加到输入数据后面。倒序可使用指令“BITR”，简单易行。

输出数据仍为大端模式。由前面所述可知：CRC8的生成多项式倒序值为0x1b3；CRC16的生成多项式倒序值为0x10811；CRC24A的生成多项式倒序值为0x1be64c3；CRC24B的生成多项式倒序值为0x18c0003。

值得注意的是：输入数据后面应该多写入一个字的0，因为每次取半字处理，当剩余比特为15 bit且CRC为长24 bit时，组合起来也不会超过40 bit，避免特殊性的出现，以便统一处理。同时完成CRC计算过后，可以直接将CRC添加到原数据之后，而不担心其会覆盖系统中的其他数据，引起不必要的错误。

图1为CRC计算及添加的程序实现流程。当CRC格式为CRC16、CRC24A、CRC24B时，读取的个数据块（半字）在次内循环中将只作16次的移位，而没有异或操作，表面上看在这里应该加一个判断，如果是这种情况则直接将数据右移16 bit，然后接着处理第二个数据块。但这样会对后续的数据块造成麻烦，因为每个数据块到达此处都需判断，当数据量比较大时，会带来更大的开销，因此在程序流程中可以忽略此问题。

在接收端，CRC的校验与发送端的计算基本相同，只是由于LTE系统的特殊性，如果在发送端CRC曾被加扰过，则在接收端校验之前，应先从接收到的数据末尾截取出CRC进行解扰，然后再将解扰后的CRC添加回去，对整个接收数据进行CRC校验。如果CRC校验正确，则接收数据正确；否则接收数据错误，在此程序流程不再赘述。

性能分析

在DSP软件实现中，通过指令并行，尽量优化程序循环体［6］，减少或消除程序中的“NOP”指令。对于不同格式的CRC，根据它们所用的环境以及数据的大致长度，通过程序仿真运行，可以得到统计结果如表1。

表1的数据长度仅为个别举例，但不失一般性。从表中可以看出，虽然块异或长除法的运算量较大，但是当运用TMS320C64x芯片实现时，由于处理器的超高主频，其计算速率也非常快，完全可以忽略它的计算量。因此，本实现采用块异或长除法不仅简化了程序实现方法，还减少了模块程序代码，节约了系统存储空间。

关于LTF

LTE（Long Term Evolution，长期演进）项目是3G的演进，始于2004年3GPP的多伦多会议。LTE并非人们普遍误解的4G技术，而是3G与4G技术之间的一个过渡，是3.9G的标准，它改进并增强了3G的空中接入技术，采用OFDM和MIMO作为其无线网络演进的标准。在20MHz频谱带宽下能够提供下行326Mbit/s与上行86Mbit/s的峰值速率。改善了小区边缘用户的性能，提高小区容量和降低系统延迟。

结束语

本文从理论分析出发，根据TD-LTE系统特性，选择了一种的CRC校验算法，并在TMS320C64x芯片上加以实现，详细讲述了块异或长除法在DSP中的实现方法。程序运行结果表明，本实现能够满足LTE系统的需要，具有可行性和高效性。