第9章差错控制编码1课件.ppt

1、第9章 差错控制编码通信原理2023-2-71通通 信信 原原 理理 电电 子子 教教 案案第9章 差错控制编码西西 北北 工工 业业 大大 学学（2012.5）第9章 差错控制编码通信原理2023-2-72干扰干扰乘性：均衡乘性：均衡加性：调制解调体制、发送功率、最佳接收加性：调制解调体制、发送功率、最佳接收9.1 9.1 引言引言一、编码问题的提出一、编码问题的提出 由于数字信号在传输过程中必不可免的受到由于数字信号在传输过程中必不可免的受到干扰干扰的影响，使的影响，使码元波形变坏，故传输到接收端后可能码元波形变坏，故传输到接收端后可能发生错判发生错判。信道信道译码译码检检/纠错编码纠错编

2、码若还不行，则需差错控制编码。若还不行，则需差错控制编码。目的：目的：在数字通信系统中，为了提高数字通信的可靠性而采在数字通信系统中，为了提高数字通信的可靠性而采取的编码称为取的编码称为信道编码信道编码。差错可控差错可控之前：之前：为了提高数字信号传输的有效性而采取的编码称为为了提高数字信号传输的有效性而采取的编码称为信信源编码源编码。如：如：PCM二、方法二、方法/模型模型第9章 差错控制编码通信原理2023-2-73研究问题：研究问题：9.1 引言 9.2 差错控制编码的基本概念 9.3 常用的简单检错码 9.4 线性分组码 9.5 循环码 9.6 检测和纠正突发错误的分组码交织码 9.7

3、 卷积码 9.8 网格编码调制(TCM)第9章 差错控制编码通信原理2023-2-741.随机性差错：差错是随机的且相互之间独立单个错。通常由高斯白噪声引起。2.突发性差错：错误之间有相关性-成串错。由脉冲性干扰引起，在短暂的时间内出现连续的差错，而这些短暂时间之后却又存在较长的无误码区间。9.2.1 差错类型 9.2 纠错编码的基本概念3.混合性差错：既存在随机差错又有突发性差错。以上两种错误性质不同，可分别处理。第9章 差错控制编码通信原理2023-2-75可以用来检测一位错误 可纠正一位错误或检测两位错误AB 许用码组 禁用码组 00 01 11 10 采用2位二进制码许用码组 禁用码组

4、 000 001 010 100 111 101 110 011采用3位二进制码采用1位二进制码019.2.2 差错控制的基本方法 在信息序列之后附加一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联，接收端按照既定的规则检验出关联关系，如这种规则受到破坏，将会发现错误，乃至纠正错误。例：第9章 差错控制编码通信原理2023-2-76检错与纠错能力与最小码距 d0 的关系(c)为了同时检测e个错误，纠正t个错误d0 et1，et(b)为了纠正t个错误 d0 2t1(a)为了检测e个错误，d0 e1码距：两个码组对应位上不同的数目。码重：码组中“1”的数目。结论：最小码距决定检错

5、和纠错能力。第9章 差错控制编码通信原理2023-2-779.2.3 差错控制方式2.前向纠错（FEC）可纠错的码 发 收3.混和纠错（HEC）可以发现和纠正错误 发 收 应答信号 比较：译码复杂性、实时性和占用传输链路(单向还是双向)。1.检错重发（ARQ）可检错的码 发 收 应答信号ARQ：自动重复请求发送接收端所识别到的错误超过了自身的纠错能力时，就请求发送端重发。第9章 差错控制编码通信原理2023-2-789.2.4 差错控制编码的效用 假设在随机信道中发“0”和发“1”的概率相同，在码长为n的码组中恰好发生 r 个错误的概率为：(p为误码率)rrnrrnnprnrnppCrP)!(

6、!)1()(371077)1(pP527101.221)2(pP837105.335)3(pP310p当码长 n7 ，误码率 时，则有：结论：采用差错控制编码，即使仅能纠正（或检测）12个错误，就能使误码率下降几个数量级。（9.2-4）第9章 差错控制编码通信原理2023-2-799.2.5 纠错码的分类1.分组码与卷积码分组码：将信息码分组，为每组信息码后面附加若干位监督码元，且 监督码元仅监督本码组中的信息位。卷积码：将信息序列分组，后面附加监督位，但监督位不但与本码组的信息位有关，还与前面码组的信息位有关，或者说监督位不仅监督本码组的信息位还监督其它码组的信息位。2.系统码与非系统码系统

7、码：就是信息位在前，监督位在后的码字。非系统码:信息位与监督位之间无特定的位置关系。编码效率：k/n（n，k）码）码 第9章 差错控制编码通信原理2023-2-710 9.3 常用的简单纠错码9.3.1 奇偶校验12100,1,nnSaaaa正确错误1,!,knRnnnk高码长信元数构成：n-1位信息位、1位监督位。n位编码构成以下约束关系接收端计算校正子（偶监督）检错能力：所有奇数个错误。一半！应用非常广泛。编码效率：1231010nnnaaaaa 督元信元奇数监督码偶数监督码第9章 差错控制编码通信原理2023-2-7119.3.2 纵向奇偶校验（LRC）用于检测突发错误11100111

8、11011101 00111001 1010100111100111110111010011100110101001纵向排列原始数据11100111 11011101 00111001 10101001 10101010突发错误接收方检验是否满足LRCLRC 10101010监督码元交织编码：针对突发性错误n位的LRC可以检测一个n位突发错误。第9章 差错控制编码通信原理2023-2-712 信 息 码 元 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1

9、1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 监督码元 0 0 1 1 1 0 0 0 0 1 0监督码元 1 0 0 1 0 1 19.3.3 水平垂直奇偶校验（二维）它能发现某一行或某一列上所有奇数个错误以及长度不大于行数（或列数）的突发错误。可检某些偶数个错误。具有一定的纠错能力。第9章 差错控制编码通信原理2023-2-7139.3.4 群计数码111001 100信息位监督位功能：发现所有奇数个错误，以及一些偶数个错误，除“0”变“1”，和“1”变“0”成对出现。规则：信息码元分组后计算“1”的个数，然后将这个数目的二进制码元表示作为监督

10、码元附加在信息码元之后。第9章 差错控制编码通信原理2023-2-7149.3.5 等重码（恒比码）功能：检测所有奇数个错误，以及一些偶数个错误，除“0”变“1”，和“1”变“0”成对出现。数字 电 码 数字 电 码 0 0 1 1 0 1 5 0 0 1 1 1 1 0 1 0 1 1 6 1 0 1 0 1 2 1 1 0 0 1 7 1 1 1 0 0 3 1 0 1 1 0 8 0 1 1 1 0 4 1 1 0 1 0 9 1 0 0 1 1表9-3 电传五中取三码许用码组:禁用码组:325log0.66CRn 编码效率：等重码是从特定码长的码组中，选取固定个数的“1”作为码组的许用

11、码组，这种码de码重相同，或“1”与“0”之比保持恒定。例：我国电传汉字电码，每个汉字用4位阿拉伯数字表示，每个阿拉伯数字又用5位二进制符号表示，其中3个“1”，码重为3。第9章 差错控制编码通信原理2023-2-7159.4 线性分组码定义：信息位和监督位之间的关系由线性方程组约束的分组码称作线性分组码。特征：督元由信元的线性组合而产生。奇偶校验码就是一种效率很高的线性分组码。这里S称为校正子：若S0，表示无错，S1表示有错。因仅用了1位监督位a0，所计算的1个校正子只能表示有错与无错。若监督位增加到2位，就可增加一个监督方程式，便可获得2个校正子S1、S2，于是：1231001nnnaaa

12、aaS 校正子督元信元无错有错22-1=312S S0 0 无错0 11 0 可指示一个错码可能出现的个位置1 1第9章 差错控制编码通信原理2023-2-716推广：显然：显然：要求要求 2r-1n（n=k+r），则可指示（仅一位错时），则可指示（仅一位错时）任一错码的位置包括信元、督元。任一错码的位置包括信元、督元。或：或：2rk+r+1112rSrrrSSS 对应对应对应对应一个督元一个监督方程一个校正子:个督元个监督方程个校正子:、122-1rrSSS 0 0 0 无错0 0 1 可指示个出错的可能位置1 1 1对于二进制编码，知道了错误的位置，就可以实现纠错了。第9章 差错控制编码通

13、信原理2023-2-717 一般说来对于(n，k)码。要想指出一位错码的所有可能位置，则要求：10212ttririnniiCC或或对于纠正t 个错误，需满足：121rnCnkr（纠正1个错误）第9章 差错控制编码通信原理2023-2-7189.4.1 线性分组码的构成121rnCnkr例：构造k4的汉明码（能纠一位错的线性分组码）。（1）确定 r 由得 r3，取r3，则n7。（7,4）码！6543210Aa a a aa a a 信元督元（2）写出校正子的编码表第9章 差错控制编码通信原理2023-2-719表9-4 校正子表 S1S2S3 误码位置 S1S2S3 误码位置 0 0 1 a0

14、 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 无错因此接收端计算下面3个校验关系，可确定误码的位置:034631356224561aaaasaaaasaaaas校正子表不是唯一的!这里的“+”代表模2和（2）写出校正子的编码表-r=3 共有3个校正子第9章 差错控制编码通信原理2023-2-720发送端构成偶校验方程可得督-信方程（线性组合）000034613562456aaaaaaaaaaaa 346035614562aaaaaaaaaaaa表9-5 16个许用码组！信息位 监督位 信息位 监督位 0 0 0 0 0

15、 0 0 1 0 0 0 111 0 0 0 1 0 1 1 1 0 0 1 100 0 0 1 0 1 0 1 1 0 1 0 010 0 0 1 1 1 1 0 1 0 1 1 001 0 1 0 0 1 1 0 1 1 0 0 001 0 1 0 1 1 0 1 1 1 0 1 010 0 1 1 0 0 1 1 1 1 1 0 100 0 1 1 1 0 0 0 1 1 1 1 1113456aaaa012aaa3456aaaa012aaa（3）生成全部许用码组第9章 差错控制编码通信原理2023-2-721654321065432106543210111010001101010010

16、110010aaaaaaaaaaaaaaaaaaaaa 65432101 11010001 10101001 0110010Taaaaaaa 线性分组码的监督矩阵和生成矩阵监督矩阵从校验方程入手0TTHA 记为 000034613562456aaaaaaaaaaaa0TAH或有第9章 差错控制编码通信原理2023-2-7226543210Aaaaaaaa000 111010011010101011001H其中：-监督矩阵-码组的行矩阵-零矩阵 可见：H一旦确定，督元和信元之间的关系也就确定了。若:1rrkrrHP-则称H为典型阵。由线性代数理论：典型阵各行一定是线性无关的；非典型阵可通过矩阵的

17、初等变换化为典型阵。0TTHA 0TAH第9章 差错控制编码通信原理2023-2-7232.2.生成矩阵生成矩阵265416530643aaaaaaaaaaaa督信关系矩阵形式:经由生成矩阵生由信元生成：成线性码组6251403111011011011aaaaPaaa 从督信方程入手由111010011010101011001H第9章 差错控制编码通信原理2023-2-724写成行阵形式:21065436543111110101011a a aa a a aa a a aQQ 其中其中 Q=PT。上式表明：上式表明：信息位给定后，就产生了监督位！信息位给定后，就产生了监督位！进一步，令进一步，

18、令生成矩阵 G=Ik Q 则，码组行阵则，码组行阵 A=a6a5a4a3 G 6251403111011011011aaaaPaaa Q能生成督元能生成督元G才生成线性分组码才生成线性分组码如何装配：信元督元？如何装配：信元督元？第9章 差错控制编码通信原理2023-2-725例：例：生成矩阵生成矩阵讨论：讨论：由信息位与生成矩阵由信息位与生成矩阵G相乘可得到全部码字相乘可得到全部码字A。具有具有 Ik Q 形式的生成矩阵称为形式的生成矩阵称为典型生成阵。由典型生成矩阵得出的码组为由典型生成矩阵得出的码组为系统码。1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10

19、 0 0 1 0 1 1kGI Q6543654365436546536431 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1Aa a a a Ga a a aaaaaaaaaaaaaa 信息位不变督位附后，码组行阵：码组行阵：督元由相应的信息位决定！督元由相应的信息位决定！6543AaaaaG第9章 差错控制编码通信原理2023-2-726一般形式:A=an-1an-2ar G 3.G 和和 H 的关系的关系由由 Q=PT 或或 P=QT 则则:H=P Ir G=Ik Q 综上：综上：线性分组码的编码，就是根据其监督阵线性分组码的编码，就

20、是根据其监督阵H或生成阵或生成阵G将将长为长为k的信息码编成长为的信息码编成长为n的码组。的码组。第9章 差错控制编码通信原理2023-2-7274.4.线性分组码的性质线性分组码的性质（1 1）封闭性）封闭性 设：设：A1、A2 分别为一线性分组码的任意两个许用码组。分别为一线性分组码的任意两个许用码组。则：则：A1+A2 仍为该线性分组码的许用码组。仍为该线性分组码的许用码组。证：证：由假设知由假设知A1HT=0、A2HT=0 所以所以A1HT+A2HT=（A1+A2）HT0 即即A1+A2也是一个码组。也是一个码组。结论：结论：线性码组中任意两个码字之和，仍为该线性码组之码字。线性码组中

21、任意两个码字之和，仍为该线性码组之码字。（2 2）线性分组码的线性分组码的最小距离等于非零码的最小重量最小距离等于非零码的最小重量。即即:d0=Wmin（除全（除全0码组）码组）证：证：由封闭性得，两个码组之间的距离（之差），必是另一码由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！组的重量。故最小码距即是码的最小重量！第9章 差错控制编码通信原理2023-2-7289.4.3 线性分组码的伴随式译码设：发送码组为A，接收码组为R。则：R-AE（模2）为错误行阵或错误图样。120,.,nnEeee对于前面（7，4）码的例子，一位错误图样为：(100000

22、0),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)0,1,iiiiibaeba，说明无错，说明有错计算校正子或伴随式：()TTTTTTHRH AEHAHESHE(0)TTRHS AH结论：结论：校正子校正子S仅与错误图案有关，与发送码组无关。仅与错误图案有关，与发送码组无关。第9章 差错控制编码通信原理2023-2-729伴随式与纠错：结论：校正子校正子S只与只与E有关，若接收码字有关，若接收码字R中第中第i 位有错，那么导位有错，那么导出的伴随式恰好同于监督矩阵出的伴随式恰好同于监督矩阵H的第的第i 列。列。例：对于前

23、面（对于前面（7，4）码例子，一位错误图样为：）码例子，一位错误图样为：(1000000),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)，分别计算当错误图样为上面七种形式之一时的伴随式值。，分别计算当错误图样为上面七种形式之一时的伴随式值。666101 101000101010011111101 1001000TTSHEH 555011101000101010011110011 1001000TTSHEH 第9章 差错控制编码通信原理2023-2-730222001 1 10100011 10101000101 1001

24、1000TTSHEH 111001 1 10100001 10101001101 10010010TTSHEH 000001 1 10100001 10101000101 10010101TTSHEH 444001 1 10100111 10101000101 10010100TTSHEH 333001 1 10100001 10101011101 10010100TTSHEH 结论：利用伴随式不仅可以判决接收码字中是否有错，而且可以指出差错的位置。第9章 差错控制编码通信原理2023-2-731例：若接收的码组为若接收的码组为1001101，请指出错误位置并译码。，请指出错误位置并译码。解：

25、计算伴随式计算伴随式 632001011101000011010100110110011101TTTSHEHRHHHHH 最后一位有错，译码得最后一位有错，译码得：1001100。第9章 差错控制编码通信原理2023-2-7329.5.1 循环码的概念 定义：是一种具有循环移位特性的线性分组码。特点：编译码设备简单；检纠错能力强。9.5 循环码 构成原理：具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。第9章 差错控制编码通信原理2023-2-7331.码多项式码多项式 定义：定义：为了利用代数理论研究循环码，可以将码组用代数多项是为

26、了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。来表示，这个多项式被称为码多项式。设：设：许用循环码许用循环码 A=(an-1 an-2 a1 a0)则：则：它的码多项式表示为：它的码多项式表示为：121210()nnnnA xaxaxa xa其中：其中：xi 仅是码元位置的标记。仅是码元位置的标记。码字与码多项式一一对应！第9章 差错控制编码通信原理2023-2-734表9-6 (7，3)循环码反之，由码多项式易得出码组。反之，由码多项式易得出码组。第9章 差错控制编码通信原理2023-2-7352.2.码多项式的按模运算码多项式的按模运算1）整数的按模运算

27、）整数的按模运算若一个整数若一个整数m可以表示为可以表示为:5122251(2)模,mpQpnQnn是整数则在模则在模n运算下，有运算下，有mp（模（模n）。）。例：例：同样对于多项式而言，也有类似按模运算。同样对于多项式而言，也有类似按模运算。第9章 差错控制编码通信原理2023-2-736 A xR xQ xNxNxA xR x其中：商商Q(x)为多项式，余数为多项式，余数R(x)的幂次低于的幂次低于N(x)的幂次。的幂次。例:求求 x4+x2+1 按模按模 x3+1 运算的余式运算的余式 R(x)2 2）码多项式的按模运算）码多项式的按模运算若若则则4223342231111111xxx

28、xxxxxxxxx+（模）第9章 差错控制编码通信原理2023-2-737 3 3）循环性）循环性可以证明：在循环码中，若在循环码中，若A(x)是一个长为是一个长为n的许用码组，的许用码组，则则xiA(x)在按模在按模xn+1运算下运算下，亦是亦是许用码组。即若有许用码组。即若有()()1)inx A xA xx(模则则也是一个许用码组。也是一个许用码组。7653765365377653()111()11101001xA xxxxxxxxxxxxxxxA xxxx 1（）前述（前述（7，3）码：）码：A(x)=x6+x5+x4+x2 （1110100）前码组循环左移前码组循环左移1位！位！11

29、11356735677 xxxxxxxxx多项式除法：余式第9章 差错控制编码通信原理2023-2-7389.5.2 循环码的生成多项式循环码的生成多项式g(x)（1 1）存在性）存在性 (n，k)循环码中循环码中有且仅有有且仅有一个一个g(x)，为，为 g(x)=xn-k+1特点特点:最高的次数为最高的次数为n-k=r；常数项常数项系数必为系数必为1 。11-110-1000 11nrrrkrrkaaaaa a 个在循环码中，除了全在循环码中，除了全0码组外，码组外，再也没有连续再也没有连续k位均为位均为0的码的码组。即连组。即连0长度最多为长度最多为k-1位！位！这唯一的这唯一的n-k次多

30、项式称为次多项式称为生成多项式生成多项式，记为，记为g(x)！第9章 差错控制编码通信原理2023-2-739（2）生成多项式）生成多项式 g(x)与生成矩阵与生成矩阵 G(x)的关系的关系12()()()()()kkxg xxg xG xxg xg xA=an-1ar GG=Ik Q 生成矩阵生成矩阵G的每一行都是一的每一行都是一个码组；个码组；G是是k行行n列矩阵。列矩阵。只要找到只要找到k个已知码组，就个已知码组，就能构成生成矩阵能构成生成矩阵G！生成多项式确定后，则生成多项式确定后，则g(x)、x g(x)、xk-1 g(x)都是码组，都是码组，且这且这k个码组信息无关，因此可以用来构

31、成生成矩阵。个码组信息无关，因此可以用来构成生成矩阵。g(x)确定了确定了G(x)也就确定了也就确定了整个码组即确定！整个码组即确定！第9章 差错控制编码通信原理2023-2-740例例:(7，3)循环码，循环码，g(x)=x4+x2+x+1 求典型生成矩阵求典型生成矩阵解解:6643225532420()1011100()010 1110()001 01111xxxxxx g xxGxg xxxxxg xxxxx(x)100 1011010 1110001 0111kGI Q可方便地直接写成码组形式可方便地直接写成码组形式典型阵典型阵:第9章 差错控制编码通信原理2023-2-741（3）生

32、成多项式生成多项式g(x)与码多项式与码多项式A(x)的关系的关系（7，3）26546542654()()()()()()()()x g xA xa a a G xa a axg xg xa xa xag xh x g x12()()()()()kkxg xxg xG xxg xg x表明：表明：所有所有A(x)都可以被都可以被g(x)整除，而且任一次数不大于整除，而且任一次数不大于(k-1)的的多项式乘以多项式乘以g(x)都是码多项式。都是码多项式。A(x)模模g(x)=0。h(x)为不大于为不大于(k-1)的多项式！的多项式！第9章 差错控制编码通信原理2023-2-742结论结论:g(x

33、)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。证明：证明：任一循环多项式任一循环多项式A(x)都是都是g(x)的倍式，即的倍式，即()()()A xh x g x()()A xg x()()ix A xA x而生成而生成多项式多项式g(x)本身也是一个码组，即有本身也是一个码组，即有由于码组由于码组A(x)为一为一（n-k）次次多项式，故多项式，故xkA(x)为一为一n次多项次多项式。由式。由知，知，xkA(x)在模在模（xn+1）的运算下，亦的运算下，亦为一码组，故可写成为一码组，故可写成 11knnx A xA xQ xxx（4）如何寻找如何寻找g

34、(x)第9章 差错控制编码通信原理2023-2-743上式左端分子和分母都是上式左端分子和分母都是n次多项式，故商次多项式，故商Q(x)1，因此上，因此上式可化成即式可化成即()(1)()knx A xxA x1()()nkxg x xh x 将将A(x)=h(x)g(x)、A(x)=g(x)代入，并整理，得代入，并整理，得()()()11knnx A xA xQ xxx表明表明:g(x)应该是应该是xn+1的一个因式！的一个因式！证得证得:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。第9章 差错控制编码通信原理2023-2-744例：例：如如

35、(x7+1)=(x+1)(x3+x2+1)(x3+x+1)则有则有g(x)：（7，4）：）：x3+x2+1、x3+x+1 （7，3）：）：(x+1)(x3+x2+1)、(x+1)(x3+x+1)（7，6）：）：x+1第9章 差错控制编码通信原理2023-2-745例例:（7，3）循环码有多项式如下，找出（循环码有多项式如下，找出（7，3）码的生成）码的生成多项式多项式g(x)。（1）x4+x3+x（2）x3+x2+1 （3）x+1 （4）x4+x2+x+1 （5）x4+x+1解解:依据依据 r=7-3=4，常数项不为零，有，常数项不为零，有 （4）x4+x2+x+1 （5）x4+x+1还须证其

36、是不是还须证其是不是xn+1=x7+1的因子的因子?x7+1=(x4+x2+x+1)(x3+x+1)+0 x7+1=(x4+x+1)(x3+1)+(x2+x)故故:仅有仅有 x4+x2+x+1 为生成多项式为生成多项式 g(x)第9章 差错控制编码通信原理2023-2-746表表9-7 (7,k)循环码循环码结论：循环码完全由其码组长度n及生成多项式 g(x)决定。表中：h(x)称为监督多项式。第9章 差错控制编码通信原理2023-2-747123 xxxg)(例9.5.1 一个一个(7，4)循环码的生成多项式为循环码的生成多项式为确定该循环码的典型化的生成矩阵和监督矩阵。确定该循环码的典型化

37、的生成矩阵和监督矩阵。解：解：由由g(x)构成的生成矩阵为构成的生成矩阵为6536534254234323211010001101000()01101000110100()()=00110100011010()00011010001101()11xxx g xxxxxx g xxxxG xGxxg xxxxxg xxxx，典型生成矩阵01000110010001100101110001101G01 0 1 1 1 0 01 1 1 0 0 1 00 1 1 1 0 0 1H典型监督矩阵：第9章 差错控制编码通信原理2023-2-7489.5.3 系统循环码的编码实现系统码组中的最左边的k位是信

38、息码元，随后是n-k位的监督码元，即码多项式为：111010()()()nn kkn knkn kA xm xmxm xrxr xxr ()()+()()()()n kn kr xm x xA xm x xr xg x ,（,（模模）因此()()=()()()nkxm xr xq xg xg x有：结论（编码步骤）：结论（编码步骤）：m(x)xn-k/g(x)除法求余得到r(x)；m(x)xn-k+r(x)求得A(x)。m(x)信息多项式信息多项式 r(x)监督多项式监督多项式第9章 差错控制编码通信原理2023-2-749例9.5.2 已知(7，4)循环码的生成多项式为若信息码为1001，求

39、编码码字。123 xxxg)(3363()()()(1)11n kA xxm xr xxxxxxx 因此：3()1m xx解：33323232()(1)11()11n kxm xxxxxxxg xxxxx 即：编码码组为：1001011或：直接由信息码元1001+监督码元011拼接而成！1()10 1r xx 监督码元第9章 差错控制编码通信原理2023-2-750上述编码过程，在硬件实现时，可以利用除法电路（曹志刚上述编码过程，在硬件实现时，可以利用除法电路（曹志刚p344348）来实现。）来实现。编码的电路编码的电路10mg，有反馈，无32323210()11g xxxgxgxgxg 第9

40、章 差错控制编码通信原理2023-2-751工作过程：工作过程：信息输入时，开关合信息输入时，开关合2：输入码一方面输入除法器，另一方面输入码一方面输入除法器，另一方面直接输出，在信息位全部进入除法器后直接输出，在信息位全部进入除法器后开关合开关合1：输出端接到移位寄存器，将移位寄存器中存储的余输出端接到移位寄存器，将移位寄存器中存储的余项依次输出，同时切断反馈线。项依次输出，同时切断反馈线。系统码！系统码！第9章 差错控制编码通信原理2023-2-752循环码的译码可以分三步进行：循环码的译码可以分三步进行：（1）由接收到的码多项式）由接收到的码多项式R(x)计算校正子（伴随式）多项式计算校

41、正子（伴随式）多项式S(x)；（2）由校正子）由校正子S(x)确定错误图样确定错误图样E(x)；（3）将错误图样）将错误图样E(x)与与B(x)相加，纠正错误。相加，纠正错误。9.5.4 循环码的译码第9章 差错控制编码通信原理2023-2-7539.6交织码，交织码，9.7卷积码，卷积码，9.8TCM 为选讲内容为选讲内容可根据课时情况选择讲授可根据课时情况选择讲授第9章 差错控制编码通信原理2023-2-754 前面介绍的线性分组码和循环码都是用来纠正随机错误的，交织码是一种纠正和检测突发错误的分组码。在纵向奇偶校验码中，按列进行检验，就可以检测出每一行上不超过列数的突发性错误，这种方法同

42、样可以用于纠正突发性错误，由此构造的纠错码称为交织码。*9.6 纠正和检测突发错误的分组码纠正和检测突发错误的分组码-交织码交织码第9章 差错控制编码通信原理2023-2-755（1）若将能纠正t个随机错误的码作为方阵的行码，m个行码组构成一个方阵，这种交织码保证可以纠正t个突发长度为m的突发错误。（2）但若将能纠正b个突发错误的码作为行码，则m个行码组构成的方阵，可以保证纠正长度为bm个突发错误。m行、行、n列列交织度交织度m第9章 差错控制编码通信原理2023-2-756 mnmnmn5621141516789123 编码器输出时，按列的顺序自左至右读出，这时的序列为:在接收端，将上述过程

43、逆向重复，即把收到的序列按列写入存储器再按行读出，这时就仍然恢复成原来的(n,k)分组码 交织码实际上是一种时间扩散技术，当交织度足够大时，就把突发错误离散成随机错误，从而被分组码所纠正,但是m受到传输时延的限制。第9章 差错控制编码通信原理2023-2-757 因而(m n,m k)也是循环码，(n,k)码中每一个码组在(m n,m k)码中对应有一个码组，它们有相同的码重只是各码元相隔 m位。()()mmgxg x)(mxg11 mnnmxx)(采用循环码构造交织码时，不必用nm阵列就能实现编码，假设交织码每行为(n,k)循环码，其生成多项式为g(x)，则g(x)必定能除尽xn+1。交织度

44、为m的交织码(m n,m k)，其生成多项式为 ，它的物理意义是在g(x)的各项之间插入(m-1)个0，显然 能除尽 。第9章 差错控制编码通信原理2023-2-758 32()1g xxx 16903233333 xxxxxxgxg)()()()()(例：用生成多项式为例：用生成多项式为 的的（7，4）线性分线性分组码，构成交织度为组码，构成交织度为3的的（21，12）交织码，求交织码的生成交织码，求交织码的生成多项式及监督矩阵多项式及监督矩阵。输入输入(7,4)码编码器码编码器输入输入(21，12)码编码器码编码器 交织码译码时，必须将码元排列成交织码译码时，必须将码元排列成 nm 阵列，

45、然后分别阵列，然后分别独立的对其进行译码。独立的对其进行译码。第9章 差错控制编码通信原理2023-2-759*9.7 卷积码卷积码(n，k，N)卷积码通常用卷积码通常用（n,k,N)来表示，它是把来表示，它是把k个信息比特编成个信息比特编成n个编码个编码比特，其中比特，其中N定义为编码定义为编码约束长度约束长度，说明编码过程中互相约束的码，说明编码过程中互相约束的码段个数。段个数。卷积码的编码器具有记忆性卷积码的编码器具有记忆性，任意时刻输出的，任意时刻输出的n个比特，不仅与个比特，不仅与当前输入的当前输入的k比特有关系，还与前比特有关系，还与前N-1个个k比特输入有关。因此，比特输入有关。

46、因此，编码编码过程中相互关联的码元就有过程中相互关联的码元就有nN个个。定义定义c=k/n为卷积码的为卷积码的编码效率编码效率，c和和N是衡量卷积码性能的两个是衡量卷积码性能的两个重要参数。重要参数。由于卷积码的编码过程充分利用了各码组的相关性，且由于卷积码的编码过程充分利用了各码组的相关性，且n和和k也较也较小，因此，在与分组码相同的编码效率下，卷积码的性能更优。在小，因此，在与分组码相同的编码效率下，卷积码的性能更优。在相似的纠错能力下，卷积码的实现通常比分组码更加简单。相似的纠错能力下，卷积码的实现通常比分组码更加简单。第9章 差错控制编码通信原理2023-2-760图9-15 卷积编码

47、器的一般形式9.7.1 卷积码的基本原理卷积码的基本原理 注：模2加法器输入端的数目不一定相同。第9章 差错控制编码通信原理2023-2-761图9-16 (3,1,3)卷积码编码器(3,1,3)卷积编码器的输入与输出逻辑关系为：122312iiiiiiiiiymymmymmm (9.7-1)例：例：以一个简单的以一个简单的(3,1,3)卷积码为例来简述卷积码的编码过程，卷积码为例来简述卷积码的编码过程，此时最高的编码效率为此时最高的编码效率为c=1/3。第9章 差错控制编码通信原理2023-2-762图图9-17 (3,1,3)卷积码树状图卷积码树状图 (每输入每输入0或或1时输出状态时输出

48、状态)9.7.2 卷积码的图解表示卷积码的图解表示第9章 差错控制编码通信原理2023-2-763图图9-21 闭合型状态图闭合型状态图 a,b,c,d 为移位寄存器状态为移位寄存器状态图图9-19 (3,1,3)卷积码网格图卷积码网格图 输入码：输入码：1 0 1 0 1状态：状态：10 01 10 01 10输出码：输出码：111 001 100 001 100 第9章 差错控制编码通信原理2023-2-7649.7.3 卷积码的解析表示卷积码的解析表示 生成多项式生成多项式12223()=1()=1+()=1+GxGxxGxx x (9.7-2)当输入为当输入为10101时，时，M(x)

49、=1+x2+x4则（则（3,1,3）编码器输出）编码器输出Y分别为：分别为：Y1(x)=G1(x)M(x)=1(1+x2+x4)=1+x2+x4Y2(x)=G2(x)M(x)=(1+x2)(1+x2+x4)=1+x6Y3(x)=G3(x)M(x)=(1+x+x2)(1+x2+x4)=1+x+x3+x5+x6相应的输出序列为：相应的输出序列为：Y1(x)=(y11y12y13y14)=(10101)Y2(x)=(y21y22 y 23y24)=(1000001)Y3(x)=(y31y32y33y34)=(1101011)编码器输出的序列为：编码器输出的序列为：Y=(y11 y21 y31y12

50、y22 y32y13 y23 y33y14y24 y34)=(111 001 100 001 100)第9章 差错控制编码通信原理2023-2-765卷积码的距离特性：卷积码的距离特性：最小码距：最小码距：卷积码中长度为卷积码中长度为nN(N为约束长度为约束长度)的编码后序列的编码后序列 之间的最小汉明距离。之间的最小汉明距离。)(minmind最小自由距最小自由距：卷积码中任意长：卷积码中任意长编码后序列之间的最小汉明距离。编码后序列之间的最小汉明距离。)(freed采用哪种距离作为纠错能力的度量与译码算法有关：采用哪种距离作为纠错能力的度量与译码算法有关：1.当译码算法仅限于处理长度为当译