数字通讯的错误检测与纠正.ppt

《数字通讯的错误检测与纠正.ppt》由会员分享，可在线阅读，更多相关《数字通讯的错误检测与纠正.ppt（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、错误检测与纠正1 错误类型错误多比特错误突发错误单比特错误单比特错误 单比特错误是指在给定数据单元（例如一个字节，一个字符，数据单元，或是数据包）中只有一个比特被从0变为1或是从1变为0。0变到1发送接收0 0 0 0 01000 0 0 0 11001.2 多比特错误 多比特错误是指数据单元中两个或两个以上不连续的比特从0变为1或是从1变为0。0 1 0 0 01000 0 0 0 11002个错误发送接收1.3 突发错误 突发错误指数据单元中两个或两个以上连续的比特从0变为1或是从1变为0。0 1 0 0 0010 0 1 0 0 01010 1 0 1 1101 0 1 0 0 0101

2、突发错误发送接收2 错误检测2.1 冗余 在数据通信中采用四种类型的冗余校验技术：垂直冗余校验（VRC）（也称为奇偶校验），纵向冗余校验（LRC），和循环冗余校验（CRC），是在物理层实现而在数据链路层被使用的。而第四种技术，校验和技术，主要由网络层，包括国际互连网，所使用，而在传输层实现的。校验方法检验和循环冗余校验纵向冗余校验垂直冗余校验2.2 垂直冗余码校验 在错误检测中最常用和费用最低的方法是垂直冗余校验（VRC），又常称作奇偶校验。在垂直冗余校验（VRC）中，在每一个数据单元上都增加一个校验位，从而使得1的总数（包括校验位）对于偶校验来说是偶数，或对于奇校验来说是奇数。偶校验生成11

3、100001校验函数1的总数 是偶数吗？11000011数据VRC接收方可靠性：垂直冗余校验（VRC）可以检测所有单位比特错误。只要发生错误的比特数是奇数（1，3，5等等），该技术也可以检测出多比特错误和突发错误。缺点：但当发生错误的个数是偶数时，它就不能检测出多比特和突发错误。2.3 纵向冗余校验 纵向冗余校验（LRC）是在两个维上的垂直冗余校验（VRC）。1010101011100111101010010011100111011101数据移动方向数据纵向冗余校验0101011010010101100111001001110011100111整个数据块的传输方向纵向冗余校验垂直冗余校验位每个

4、数据块的传输方向可靠性 LRC技术极大地提高了发现多比特错误和突发错误的可能性。但是，有一种类型的错误仍然会被遗漏。如果在某个数据单元中的两个比特被破坏，同时在另一个数据单元中正好相同位置的两个比特也被破坏，那么LRC校验器就检测不出这种错误。2.4 循环冗余码校验 第三种也是最有效的一种冗余校验技术就是循环冗余校验（CRC）。和基于加法的VRC及LRC技术不同，循环冗余校验（CRC）是基于二进制除法的。000数据除数n bitn+1 bit余数n bit循环冗余码数据除数余数0，接收非0，拒绝数据发送方接收方 1 1 1 1 0 11 1 0 11 1 0 11 0 0 00 0 01 0

5、0 1 0 01 1 0 11 0 1 01 1 0 11 1 1 01 1 0 10 1 1 00 0 0 01 1 0 01 1 0 10 0 1除数商当余数最左位是0时，必须用0000代替原来的除数余数数据加上额外的0时，0的个数比除数位数少1可靠性：除了正好数据块的比特值是按除数值变化的错误外，循环冗余校验（CRC）将检测出其他所有错误。甚至对于上面所提到的四比特错误，这种情况发生的可能性仍然是很小的。而且，常用的CRC除数通常有13，17，或是33个比特，使得不可检测的错误可能降低到几乎近于零。3 错误纠正 错误纠正可以通过两种方式进行。一种方式是当发现错误时，接收方可以让发送方重新

6、发送整个数据单元。另一种方法是可以采用错误纠正码，自动纠正一些错误。理论上，可以自动纠正任何一种二进制编码错误。但是错误纠正码比错误检测码要复杂得多，并且需要占据更多的冗余比特位。纠正多比特错误和突发错误所需要的比特位数是如此巨大，因此在大多数情况下这样做是十分低效的。因此，大多数错误纠正技术都局限于一个，两个，或是三个比特错误。3.1 单比特错误纠正 实现错误纠正，必须知道错误的比特位。所以，错误纠正的诀窍在于对非法比特或比特组的定位。3.2 海明码1.为冗余比特定位一个七位的ASC码需要在数据单元末尾附加或者在原始数据中间插入四个冗余比特。在图9-18中，这些比特放在位置1，2，4和8上（

7、这些都是在11比特位中的2的指数序数）。为清楚表明下面的例子，我们将它们称为r1,r2,r4,以及r8。ddrdrddrdrd1110987654321冗余bit图9-18 在海明码中冗余比特的位置 在海明码中，每个冗余比特都是一组数据比特的VRC校验位：r2是另一组数据比特的VRC校验位，等等。在七位数据序列中用来计算四个冗余比特位的比特组合如下：R1：第1，3，5，7，9，11比特（最低位为“1”）R2：第2，3，6，7，10，11（次低位为“1”）R4：第4，5，6，7比特（第三位为“1”）R8：第8，9，10，11比特（第四位为“1”）R1与这些bit有关119 3751ddddddd

8、R8R1R4R211011001 0011011101010001 R2与这些bit有关dddddddR8R1R4R2R4与这些bit有关 7564dddddddR8R1R4R2 0111010101100100R8与这些bit有关11910 8dddddddR8R1R4R2101110011010 1000119 37621011 1010 00110111 01100010 数据：1001101100110111910 37568142数据加入r1加入r2加入r4加入r810011011100110111001101100110111910 3756814211910 3756814211

9、910 3756814211910 37568142编码：000001113.错误检测与纠正 现在假设在上述传输被接收时，第7位从1变成了0 接收方接收该传输并采用与发送方计算每个冗余比特时相同的比特组合来重新为每一个组计算新的VRC校验位。然后将新的校验位置按照冗余比特位置（r8,r4,r2,r1)排列成一个二进制数。在本例中。这一步就得出结果0111（十进制7），就指示了发生错误的比特的精确位置。一旦确定了发生错误的比特，接收方就可以将该比特值取反并纠正该错误。1001110010110010100101错误发送方接收方 0110101001010111987654320110101001010111987654320110101001010111987654320110101001010111987654327在第7个位置的bit发生错误0111