目录:
话在前面最近又过了一遍海明码,就想着给大家分享分享。在写作的过程中,同时又解决了很多疑惑。真应了 差错控制编码在数据通讯方面,要求信息传输具有高度的可靠性,即要求误码率足够低。然而实际会有各种干扰对信号造成不良的影响,致使数据在传输过程中出错。 为了满足通讯要求,减少误码出现,一方面要提高硬件的质量,另一方面可以采用差错控制编码。 差错控制编码的基本思想是:在发送端被传送给的信息码序列的基础上,按照一定的规则加入若干'监督码元'后进行传输,这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时,如果既定的约束关系遭到破坏,则在接收端可以发现传输中的错误,乃至纠正错误。
差错控制编码的分类根据码组的分类,可以分为检错码和纠错码两类。 检错码
纠错码
奇偶校验码这是一种简单的 奇偶校验码的这种监督关系可以用公式表示。设该组码长度为n,表示为(, , , ,),其中前n-1位为信息码元,第n位为监督位。 在偶校验时有:⊕⊕······⊕ = 0 海明码海明码(Hamming Code)是一个可以有多个校验位,具有 校验位的位数一般来说,若信息长为n,信息位数为k,则监督位数r=n-k,如果希望用r个监督位构造除r个监督关系式来指示一位错误码的n中可能位置。则要求: 推导并使用信息长度为k位的码字的海明码,所需步骤如下:
如果发现有一个或多个错误,则错误的位由这些检查的结果来唯一地确定。 码字格式从理论上讲,校验位可放在任何位置,但习惯上校验位被安排在1、2、4、8、…的位 置上。当 k=4,r=3 时,信息位和校验位的分布情况如下表所示(其中,、、为校验位,,…,为信息位)。
校验位的位置r 个校验位是通过对 k+r 位复合码字进行奇偶校验而确定的。校验位置在位置上,例如:1、2、4、8...
当n=1时,第1位校检码校检的起始位置为1,并从当前位置开始校验1位,每隔1位在校检1位。 所以有以下结果:
校验位的校验规则上面说第一位校验位校验1、3、5、7位,但是为什么校验这些位却没有说。包括一些教材也都没有说明缘由。
我们来看一张表格,就知道是什么意思了。如下图:
这就就是P1监控1、3、5、7位的原因。P2、P3同理。这部分才是精髓,一定要理解。 海明编码示例若有四位信息码:1101,进行偶校验,求编码之后的海明编码。 根据前文提到的校验规则,可以得知,根据校验码的位置:
根据上述的条件得知(,,) = (0,1,0)
检错和纠错在原有的编码系统中插入若干校验位,能够提高系统的码距,从而能够实现检错和纠错的功能。 什么是码距码距是编码系统中两个编码之间不同的二进制的位数。 假如四位信息码中,编码范围为0000~1111。例如数据1001和数据0000的码距就是2,因为它们的第1和第4位数据不同,所以码距是2。 但是我们通常关心的是编码系统中的最小码距。即最小的那个值。例如四位编码系统中的数据0000和0001,最小码距为1,没有比这个码距更小的值了。 增加码距为何能提高纠错能力?这里举个极端的例子,假如说我的编码系统中,经过编码之后的数据只会出现数据 但是我在接收方却收到了数据 由于数据 海明码的码距首先我们说的海明码通常指的是(n,k)=(7,4),即编码长度为7位、信息位为4、校验位为3位的海明码,所以通常叫74海明码。 关于海明码的码距,在网络上搜了大量的资料,也没见到说的比较明白的,果然还是得靠自己啊。 既然最小码距是编码系统中码距的最小值。那我们直接把4位信息码经过海明码编码后的所有可能穷举出来,找到最小值即可,请看下面这张表格。
通过观察上面这个表可以得知,经过插入三个校验位,任意两个编码之间不同的二进制位最小值为3,所以 海明码的检错和纠错能力码距和纠错的能力有如下关系:
根据上述公式和海明码的最小码距为3可以得知,海明码 海明码检2纠1理解在接收方,也可根据这3个校验方程对接收到的信息进行,同样的奇偶测试:
假如只有一位数据出错,错误位置就可简单地用二进制数CBA指出。如果CBA=000,则说明没有错。若CBA不等于0,说明有错。假如B5位出错。根据上述校验可得CBA=101,刚好是十进制5。也代表是第五位出现错误。 但是当有两位错误的时候,例如B3和B6同时出错,CBA仍然是等于101。 可以观看下面的图,比较直观。 总结
考题看了这么多,做两题练练手吧,请问下面两句话表述是否正确。
参考链接
来源:typedef |
|