检错码(奇偶校验与循环冗余)与纠错码(汉明码)

一、常用检错码

(1)奇偶校验码

奇偶校验码是一种最简单的校验码,其编码规则:先将所要要传送的数据码元分组,并在每组的数据后面附加一位冗余位即校验位,使该组包括冗余位在内的数据码元中”1″的个数保持为奇数(奇校验)或偶数(偶校验)。在接收端按照同样的规则检查,如发现不符,说明有错误发生;只有”1″的个数仍然符合原定的规律时,认为传输正确。实际数据传输中所采用的奇偶校验码分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验三种。垂直奇偶校验是一字符为单位的校验方法。例如,传输数据信息为”1010001″,采用偶校验时,附加位为”1″,则发送信息变为”10100011″;采用奇校验时,附加位为”0″,发送信息变为”10100010″;

(2)循环冗余校验码(CRC)

循环冗余校验码CRC(CyclicRedundancyCode)采用一种多项式的编码方法。把要发送的数据位串看成是系数只能为”1″或为”0″的多项式。一个k位的数据块可以看成Xk-1到X0的k项多项式的系数序列。例如,”110001″有6位,表示多项式是”X5+X4+1″。多项式的运算是模2运算。采用CRC码时,发方和收方必须事先约定一个生成多项式G(X),并且G(X)的最高位和最低必须是1。要计算m位数据块的M(X)的校验和,生成多项式必须比该多项式短。其基本思想是:将校验和附加在该数据块的末尾,使这个带校验和的多项式能被G(X)除尽。当接收方收到带校验和的数据块时,用G(X)去除它,如果有余数,则传输有错误。

二、纠错码

纠错码与检错码相比其功能更强,它不但能检错还能纠错。海明码就是一种能够纠正一位错误的检错码。海明码是海明(H.W.Hamming)于1950年提出的一种码制。在发送数据之前将数据按照海明码制形成海明码,然后发送海明码,到达对方后根据接收到的海明码进行解释分析、判错、纠错。

  • 海明码的形成
  • 海明码的组合规则:海明码是由数据与校验位组合而成的。其组合规则为:将数据与校验码(寄偶校验)自左至右进行编码,其中编号为2的幂的位均为校验位,其余为数据位。
  • 校验位值的确定:将每一数据位的编号展开成2的幂的和(每一项不可重复),则每一项所对应的位均为该数据位的校验位。据此,按照寄偶校验规则确定各校验位的值。例:要传送的数据为”11001100″则相应的海明码为:AB1C100D1100其中A、B、C、D是加入的校验位。将每一数据位的编号展开成2的幂的和:3=2+1,9=8+1,5=4+1,10=8+2,6=4+2,11=8+2+1,7=4+2+1,12=8+4从而得出校验位所负责校验的数据位:第1位即A是1,3,5,7,9…(所有奇数位数据)的校验位。第2位即B是6,7,10,11…的校验位。第4位即C是5,6,7,12…的校验位。第8位即D是9,10,11,12…的校验位。最终确定A、B、C、D的值分别为:1、0、1、0(这里采用偶校验),因此其海明码为”101110001100″
  • 检错与纠错过程

当对方收到海明码后应进行以下检错和纠错:

  • 将出错计数器置为0。
  • 依次对每个校验位进行奇偶校验,如果有错将校验位所对应的编码值加入计数器中。直到每个校验位检查完为止。
  • 如果出错计数器值为0,则数据传输无错。反之如果计数器值不为0,则数据传输有错,且出错计数器值即为出错数据位的编码。
  • 将出错数据位的数据取反即可。

注意:海明码只能纠正一位错,若多位出错则无能为力。

【例】已知数据”11001100″在发送前,编码后得到的海明码是”101110001100″(这里采用偶校验),经信道传输到达接收端后,设定由于噪声干扰或其它方面的原因,数据被改为”100110001100″,即第3位出错。

分析海明码检错与纠错过程。按照上述海明码检错、纠错原理与过程,分析可得:

  • 在目标节点,首先将计数器置为0。
  • 依次对每个校验位与对所负责的数据位进行偶校验,由于第1位校验位(负责1,3,5,7,9,11位数据)负责第3位数据的校验,所以对第1位校验位进行检查时,发现1,3,5,7,9,11这6位数据之和已不是偶数了(由于第3位由”1″变为”0″的缘故),故出错,因此将该校验位的编码”1″加入到出错计数器中,即此时出错计数器的值为”1″。同理对第2位校验位检查时,发现3,6,7,10,11这5位数据之和也不是偶数了,故出错,因此将该校验位的编码”2″加入到出错计数器中。此时出错计数器的值为”3″。
  • 其余检验位由于与第3位数据无关,因此等所有的校验位检验结束后,出错计数器的值仍为”3″,故可知海明码的第3位数据出错。将第3位数据取反即可。

未经允许不得转载:TacuLee » 检错码(奇偶校验与循环冗余)与纠错码(汉明码)

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址