第六章信道编码优秀课件.ppt

第六章信道编码2022/10/71第1页，本讲稿共107页一、信道编码一、信道编码线路码与纠错码线路码与纠错码 信信道道编编码码是是以以信信息息在在信信道道上上的的正正确确传传输输为为目目标标的的编编码码，它它可可分分为为两两个个层层次次上上的的问问题题：一一是是如如何何正正确确接接收收载载有有信信息息的的信信号号，二二是是如如何何避避免免少少量量差差错错信信号号对对信信息息内内容容的的影影响响；前前者者是是通通信信原原理理的的问问题题，后后者者是是信信息息论论的问题。的问题。比比如如在在数数字字基基带带信信号号中中的的编编码码，主主要要目目的的是是为为了了消消除除直直流流分分量量、改改造造信信号号频频谱谱、便便于于时时钟钟频频率率的的提提取取、实实现现数数字字信信号号的的透透明明传传输输等等。还还有有的的是是为为了了压压缩缩占占用用带带宽宽、抑抑制制码码间间干干扰扰，如如部部分分响响应应系系统统。这这个个层层次次上上的的编编码码，如如曼曼彻彻斯斯特特码码、AMI码码、HDB3码码、nBmB码码、部部分响应系统中的相关编码等，一般称之为线路编码（分响应系统中的相关编码等，一般称之为线路编码（line code）。）。第2页，本讲稿共107页 从从信信息息论论角角度度来来看看的的信信道道编编码码是是指指第第二二层层次次的的编编码码，即即差差错错控控制制编编码码，包包括括各各种种形形式式的的纠纠错错、检检错错码码，统统称称为为纠纠错错编编码码。纠纠错错编编码码的的理理论论体体系系属属于于信信息息理理论论，但但纠纠错错编编码码的的实实现现离离不不开开有有形形载载体体的的信信号号理理论论，因因此此信信息息的的编编码码与与信信号号的的编编码码有有天天然然联联系系。纠纠错错码码在在有有形形化化信信号号阶阶段段的的差差错错概概率率是是符符号号(symbol)差差错错概概率率（误误码码元元率率），而而在在承承载载信信息息方方面面的的差差错错概率是比特差错概率概率是比特差错概率(误比特率误比特率)。本本书书讨讨论论的的信信道道编编码码主主要要指指纠纠错错编编码码，而而衡衡量量纠纠错错编编码码性性能的指标主要是误比特率的改善程度。能的指标主要是误比特率的改善程度。第3页，本讲稿共107页举例说明：举例说明：A A、B B两消息，可用一位二进制数表示，两消息，可用一位二进制数表示，A=1A=1、B=0B=0出错时无法判定出错时无法判定。增加一个增加一个监督监督位，取位，取11A11A、00B,00B,若收到若收到0101或或1010时，时，可知发生了错误，但不能纠正错误。可知发生了错误，但不能纠正错误。再增加一个监督位，取再增加一个监督位，取111A111A、000B,000B,若一位错：若一位错：B001 B001 A110A110，这样纠码：，这样纠码：001 000 B,110 111 A001 000 B,110 111 A若两位若两位错错011,110011,110则则只能只能发现发现不能不能纠错纠错 因此，这种（因此，这种（3 3，1 1）码，能纠正一个错，发现两个错。）码，能纠正一个错，发现两个错。可以看出：本来只需要可以看出：本来只需要2 2位二进制数就可以表示位二进制数就可以表示A A、B B两个符号两个符号，用，用2 2或或3 3位表示时，码长变长，带来信息冗余。所以，位表示时，码长变长，带来信息冗余。所以，纠错能力是纠错能力是靠冗余换取的靠冗余换取的。二、检错和纠错（差错控制）的基本原理二、检错和纠错（差错控制）的基本原理：第4页，本讲稿共107页第一、二节 有扰离散信道的编码定理一、差错控制一、差错控制（1）前向纠错法）前向纠错法FEC 所发码具有纠错能力，收端接收后自动纠错，无需反向所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备复杂，信道。实时性好，但译码设备复杂，传输效率传输效率。信源FEC编码信道FEC译码信宿（2）反馈重发）反馈重发ARQ(Automatic Repeat Request 能检错的码能检错的码应答信号应答信号发端发端收端收端第5页，本讲稿共107页 方法和设备简单，无需纠检错编译系统。但需要双向信道，方法和设备简单，无需纠检错编译系统。但需要双向信道，传传输效率输效率、实时性差、实时性差。（3）混合纠错法）混合纠错法HEC 能纠错（能力能纠错（能力有限）的码有限）的码应答信号应答信号发端发端收端收端性能介于前面二者之间性能介于前面二者之间第6页，本讲稿共107页（1）根据各码组信息码和监督码的关系分：根据各码组信息码和监督码的关系分：线性码，非线性码线性码，非线性码根据监督码元是否仅与本组信息元有关根据监督码元是否仅与本组信息元有关 分组码，卷积码分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：根据纠错码组中信息元是否隐蔽分：系统码，非系统码系统码，非系统码（3）根据码的用途分：根据码的用途分：检错码检错码 ，纠错码，纠错码（4）根据根据码元的取值码元的取值：二进制码，多进制码二进制码，多进制码（5）根据根据构造编码的数学方法构造编码的数学方法：代数码，几何码，算术码代数码，几何码，算术码（6）二、二、纠错码的分类纠错码的分类第7页，本讲稿共107页 对于给定的有扰信道，若信道容量为对于给定的有扰信道，若信道容量为C，只要发送端以低于，只要发送端以低于C的信息速率的信息速率Rb发送信息，则发送信息，则一定存在一种编码方法一定存在一种编码方法，使得译码，使得译码错误概率错误概率P随着码长随着码长n的增加，按指数下降至任意小的值，表示为的增加，按指数下降至任意小的值，表示为 P e-nE(Rb)E(Rb)为误差指数，为误差指数，Rb0。两个结论：两个结论：1.码长码长n和信息速率和信息速率Rb一定时，随一定时，随C E(Rb)P随指数下降。随指数下降。其中其中 C=Blog2(1+S/N)（bit/s）2.在在C和和Rb一定时一定时(Rb k=3.n=6G=0 01 1 1;0 1 1 0 0 1;1 0 1 0 1 1Gs=1 0 0 0 1 1;0 1 0 1 0 1;0 0 1 1 1 1第44页，本讲稿共107页复习矢量空间的矢量空间的基底基底、生成生成重数重数-构成矢量的元素的个数构成矢量的元素的个数维数维数-张成矢量空间的基底的个数张成矢量空间的基底的个数矢量空间的正交、对偶空间矢量空间的正交、对偶空间分组编码的数学概念分组编码的数学概念第45页，本讲稿共107页生成矩阵：第46页，本讲稿共107页校校验验矩矩阵阵例例6-2 6-2 ！第47页，本讲稿共107页伴随式和标准阵列译码伴随式和标准阵列译码编、译码过程编、译码过程：选择重量最轻的那组差错图样进行译码选择重量最轻的那组差错图样进行译码理解最小距离译码理解最小距离译码Go on第48页，本讲稿共107页 最佳译码（最大后验概率译码）：在已知r的条件下找出可能性最大的发码c作为译码估值，即令：这是一种通过经验与归纳由收码推测发码的方法，是我们认为的最优译码算法。但在实际译码时，后验概率的定量确定是很困难的。最大似然译码：在已知r的条件下使先验概率最大的译码算法，即令：，p(r|c)为似然函数当发送码的概率都相等以及接受码的概率也都相等时，二者等效。根据贝叶斯公式可以建立先验概率和后验概率之间的关系：第49页，本讲稿共107页设每个码字长为n，若接收码字 R 与码字 C 的距离为 d(R,C)，则条件概率 p(RC)可表示为：最大化 p(RC)等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C 距离最小的译码。对于BSC信道，最大似然译码就是最小距离译码。（5）构造标准阵列译码表 上述概率译码不能进行实时译码：每收到一个码字R,就要计算一次伴随式S，然后求解方程组，得到2k个差错图样，选择重量轻者进行译码。第50页，本讲稿共107页 为此，首先构造标准阵列译码表，事先将所有不同取值的伴随式S所对应的差错图样全部解出来，选择最轻者与所有可能的发送码字相加，得到所有可能的接收码字。并将它们排列成表格，接收端只需要根据接收到的码字查表即可译码。标准阵列的构造方法是：选择所有码字构成阵列的第0行，通常将全零码字 c1作为第0行第 1列元素。选择差错图案ei作为第0列，通常以无差错图案e1=(00)作为第0列第 l行元素。阵列中的i行j列元素为eicj；i=l,2,2r，j=l,2,2k对越小的i，ei选择为越容易出现的差错图案 以（6,3）码为例介绍：第51页，本讲稿共107页（6，3）码：陪集首c1000000c2001110c3010011c4011101c5100101c6101011c7110110c8111000se1000000e1+c1000000e1+c2001110e1+c3e1+c4e1+c5e1+c6e1+c7e1+c8000e2000001e2+c1000001001e3000010e3+c1010e4000100e4+c1100e5001000e5+c1ei+cj010101110e6010000e6+c1011e7100000e7+c1101e8100010e8+c1100010101100110001111111000111001001010100011010111第52页，本讲稿共107页 伴随式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页举例：当收到码组R=111011时，判断是否码字？解：查表：e=010000 c=re=101011 7、完备码 任何一个二元（n，k）线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，即伴随式的数目满足条件：上式称作汉明限，任何一个纠t码都应满足上述条件。第54页，本讲稿共107页 如果某二元（n，k）线性分组码伴随式数目恰好和不大于t个差错的图案数目相等，相当于在标准阵列中能将所有重量不大于t的差错图案选作陪集首而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。（1）完备码：满足方程 的二元(n，k)线性分组码（2）完备码特性：围绕2k个码字、汉明距离为t的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码离发送码的距离至多为t，这时所有重量t的差错图案都能用最佳（最小距离）译码器得到纠正，而所有重量t1的差错图案都不能纠正。（3）几种 完备码：汉明码：t=1（d=3）的二进制完备码由上述方程得：m3，（7，4）m4，（15，11）m5，（31，26）m6，（63，57）m7，（127，120）m8，（255，247）第55页，本讲稿共107页汉明码的构造:汉明码的校验矩阵H具有特殊的性质(二进制时):（n，k）码的H：rnr个码元所能组成的列矢量总数是 2rl，（全零矢量除外）恰好和校验矩阵的列数 n=2m1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。例：（7，4）汉明码.相应的伴随式计算方程：第56页，本讲稿共107页另一种完备码：（高莱）戈雷码，t=3的（23，12）二进制完备码采用伴随式计算的一种纠错译码电路实现形式如图:满足方程：第57页，本讲稿共107页总复习（一）1、按发出符号之间的关系来分，信源可以分为（）和（）2、连续信源的熵是（），不再具有熵的物理含义。3、对于有记忆离散序列信源，需引入（）描述信源发出的符号序列内各个符号之间的统计关联特性3、连续信源X,平均功率被限定为P时，符合（）分布才具有最大熵，最大熵是（）。4、数据处理过程中信息具有（）。5、信源冗余度产生的原因包括（）和（）。6、单符号连续信道的信道容量取决于（）。7、香农信息极限的含义是（）。8、对于无失真信源编码，平均码长越小，说明压缩效率（）。第58页，本讲稿共107页9、对于限失真信源编码，保证 D的前提下，尽量减少（）。10、立即码指的是（）。11、算术编码是（）分组码。12、游程编码是（）失真信源编码。13、线性分组码的（）就是该码空间的对偶空间的生成矩阵。14、若（n，k）线性分组码为MDC码，那么它的最小码距为（）。15、完备码的特点是（）。16、卷积码的自由距离决定了其（）。第59页，本讲稿共107页（）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页（）11、非高斯噪声信道的信道容量比高斯噪声信道的信道容量小。（）12、信息率失真函数具有单调递减性。（）13、异前缀码不能及时可译。（）14、用码树构造的一定是及时码。（）15、香农编码压缩了符号相关造成的冗余。（）16、有失真信源编码指的是保真度准则下的信源编码。（）17、变长无失真信源编码比定长编码的编码效率高。（）18、香农编码是最佳编码。（）19、卷积、交织都可以达到差错随机化的目的。（）20、卷积码的序列距离决定了其检错和纠错能力。第61页，本讲稿共107页复习 第三节 线性分组码四、四、线性分组码线性分组码1 1、基本概念基本概念2、最简单的线性分组码、最简单的线性分组码奇偶检验码奇偶检验码3、错误图样、错误图样4、矢量空间和码空间、矢量空间和码空间5、线性分组码的生成矩阵和校验矩阵、线性分组码的生成矩阵和校验矩阵 6、伴随式和标准阵列译码、伴随式和标准阵列译码7、完备码、完备码第62页，本讲稿共107页8、循环码由循环移位特性而界定的一类线性分组码 设n位码组：c=(c0,c1,cn-2,cn-1),ci0,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=1n第63页，本讲稿共107页（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页（1）循环码的多项式描述(续)1.码字的多项式表示(3)模运算与整数模运算相同 如：3=1(mod2)，x2+1=1(mod x2)一般式：如有 h(x)=q(x)f(x)+r(x)则有 h(x)=r(x)(mod f(x)对于循环码，有：c(i)(x)=c(x)xi (mod xn+1)如：c=(c0,c1,cn-2,cn-1),ci0,1 码多项式为：c(x)=c0+c1x+cn-1xn-1,右移一位：c(1)(x)=c(x).x (mod xn+1)=c0 x+c1x2+cn-2xn-1+cn-1xn (mod xn+1)第65页，本讲稿共107页相应的码字为：c(1)=(cn-1,c0,c1,cn-2)=c0 x+c1x2+cn-2xn-1+cn-1xn (mod xn+1)=c0 x+c1x2+cn-2xn-1-cn-1=cn-1+c0 x+c1x2+cn-2xn-1 同理：右移2位：c(2)(x)=c(x).x2 (mod xn+1)=c0 x2+c1x3+cn-3xn-1+cn-2xn+cn-1xn+1 (mod xn+1)=c0 x2+c1x3+cn-3xn-1-cn-2-cn-1 x =cn-2+cn-1 x+c0 x2+c1x3+cn-3xn-1相应的码字为：c(2)=(cn-2,cn-1,c0,c1,cn-3)第66页，本讲稿共107页 结论：c(i)(x)=c(x)xi (mod xn+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页（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+1 mod(2)=x7+1第68页，本讲稿共107页共有4种因式：1次-x+13次-x3+x2+1 和 x3+x+14次-x4+x2+x+1 和x4+x3+x2+1 6次-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页以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+1c=(0111010)第70页，本讲稿共107页（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)=0 mod(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页 =mk-1 mk-2m0 =mk-1 mk-2m0 其中，g(x)=gn-k xn-k+g1 x+g0（4）循环码的生成矩阵和校验矩阵第72页，本讲稿共107页将将矩矩阵阵中中的的多多项项式式改改写写成成对对应应的的n重重矢矢量量形形式式，得得矢量的矩阵表达式：矢量的矩阵表达式：C=(cn-1,c1,c0)=mk-1,m1,m0 =mG这里，我们定义这里，我们定义(k n)矩阵矩阵G为循环码的生成矩阵为循环码的生成矩阵第73页，本讲稿共107页循环码的循环码的(n-k)n阶的校验矩阵可写为：阶的校验矩阵可写为：H=循循环环码码生生成成矩矩阵阵G与与校校验验矩矩阵阵的的乘乘积积一一定定是是的的零零阵。阵。GHT0 第74页，本讲稿共107页(5)系统循环码 设信息多项式 m(x)=mk-1xk-1+m1x+m0 则系统循环码 c(x)=xn-km(x)+r(x),r(x)-监督式 c(x)=a(x)g(x)=0 mod g(x)r(x)=xn-km(x)mod g(x)构码步骤：升幕：信息多项式乘以 xn-kxn-km(x),即右移n-k位 求余：r(x)=xn-k m(x)modg(x)拼合：c(x)=xn-k m(x)+r(x)循环码多项式第75页，本讲稿共107页例6-6(7,3)循环码 g(x)=x4+x3+x2+1,构造系统码以m=(011),m(x)=x+1为例：升幂：xn-km(x)=x5+x4余式：r(x)=x5+x4 mod(x4+x3+x2+1)=x3+x拼合：c(x)=xn-k m(x)+r(x)=x5+x4+x3+x 即：c=(0111010)同理：可求出其它信息序列m=(xxx)对应的编码输出第76页，本讲稿共107页（6）循环码编码电路1.非系统码编码电路乘法编码电路 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节节拍拍ms2 s1 s0c123401010 0 00 0 01 0 00 1 001005670001 0 10 1 00 0 1111关系s2=m,s1=s2,s0=s1,c=m+s1+s0,“”下一个值m=0101(升幂)，c=0100111第77页，本讲稿共107页2.系统循环码编码除法编码电路如：(7.4)系统循环码,g(x)=x3+x2+1,设：m(x)=x3+x+G1p0p1p2g0=1G2m(x)(m3 m2 m1 m0000)c(x)(c6 c5 c0)g2=1g3=1节拍m p0p1p2c G1G2关系123410100 0 01 0 11 1 10 1 110101 01 01 01 0p0=m+p2p1=p0p2=p0+p15670001 0 00 1 00 0 10010 10 10 1p0=0 p1=p0p2=p1结论：m=1010，c=1010001第78页，本讲稿共107页9、BCH码和RS码 BCH码是纠错能力可控的纠随机差错码，是码是纠错能力可控的纠随机差错码，是循环码的子类循环码的子类。该码。该码有严格的代数结构，生成多项式有严格的代数结构，生成多项式g(x)与最小距离与最小距离d有密切关系，使设有密切关系，使设计者可以根据对计者可以根据对d的要求，轻易地构造出具有预定纠错能力的码。的要求，轻易地构造出具有预定纠错能力的码。BCH编、译码电路比较简单，易于工程实现，在编、译码电路比较简单，易于工程实现，在中、短码长情况中、短码长情况下的性能接近理论最佳值下的性能接近理论最佳值。因此。因此BCH码不仅在编码理论上占有重要地位，码不仅在编码理论上占有重要地位，而且也是实际使用最广泛的码之一而且也是实际使用最广泛的码之一 Bose Chandhari BCH HocquenghemBCH码最初是定义在码最初是定义在GF(2)域上的二进制码，后被推广到多元域域上的二进制码，后被推广到多元域GF(q)上。上。第79页，本讲稿共107页（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,qn第80页，本讲稿共107页（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页（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=2 4+2 2+2=0;据近世代数理论，幂次为据近世代数理论，幂次为m的多项式，必有的多项式，必有m个根。个根。如：如：本原多项式本原多项式p(x)=x3+x+1产生的二元扩域为产生的二元扩域为GF(23)，本原元本原元 为其中的一个根，为其中的一个根，p()=3+1=0而而 、3、5不是它的根；当然不是它的根；当然0和和1也不是它的根。也不是它的根。第82页，本讲稿共107页 、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页实际上实际上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,4 x3+x2+1在扩域上的在扩域上的3个根为个根为 3,5,6每一个根都对应于一个最小多项式每一个根都对应于一个最小多项式(6)BCH码码用用xn+1 在其本原多项式定义的扩域在其本原多项式定义的扩域GF(2m)上的上的2t个连续幂次的个连续幂次的根根 ,2,2t 所对应的最小多项式所对应的最小多项式mi(x)的最小公倍式作为生的最小公倍式作为生成多项式生成的循环码。成多项式生成的循环码。(t为纠错能力为纠错能力)纠错能力可控纠错能力可控第84页，本讲稿共107页总结：总结：本原本原BCHBCH码构造法码构造法由关系式由关系式n=2n=2m m-1-1算出算出m，查表，找到一个，查表，找到一个m m次本原多项式次本原多项式P(x)P(x)，产生一，产生一个个GF(2GF(2m m)扩域。扩域。在在GF(2GF(2m m)上找一个本原元上找一个本原元，分别计算，分别计算2 2t t个连续幂次根个连续幂次根、2 2、2 2t t所对应的所对应的GF(2)GF(2)域上的最小多项式域上的最小多项式m m1 1(x)(x)、m m2 2(x)m(x)m2t2t(x)(x)。m m 8 8时连续时连续幂次根幂次根 i i所对应的最小多项式见表。所对应的最小多项式见表。计算这些最小多项式的最小公倍式，得到生成多项式计算这些最小多项式的最小公倍式，得到生成多项式g g(x x)g g(x x)=LCM)=LCMm m1 1(x x)m m2 2(x x)m m2 2t t(x x)由关系式由关系式C(x)=m(x)g(x)C(x)=m(x)g(x)求求BCHBCH码字。码字。例题例题6-8 设计一个码长设计一个码长n=7的二元本原的二元本原BCH码，在不同纠错能码，在不同纠错能力力下的生成多项式是怎样的？下的生成多项式是怎样的？第85页，本讲稿共107页解：解：n=7 m=3查表：查表：m=13(8进制表示，即进制表示，即001011）；）；本原多项式为本原多项式为p(x)=x3+x+1 dminn=2n=2m m-1 t (-1 t (dmin-)/2=2-)/2=2m-1m-1-1=3-1=3分别计算分别计算2t2t个连续幂次的根对应的最小多项式：个连续幂次的根对应的最小多项式：t=1,2t=2;2t=1,2t=2;2个连续幂次的根个连续幂次的根 ,2 (x3+x+1),2 (x3+x+1)g(x)=x3+x+1 生成生成(7,4)码。码。t=2,2t=4;4t=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=3t=3，结果同上，结果同上第86页，本讲稿共107页(6)RS码码 -多进制多进制BCH码码RS-Reed-Solomon 里德里德-索洛蒙码，索洛蒙码，BCH码最重要的一个子码最重要的一个子类类符号集由本原多项式产生的扩域符号集由本原多项式产生的扩域GF(2m)中的元素构成。中的元素构成。BCHBCH码码二元域：二元域：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个连续幂次的根对应的最小个连续幂次的根对应的最小 多项式的最小公倍式。多项式的最小公倍式。RSRS码码二元域：二元域：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页总复习（二）l信息、消息、信号的定义是什么？三者的关系是什么？l什么样的马尔可夫链是遍历的？l简述离散信源的最大熵定理。l简述信息率失真函数的物理意义。l叙述变长信源编码定理。l惟一可译码存在的充要条件是什么？l什么是差错图样？有哪些差错图样类型？l什么是本原多项式？l对于信道编码，有哪两种译码算法？简述之。l为什么说BSC信道的最小距离译码就是最大似然译码？l什么是完备吗？举出两种完备吗的例子。l写出卷积码的解析表达式。说明为什么称之为卷积码？第88页，本讲稿共107页设在一只布袋中装有100个大小相同的乒乓球，（1）若红色球和白色球各50个，从中随机取出一个球，问猜测其颜色需要的信息量是多少？（2）若红色球99个，白色球1个，从中随机取出一个球，猜测其颜色需要的信息量又是多少？某信道为强对称信道（即均匀信道）输入符号和输出符号的个数均为m，正确的传输概率为1,错误概率为被对称的均匀分给m1个输出符号，试写出转移概率矩阵及其信道容量的表达式。第89页，本讲稿共107页一个平均功率受限的连续信道，其通频带为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页卷积码convolutional code发展1955年，埃里亚斯(Elias)提出卷积码1957年，伍成克拉夫特(Wozencraft)提出序列译码1963年，梅西(Massey)提出门限译码1967年，维特比(Viterbi)提出最大似然译码优点简单、性能好主要应用FEC（前向纠错）系统，纠错6.4 卷积码6.4.1 卷积码概述第91页，本讲稿共107页特点输出的n个码元中，每个码元不仅与本段的k比特信息码元有关，而且还与前m 段的信息码元有关记作(n,k,m)n、k较小，m较大(m10)参数码率k/n记忆长度m有效工作的移存器段数编码约束度N=m+1 相互关联的码段个数编码约束长度Nn 相互关联的码元个数第92页，本讲稿共107页编码输出编码输出每次输入每次输入k比特比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每