冗余校验算法

《冗余校验算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、错误检测与修正(Error Check & Correct)　　在数字数据通信中，由发送器发送的数据信号祯(Frame)在经由网络传到接收器后，由于多种原因可能导致错误位(bit errors)的出现，因此必须由接收器采取一定的措施探测出所有的错误位，并进而采取一定的措施予以修正。一、错误检测的基本原理(Principle of Error Check)　　发送器向所发送的数据信号祯添加错误检验码(Check Bits)，并取该错误检测码作为该被传输数据信号的函数；接收器根据该函数的定义进行同样的计算，然后将两个结果进行比较：如果结果相同，则认为无错误位；否则认为

2、该数据祯存在有错误位。一般说来，错误检测可能出现三种结果： 在所传输的数据祯中未探测到，也不存在错误位；  所传输的数据祯中有一个或多个被探测到的错误位，但不存在未探测到的错误位；  被传输的数据祯中有一个或多个没有被探测到的错误位。 　　显然我们希望尽可能好地选择该检测函数，使检测结果可靠，即：所有的错误最好都能被检测出来；如检测出现无错结果，则应不再存在任何未被检测出来的错误。　　实际采用的错误检测方法主要有两类：奇偶校验(Parity)和CRC循环冗余校验(Cyclic Redundancy Check)。　　二、奇偶校验(Parity)　　1.单向奇偶校验

3、　　单向奇偶校验(Row Parity)由于一次只采用单个校验位，因此又称为单个位奇偶校验(Single Bit Parity)。发送器在数据祯每个字符的信号位后添一个奇偶校验位，接收器对该奇偶校验位进行检查。典型的例子是面向ASCII码的数据信号祯的传输，由于ASCII码是七位码，因此用第八个位码作为奇偶校验位。　　单向奇偶校验又分为奇校验(Odd Parity)和偶校验(Even Parity)，发送器通过校验位对所传输信号值的校验方法如下：奇校验保证所传输每个字符的8个位中1的总数为奇数；偶校验则保证每个字符的8个位中1的总数为偶数。　　显然，如果被传输字符

4、的7个信号位中同时有奇数个(例如1、3、5、7)位出现错误，均可以被检测出来；但如果同时有偶数个(例如2、4、6)位出现错误，单向奇偶校验是检查不出来的。　　一般在同步传输方式中常采用奇校验，而在异步传输方式中常采用偶校验。　　2.双向奇偶校验　　为了提高奇偶校验的检错能力，可采用双向奇偶校验(Row and Column Parity)，也又称为双向冗余校验(Vertical and Longitudinal Redundancy Checks)。　　图1.4给出了由5个ASCII码字符数据信号及其双向偶校验位组成的典型传输矩阵(其中：前五行各字符的偶校验位组成

5、的校验位列(最右边一列)，最下面一行由各列信号位的偶校验位组成)，该矩阵右下角的校验位则可按行或按列取校验位。　　传输方向 　　　　　　　　　　　　 校验位列　　　　   ← 　　　　　　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 

6、 0  1  1  1  0 ← 校验位行图1.4 典型双向偶校验传输矩阵　　显然，如果被传输的字符信号矩阵中同时在偶数个行中的偶数个相同的列中出现错误，双向奇偶校验也是检查不出来的。三、CRC循环冗余校验(Cyclic Redundancy Check)　　1.CRC循环冗余校验的基本原理　　发送器和接收器约定选择同一个由n+1个位组成的二进制位列P作为校验列，发送器在数据祯的K个位信号后添加n个位(n

7、数据信号列值(含有数据信号祯和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，选定

8、的P校验二