指导教师杨建国二零零七年十一月

《指导教师杨建国二零零七年十一月》由会员分享，可在线阅读，更多相关《指导教师杨建国二零零七年十一月（99页珍藏版）》请在金锄头文库上搜索。

1、指导教师:杨建国二零零七年十一月指导教师指导教师: :杨建国杨建国二零零八年三月2盛威网：专业的计算机学习网站第十章 差错控制编码10.1 概述 10.2 检错与纠错原理 10.3 简单分组码 10.4 线性分组码 10.5 循环码 10.6 卷积码 3盛威网：专业的计算机学习网站10.1 概 述 10.1.1 信源编码与信道编码 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗

2、干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外 ，还可以采用信道编码技术。4盛威网：专业的计算机学习网站10.1.2 差错控制方式常用的差错控制方式有三种：检错重发、前向纠错和混合纠错。它们的系统构成如图101所示, 图中有斜线的方框图表示在该端检出错误。 5盛威网：专业的计算机学习网站图10-1 差错控制方式的系统构成 6盛威网：专业的计算机学习网站1. 检错重发方式检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判

3、决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效， 但实时性差，主要在计算机数据通信中得到应用。 7盛威网：专业的计算机学习网站2. 前向纠错方式前向纠错方式记作FEC(Forword Error Correction)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。 8盛威网：专业的计算机学习网站3. 混合纠错方式混合纠错方式记作HEC(Hybrid Error Correction)是FEC和ARQ方式的结合。发端发送具有自动

4、纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广泛应用。 9盛威网：专业的计算机学习网站另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道， 错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错

5、误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。 10盛威网：专业的计算机学习网站10.2.1纠错码的分类 (1) 根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组 线性方程式，则称为线性码，否则为非线性码。(2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不 仅与本组的信息元有关， 而且还与前面若干组的信息元有关 。(3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能 检错。 10.2 检错与纠错原理 11盛威网：专业的

6、计算机学习网站1. 分组码分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元， 组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。 10.2.2检错与纠错的原理 12盛威网：专业的计算机学习网站在分组码中，非零码元的数目称为码字的汉明重量， 简称码重。例如，码字 10110，码重w=3。两个等长码组之间相应位取值不同的数目称为这两

7、个码组的汉明(Hamming)距离， 简称码距。例如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d表示。最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据。 13盛威网：专业的计算机学习网站2. 检错和纠错能力 若分组码码字中的监督元在信息元之后，而且是信息元的简单重复， 则称该分组码为重复码。它是一种简单实用的检错码， 并有一定的纠错能力。例如(2,1)重复码，两个许用码组是 00 与 11，d0=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是 000 与111,

8、 d0=3; 当收端出现两个或三个 1 时，判为 1，否则判为 0。此时，可以纠正单个错误，或者该码可以检出两个错误。 14盛威网：专业的计算机学习网站码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:(1) 检测e个随机错误，则要求码的最小距离d0e+1;(2) 纠正t个随机错误， 则要求码的最小距离d02t+1;(3) 纠正t个同时检测e(t)个随机错误，则要求码的最小距离d0t+e+1。 15盛威网：专业的计算机学习网站3. 编码效率用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:其中, k是信息元的个数，

9、n为码长。对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。 际中要根据具体指标要求， 保证有一定纠、 检错能力和编码效率，并且易于实现。 （10-1）16盛威网：专业的计算机学习网站10.2.1 奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元， 使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。 10.3简单分组码17盛威网：专业的计算机学习网站设码字A=an-1,an-2,a1,a0，对偶监督码有 奇监督码情况相似， 只是码组中“1”的数目为奇数， 即 满足条件

10、 而检错能力与偶监督码相同。奇偶监督码的编码效率R为 (10-2)(10-3)18盛威网：专业的计算机学习网站10.3.2 水平奇偶监督码为了提高奇偶监督码的检错能力，特别是克服其不能检测突发错误的缺点，可以将经过奇偶监督的码元序列按行排成方阵，每行为一组奇偶监督码，如表10-1所示。发送时按列的顺序传输，接收时仍将码元序列还原为发送时的方阵形式，然后按行进行奇偶校验。 19盛威网：专业的计算机学习网站表10-1水平奇偶监督码 20盛威网：专业的计算机学习网站10.3.3 行列监督码奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。这种码不仅对水平(行)方向的码元，而且对垂直(列

11、)方向的码元实施奇偶监督。这种码既可以逐行传输，也可以逐列传输。一般地，LM个信息元附加L+M+1个监督元，组成(LM+L+M+1,LM)行列监督码的一个码字(L+1行，M+1列)。图 10-2 是(66,50)行列监督码的一个码字。这种码具有较强的检测能力，适于检测突发错误，还可用于纠错。 21盛威网：专业的计算机学习网站表10-2 (66,50)行列监督码 22盛威网：专业的计算机学习网站10.3.4群计数码把信息码元中“1”的个数用二进制数字表示，并作为监督码元放在信息码元的后面，这样构成的码称为群计数码。例如，一码组的信息码元为1010111，其中“1”的个数为5，用二进制数字表示为“

12、101”，将它作为监督码元附加在信息码元之后，即传输的码组为1010111101。群计数码有较强的检错能力，除了同时出现码组中“1”变“0”和“0”变 “1”的成对错误外，它能纠正所有形式的错误。 23盛威网：专业的计算机学习网站10.3.5 恒比码 码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码，定 1 码。这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。 目前我国电传通信中普遍采用 32 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的

13、不同码组数目等于从 5 中取 3 的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字，如表 7 - 1 所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。 24盛威网：专业的计算机学习网站表 10-3 32 恒比码 25盛威网：专业的计算机学习网站10.4 线 性 分 组 码 10.4.1基本概念在(n,k)分组码中，若每一个监督元都是码组中某些信息元按模二加而得到的，即监督元是按线性关系相加而得到的，则称为线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线性分组码。线性分组码是一类重要的纠错码，应用很广泛。现以（7，3

14、）分组码为例说明线性分组码的意义和特点。 26盛威网：专业的计算机学习网站现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元， 可用下列线性方程组来描述该分组码，产生监督元。 (10-)27盛威网：专业的计算机学习网站表10-4（7，3）分组码的八个码字 28盛威网：专业的计算机学习网站我们可以把(n，k)线性分组码看成一个n维线性空间，每一个码字就是这个空间的一个矢量。n维线性空间长度为n的码组共有2n个，但线性分组码的码字共有2k个，kn。显然，这2k个分组码构成了n维线性空间的K维线性子空间，

15、它是线性分组码的许用码组，剩余的空间构成的码组是禁用码组。 29盛威网：专业的计算机学习网站10.4.2汉明(Hamming)码汉明码是一种用来纠正单个错误的线性分组码，已作为差错控制码广泛用于数字通信和数据存储系统中。一般来说，若码长为n，信息位为k，则监督元为r=n-k。如果求用r个监督位构造出r个监督方程能纠正一位或一位以上错误的线性码，则必须有 2r-1n （10-5） 现以(n,k)汉明码为例来说明线性分组码的特点。 30盛威网：专业的计算机学习网站在前面讨论奇偶监督码时，如考虑偶监督，则用式（10-2）作为监督方程，而在接收端译码时，实际是按下式计算 的： (10-6) 若S=0，

16、就认为无错；若S=1，就认为有错，我们称上式为监督 方程，S校正子（校验子），又称伴随式。如果增加一位监督 元，就可以写出两个监督方程，计算出两个校正子S1和S2。S1S2 为00时，表示无错；S1S2为01、10、11时，指示3种不同的错误 图样。由此可见，若有r位监督元，就可以构成r个监督方程， 计算得到的校正子有r位，可用来指示2r-1种不同的错误图样，r位校正子为全零时，表示无错。 31盛威网：专业的计算机学习网站设分组码中信息位k=4，又假设该码能纠正一位错码，这时d03，要满足2r-1n，取r3时，当r=3时，n=k+r=7，这样就构成了（7，4）汉明码。这里用A=a6 a5 a4 a3 a2 a1 a0表示码字，其中前4位是信息元，后3位是监督元，用S1，S2，S3表示由3个监督方程得到的3个校正子。3个校正子S1，S2，S3指示23-1种不同的错误图样，校正子与错码位置的对应关系如表10-5所示。 32盛威网：专业的计