数字通讯的错误检测与纠正.ppt
错误检测与纠正,1 错误类型,错误,多比特错误,突发错误,单比特错误,1.1单比特错误 单比特错误是指在给定数据单元（例如一个字节，一个字符，数据单元，或是数据包）中只有一个比特被从0变为1或是从1变为0。,0变到1,发送,接收,1.2 多比特错误 多比特错误是指数据单元中两个或两个以上不连续的比特从0变为1或是从1变为0。,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,2个错误,发送,接收,1.3 突发错误 突发错误指数据单元中两个或两个以上连续的比特从0变为1或是从1变为0。,突发错误,发送,接收,2 错误检测2.1 冗余 在数据通信中采用四种类型的冗余校验技术：垂直冗余校验（VRC）（也称为奇偶校验），纵向冗余校验（LRC），和循环冗余校验（CRC），是在物理层实现而在数据链路层被使用的。而第四种技术，校验和技术，主要由网络层，包括国际互连网，所使用，而在传输层实现的。,校验方法,检验和,循环冗余校验,纵向冗余校验,垂直冗余校验,2.2 垂直冗余码校验 在错误检测中最常用和费用最低的方法是垂直冗余校验（VRC），又常称作奇偶校验。在垂直冗余校验（VRC）中，在每一个数据单元上都增加一个校验位，从而使得1的总数（包括校验位）对于偶校验来说是偶数，或对于奇校验来说是奇数。,偶校验生成,1,1100001,校验函数1的总数 是偶数吗？,数据,VRC,接收方,可靠性：垂直冗余校验（VRC）可以检测所有单位比特错误。只要发生错误的比特数是奇数（1，3，5等等），该技术也可以检测出多比特错误和突发错误。缺点：但当发生错误的个数是偶数时，它就不能检测出多比特和突发错误。,2.3 纵向冗余校验 纵向冗余校验（LRC）是在两个维上的垂直冗余校验（VRC）。,可靠性 LRC技术极大地提高了发现多比特错误和突发错误的可能性。但是，有一种类型的错误仍然会被遗漏。如果在某个数据单元中的两个比特被破坏，同时在另一个数据单元中正好相同位置的两个比特也被破坏，那么LRC校验器就检测不出这种错误。,2.4 循环冗余码校验 第三种也是最有效的一种冗余校验技术就是循环冗余校验（CRC）。和基于加法的VRC及LRC技术不同，循环冗余校验（CRC）是基于二进制除法的。,除数,商,当余数最左位是0时，必须用0000代替原来的除数,余数,数据加上额外的0时，0的个数比除数位数少1,可靠性：除了正好数据块的比特值是按除数值变化的错误外，循环冗余校验（CRC）将检测出其他所有错误。甚至对于上面所提到的四比特错误，这种情况发生的可能性仍然是很小的。而且，常用的CRC除数通常有13，17，或是33个比特，使得不可检测的错误可能降低到几乎近于零。,3 错误纠正 错误纠正可以通过两种方式进行。一种方式是当发现错误时，接收方可以让发送方重新发送整个数据单元。另一种方法是可以采用错误纠正码，自动纠正一些错误。理论上，可以自动纠正任何一种二进制编码错误。但是错误纠正码比错误检测码要复杂得多，并且需要占据更多的冗余比特位。纠正多比特错误和突发错误所需要的比特位数是如此巨大，因此在大多数情况下这样做是十分低效的。因此，大多数错误纠正技术都局限于一个，两个，或是三个比特错误。3.1 单比特错误纠正 实现错误纠正，必须知道错误的比特位。所以，错误纠正的诀窍在于对非法比特或比特组的定位。,3.2 海明码1.为冗余比特定位一个七位的ASC码需要在数据单元末尾附加或者在原始数据中间插入四个冗余比特。在图9-18中，这些比特放在位置1，2，4和8上（这些都是在11比特位中的2的指数序数）。为清楚表明下面的例子，我们将它们称为r1,r2,r4,以及r8。,图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有关,R2与这些bit有关,R4与这些bit有关,R8与这些bit有关,数据：1001101,数据,加入r1,加入r2,加入r4,加入r8,编码：,0,0,0,0,0,1,1,1,3.错误检测与纠正 现在假设在上述传输被接收时，第7位从1变成了0 接收方接收该传输并采用与发送方计算每个冗余比特时相同的比特组合来重新为每一个组计算新的VRC校验位。然后将新的校验位置按照冗余比特位置（r8,r4,r2,r1)排列成一个二进制数。在本例中。这一步就得出结果0111（十进制7），就指示了发生错误的比特的精确位置。一旦确定了发生错误的比特，接收方就可以将该比特值取反并纠正该错误。,1,0,0,1,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,1,错误,发送方,接收方,7,在第7个位置的bit发生错误,
