一、常用检错码

(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 » 检错码（奇偶校验与循环冗余）与纠错码（汉明码）