常用的差错控制编码方法

第二节常用差错控制编码方法一、奇偶校验码奇偶校验码是一种检错码，又称奇偶监督码，属于分组码。奇偶监督码是在原信息码后面附加一个监督元，使得码字中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的（n，n-1）分组码。奇偶监督码分为奇监督码和偶监督码。1.一般奇偶校验码（1）基本原理编码规则：先将所要传输的数据码元分组，在分组数据后面附加一位校验位，使得该组码连同校验位在内的码组中的“1”的个数为偶数（称为偶校验）或奇数（称为奇校验）在接收端按同样的规律检查，如发现不符就说明产生了差错，但是不能确定差错的具体位置，即不能纠错。偶检验条件：奇校验条件：1.一般奇偶校验码（2）纠错能力只能发现单个或奇数个错误，而不能检测出偶数个错误，此方法难于对付突发错。偶校验监督码2.垂直奇偶校验码（1）基本原理以ASCII码的数字0～9为例说明垂直奇偶校验的编码。接收端根据收到的b1～b7重新计算奇偶校验码元，将此与收到的b8相比较。如相同则无错，否则存在错误。垂直偶校验2.垂直奇偶校验码（2）纠错能力垂直奇偶校验编码，无论是采用偶校验还是奇校验，将检出全部奇数个差错，而出现的全部偶数个差错均不能发现。3.水平奇偶校验码（1）基本原理将要进行奇偶校验的码元序列按行排成方阵，每行为一组奇偶校验码，但发送时则按列的顺序传输，接收端仍将码元排成发送时的方阵形式，然后按行进行奇偶校验。水平偶校验练习：写出水平奇校验的校验码元3.水平奇偶校验码（2）纠错能力可发现某一行上所有奇数个错误及所有长度小于或等于方阵中行数的突发错。这种编码的优点是突发连续错误被分散到每行，当收端按行监督检验时，可检测出有错；但是由于该编码在检错过程中需要对数据进行重组，所以需要的缓存空间较大，并且在数据的处理方面延时增大。4.二维奇偶校验码（1）基本原理二维奇偶校验码又称行列校验码或方阵码。其方法是水平监督的基础上对方阵中每一列再进行奇偶校验，发送是按列序顺次传输。二维齐偶校验问题：这是二维齐校验还是偶校验？练习：写出另一种校验的校验码元

二维奇偶监督码，它是将若干个信息码字按每个码字一行排列成矩阵形式，然后在每一行和每一列的码元后面附加一位奇（偶）监督码元。

信息码元监督码元信息码元监督码元

10110001101100011101001011010010001001110110011101101100011011001001100110011001监督码元1

0

11000

1

10110001二维奇偶监督码4.二维奇偶校验码（2）纠错能力能发现某行或某列上的奇数个错误和长度不大于行数（或列数）的突发错误。有可能检测出偶数个错码。可以纠正一些错误。检错能力强，又有一定纠错能力，且实现容易得到广泛应用。二、恒比码码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的个数是否与规定的相同，就可判断有无错误。汉明码：能够纠正1位错码且编码效率较高的一种线性分组码。构造原理（以奇偶校验为例）在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1…a1一起构成一个代数式： 在接收端解码时，实际上就是在计算若S=0，就认为无错码；若S=1，就认为有错码。三、汉明码现将上式称为监督关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4中组合：00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r–1)个可能位置。一般来说，若码长为n，信息位数为k，则监督位数r＝n－k。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求

例：设分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数r

3。若取r=3，则n=k+r=7。我们用a6

a5

a0表示这7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：S1S2

S3错码位置S1S2

S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码由表中规定可见，仅当一位错码的位置在a2

、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2

、a4、a5和a6四个码元构成偶数监督关系：

a1、a3、a5和a6构成偶数监督关系：a0、a3、a4

和a6构成偶数监督关系在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位。给定信息位后，可以直接按上式算出监督位，结果见下表：信息位a6a5a4a3监督位a2a1a0信息位a6a5a4a3监督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1

S2

S3

等于011，故查表可知在a3位有1错码。按照上述方法构造的码称为汉明码。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1–r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。三、汉明码2.编码示例设分组码（n，k）中k=4，则r≥3.校正子与错码位置对应关系规定如表4-5.阅读练习若接收码组为1100101，判断错误位置。已知信息位k为1001，求监督位r。四、循环码1.循环码的特性（1）循环性（2）封闭性阅读p31(7，3)循环码的一种码组2.循环码的码多项式阅读，练习：写出表4-6中码组的码多项式在这种多项式中，x仅是码元位置的标记3.码多项式的按模运算若一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个小于n的余式R(x)，即F(x)=N(x)Q(x)+R(x)写为F(x)≡R(x)（模N(x)）3.码多项式的按模运算就循环码来说，若是一个长为n的许用码组A(x)，则xi·A(x)在按模（xn+1）运算下，亦是一个许用码组，即若xi·A(x)≡A´(x)（模xn+1）（4-12）则A´(x)也是一个许用码组。可见：一个长为n的（n，k）循环码，它必是按模（xn+1）运算的一个余式。4.循环码的生成多项式一个（n，k）循环码有2k个不同的码组。若用g(x)表示其中前（k−1）位皆为“0”，而第k位及第n位为1的码组为循环码的一个许用码组，根据循环性，则xg(x)，x2g(x)，…，xk－1g(x)都是它的许用码组，连同g(x)共同构成k个许用码组，即