CRC校验码的原理.doc

CRC校验码的原理在通信与数字信号处理等领域中循环冗余校验码（Cyclic Redundancy Check,CRC）是一种很常用的设计。一般来说数据通信中的编码可以分为信源编码和信道编码两大类，其中，为了提高数据通信的可靠性而采取的编码称为信道编码，即抗干扰编码。在通信系统中，要求数据传输过程中的误码率足够低，而为了降低数据传输过程中的误码率，经常采用的一种方法是差错检测控制。在实际的通信系统中，差错检测控制的主要方法又3种：前向纠错（FEC），自动重发（ARQ）和反馈检验法。FEC指接收端不仅能够在收到的信码中发现错码，而且还能够纠正错码。一般来说，这种方法不需要反向信道，实时性很好，不过设备较复杂。ARQ是指接收端在收到的信码中检测出错码时，即设法通知发送端重新发送信号，直到能够正确接收为止。通常，这种方法只用来检测误码，而且只能在双向信道中使用。反馈检验法是指接收端将收到的信码一字不差地转发回发送端，同时与原发送信码进行比较，如果有错，则发端重发。这种方法的原理和设备都比较简单，但需要双向信道的支持，而且传输效率低下；通过实践检验，在这三中方法中，如果传输过程中的误码率较低，那么采用前向纠错法比较理想，但如果误码率较高时，这种方法又会出现“乱纠”的现象；在网络通信中，广泛的采用差错检测方法时自动请求重发，这种方法只要检错功能即可；反馈检验法时前向纠错法和自动请求重发的结合。在实现差错检测控制的众多方法中，循环冗余校验就是一类重要的线性分组码。它时一种高效的差错控制方法，它广泛应用于测控及数据通信领域，同时具有编码和解码方法简单，检错能力强，误判概率很低和具有纠错能力等优点。循环冗余校验码实现的方法CRC的基本原理就是在一个P位二进制数据序列之后附加一个R位二进制检验码序列，从而构成一个总长位N=P+R位的二进制序列。例如，P位二进制数据序列D=dddd，R位二进制检验码R= rrrr,那么所得到的这个N位二进制序列就是M=dddd rrrr，这里附加在数据序列之后的CRC码与数据序列的内容之间存在着某种特定的关系。如果在数据传输过程中，由于噪声或传输特性不理想而使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏。可见在数据的接收端通过检查这种特定关系，可以很容易地实现对数据传输正确性的检验。在CRC中，检验码R使通过对数据序列D进行二进制除法取余式运算得到的，他被一个称为生成多项式的（r+1）位二进制序列G=gggg来除，具体的多项式除法形式如下： =Q(x)+其中，表示将数据序列D左移r位，即在D的末尾再增加r个0位；Q（x）代表这一除法所得的商，R（x）就是所需的余式。此外，这一运算关系还可以表示为 通过上面CRC基本原理的介绍，可以发现生成多项式使一个非常重要的概念，它决定了CRC的具体算法。目前，生成多项式具有一下一些通用标准，其中CRC-12，CRC-16，CRC-ITU和CRC-32是国际标准。CRC-4 CRC-12 CRC-16 CRC-ITU CRC-32 CRC-32c CRC-ITU的硬件实现方法 Data_in该图反映了CRC-ITU用硬件实现的原理，从左至右分别代表16个移位寄存器，左边代表高位右边代表低位，可以分析得知，在生成多项式的非零项指数对应的寄存器前有一个异或门，这种电路能够实现相应的模二除法。但是这种电路实现的却是串行输入，在高速场合下，这种方案势必会造成编码效率低下，误码率高的弊端，为了解决这个问题，提高编码效率和正确率，要求能够实现并行算法，在一个时钟周期内得到一个多位数据的CRC码。CRC的并行算法原理与实现在上面已经给出了CRC的硬件原理，我们可以依此得到并行算法的原理。因为CRC硬件的实现方法是利用反馈移位寄存器外加异或门进行运算得来(开始计算时，所有的寄存器要清零)，假如说我们输入一个数据串，每输入一个比特的数据时，上一状态的所有寄存器的值，都会进行移位或进行异或运算后移位。当前状态与前一状态有着紧密的联系，而这种关系就通过硬件电路的形式表示出来，同理，以此类推，那么若干个状态后的状态与初始状态也有很紧密的联系，不难看出，初始状态为全零，8个比特串行输入后又为一个状态，8个比特串行再输入后，此时的状态与上一个8比特后的状态又有着固定的联系。可见，只要我们找到他们之中的这种联系，那么我们就可以得到每次运算8位数据的CRC并行算法。我们假设寄存器D15-D0的初始状态为A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P，输入的数据为C7,C6,C5,C4,C3,C2,C1,C0,当所有数据都输入完时，根据硬件电路图可以得到由初始状态和各输入数据构成的各现态的函数。寄存器初态数据1数据2数据3数据4数据5数据6数据7数据8C7C6C5C4C3C2C1C0D15ABCDE+A+C7F+B+C6G+C+C5H+D+C4I+E+A+C7+C3D14BCDE+A+C7F+B+C6G+C+C5H+D+C4I+E+A+C7+C3J+F+B+C6+C2D13CDE+A+C7F+B+C6G+C+C5H+D+C4I+E+A+C7+C3J+F+B+C6+C2K+G+C+C5+C2D12DE+A+C7F+B+C6G+C+C5H+D+C4I+E+A+C7+C3J+F+B+C6+C2K+G+C+C5+C1C+A+C7+H+D+C4+C0D11EFGHIJKC+A+C7M+B+C7D10FGHIJKL+A+C7M+B+C6N+C+C5D9GHIJKL+A+C7M+B+C6N+C+C5O+D+C4D8HIJKL+A+C7M+B+C6N+C+C5O+D+C4P+E+A+C7+C3D7IJKL+A+C7M+B+C6N+C+C5O+D+C4P+E+A+C7+C3A+C7+F+B+C6+C2D6JKL+A+C7M+B+C6N+C+C5O+D+C4P+E+A+C7+C3A+C7+F+B+C6+C2B+C6+G+C+C5+C1D5KL+A+C7M+B+C6N+C+C5O+D+C4P+E+A+C7+C3A+C7+F+B+C6+C2B+C6+G+C+C5+C1C+C5+H+D+C4+C0D4LMNOPA+C7B+C6C+C5D+C4D3MNOPA+C7B+C6C+C5D+C4E+A+C7+C3D2NOPA+C7B+C6C+C5D+C4E+A+C7+C3F+B+C6+C2D1OPA+C7B+C6C+C5D+C4E+A+C7+C3F+B+C6+C2G+C+C5+C1D0PA+C7B+C6C+C5D+C4E+A+C7+C3F+B+C6+C2G+C+C5+C1H+D+C4+C0通过以上推导，我们可以得到D(15)=D(7)+D(11)+D(15)+C(7)+C(3)D(14)=D(6)+D(10)+D(14)+C(6)+C(2)D(13)=D(5)+D(9)+D(13)+C(5)+C(1)D(12)=D(4)+D(15)+C(7)+D(8)+D(12)+C(4)+C(0)D(11)=D(3)+D(14)+C(6)D(10)=D(2)+D(13)+C(5)D(9)=D(1)+D(12)+C(4)D(8)=D(0)+D(11)+D(15)+C(7)+C(3)D(7)=D(15)+C(7)+D(10)+D(14)+C(6)+C(2)D(6)=D(14)+C(6)+D(9)+D(13)+C(5)+C(1)D(5)=D(13)+C(5)+D(8)+D(12)+C(4)+C(0)D(4)=D(12)+C(4)D(3)=D(11)+D(15)+C(7)+C(3)D(2)=D(10)+D(14)+C(6)+C(2)D(1)=D(9)+D(13)+C(5)+C(1)D(0)=D(8)+D(12)+C(4)+C(0)CRC的VHDL语言实现LIBRARY IEEE;USE IEEE.STD_LOGIC_1164.ALL;USE IEEE.STD_LOGIC_UNSIGNED.ALL;ENTITY CRC ISPORT(CLK,CLR:IN STD_LOGIC; DATA_IN :IN STD_LOGIC_VECTOR(7 DOWNTO 0); DATA_OUT:OUT STD_LOGIC_VECTOR(15 DOWNTO 0);END CRC;ARCHITECTURE A OF CRC ISSIGNAL Q:STD_LOGIC_VECTOR(7 DOWNTO 0);SIGNAL D:STD_LOGIC_VECTOR(15 DOWNTO 0);BEGINPROCESS(CLR,CLK)BEGIN IF CLR=1THEN D0); ELSIF CLKEVENT AND CLK=1THEN Q=DATA_IN; D(0)=D(8) XOR D(12) XOR Q(4) XOR Q(0); D(1)=D(9) XOR D(13) XOR Q(5) XOR Q(1); D(2)=D(10) XOR D(14) XOR Q(6) XOR Q(2); D(3)=D(11) XOR D(15) XOR Q(7) XOR Q(3); D(4)=D(12) XOR Q(4); D(5)=D(13) XOR Q(5) XOR D(8) XOR D(12) XOR Q(4) XOR Q(0); D(6)=D(14) XOR Q(6) XOR D(9) XOR D(13) XOR Q(5) XOR Q(1); D(7)=D(15) XOR Q(7) XOR D(10) XOR D(14) XOR Q(6) XOR Q(2); D(8)=D(0) XOR D(11) XOR D(15) XOR Q(7) XOR Q(3); D(9)=D(1) XOR D(12) XOR Q(4); D(10)=D(2) XOR D(13) XOR Q(5); D(11)=D(3) XOR D(14) XOR Q(6); D(12)=D(4) XOR D(15) XOR Q(7) XOR D(8) XOR D(12) XOR Q(4) XOR Q(0); D(13)=D(5) XOR D(9) XOR D(13) XOR Q(5) XOR Q(1); D(14)=