在检测或纠正错误的过程中,冗余是一个核心概念。为了能够检测或纠正错误,我们需要在数据中发送一些额外的比特位。这些冗余比特位由发送端添加,并由接收端去除。它们的存在可以让接收端检测或纠正损坏的比特位。在传输中包含额外信息以进行错误检测的概念是一个很好的方法。但是,与其重复整个数据流,我们可以在每个单元的末尾附加一个较短的比特位组。这种技术被称为冗余,因为额外的比特位对于信息来说是多余的:一旦确定了传输的准确性,它们就会被丢弃。
图8显示了使用冗余比特位来检查数据单元准确性的过程。一旦生成数据流,它经过一个设备进行分析,并添加一个适当编码的冗余检查。现在扩大了数个比特位的数据单元通过链路传输到接收端。接收端通过一个检查函数对整个流进行检查。如果接收到的流满足检查标准,则接受数据单元的数据部分,并丢弃冗余比特位。
循环冗余校验(CRC)
最强大的冗余检查技术是循环冗余校验(CRC)。CRC基于多项式算术,特别是在GF(2)(具有两个元素的伽罗瓦域)中计算将一个多项式除以另一个的余数。与基于加法的奇偶校验不同,CRC基于二进制除法。在CRC中,不是通过添加位来实现所需的奇偶校验,而是将一系列冗余位(称为CRC或CRC余数)附加到数据单元的末尾,使得生成的数据单元恰好可以被第二个预定的二进制数整除。在目的地处,传入的数据单元被同样的数字除以。如果在此步骤中没有余数,则认为数据单元完好无损,因此被接受。余数表示数据单元在传输过程中已经损坏,因此必须被拒绝。CRC使用的冗余位是通过将数据单元除以预定的除数来派生的;余数即为CRC。为了有效,CRC必须具备两个特点:它必须比除数少一个位,并将其附加到数据字符串的末尾必须使得生成的位序列恰好可以被除数整除。CRC错误检测的理论和应用都很简单。唯一的复杂性在于推导CRC。
CRC的性能
CRC是一种非常有效的错误检测方法。如果按照先前提到的规则选择除数,则:
1.CRC可以检测影响奇数位的所有突发错误。
2.CRC可以检测所有长度小于或等于多项式次数的突发错误。
3.CRC可以以非常高的概率检测长度大于多项式次数的突发错误。
错误的纠正
纠错比检测更困难。
在错误检测中,我们只是查看是否发生了任何错误。答案是简单的是或否。我们甚至不关心错误的数量。对于我们来说,单比特错误与突发错误相同。在错误纠正中,我们需要知道已损坏的位数以及更重要的是它们在消息中的位置。错误的数量和消息的大小是重要因素。如果我们需要在8位数据单元中纠正一个错误,则需要考虑八个可能的错误位置;如果我们需要在相同大小的数据单元中纠正两个错误,则需要考虑28种可能性。您可以想象接收器在1000位数据单元中查找10个错误时的困难。
为了计算纠错码所需的冗余位数r
,以纠正给定数量的数据位m
,我们必须找到m
和r
之间的关系。使用m
位数据和添加到它们的r
位冗余,生成代码的长度为m + r
。如果可传输单元中的总位数为m + r
,则r
必须能够指示至少m+r+1
个不同状态。其中一个状态表示无误差,m + r
个状态表示每个m + r
位置上的错误位置。
因此,r
位必须能够发现m+r+1
个状态:而r
位可以指示2^r
个不同状态。因此,2^r
必须等于或大于m+r+1
:
2^r=>m+r+1
例如,如果m的值为7(如7位ASCII码),可以满足此方程的最小r值为4:
2^4=>7+4+1
海明码
海明提供了一个实用的解决方案。海明码可应用于任何长度的数据单元,并使用上述数据和冗余位之间的关系。例如,7位ASCII码需要4个冗余位,可以将其添加到数据单元的末尾或与原始数据位交错。在图17中,这些位被放置在位置1、2、4和8(11位序列中是2的幂次位置)。
请点击以下链接查看信息和示例(所有以上信息都来自一个链接):
1,
2,
3。