第六章信道编码

第六章信道编码2024/3/231第1页，课件共107页，创作于2023年2月一、信道编码－线路码与纠错码信道编码是以信息在信道上的正确传输为目标的编码，它可分为两个层次上的问题：一是如何正确接收载有信息的信号，二是如何避免少量差错信号对信息内容的影响；前者是《通信原理》的问题，后者是《信息论》的问题。比如在数字基带信号中的编码，主要目的是为了消除直流分量、改造信号频谱、便于时钟频率的提取、实现数字信号的透明传输等。还有的是为了压缩占用带宽、抑制码间干扰，如部分响应系统。这个层次上的编码，如曼彻斯特码、AMI码、HDB3码、nBmB码、部分响应系统中的相关编码等，一般称之为线路编码（linecode）。第2页，课件共107页，创作于2023年2月从信息论角度来看的信道编码是指第二层次的编码，即差错控制编码，包括各种形式的纠错、检错码，统称为纠错编码。纠错编码的理论体系属于信息理论，但纠错编码的实现离不开有形载体的信号理论，因此信息的编码与信号的编码有天然联系。纠错码在有形化信号阶段的差错概率是符号(symbol)差错概率（误码元率），而在承载信息方面的差错概率是比特差错概率(误比特率)。本书讨论的信道编码主要指纠错编码，而衡量纠错编码性能的指标主要是误比特率的改善程度。第3页，课件共107页，创作于2023年2月举例说明：A、B两消息，可用一位二进制数表示，A=1、B=0出错时无法判定。

增加一个监督位，取11→A、00→B,若收到01或10时，

可知发生了错误，但不能纠正错误。

再增加一个监督位，取111→A、000→B,若一位错：B→001A→110，这样纠码：001→000→B,110→111→A若两位错011,110则只能发现不能纠错

因此，这种（3，1）码，能纠正一个错，发现两个错。

可以看出：本来只需要2位二进制数就可以表示A、B两个符号，用2或3位表示时，码长变长，带来信息冗余。所以，纠错能力是靠冗余换取的。二、检错和纠错（差错控制）的基本原理：第4页，课件共107页，创作于2023年2月第一、二节有扰离散信道的编码定理一、差错控制（1）前向纠错法FEC

所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备复杂，传输效率↓

。信源FEC编码信道FEC译码信宿（2）反馈重发ARQ(AutomaticRepeatRequest能检错的码应答信号发端收端第5页，课件共107页，创作于2023年2月方法和设备简单，无需纠检错编译系统。但需要双向信道，传输效率↓、实时性差

。（3）混合纠错法HEC

能纠错（能力有限）的码应答信号发端收端性能介于前面二者之间第6页，课件共107页，创作于2023年2月（1）根据各码组信息码和监督码的关系分：

线性码，非线性码根据监督码元是否仅与本组信息元有关

分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：

系统码，非系统码（3）根据码的用途分：

检错码，纠错码（4）根据码元的取值：

二进制码，多进制码（5）根据构造编码的数学方法：

代数码，几何码，算术码（6）二、纠错码的分类第7页，课件共107页，创作于2023年2月对于给定的有扰信道，若信道容量为C，只要发送端以低于C的信息速率Rb发送信息，则一定存在一种编码方法，使得译码错误概率P随着码长n的增加，按指数下降至任意小的值，表示为

P

e-nE(Rb)E(Rb)为误差指数，Rb<C时，E(Rb)>0。两个结论：1.码长n和信息速率Rb一定时，随CE(Rb)P↓随指数下降。其中C=Blog2(1+S/N)（bit/s）2.在C和Rb一定时(Rb<C)，随nP随指数下降(P0)。三、有扰信道编码定理（Shannon第二定理第8页，课件共107页，创作于2023年2月一、分组码

将信息码首先分成若干组，分别代表不同的含义，然后为每个码组附加若干位监督码元，这种编码方式称之为分组码在分组码中，监督码仅监督本码组中的信息码元。与分组码相对应，存在非分组码，如卷积码。在非分组码中，监督码元除了与本组信息元有关，还与其它组的信息码元有关。由于卷积码充分利用了各码组间的相关性，其性能要优于分组码。第三节线性分组编码

分组码一般用符合（n,k）表示，其中k表示每组码二进制信息码元的数目，n是码组的总位数或码组长度，则n-k=r为每组码中的监督码元的数目，因此分组码的结构通常可表示为：第9页，课件共107页，创作于2023年2月二、码组重量和距离为了分析各种码的检错纠错能力，引入码组重量和距离的概念。码组中包含1的个数称为码组的权，也称码组的汉明重量，用W表示。码长n=k+rk个信息位r个监督位两个不同的码组，其对应码位码元不同的个数，称为汉明距离，用d表示。例：C1＝{11001100}和C2={10010111}重量分别为W1＝4，W2＝5；它们的距离为d(c1,c2)=5。第10页，课件共107页，创作于2023年2月

在某种编码中，各码组间距离的最小值称为最小码距，用d0表示。最小码距的大小直接关系着这种编码的检错和纠错能力，它是衡量各种码抗干扰能力大小的标准。码组的最小距离越大，抗干扰能力越强，这个结论具有普遍性。最小距离与检错和纠错能力之间满足如下关系：设码组能检错个数为e，则有设码组能纠错个数为t，则有若码组能检错个数为e，又能纠错t个，则有

对任何纠错编码都适用。第11页，课件共107页，创作于2023年2月三、编码效率对于分组码（n,k），编码效率定义为信息位在码字中所占的比重，按下式计算：在信道中传送n个单位的时间内，传输信息位占k个单位的时间。因此，编码效率可看成是信道传送信息码元的利用率。

编码效率是衡量码性能的一个重要参量。但不难看出，编码效率与抗干扰能力这两个参数是相互矛盾的。编码的主要任务就是如何找到一种方法，在满足一定编码效率的前提下，使抗干扰能力尽可能大。第12页，课件共107页，创作于2023年2月四、线性分组码1、基本概念线性分组码的性质：含有全零码字。任意两个许用码字之和仍是一个许用码字。（封闭性）最小码距d0等于非零码字的最小重量即d0=wmin

（由此性质可以方便的确定出线性分组码的最小码距，进而明确其纠错能力。）可用线性方程组表述码的规律性建立在代数学群论基础上，各许用码的集合构成代数学中的群，又称为群码。在群中只有一种运算，就是模2和。第13页，课件共107页，创作于2023年2月如：码长为5的偶监督码2、最简单的线性分组码—奇偶检验码序码字序码字号信息码元监督元号信息码元监督元a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110

第14页，课件共107页，创作于2023年2月

偶监督码编码器a4a3a2a1+信息组a0a1a2a3a4码字第15页，课件共107页，创作于2023年2月偶监督码的检错电路b3b0b1b2b4+接收码组BS检错信号这里S称为校正子，上式也称伴随式。第16页，课件共107页，创作于2023年2月例：一数据序列：{11100

10111

01101

10001

10101}试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力解：（6，5）,将数据序列每5码元分组，并作：的运算可得出编码数据序列：{111001∣101110∣011011∣100010∣101011}只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。用以下方法改进。∣∣∣

∣第17页，课件共107页，创作于2023年2月水平垂直奇偶校验码：

又称行列监督码或二维奇偶监督码。特点：对水平方向和垂直方向的码元同时实施奇偶监督。110010100000100001101001111000011100111000001010101010111000111100行列监督码第18页，课件共107页，创作于2023年2月把接收码R与发送码C的差称为错误图样,用E表示：E=C-R（模M）如：八进制M=8，C=(0254752

),R=(0154754)则：E=(010006）

3、错误图样E=C⊕R→C=R⊕E,只要设法估计出差错图样，就可以由接收码估计出发送码。这就是译码的概念。M=2,二进制码，则为异或运算，可以写为E=C⊕R。E中的某一位值为1，表示接收码在该位出了错。第19页，课件共107页，创作于2023年2月4、矢量空间和码空间

长度为n的码字看作一个n维矢量，又叫码字矢量，所以可以从矢量空间的角度来分析和研究分组编码。①矢量空间的定义：第20页，课件共107页，创作于2023年2月②矢量（码字）的运算法则③线性相关和线性无关第21页，课件共107页，创作于2023年2月④矢量空间的基底⑤n维矢量空间是由n个基底张成的一维空间是一条直线。一个基底（不是唯一的）。如x=5是其一个基底。由x=5向两边延伸就张成了一条直线。第22页，课件共107页，创作于2023年2月二维空间是一个平面。两个基底（不是唯一的）。如（0,1)和(1,0)是其两个基底。这两个基底的所有线性组合构成了平面，或者说张成了二维空间三维空间有三个基底如（1,0,0),(0,1,0),(0,0,1)这三个基底的所有线性组合张成了三维空间自然基底：矢量中的元素包含一个1，其它为0的那组基底。如三维空间的基底（1,0,0),(0,1,0),(0,0,1)。在线性无关的前提下，任意缩放或旋转后仍为基底，如(0,0,2),(0,2,0),(0,0,2)第23页，课件共107页，创作于2023年2月⑥子空间第24页，课件共107页，创作于2023年2月总结:重数---构成矢量的元素的个数

维数---张成矢量空间的基底的个数⑦矢量空间的正交第25页，课件共107页，创作于2023年2月⑧分组码的码集（n,k)码信息长度为k,信息序列的个数为2k。码字长度为n，n维n重的矢量空间Vn中矢量的总数为2n。其中的2k个为码字，其余2n-2k个是禁用码组。若接收到了禁用码组说明在传输过程中出了差错。一般地，码集不一定是Vn的子空间。但对于线性分组码而言，码集则一定是它的一个子空间（线性分组码包含了所有的线性组合，构成一个子空间）。第26页，课件共107页，创作于2023年2月⑨分组编码的数学概念从2n组合中，选择2k个作为码字构成码集。或说，从n维n重的矢量空间Vn中选择一个k维n重的子空间作为码空间。确定k维k重的信息空间到k维n重的子空间的映射方法，就是编码。不同的k维n重的子空间构成不同的码。即使是同一个k维n重的子空间，映射的方法不同，也是不同的码。第27页，课件共107页，创作于2023年2月5、线性分组码的生成矩阵和校验矩阵

①生成矩阵第28页，课件共107页，创作于2023年2月用矩阵运算来表示上述组合运算，将k个基底排列成矩阵G:

码空间中的码字是由信息组和矩阵G相乘得到的，把G叫做线性分组码的生成矩阵

第29页，课件共107页，创作于2023年2月②系统形式的生成矩阵线性空间的底不是唯一的→码空间的生成矩阵G也不是唯一的。通过线性组合运算可以将G变换成如下形式：k*k单位矩阵P:k*(n-k)的矩阵形式第30页，课件共107页，创作于2023年2月

码字的前k位就是信息组的各信息位，而其余的n-k位就是冗余位（或监督位）。这种码叫系统码，相应的生成矩阵叫系统形式的生成矩阵。

将非系统形式的生成矩阵，通过线性组合运算变换成系统形式的生成矩阵，该过程叫做系统化。

显然，系统化只是改变映射关系，码空间不变。第31页，课件共107页，创作于2023年2月③校验矩阵（监督矩阵）对偶空间和对偶码K个n重的基底张成k维n重的码空间C即(n,k)码，一定存在n-k个正交矢量作为基底，构成其生成矩阵H，张成C的对偶空间D,即(n,n-k)码，称后者为前者的对偶码（互为对偶码）。对偶码(n,n-k)的生成矩阵H是(n,k)码的校验矩阵，这是因为，第32页，课件共107页，创作于2023年2月释：码空间C与D正交，C中的任一码子正交与D中的任一码字，而H是D的生成矩阵（D中n-k个基底）④如何求检验矩阵H?第33页，课件共107页，创作于2023年2月（1）计算码集C,列出信息组与码字的映射关系（2）系统化处理后，计算码集，列出映射关系（3）计算系统码的校验矩阵H。若收码为100110，检验是否是码字。（4）据系统码的生成矩阵，画出编码电原理图例6-2：(6,3)码的生成矩阵为：解：（1）求出每一个码字第34页，课件共107页，创作于2023年2月

信息组码字0000→0000001001→0111012010→1100013011→1011004100→

111010

5101→1001116110→

0010117111→010110第35页，课件共107页，创作于2023年2月（2）正交化处理

信息组码字0000→0000001001→0010112010→0101103011→0111014100→

100111

5101→1011006110→

1100017111→111010第36页，课件共107页，创作于2023年2月（3）校验矩阵（4）编码的电原理图（据输入与输出的关系）第37页，课件共107页，创作于2023年2月第38页，课件共107页，创作于2023年2月6、伴随式和标准阵列译码第39页，课件共107页，创作于2023年2月第40页，课件共107页，创作于2023年2月选择哪一个？

第41页，课件共107页，创作于2023年2月作业讲评1、3.33.6一定要画出信道模型，判断对称性。2、3.8Ps/N0=45.5或Ps/（N0/2）=45.5皆可3、3.10dB数换算成倍数4、4.1计算平均失真=ε。不是2ε5、5.1唯一可译码：C1C2?C3C6。C4?6、5.55.85.10。霍夫曼编码读码一定要仔细。

5.10:a4

101,a51000,a61001第42页，课件共107页，创作于2023年2月测验：

某(n,k)线性二元码的码集为C={C1=000000,C2=000111,C3=011001,C4=011110,C5=101011,C6=101100,C7=110010,C8=110101}求n,k为何值？构造此码的生成矩阵G.对G进行系统化，重新编码。第43页，课件共107页，创作于2023年2月2k=8,-->k=3.n=6G=[00111;011001;101011]Gs=[100011;010101;001111]第44页，课件共107页，创作于2023年2月复习矢量空间的基底、生成重数---构成矢量的元素的个数维数---张成矢量空间的基底的个数矢量空间的正交、对偶空间分组编码的数学概念第45页，课件共107页，创作于2023年2月生成矩阵：第46页，课件共107页，创作于2023年2月校验矩阵例6-2！！！！第47页，课件共107页，创作于2023年2月伴随式和标准阵列译码编、译码过程：选择重量最轻的那组差错图样进行译码

理解最小距离译码Goon第48页，课件共107页，创作于2023年2月最佳译码（最大后验概率译码）：在已知r的条件下找出可能性最大的发码c作为译码估值，即令：这是一种通过经验与归纳由收码推测发码的方法，是我们认为的最优译码算法。但在实际译码时，后验概率的定量确定是很困难的。最大似然译码：在已知r的条件下使先验概率最大的译码算法，即令：，p(r|c)为似然函数当发送码的概率都相等以及接受码的概率也都相等时，二者等效。根据贝叶斯公式可以建立先验概率和后验概率之间的关系：第49页，课件共107页，创作于2023年2月设每个码字长为n，若接收码字R与码字C的距离为d(R,C)，则条件概率p(R│C)可表示为：最大化p(R│C)等价于最小化d(R,C)，所以使差错概率最小的译码是使接收向量R与输出码字C’距离最小的译码。对于BSC信道，最大似然译码就是最小距离译码。（5）构造标准阵列译码表上述概率译码不能进行实时译码：

每收到一个码字R,就要计算一次伴随式S，然后求解方程组，得到2k个差错图样，选择重量轻者进行译码。第50页，课件共107页，创作于2023年2月为此，首先构造标准阵列译码表，事先将所有不同取值的伴随式S所对应的差错图样全部解出来，选择最轻者与所有可能的发送码字相加，得到所有可能的接收码字。并将它们排列成表格，接收端只需要根据接收到的码字查表即可译码。标准阵列的构造方法是：⑴选择所有码字构成阵列的第0行，通常将全零码字c1作为第0行第1列元素。⑵选择差错图案ei作为第0列，通常以无差错图案e1=(0…0)作为第0列第l行元素。⑶阵列中的i行j列元素为ei＋cj；i=l,2,…2r，j=l,2,…2k⑷对越小的i，ei选择为越容易出现的差错图案

以（6,3）码为例介绍：第51页，课件共107页，创作于2023年2月（6，3）码：陪集首c1000000c2001110c3010011c4011101c5100101c6101011c7110110c8111000se1000000e1+c1000000e1+c2001110e1+c3e1+c4e1+c5e1+c6e1+c7e1+c8000e2000001e2+c1000001001e3000010e3+c1010e4000100e4+c1100e5001000e5+c1ei+cj010101110e6010000e6+c1011e7100000e7+c1101e8100010e8+c1100010101100110001111111000111001001010100011010111第52页，课件共107页，创作于2023年2月伴随式S有23=8种组合，而差错图样中代表无差错的有一种，代表一个差错的图案有=6种，代表两个差错的图案=15种。要把8个伴随式对应到8个最轻的差错图样，无疑应先选无差错的图案和6种一个差错的图样。对于两个差错的图样，我们只能挑选其中的1个，至于挑选方法可有若干种，不是唯一的。先将ei=(000000)、(000001)、…(100000)解得对应的S；剩下的伴随式（111）所对应的差错图案有2k=8个，其中(100010)、(001001)、(010100)并列重量最轻，任选其中一个比如(100010)。陪集首：在最小距离准则下最可能产生错误的集合标准阵列译码：根据最大似然译码思想，把2n个n重接收矢量划分成2k个互不相交的子集D1D2…，在这2k个子集中使每个子集仅含有一个码字，使得某个子集Di与某一ci一一对应。译码时，凡是落在Di这个子集中的接收矢量都被译成ci.第53页，课件共107页，创作于2023年2月举例：当收到码组R=[111011]时，判断是否码字？解：查表：e=[010000]c=r⊕e=[101011]

7、完备码

任何一个二元（n，k）线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，即伴随式的数目满足条件：上式称作汉明限，任何一个纠t码都应满足上述条件。第54页，课件共107页，创作于2023年2月如果某二元（n，k）线性分组码伴随式数目恰好和不大于t个差错的图案数目相等，相当于在标准阵列中能将所有重量不大于t的差错图案选作陪集首而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。（1）完备码：满足方程的二元(n，k)线性分组码（2）完备码特性：围绕2k个码字、汉明距离为t的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码离发送码的距离至多为t，这时所有重量≤t的差错图案都能用最佳（最小距离）译码器得到纠正，而所有重量≥t＋1的差错图案都不能纠正。（3）几种完备码：汉明码：t=1（d=3）的二进制完备码由上述方程得：m＝3，→（7，4）m＝4，→（15，11）m＝5，→（31，26）m＝6，→（63，57）m＝7，→（127，120）m＝8，→（255，247）第55页，课件共107页，创作于2023年2月汉明码的构造:汉明码的校验矩阵H具有特殊的性质(二进制时):（n，k）码的H：r×nr个码元所能组成的列矢量总数是2r－l，（全零矢量除外）恰好和校验矩阵的列数n=2m－1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。例：（7，4）汉明码.相应的伴随式计算方程：第56页，课件共107页，创作于2023年2月另一种完备码：（高莱）戈雷码，t=3的（23，12）二进制完备码采用伴随式计算的一种纠错译码电路实现形式如图:满足方程：第57页，课件共107页，创作于2023年2月总复习（一）1、按发出符号之间的关系来分，信源可以分为（）和（）2、连续信源的熵是（），不再具有熵的物理含义。3、对于有记忆离散序列信源，需引入（）描述信源发出的符号序列内各个符号之间的统计关联特性3、连续信源X,平均功率被限定为P时，符合（）分布才具有最大熵，最大熵是（）。4、数据处理过程中信息具有（）。5、信源冗余度产生的原因包括（）和（）。6、单符号连续信道的信道容量取决于（）。7、香农信息极限的含义是（）。8、对于无失真信源编码，平均码长越小，说明压缩效率（）。第58页，课件共107页，创作于2023年2月9、对于限失真信源编码，保证D的前提下，尽量减少（）。10、立即码指的是（）。11、算术编码是（）分组码。12、游程编码是（）失真信源编码。13、线性分组码的（）就是该码空间的对偶空间的生成矩阵。14、若（n，k）线性分组码为MDC码，那么它的最小码距为（）。15、完备码的特点是（）。16、卷积码的自由距离决定了其（）。第59页，课件共107页，创作于2023年2月（）1、信息是指各个事物运动的状态及状态变化的方式。（）2、信息就是信息，既不是物质也不是能量。（）3、马尔可夫信源是离散无记忆信源。（）4、不可约的马尔可夫链一定是遍历的。（）5、单符号连续信源的绝对熵为无穷大。（）6、序列信源的极限熵是这样定义的：H(X)=H(XL|X1,X2,…,XL-1)。（）7、平均互信息量I(X;Y)是接收端所获取的关于发送端信源X的信息量。（）8、信源X,经过处理后，输出为Y，H(Y)小于H(X),说明信息不增。（）9、如果一个消息包含的符号比表达这个消息所需要的符号多，那么该消息存在冗余度。（）10、有噪无损离散信道的输入为X,输出为Y，那么其信道容量Ｃ＝ｍａｘＨ（Ｙ）。第60页，课件共107页，创作于2023年2月（）11、非高斯噪声信道的信道容量比高斯噪声信道的信道容量小。（）12、信息率失真函数具有单调递减性。（）13、异前缀码不能及时可译。（）14、用码树构造的一定是及时码。（）15、香农编码压缩了符号相关造成的冗余。（）16、有失真信源编码指的是保真度准则下的信源编码。（）17、变长无失真信源编码比定长编码的编码效率高。（）18、香农编码是最佳编码。（）19、卷积、交织都可以达到差错随机化的目的。。（）20、卷积码的序列距离决定了其检错和纠错能力。第61页，课件共107页，创作于2023年2月复习

第三节线性分组码四、线性分组码1、基本概念2、最简单的线性分组码—奇偶检验码3、错误图样4、矢量空间和码空间5、线性分组码的生成矩阵和校验矩阵6、伴随式和标准阵列译码7、完备码第62页，课件共107页，创作于2023年2月8、循环码——由循环移位特性而界定的一类线性分组码设n位码组：c=(c0,c1,…,cn-2,cn-1),ci∈{0,1}则右移一位：c(1)

=(cn-1,c0,c1,…,cn-2),右移i位：c(i)

=(cn-i,cn+1-i,…,cn-1,c0,c1,…,cn-1-i),

i=1~n第63页，课件共107页，创作于2023年2月（1）循环码的多项式描述1.码字的多项式表示：（n，k）码例:c(x)=c0+c1x+…+cn-1xn-1,(n-1次)(1)一般形式f(x)=f0+f1x+…+fnxn,(n次)(2)性质①多项式次数②零次多项式——f(x)=f0③零多项式——f(x)=0④两多项式四则运算——同一般多项式第64页，课件共107页，创作于2023年2月（1）循环码的多项式描述(续)1.码字的多项式表示(3)模运算——与整数模运算相同如：3=1(mod2)，x2+1=1(modx2)一般式：如有h(x)=q(x)f(x)+r(x)则有h(x)=r(x)(modf(x))对于循环码，有：

c(i)(x)

=c(x)xi

(modxn+1)

如：c=(c0,c1,…,cn-2,cn-1),ci∈{0,1}

码多项式为：c(x)=c0+c1x+…+cn-1xn-1,

右移一位：c(1)(x)=c(x).x(modxn+1)

=c0x+c1x2+…+cn-2xn-1+cn-1xn

(modxn+1)

第65页，课件共107页，创作于2023年2月相应的码字为：

c(1)

=(cn-1,c0,c1,…,cn-2)=c0x+c1x2+…+cn-2xn-1+cn-1xn

(modxn+1)

=c0x+c1x2+…+cn-2xn-1-cn-1

=cn-1+c0x+c1x2+…+cn-2xn-1

同理：右移2位：c(2)(x)=c(x).x2

(modxn+1)

=c0x2+c1x3+…+cn-3xn-1+cn-2xn+cn-1xn+1

(modxn+1)

=c0x2+c1x3+…+cn-3xn-1-cn-2-cn-1x=cn-2+cn-1x+c0x2+c1x3+…+cn-3xn-1相应的码字为：

c(2)

=(cn-2,cn-1,c0,c1,…,cn-3)第66页，课件共107页，创作于2023年2月结论：c(i)(x)

=c(x)xi

(modxn+1)n位码字的循环右移i位等价于相应的码多项式乘以xi后取xn+1的模剩余2.定义——若一个线性分组码的任意一个码字c，都是另一个码字c’的循环移位，则称为循环码3.生成多项式g(x)(1)定义(n,k)循环码c(x)中存在着唯一的一个生成多项式g(x)，其最高次为r=n-k，常数项为1，且是xn+1的一个因子g(x)=xr

+gr-1xr-1+…+g1x+1(2)性质：①任一码多项式必是g(x)的倍式：c(x)=a(x)g(x)②任一次数≤k-1的多项式a(x)与g(x)相乘，必为码多项式第67页，课件共107页，创作于2023年2月（2）循环码的构造方法

对xn+1作因式分解，求出所有的最小多项式，从而求出n-k次的因式作为生成多项式g(x)。用生成多项式g(x)乘以信息多项式m(x),得到码多项式c(x)。例题：研究构造一个长度n=7的循环码的构造方法。解：对x7+1作因式分解(二元域）：

x7+1=（x+1）（x3+

x2+1）（x3+

x

+1）验证：（x+1）（x3+

x2+1）（x3+

x

+1）=x7+2x6+2x5+4x4+2x2+2

x

+1mod(2)=x7+1第68页，课件共107页，创作于2023年2月共有4种因式：1次----x+13次----x3+

x2+1和x3+

x

+14次----x4+x2+

x

+1和x4+x3+x2+16次----x6+x5+x4+x3+x2+

x

+1选择生成多项式：g(x)=x+1，n-k=1,k=6→(7,6)循环码g(x)=x3+

x2+1或x3+

x

+1→(7,4)循环码g(x)=x4+x2+

x

+1或x4+x3+x2+1→(7,3)循环码g(x)=x6+x5+x4+x3+x2+

x

+1→(7,1)循环码第69页，课件共107页，创作于2023年2月以g(x)=x4+x3+x2+1为例构造(7,3)循环码：m1=(000),m(x)=0,c(x)=

m(x)g(x)=0→c=(0000000)m2

=(001),m(x)=1,c(x)=

m(x)g(x)=g(x)

→c=(0011101)m3=(010),m(x)=x,c(x)=

m(x)g(x)=x5+x4+x3+x

→c=(0111010)m4=(011),m(x)=x+1,c(x)=

m(x)g(x)=x5+x2+x+1

→c=(0100111)m5=(100),m(x)=x2,c(x)=

m(x)g(x)=x6+x5+x4+x2

→c=(1110100)m6=(101),m(x)=x2+1,c(x)=

m(x)g(x)=x6+x5+x3+1→c=(1101001)m7=(110),m(x)=x2+x,c(x)=

m(x)g(x)=x6+x3+x2+x

→c=(1001110)m8=(111),m(x)=x2+x+1,c(x)=

m(x)g(x)=x6+x4+x+1→c=(0111010)第70页，课件共107页，创作于2023年2月（3）循环码的校验多项式生成多项式g(x)是xn+1的一个因子，即：xn+1=g(x).h(x)那么，对于任意码多项式c(x)有：c(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)。定义h(x)=(xn+1)/g(x)=h0+h1x+…+hk-1xk-1+hkxk为循环码的校验多项式。正如普通线性分组码的生成矩阵G和校验矩阵H的关系，(n,k)循环码的校验多项式h(x)是(n,n-k)对偶码的生成多项式。第71页，课件共107页，创作于2023年2月

=[mk-1mk-2…m0] =[mk-1mk-2…m0]

其中，g(x)=gn-kxn-k+…+g1

x+g0

（4）循环码的生成矩阵和校验矩阵第72页，课件共107页，创作于2023年2月将矩阵中的多项式改写成对应的n重矢量形式，得矢量的矩阵表达式：

C=(cn-1,…c1,c0)=[mk-1,…m1,m0]=mG这里，我们定义(k

n)矩阵G为循环码的生成矩阵第73页，课件共107页，创作于2023年2月循环码的(n-k)n阶的校验矩阵可写为：H= 循环码生成矩阵G与校验矩阵的乘积一定是的零阵。GHT＝0

第74页，课件共107页，创作于2023年2月(5)系统循环码设信息多项式m(x)=mk-1xk-1+…+m1x+m0则系统循环码c(x)=xn-km(x)+r(x),r(x)---监督式∵c(x)=a(x)g(x)=0modg(x)∴r(x)=xn-km(x)modg(x)构码步骤：①升幕：信息多项式乘以xn-k→xn-km(x),即右移n-k位②求余：r(x)=xn-k

m(x)modg(x)③拼合：c(x)=xn-km(x)+r(x)——循环码多项式第75页，课件共107页，创作于2023年2月例6-6(7,3)循环码g(x)=x4+x3+x2+1,构造系统码以m=(011),m(x)=x+1为例：升幂：xn-km(x)=x5+x4余式：r(x)=x5+x4mod(x4+x3+x2+1)=x3+x拼合：c(x)=xn-km(x)+r(x)=x5+x4+x3+x即：c=(0111010)同理：可求出其它信息序列m=(xxx)对应的编码输出第76页，课件共107页，创作于2023年2月（6）循环码编码电路非系统码编码电路——乘法编码电路c(x)=m(x)·

g(x)如：(7,4)循环码g(x)=x3+x2+1,设m(x)=x3+x，低幂次在前可用下图实现编码：s2s1s0m(x)g0=1c(x)g2=1g3=1节拍ms2s1s0c123401010000001000100100567000101010001111关系s2´=m,s1´=s2,s0´=s1,c=m+s1+

s0,“´”——下一个值m=0101(升幂)，

c=0100111第77页，课件共107页，创作于2023年2月2.系统循环码编码—除法编码电路如：(7.4)系统循环码,g(x)=x3+x2+1,设：m(x)=x3+x+G1p0p1p2g0=1G2m(x)(m3m2

m1

m0000)c(x)(c6c5…c0)g2=1g3=1节拍mp0p1p2cG1G2关系12341010000101111011101010101010p

0=m+p2p

1=p0p

2=p

0+p1567000100010001001010101p

0=0p

1=p0p

2=p1结论：m=1010，

c=1010001第78页，课件共107页，创作于2023年2月9、BCH码和RS码

BCH码是纠错能力可控的纠随机差错码，是循环码的子类。该码有严格的代数结构，生成多项式g(x)与最小距离d有密切关系，使设计者可以根据对d的要求，轻易地构造出具有预定纠错能力的码。BCH编、译码电路比较简单，易于工程实现，在中、短码长情况下的性能接近理论最佳值。因此BCH码不仅在编码理论上占有重要地位，而且也是实际使用最广泛的码之一Bose

ChandhariBCH

HocquenghemBCH码最初是定义在GF(2)域上的二进制码，后被推广到多元域GF(q)上。第79页，课件共107页，创作于2023年2月（1）什么是GF域？对于任何质数p，存在一个有限域，域中含有p个元素；任何两个元素的和、积仍在域中，且满足交换率、结合率和分配率，称此域为GF(p)域。如：二元域GF(2)={0,1)（2）GF域多项式如：二元域多项式

p(x)=x3+x2+1，x取值为0或1

二元域本原多项式：m次的二元域多项式，若满足以下条件，称为本原多项式。既约（不能再因式分解）；能整除xn+1,n=2m-1

；不能整除xq+1,q<n第80页，课件共107页，创作于2023年2月（3）GF(pm)扩域如：二元扩域GF(2m)，可以用二元域上的本原多项式来产生。以p(x)=x3+x+1为例，m=3,GF(23)={0、1、

1、

2、

3、

4、

5、

6}。其中，

为本原元，它是本原多项式在扩域上的的根。域不同则多项式的分解亦不同，在一个域的既约不等于在另一个域的既约。如：（x4-1）在不同域上的因式分解在实数域的分解：x4-1=

(x2+1)(x+1)(x-1)在复数域的分解：x4-1=

(x+i)(x-i)(x+1)(x-1)在二元域的分解：x4-1=x4+1=(x+1)(x+1)(x+1)(x+1)本原多项式（既约的）在GF(2)上不能再分解，但在二元扩域GF(2m)未必就不能再分解，因GF(2m)是多项式域，系数取值于{0、1、

1、

2、…、}。第81页，课件共107页，创作于2023年2月（4）二元域本原多项式在GF(2m)扩域上的根

则：

3=

+1；

4=

3=

(

+1)=

2+

;

5=

3

2=(

+1)(

2+

)=

2+

+1

；

6=

2+1;8个元素都可以表示为的最高幂次为m-1(这里m=3)的多项式

此外，

2和

4是p(x)=x3+x+1

的另外两个根：p(

2)=

6+

2

+1=2+1+2+1=0;p(

4)=

12+

4

+1=6

6+

4+1=24+22+2=0;据近世代数理论，幂次为m的多项式，必有m个根。如：本原多项式p(x)=x3+x+1产生的二元扩域为GF(23)，本原元

为其中的一个根，p(

)=

3+

+1=0而

、

3、

5不是它的根；当然0和1也不是它的根。第82页，课件共107页，创作于2023年2月

、

2、

4是p(x)=x3+x+1

在扩域上的三个根，可作如下因式分解：x3+x+1

=(x+)(x+

2)(x+

4)

(5)

xn+1

在其本原多项式定义的扩域上的根n个根;以n=7为例，x7+1在其本原多项式p(x)=x3+x+1定义的扩域GF(23)={0,1,

,

2,

3,

4,

5,

6

}有7个根。

普通的循环码(n,k)，其生成多项式g(x)是xn+1在二元域上的因式；而BCH码的生成多项式g(x)则是xn+1在二元扩域上的因式。所以，关心xn+1

在其本原多项式定义的扩域上的根。除了0以外,1,

,

2,

3,

4,

5,

6都是x7+1的根。第83页，课件共107页，创作于2023年2月实际上x7+1的7个根1,

,

2,

3,

4,

5,

6是其三个最小多项式在扩域上的根的集合。x7+1=(x+1)(x3+x+1)=(x3+x2+1)(二元域上）其中：x+1在扩域上的根为1

x3+x+1在扩域上的3个根为

,

2,

4x3+x2

+1在扩域上的3个根为

3,

5,

6每一个根都对应于一个最小多项式

(6)

BCH码用xn+1

在其本原多项式定义的扩域GF(2m)上的2t个连续幂次的根

,

2,…

,

2t所对应的最小多项式mi(x)的最小公倍式作为生成多项式生成的循环码。(t为纠错能力)纠错能力可控第84页，课件共107页，创作于2023年2月总结：本原BCH码构造法①由关系式n=2m-1算出m，查表，找到一个m次本原多项式P(x)，产生一个GF(2m)扩域。②在GF(2m)上找一个本原元

，分别计算2t个连续幂次根

、

2、…、

2t所对应的GF(2)域上的最小多项式m1(x)、m2(x)…m2t(x)。m

8时连续幂次根

i所对应的最小多项式见表。③计算这些最小多项式的最小公倍式，得到生成多项式g(x)g(x)=LCM[m1(x)m2(x)…m2t(x)] ④由关系式C(x)=m(x)g(x)求BCH码字。例题6-8设计一个码长n=7的二元本原BCH码，在不同纠错能力下的生成多项式是怎样的？第85页，课件共107页，创作于2023年2月解：①n=7m=3查表：m=13(8进制表示，即001011）；本原多项式为p(x)=x3+x+1②dmin≤n=2m-1→t≤(dmin-)/2=2m-1-1=3分别计算2t个连续幂次的根对应的最小多项式：t=1,2t=2;2个连续幂次的根

,

2

→(x3+x+1),

2→(x3+x+1)∴g(x)=x3+x+1生成(7,4)码。t=2,2t=4;4个连续幂次的根

,

2,

3,

4

,

2,

4→(x3+x+1),

3→(x3+x2+1)∴g(x)=(x3+x+1)(x3+x2+1)=x6+x5

+x4+x3

+x2+x+1,(7,1)码。t=3，结果同上第86页，课件共107页，创作于2023年2月

(6)

RS码---多进制BCH码RS---Reed-Solomon里德-索洛蒙码，BCH码最重要的一个子类符号集由本原多项式产生的扩域GF(2m)中的元素构成。

BCH码二元域：GF(2)={0,1}本原多项式：如p(x)=(x3+x+1)扩域：GF(2m)={0,1,

,

2,….}符号集：{0，1}多项式：g(x)=gn-k

xn-k+….+g1

x+g0

m(x)=mk-1

xk-1+….+m1

x+m0

c(x)=cn-1

xn-1+….+c1

x+c0

各多项式以0或1为系数g(x)---2t个连续幂次的根对应的最小多项式的最小公倍式。

RS码二元域：GF(2)={0,1}本原多项式：如p(x)=(x3+x+1)扩域：GF(2m)={0,1,

,

2,….}符号集：{0,1,

,

2,….

q-2}多项式：g(x)=gn-k

xn-k+….+g1

x+g0

m(x)=mk-1

xk-1+….+m1

x+m0

c(x)=cn-1

xn-1+….+c1

x+c0

各多项式以0,1,

,

2,….

q-2为系数g(x)---2t个连续幂次的根。g(x)=(x-

)(x-

2)…(x-

2t)第87页，课件共107页，创作于2023年2月总复习（二）信息、消息、信号的定义是什么？三者的关系是什么？什么样的马尔可夫链是遍历的？简述离散信源的最大熵定理。简述信息率失真函数的物理意义。叙述变长信源编码定理。惟一可译码存在的充要条件是什么？什么是差错图样？有哪些差错图样类型？什么是本原多项式？对于信道编码，有哪两种译码算法？简述之。为什么说BSC信道的最小距离译码就是最大似然译码？什么是完备吗？举出两种完备吗的例子。写出卷积码的解析表达式。说明为什么称之为卷积码？第88页，课件共107页，创作于2023年2月设在一只布袋中装有100个大小相同的乒乓球，（1）若红色球和白色球各50个，从中随机取出一个球，问猜测其颜色需要的信息量是多少？（2）若红色球99个，白色球1个，从中随机取出一个球，猜测其颜色需要的信息量又是多少？某信道为强对称信道（即均匀信道）输入符号和输出符号的个数均为m，正确的传输概率为1—ε,错误概率为ε被对称的均匀分给m—1个输出符号，试写出转移概率矩阵及其信道容量的表达式。第89页，课件共107页，创作于2023年2月一个平均功率受限的连续信道，其通频带为1MHZ,信道上存在白色高斯噪声。（1）已知信道上的信号和噪声的平均功率比值为10，求该信道的信道容量。（2）信道上的信号和噪声的平均功率比值降为5，要达到相同的信道容量，信道的通频带应为多大？（3）若信道通频带减少为0.5MHZ,信道上的信号和噪声的平均功率比值应为多大？（4）。。。。设有离散无记忆信源P(X)={0.37,0.25,0.18,0.10,0.07,0.03},（1）、求该信源的符号熵。（2）、用哈夫曼编码编成二元变长码，计算其编码效率。（3）、要求其译码错误小于10采用定长二元码要达到（2）中的哈夫曼编码效率，问需要多少个信源符号连在一起编？第90页，课件共107页，创作于2023年2月卷积码——convolutionalcode发展1955年，埃里亚斯(Elias)提出卷积码1957年，伍成克拉夫特(Wozencraft)提出序列译码1963年，梅西(Massey)提出门限译码1967年，维特比(Viterbi)提出最大似然译码优点——简单、性能好主要应用——FEC（前向纠错）系统，纠错6.4卷积码

6.4.1卷积码概述第91页，课件共107页，创作于2023年2月特点输出的n个码元中，每个码元不仅与本段的k比特信息码元有关，而且还与前m段的信息码元有关记作——(n,k,m)n、k较小，m较大(m＜10)参数码率——k/n记忆长度m——有效工作的移存器段数编码约束度N=m+1——相互关联的码段个数编码约束长度Nn——相互关联的码元个数第92页，课件共107页，创作于2023年2月编码输出每次输入k比特1k…1k…1k…1k…………

1…k…2k3kNk……………

…………

12nNk级移存器n个模2加法器每输入k比特旋转1周输出n比特6.4.2卷积码编码原理第93页，课件共107页，创作于2023年2月特点工作流程——按段工作：对每段k比特信息码元输入，产生一段n比特输出连环码——每一码段与前后码段皆有关，环环相扣卷积码——能以离散卷积表达式表示线性非分组码分析方法解析法——离散卷积法、生成矩阵法、码多项式法图解法——状态图法、树图法、网格图法6.4.2卷积码编码原理(续)第94页，课件共107页，创作于2023年2月每输入1比特，编码器输出3比特c1c2c3输入为1101时，编码器的工作状态表如下123b3b1输入b2编码输出c2c1c3b11101000b3b200011110011000c1c2c3111110010100001011000状态abdcbca卷积码编码器实例——（3,1,2）码第95页，课件共107页，创作于2023年2月000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3abcdabcdabcdabcd上半部下半部信息位 1 1 0 1ba起点信息位000111c1c2c310aabcdabcdcdab↑0↓1↓1↑0↑0↓16.4.3卷积码的分析方法1.树图法——[例](3,1,2)卷积码树图(0走上，1走下)状态b3b2abcd00011011第96页，课件共107页，创作于2023年2月2.状态表和状态图123b3b1输入b2编码输出c2c1c3b1/1101/111adc0/0001/1000/0010/0100/0111/101当前状态b3b2输入

b1输