数据通信编码纠错.doc

《数据通信编码纠错.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、纠错编码方式的简介2.1奇偶监督码奇偶校验码也称奇偶监督码，它是一种最简单的线性分组检错编码方式。其方法是首先把信源编码后的信息数据流分成等长码组，在每一信息码组之后加入一位(1比特)监督码元作为奇偶检验位，使得总码长n(包括信息位k和监督位1)中的码重为偶数(称为偶校验码)或为奇数(称为奇校验码)。如果在传输过程中任何一个码组发生一位(或奇数位)错误，则收到的码组必然不再符合奇偶校验的规律，因此可以发现误码。奇校验和偶校验两者具有完全相同的工作原理和检错能力，原则上采用任一种都是可以的。由于每两个1的模2相加为0，故利用模2加法可以判断一个码组中码重是奇数或是偶数。模

2、2加法等同于“异或”运算。现以偶监督为例。对于偶校验，应满足故监督位码元a0可由下式求出：(2－2)不难理解，这种奇偶校验编码只能检出单个或奇数个误码，而无法检知偶数个误码，对于连续多位的突发性误码也不能检知，故检错能力有限，另外，该编码后码组的最小码距为=2，故没有纠错码能力。奇偶监督码常用于反馈纠错法。2.2行列监督码行列监督码是二维的奇偶监督码，又称为矩阵码，这种码可以克服奇偶监督码不能发现偶数个差错的缺点，并且是一种用以纠正突发差错的简单纠正编码。其基本原理与简单的奇偶监督码相似，不同的是每个码元要受到纵和横的两次监督。具体编码方法如下：将若干个

3、所要传送的码组编成一个矩阵，矩阵中每一行为一码组，每行的最后加上一个监督码元，进行奇偶监督，矩阵中的每一列则由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶监督。如果用×表示信息位，用表示监督位，由矩阵码的结构可如图6－5所示，这样，它的一致监督关系按行及列组成。每一行每一列都是一个奇偶监督码，当某一行(或某一列)出现偶数个差错时，该行(或该列)虽不能发现，但只要差错所在的列(或行)，没有同时出现偶数个差错，则这种差错仍然可以被发现。矩阵码不能发现的差错只有这样一类：差错数正好为4倍数，而且差错位置正好构成矩形的四个角，如图6－5中所示有的差错情况。因

4、此，矩阵码发现错码的能力是十分强的，它的编码效率当然比奇偶监督码要低。2.3恒比码恒比码又称为定比码。在恒比码中，每个码组“1”和“0”都保持固定的比例，故得此名。这种码在检测时，只要计算接收到的码组中“1”的数目是否对就知道有无错误。在我国用电传机传输汉字时，只使用阿拉伯数字代表汉字。这时采用的所谓“保护电码”就是“3∶2”或称“5中取3”的恒比码，即每个码组的长度为5，其中“1”的个数总是3，而“0”的个数总是2。如表6－2所示。表6－2数字字符普通的五单位码恒比码1234511101110011000001010000010101111001101101101

5、0001116789010101111000110000011011011010111100011101001101101本来以5位码元组成的码组总共可以有25=32种，而恒比码规定只有确切地含有3个“1”，2个“0”的那些码组为准用码组，而有3个“1”，2个“0”的5位码组共有多少?这是“5中取3”求组合的算法，组合数为，一般情况下，从“n中取m”(m＜n)恒比码的码组数为：由此可以看出，恒比码实际上是n个码元传送比特信息，例如上述“3∶2”即“5中取2”恒比码，用5位码只传10种信息。每个码组的信息量为，有5-3.3=1.7bit作为代价付出。恒比码适用于传输

6、字母和符号。2.4汉明码汉明码属于线性分组编码方式，大多数分组码属于线性编码，其基本原理是，使信息码元与监督码元通过线性方程式联系起来。线性码建立在代数学群论的基础上，各许用码组的集合构成代数学中的群，故又称为群码。(1)校验子和监督关系式我们先回顾一下按式(2－2)条件构成的偶数监督码。由于我们使用了一位监督码C0，它就能和信息码一起构成一个代数式，在接收端解码时，我们实际上是在计算，若S=0，就认为无错码。若S=1，就认为有错码。上式就是一致监督关系式。S称为“校验子”。由于校验子S的取值只有这样两种，它就只能代表有错和无错两种信息，而不能指出错码的位置。我们

7、不难推想，如监督位增加一位，变成两位，则能增加一个类似于式(2－3)的监督关系式。两个校验子的可能值有4种组合00，01，10，11。故能表示4种不同的信息，其中一种表示无错，其余三种就有可能用来指示一位错码的3种不同位置。同理，r个监督关系式能指示一位错码的()个可能位置。一般说来，若码长为n，信息码为k，则监督码数r=n-k。若希望用r个监督码构造出r个监督关系式来指示一位错码的n种可能位置，则要求：下面通过一个例子来说明如何具体构造这些监督关系式。设分组码(n、k)中k=4，为了能纠正一位错码，按式(2