冗余校验算法.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码字符数据信号及其双向偶校验位组成的典型传输矩阵(其中：前五行各字符的偶校验位组成的校验位列(最右边一列)，最下面一行由各列信号位的偶校验位组成)，该矩阵右下角的校验位则可按行或按列取校验位。

　　传输方向   　　　　　　　　　　　　   校验位列

　　　　       ←   　　　　　　1     0     1     1     0     1     1     1

　　　　　←   　　　　       1       1     0     1     0     1     1     1

　　　　　←   　　　　       0       0     1     1     1     0     1     0

　　　　　←   　　　　       1       0     0     0     1     0     1     1

　　　　　←   　　　　　　0     1     0     1     1     1     1     1

　　　　　←   　　　　       1       0     0     0     1     1     1     0   ←   校验位行

图1.4   典型双向偶校验传输矩阵

　　显然，如果被传输的字符信号矩阵中同时在偶数个行中的偶数个相同的列中出现错误，双向奇偶校验也是检查不出来的。

三、CRC循环冗余校验(Cyclic   Redundancy   Check)
　　1.CRC循环冗余校验的基本原理
　　发送器和接收器约定选择同一个由n+1个位组成的二进制位列P作为校验列，发送器在数据祯的K个位信号后添加n个位(n <K)组成的FCS祯检验列(Frame   Check   Sequence)，以保证新组成的全部信号列值可以被预定的校验二进制位列P的值对二取模整除；接收器检验所接收到数据信号列值(含有数据信号祯和FCS祯检验列)是否能被校验列P对二取模整除，如果不能，则存在传输错误位。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+1

　　CRC(CCITT)   =   X16+X12   +X5+1

　　CRC(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_unit_16 (clk,ready,indata,reset,crc);
 2 
 3 input clk;          
 4 input ready;
 5 input indata;
 6 input reset;
 7 output [15:0] crc;          //CRC checksum
 8     
 9 //Registers for CRC
10 reg  d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16;
11 
12 wire xor1, xor2, xor3; 
13 
14 assign xor1 = indata ^ d16;
15 assign xor2 = d5 ^ xor1;
16 assign xor3 = d12 ^ xor1;
17 
18 assign crc[0] = d1;
19 assign crc[1] = d2;
20 assign crc[2] = d3;
21 assign crc[3] = d4;
22 assign crc[4] = d5;
23 assign crc[5] = d6;
24 assign crc[6] = d7;
25 assign crc[7] = d8;
26 assign crc[8] = d9;
27 assign crc[9] = d10;
28 assign crc[10] = d11;
29 assign crc[11] = d12;
30 assign crc[12] = d13;
31 assign crc[13] = d14;
32 assign crc[14] = d15;
33 assign crc[15] = d16;
34 
35 
36 always @ (posedge clk or posedge reset) begin
37     if (reset) begin
38        d1 <= 0;
39        d2 <= 0;
40        d3 <= 0;
41        d4 <= 0;
42        d5 <= 0;
43        d6 <= 0;
44        d7 <= 0; 
45        d8 <= 0;
46        d9 <= 0;
47        d10 <= 0;
48        d11 <= 0;
49        d12 <= 0;
50        d13 <= 0;
51        d14 <= 0; 
52        d15 <= 0;
53        d16 <= 0; 
54       end   
55    else if (ready) begin
56        d1 <= xor1;
57        d2 <= d1;
58        d3 <= d2;
59        d4 <= d3;
60        d5 <= d4;
61        d6 <= xor2;
62        d7 <= d6; 
63        d8 <= d7;
64        d9 <= d8;
65        d10 <= d9;
66        d11 <= d10;
67        d12 <= d11;
68        d13 <= xor3;
69        d14 <= d13; 
70        d15 <= d14;
71        d16 <= d15; 
72      end
73 end   
74     
75 endmodule