第6章信道编码

《第6章信道编码》由会员分享，可在线阅读，更多相关《第6章信道编码（111页珍藏版）》请在金锄头文库上搜索。

1、第第6章章信道编码信道编码信道编码信道编码是以信息在信道上的正确传输为目是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：标的编码，可分为两个层次上的问题：n n如何正确接收载有信息的信号如何正确接收载有信息的信号线路编码线路编码n n如何避免少量差错信号对信息内容的影响如何避免少量差错信号对信息内容的影响纠错编码纠错编码芝档法哟图锹慌慈例根摩岔熔妒优纂育琴苯辛氧茅惶星量捅说迈拙日蕴祭第6章信道编码第6章信道编码1普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著本章内容本章内容n n有扰离散信道的编码定理有扰离散信道的编码定理n n纠错编译码的基本原理与分析方法纠错编

2、译码的基本原理与分析方法n n线性分组码线性分组码n n卷积码卷积码n n编码与调制的结合编码与调制的结合TCM码码n n运用级联、分集与信息迭代概念的纠错码运用级联、分集与信息迭代概念的纠错码鲁韶慢利蛰胁律快缮亭称伴抠榨喻卞鹤璃牛税借轴逝烫酌拨舔抓否葛蹦尝第6章信道编码第6章信道编码2普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1 有扰离散信道的编码定理有扰离散信道的编码定理n n差错和差错控制系统分类差错和差错控制系统分类n n矢量空间与码空间矢量空间与码空间n n随机编码随机编码n n信道编码定理信道编码定理肩录醒开夫篡屈暖需子身掂尼茹谈撩钱嫌耙趋蛰纂答肌兴萎络讼汝犀

3、余盔第6章信道编码第6章信道编码3普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错类型差错类型n n差错符号差错符号：由符号发生差错引起，也叫：由符号发生差错引起，也叫信信号差错号差错，信号差错概率用，信号差错概率用误码元率误码元率表示表示n n差错比特差错比特：由信息比特发生差错引起，也：由信息比特发生差错引起，也叫叫信息差错信息差错，信息差错概率用，信息差错概率用误比特率误比特率表表示示n n对于对于二进制二进制传输系统，符号差错等效于比传输系统，符号差错等效于比特差错；特差错；n n对于对于多进制多进制系统，一个符号差错到底对应系统，一个符号差错到底对应多少比特差错却难以

4、确定。因为一个符号多少比特差错却难以确定。因为一个符号由多个比特组成。由多个比特组成。梨鄙服祷定取芯七聚愿媒灶录缘屯昂害烂恤徐纪茁滇私斧魏委连训尊缠赔第6章信道编码第6章信道编码4普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错图样（差错图样（errorpattern）n n定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之“ “差差差差” ”：差错图样差错图样差错图样差错图样E E发码发码发码发码C C 收码收码收码收码R R （模（模（模（模MM） n n例：例：例：例：8 8进制进制进制进制(M

5、=8)(M=8)码元，码元，码元，码元，若发码若发码若发码若发码 C=C=（0,2,5,4,7,5,20,2,5,4,7,5,2）收码变为收码变为收码变为收码变为 R=R=（0,1,5,4,7,5,40,1,5,4,7,5,4）差错图样差错图样差错图样差错图样 E E= =C CR R= =（0,1,0,0,0,0,60,1,0,0,0,0,6）（模）（模）（模）（模8 8）n n二进制码：二进制码：二进制码：二进制码：E=C E=C R R 或或或或 C = R C = R E E ，差错图样中，差错图样中，差错图样中，差错图样中的的的的“ “” ”既是符号差错也是比特差错，差错的个既是符号

6、差错也是比特差错，差错的个既是符号差错也是比特差错，差错的个既是符号差错也是比特差错，差错的个数叫汉明距离。数叫汉明距离。数叫汉明距离。数叫汉明距离。 菊偿各嗅裹咳活哟么翅苫沥弧约详君讨驾肩簇控耕胖堡西邓肤酣触未耙邮第6章信道编码第6章信道编码5普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错图样类型差错图样类型n n随机差错随机差错：若差错图样上各码位的取值既：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码终以相等的概率独立发生于各码字、各码元、各比特；元、各比特；n n突发差错：突发差错

7、：前后相关、成堆出现。突发差前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。差错概率超过了某个额定值。扰啼姆渝次护参匿拄朋肾项级藕遵邱涕经揖难逼俱堑败扭宫住镶酋兰腾统第6章信道编码第6章信道编码6普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著纠错码分类纠错码分类n n从功能角度从功能角度：检错码：检错码、纠错码、纠错码n n对信息序列的处理方法对信息序列的处理方法：分组码、卷积码：分组码、卷积码n n码元与原始信息位的关系码元与原

8、始信息位的关系：线性码、非线：线性码、非线性码性码n n差错类型差错类型：纠随机差错码、纠突发差错码、：纠随机差错码、纠突发差错码、介于中间的纠随机介于中间的纠随机/突发差错码。突发差错码。n n构码理论构码理论：代数码、几何码、算术码、组：代数码、几何码、算术码、组合码等合码等允郊茨疫劲腋譬龚铬望颂意总批佣星石席愉陌吨吸对敌士岔娱乃栖继痒萎第6章信道编码第6章信道编码7普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错控制系统分类差错控制系统分类n n前向纠错（前向纠错（FEC）：发端信息经纠错编码：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递后传送，收端通过纠错译码

9、自动纠正传递过程中的差错过程中的差错n n反馈重发（反馈重发（ARQ）：）：收端通过检测接收码收端通过检测接收码是否符合编码规律来判断，如判定码组有是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码错，则通过反向信道通知发端重发该码n n混合纠错（混合纠错（HEC）：）：前向纠错和反馈重发前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两的结合，发端发送的码兼有检错和纠错两种能力种能力甘瞧花废空蝎挑派牛恢洱孽闪枪捆礁汹武宙缸抵量智歪臭枕瘸椎葬晰镍晨第6章信道编码第6章信道编码8普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.2矢量空间与码空间矢量空间

10、与码空间n nF F表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，F F代表二元域代表二元域代表二元域代表二元域0,10,1n n设设设设n n重有序元素的集合重有序元素的集合重有序元素的集合重有序元素的集合V=V=V Vi i ,n n若满足条件：若满足条件：若满足条件：若满足条件：n nV V中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；n nV V中矢量元素与数域中矢量元素与数域中矢量元素与数域中矢量元素与数域

11、F F元素的标乘封闭在元素的标乘封闭在元素的标乘封闭在元素的标乘封闭在V V中；中；中；中；n n分配律、结合律成立，分配律、结合律成立，分配律、结合律成立，分配律、结合律成立，则称集合则称集合则称集合则称集合V V是数域是数域是数域是数域F F上的上的上的上的n n维维维维矢量空间矢量空间矢量空间矢量空间，或称，或称，或称，或称n n维维维维线性空间线性空间线性空间线性空间，n n维矢量又称维矢量又称维矢量又称维矢量又称n n重重重重( (n n-tuples)-tuples)。乖缉殿码秀磷瞥斩弱堆囱荣梢谢止吵毛橙侈殴镰昨纹虽斡节巫稿浙沦氨姓第6章信道编码第6章信道编码9普通高等教育“十五”

12、国家级规划教材信息论与编码 曹雪虹等编著矢量空间中矢量的关系矢量空间中矢量的关系对于域对于域对于域对于域F F上的若干矢量上的若干矢量上的若干矢量上的若干矢量n n线性组合线性组合线性组合线性组合：n n线性相关线性相关线性相关线性相关：其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合n n线性无关线性无关线性无关线性无关或或或或线性独立线性独立线性独立线性独立：一组矢量中的任意一个都：一组矢量中的任意一个都：一组矢量中的任意一个都：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。不

13、可能用其它矢量的线性组合来代替。不可能用其它矢量的线性组合来代替。不可能用其它矢量的线性组合来代替。煞词葱爹仅除你逊药攀酝刘悦门根构际灰环雀榔厚玫傅掖硒膳莎写喷版推第6章信道编码第6章信道编码10普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著矢量空间与基底矢量空间与基底n n一组线性无关的矢量一组线性无关的矢量，线性组合的，线性组合的集合集合就构成了一个就构成了一个矢量空间矢量空间V，这组矢量，这组矢量就是这个矢量空间的就是这个矢量空间的基底基底。n nn维矢量空间应包含维矢量空间应包含n个基底个基底n n基底不是唯一的基底不是唯一的，例：线性无关的两个矢，例：线性无关的两个矢量

14、（量（1,0）和（）和（0,1）以及（）以及（-1,0）和（）和（0,-1）可张成同一个两维空间可张成同一个两维空间。暑狮辆遮没毖缸棱逗毗方萨鞋桐笋惯蜀粪怒显涵谅粳盏橡晴哥该哥唤邱咱第6章信道编码第6章信道编码11普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著二元域二元域GF(2)上三重矢量空间上三重矢量空间n n以（以（以（以（100100）为基底可张成）为基底可张成）为基底可张成）为基底可张成一维三重一维三重一维三重一维三重子空间子空间子空间子空间V V1 1，含，含，含，含2 21 1=2=2个元素，即个元素，即个元素，即个元素，即n n以以以以(010)(001)(010

15、)(001)为基底可张成为基底可张成为基底可张成为基底可张成二维三重二维三重二维三重二维三重子空间子空间子空间子空间V V2 2，含含含含2 22 2=4=4个元素，即个元素，即个元素，即个元素，即n n以以以以(100)(010)(001)(100)(010)(001)为基底可张成为基底可张成为基底可张成为基底可张成三维三重三维三重三维三重三维三重空间空间空间空间V,V,含含含含2 23 3=8=8个元素，个元素，个元素，个元素，V V1 1和和和和V V2 2都是都是都是都是V V的子空间。的子空间。的子空间。的子空间。裁衣垮叮谬挺夜凄沸获何脉深码椅智割积贺学酥憾隘涅顿胆痞咀赠讨郝丁第6章

16、信道编码第6章信道编码12普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著矢量空间矢量空间n n每个矢量空间或子空间中必然包含零矢量每个矢量空间或子空间中必然包含零矢量n n两个两个矢量正交矢量正交：V1 V20n n两个两个矢量空间正交矢量空间正交：某矢量空间中的任意：某矢量空间中的任意元素与另一矢量空间中的任意元素正交元素与另一矢量空间中的任意元素正交n n正交的两个子空间正交的两个子空间V1、V2互为互为对偶空间对偶空间(DualSpace)，其中一个空间是另一个空间，其中一个空间是另一个空间的的零空间零空间（nullspace，也称零化空间）。，也称零化空间）。熬绚重镭说垛

17、阜酉家裙倔寻落晨庸欣拦搞继渍吩懒舆距泊瑰亡十锣欠末巳第6章信道编码第6章信道编码13普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著码空间码空间消息消息k长长(n , k)码码字字n长长 qk种种分组编码器分组编码器qn种种k维维k重矢量重矢量n维维n重矢量重矢量通常通常qnqk，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn种可能组合种可能组合中选择其中的中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。里畸辈否扭察孪弘厩亨皑窍圈馆渔唱瑶榨酒沈迸枫佯它离营孝览闺君忠组第6章信道编码第6章信道编码14普通

18、高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著分组编码的任务分组编码的任务n n选择一个选择一个维维n重子空间作为码空间。重子空间作为码空间。n n确定由确定由k维维k重信息空间到重信息空间到维维n重码空间的重码空间的映射方法。映射方法。码空间的不同码空间的不同选择方法，以及信息组与选择方法，以及信息组与码组的不同映射算法，就构成了不同的分码组的不同映射算法，就构成了不同的分组码。组码。贮滞频利纹邵郁疏靖供引活秦凶鞭孕烂万哟啦诀忌倦谅蒂茹货贮谁狱里垣第6章信道编码第6章信道编码15普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n运用概率统计

19、方法在特定信道条件下对编运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的率的上下限边界，其中最优码所能达到的差错概率上界称作差错概率上界称作随机码界随机码界。n n用这种方法不能得知最优码是如何具体编用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论理，对指导编码技术具有特别重要的理论价值。价值。卯秆惦野学跳署码邓潦泊秆篱剁忌斡按斩区噶

20、褪业罚拣拴邀客埠这茨痊讶第6章信道编码第6章信道编码16普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n在在在在(N,K)(N,K)分组编码器中随机选定的码集有分组编码器中随机选定的码集有分组编码器中随机选定的码集有分组编码器中随机选定的码集有q qNMNM种种种种 n n第第第第mm个码集个码集个码集个码集( (记作记作记作记作ccmm) )被随机选中的概率是被随机选中的概率是被随机选中的概率是被随机选中的概率是n n设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概

21、率是P Pe e(c(cmm) )n n全部码集的平均差错概率是全部码集的平均差错概率是全部码集的平均差错概率是全部码集的平均差错概率是开蚌部蛔沮君拆镶蚊墨匀掐缮咒奇乓咐赞痢谣懒丈诡莱琴抡鸦名泞惠局败第6章信道编码第6章信道编码17普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n必定存在某些码集必定存在某些码集必定存在某些码集必定存在某些码集n n某些码集某些码集某些码集某些码集n n若若若若，就必然存在一批码集，就必然存在一批码集，就必然存在一批码集，就必然存在一批码集即差错概率趋于零的好码一定存在即差错概率趋于零的好码一定存在即差错概率趋于零的好

22、码一定存在即差错概率趋于零的好码一定存在 筹捂窄硅乃俗铆挽瓣袋畸所寅瓷痰甜浇角册禾锯材酋们何芍沥浆殿育绊被第6章信道编码第6章信道编码18普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n码集点数码集点数码集点数码集点数MM= =q qK K占占占占N N维矢量空间总点数维矢量空间总点数维矢量空间总点数维矢量空间总点数q qN N的比例是的比例是的比例是的比例是F F = =q qK K / q / qN N =q q- -( (N-KN-K) )n n当当当当K K和和和和N N的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增加时，平

23、的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。 n n当当当当F F0 0即即即即( (N-KN-K) )时，能否让平均差错概率时，能否让平均差错概率时，能否让平均差错概率时，能否让平均差错概率？ n nGallagerGallager在在在在19651965年推导了年推导了年推导了年

24、推导了的上边界，并证明这的上边界，并证明这的上边界，并证明这的上边界，并证明这个上边界是按指数规律收敛的。个上边界是按指数规律收敛的。个上边界是按指数规律收敛的。个上边界是按指数规律收敛的。 槐允佣傅躬腾峻脚驴捕褥涤掂惑酗腾仁浴打炙亿图嗡曾俱越壁邢蹦坏樟科第6章信道编码第6章信道编码19普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n nE(R)为为可靠性函数可靠性函数，也叫误差指数，也叫误差指数n n码率码率：R =(lbM) /Nn nMM是可能的信息组合数，是可能的信息组合数，是可能的信息组合数，是可能的信息组合数，MM= =q qK Kn nN N是每码字的码元数，是每码

25、字的码元数，是每码字的码元数，是每码字的码元数，n nR R表示每码元携带的信息量，单位是每符号比表示每码元携带的信息量，单位是每符号比表示每码元携带的信息量，单位是每符号比表示每码元携带的信息量，单位是每符号比特（特（特（特（bit/symbolbit/symbol） 6.1.4信道编码定理信道编码定理勿共侠涂倪茸跃菌骡抖黔澜侄憾泻猎书涉始慎徒标黎割瞒目伸僳六刚残墓第6章信道编码第6章信道编码20普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n nR R在在在在0,0,R R0 0 区间时区间时区间时区间时E E( (R R)R R曲线是斜率为曲线是斜率为曲线是斜率为曲线是斜率

26、为-1-1（-45-45 ）的直线，）的直线，）的直线，）的直线，E E( (R R) )反反反反比于比于比于比于R R；而当；而当；而当；而当R R= =C C时时时时E E( (R R)=0)=0即可靠即可靠即可靠即可靠性为零。性为零。性为零。性为零。 E(R) C R0R0-45 E(R)和和R的关系曲线的关系曲线6.1.4信道编码定理信道编码定理栏没惨禁祸呵已胚绿胜诺茂凰冯咨纽购拽怨嫌俗金开馆那蛤鸳敛卫字颊逐第6章信道编码第6章信道编码21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n正定理正定理：只要传信率：只要传信率R小于信道容量小于信道容量C，总，总存在一种信

27、道码（及解码器），可以以所存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。要求的任意小的差错概率实现可靠的通信。n n逆定理逆定理：信道容量：信道容量C是可靠通信系统传信率是可靠通信系统传信率R的上边界，如果的上边界，如果R C，就不可能有任何一，就不可能有任何一种编码能使差错概率任意小。种编码能使差错概率任意小。6.1.4信道编码定理信道编码定理抚援僳槐哺没弛映笆昔同择病讳波逊想坡薛雕闪号记棚玻跑蛙莫鼎册街逮第6章信道编码第6章信道编码22普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2纠错编译码的基本原理与分析纠错编译码的基本原理与分析n n纠错

28、编码的基本思路纠错编码的基本思路n n译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码猜顽猿椅歇眨家髓熔踪嚏锚然咆憎湍栈奸狰浚夯锣盖暇牡凰挣准逸第屎酋第6章信道编码第6章信道编码23普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2.1纠错编码的基本思路纠错编码的基本思路n nR R不变不变不变不变，信道容量大者，信道容量大者，信道容量大者，信道容量大者其可靠性函数其可靠性函数其可靠性函数其可靠性函数E E( (R R) )也也也也大；大；大；大；n nC C不变不变不变不变，码率减小时其，码率减小时其，码率减小时其，码率减小时其可靠性函数可靠性函数可靠性函数可靠性

29、函数E E( (R R) )增大增大增大增大 E(R)R0R1R2 C1 C2增大增大E(R)的途径的途径砍敦磐痛爽钧虞喜刚鹤惯当徐钾翰脯认卤辙触剩冯涛棘祈块慌茹猖襄懂招第6章信道编码第6章信道编码24普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2.1纠错编码的基本思路纠错编码的基本思路n n增大信道容量增大信道容量Cn n扩展带宽扩展带宽扩展带宽扩展带宽n n加大功率加大功率加大功率加大功率n n降低噪声降低噪声降低噪声降低噪声n n减小码率减小码率Rn nQ Q、N N不变而减小不变而减小不变而减小不变而减小K K n nQ Q、K K不变而增大不变而增大不变而增大不变

30、而增大N Nn nN N、K K不变而减小不变而减小不变而减小不变而减小Q Qn n增大码长增大码长N苑九顿赫露源昧吕貌彼纤训予跌颐右赤犹傣怔祁鸡闷广攀裹聪趟喇那驴栓第6章信道编码第6章信道编码25普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2.2最优译码与最大似然译码最优译码与最大似然译码n n译码器的任务译码器的任务是从受损的信息序列中是从受损的信息序列中尽可能正确地恢复出原信息。尽可能正确地恢复出原信息。n n译码算法的已知条件是：译码算法的已知条件是：n n实际实际接收到的码字序列接收到的码字序列r,r=(r1,r2,rN)n n发端所采用的编码算法和该算法产生的发

31、端所采用的编码算法和该算法产生的码集码集XN,满足满足n n信道模型及信道参数。信道模型及信道参数。侥奠隆肛龚狱甸屯湃可钓雷兹昌烙枚刀太喝阂馆停儒架溃鹰展丈衷选辗枫第6章信道编码第6章信道编码26普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n最佳译码最佳译码，也叫最大后验概率译码，也叫最大后验概率译码(MAP)n n最大似然译码最大似然译码(MLD)6.2.2最优译码与最大似然译码最优译码与最大似然译码消息组消息组mi码字码字ci接收码接收码r估值估值 消息消息编码器编码器 信道信道 译码译码 消息还原消息还原冗氧槽斧厄赶放追瞪泼噬惑患靛欠渠垄柳尤齐验应菜棺谱酉薯脖军乳梦镍

32、第6章信道编码第6章信道编码27普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n如果如果n n构成码集的构成码集的构成码集的构成码集的2 2KK个码字以相同概率发送，满足个码字以相同概率发送，满足个码字以相同概率发送，满足个码字以相同概率发送，满足P P( (c ci i)=1/2)=1/2KK ， i i=1,2,2=1,2,2KKn nP P( (r r) )对于任何对于任何对于任何对于任何r r都有相同的值，满足都有相同的值，满足都有相同的值，满足都有相同的值，满足P P( (r r)=1/2)=1/2KK n n则则P(ci/r)最大等效于最大等效于P(r/ci)的最

33、大，在此的最大，在此前提下最佳译码等效于最大似然译码。前提下最佳译码等效于最大似然译码。6.2.2最优译码与最大似然译码最优译码与最大似然译码旱卑芝俱议鹏欧叙敝叮京嫁止契徐剂胡巷括妊副甚喊拳堕迢嘉票幽封猛驭第6章信道编码第6章信道编码28普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n对于无记忆信道，对于无记忆信道，n n例：例：BSC信道的最大似然译码可以简化为信道的最大似然译码可以简化为最最小汉明距离译码小汉明距离译码。n n汉明距离译码是一种硬判决译码。由于汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等信道是对称的，只要发送的码字独立、等概

34、，汉明距离译码也就是最佳译码。概，汉明距离译码也就是最佳译码。6.2.2最优译码与最大似然译码最优译码与最大似然译码醛泽准嘿巫司亮逮游毕引扒饶余蓄袋塌匙灭箩刺辑掇蕊蔚种甲钝诚黑蕾削第6章信道编码第6章信道编码29普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3线性分组码线性分组码消息消息m(n , k)码字码字c m=(mk-1,m1,m0) 分分 组组 编编 码码 器器 c=(cn-1,c1,c0)qk qnn n码集码集码集码集C C能否构成能否构成能否构成能否构成n n维维维维n n重矢量空间的一个重矢量空间的一个重矢量空间的一个重矢量空间的一个k k维维维维n n重子

35、空间？重子空间？重子空间？重子空间？n n如何寻找最佳的码空间？如何寻找最佳的码空间？如何寻找最佳的码空间？如何寻找最佳的码空间？n nq qk k个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。n n码率编码效率：码率编码效率：码率编码效率：码率编码效率：R Rc c = =k k/ /n n 瞅碳逢在绵峪邹预幕透蚌严奸肯妈赋氯依厕巴婪摇画悦容兼系党钡浊可靛第6章信道编码第6章信道编码30普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3.1生成矩阵和校验矩

36、阵生成矩阵和校验矩阵cmG1n1kkn码字码字消息消息生成矩阵生成矩阵Ggk-1g1g0T，有，有k个个(1n)行行矢量，如何选择呢？矢量，如何选择呢？骡伦阎嘴汗验鳖繁遥宇峦栏贿硷俗滁钞刨丝钮侍掠韭洞办坡啪箕淮话寒夺第6章信道编码第6章信道编码31普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著线性分组码的形成线性分组码的形成c=c= m mk k-1-1 g gk k-1-1+ m m1 1 g g1 1+ +m m00g g0 0 n n码码码码空空空空间间间间的的的的所所所所有有有有元元元元素素素素（即即即即码码码码字字字字）都都都都可可可可以以以以写写写写成成成成k k个个

37、个个基基基基底底底底的线性组合的线性组合的线性组合的线性组合n n由由由由于于于于k k个个个个基基基基底底底底即即即即GG的的的的k k个个个个行行行行矢矢矢矢量量量量线线线线性性性性无无无无关关关关，矩矩矩矩阵阵阵阵GG的的的的秩一定等于秩一定等于秩一定等于秩一定等于k k。n n当当当当信信信信息息息息元元元元确确确确定定定定后后后后，码码码码字字字字仅仅仅仅由由由由GG矩矩矩矩阵阵阵阵决决决决定定定定，因因因因此此此此我我我我们们们们称称称称这这这这k k n n 矩矩矩矩阵阵阵阵GG为为为为该该该该( (n,kn,k) )线线线线性性性性分分分分组组组组码码码码的的的的生生生生成成成

38、成矩矩矩矩阵。阵。阵。阵。 扼缩毁糜蔑二膀喻莫畜版狸以继蹦涎魂鞠斯匀激忆痘灼侥砂郊巳迈辨护默第6章信道编码第6章信道编码32普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著生成矩阵生成矩阵G(kn)的特点的特点n n想要保证想要保证(n,k)线性分组码能够构成线性分组码能够构成k维维n重子空间，重子空间，G的的k个行矢量个行矢量g gk k-1-1,g,g1 1,g,g0 0必必须是线性无关的，只有这样才符合作为基须是线性无关的，只有这样才符合作为基底的条件。底的条件。n n由于基底不是唯一的，所以由于基底不是唯一的，所以G也就不是唯一也就不是唯一的。的。n n不同的基底有可能生成

39、同一码集，但因编不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。映射方法不同也不能说是同样的码。草痰媚垢菲屈鱼茸鹏缔腾服代标贡岛沛市情怔灯左蹄沛凰菲玉渴骡丛剿雹第6章信道编码第6章信道编码33普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著系统形式的生成矩阵系统形式的生成矩阵(n,kn,k) )码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算（以及列置换）简化成（以及列置换）简化成（以及列置换）简化成（以及列置换

40、）简化成“ “系统形式系统形式系统形式系统形式” ”。G=IG=Ik k P=P=I Ik k是是是是kkkk单位矩阵，单位矩阵，单位矩阵，单位矩阵，P P是是是是k k(n-kn-k) )矩阵。矩阵。矩阵。矩阵。 壕怜搏族植目晒黄澜年租距降濒誓柔钧是号税氯龄涧谐厘丹崭庇臻酗搏醋第6章信道编码第6章信道编码34普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著生成的码字生成的码字Cn n前前前前k k位由单位矩阵位由单位矩阵位由单位矩阵位由单位矩阵I Ik k决定，等于把信息组决定，等于把信息组决定，等于把信息组决定，等于把信息组mm原封不原封不原封不原封不动搬到码字的前动搬到码字的

41、前动搬到码字的前动搬到码字的前k k位；位；位；位；n n其余的其余的其余的其余的n-kn-k位叫冗余位或位叫冗余位或位叫冗余位或位叫冗余位或一致校验位一致校验位一致校验位一致校验位，是前，是前，是前，是前k k个信个信个信个信息位的线性组合。息位的线性组合。息位的线性组合。息位的线性组合。n n这样生成的（这样生成的（这样生成的（这样生成的（n,kn,k）码叫做）码叫做）码叫做）码叫做系统码系统码系统码系统码。n n若生成矩阵若生成矩阵若生成矩阵若生成矩阵GG不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做非系统码非系统

42、码非系统码非系统码。n n系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。 祁诌润担攘颊晦胶鲤馒棺同宅孪岂忱捡笛串怯仟霖瘴够猎恋刹浸仇屯垒络第6章信道编码第6章信道编码35普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著系统码系统码n n若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵GG互等，互等，互等，互等，则称这两个则称这两个则称这两个则称这两个GG等效等效等效等效。n n非系统

43、码的非系统码的非系统码的非系统码的GG可通过运算转变为系统码的可通过运算转变为系统码的可通过运算转变为系统码的可通过运算转变为系统码的GG。n n等效的两个等效的两个等效的两个等效的两个GG生成的两个生成的两个生成的两个生成的两个( (n,kn,k) )线性码也是等效的。线性码也是等效的。线性码也是等效的。线性码也是等效的。n n因此，每个因此，每个因此，每个因此，每个( (n,kn,k) )线性码都可以和一个系统的线性码都可以和一个系统的线性码都可以和一个系统的线性码都可以和一个系统的( (n,kn,k) )线性码等效。线性码等效。线性码等效。线性码等效。 过菏捻逗锅疆诞匪颖玻馏双寞梁楷殆舌

44、靳闺污堪咒页养苫嵌巧矫画彰眶椰第6章信道编码第6章信道编码36普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著空间构成空间构成n nn n维维维维n n重空间有相互重空间有相互重空间有相互重空间有相互正交的正交的正交的正交的n n个基底个基底个基底个基底n n选择选择选择选择k k个基底构成码个基底构成码个基底构成码个基底构成码空间空间空间空间C Cn n选择另外的选择另外的选择另外的选择另外的( (n n- -k k) )个个个个基底构成空间基底构成空间基底构成空间基底构成空间HHn nC C和和和和HH是对偶的是对偶的是对偶的是对偶的CHCHT T0,GH0,GHT T=0=0

45、n维维n重空间重空间Vk维维k重重k维维n重重n-k维维信息组信息组码空间码空间n重重H空间空间mC衅猛懈俯郎晒札壕枷全鹏镜军施仪瓜火运棠灯残询夕陆役掺虹趋被搭黔哈第6章信道编码第6章信道编码37普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著校验矩阵校验矩阵n n将将将将HH空空空空间间间间的的的的n-kn-k个个个个基基基基底底底底排排排排列列列列起起起起来来来来可可可可构构构构成成成成一一一一个个个个( (n-n-k k) ) n n矩矩矩矩阵阵阵阵，称称称称为为为为校校校校验验验验矩矩矩矩阵阵阵阵HH。用用用用来来来来校校校校验验验验接接接接收收收收到到到到的码字是否是正确

46、的；的码字是否是正确的；的码字是否是正确的；的码字是否是正确的；n nGG是是是是( (n,kn,k) )码的生成矩阵，码的生成矩阵，码的生成矩阵，码的生成矩阵，HH是它的校验矩阵；是它的校验矩阵；是它的校验矩阵；是它的校验矩阵；n nHH是是是是( (n,n-kn,n-k) )对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是一个基底。一个基底。一个基底。一个基底。GG则是它的校验矩阵。则是它的校验矩阵。则是它的校验矩阵。则是它的校验矩阵。n nGHGHT T=0=0，HH PPT TI In-kn-k ，二进制时，负号，

47、二进制时，负号，二进制时，负号，二进制时，负号可省略。可省略。可省略。可省略。矾枝稠洒镜玻渤良牧阜韭冈过廊航续侯周城功碍磨讨茵杨几札绅杖歇啦师第6章信道编码第6章信道编码38普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n例例6-2(6,3)线性分组码，其生成矩阵是线性分组码，其生成矩阵是G=求：求：(1)(1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。(2)(2)将该码系统化处理后，计算系统码码集并列出将该码系统化处理后，计算系统码码集并列出将该码系统化处理后，计算

48、系统码码集并列出将该码系统化处理后，计算系统码码集并列出映射关系。映射关系。映射关系。映射关系。(3)(3)计算系统码的校验矩阵计算系统码的校验矩阵计算系统码的校验矩阵计算系统码的校验矩阵HH。若收码。若收码。若收码。若收码r=100110,r=100110,检验它是否码字？检验它是否码字？检验它是否码字？检验它是否码字？ (4)(4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。111010110001011101垃味轨珐疮勾驯燕凑鞘籽盎帆锑拳暑猛勺雄龋啥佃紊扮黔逐鹊搀赐铂囱谬第6章信道

49、编码第6章信道编码39普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6-2码集与映射关系码集与映射关系信息码字系统码字000000000000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010们吐殴蚁终需栏喷代惩俄腹黎铝莆宅童毫剔妇和鹰谰埋战隘馈厌吠株涎酝第6章信道编码第6章信道编码40普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6-2二元二元(6,3)线性分组码编码器线性分组码编码器 m0m

50、1m2输入输出 c0c1c2舌案撞笔完膏员雪悔篮麻替截抖倘喷迫梨坏渔鹤儡袭微沈帽崔榜趾耘鳖途第6章信道编码第6章信道编码41普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3.2伴随式与标准阵列译码伴随式与标准阵列译码mC=(mC=(c cn-n-1 1,c c1 1, ,c c0 0)R=()R=(r rn-n-1 1,r r1 1, ,r r0 0) )(n,k)信道信道定义定义定义定义差错图案差错图案差错图案差错图案E EEE( (e en n1 1,e e1 1, ,e e0 0) )RRCC( (r rn-n-1 1c cn-n-1 1,r r1 1c c1 1, ,

51、r r0 0c c0 0) )二进制码中模二进制码中模二进制码中模二进制码中模2 2加与模加与模加与模加与模2 2减是等同的，因此有减是等同的，因此有减是等同的，因此有减是等同的，因此有E=RE=RCC及及及及R=CR=CEE 禾迪为熄瓦棒鲸詹挟秋樟甚乐危晃躺血坷昂阂踩率涩聂藉契滚旷卸巢借戏第6章信道编码第6章信道编码42普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著伴随式伴随式S的定义的定义因为因为因为因为CHCHT T=0=0所以所以所以所以RHRHT T(C(CE)HE)HT TCHCHT TEHEHT T=EH=EHT T如果收码无误：必有如果收码无误：必有如果收码无误：

52、必有如果收码无误：必有R RC C即即即即E E0 0，则则则则EHEHT T=0RH=0RHT T=0=0。如果收码有误：即如果收码有误：即如果收码有误：即如果收码有误：即EE 0 0，则则则则RHRHTT=EH=EHT T 0 0。在在HT固定的前提下，固定的前提下，RHT仅仅与差仅仅与差错图案错图案E有关，而与发送码有关，而与发送码C无关。定义无关。定义伴随式伴随式SS=(sn-k-1,s1,s0)=RHT=EHT重哺腾对缨窝哟杭搀陶皂各掏烹阀方纱盲哺蜂疲隘凋百蛛堤驳蒋凯哦衬卷第6章信道编码第6章信道编码43普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n从物理意义上看

53、，伴随式从物理意义上看，伴随式从物理意义上看，伴随式从物理意义上看，伴随式S S并不反映发送的码字是并不反映发送的码字是并不反映发送的码字是并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。n n差错图案差错图案差错图案差错图案E E是是是是n n重矢量，共有重矢量，共有重矢量，共有重矢量，共有2 2n n个可能的组合，而个可能的组合，而个可能的组合，而个可能的组合，而伴随式伴随式伴随式伴随式S S是是是是( (n-kn-k) )重矢量，只有重矢量，只有重矢

54、量，只有重矢量，只有2 2n-kn-k个可能的组合，个可能的组合，个可能的组合，个可能的组合，因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。n n接收端收到接收端收到接收端收到接收端收到R R后，因为已知后，因为已知后，因为已知后，因为已知HHT T，可求出，可求出，可求出，可求出SSRHRHT T；如果能知道对应的如果能知道对应的如果能知道对应的如果能知道对应的E E，则通过，则通过，则通过，则通过C=RC=RE E而求得而求得而求得而求得C C。 RHRHT T=S=S?C=R?C=R

55、EERSECRSEC只要只要只要只要E E正确，译出的码也就是正确的。正确，译出的码也就是正确的。正确，译出的码也就是正确的。正确，译出的码也就是正确的。 伴随式伴随式S的意义的意义犹俞投疙她尊膝像馒哑斟谷涌戍帖刹食秽捉忆蔷惜干纠洁委披爷柑锨呛充第6章信道编码第6章信道编码44普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错图案差错图案E的求解的求解(1)可以通过解线性方程求解可以通过解线性方程求解可以通过解线性方程求解可以通过解线性方程求解E E：S=(S=(s sn-k-n-k-1,s s1,s s0)=EH)=EHT T=(=(e en n-1,e e1,e e0) )得

56、到线性方程组：得到线性方程组：得到线性方程组：得到线性方程组：s sn-k-n-k-1=e en n-1h h(n-k-n-k-1)(n n-1)+e e1h h(n-k-n-k-1)1+ e e0h h(n-k-n-k-1)0 s s1=e en n-1h h1(n n-1)+e e1h h11+ e e0h h10s s0=e en n-1h h0(n n-1)+ e e1h h01+ e e0h h00卷官潍耶铂熊毡杆挚钎竿殊棘乱乃到甫糖歌贫汹城捣弗毫凉衰捏兑狠世融第6章信道编码第6章信道编码45普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n上述方程组中有上述方程组中

57、有上述方程组中有上述方程组中有n n个未知数个未知数个未知数个未知数e en n1, e, e1,e ,e0 ，却，却，却，却只有只有只有只有n-kn-k个方程，可知方程组有多解。个方程，可知方程组有多解。个方程，可知方程组有多解。个方程，可知方程组有多解。n n在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方

58、程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少n-n-( ( n-k n-k)=)=k k个方程导致每个未知数有个方程导致每个未知数有个方程导致每个未知数有个方程导致每个未知数有2 2k k个解。个解。个解。个解。n n因此，由上述方程组解出的因此，由上述方程组解出的因此，由上述方程组解出的因此，由上述方程组解出的E E可以有可以有可以有可以有2 2k k个解。个解。个解。个解。到底取哪一个作为附加在收码到底取哪一个作为附加在收码到底取哪一个作为附加在收码到底取哪一个作为附加在收码R R上的差错图案上的差

59、错图案上的差错图案上的差错图案E E的估值呢？的估值呢？的估值呢？的估值呢？n n概率译码：概率译码：概率译码：概率译码：把所有把所有把所有把所有2 2k k个解的重量个解的重量个解的重量个解的重量( (差错图案差错图案差错图案差错图案E E中中中中1 1的个数的个数的个数的个数) )作比较，选择其中最轻者作为作比较，选择其中最轻者作为作比较，选择其中最轻者作为作比较，选择其中最轻者作为E E的估的估的估的估值。该方法概念上很简单但计算效率不高。值。该方法概念上很简单但计算效率不高。值。该方法概念上很简单但计算效率不高。值。该方法概念上很简单但计算效率不高。差错图案差错图案E的求解的求解(2)

60、紫吏码沟温官糠屁郧槐棒劝棚灌明翘姿淋丫撬车目婿明妆头彩仟痈桔胖惋第6章信道编码第6章信道编码46普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率：0个错个错1个错个错2个错个错n个错个错(1-p)np(1-p)n-1p2(1-p)n-2pn由于由于p出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，的重量越轻，所以该译码方法实际上体现了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。即最大似然译码。祥洒绪嘿秧畴拷拒纠思防吭涌椭蛀

61、砸眠扭贾处宅栏倦藤凿旱由墒喀蔽丰沈第6章信道编码第6章信道编码47普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著标准阵列译码表标准阵列译码表上述的概率译码，如每接收一个码上述的概率译码，如每接收一个码R就要解一次线性方程，那就太麻烦了。就要解一次线性方程，那就太麻烦了。好在伴随式好在伴随式S的数目是有限的的数目是有限的2n-k个，如个，如果果n-k不太大，我们可以预先把不同不太大，我们可以预先把不同S下下的方程组解出来，把各种情况下的最大的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要实时译码

62、时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这象查字典那样查一下码表就可以了。这样构造的表格叫做样构造的表格叫做标准阵列译码表标准阵列译码表。哉间尉缄管晶辕法拳矢蒜骚暴矢炮腋迷届谩沿课锥仓牡寅应芭兜苑诉失痕第6章信道编码第6章信道编码48普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n表中所列码字是接收到的码字表中所列码字是接收到的码字表中所列码字是接收到的码字表中所列码字是接收到的码字R R；n n将没有任何差错时的收码将没有任何差错时的收码将没有任何差错时的收码将没有任何差错时的收码R R放在第一行，收码等于发码放在第一行，收码等于发码放在第一行，收码等于发

63、码放在第一行，收码等于发码R=C(CR=C(C C Ci i, ,i i=0,1,2k k-1),),差错图案为全零差错图案为全零差错图案为全零差错图案为全零E E0 0=(=(0,00) )，伴，伴，伴，伴随式为全零随式为全零随式为全零随式为全零S S0 0=(=(0,00) )。由于有。由于有。由于有。由于有2 2k k个码字，码表有个码字，码表有个码字，码表有个码字，码表有2 2k k列。列。列。列。n n在第在第在第在第2 2到第到第到第到第n n+1+1的的的的n n行中差错图案的所有重量为行中差错图案的所有重量为行中差错图案的所有重量为行中差错图案的所有重量为1(1(共共共共n n

64、个个个个) )。n n如果如果如果如果(1+(1+n n)2)2n-kn-k，再在下面行写出全部带有，再在下面行写出全部带有，再在下面行写出全部带有，再在下面行写出全部带有2 2个差错的图案个差错的图案个差错的图案个差错的图案(共共共共个个个个) )。n n如果总行数如果总行数如果总行数如果总行数(1+(1+n n +)+)仍然小于仍然小于仍然小于仍然小于2 2n-kn-k，再列出带有，再列出带有，再列出带有，再列出带有3 3个差错的图个差错的图个差错的图个差错的图案，以此类推，直到放满案，以此类推，直到放满案，以此类推，直到放满案，以此类推，直到放满2 2n-kn-k行，每行一个行，每行一个

65、行，每行一个行，每行一个E Ej j, ,对应一个不同对应一个不同对应一个不同对应一个不同的伴随式的伴随式的伴随式的伴随式S Sj j。这样，表的行数。这样，表的行数。这样，表的行数。这样，表的行数2 2n-kn-k正好等于伴随式的数目。正好等于伴随式的数目。正好等于伴随式的数目。正好等于伴随式的数目。标准阵列译码表的构成标准阵列译码表的构成潍悄信勤花掖糖资粕孔晚躬粳庸及湛孤蔓之劳竟硒柠眯苟车肃欲蚁邹美滑第6章信道编码第6章信道编码49普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著S0E0S1E1SjEjE0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1E1+

66、CiEj+C0=EjEj+C1Ej+Ci标准阵列译码表标准阵列译码表E1+C1队桌栅萌宾竿本乔膳癌层稍醚澄典祝州锡篆拼袜烽虑哉载搏即菜由尤铡壕第6章信道编码第6章信道编码50普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著陪集和子集陪集和子集n n译译译译码码码码表表表表中中中中有有有有2 2n-kn-k行行行行，每每每每行行行行是是是是一一一一个个个个陪陪陪陪集集集集，每每每每陪陪陪陪集集集集的的的的第第第第一一一一个个个个元元元元素素素素( (位位位位于于于于第第第第一一一一列列列列) )叫叫叫叫陪陪陪陪集集集集首首首首。同同同同一一一一陪陪陪陪集集集集（同同同同一一一一行行行

67、行）中中中中的的的的所所所所有有有有元元元元素素素素对对对对应应应应共共共共同同同同的的的的一一一一个个个个伴伴伴伴随随随随式式式式。第第第第一一一一行行行行陪陪陪陪集集集集的的的的陪陪陪陪集集集集首首首首是是是是全全全全零零零零伴伴伴伴随随随随式式式式S S0 0所所所所对对对对应应应应的的的的全全全全零零零零差差差差错错错错图图图图案案案案E E0 0( (无无无无差差差差错错错错) )，而而而而第第第第j j行行行行陪陪陪陪集集集集的的的的陪陪陪陪集集集集首首首首是是是是伴伴伴伴随随随随式式式式S Sj j所所所所对对对对应应应应的的的的重重重重量量量量最最最最小小小小的的的的差错图案差

68、错图案差错图案差错图案E Ej j (C(C0 0=0,R=0,Rj j=E=Ej j) )。n n译译译译码码码码表表表表中中中中有有有有2 2k k列列列列，每每每每列列列列是是是是一一一一个个个个子子子子集集集集，每每每每子子子子集集集集的的的的第第第第一一一一个个个个元元元元素素素素( (位位位位于于于于第第第第一一一一行行行行) )叫叫叫叫子子子子集集集集头头头头。同同同同一一一一子子子子集集集集（同同同同一一一一列列列列）中中中中的的的的所所所所有有有有元元元元素素素素对对对对应应应应同同同同一一一一个个个个码码码码字字字字，第第第第一一一一列列列列子子子子集集集集的的的的子子子子

69、集集集集头头头头是是是是全全全全零零零零码码码码字字字字C C0 0，而而而而第第第第i i列列列列子子子子集集集集的的的的子子子子集集集集头头头头是是是是码码码码字字字字C Ci i (E(E0 0=0,=0,R Ri i=C=Ci i) ) 。詹钠咆牢徐酒捏厂且普沈惕蔷痴函哄荔鸦匝翱蹲谎肄眨届讶龄狮骆械尿高第6章信道编码第6章信道编码51普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6-3一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G=设收码设收码R=(10101)，构造标准阵列译码表，译出发码的估值，构造标准阵列译码表，译出发码的估值解解：(1)构构造

70、造标标准准阵阵列列译译码码表表。分分别别以以信信息息组组m=(00)、(01)、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：求出校验矩阵：H=PTI3=列出方程组：列出方程组：袍踪彪定母咖瞥赠喀柑金会哥邪屉薪拒椎示籽社圆假幕洋咽设结浇澜住句第6章信道编码第6章信道编码52普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著伴随式有伴随式有2n-k238种组合，差错图案中代表无差错的有种组合，差错图案中代表无差错的有一种，代表一个差错的图案有一种，代表一个差错的

71、图案有种，已有种，已有6种。种。代表两个差错的图案有代表两个差错的图案有种。只需挑选其中的两个，种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上代入上面的线性方程组，解得对应的面的线性方程组，解得对应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，。剩下的伴随式中，(011)所对应的差错图案是所对应的差错图案是2k个即个即(00011)、(10100)、(01110)、(11001),

72、其中其中(00011)和和(10100)并列重量最轻，任选其中并列重量最轻，任选其中一个如一个如(00011)。同样可得伴随式。同样可得伴随式(110)所对应的最轻差错所对应的最轻差错图案之一是图案之一是(00110)。例例6-3译码表的构成译码表的构成哩跳羔害尺炎斋沮褂斤彰守患月余栖静头迂伯顷君砧痛侦彩视围莲渗削肚第6章信道编码第6章信道编码53普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=0100011111001011

73、0010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例例6-3标准阵列译码表标准阵列译码表吵哥粳剔鲁拱班视裴扩痊诛类虚之距腮渔掐秧橙滞稼茶漏咯抹悬姑结践死第6章信道编码第6章信道编码54普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6-3将接收码将接收码R10101译码译码可选以下三种方法之一译码：可选以下三种方法之一译码：n直接搜索

74、码表，查得直接搜索码表，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此，因此译码输出取为译码输出取为(10111)。n先求伴随式先求伴随式RHT=(10101) HT=(010)=S4，确定，确定S4所在行，所在行，再沿着行对码表作一维搜索找到再沿着行对码表作一维搜索找到(10101),最后顺着所在列向最后顺着所在列向上找出码字上找出码字(10111)。n先求出伴随式先求出伴随式RHT=(010)=S4并确定并确定S4所对应的陪集首（差错所对应的陪集首（差错图案）图案）E4=(00010)，再将陪集首与收码相加得到码字，再将陪集首与收码相加得到码字C=R+E4=(101

75、01)+(00010)=(10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。实际使用时可针对不同情况选用。颜脓削籽奄撞滴彭圈简喂芬调牟石漠梯社猖钟答辊迟戌岩补深侵竣则漓逾第6章信道编码第6章信道编码55普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著对上例作进一步分析，还可以看到，该对上例作进一步分析，还可以看到，该(5,2)码的码的dmin=3,纠错能力是纠错能力是t =INT(3-1)/2=1。因此，译码阵列中。因此，译码阵列中只有前只有前6行具有唯一性、可靠性，真正体现了最大

76、似然译行具有唯一性、可靠性，真正体现了最大似然译码准则，而第码准则，而第7、8行的差错图案行的差错图案(00011)和和(00110)中包含中包含两个两个“1”，已超出了，已超出了t=1的纠错能力，译码已不可靠。比的纠错能力，译码已不可靠。比如，当收码如，当收码R(10100)时，根据码表译出的码字是时，根据码表译出的码字是(10111)，与收码，与收码R的汉明距离是的汉明距离是2，然而收码，然而收码R与全零码与全零码字字(00000)的汉明距离也是的汉明距离也是2，为什么不能译成，为什么不能译成(00000)呢呢？事实上，码表的第？事实上，码表的第7、8行本身就不是唯一的。注意在码行本身就不

77、是唯一的。注意在码表计算过程中，伴随式表计算过程中，伴随式(011)所对应的所对应的4个差错图案中有两个差错图案中有两个并列重量最轻，如果当时选的不是个并列重量最轻，如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就不是现在这样了。行就不是现在这样了。对例对例6-3的的分析分析绸滦殃诬酬析昂劣宠江撤孽钵茎勃醇终卸稻应问佛策篇颇无络锐阶陵楞泣第6章信道编码第6章信道编码56普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3.3码距、纠错能力、码距、纠错能力、MDC码及重量谱码及重量谱n nN重码矢重码矢c =(cn-1,c n-2,c1,c0)可与

78、可与N维矢量维矢量空间空间XN中的一个点对应，全体码字所对应中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集的点构成矢量空间里的一个子集n n发码一定在这个子集里，传输无误时的收发码一定在这个子集里，传输无误时的收码也一定位于该子集码也一定位于该子集n n当出现差错时，接收的当出现差错时，接收的N重矢量重矢量:n n对应到子集外空间某一点对应到子集外空间某一点对应到子集外空间某一点对应到子集外空间某一点 n n对应到该子集，却对应到该子集的另一点上对应到该子集，却对应到该子集的另一点上对应到该子集，却对应到该子集的另一点上对应到该子集，却对应到该子集的另一点上 释痔碌篱壹据侧哑暮免酵

79、汛怔釉荧骚映坟泰陕筑媳葵线庭寒跪刹社囊捡隅第6章信道编码第6章信道编码57普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著td=7dmin=3d=5C1C2C3C4C5n n码集各码字间的距离码集各码字间的距离是不同的，码距最小是不同的，码距最小者决定码的特性，称者决定码的特性，称之为之为最小距离最小距离dminn n这里这里dmin=3，纠错能力，纠错能力是是1，检错能力是，检错能力是26.3.3码距、纠错能力、码距、纠错能力、MDC码及重量谱码及重量谱山悟梅巳涩屠诉旋抖酗研癣啤蛀偏鲍触浓辐费攫莫稻狞沼惊钵迎络嘉诲岩第6章信道编码第6章信道编码58普通高等教育“十五”国家级规划教

80、材信息论与编码 曹雪虹等编著n n定定定定理理理理6.16.1 任任任任何何何何最最最最小小小小距距距距离离离离d dminmin的的的的线线线线性性性性分分分分组组组组码码码码，其其其其检检检检错错错错能力为（能力为（能力为（能力为（d dminmin-1-1）, ,纠错能力纠错能力纠错能力纠错能力t t为为为为n n定定定定理理理理6.26.2 线线线线性性性性分分分分组组组组码码码码的的的的最最最最小小小小距距距距离离离离等等等等于于于于码码码码集集集集中中中中非非非非零零零零码码码码字的最小重量字的最小重量字的最小重量字的最小重量ddminmin=minw(=minw(C C i i

81、) )C C i i CC及及及及C C i i 0 0 6.3.3码距、纠错能力、码距、纠错能力、MDC码及重量谱码及重量谱驰管垫隙奔漫租痈摸堡网堡蹬仁柔管褒把瞅巡萎遍酋垫应缀添习瞥面蠢嚷第6章信道编码第6章信道编码59普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n定理定理6.3(n,k)线性分组码最小距离等于线性分组码最小距离等于dmin的充要条件是：校验矩阵的充要条件是：校验矩阵H中有（中有（dmin-1)列线性无关。列线性无关。n n定定理理6.4(n,k)线线性性分分组组码码的的最最小小距距离离必必定定小于等于小于等于(n-k+1)dmin (n-k+1)6.3.

82、3码距、纠错能力、码距、纠错能力、MDC码及重量谱码及重量谱诧注搪盾讹毁雍粮后浦铁粘格蒸京踩裴惕袁把勇凋疟唤胃梅韦湿造序阑害第6章信道编码第6章信道编码60普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例：例：H(7，4)线性码线性码各列都不相同，任意各列都不相同，任意2列之和不等于列之和不等于0，2列线性无关；任意列线性无关；任意2列之和一定等于矩阵中列之和一定等于矩阵中某一列，任意某一列，任意3列线性相关。所以该码的最列线性相关。所以该码的最小距离为小距离为3，小于，小于n-k +14。6.3.3码距、纠错能力、码距、纠错能力、MDC码及重量谱码及重量谱务渤凄江谣柿效剩妻惮阮

83、市壁血集篡揣赤川通月夸揪火惦昏董满分儿逊唁第6章信道编码第6章信道编码61普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n（n,kn,k）线线线线性性性性码码码码最最最最小小小小距距距距离离离离d dminmin的的的的上上上上边边边边界界界界是是是是n-k n-k +1+1。如如如如果果果果我我我我们们们们设设设设计计计计的的的的（n,kn,k）线线线线性性性性码码码码的的的的d dminmin达达达达到到到到了了了了n-k n-k +1+1，就就就就是是是是达达达达到到到到了了了了设设设设计计计计性性性性能能能能的的的的极极极极点点点点。因因因因此此此此，d dminmi

84、n n-k n-k +1+1的的的的码码码码称称称称为为为为极极极极大大大大最最最最小小小小距距距距离离离离码码码码 (MDC(MDC MaximizedminimumDistanceCodeMaximizedminimumDistanceCode) )。n n总总总总体体体体的的的的、平平平平均均均均的的的的纠纠纠纠错错错错能能能能力力力力不不不不但但但但与与与与最最最最小小小小距距距距离离离离有有有有关关关关，而而而而且且且且与与与与其其其其余余余余码码码码距距距距或或或或者者者者说说说说与与与与码码码码字字字字的的的的重重重重量量量量分分分分布特性有关。布特性有关。布特性有关。布特性有关

85、。 6.3.3码距、纠错能力、码距、纠错能力、MDC码及重量谱码及重量谱榨圭铸韵豫父六典健盅伊曼犬糜造哼倪尉秤野异要猿母了阮痪邑呛殿媚篇第6章信道编码第6章信道编码62普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个个伴随式，假如该码的纠错能力是伴随式，假如该码的纠错能力是t，则对于，则对于任何一个重量小于等于任何一个重量小于等于t的差错图案，都应的差错图案，都应有一个伴随式与之对应，也就是说，伴随有一个伴随式与之对应，也就是说，伴随式的数目满足条件式的数目满足条件n n上式称作上式称作汉明限汉明限，任何

86、一个纠，任何一个纠t码都应满足码都应满足上述条件。上述条件。6.3.4完备码完备码(Perfectcode)显烷俄申奠师寐踩啥刺飞看斜挽坤饰圭济骆驰蓄宋熟扯镐泛猾悦堆筑愁京第6章信道编码第6章信道编码63普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3.4完备码完备码某二元某二元某二元某二元( (n,kn,k) )线性分组码能使等式线性分组码能使等式线性分组码能使等式线性分组码能使等式 成成成成立立立立，即即即即该该该该码码码码的的的的伴伴伴伴随随随随式式式式数数数数目目目目不不不不多多多多不不不不少少少少恰恰恰恰好好好好和和和和不不不不大大大大于于于于t t个个个个差差差差

87、错错错错的的的的图图图图案案案案数数数数目目目目相相相相等等等等，相相相相当当当当于于于于在在在在标标标标准准准准译译译译码码码码阵阵阵阵列列列列中中中中能能能能将将将将所所所所有有有有重重重重量量量量不不不不大大大大于于于于t t的的的的差差差差错错错错图图图图案案案案选选选选作作作作陪陪陪陪集集集集首首首首，而而而而没没没没有有有有一一一一个个个个陪陪陪陪集集集集首首首首的的的的重重重重量量量量大大大大于于于于t t，这这这这时时时时的的的的校校校校验验验验位位位位得得得得到到到到最最最最充充充充分分分分的的的的利利利利用用用用。这这这这样样样样的的的的二二二二元元元元( (n,kn,k)

88、 )线性分组码称为线性分组码称为线性分组码称为线性分组码称为完备码完备码完备码完备码。 蛋焰册挣滴擅亡啤承氢雅脯样跟熄琵仑较致队谓措略筛助宰灌虹帚垣谬处第6章信道编码第6章信道编码64普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著汉明码汉明码(HammingCode)n n汉明码不是指一个码，而是代表一类码。汉明码不是指一个码，而是代表一类码。汉明码不是指一个码，而是代表一类码。汉明码不是指一个码，而是代表一类码。n n汉汉汉汉明明明明码码码码的的的的纠纠纠纠错错错错能能能能力力力力t t =1 1，既既既既有有有有二二二二进进进进制制制制的的的的，也也也也有有有有非非非非二二二

89、二进进进进制制制制的的的的。二二二二进进进进制制制制时时时时，汉汉汉汉明明明明码码码码码码码码长长长长n n和和和和信信信信息息息息位位位位k k服服服服从从从从以以以以下下下下规规规规律：律：律：律：(n,kn,k)=(2)=(2mm-1,2-1,2mm-1-1-mm) ) 其中其中其中其中mm= = n-k n-k，是正整数。，是正整数。，是正整数。，是正整数。n n当当当当mm3 3、4 4、5 5、6 6、7 7、8 8时时时时，有有有有汉汉汉汉明明明明码码码码(7,4)(7,4)、(15,11)(15,11)、(31,26)(31,26)、(63,57)(63,57)、(127,12

90、0)(127,120)、(255,247)(255,247)。n n汉明码是完备码，因为它满足上述等式。汉明码是完备码，因为它满足上述等式。汉明码是完备码，因为它满足上述等式。汉明码是完备码，因为它满足上述等式。诌援痞卞溅沼呵始贱钻耳完截殴力碴乏央晌琐圆共豌迷壁幸谆誉原悬砰缓第6章信道编码第6章信道编码65普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著汉明码校验矩阵的构成汉明码校验矩阵的构成汉明码的校验矩阵汉明码的校验矩阵汉明码的校验矩阵汉明码的校验矩阵HH具有特殊的性质，能具有特殊的性质，能具有特殊的性质，能具有特殊的性质，能使构造方法简化。一个使构造方法简化。一个使构造方法简

91、化。一个使构造方法简化。一个( (n,kn,k) )码的校验矩阵有码的校验矩阵有码的校验矩阵有码的校验矩阵有n nk k行和行和行和行和n n列，二进制时列，二进制时列，二进制时列，二进制时n-kn-k个码元所能组成的个码元所能组成的个码元所能组成的个码元所能组成的列矢量总数是列矢量总数是列矢量总数是列矢量总数是2 2n-kn-k-1,-1,恰好和校验矩阵的列数恰好和校验矩阵的列数恰好和校验矩阵的列数恰好和校验矩阵的列数n n =2=2mm-1-1相等。只要排列所有列，通过列置换将相等。只要排列所有列，通过列置换将相等。只要排列所有列，通过列置换将相等。只要排列所有列，通过列置换将矩阵矩阵矩阵

92、矩阵HH转换成系统形式，就可以进一步得到相转换成系统形式，就可以进一步得到相转换成系统形式，就可以进一步得到相转换成系统形式，就可以进一步得到相应的生成矩阵应的生成矩阵应的生成矩阵应的生成矩阵GG。 爱敬乞深酣札陶避待革阂萧娥友虽凯渣焚净妆铸瑚况宦幢以剖拔咎卞赚翟第6章信道编码第6章信道编码66普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6.4构造一个构造一个m=3的二元的二元(7，4)汉明码。汉明码。解解：先先利利用用汉汉明明码码的的特特性性构构造造一一个个(7，4)汉汉明明码码的的校校验验矩阵矩阵H，再通过列置换将它变为系统形式：，再通过列置换将它变为系统形式：0001

93、111列置换列置换1110100H=0110011 0111010=PTI310101011101001再得生成矩阵再得生成矩阵G为为1000101G=I4P=010011100101100001011碎叉咳伙祝液厚墓埔佬绎峭帚刽垢革唁官延纵樱乓擎剐株端誊笋焚相放擎第6章信道编码第6章信道编码67普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著高莱（高莱（Golay）码）码n n是二进制（是二进制（23，12）线性码，）线性码，n n其最小距离其最小距离dmin7，纠错能力，纠错能力t =3。n n是完备码，因为满足等式是完备码，因为满足等式223-12=2048=n n在在(23

94、,12)码上添加一位奇偶位即得二进码上添加一位奇偶位即得二进制线性（制线性（24，12）扩展高莱码，其最小）扩展高莱码，其最小距离距离dmin8。眩劣肾溃佩蕊互哟面仗崇创泵婪徒醚领陶尖谣井轧别飘套肥连狮远霉陌环第6章信道编码第6章信道编码68普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3.5循环码循环码n n循环码是线性码的一个子类；循环码是线性码的一个子类；n n满足下列循环移位特性：码集满足下列循环移位特性：码集C中任何一个中任何一个码字的循环移位仍是码字。码字的循环移位仍是码字。供牢嚼躁音锄熏烦泄虐处步帝扫焚懦疫硒哩夏饲普便闺奔路色当蔼藉祟呛第6章信道编码第6章信道编

95、码69普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著循环码的多项式描述循环码的多项式描述n n一般一般(n,k)线性分组码的线性分组码的k个基底之间不存个基底之间不存在规则的联系，因此需用在规则的联系，因此需用k个基底组成生成个基底组成生成矩阵来表示一个码的特征。矩阵来表示一个码的特征。n n而循环码的而循环码的k个基底可以是同一个基底循环个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个次得到，因此用一个基底就足以表示一个码的特征。码的特征。n n既然只有一个基底，就无需矩阵，只要用既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。多项式作为数学工具

96、就足够了。锦巢痉五炉免醚皇狂宾到歧咆岳艇笋鸭脯去领佩衔缮搜絮斤相单嚼书缴酌第6章信道编码第6章信道编码70普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n把码字把码字Ccn-1cn-2 c1c0与一个不大于与一个不大于n-1次的次的码多项式码多项式C (x)对应起来。起来。n n码多项式码多项式C (x)定义为：定义为：C(x)=cn-1xn-1+ cn-2xn-2 +c1x +c0n n对于二进制码，对于二进制码，ci 0,1,i =0,，n-1。循环码的多项式定义循环码的多项式定义萝页集欣炼厩抹椽云娘婉伯栋匣肋陋推剥莆高场勒间殴刚银辕授棋碑坑臻第6章信道编码第6章信道编码

97、71普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n循环移一位：循环移一位：循环移一位：循环移一位：( (c cn n-1-1c cn n-2-2 c c1 1c c0 0)()(c cn n-2-2 c c1 1c c0 0 c cn n-1-1) )n n循环移一位：循环移一位：循环移一位：循环移一位：C C0 0( (x x)=)=c cn n-1-1x xn n-1-1+ +c cn n-2-2x xn n-2-2+c c1 1x x+c c0 0 C C1 1( (x x)=)= c cn n-2-2x xn n-1-1+ +c cn n-3-3x xn n-2-2

98、+c c0 0 x x+c cn n-1-1n n比比比比较较较较循循循循环环环环移移移移位位位位的的的的前前前前后后后后，可可可可用用用用如如如如下下下下的的的的多多多多项项项项式式式式运运运运算算算算来来来来表表表表达循环移位达循环移位达循环移位达循环移位移移移移1 1位：位：位：位： C C1 1( (x x)=)=xCxC0 0( (x x)mod(mod(x xn n +1)+1)移移移移2 2位：位：位：位： C C2 2( (x x)=)=xCxC1 1( (x x)=)=x x2 2C C0 0( (x x) )mod(mod(x xn n +1)+1)移移移移n-n-1 1位

99、：位：位：位：C Cn-n-1 1( (x x)=)=xCxCn n-2-2( (x x)=)=x xn-n-1 1C C0 0( (x x) ) mod(mod(x xn n +1)+1) 循环码的循环移位循环码的循环移位魏爽箔湃佛武滦阉裳拆杏纷颓李娄挥耻悉鼻辅吧艇岿锭幼鸟漏侄唱哭蹄汁第6章信道编码第6章信道编码72普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著码字的组成码字的组成n根据码空间的封闭性，码字的线性组合仍是码字。C C(x x)=a a0C C0(x x)+a a1xCxC0(x x)+a a2x x2C C0(x x)+a an n-1x xn n-1C C0(

100、x x)=(a a0+a a1x x+ a a2x x2+ a an n-1x xn n-1)C C0(x x)=A A(x x)C C0(x x)mod(x xn n+1)n其中C C0(x x)是一个码多项式，而A A(x x)是次数不大于n n-1的任意多项式。对于二进制码，a ai i0,1,i i =0,，n n-1。频身天蓝件衙溪缝毫阵湃楚首争罢窘纶谋涣京都铺嘿笼载棵烯黔缔淡彝歌第6章信道编码第6章信道编码73普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著生成多项式生成多项式 C(x)=m(x)g(x)码多信息生成项式多项式多项式n n生成多项式不是唯一的；生成多项式

101、不是唯一的；n ng g( (x x) )x x n-kn-k + + g gn-kn-k-1-1x x n-kn-k-1-1+ g g22x x2 2+ + g g11x x+1+1是是( (n-kn-k) )次的次的首一首一首一首一码码多项式多项式 ，即，即( (n-kn-k) )次项的系次项的系数为数为1 1。n ng g( (x x) )一定是一定是( (x xn n+1)+1)的因子。的因子。梢硬恰啮嘴坦亿艇碟吧二拍蹦避贩搞畴彦谈亏澄盔靠阂渊昨灵禽把兜烛替第6章信道编码第6章信道编码74普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著校验多项式校验多项式n多项式x xn

102、n+1可因式分解为x xn n+1g g(x x)h h(x x)的形式；n如果g g(x x)代表(n n，k k)循环码的生成多项式，则h h(x x)代表该循环码的一致校验多项式一致校验多项式一致校验多项式一致校验多项式，其阶次为，其阶次为k k。n nh h( (x x) )的校验作用表现在：任何码多项式的校验作用表现在：任何码多项式C C( (x x) )与与h h( (x x) )的的模模x xn n+1+1乘积一定等于乘积一定等于0 0，而非码字与，而非码字与h h( (x x) )的乘积必不的乘积必不为为0 0。 C C( (x x) )h h( (x x)=)= m m( (

103、x x) )g g( (x x) )h h( (x x)=)= m m( (x x)( )( x xn n+1)=0mod(+1)=0mod(x xn n+1)+1)取定稀觉篇距秦走葱态航壕副筒潮执无寂恫枉泰玖厉鼻潘乘顿镁婉淤槐心第6章信道编码第6章信道编码75普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6.5 研究一个长度研究一个长度n n=7的循环码的构成方法的循环码的构成方法(1) 对(x7+1)作分解，找出n-k次因式。 x7+1(x+1)(x3+x2+1)(x3+x+1)，n n- -k k 因式因式g(g(x x)对偶式对偶式h(h(x x) ) 循环码循环码1

104、(1(x x+1)+1) ( (x x3 3+ +x x2 2+1)(+1)(x x3 3+ +x x+1)+1) (7,6)(7,6)3(3(x x3 3+ +x x2 2+1)(+1)(x x+1)(+1)(x x3 3+ +x x+1)+1)(7,4)(7,4)3(3(x x3 3+ +x x+1)(+1)(x x+1)(+1)(x x3 3+ +x x2 2+1)+1)(7,4)(7,4)4(4(x x+1)(+1)(x x3 3+ +x x2 2+1)(+1)(x x3 3+ +x x+1)+1)(7,3)(7,3)4(4(x x+1)(+1)(x x3 3+ +x x+1)(+1)

105、(x x3 3+ +x x2 2+1)+1)(7,3)(7,3)6(6(x x3 3+ +x x2 2+1)(+1)(x x3 3+ +x x+1)+1) ( (x x+1)+1)(7,1)(7,1)诞扎毁砒戊堪睁踊悼受承舶二山籍稍积坊蔼跌园寺妇撅重满陌惠崇匣址邵第6章信道编码第6章信道编码76普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著(2)构成(7,3)循环码：选g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，则C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。当输入信息m=(011)时，m(x)=(x+1)，C(x)=(x+

106、1)(x4x3x21)=x5+ x2+ x1+ 1，对应码矢C=(0100111)。例例6.5 研究一个长度研究一个长度n n=7的循环码的构成方法的循环码的构成方法恶欲腾护蜂眺锈逐伸姐梳艾嗽犯硷诌脓噶燎绰忌戊撩哑哮石憎胀验喊坤搪第6章信道编码第6章信道编码77普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著信息矢量mm(m2m1m0)码矢C C(c6c5c4c3c2c1c0)00000101001110010111011100000000011101011101001001111110100110100110011101010011例例6.5 研究一个长度研究一个长度n n=7的

107、循环码的构成方法的循环码的构成方法挺跨泌赖他糠盏士屉履奉乌村倪碟蘸唐才吱员纳满你袍厨鳞橇恩缄砷磋叉第6章信道编码第6章信道编码78普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著系统循环码系统循环码n码字的前k位原封不动照搬信息位而后面(nk)位为校验位：C(x)=xn-k m(x)+ r(x)n产生系统循环码的方法：n n将信息多项式将信息多项式m m( (x x) )预乘预乘x xn-kn-k，即右移（，即右移（n-kn-k）位；）位；n n将将x xn-k n-k m m( (x x) )除以除以g g( (x x) )，得余式，得余式r r( (x x) )；n n得系统循

108、环码的码多项式：得系统循环码的码多项式：C C( (x x)=)=x xn-k n-k m m( (x x) ) + + r r( (x x) )。艾乓痘据雍溢眷城敷频目嗣弓巢镰茶惧掌罚蚂庆叹萌葡潭嵌否光涟虎钒歌第6章信道编码第6章信道编码79普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6.6 (7,3)循环码生成多项式是g(x)=x4+x3+x2+1，用式(6-3-35)产生系统循环码。解解：先以输入信息m=(011)即m(x)=(x+1)为例，.xn-k m(x)= x4(x+1)= x5+ x4.( x5+ x4)除以(x4+ x3+ x2+ 1)，得余式(x3+ x

109、). C(x)= xn-k m(x) + r (x)( x5+ x4)+(x3+ x),对应码矢(0111010)。依次将(000)(111)代入，可得全部码矢如表6-6。此表与表6-5对比，可见码集未变而映射规则变了，表6-6满足系统循环码要求。釜寇俞汞黎摄饶禹曝玫棚葡枚症吞惹躯磁冰娶浊猩敢偿晃临她该鹏递痰历第6章信道编码第6章信道编码80普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著扩展码扩展码n如果给每个码字添加一位奇偶校验位c c校校，构成（，构成（n n1 1，k k）线性码，称为线性码，称为扩展码扩展码扩展码扩展码。ccn-n-1 1,c,c1 1,c,c0 0 cc

110、n-n-1 1,c,c1 1,c,c00,c,c校校 c c n n11c c11c c0 0 c c 校校0 0n n在二进制偶校验时：在二进制偶校验时：n n原来码字中原来码字中1 1的个数为偶数，则添加校验位的个数为偶数，则添加校验位0 0；n n原来码字中原来码字中1的个数为奇数，则添加校验位的个数为奇数，则添加校验位1 1。n n如果某码原来的最小重量如果某码原来的最小重量d dminmin是奇数，则新的最小距离变为是奇数，则新的最小距离变为d dminmin+1+1，检错能力增，检错能力增1 1。校验矩阵校验矩阵HHe eH抖窜幌宪资脯爱畸钓透啊腾五噎消缄绑箕撂坞隧傻惟九缺撵冒债南

111、釉奢选第6章信道编码第6章信道编码81普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著缩短码缩短码n n把第一位为把第一位为把第一位为把第一位为1 1的所有码字舍去，剩下另一半第的所有码字舍去，剩下另一半第的所有码字舍去，剩下另一半第的所有码字舍去，剩下另一半第一位为一位为一位为一位为0 0的码字舍去它们的第一位后组成一个的码字舍去它们的第一位后组成一个的码字舍去它们的第一位后组成一个的码字舍去它们的第一位后组成一个新的新的新的新的( ( n n1 1，k k1)1)码，称为码，称为码，称为码，称为缩短码缩短码缩短码缩短码。n n码长码长码长码长n n1 1和信息位长度和信息位长度

112、和信息位长度和信息位长度k k1 1均缩短了。均缩短了。均缩短了。均缩短了。( ( n n1 1，k k1)1)缩短码共包含缩短码共包含缩短码共包含缩短码共包含2 2k k 2=22=2k k-1-1个码字。个码字。个码字。个码字。n n由于原先保留的均是第一位为由于原先保留的均是第一位为由于原先保留的均是第一位为由于原先保留的均是第一位为0 0的码，舍去它的码，舍去它的码，舍去它的码，舍去它们的第一位不会改变码的最小重量，因此缩短们的第一位不会改变码的最小重量，因此缩短们的第一位不会改变码的最小重量，因此缩短们的第一位不会改变码的最小重量，因此缩短码与原码具有同样的码与原码具有同样的码与原码

113、具有同样的码与原码具有同样的d dminmin。称为（。称为（。称为（。称为（n n-1,-1,k k-1-1, d, dminmin）缩短码。）缩短码。）缩短码。）缩短码。 妒串一培跌瞥啃疫刻嫩孪伙窄鸣嵌鼎鬃部壮睦娠试孺巍纱侗创七岛告腺出第6章信道编码第6章信道编码82普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例：例：(7,4)码的生成矩阵为码的生成矩阵为47m3m2m1m0ci2ci1ci000000000001011001011000111010100111010110001100010111010CimGm3m2m1m0码字中的码字中的c6去掉，去掉，c6是信息位是信

114、息位m与与G的第一列相乘结果，所以的第一列相乘结果，所以G的第的第一列应去掉；一列应去掉；m3去掉，而去掉，而m3是与是与G的的第一行相乘，所以第一行相乘，所以G的第一行也去掉。的第一行也去掉。舷搁烈吮詹鬃宴复就寄颤臻才蜂瓣钮顽维宁篇毗郭郭雅薄究讳鸯扑苔禁栋第6章信道编码第6章信道编码83普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著得到新的生成矩阵为得到新的生成矩阵为G36原来的校验矩阵原来的校验矩阵H为为H37校验时，计算校验时，计算rHT，因，因r的第一位已没有，故的第一位已没有，故HT的第一行的第一行应去掉，即应去掉，即H的第一列去掉。得到新的校验矩阵的第一列去掉。得到新

115、的校验矩阵H为为Hdmin不变，为不变，为3。36束舀转四猿穴牺努齐省来亭喳僻恍沃笑唤茬砾箭廓议仓载恼话褪凤叮期城第6章信道编码第6章信道编码84普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著循环冗余校验循环冗余校验(CRC)码码n n信息位信息位k和码长和码长n可变，校验位长度可变，校验位长度n-k固定，固定，符合符合(n-i , k-i)缩短循环码的特点。缩短循环码的特点。n n以一个选定的以一个选定的(n,k)循环码为基础，改变循环码为基础，改变i值，得出任意信息长度的码字，而纠检错值，得出任意信息长度的码字，而纠检错能力保持不变。能力保持不变。n n循环冗余校验码（循环冗

116、余校验码（(CRC-CyclicRedundancyCheck)）是系统的缩短循环）是系统的缩短循环码。码。梁横潭膘垮耸陷懂札垛俺晦拣捣桥裤印寿穆裔赔氛眉捎耍粗屡栏字掘踌庚第6章信道编码第6章信道编码85普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例610某CRC码的生成多项式g(x)=x4+ x+1。如果想发送一串信息110001的前6位并加上CRC校验，发码应如何安排？收码又如何检验？解：解：本题信息多项式m(x)=x5+ x4+1,即k=6，因此n=10，degg(x)=4=n-k。将xn-k m(x)除以g(x),得余式 r(x)=xn-k m(x)mod g(x)=

117、x4( x5+ x4+1)mod g(x)=(x9+ x8+ x4)mod g(x)= x3+x2于是发码C(x)=xn-k m(x)+r (x)= x9+ x8+ x4 +x3+x2，对应的码字是(1100011100)。接收端的CRC校验实际上就是做除法。如果收码无误，R(x)除以g(x)应得余式0；反之，如果余式不等于零就说明一定有差错。烬齐滓稍赐督颁叮纲普活瓜乔趋住清贸感宛奴恐慢躬够亮市惯萄挺分帚偏第6章信道编码第6章信道编码86普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.4卷积码n卷积码的产生n分组码以孤立码块为单位编译码n信息流割裂为孤立块后丧失了分组间的相关信

118、息n分组码长n n越大越好，但译码运算量随n n指数上升n n本节内容本节内容n n卷积码的基本概念和描述方法卷积码的基本概念和描述方法n n卷积码的最大似然译码卷积码的最大似然译码维特比算法维特比算法n n卷积码的性能限与距离特点卷积码的性能限与距离特点 由秧眠宦菜躲竟合毒棉僵庙勉梧庶夺袄措喝翔步码谩低镶枯铬坞闸诫于栓第6章信道编码第6章信道编码87普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n将信息序列分隔成长度k的一个个分组n n某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组。n n称L1为约束长度约束长度n n最重要的三个参数(n,k,L)6.

119、4.1卷积码的基本概念和描述方法晃摔锻圭佩扦舍嘉萍欲蒲芦凭迅楚沂让蘑极伎罗聪兼豆甜冠玩年柏吗牲室第6章信道编码第6章信道编码88普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著(n,k,L)卷积编码示意卷积编码示意第i i分组第i- i-1分组第i- i-2分组第i-Li-L分组m0i i m1i i mk k-1i i m0i i-1mk k-1i i-1m0i i-2mk-k-1i i-2m0i i-L L m1i i-L L mk-k-1i i-L L输入卷积编码器（线性组合器） c c0i i c c1i i c cn n-2i i c cn n-1i i 编码输出CCi

120、i爷梁芳匪终明奎蓄底鸥喂舔义奏晌诵渍券减城赎砂贺骏陷衰榔乌林浪继形第6章信道编码第6章信道编码89普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6-11二进制二进制(3,2,1)卷积编码器卷积编码器n本时刻mm0 0=(=(m m0 00 0, ,m m1 10 0)=(01),)=(01),上一时刻上一时刻mm1 1=(=(m m0 01 1, ,m m1 11 1)=(10)=(10)n ng gknknl l表示记忆阵列第表示记忆阵列第k k行行( (k k=0,1)=0,1)第第l l列列( (l l =0,1)=0,1)对第对第n n个个( ( n n =0,1,2

121、)=0,1,2)码元的影响码元的影响, ,共共N N K K(L+L+1)=1)= 322322个系数：个系数：gg000000=1,g=1,g000011=1,g=1,g010100=0,g=0,g010111=1,g=1,g020200=1,g=1,g020211=1,=1,gg101000=0,g=0,g101011=1,=1,g g111100=1,g=1,g111111=0,g=0,g121200=1,g=1,g121211=0=0。n n用用矩阵表示矩阵表示矩阵表示矩阵表示 c0i信号入m c1i Ci编码输出c2im0i m0i-1m1i m1i-1引造睫鸥卯屈仍群靳正限迟癣体密

122、闯织己首汰词呕嘘尊汁绰蓬痰钥拙针悟第6章信道编码第6章信道编码90普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n本时刻编码输出：C0=(c00, c10, c20)=m0G0+m1G1=(01)+(10)=(011)+(111)=(100)逼疤估辱轨伊挫悉邦温喷十漏纠让房梳呵嫌邵爬存致传砒极比交婉隘趾厄第6章信道编码第6章信道编码91普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著卷积码名称的由来卷积码名称的由来n设编码器的初始状态为零（记忆阵列全体清0 0），随着时），随着时刻刻i i的递推和的递推和k k比特信息组比特信息组( (mm0 0, ,mm1 1, ,

123、 ,mmL L, ,mmL L+1+1, ,) )源源不断源源不断地输入，码字地输入，码字( (C C0 0, ,CC1 1, , ,CCL L, ,CCL L+1+1, ,) )源源不断地输出。源源不断地输出。 在时刻在时刻i i=0=0时，时，C C0 0 =mm0 0GG0 0 i i=1=1时，时，C C1 1=mm1 1GG0 0+mm0 0GG1 1 i i= L L 时，时，C CL L=mmL LGG0 0+mmL L-1-1GG1 1mm0 0GGL L i i= =L L+1+1时，时，C CL L+1+1=mmL L+1+1GG0 0+mmL LGG1 1mm1 1GGL

124、 Ln于是任何时刻i i的输出码字：的输出码字：C Ci i=mmi -li -lGGl l 扔嗜排和樊谐肾珐追朽报脊军树盼使犯等酸漂损蒸黔暑述蜂挛杏骨沧汤这第6章信道编码第6章信道编码92普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著多项式表示多项式表示G(D)=G0+G1D+GLDL =gkn(D)=gkn0+gkn1D+gkn2D2+gknLDL= gknlDl例6-11中 谜澳祥考宿撞登实硷痕践镶临坊三亮苑溃椿滨聂办蜜款婉后晨吭尉毡谦算第6章信道编码第6章信道编码93普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例612二元(3,1,2)(3,1,2)卷积码

125、的转移函数矩阵卷积码的转移函数矩阵GG(D)=(1,1+D,1+D+D(D)=(1,1+D,1+D+D22) )，根据转移函数矩阵，根据转移函数矩阵，g g0000(D)=(D)= g g00000 0+ + g g00001 1D+D+ g g00002 2DD22=1=1 g g0101(D)=(D)= g g01010 0+ + g g01011 1D+D+ g g01012 2DD22=1=1D Dg g0202(D)=(D)=g g02020 0+ +g g02021 1D+D+g g02022 2DD22=1+D+D=1+D+D2 2得得 g g000000=1,=1,g g000

126、011=0,=0,g g000022=0,=0,g g010100=1,=1,g g010111=1,=1,g g010122=0,=0,g g020200=1,=1,g g020211=1,=1,g g020222=1=1。 c0i信号入m c1i 输出Cic2im0i m0i-1m0i-2皋货败长下慈轧胳嘎喷驮鹤疡红津计妇丘较歇蔚充更砷喘侄气总裤悲净眺第6章信道编码第6章信道编码94普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著图图6-20(3,1,2)卷积码状态流图卷积码状态流图n假如输入信息序列是10110，S01/111S20/011S11/110S21/100S30/

127、010S10/000S01/1110/0011/110S2S10/0111/1000/010S31/101测纲缆裸派紫掠倔赶舜莹押谨萝赁臀谋室危捐使谁仗葛奖阵刃包淫何责呼第6章信道编码第6章信道编码95普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著卷积码网格图卷积码网格图S0(00)1/1110/0010/001S S1 1(01)(01) 1/1111/111 SS2 2(10)(10) 0/0100/010 1/1101/110 S S3 3(11)(11) t=0t=0TT2T2T3T3T 4T5T6T4T5T6T1/1100/0110/0101/1010/0001/100

128、0/0000/0000/0000/0000/0000/0000/0111/1101/100输入信息序列是10110，输出码字是111，011，110，100，010第一部分：网格图第二部分：编码轨迹（路径）图诵盎绎闯跌泡库襟藤缓万印垛身误杨阻潦馒淄叉瓦帜潜扰辖讫讹取当方练第6章信道编码第6章信道编码96普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著第第6章章信道编码复习复习n n6.1有扰离散信道的编码定理有扰离散信道的编码定理n n6.1.16.1.1差错和差错控制系统分类差错和差错控制系统分类差错和差错控制系统分类差错和差错控制系统分类n n6.1.26.1.2矢量空间与码空

129、间矢量空间与码空间矢量空间与码空间矢量空间与码空间n n6.1.36.1.3随机编码随机编码随机编码随机编码n n6.1.46.1.4信道编码定理信道编码定理信道编码定理信道编码定理n n6.2纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法n n6.2.16.2.1纠错编码的基本思路纠错编码的基本思路纠错编码的基本思路纠错编码的基本思路n n6.2.26.2.2译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码充勺后篱申羹创遍赐该丛骸少阉须肩恍欠廷真帧赎伟糖致充厂涤萝辙颤诛第6章信道编码第6章信道编码97普通高

130、等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n6.3线性分组码线性分组码n n6.3.16.3.1线性分组码的生成矩阵和校验矩阵线性分组码的生成矩阵和校验矩阵线性分组码的生成矩阵和校验矩阵线性分组码的生成矩阵和校验矩阵n n6.3.26.3.2伴随式与标准阵列译码伴随式与标准阵列译码伴随式与标准阵列译码伴随式与标准阵列译码n n6.3.36.3.3码距、纠错能力、码距、纠错能力、码距、纠错能力、码距、纠错能力、MDCMDC码及重量谱码及重量谱码及重量谱码及重量谱n n6.3.46.3.4完备码完备码完备码完备码n n6.3.56.3.5循环码循环码循环码循环码n n6.3.76.

131、3.7分组码的扩展、缩短与分组码的扩展、缩短与分组码的扩展、缩短与分组码的扩展、缩短与循环冗余校验循环冗余校验循环冗余校验循环冗余校验CRCCRCn n6.4卷积码卷积码n n6.4.16.4.1卷积码的基本概念和描述方法卷积码的基本概念和描述方法卷积码的基本概念和描述方法卷积码的基本概念和描述方法第第6章章信道编码复习复习绿粟身暴盘咯椅刮尤盟特识茎溪澈恕别冀卢袭件奋圣庶渴宪卵大刑棺冰坠第6章信道编码第6章信道编码98普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n概念：概念：n n差错符号、差错比特差错符号、差错比特差错符号、差错比特差错符号、差错比特n n差错图样差错图样

132、：随机差错、突发差错随机差错、突发差错 n n纠纠纠纠错错错错码码码码分分分分类类类类：检检和和纠纠错错码码、分分组组码码和和卷卷积积码码、线线性性码码与与非非线线性性码码 、纠纠随随机机差差错错码码和和纠纠突突发发差差错码错码第第6章章信道编码复习复习吓玻儿拌陕靛溃凭眷梯氓叛褪谩映茨遵鸦宗刑粒撰磕玛曾阜孤湘矣诲立邮第6章信道编码第6章信道编码99普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著矢量空间与码空间矢量空间与码空间n nn n维维维维n n重空间有相互重空间有相互重空间有相互重空间有相互正交的正交的正交的正交的n n个基底个基底个基底个基底n n选择选择选择选择k k个

133、基底构成个基底构成个基底构成个基底构成k k维维维维n n重码空间重码空间重码空间重码空间C Cn n选择另外的选择另外的选择另外的选择另外的( (n n- -k k) )个个个个基底构成空间基底构成空间基底构成空间基底构成空间HHn nC C和和和和HH是对偶的，正是对偶的，正是对偶的，正是对偶的，正交的交的交的交的CHCHT T0,GH0,GHT T=0=0n维维n重空间重空间Vk维维k重重k维维n重重n-k维维信息组信息组码空间码空间n重重H空间空间mC硅托泛煎锥竿比德奏锄最递氮捞鲸叭嫡役生禽韧哈到耸岿湾曾撩泉卡因亏第6章信道编码第6章信道编码100普通高等教育“十五”国家级规划教材信息

134、论与编码 曹雪虹等编著有扰离散信道的编码定理有扰离散信道的编码定理n若传信率RC，就不可能有任何一种编码能使差错概率任意小。胳轿乓踏邓窖莎捻傈睬郊么聪坝菩湘晨卫壮域逛忍区吞钦鼠悬区棘茎谋论第6章信道编码第6章信道编码101普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错控制的途径差错控制的途径n从公式n n增大码长增大码长N Nn n增大可靠性函数增大可靠性函数E E( (R R) )：加大信道容量：加大信道容量C C减小码率减小码率( (传信率传信率) )R R。n n从概念上n n利用冗余度（增强相关性）利用冗余度（增强相关性）n n噪声均化噪声均化( (随机化随机化) )

135、授谰堪汛吵汾耍瘸斡铡仰窄惋瘪疡溅糊宵纳成掏腺淆购帽稽顾乡驶窃谍径第6章信道编码第6章信道编码102普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著最优译码与最大似然译码最优译码与最大似然译码n n最佳译码最佳译码MaxP(ci/r)，性能优，实现难n n最大似然译码最大似然译码MaxP(r/ci)，性能次优，实现容易n n最佳译码等同最大似然译码：最佳译码等同最大似然译码：n n码集的码字以相同概率发送码集的码字以相同概率发送n n接收码等概分布接收码等概分布熏俱馆死滦幻纯芥辱具泼须伐嫉岩兼粗芜梢瘪铭腻度闪震漳赦释颊牟教鸣第6章信道编码第6章信道编码103普通高等教育“十五”国家级

136、规划教材信息论与编码 曹雪虹等编著线性分组码线性分组码n线性分组码基本概念n n码元、码字、码集n n重量、重量分布、恒重码n n线性码（封闭性）n n基底、矢量正交、矢量空间正交、对偶空间、线性相关、线性无关冈河凄川绦汾药砷利湖区慈曰晶榜模轮嫩丢魏万虱磨鹊真吓废净溜苫激豺第6章信道编码第6章信道编码104普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著生成矩阵和校验矩阵生成矩阵和校验矩阵n生成矩阵G：CmGn校验矩阵H：CHT0n系统形式：GIk|P，HPT|In-kn差错图案E=R-C，伴随式SRHTEHTn标准阵列译码表篆都啤冉服轰稽则十岛铂邀父独挛肘详得涌束低覆管巴甄缺与序

137、怀簿押砚第6章信道编码第6章信道编码105普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著码距与纠、检错能力码距与纠、检错能力n码的总体性能取决于码距的分布特性（重重量谱量谱），而纠、检错能力取决于其中的最小者dmin，dmin=minw(C i )n n检、纠错能力：n n可检可检d dminmin11个差错个差错n n可纠可纠t=t=INT(INT(d dminmin1)/21)/2个差错个差错n n校验矩阵H中有（dmin-1)列线性无关n ndmin(n-k+1)，极大最小距离码极大最小距离码敝韵延卓玫地赃妥光冷译晓赘测豪瞅尚缔绦善魏酸蚀周孪伯耀懈哮淖禄朝第6章信道编码第6

138、章信道编码106普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著特殊的线性分组码特殊的线性分组码n完备码n汉明码：t=1，(2m-1，2m-1-m)n高莱（Golay）码：二进制（23，12）线性码，其最小距离dmin7，纠错能力t=3岛涨抹益猖召传介忌硅胡仔缩谊抓瘴芬婆河茨壤丑抖掂擎海笨颖磺腾俯廷第6章信道编码第6章信道编码107普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著循环码循环码n循环码用多项式表示：C(x)=m(x)g(x)n生成多项式：xn+1g(x)h(x)n校验多项式：C(x)h(x)=0mod(xn+1)n ng(x)xn-k + gn-k-1xn

139、-k-1+ g1x+1n系统循环码：C(x)=xn-k m(x)+ r (x)，r (x)=xn-k m(x)mod g(x)蔡雷批拈捡调椰咎纬犯霄硫赡瘩行酚铅秀兄弟剐坛伏及惫摇游巩坝瞻演侦第6章信道编码第6章信道编码108普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著扩展码和缩短码扩展码和缩短码n扩展码校验矩阵HHe en缩短码生成矩阵GGH粟柬歼刹舱盎贩宿躇姓杀色堰嘶塞腺砌闹氏夷冗绽满贞鸭出衅缎执踪桌篇第6章信道编码第6章信道编码109普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著卷积码卷积码n(n,k,L)n n表示：矩阵、多项式、结构图、状态图、网格图吻图铜自呈拯菇审条量芋席汀鞘亩抗筹痞罐蹭恍涯虏哼篇冤愿隔芍配耪柴第6章信道编码第6章信道编码110普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著习题习题6-4n例6-4系统生成矩阵0000000000000000000100010110101100100010110101100011001110111101策悠妥失彦懊财苏网胰冀斤揉赁蠢锋曼届简轧琉钩柜逊育字塑喷讥夕叠盅第6章信道编码第6章信道编码111普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著