冗余校验算法.doc

错误检测与修正 (Error Check & Correct) 在数字数据通信中，由发送器发送的数据信号祯 (Frame) 在经由网络传到接收器后，由于多种原因可能导致错误位 (bit errors)的出现，因此必须由接收器采取一定的措施探测出所有的错误位，并进而采取一定的措施予以修正一、错误检测的基本原理 (Principle of Error Check) 发送器向所发送的数据信号祯添加错误检验码 (Check Bits)，并取该错误检测码作为该被传输数据信号的函数； 接收器根据该函数的定义进行同样的计算， 然后将两个结果进行 比较：如果结果相同，则认为无错误位；否则认为该数据祯存在有错误位 一般说来，错误检测可能出现三种结果：在所传输的数据祯中未探测到，也不存在错误位； 所传输的数据祯中有一个或多个被探测到的错误位，但不存在未探测到的错误位； 被传输的数据祯中有一个或多个没有被探测到的错误位显然我们希望尽可能好地选择该检测函数， 使检测结果可靠， 即：所有的错误最好都能 被检测出来；如检测出现无错结果，则应不再存在任何未被检测出来的错误实际采用的错误检测方法主要有两类：奇偶校验 (Parity)和CRC循环冗余校验(Cyclic Redundancy Check) 。

二、奇偶校验 (Parity)1. 单向奇偶校验单向奇偶校验(Row Parity)由于一次只采用单个校验位，因此又称为单个位奇偶校验(Single Bit Parity)发送器在数据祯每个字符的信号位后添一个奇偶校验位，接收器对该奇偶校验位进行检查典型的例子是面向 ASCII 码的数据信号祯的传输，由于 ASCII 码 是七位码，因此用第八个位码作为奇偶校验位单向奇偶校验又分为奇校验 (Odd Parity)和偶校验(Even Parity)，发送器通过校验位对所传输信号值的校验方法如下：奇校验保证所传输每个字符的 8 个位中 1的总数为奇数；偶校验则保证每个字符的 8 个位中 1 的总数为偶数显然，如果被传输字符的 7 个信号位中同时有奇数个 (例如 1、3、5、7)位出现错误，均 可以被检测出来；但如果同时有偶数个 (例如 2、4、6)位出现错误，单向奇偶校验是检查不出来的一般在同步传输方式中常采用奇校验，而在异步传输方式中常采用偶校验2. 双向奇偶校验为了提高奇偶校验的检错能力，可采用双向奇偶校验 (Row and Column Parity)， 也又称为双向冗余校验 (Vertical and Longitudinal Redundancy Checks)。

图 1.4 给出了由 5 个 ASCII 码字符数据信号及其双向偶校验位组成的典型传输矩阵 (其中：前五行各字符的偶校验位组成的校验位列 (最右边一列 )，最下面一行由各列信号位的偶 校验位组成 )，该矩阵右下角的校验位则可按行或按列取校验位传输方向 校验位列101101111101011100111010100010110 101111110001110 &- 校验位行图1.4 典型双向偶校验传输矩阵显然，如果被传输的字符信号矩阵中同时在偶数个行中的偶数个相同的列中出现错误， 双向奇偶校验也是检查不出来的三、CRC循环冗余校验（Cyclic Redundancy Check）1.CRC循环冗余校验的基本原理发送器和接收器约定选择同一个由 n+1个位组成的二进制位列 P作为校验列，发送器在数据祯的K个位信号后添加n个位（n

P被称为CRC循环冗余校验列，正确选择 P可以提高CRC冗余校验的能力注：对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR 异或运算，即：1 XOR 1=0，0 XOR 0=0，1 XOR 0=1）可以证明，只要数据祯信号列 M和校验列P是确定的，则可以唯一确定 FCS祯检验列（也称为CRC冗余检验值）的各个位FCS帧检验列可由下列方法求得：在 M后添加n个零后对二取模整除以 P所得的余数例如：如要传输的M=7位列为1011101,选定的P校验二进制位列为10101（共有n+1=5位）， 对应的FCS帧校验列即为用 1011101 0000（共有M+n=7+4=11位）对二取模整除以 10101 后的余数0111（共有n=4位）因此，发送方应发送的全部数据列为 10111010111接收方将收到的11位数据对二取模整除以 P校验二进制位列10101，如余数非0，则认为有传输错误位2.CRC循环冗余校验标准多项式 P（X）为了表示方便，实用时发送器和接收器共同约定选择的校验二进制位列 P常被表示为具有二进制系数(1或0)的CRC标准校验多项式 P(X)1)CRC循环冗余校验常用的标准多项式 P(X)常用的CRC循环冗余校验标准多项式如下:CRC（16 位）= X16+X15+X2+1CRC（CCITT）= X16+X12 +X5+1CRC（32 位） = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1以CRC(16位)多项式为例，其对应校验二进制位列为 1 1000 0000 0000 0101。

注意：这儿列出的标准校验多项式 P(X)都含有(X+1)的多项式因子；各多项式的系数均为二进制数，所涉及的四则运算仍遵循对二取模的运算规则2)CRC循环冗余校验标准多项式 P(X)的检错能力CRC循环冗余校验具有比奇偶校验强得多的检错能力可以证明：它可以检测出所有 的单个位错、几乎所有的双个位错、低于 P(X)对应二进制校验列位数的所有连续位错、大于或等于P(X)对应二进制校验列位数的绝大多数连续位错但是，当传输中发生的错误多项式 E(X)能被校验多项式 P(X)对二取模整除时，它就不可能被P(X)探测出来，例如当 E(X)=P(X)时四、错误修正(Error Correction)对数据信号祯传输过程中的位错进行修正的方法主要有两种：由发送器提供错误修正码，然后由接收器自己修正错误； 在接收器发现接收到的错误祯中有位错误时，通知发送器重新发送数据信号祯前一种方法中的错误修正码需要发送器由被传送数据信号祯计算得到， 然后添加到数据祯的后面，其长度几乎等于数据位数，导致效率降低 50%，实际采用不多；一般采用后一种较为有效的重发送方法1 module crc_uni t_16 (clk,ready,i ndata,reset,crc);22 in put clk;3 in put ready;4 in put in data;5 in put reset;6 output [ 15:0] crc; //CRC checksum89 //Registers for CRCreg d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16;1011121314151617181920212223242526272829303132333435363738394041424344454647484950515253wire xor1, xor2, xor3;assignxor1=in data A d16assignxor2=d5 a xorl;assignxor3= d12 A xor1;assigncrc[0] = d1;assigncrc[1] = d2;assigncrc[2] = d3;assigncrc[3] = d4;assigncrc[4] = d5;assigncrc[5] = d6;assigncrc[6] = d7;assigncrc[7] = d8;assigncrc[8] = d9;assigncrc[9] = d10;assigncrc[10] = d11;assigncrc[11] = d12;assigncrc[12] = d13;assigncrc[13] = d14;assigncrc[14] = d15;assigncrc[15] = d16;reg d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16;reg d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16;always@ ( posedge clkor posedge reset)beginreg d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16;if (reset) begind1 <= 0;d2 <= 0;d3 <= 0;d4 <= 0;d5 <= 0;d6 <= 0;d7 <= 0;d8 <= 0;d9 <= 0;d10 <= 0;d11 <= 0;d12 <= 0;d13 <= 0;d14 <= 0;d15 <= 0;d16 <= 0;54555657585960616263646566676869707172737475endbeginelse if (ready) d1 <= xor1;d2 <= d1;d3 <= d2;d4 <= d3;d5 <= d4;d6 <= xor2;d7 <= d6;d8 <= d7;d9 <= d8;d10 <= d9;d11 <= d10;d12 <= d11;d13 <= xor3;d14 <= d13;d15 <= d14;d16 <= d15;endendendmodule。