通信原理教程第十章

1、大连海事大学信息科学技术学院大连海事大学信息科学技术学院1 1 1 1第第1010章章 信道编码和差错控制信道编码和差错控制10.1 10.1 引言引言 10.10.2 2 常用的几种简单分组码常用的几种简单分组码 10.10.3 3 线性分组码线性分组码 10.10.4 4 循环码循环码 10.10.5 5 卷积码卷积码 10.10.6 6 本章小结本章小结大连海事大学信息科学技术学院大连海事大学信息科学技术学院2 2 2 210.1 引言引言10.1.1 信道编码信道编码 在数字通信中，编码可分为信源编码信源编码和信道编码信道编码。 信源编码是为了提高数字信号的有效性以及为了使模拟信号数字

2、化而采取的编码。 信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。 数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术信道编码技术。大连海事大学信息科学技术学院大连海事大学信息科学技术学院3 3 3 3信道编码：n目的：提高信号传输的可靠性。n方法：增加多余比特，以发现或纠正错误。 差错控制：包括信道编码在内的一切纠正错误手段。产生错码的原因：n乘性干扰引起的码间串扰n加性干扰引起的信噪比降低大连海事大学信息科学技术学院大连海事大学信息科学技术学院4

3、4 4 4信道分类：按照加性干扰造成错码的统计特性不同加性干扰造成错码的统计特性不同划分n随机信道：错码随机出现，各个错码出现是统计独立的。例如由白噪声引起的错码。恒参高斯白噪声信道是典型的随机信道n突发信道：错码相对集中出现，即在短时间段内有很多错码出现，而在这些短时间段之间有较长的无错码时间段，例如由脉冲干扰引起的错码。具有脉冲干扰的信道是典型的突发信道。 n混合信道：信道中的错码既有随机的又有突发的。短波信道和对流层散射信道是典型的混合信道。大连海事大学信息科学技术学院大连海事大学信息科学技术学院5 5 5 510.1.2 差错控制方式差错控制方式 图 10-1 差错控制方式 发端纠错码

4、收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号大连海事大学信息科学技术学院大连海事大学信息科学技术学院6 6 6 6 1. 检错重发方式检错重发方式 检错重发又称自动请求重传方式，记作ARQ (Automatic Repeat Request)。 需要反馈信道 译码设备简单 对突发错误和信道干扰较严重时有效（相对于FEC而言） 但实时性差。 主要用在计算机数据通信中，另外海上通信NBDP中也使用ARQ。大连海事大学信息科学技术学院大连海事大学信息科学技术学院7 7 7 7 2. 前向纠错方式前向纠错方式 前向纠错方式记作FEC ( Forwar

5、d Error Correction)。 发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。 单向传输 实时性好 但译码设备较复杂。 海上卫星通信Inmarsat-A中采用。大连海事大学信息科学技术学院大连海事大学信息科学技术学院8 8 8 8 3. 混合纠错方式混合纠错方式 混合纠错方式记作HEC (Hybrid Error Correction)是FEC和ARQ方式的结合。 发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。 这种方式具有自动纠错

6、和检错重发的优点，可以达到较低的误码率。近年来得到广泛应用，如海上卫星通信Inmarsat-C中应用。大连海事大学信息科学技术学院大连海事大学信息科学技术学院9 9 9 910.1.3 纠错码的分类纠错码的分类 (1) 根据纠错码各码组信息元和监督元的函数关系，可分为线性码线性码和非线性码非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组码分组码的各码元仅与本组的信息元有关；卷积码卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码

7、以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。 大连海事大学信息科学技术学院大连海事大学信息科学技术学院10101010编码序列的参数nn 编码序列中总码元数量nk 编码序列中信息码元数量nr 编码序列中差错控制码元数量；n差错控制码元称为监督码元或监督位nk/n 编码效率n(n - k) / k = r / k 冗余度大连海事大学信息科学技术学院大连海事大学信息科学技术学院11 11 11 1110.1.4 纠错编码的基本原理分组码举例n设：有一种由3个二进制码元构成的编码，它共有23 = 8种n不同的可能码组：000 晴 001 云 010 阴 011 雨100 雪 101

8、 霜 110 雾 111 雹这时，若一个码组中发生错码，则将收到错误信息。大连海事大学信息科学技术学院大连海事大学信息科学技术学院12121212 若在此8种码组中仅允许使用4种来传送天气，例如：令000 晴 011 云 101 阴 110 雨为许用码组，其他4种不允许使用，称为禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。p这种编码只能检测错码，不能纠正错码。 n若规定只许用两个码组：例如000 晴 111 雨就能检测两个以下错码，或纠正一个错码。 大连海事大学信息科学技术学院大连海事大学信息科学技术学院13131313 00 ：晴 01 ：云 10 ：阴 11 ：雨0001

9、1011如果不要求检（纠）错，为了传输4种不同的信息，只需两位码组就够了，它们是：00，01，10，11。大连海事大学信息科学技术学院大连海事大学信息科学技术学院14141414 00 0：晴 01 1：云 10 1：阴 11 0：雨000010100110001101111011信息位监督位代表所传输信息的这些两位码称为信息位。多增加的那位称为监督位。把这种将信息码分组，为每组信码附加若干监督码的编码集合，称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。第1位：1第2位：1第3位：1大连海事大学信息科学技术学院大连海事大学信息科学技术学院15151515 1. 分组码分组码 分组码

10、一般可用(n, k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。 krn大连海事大学信息科学技术学院大连海事大学信息科学技术学院16161616k个信息位r个监督位an-1an-2.arar-1ar-2.a0t码长 n = k + r分组码的结构大连海事大学信息科学技术学院大连海事大学信息科学技术

11、学院17171717 在分组码中，非零码元“1”的数目称为码字的汉明(Hamming)重量， 简称码重。例如，码字 10110，码重w=3。 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离，简称码距。例如 11000 与 10011之间的距离d=3。 在码组集中，任意两个码字之间距离的最小值称为码的最小距离，用d表示。 最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。 大连海事大学信息科学技术学院大连海事大学信息科学技术学院18181818 码距的几何意义：以n = 3的编码为例 一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离。 各顶点

12、之间沿多面体各边行走的几何距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1码字（a2 a1 a0 )大连海事大学信息科学技术学院大连海事大学信息科学技术学院191919192. 检错和纠错能力检错和纠错能力 若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码重复码。它是一种简单实用的检错码，并有一定的纠错能力。 例如，(2,1)重复码，两个许用码组是 00 与 11，d0=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是 0

13、00 与111, d0=3; 当收端出现两个或三个 1 时，判为 1，否则判为0。此时，可以纠正单个错误，或者该码可以检出两个错误。大连海事大学信息科学技术学院大连海事大学信息科学技术学院20202020 码的最小距离码的最小距离d0直接关系着码的检错和纠错能力：直接关系着码的检错和纠错能力： 任一任一(n, k)分组码，若要在码字内分组码，若要在码字内: (1) 检测检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d0e+1; 0 1 2 3BAed0码距等于3的两个码组大连海事大学信息科学技术学院大连海事大学信息科学技术学院21212121 设一码组A位于0点，若码组A中

14、发生一位错码，则可以认为A的位置将移到以0点为圆心、以1为半径的圆上某点，但其位置不会超过此圆； 若码组A中发生两位错码，则其位置不会超出以0点为圆心，以2为半径的圆，因此，只要最小码距不小于3(如图中B点)，在此半径为2的圆上及圆内就不会有其他码组，也就是说，码组A发生两位以下错码时，不可能变成另一任何许用码组，因而能检测错码的位数为2。 同理，若一种编码的最小码距为d0，则将能检测（ d0 -1）个错码；反之，若要检测e个错码，则最小码距至少应不少于（e+1）。大连海事大学信息科学技术学院大连海事大学信息科学技术学院22222222 (2) 纠正纠正t个随机错误，则要求码的最小距离个随机错

15、误，则要求码的最小距离d02t+1;BtA012345td0码距等于5的两个码组若码组A和B发生不多于t位错误，则其位置均不会超出以C1和C2为圆心，t为半径的圆，只要这两个圆不相交，则当误码小于t时，可根据它们落入哪个圆内，就可正确地判为A或B，即可纠错。以C1、C2为圆心，以t为半径的两圆不相交的最近圆心距离为2t+1，即为纠t个错误的最小距离。大连海事大学信息科学技术学院大连海事大学信息科学技术学院23232323(3) 纠正纠正t个同时检测个同时检测e(t)个随机错误，则要求码的个随机错误，则要求码的最小距离最小距离d0t+e+1。AB1tte码距等于(e+t+1)的两个码组 “纠正t

16、个错误，同时检测e个错误”，简称“纠检结合”。差错控制设备按照接收码组与许用码组的距离自动改变工作方式。若接收码组与某一许用码组间的距离在纠错能力t范围内，则将按纠错方式工作，若与任何码组间的距离都超过t，则按检错方式工作。 大连海事大学信息科学技术学院大连海事大学信息科学技术学院24242424AB1tte码距等于(e+t+1)的两个码组 证明：设码的检错能力为e，则当码组A中存在e个错码时，该码组与任一许用码组的距离至少应为t+1，否则将进入许用码组B的纠错能力范围内，而被错纠为B。 因此，要求最小码距满足(3)。大连海事大学信息科学技术学院大连海事大学信息科学技术学院25252525 3

17、. 编码效率编码效率 用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。定义编码效率R来衡量有效性:R=k/n其中, k是信息元的个数，n为码长。 对纠错码的基本要求是: 检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。 实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。 大连海事大学信息科学技术学院大连海事大学信息科学技术学院262626264. 差错控制编码的效用 设信道发生01和10的错误概率都为p，则在码长为n的码组中，恰好发生r个错码的概率为 以n=7, p=10-3为例，则 P7(1)=7p=710-3 P7(2)=21p2=2.110

18、-5 P7(3)=35p3=3.510-8!( )(1)()!()!1( )!()!rrnrrnrnnrnpnP rC ppprnrnP rprnr-=-=-可见，采用差错控制编码，即使仅能纠正(或检测)1-2个错误，也可使误码率下降几个数量级。大连海事大学信息科学技术学院大连海事大学信息科学技术学院2727272710.2 常用的几种简单分组码常用的几种简单分组码10.2.1 奇偶监督码奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码它是含一个监督元，码重为奇数或偶数的重为奇数或偶数的(n, n-1)(n, n-1)分组码

19、分组码。 奇偶监督码又分为奇监督码和偶监督码，检错能力相同。 设码字A=an-1,an-2,a1,a0对偶监督码有对奇监督码有奇偶监督码的编码效率12100nnaaaa-排排=12101nnaaaa-排排=1nRn-=大连海事大学信息科学技术学院大连海事大学信息科学技术学院28282828 检错能力：能够检测奇数个错码。奇偶监督码不能检测码组中出现的偶数个错码。10.2.2 行列监督码（二维奇偶监督码、方阵码） 11na12na11a10a21na22na21a20amna1mna2ma1ma01nc2nc1c0c.有可能检测偶数个错码适合检测突发错码 能够纠正部分错码水平校验元垂直校验元信元

20、大连海事大学信息科学技术学院大连海事大学信息科学技术学院29292929 编码器按行（每行n-1个码）分组（共m组）输入信元，对每行按奇或偶校验加水平校验元，再对每列按奇或偶校验加垂直校验元后，按列次序输出传送。 方阵码可以检测全部奇数个错码和大部分偶数个错码；但不能检测出行、列中同时出现偶数个错的情况（即不能检测出矩形四角位置上同时出现错码的情况）；适合检测突发长度 （m+1)的所有突发差错；且能够纠正部分错码，例如，当码组中仅在某一行中有奇数个错码时就能够确定错码的位置，从而纠正错码。 方阵码容易实现，检错性能优良，故被广泛应用。 编码效率为：(1)(1)m nRmn-=+大连海事大学信息

21、科学技术学院大连海事大学信息科学技术学院3030303010.2.3 恒比码恒比码 码字中1的数目与0的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码，定 1 码。这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。 目前我国电传通信中普遍采用 3 2 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的不同码组数目等于从 5 中取 3 的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字，如表 9 - 1 所示。而每个汉字又是以四位十进制数来代表的。实践证明，

22、采用这种码后，我国汉字电报的差错率大为降低。 大连海事大学信息科学技术学院大连海事大学信息科学技术学院31313131表表 10-1 3 2 恒比码恒比码 每个码组的长度为 5，其中 3 个“1”大连海事大学信息科学技术学院大连海事大学信息科学技术学院3232323210.2.4 正反码 正反码是一种简单的能够纠正错码的编码。其监督位数目与信息位数目相同。 （1）当信息位中有奇数个“1”时，监督码元与信息码元相同（是信息码元的重复） （2）当信息位中有偶数个“1”时，监督码元与信息码元相反（是信息码的反码）。 编码效率：R1/2大连海事大学信息科学技术学院大连海事大学信息科学技术学院33333

23、33310.3 线线 性性 分分 组组 码码 1. 基本概念：基本概念： 代数码代数码 ：利用代数关系式产生监督位的编码。 线性分组码线性分组码：代数码的一种，其监督位和信息位的关系由线性代数方程决定。 汉明码汉明码：一种能够纠正一个错码的线性分组码。：一种能够纠正一个错码的线性分组码。 校正子校正子： 在偶数监督码中，计算 实际上就是计算 ，并检验S是否等于0。S称为校正子。 监督关系式监督关系式： 称为监督关系式。称为监督关系式。0021aaann021aaaSnn021aaaSnn大连海事大学信息科学技术学院大连海事大学信息科学技术学院343434342. 纠错基本原理纠错基本原理 中，

24、S只有两种取值，只能表示有错和无错，而不能进一步指明错码的位置。 若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。 两个校正子的可能取值有4种组合，即00，01，10，11，能表示4种不同的信息。 若用其中一种组合表示无错码，则其他3种组合可以用于指明一位错码的3种不同位置，从而可以有纠错能力。021aaaSnn大连海事大学信息科学技术学院大连海事大学信息科学技术学院35353535 一般而言，若有一般而言，若有 r r 个监督关系式，则个监督关系式，则 r r 个校正个校正子可以指明一个错码的子可以指明一个错码的 (2(2r r 1) 1) 个不同位置个不同位置。 当

25、校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求2121rrnkr 或大连海事大学信息科学技术学院大连海事大学信息科学技术学院36363636汉明码：一种能够纠正一个错码的线性分组码。一种能够纠正一个错码的线性分组码。例：要求设计一个能够纠正1个错码的分组码(n, k)，设给定的码组中有4个信息位，即k = 4。 由 知，这时要求监督位数r 3。若取r = 3，则n = k + r = 7。现在用a6 a5 a4 a3 a2 a1 a0表示这7个码元，用S1 S2 S3表示校正子，则这3个校正子恰好能够指明23 1 = 7个错码的位置。若规定校正

26、子和错码位置的关系如下表：注：也可规定另外的关系表。2121rrnkr 或大连海事大学信息科学技术学院大连海事大学信息科学技术学院37373737S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码24561aaaaS13562aaaaS03463aaaaS则仅当一错码位置在a6 、a5 、a4 或a2时，校正子S1的值才等于1；否则S1的值为零。这就意味着a6 a5 a4 a2四个码元构成偶数监督关系：同理有大连海事大学信息科学技术学院大连海事大学信息科学技术学院38383838在编码时，信息

27、位a6 a5 a4 a3的值决定于输入信号，它们是随机的。监督位a2 a1 a0是根据信息位的取值，按照监督关系确定的，它们应保证上列3式中的校正子等于0，即有给定信息位后，为了计算监督位，上式可以改写为000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa大连海事大学信息科学技术学院大连海事大学信息科学技术学院39393939按照上式计算结果为信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a00000000100011100010111001100001010110100

28、100011110101100101001101100001010110111010100110011111010001110001111111大连海事大学信息科学技术学院大连海事大学信息科学技术学院40404040在接收端解码时，对于每个接收码组，先按式计算出校正子S1，S2和S3，然后按照下表判断错码的位置。24561aaaaS13562aaaaS03463aaaaSS1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码大连海事大学信息科学技术学院大连海事大学信息科学技术学院41414141

29、例：若接收码组为0000011，则按上三式计算得到：S1 = 0，S2 = 1，S3 = 1。这样，由上表可知，错码位置在a3。 上例中的汉明码是(7, 4)码，其最小码距d0 = 3。由式 和 可知，此码能够检测2个错码，或纠正1个错码。 汉明码的码率：当r (或n)很大时，上式趋近于1。所以汉明码是一种高效编码。 汉明码是一种可纠一位错的线性分组码，汉明码是一种可纠一位错的线性分组码，其码参数为其码参数为：n = 2r-1, k = n - r = 2r - 1 - r, r 3 , d0 = 3。 如：如：（1515，1111）汉明码中汉明码中 r = 4。10 ed120 td1212

30、rrrnk大连海事大学信息科学技术学院大连海事大学信息科学技术学院42424242分组码的一般原理线性分组码是监督位和信息位满足一组线性方程的码，如前述(7, 4)码满足如下关系： 可以改写为上式中，已经将“”简写成“+”。本章中除非特别说明，都是指模加。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa大连海事大学信息科学技术学院大连海事大学信息科学技术学院43434343上式可以写成矩阵形式： （模2） 将上式简写为HAT = 0T 或AHT = 000

31、01011001110101011101000123456aaaaaaa大连海事大学信息科学技术学院大连海事大学信息科学技术学院44444444式中，称为监督矩阵。 H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据监督矩阵的性质监督矩阵的性质：监督矩阵H确定码组中的信息位和监督位的关系。H 的行数就是监督关系式的数目，即监督位数 r 。H 的每行中“1”的位置表示相应的码元参与监督关系。101100111010101110100HA = a6 a5 a4 a3 a2 a1 a0 称为码字 0 = 000大连海事大学信息科学技术学院大连海事大学信息科学技术学院4545454

32、5 H 可以分成两部分：例如 典型监督矩阵 式中，P 为r k阶矩阵，Ir为 r r 阶单位方阵。将具有PIr 形式的H矩阵称为典型阵。H 矩阵的各行应该是线性无关的矩阵的各行应该是线性无关的，否则将得不到 r 个线性无关的监督关系式。若一个矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。rPIH001101101011011001110大连海事大学信息科学技术学院大连海事大学信息科学技术学院46464646生成矩阵生成矩阵 可以写为上式两端分别转置后，可以变成式中，Q为k r 阶矩阵，是P的转置，即Q = PT。3456012101111011110aaaaaaa3460356145

33、62aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa大连海事大学信息科学技术学院大连海事大学信息科学技术学院47474747将Q的左边加上一个k阶单位方阵，称为生成矩阵，即 生成矩阵 G称为生成矩阵，因为可以用它产生整个码组A，即有0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA大连海事大学信息科学技术学院大连海事大学信息科学技术学院48484848生成矩阵的性质： 具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。 由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于

34、其后。这种形式的码组称为系统码系统码。 生成矩阵G的各行也必须是线性无关的。原因 如果已有k个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。继续继续大连海事大学信息科学技术学院大连海事大学信息科学技术学院49494949 任一码组A都是G的各行的线性组合； 共有行，若它们线性无关，则可组合出k种不同的码组A，它恰好是k位信息位的全部码组； 若G的各行有线性相关的，则不可能由G生出k种不同码组。 实际上，G的各行本身就是一个码组。返回返回大连海事大学信息科学技术学院大连海事大学信息科学技术学院50505050错误图样错误图样设：发送码组A是一个n列的行矩阵： 接收码组是一个n

35、列的行矩阵B： 令接收码组和发送码组之差为 E就是错码的行矩阵： ，称为错误图样。0121aaaaAnn0121bbbbBnnB A = E (模2)0121eeeeEnn大连海事大学信息科学技术学院大连海事大学信息科学技术学院51515151式中， (i = 0, 1, , n-1)若ei = 0，表示该码元未错；若ei = 1，表示该码元为错码。 B A = E 可以改写成 B = A + E上式表示发送码组A与错码矩阵E之和等于接收码组B。 例如， 若发送码组A = 1 0 0 0 1 1 1， 错码矩阵E = 0 0 0 0 1 0 0， 则 接收码组B = 1 0 0 0 0 1 1

36、。iiiiiababe当当, 1, 0校正子矩阵校正子矩阵：大连海事大学信息科学技术学院大连海事大学信息科学技术学院52525252在接收端解码时，将接收码组B代入式AHT = 0中A的位置进行计算。（1）若接收码组中无错码，则B = A。代入后，该式仍成立，即有BH T = 0（2）当接收码组有错时，E0，将B带入AHT = 0 中，该式不一定成立。 (a)只有当错码较多，已经超出这种编码的检测能力时，B变为另一许用码组，上式才成立。 (b)当错码未超过检错能力时，上式不成立，即其右端不为0。假设此时该式的右端等于S，即有大连海事大学信息科学技术学院大连海事大学信息科学技术学院5353535

37、3 BH T = S将B = A + E 代入上式，得到: S = (A + E) H T = AH T + EH T 上式右端第一项等于0，所以 S = EH T将S称为校正子校正子。 当H 确定后，上式中S只与E 有关，而与A 无关。这意味着，S 和错码和错码E 之间有确定的线性变换关系之间有确定的线性变换关系。 若S 和E 有一一对应关系，则S 将能代表错码位置。大连海事大学信息科学技术学院大连海事大学信息科学技术学院54545454线性码的封闭性：线性码的封闭性： 若若A1和和A2是一种线性码中的两个码组，则是一种线性码中的两个码组，则(A1+A2)仍是其仍是其中一个码组。中一个码组。

38、 证 若A1和A2是两个码组，则有：A1HT = 0, A2HT = 0 将上两式相加，得出 A1HT + A2HT = (A1 + A2 ) HT = 0 所以，(A1 + A2)也是一个码组。 由于线性码具有封闭性，所以两个码组两个码组(A1和和A2)之间的距之间的距离（即对应位不同的数目）必定是另一个码组离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量的重量（即（即“1”的数目）的数目）。因此，码的最小距离就是码的最小重量码的最小距离就是码的最小重量（除全（除全“0”码组外）码组外）。大连海事大学信息科学技术学院大连海事大学信息科学技术学院55555555例：已知（7，3

39、）分组码的监督关系为632152106515400000aaaaaaaaaaaaaa求其监督矩阵、生成矩阵、全部码字及纠错能力。求其监督矩阵、生成矩阵、全部码字及纠错能力。大连海事大学信息科学技术学院大连海事大学信息科学技术学院56565656解：解：将非典型H阵化为典型H阵：22341123HAT = 0T大连海事大学信息科学技术学院大连海事大学信息科学技术学院5757575701大连海事大学信息科学技术学院大连海事大学信息科学技术学院5858585810.4 循环码10.4.1 循环码的概念： 循环性是指任一码组循环一位后仍然是该编码中的一个码组。 例：一种(7, 3)循环码的全部码组如下

40、码组码组编号编号信息位信息位监督位监督位码组码组编号编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。大连海事大学信息科学技术学院大连海事大学信息科学技术学院59595959一般情况 若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组： (an-2 an-3 a0 an-1) (an-3 an-4 an-1 an-2) (a0 an-1 a2 a

41、1) 仍然是该编码中的码组。大连海事大学信息科学技术学院大连海事大学信息科学技术学院60606060多项式表示法: 一个长度为n的码组(an-1 an-2 a0)可以表示成 上式中x 的值没有任何意义，仅用它的幂代表码元的位置。 例如：码组1 1 0 0 1 0 1可以表示为 012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT大连海事大学信息科学技术学院大连海事大学信息科学技术学院6161616110.4.2 循环码的运算(1) 整数的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1 + 1 = 2 0 (模2)，1 + 2 = 3

42、1 (模2)，2 3 = 6 0 (模2)等等。 一般说来，若一个整数m可以表示为式中，Q为整数，则在模n运算下，有m p (模n) 在模在模n n运算下，一个整数运算下，一个整数m m等于它被等于它被n n除所得的余数除所得的余数。npnpQnm,大连海事大学信息科学技术学院大连海事大学信息科学技术学院62626262（2）码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有 这时，码多项式系数仍按模2运算。 例1：x3被(x3 + 1)除，得到余项即 )()()()(xRxQxNxF）（模)()

43、()(xNxRxF）（模) 1(133xx大连海事大学信息科学技术学院大连海事大学信息科学技术学院63636363 例2：因为xx3 + 1 x4 +x2 + 1x4 +x x2 +x +1 在模2运算中加法和减法一样。）（模) 1(113224xxxxx大连海事大学信息科学技术学院大连海事大学信息科学技术学院64646464（3）循环码的数学表示法 在循环码中，设T(x)是一个长度为n的码组，若则T (x)也是该编码中的一个码组。 证 设一循环码为则有 上式中的T (x) 正是码组T (x)向左循环移位 i 次的结果。）（模) 1()()(nixxTxTx012211)(axaxaxaxTn

44、nnn)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni大连海事大学信息科学技术学院大连海事大学信息科学技术学院65656565例： 一循环码为1100101，即 若给定 i = 3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 ）（模) 1()(723535893xxxxxxxxxxTx1)(256xxxxT大连海事大学信息科学技术学院大连海事大学信息科学技术学院66666666（4）循环码的生成 有了生成矩阵G，就可

45、以由k个信息位得出整个码组：例：式中，生成矩阵G的每一行都是一个码组。若能找到 k 个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。在循环码中，一个(n, k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。G34560123456aaaaaaaaaaaA0110001101001011001001111000QGkI I大连海事大学信息科学技术学院大连海事大学信息科学技术学院67676767 在循环码中

46、除全“0”码组外，再没有连续k位均为“0”的码组 ，即连0的长度最多只能有k-1位。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。 g(x)必须是一个常数项不为“0”的(n - k)次多项式，而且这个g(x)还是这种(n, k)码中次数为(n k)的唯一一个多项式。（常数项为0，右循环一次将导致k个连0）因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的。 称这唯一的(n k)次多项式g(x)为码的生成多项式码的生

47、成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。大连海事大学信息科学技术学院大连海事大学信息科学技术学院68686868 循环码的生成矩阵G可以写成 例：)()()()()(21xgxxgxgxxgxxkkG码组码组编号编号信息位信息位监督位监督位码组码组编号编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010大连海事大学信息科学技术学院大连海事大学信息科学技术学院69696969 上表中的编码为(7, 3)循环码，n

48、 = 7, k = 3, n k = 4，其中唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为g(x) = x4 + x2 + x + 1。将此g(x)代入上矩阵，得到)()()()(2xgxxgxgxxG101110001011100010111G或大连海事大学信息科学技术学院大连海事大学信息科学技术学院70707070上式不符合G = IkQ形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。 此循环码组的多项式表示式T(x)：上式表明：所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多

49、项式乘g(x)都是码多项式。 )()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG大连海事大学信息科学技术学院大连海事大学信息科学技术学院71717171（5）寻求码生成多项式 因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成T(x) = h(x)g(x) 而生成多项式g(x)本身也是一个码组，即有 T (x) = g(x) 由于码组T (x)是一个(n k)次多项式，故xk T (x)是一个n次多项式。由可知，xk T (x)在模(xn + 1)运算下也是一个码组，所以有）（模) 1()()(

50、nixxTxTx1)()(1)(nnkxxTxQxxTx大连海事大学信息科学技术学院大连海事大学信息科学技术学院72727272上式左端分子和分母都是n次多项式，故相除的商式Q(x) = 1。因此，上式可以写成将 T(x) = h(x)g(x) 和 T (x) = g(x) 代入化简后，得到上式表明：生成多项式g(x)应该是(xn + 1)的一个因子。)() 1()(xTxxTxnk)() 1()(xTxxTxnk)()(1xhxxgxkn大连海事大学信息科学技术学院大连海事大学信息科学技术学院73737373例：(x7 + 1)可以分解为为了求出(7, 3)循环码的生成多项式 g(x)，需要

51、从上式中找到一个(n k) = 4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。 ) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx二者互逆大连海事大学信息科学技术学院大连海事大学信息科学技术学院7474747410.4.3 循环码的编码方法（1） 根据给定的(n, k)值选定生成多项式g(x)，即从(xn+1)的因式中选一(n-k)次多项式作为g(x)。（2）设待编码的k位信息多项式为m(x)，用xn-k 乘m(x)：这一运算实际上是在信息码后附加上(n k)个“0

52、”。 例如，信息码为110，它写成多项式为m(x) = x2 + x。当n k = 7 3 =4时，xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示码组1100000。 （3）用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有 )()()()()(xgxrxQxgxmxkn大连海事大学信息科学技术学院大连海事大学信息科学技术学院7575例：若选定g(x) = x4 + x2 + x + 1，则有 （多项式长除）上式是用码多项式表示的运算。它和下式（长除）等效： （4）由（3）的结果经整理得： Q(x) g(x) = xn-k m(x) + r(x) T(x

53、)（令）可见：T(x)可被g(x)整除且其次数不大于（n1）次，则T(X)必为一许用码组多项式，编出的系统码码组T(x)为： T(x) = xn-k m(x) +r(x) 在上例中，T(x) = 1100000 + 101 = 110 0101 11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn10111101111101111100000注：g(x): n-k次m(x): k-1次Q(x): k-1次r(x): n-k次 信元 监元大连海事大学信息科学技术学院大连海事大学信息科学技术学院7676（5）上述4个编码步骤的实现1.软件法：a.长除法b.查表法（预先算出各种

54、信元状态所对应的r(x)， 列表成库备查）2.硬件法： 用除法电路实现，除法电路主要由一些移存器、模2加法器和控制开关构成。大连海事大学信息科学技术学院大连海事大学信息科学技术学院7777移位寄存器的个数为g(x)最高项的次数，即r个移位寄存器为P0, P1, , Pr-1。反馈线gi的连接与g(x)的非零系数相对应，且g0= gr = 1, 得出的是系统码。除法电路的一般结构如下图所示：ba大连海事大学信息科学技术学院大连海事大学信息科学技术学院7878(7, 3)循环码系统码编码电路， 取g(x) = x4 + x2 + x + 1例如：上述(7, 3)码的编码器包含四级移存器，分别用a,

55、 b, c, d表示，一个双刀双掷开关S。当信息位输入时，开关向下，输入信码一方面送入除法器进行运算，另一方面直接输出。输入k位信息全部进入除法器后，开关转向上，此时输出端接到移存器，将移存器中存贮的除法余项依次取出，同时切断反馈线，并从左到右逐次清零。fmg0gr大连海事大学信息科学技术学院大连海事大学信息科学技术学院79797979工作时，首先所有移存器清零。大连海事大学信息科学技术学院大连海事大学信息科学技术学院80808080 10.4.4 循环码的解码方法（1）在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即下式中余项r(x)应为零；否则，有误码。当接收码组中

56、的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出。 （2）在纠错时：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)。注：r(x)与E(x)必须有一一对应关系才可纠错。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。)(/)()()(/)(xgxrxQxgxR大连海事大学信息科学技术学院大连海事大学信息科学技术学院8181818110.4.5 截短循环码 截短目的： 在设计时，通常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的

57、循环码存在。故采用截短码长，得出满足要求的编码。 截短方法： 设给定一个(n, k)循环码，它共有2k种码组，现使其前i (0 i N时码树中节点自上而下重复取4种状态。在网格图中，将码树中具有相同状态的节点合并在一起，码树中的上支路用实线表示，下支路用虚线表示，支路上标注的码元为输出比特。自上而下的四行节点分别表示a, b, c, d四种状态。下图画出了5个时隙。可以看出：在第4时隙以后的网格图形完全是重复第3时隙的图形。这也反映了此(3, 1, 3)卷积码的约束长度为3。 110110110110011011011010010010101101101001001001001abcdabcd

58、000000000000000111111111111111100100100大连海事大学信息科学技术学院大连海事大学信息科学技术学院97979797abcdabcd110010001111100对于一般的(n, k, N)卷积码，可以由此推广出来以下结论： (1) 对应于每组k个输入比特，编码后产生n个输出比特。 (2) 树状图中每个节点引出2k条支路。 (3) 网格图和状态图都有2k(N-1)种可能的状态。每个状态引出2k条支路，同时也有2k条支路从其他状态或本状态引入。网格图中的编码路径举例：设起始状态为a，输入信息位为11010时，则输出编码序列是：111 110 010 100 00

59、1大连海事大学信息科学技术学院大连海事大学信息科学技术学院98989898(4) 维特比算法卷积码的译码有大数逻辑译码（门限译码）和概率译码。维特比译码属于概率译码。 基本原理：将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列。 例：设卷积码为(n, k, N) = (3, 1, 3)码 现在的发送信息位为1101为了使移存器中的信息位全部移出，在信息位后面加入了3个“0”，即1101000编码后的发送序列：111 110 010 100 001 011 000接收序列：111 010 010 110 001 011 000 (红色为错红色为错码码) 由于这是一个 (3, 1, 3)卷积码，发送序列的约束长度为N = 3，所以首先需考察3个信息段，即考察3n 9比特，即