1、第10章 差错控制编码 1第第10章章 差错控制编码差错控制编码7.1 概述概述 7.2 常用的几种简单分组码常用的几种简单分组码 7.3 线性分组码线性分组码 7.4 循环码循环码 第10章 差错控制编码 2 10.1 10.1 概述概述 在数字信号传输中，由于信道不理想以及加性噪声的影响，被传输的信号码元波形会变坏，造成接收端错误判决。为了尽量减小数字通信中信息码元的差错概率，应合理设计基带信号并采用均衡技术以减小信道线性畸变引起的码间干扰；对于由信道噪声引起的加性干扰，应考虑采取加大发送功率、适当选择调制解调方式等措施。但是随着现代数字通信技术的不断发展，以及传输速率的不断提高，对信息码
2、元的差错概率Pe的要求也在提高，例如计算机间的数据传输，要求Pe低于10-9，并且信道带宽和发送功率受到限制，此时就需要采用信道编码，又称为差错控制编码。第10章 差错控制编码 3 信道编码理论建立在香农信息论的基础上，其实信道编码理论建立在香农信息论的基础上，其实质是给信息码元增加质是给信息码元增加冗余度冗余度，即增加一定数量的，即增加一定数量的多余多余码元码元(称为监督码元或校验码元称为监督码元或校验码元)，由信息码元和监督，由信息码元和监督码元共同组成一个码字，两者间满足一定的约束关系。码元共同组成一个码字，两者间满足一定的约束关系。如果在传输过程中受到干扰，某位码元发生了变化，如果在传
3、输过程中受到干扰，某位码元发生了变化，就破坏了它们之间的约束关系。接收端通过检验约束就破坏了它们之间的约束关系。接收端通过检验约束关系是否成立，完成识别错误或者进一步判定错误位关系是否成立，完成识别错误或者进一步判定错误位置并纠正错误，从而提高通信的可靠性。置并纠正错误，从而提高通信的可靠性。第10章 差错控制编码 4 10.2 10.2 差错控制编码的基本概念差错控制编码的基本概念 10.2.1 10.2.1 差错控制方式差错控制方式 在差错控制系统中，差错控制方式主要有三种。1.1.前向纠错控制方式前向纠错控制方式(FEC)(FEC)又称自动纠错自动纠错，是指发送端发出的可以纠正错误码发送
4、端发出的可以纠正错误码元的编码序列元的编码序列，接收端的译码器能自动纠正传输中的错接收端的译码器能自动纠正传输中的错码码，系统框图如图10.2.1(a)所示。这种方式的优点优点是不需要反馈信道，译码实时性好，具有恒定的信息传输速率。缺点缺点是为了要获得比较低的误码率，必须以最坏的信道条件来设计纠错码，故需要附加较多的监督码元，这样既增加了译码算法选择的难度，也降低了系统的传输效率，所以不适宜应用在传输条件恶化的信道。第10章 差错控制编码 5 2.2.反馈重发纠错方式反馈重发纠错方式(ARQ)(ARQ)发送端发出的是能够检测错误的编码序列，接收端译码发送端发出的是能够检测错误的编码序列，接收端
5、译码器根据编码规则进行判决，并通过反馈信道把判决结果回传，器根据编码规则进行判决，并通过反馈信道把判决结果回传，无错认可无错认可(ACK)(ACK)，有错时否认，有错时否认(NAK)(NAK)。发送端根据回传指令，。发送端根据回传指令，将有错的码组重发，直到接收端认为正确接收为止将有错的码组重发，直到接收端认为正确接收为止，系统框图如图10.2.1(b)所示。优点：优点：检错码构造简单，不需要复杂的编译码设备，在冗余度一定的条件下，检错码的检错能力比纠错码的纠错能力强得多，故整个系统的误码率可以保持在极低的数量级上。缺点：缺点：需要反馈信道，并要求发送端有大容量的信源存储器，且为保证收、发两端
6、互相配合，控制电路较为复杂。另外，当信道干扰很频繁时，系统经常处于重发消息的状态，使传送信息的实时性变差。第10章 差错控制编码 6 3 3混合纠错方式混合纠错方式(HEC)(HEC)该方式是上述两种方式的结合，即在ARQ系统中包含一个FEC子系统，系统框图如图10.2.1(c)所示。发发送端发出的是具有一定送端发出的是具有一定纠错能力纠错能力和较强和较强检错能力检错能力的码的码，所以经信道编码而附加的监督码元并不多所以经信道编码而附加的监督码元并不多。接收端检测数据码流，发现错误先由FEC子系统自动纠错，仅当错误较多超出纠错能力时，再发反馈信息要求重发，因此大大减少了重发次数。HEC在一定程
7、度上弥补了反馈重发和前向纠错两种方式的缺点，充分发挥了码的检、纠错能力，在较强干扰的信道中仍可获得较低误码率，是实际通信中应用较多的纠错方式。第10章 差错控制编码 7第10章 差错控制编码 8 10.2.2 10.2.2 差错控制编码的分类差错控制编码的分类 用不同的方法可以对差错控制编码进行不同的分类。1.根据已编码组中信息码元与监督码元之间的函数信息码元与监督码元之间的函数关系，可分为关系，可分为线性码线性码及及非线性码非线性码。若信息码元与监督码元之间的关系呈线性，即满足一组线性方程式，则称为线性码线性码。否则称为非线性码非线性码。第10章 差错控制编码 9 2.根据信息码元信息码元和
8、监督码元之间的约束方式不同监督码元之间的约束方式不同，可分为分组码分组码和卷积码卷积码。分组码的监督码元仅与本码组的信息码元有关，卷积码的监督码元不仅与本组信息码元有关，而且与前面若干码组的信息码元有约束关系。3.根据编码后信息码元是否保持原来的形式，可编码后信息码元是否保持原来的形式，可分为分为系统码系统码和和非系统码非系统码。在系统码中，编码后的信息码元保持原样，而非系统码中的信息码元则改变了原来的信号形式。第10章 差错控制编码 10 4.根据编码的不同功能编码的不同功能，可分为检错码检错码、纠错码纠错码和和纠删码纠删码。检错码只能够发现错误，但不能纠正错误；纠错码能够纠正错误；纠删码即
9、可以检错又可以纠错，但纠错能力有限，当有不能纠正的错误时将发出错误指示或删除不可纠正的错误段落。5.根据纠正、检验错误的类型不同纠正、检验错误的类型不同，可分为纠正、纠正、检验随机性错误的码检验随机性错误的码和和纠正、检验突发性错误的码纠正、检验突发性错误的码。6.根据码元取值的不同码元取值的不同，可分为二进制码二进制码和多进多进制码制码。这里只介绍二进制纠、检错编码。第10章 差错控制编码 11 10.2.3 10.2.3 检错和纠错的基本原理检错和纠错的基本原理 差错控制编码的基本思想基本思想是在被传输的信息码元中附加一些监督码元，并且使它们之间确定某一种关系，根据传输过程中这种关系是否被
10、破坏来发现或纠正错误。可见这种差错控制能力是用增加信息量的冗余度来换取这种差错控制能力是用增加信息量的冗余度来换取的。的。设编码后的码组长度码组长度、码组中所含信息码元个数信息码元个数以及监督码元个数监督码元个数分别为n n、k k和r r，三者间满足n n=k k+r r，定义编码效率为R R=k k/n n =1-=1-r r/n n。可见码组长度一定时，所加入的监督码元个数越多，编码效率越低。第10章 差错控制编码 12 香农的信道编码定理指出:对于一个给定的有扰信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为编码器的输入二进制码元速率），则一定存在一种编码方法，使编码错误
11、概率P随着码长n的增加，按指数下降到任意小的值。可以表示为 其中E(R)称为误差指数，它与R和C的关系如图10.2.2所示。(10.2.1)第10章 差错控制编码 13第10章 差错控制编码 14 由定理有如下结论:1.在码长及发送信息速率一定的情况下，为减小P可以增大信道容量。由图10.2.2可知，E(R)随信道容量的增加而增大。由式(10.2.1)可知，错误概率随E(R)的增大而指数下降。2.在信道容量及发送信息速率一定的条件下，增加码长，可以使错误概率指数下降。对于实际应用来说，此时的设备复杂性和译码延时也随之增加。第10章 差错控制编码 15 香农的信道编码定理为信道编码奠定了理论基础
12、，虽然定理本身并没有给出具体的差错控制编码方法和纠错码的结构，但它从理论上为信道编码的发展指出了努力方向。我们用3位二进制码组来说明检错纠错的基本原理。3位二进制码元共有8种可能的组合:000、001、010、011、100、101、110、111。如果这8种码组都可传递消息，若在传输过程中发生一个误码，则一种码组会错误地变成另一种码组。由于每一种码组都可能出现，没有多余的信息量，因此接收端不可能发现错误，认为发送的就是另一种码组。第10章 差错控制编码 16 如果选其中000、011、101、110来传送消息，这相当于只传递00、01、10、11四种信息，而第3位是附加的。这位附加的监督码元
13、与前面两位码元一起，保证码组中“1”码的个数为偶数。这4种码组称为许用码组许用码组。另外4种码组不满足这种校验关系，称为禁用码组禁用码组，它们在编码后的发送码元中不会出现。接收时一旦发现有禁用码组，就表明传输过程中发生了错误。用这种简单的校验关系可以发现1个或3个错误，但不能纠正错误。因为当接收到的码组为禁用码组时，比如为010，无法判断发送的是哪个码组。虽然原发送码组为101的可能性很小(因为3个误码的概率一般很小)，但不能绝对排除，即使传输过程中只发生一个误码，也有三种可能的发送码组即000、011和110。第10章 差错控制编码 17 假如我们进一步将许用码组限制为二种即000和111，
14、显然这样可以发现所有2位以下的误码，若用来纠错，可以用最大似然准则纠正1位错误。可以用一个三维立方体来表示上述3位二进制码组的例子，如图10.2.3所示。图中立方体各顶点分别表示8位码组，3位码元依次表示x、y、z轴的坐标。第10章 差错控制编码 18第10章 差错控制编码 19 这里定义码组中非零码元的数目为码组中非零码元的数目为码组的重量码组的重量，简称码重码重。比如100码组的码重为1，101码组的码重为2。定义两个码组中对应码位上具有不同二进制码元的两个码组中对应码位上具有不同二进制码元的位数为两码组的距离，称为汉明位数为两码组的距离，称为汉明(Hamming)(Hamming)距，简
15、称距，简称码码距距。在前面3位二进制码组的例子中，当8种码组均为许用码组时，两码组间的最小距离为1，称这种编码的最小码距为1，一般记为dmin=l；当选4种码组为许用码组时，最小码距dmin=2；当用2种码组作为许用码组时，dmin=3。第10章 差错控制编码 20 从图10.2.3所示的立方体可以看出，码距就是从一个顶点沿立方体各边移到另一个顶点所经过的最少边数。图中粗线表示000与111之间的一条最短路径。很容易得出前例中各种情况下的码距。根据以上分析可知，编码的最小码距直接关系到这种码的检错和纠错能力，所以最小码距是差错控制编码的一个重要参数。对于分组码一般有以下结论:第10章 差错控制
16、编码 21 1.在一个码组内检测在一个码组内检测e个误码，要求最小码距个误码，要求最小码距 dmin e+1 (10.2.2)2.在一个码组内纠正在一个码组内纠正t个误码，要求最小码距个误码，要求最小码距 dmin 2t+1 (10.2.3)3.在一个码组内纠正在一个码组内纠正t个误码，同时检测个误码，同时检测e(et)个误个误码，要求最小码距码，要求最小码距 dmin t+e+1 (10.2.4)这些结论可以用图这些结论可以用图10.2.4所示的几何图形简单的给所示的几何图形简单的给予证明。予证明。第10章 差错控制编码 22第10章 差错控制编码 23 可见dmin体现了码组的纠、检错能力
17、。码组间最小距离越大，说明码字间最小差别越大，抗干扰能力就越强。由于编码系统具有纠错能力，因此在达到同样误码率要求时，编码系统会使所要求的输入信噪比低于非编码系统，为此引入了编码增益的概念。其定义为，在给定误码率下，非编码系统与编码系统之间所需信噪比Eb/N0之差(用dB表示)。采用不同的编码会得到不同的编码增益，但编码增益的提高要以增加系统带宽或复杂度来换取。第10章 差错控制编码 24 10.2.4 10.2.4 常用的简单检错码常用的简单检错码 常用检错码的结构一般都很简单，由于这些码组具有较强的检错能力，并且易于实现，所以在实际当中应用很广泛。1 1奇偶校验码奇偶校验码 奇偶校验码又称
18、奇偶监督码，它只有一个监督码元，是一种最简单的检错码，在计算机数据传输中得到广泛应用。编码时，首先将要传送的信息分组，按每组中“1”码的个数计算监督码元的值。编码后，整编码后，整个码组中个码组中“1”1”码个数成为奇数的称码个数成为奇数的称奇校验奇校验，成为偶数，成为偶数的称的称偶校验偶校验。第10章 差错控制编码 25 设码组长度为码组长度为n n，其中前，其中前n n-1-1位位(an-1,an-2,a1)是是信息码元，信息码元，a0 是监督码元，二者之间的监督关系可用是监督码元，二者之间的监督关系可用公式表示。公式表示。奇校验满足奇校验满足 偶校验满足偶校验满足 (10.2.6)(10.
19、2.5)第10章 差错控制编码 26 接收端用一个模2加法器就可以完成检错工作。当错码为一个或奇数个时，因打乱了“1”数目的奇偶性，故能发现差错。然而，当错误个数为偶数时，由于未破坏“l”数目的奇偶性，所以不能发现偶数个错码。第10章 差错控制编码 27 2 2行列监督码行列监督码 行列监督码也叫方阵校验码，编码原理编码原理与简单的奇偶监督码相似，不同之处在于每个码元都要受到纵、横两个每个码元都要受到纵、横两个方向的监督方向的监督。以图10.2.5为例，有28个待发送的数据码元，将它们排成4行7列的方阵。方阵中每行是一个码组，每行每行的最后加上一个监督码元进行行监督，同样在每列的最后的最后加上
20、一个监督码元进行行监督，同样在每列的最后也加上一个监督码元进行列监督，然后按行也加上一个监督码元进行列监督，然后按行(或列或列)发送。发送。接收端按同样行列排成方阵，发现不符合行列监督规则的判为有错。它除了能检出所有行、列中的奇数个错误外，它除了能检出所有行、列中的奇数个错误外，也能发现大部分偶数个错误。也能发现大部分偶数个错误。因为如果碰到差错个数恰为4的倍数，而且差错位置正好处于矩形四个角的情况，方阵码无法发现错误。第10章 差错控制编码 28第10章 差错控制编码 29 行列监督码在某些条件下还能纠错，观察第3行、第4列出错的情况，假设在传输过程中第3行、第4列的“1”错成“0”，由于此
21、错误同时破坏了第3行、第4列的偶监督关系，所以接收端很容易判断是3行4列交叉位置上的码元出错，从而给予纠正。行列监督码也常用于检查或纠正突发错误。它可以检查出错误码元长度小于和等于码组长度的所有错码，并纠正某些情况下的突发差错。行列监督码实质上是运用矩阵变换，把突发差错变成独立差错加以处理。因为这种方法比较简单，所以被认为是克制突发差错很有效的手段。第10章 差错控制编码 30 3.3.恒比码恒比码 恒比码又称恒比码又称等比码等比码或或等重码等重码。恒比码的每个码组中，“1”和“0”的个数比是恒定的。我国电传通信中采用的五单位数字保护电码是一种32等比码，也叫五中取三的恒比码，即在5单位电传码
22、的码组中(25=32)，取其“1”的数目恒为3的码组(C53=10)，代表10个字符(09)，如表10.2.1所示。因为每个汉字是以四位十进制数表示的，所以提高十进制数字传输的可靠性，相当于提高了汉字传输的可靠性。第10章 差错控制编码 31 国际电传电报上通用的ARQ通信系统中，选用三个“1”、四个“0”的3:4码，即七中取三码。它有C73=35个码组，分别表示26个字母及其他符号。在检测恒比码时，通过计算接收码组中“1”的数目，判定传输有无错误。除了“1”错成“0”和“0”错成“1”成对出现的错误以外，这种码能发现其他所有形式的错误，因此检错能力很强。实践证明，应用这种码，国际电报通信的误
23、码率保持在10-6以下。第10章 差错控制编码 32 4.ISBN4.ISBN国际统一图书编号国际统一图书编号 国际统一图书编号是一种检错码，以防止书号在通信过程中发生误传。这里以编号ISBN 0-1315-2447-X为例，其中第一位数字“0”0”表示该书是美国及其它美国及其它英语国家的出版物英语国家的出版物(中国的代号是数字中国的代号是数字“7”)7”)，“1315”1315”代表出版公司版公司，“2447”2447”代表书名编号书名编号，最后一位数字“X”X”是校验位校验位(这是这是1010的罗马字表示的罗马字表示)。这里采用的校验方法如图10.2.6所示。第10章 差错控制编码 33第
24、10章 差错控制编码 34 图中第1行为ISBN编号。第2行第1个数字与第1行第1个数字相同；第2行第2个数字则为第1行第2个数字与第2行第1个数字之和，即1+0=1；第2行第3个数字为第1行第3个数字与第2行第2个数字之和，即3+1=4；依次类推，第2行最后所得的累计和为37。用同样方法得到第3行的最后累计和为132。然后用模11对132进行校验，132(mod 11)0。显然，若通信过程中统一书号发生了错误，则上累计和就不能被11所整除，从而可校验出来。第10章 差错控制编码 3510.3 10.3 线性分组码线性分组码 10.3.1 10.3.1 基本概念基本概念 一个长为一个长为n n
25、的分组码，码字由两部分构成，即的分组码，码字由两部分构成，即信息信息码元码元(k k位位)+)+监督码元监督码元(r r位位)。监督码元是根据一定规则由信息码元变换得到的，变换规则不同就构成不同的分组码。如果监督位为信息位的线性组合，就称其为如果监督位为信息位的线性组合，就称其为线性线性分组码分组码。要从k个信息码元中求出r个监督码元，必须有r个独立的线性方程。根据不同的线性方程，可得到不同的(n,k)线性分组码。第10章 差错控制编码 36 例如，已知一个(7，4)线性分组码，4个信息码元a6、a5、a4、a3和3个监督码元a2、a1、a0之间符合以下规则 计算上式得到此(7，4)线性分组码
26、的全部码组，列于表10.3.1中(许用码组的个数等于k个信息码元的全部组合数2k个)。(10.3.1)第10章 差错控制编码 37第10章 差错控制编码 38 前面介绍的奇偶监督码是一种最简单的线性码。改写式(10.2.5)、式(10.2.6)可以得到监督码元a0和信息码元之间的关系。奇校验 偶校验(10.3.2)(10.3.3)第10章 差错控制编码 39 线性码各许用码组的集合构成了代数学中的群，因此线性码各许用码组的集合构成了代数学中的群，因此又称又称群码群码。它有如下性质:1）任意两许用码组之和任意两许用码组之和(按位模按位模2 2加加)仍为一许用码仍为一许用码组，即线性码具有组，即线
27、性码具有封闭性封闭性；2）集合中的最小距离等于码组中非全集合中的最小距离等于码组中非全“0”0”码字的码字的最小重量最小重量。在群中只存在一种运算，即模2加，通常四则运算中的加、减法在这里都是模2加的关系。所以后面将简化运算符号为“+”。为了说明(n,k)线性分组码的编码原理，下面引入监监督矩阵督矩阵H H和生成矩阵生成矩阵G G的概念。第10章 差错控制编码 40 10.3.2 10.3.2 监督矩阵和生成矩阵监督矩阵和生成矩阵 1.1.监督矩阵监督矩阵H H 改写式(10.3.1)所示(7，4)线性分组码的3个线性方程式 写成矩阵形式(10.3.4)(10.3.5)第10章 差错控制编码
28、41 或(10.3.6)第10章 差错控制编码 42 分别记作 或 式中 是rn阶矩阵，称为线性分组码的一致监督矩阵(或校验矩阵)。(10.3.8)(10.3.7)(10.3.9)第10章 差错控制编码 43 A AT、0T、H HT分别是A A、0、H H矩阵的转置。对于码字A A来说，恒有 或 成立，即当监督矩阵H H给定时，利用式(10.3.7)可以验证接收码是否正确。H H矩阵可以分成两部分:第10章 差错控制编码 44 H H矩阵可以分成两部分:式中P P为rk阶矩阵，I Ir为rr阶单位方阵，具有具有 P P I Ir r 形式的形式的H H矩阵被称为矩阵被称为典型矩阵典型矩阵。线
29、性代数的基本理论指出，典型形式的监督矩阵各行一定是线性无关的，非典型形式的监督矩阵可以经过线性变换化为典型形式，除非非典型形式监督矩阵的各行不是线性无关的。(10.3.10)第10章 差错控制编码 45 2.2.生成矩阵生成矩阵G G 改写式(10.3.1)为矩阵形式 或者(10.3.11)(10.3.12)第10章 差错控制编码 46 其中Q Q为kr阶矩阵。该式表明，已知Q Q矩阵，同样可以由信息位算出监督码元。不难看出,Q Q是P P的转置，即 如果在Q Q的左边加上一个kk阶单位方阵，就构成了生成矩阵(10.3.13)(10.3.14)第10章 差错控制编码 47 称G G为生成矩阵，
30、是因为利用它可以产生码组A A，即 符合符合 I Ik k Q Q 形式的生成矩阵称为典型形式的生成矩阵形式的生成矩阵称为典型形式的生成矩阵，由该矩阵得到的码组是系统码。利用此生成矩阵同样可以得到表10.3.1中给出的(7，4)线性分组码的全部码字。同样，典型形式的生成矩阵的各行也必定是线性无关的，每行都是一个许用码组，k行许用码组经过行运算可以生成2k个不同的许用码组。非典型形式的生成矩阵经过运算也一定可以化为典型形式。典型监督矩阵和典型生成矩阵之间存在关系(10.3.15)(10.3.16)第10章 差错控制编码 48 10.3.3 10.3.3 伴随式（校正子）伴随式（校正子）发送码组A
31、=an-1 an-2 a0 在传输过程中可能会发生误码。设接收到的码组为B=bn-1 bn-2 b0，则收、发码组之差为 B A=E 或写成 B=A+E 式中E=en-1 en-2 e0为错误图样。令 S=BH T 为分组码的伴随式(亦称校正子或校验子)。利用式(10.3.8)，可以得到 S=(A+E)H T=AH T+EH T=EH T 这样就把校正子S S与接收码组B B的关系转换成了校正子S S与错误图样E E的关系。(10.3.17)(10.3.18)(10.3.19)第10章 差错控制编码 49 在接收机中只要用式(10.3.18)计算校正子S S，并判断计算结果是否为0，就可完成检
32、错工作。因为如果是正确接收(E=0)，则B=A+E=A，依照式(10.3.8)有 S=BH T=AH T=0 如果接收码组不等于发送码组(BA)，则E0，故S=EH T0。在讨论怎样利用校正子S S完成纠错工作之前，先看一下S与E的关系。前面所说的(7，4)线性分组码见式(10.3.9)第10章 差错控制编码 50 设接收码组的最高位有错，错误图样E E=1 0 0 0 0 0 0，计算第10章 差错控制编码 51 它的转置 恰好是典型监督矩阵H中的第一列。如果是接收码组B中的次高位有错，E=0 1 0 0 0 0 0，那么算出的S=1 1 0，其转置ST恰好是典型监督矩阵H中的第二列。换言之
33、，在接收码组只错一位码元的情况下，计算出的校正子S总是和典型监督矩阵HT中的某一行相同。可以证明，只要不超出线性分组码的纠错能力，接收机依据计算出的校正子S，可以判断码组的错误位置并予以纠正。这里仅讨论纠正一位错误码元的情况。第10章 差错控制编码 52 例例10.3.1 10.3.1 已知前述已知前述(7(7，4)4)线性分组码某码组，在线性分组码某码组，在传输过程中发生一位误码，设接收码组传输过程中发生一位误码，设接收码组B=0 0 0 0 1 0 1，试将其恢复为正确码组。试将其恢复为正确码组。解解:(1)首先确定码组的纠、检错能力首先确定码组的纠、检错能力 查表查表10.3.1，得到最
34、小码距，得到最小码距dmin=3，故此码组，故此码组可以纠正一位错码或检测两位错误码元。可以纠正一位错码或检测两位错误码元。(2)计算计算ST第10章 差错控制编码 53已知前述已知前述(7,4)线性分组码的典型监督矩阵线性分组码的典型监督矩阵利用矩阵性质汁算校正子的转置利用矩阵性质汁算校正子的转置 第10章 差错控制编码 54 (3)恢复正确码组恢复正确码组 因为此码组具有纠正一位错误的能力，且计算结果ST与H矩阵中的第三列相同，相当于得到错误图样E=0 0 1 0 0 0 0，所以正确码组为 A=B+E =0 0 0 0 1 0 1+0 0 1 0 0 0 0 =0 0 1 0 1 0 1
35、 第10章 差错控制编码 55 10.3.4 10.3.4 汉明码汉明码 汉明码是一种可以纠正单个随机错误的线性分组码。它的最小码距dmin=3，监督码元位数r=n k(r是一个大于或等于2的正整数)，码长n=2r-1，信息码元位数k=2r-1-r,编码效率R=k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)。当r很大时，极限趋于1，所以是一种高效码。汉明码的监督矩阵H H有n列r行，它的n列由不全为0的二进制r位码的不同组合构成，即每种组合只在某列中出现一次。第10章 差错控制编码 56 以r=3为例，它的码长n=23-1=7，所以前面所说的(7，4)线性分组码就是汉明码，并且任
36、意调换H H矩阵中各列的位置，不会影响码的纠、检错能力。例如可以构造出与式(10.3.9)不同的监督矩阵，即 其相应的生成矩阵为(10.3.21)(10.3.20)第10章 差错控制编码 57 因此，汉明码H H矩阵中各列的位置还可以有其它多种排列形式。汉明码的译码方法，可以采用计算校正子，然后确定错误图样并加以纠正的方法。图10.3.1中给出式(10.3.20)所示(7，4)汉明码的编码器和译码器电路图。第10章 差错控制编码 58第10章 差错控制编码 59 纠正单个错误的汉明码中，r位校正子码组与误码图样一一对应，最充分地利用了监督位所能提供的信息，这种码称为完备码。在一般情况下，对于能
37、纠正t个错误的线性分组码(n，k)，应满足不等式(10.3.22)第10章 差错控制编码 60 这里，为中n取i的组合，其物理意义是n位码组中有i个误码的错误图样数目(i0)。式(10.3.22)取等号时，校正子与误码不超过t个的所有错误图样一一对应，监督码元得到最充分的利用，这种(n，k)码即为完备码。除了汉明码外，迄今为止已找到的唯一能纠正多个错误的完备码是(23，12)非本原BCH码，常称为戈雷码。第10章 差错控制编码 6110.4 10.4 循环码循环码 循环码是线性分组码中一个最重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，所以循环码受到人们的高度重视，在前向纠错系统中
38、得到了广泛应用。循环码有严密的代数理论基础，是目前研究得最成熟的一类码。这里对循环码不作严格的数学分析，只重点介绍循环码在差错控制中的应用。第10章 差错控制编码 62 10.4.1 10.4.1 循环码的特点循环码的特点 循环码有两个数学特征：1）线性分组码的封闭性封闭性；2）循环性循环性，即任一许用码组经过循环移位后所得任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组。到的码组仍为该许用码组集合中的一个码组。表10.4.1列出了某(7，3)循环码的全部码组。第10章 差错控制编码 63 以2号码组(0010111)为例，左移循环一位变成3号码组(0101110)，依次左
39、移一位构成的状态图如图10.4.1所示。第10章 差错控制编码 64 可见除全零码组外，不论循环右移或左移，移多少位，其结果均在该循环码组的集合中(全零码组自己构成独立的循环圈)。为了用代数学理论研究循环码，可将码组用多项将码组用多项式表示，称为式表示，称为码多项式码多项式。循环码组中各码元分别为多。循环码组中各码元分别为多项式的系数。项式的系数。长度为n的码组A=(an-1 an-2 a1 a0)用码多项式可表示为(10.4.2)第10章 差错控制编码 65 若左移i位后的码组A(i)=(an-i-1 an-i-2 an-i+1 an-i)，其码多项式为 A(i)(x)可以用下式由xiA(x
40、)求得:这里Q(x)是xiA(x)除以(xi+1)的商式，而A(i)(x)是所得的余式。式(10.4.4)也可表示为(10.4.3)(10.4.4)(10.4.5)第10章 差错控制编码 66 在A(x)的表达式中，系数ai=0的项常略去不写，ai=1的项只写符号x及其幂次。码多项式之间可以进行代数运算，在二元码中遵循模2运算的规则。根据线性码的封闭性，任意两码字经模运算后仍为本码组中的码字。从代数学的角度，每个二进制码组可以看成是只有0和1两个元素的二元域中的n重。所有二元n重的集合称为二元域上的一个矢量空间。二元域上只有两种运算，即加和乘，所有运算结果也必定在同一个二元集合中。第10章 差
41、错控制编码 67 在二元域中加和乘的运算规则定义为 一组多项式就构成一个(n,k)循环码。也就是说，阶数小于等于n-1能被g(x)除尽的每个多项式都是该循环码的许用码组许用码组。(n,k)循环码有2k个码组，因为可以构成循环许用码组A(x)的信息码组m(x)有2k个。第10章 差错控制编码 68 这里，m(x)为不大于k-1阶的多项式。例如，令n7，g(x)x4+x3+x2+1是x7+1的一个因式，共有8个阶次不大于6的多项式是g(x)的倍式，即(10.4.6)第10章 差错控制编码 69 这8个多项式是一个(7，3)循环码。由于它有8个码组，k3，因此n-k7-34，这必定是生成多项式的阶次
42、。为了寻找生成多项式，必须对xn+1进行因式分解，这可以用计算机来完成。对于某些n值，xn+1只有很少几个因式，因而码长为这些n值的循环码很少。仅对于很少几个n值才有很多因式。第10章 差错控制编码 70 对于任意n值有 若取x+1为生成多项式，这样构成的循环码就是简单的偶监督码(n，n-1)。由于g(x)为一阶多项式，因此只有一位监督码。可以证明，x+1的任何倍式的码重（即码组中1的个数）必定保持偶数。这是一种最简单的循环码，dmin=2。(10.4.7)第10章 差错控制编码 71 另一个最简单的循环码是以xn-1+xn-2+x+1为生成多项式，由于生成多项式是n-1阶故信息码位为1。只有
43、两种码组即全0和全1，因此这种循环码是重复码(n，1)，dmin=n。任何(n,k)循环码的生成多项式g(x)，用乘上(x+1)后得到生成多项式g(x)(x+1)所构造的循环码(n，k-1)，其最小码距增加1。(n，k-1)码是(n，k)码的一个子集。第10章 差错控制编码 72 以因式分解中的本原多项式作为生成多项式，可以构造出纠正一个错误的循环汉明码。考查表10.4.1，其中n-k=4阶的多项式只有编号为(2)的码组(0010111)，所以表中所示(7，3)循环码组的生成多项式g(x)=x4+x2+x+1，并且该码组集合中的任何码多项式A(x)都可由信息位乘以生成多项式得到第10章 差错控
44、制编码 73 式中(mk-1 mk-2 m1 m0)为信息码元。对于(7，k)循环码，有 表10.4.1中所示(7，3)循环码组的g(x)，是由式(10.4.9)中第1、3两项相乘得到的。如果令式(10.4.9)中第1、2两项相乘，也得到一个4阶多项式，由它可以构成另一个(7，3)循环码组的集合。可见选择不同的因式组合会得到不同的生成多项式，从而构成不同的循环码组。(10.4.8)(10.4.9)第10章 差错控制编码 74 由于g(x)为n-k阶多项式，以与此相对应的码组作为生成矩阵中的一行，可以证明g(x)，xg(x)，xk-1g(x)等多项式必定是线性无关的。把这k个多项式相对应的码组作
45、为各行构成的矩阵即为生成矩阵，由各行的线性组合可以得到2k个循环码码组。这样循环码的生成矩阵多项式可以写成(10.4.10)第10章 差错控制编码 75 以表10.4.1中的生成多项式g(x)构造G(x)，相应的矩阵形式为 作线性变换，整理成典型形式的生成矩阵(10.4.12)(10.4.11)第10章 差错控制编码 76 信息码元与式(10.4.12)相乘，得到的就是系统循环码。由式(10.4.10)生成矩阵得到的循环码并非系统码。在系统码中码组的最左k位是信息码元，随后是n-k位监督码元。这相当于码多项式为第10章 差错控制编码 77 这里r(x)=rn-k-1xn-k-1+r0为监督码多
46、项式，其相应的监督码元为(rn-k-1,r0)。由式(10.4.14)可知 可见，构造系统循环码时，只需将信息码多项式升n-k阶(即乘上xn-k)，然后以g(x)为模，即除以g(x)，所得余式r(x)即为监督码元。因此，系统循环码的编码过程就变成用除法求余的问题。系统码的生成矩阵为典型形式G=Ik Q，与单位矩阵Ik每行对应的信息多项式为(10.4.14)(10.4.15)第10章 差错控制编码 78由式(10.4.15)可得相应的监督多项式为 由此得到生成矩阵中每行的码多项式为因此系统循环码生成矩阵多项式的一般表示为(10.4.18)(10.4.17)(10.4.16)第10章 差错控制编码
47、 79 10.4.3 10.4.3 监督多项式与监督矩阵监督多项式与监督矩阵 如前所述，在(n,k)循环码中，xn+l可分解成g(x)和其它因式的乘积，记为 由于g(x)是常数项为1的r次多项式，则h(x)为k次多项式,即h(x)=hk xk+h1x+h0,称h(x)为监督多项式。若g(x)=gn-kxn-k+g1x+g0，由式(10.4.19)可知，必定有(10.4.19)第10章 差错控制编码 80 这样可以得到循环码的监督矩阵为 它有n-k行n列，完全由h(x)的系数确定，可以证明GHT=0。(10.4.20)(10.4.21)第10章 差错控制编码 81 与式(10.4.10)给出的G
48、 G(x)相对应，监督矩阵多项式可用下式表示 其中h*(x)是h(x)的逆多项式。典型形式的监督矩阵可以由式(10.4.22)作线性变换得到。(10.4.22)第10章 差错控制编码 82 例例10.4.1 10.4.1 已知已知(7(7，4)4)系统码的生成多项式为系统码的生成多项式为g(x)=x3+x2+1，求生成矩阵。求生成矩阵。解：由式解：由式(10.4.16)可得可得(10.4.23)第10章 差错控制编码 83因此，生成矩阵多项式表示为因此，生成矩阵多项式表示为由多项式系数得到的生成矩阵为由多项式系数得到的生成矩阵为(10.4.25)(10.4.24)第10章 差错控制编码 84
49、10.4.4 10.4.4 系统循环码的编译码方法系统循环码的编译码方法 1.1.系统循环码的编码系统循环码的编码 对于码组前k位是信息码元的系统码，用多项式表示则为 式中，m(x)是不大于(k-1)次的多项式，代表信息信息码元码元；r(x)是不大于(r-1)次的多项式，代表监督码元监督码元。若令式(10.4.8)中的信息码元为m(x)，则码组多项式可写成(10.4.27)(10.4.26)第10章 差错控制编码 85 联立式(10.4.26)、式(10.4.27)得 即 这就是循环码编码的数学依据，式中为m(x)商，r(x)为余式。(10.4.28)第10章 差错控制编码 86 利用生成多项
50、式利用生成多项式g g(x x)作除法运算的循环码编码方作除法运算的循环码编码方法归纳如下法归纳如下:1 1）信息多项式）信息多项式m(x)左移左移n-k位，即相当于位，即相当于m(x)乘乘因子因子xn-k；2 2）以）以g(x)为除式作模运算，得余式为除式作模运算，得余式r(x)；即；即 3 3）余式的系数作监督码元，附加在信息码元之后）余式的系数作监督码元，附加在信息码元之后形成系统码，相当于令余式形成系统码，相当于令余式r(x)和已经左移和已经左移n-k位的信位的信息码多项式作按位模息码多项式作按位模2 2加运算。即加运算。即(10.4.29)(10.4.30)第10章 差错控制编码 8
