CRC校验码系统设计.

1、 南华大学电气工程学院 通信原理课程设计设计题目： CRC校验码系统设计 专 业： 通信工程 学生姓名: 学 号 起迄日期: 2015年4月30日2015年5月15日指导教师: 系主任： 目录1概要.3 1.1 循环码的介绍.31.2校验原理32 MATLAB基本介绍.52.1 MATLAB的介绍.52.2 MATLAB的组成部分.52.3 MATLAB的特点.52.4 MATLAB的优势.63 设计原理63.1编码器模块63.2译码器模块74 设计思想94.1程序流程图95 CRC编解码系统的设计及实现.105.1程序设计105.2系统仿真126 总结13参考文献14 摘要 CRC(Cycl

2、ical Redundancy Checking)循环冗余校验码是一种重要的线性分组码，通过多项式除法检测错误，是在数据通信和数据检测中广泛应用的检错校验的循环码。 本设计研究了CRC循环冗余校验码的原理，以及利用C语言对其进行了编程和编译仿真，实现了CRC循环冗余校验码的编码及校验，在接收端收到通过校验的码，从而确定传输过程是否出错，得到的结论和理论上是一致的。在本次计中，使用的系统开发平台为MATLAB。设计方案中，实现了编码，纠错，译码。从循环的原理出发，讨论循环码编译码系统的特点。以一个（15，11）循环码的编译码的设计与仿真为例 ,使用C语言对该系统进行了设计 。 关键词: MATL

3、AB;C语言 ;CRC循环冗余校验码 1.概要1.1循环码的介绍 随着计算机通信的日益发展 ,传输数据的场合越来越多。串行数据的差错检验是保证数据传输正确的必要手段 ,而循环码是差错码中最常用的一种编码。 循环冗余校验码（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)*2的R

4、次方，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2的R次方除以生成多项式G(x)得到的余数就是校验码。 循环码是线性分组码中最重要的一种子类 ,它除了具有分组码的线性外 ,还具有循环性 ,其码字结构一般用符号( n , k)表示 ,其中 , n 是该码组中的码元数 , k 是信息码元位数 , r = n - k 是监督码元位数1 。循环码具有许多特殊的代数性质 ,这些性质有助于按照要求的纠错能力系统地构造这类码 ,能简化译码算法 ,并且目前发现的大部分线性码与循环码有密切关系。 已有循环码编译码系统大多以标准逻辑器件(如中小规模 TTL 系列、 CMOS系列)按传统数字

5、系统设计方法设计而成 ,其主要缺点是逻辑规模小、功耗大、 可靠性低。随着大规模、 超大规模集成电路的发展 ,以及电子设计自化水平的提高 ,这种制约正在被逐渐消除。 1.2 校验原理 1、循环校验码（CRC码）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。 2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为0和1取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。 3、CRC码集选择的原则：若设码字长度为N，信息字段为K位，校验字段为R

6、位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得V(x)=A(x)g(x)=xRm(x)+r(x);其中: m(x)为K次信息多项式， r(x)为R-1次校验多项式， g(x)称为生成多项式：g(x)=g0+g1x+ g2x2+.+g(R-1)x(R-1)+gRxR发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。 4、CRC校验码软件生成方法： 借助于多项式除法，其余数为校验字段。例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1 假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代

7、码为: 11001 x4m(x)=x10+x8+x7+x4 对应的代码记为：10110010000；采用多项式除法: 得余数为: 1010 (即校验字段为：1010）发送方：发出的传输字段为: 1 0 1 1 0 0 1 1 0 10 信息字段 校验字段接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）如果能够除尽，则正确。 2 MATLAB基本介绍2.1 MATLAB的介绍MATLAB 是美国MathWorks公司出品的商业数学软件，主要包括MATLAB和Simulink两大部分。MATLAB是矩阵实验室（Matrix Laboratory）的简称。MATLAB可以进行矩阵

8、运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完相同的事情简捷得多，并且mathwork也吸收了像Maple等软件的优点,使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C，FORTRAN，C+ ，JAVA的支持。可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用，此外许多的MATLAB爱好者都

9、编写了一些经典的程序，用户可以直接进行下载就可以用。2.2 MATLAB的组成部分（1）开发环境(development Environment)：一组图形化用户接口工具和组件的集成：MATLAB桌面、命令窗口、命令历史窗口、编辑调试窗口及帮助信息、工作空间、文件和搜索路径等浏览器;（2）MATLAB数学函数库：(Math Function Library)基本函数：求和、正弦、余弦和复数运算等；特殊函数：矩阵求逆、矩阵特征值、贝塞尔函数和快速付里叶变换等;（3）MATLAB 语言：(MATLAB Language)一种高级编程语言，包括控制流的描述、函数、数据结构、输入输出及面对对象编程；（

10、4）句柄图形：(Handle Graphics) 可以对各种图形对象进行更为细腻的修饰和控制，建立完整的图形界面的应用程序;（5）应用程序接口：(Applied Function Interface) MATLAB的应用程序接口允许用户使用C或FORTRAN语言编写程序与MATLAB连接。2.3 MATLAB的特点 （1）此高级语言可用于技术计算;（2）此开发环境可对代码、文件和数据进行管理;（3）交互式工具可以按迭代的方式探查、设计及求解问题;（4）数学函数可用于线性代数、统计、傅立叶分析、筛选、优化以及数值积分等;（5）二维和三维图形函数可用于可视化数据;（6）各种工具可用于构建自定义的图

11、形用户界面;（7）各种函数可将基于MATLAB的算法与外部应用程序和语言（如 C、C+、Fortran、Java、COM 以及 Microsoft Excel）集成。2.4 MATLAB的优势（1）友好的工作平台和编程环境（2）简单易用的程序语言（3）强大的科学计算机数据处理能力（4）出色的图形处理功能（5）应用广泛的模块集合工具箱（6）实用的程序接口和发布平台（7）应用软件开发（包括用户界面） 3 设计原理3.1编码器模块根据给定的 (n,k) 值选定生成多项式 g (x)，即从 xn+1 的因子中选一个 (n-k） 次多项式作为，假设给定信息码组为 m (x)= (mk-1,mk-2.m0

12、)，其次数小于 k，则xn-km (x) 的次数必定小于n。用 g (x) 除xn-km (x)，得到余式 r (x)，r (x) 的次数必定小于 g (x) 的次数，即小于 (n-k)。将此余式 r (x) 加于信息位之后作为监督位，即 r (x) 和xn-km (x) 相加，得到多项式必定是一个码组多项式。因为它必定能被 g (x) 整除，且商的次数不大于 (k-1)。根据以上原理，循环码的编码步骤可以归纳如下：（1） 用xn-k 乘信息码 m (x)，这一运算实际上是在信息码后附加上 (n-k)个“0”。（2） 用 g (x) 除xn-km (x)，得到商 Q (X)，(3) 编出的码组

13、 T (x) =xn-km (x) +r (x)。由此可见，编码的核心是如何确定余式 r (x)，找到 r (x)后，可直接将其所代表的编码位附加到信息位之后，完成编码。编码电路可采用 （n-k） 级反馈移位寄存器和异或门 （模2 加） 组成的除法电路实现。以生成矩阵 g (x) =x3+x+1 生成 （7，4） 循环码的编码器为例，其除法电路如图3. 1 所示。图3.1 除法电路图此移位寄存器的个数与 g (x) 的次数相等，并且 g (x) 的系数 1 表示有反馈，0 表示无反馈。每个寄存器的初始值均为0，将码组 m3m2m1m0 依次串行送入电路的最高端，相当于对其后面补三个零，除法电路

14、经过四次移位后，寄存器 D1D2D3里的数即为余式 r (x) 。因此，编出码组 T (x) = (m3m2m1m0D1D2D3)。实际设计中，要有一个信号 K 来控制码组的输入与输出，在 K 的控制下，输入的信息码元，一方面串行输入信道，另一方面进入除法电路进行计算。当输入最末一位信息码元结束时，K 信号也为零，在时钟脉冲作用下，移位寄存器将计算结果送往信道，即在最末一位信息码元后附加监督码。3.2译码器模块接收端译码的要求有两个：检错和纠错。（1） 检错若接收码组 R (x) 与发送码组相同，即 R (x) =T (x)，则R (x) 必定能被 g (x) 整除；若在传输中发生错误，即 R

15、 (x)T (x)，则 R (x) 被 g (x) 除时可能除不尽而有余项，从而发生错误。因此，可以以余项是否为零来判断接收码组中有无错误。但是，有错码的接收码组也有可能被 g (x) 整除，这时的错码就不能检出。这种错误称为不可检错误，其误码必定超过了此编码的检错能力。（2） 纠错为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。以下是为纠错而设计的。由于 （7，4） 循环码的最小码距为 d0=3，由 d02t+1 得，此循环码只能纠正一个错码。当经过信道传输后发生错误时，接收码组多项式 R

16、 (x) 不再是的倍式。其中 S (x) 是 R (x) 除以 g (x) 后的余式，是不大于 r-1次的码组多项式，称为伴随多项式或校正子多项式。时接收码组多项式 可表示为发送码组多项式 T (x) 与差错多项式 E (x) 之和，即：R (x) =T (x) +E (x)综合以上式子，我们由 就可进一步确定 E (x)：S (x) =remT (x) +E (x) =rem E (x) g (x) g (x)对于一个 S (x)，E (x) 可能有多种形式。由 S (x) 确定 E(x) 时同样使用最大似然比准则。对最小码重的差错多项式 E(x)，由上式求出对应的伴随多项式 S (x)，将

17、 E (x) 与 S (x) 的对应关系列成译码表。当收到任一码组 R (x) 后，利用 S (x)=rem R (x) /g (x) 求出 S (x)，对照译码表找到 E (x)，再用R (x) =T (x) +E (x) 求 T (x)，即 T (x) =R (x) -E (x) 为已经纠错的原发送码组。纠错完毕之后，只需要取纠错后的前四位，即为所译码元。而在实际电路设计过程中，由于二进制只有 0 与 1 两种状态，知道错误位置后，可以直接对该位置的码元取反即可。综上所述，纠错的步骤如下：（1）把 接 收 码 组 R ( x) 送 入 除 法 电 路 ， 得 到 余 数D1D2D3 即为伴

18、随矩阵 S (x)。（2）由典型生成矩阵 G 和典型监督矩阵 HT 之间的关系可进一步求得，再由 S=E.HT 可得错误图样 E(x)，这样就可以确定错码的位置。（3）根据错误的码位，对该码位的码元取反输出便可得到原发送码组 T (x)。其中，T (x) 的前四位即为译出码元 m(x)。图3.2 译码器示意图 4 设计思想4.1程序流程图 图1 CRC编码程序流程图 5 CRC编解码系统的设计及实现取n =15，r =9，k =6，生成多项式G(X)=X9+X6+X5+X4+X+1 ，设计了CRC编译码系统，其框图如图1 所示。 该系统包含发端电路和收端电路两部份。发端有信码发生器模块、编码器

19、模块，收端有模拟错码发生器模块、错码位置计算模块、纠错单元模块。其中错码位置计算单元和纠错单元合在一起构成译码器。 5.1程序设计MATLAB程序编写% CRC 编码主程序clear;clc;close all;uncode_sequence=randint(1,11)sequence_length = length(uncode_sequence); % 得到原始信号长度crc_ccitt = 1 1 0 0 1 ; % 常用的CRC生成多项式add_bit = zeros(1,4); % 添加冗余比特位crc_coded_sequence = uncode_sequence zeros(1

20、,4); % 初始化输出检错码序列uncode_sequence = uncode_sequence add_bit;remainder_bits = uncode_sequence; % 初始化余数数组for k = 1:sequence_length % 开始循环计算长除得到最终余数 add_zeros = zeros(1,sequence_length-k); % 加入冗余位参与模2运算 register_bits = crc_ccitt add_zeros; % 构造除数数组 if remainder_bits(1) = 0 % 被除数第一位为0则将除数所有位置0 register_b

21、its = zeros(1,length(register_bits); endremainder_bits = bitxor(register_bits,remainder_bits); % 将除数与被除数进行异或操作register_bits = crc_ccitt; % 将寄存器恢复为除数数组remainder_bits(1) = ; % 去除模2后得到的被除数的第1位endadd_len = length(crc_coded_sequence) - length(remainder_bits); % 生成余数序列的冗余位以叠加到编码序列remainder_bits = zeros(1,

22、add_len),remainder_bits; % 余数序列添加冗余crc_coded_sequence = crc_coded_sequence + remainder_bits % 合成编码序列sequence_length = length(crc_coded_sequence); % 得到冗余编码的长度original_sequence = crc_coded_sequence; % 初始化输出序列 crc_ccitt = 1 1 0 0 1; %常用的CRC生成多项式 remainder_bits = crc_coded_sequence; % 初始化余数数组 cycle_leng

23、th = sequence_length-length(crc_ccitt)+1; % 计算长除法的循环周期 for k = 1:cycle_length % 开始循环计算长除得到最终余数 add_zeros = zeros(1,cycle_length-k); % 加入冗余位参与模2运算 register_bits = crc_ccitt add_zeros; % 构造除数数组 if remainder_bits(1) = 0 % 被除数第一位为0则将除数所有位置0 register_bits = zeros(1,length(register_bits); end remainder_bi

24、ts = bitxor(register_bits,remainder_bits); % 将除数与被除数进行异或操作 register_bits = crc_ccitt; % 将寄存器恢复为除数数组 remainder_bits(1) = ; % 去除模2后得到的被除数的第1位 end if sum(remainder_bits) = 0 % 传输码元中没有发生奇数个错误 original_sequence = crc_coded_sequence(1:cycle_length) else err = 1 % 码元传输发生错误5.2系统仿真运行结果及其分析运行结果MATLAB的运行结果如下：

25、图2 程序仿真图 结果分析CRC校验的基本思想是利用线性编码理论，在发送端根据要传送一个n比特的帧或报文，发送器生成一个r比特的序列，称为帧检验序列（FCS）。这样形成的帧将由（n+r）比特组成。这个帧刚好能被某个预先规定的数整除。接收器用相同的数去除外来的帧，结果无余数，则认为无差错。循环冗余校验与奇偶校验不同，或者是一个字符校验一次，而前者是一个数据块校验一次。在同步通信中，几乎都使用这种校验方法。二进制多项式的加减运算为模2加减运算，即两个码多项式相加时，对应系数进行模2加减。所谓模2加减就是各位做不带进位、借位的按位加减。这种加减运算实际上是逻辑上的异或运算，即加法和减法等价。信息多项式和余数多项式可以合并成一个新的多项式（称为循环码的码多项式），则该多项式是生成多项式的整数倍，即能被声称多项式整除。根据这一原理，在发送端用信息码多项式除以生成多项式所得的余数多项式就是所要加的监督位。将循环码的码多项式除以生成多项式，若能除尽，说明传输正确，否则说明出错。CRC校验的关键是如何求出余数，此余数即为校验码（CRC校验码）。以前用数字电路来实现，而现