第6章信道编码.ppt

《第6章信道编码.ppt》由会员分享，可在线阅读，更多相关《第6章信道编码.ppt（111页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章信道编码 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望本章内容本章内容n n有扰离散信道的编码定理有扰离散信道的编码定理 n n纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法n n线性分组码线性分组码 n n卷积码卷积码n n编码与调制的结合编码与调制的结合TCM码码n n运用级联、分集与信息迭代概念的纠错码运用级联、分集与信息迭代概念的纠错码2普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1 有扰离散信道的编码定理有扰离散

2、信道的编码定理 n n差错和差错控制系统分类差错和差错控制系统分类n n矢量空间与码空间矢量空间与码空间 n n随机编码随机编码 n n信道编码定理信道编码定理 3普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错类型差错类型n n差错符号差错符号：由符号发生差错引起，也叫：由符号发生差错引起，也叫信信号差错号差错，信号差错概率用，信号差错概率用误码元率误码元率表示表示n n差错比特差错比特：由信息比特发生差错引起，也：由信息比特发生差错引起，也叫叫信息差错信息差错，信息差错概率用，信息差错概率用误比特率误比特率表表示示n n对于对于二进制二进制传输系统，符号差错等效于比传输系统

3、，符号差错等效于比特差错；特差错；n n对于对于多进制多进制系统，一个符号差错到底对应系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号多少比特差错却难以确定。因为一个符号由多个比特组成。由多个比特组成。4普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错图样（差错图样（error pattern）n n定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之“差差差差”：差错图样差错图样差错图样差错图样E E发码发码发码发码C C 收码收码收码收码R R （模（模（模（模MM）n n例：例：例：

4、例：8 8进制进制进制进制(M=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 ，差错图样，差错图样，差错图样，差错图样中的中的中的中的“”既是符号差错也是比特差错，差错的既是符

5、号差错也是比特差错，差错的既是符号差错也是比特差错，差错的既是符号差错也是比特差错，差错的个数叫汉明距离。个数叫汉明距离。个数叫汉明距离。个数叫汉明距离。5普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错图样类型差错图样类型 n n随机差错随机差错：若差错图样上各码位的取值既：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码终以相等的概率独立发生于各码字、各码元、各比特；元、各比特；n n突发差错：突发差错：前后相关、成堆出现。突发差前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结

6、尾，错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。差错概率超过了某个额定值。6普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著纠错码分类纠错码分类 n n从功能角度从功能角度：检错码：检错码、纠错码、纠错码 n n对信息序列的处理方法对信息序列的处理方法：分组码、卷积码：分组码、卷积码n n码元与原始信息位的关系码元与原始信息位的关系：线性码、非线：线性码、非线性码性码 n n差错类型差错类型：纠随机差错码、纠突发差错码、：纠随机差错码、纠突发差错码、介于中间的纠随机介于中间的纠随机/突发差错

7、码。突发差错码。n n构码理论构码理论：代数码、几何码、算术码、组：代数码、几何码、算术码、组合码等合码等 7普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著差错控制系统分类差错控制系统分类 n n前向纠错（前向纠错（FEC）：发端信息经纠错编码：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递后传送，收端通过纠错译码自动纠正传递过程中的差错过程中的差错 n n反馈重发（反馈重发（ARQ）：）：收端通过检测接收码收端通过检测接收码是否符合编码规律来判断，如判定码组有是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码错，则通过反向信道通知发端重发该码 n n

8、混合纠错（混合纠错（HEC）：）：前向纠错和反馈重发前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两的结合，发端发送的码兼有检错和纠错两种能力种能力 8普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.2矢量空间与码空间矢量空间与码空间 n nF F表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，F F代表二元域代表二元域代表二元域代表二元域0,10,1n n设设设设n n重有序元素的集合重有序元素的集合重有序元素的集合重有序元素的集合V=V=V Vi i ,n n若满足条件：若满足

9、条件：若满足条件：若满足条件：n nV V中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；n nV V中矢量元素与数域中矢量元素与数域中矢量元素与数域中矢量元素与数域F F元素的标乘封闭在元素的标乘封闭在元素的标乘封闭在元素的标乘封闭在V V中；中；中；中；n n分配律、结合律成立，分配律、结合律成立，分配律、结合律成立，分配律、结合律成立，则称集合则称集合则称集合则称集合V V是数域是数域是数域是数域F F上的上的上的上的n n维维维维矢量空间矢量空间矢量空间矢量空间，或称，或称，或称，或称n n维维维维

10、线性空间线性空间线性空间线性空间，n n维矢量又称维矢量又称维矢量又称维矢量又称n n重重重重(n n-tuples)-tuples)。9普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著矢量空间中矢量的关系矢量空间中矢量的关系 对于域对于域对于域对于域F F上的若干矢量上的若干矢量上的若干矢量上的若干矢量n n线性组合线性组合线性组合线性组合：n n线性相关线性相关线性相关线性相关：其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合n n线性无关线性无关线性无关线性无关或或或或线性

11、独立线性独立线性独立线性独立：一组矢量中的任意一个都：一组矢量中的任意一个都：一组矢量中的任意一个都：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。不可能用其它矢量的线性组合来代替。不可能用其它矢量的线性组合来代替。不可能用其它矢量的线性组合来代替。10普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著矢量空间与基底矢量空间与基底n n一组线性无关的矢量一组线性无关的矢量 ，线性组合的，线性组合的集合集合就构成了一个就构成了一个矢量空间矢量空间V，这组矢量，这组矢量 就是这个矢量空间的就是这个矢量空间的基底基底。n nn维矢量空间应包含维矢量空间应包含n个基底个基底 n n

12、基底不是唯一的基底不是唯一的，例：线性无关的两个矢，例：线性无关的两个矢量（量（1,0）和（）和（0,1）以及（）以及（-1,0）和（）和（0,-1）可张成同一个两维空间可张成同一个两维空间。11普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著二元域二元域GF(2)上三重矢量空间上三重矢量空间 n n以（以（以（以（100100）为基底可张成）为基底可张成）为基底可张成）为基底可张成一维三重一维三重一维三重一维三重子空间子空间子空间子空间V V1 1，含，含，含，含2 21 1 =2=2 个元素，即个元素，即个元素，即个元素，即n n以以以以(010)(001)(010)(001)

13、为基底可张成为基底可张成为基底可张成为基底可张成二维三重二维三重二维三重二维三重子空间子空间子空间子空间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的子空间。的子空间。的子空间。的子空间。12普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著矢量空间矢量空

14、间n n每个矢量空间或子空间中必然包含零矢量每个矢量空间或子空间中必然包含零矢量n n两个两个矢量正交矢量正交：V1 V2 0 n n两个两个矢量空间正交矢量空间正交：某矢量空间中的任意：某矢量空间中的任意元素与另一矢量空间中的任意元素正交元素与另一矢量空间中的任意元素正交 n n正交的两个子空间正交的两个子空间V1、V2互为互为对偶空间对偶空间(Dual Space)，其中一个空间是另一个空间，其中一个空间是另一个空间的的零空间零空间（null space，也称零化空间）。，也称零化空间）。13普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著码空间码空间 消息消息k长长(n,k)

15、码码字字n长长 qk种种分组编码器分组编码器qn种种k维维k重矢量重矢量n维维n重矢量重矢量通常通常qnqk，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn种可能组合种可能组合中选择其中的中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。14普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著分组编码的任务分组编码的任务 n n选择一个选择一个维维n重子空间作为码空间。重子空间作为码空间。n n确定由确定由k维维k重信息空间到重信息空间到维维n重码空间的重码空间的映射方法。映射方法。码空间的不同码空间的不同选

16、择方法，以及信息组与选择方法，以及信息组与码组的不同映射算法，就构成了不同的分码组的不同映射算法，就构成了不同的分组码。组码。15普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n运用概率统计方法在特定信道条件下对编运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的率的上下限边界，其中最优码所能达到的差错概率上界称作差错概率上界称作随机码界随机码界。n n用这种方法不能得知最优码是如何具体编用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么

17、程出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论理，对指导编码技术具有特别重要的理论价值。价值。16普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n在在在在(N,K)(N,K)分组编码器中随机选定的码集有分组编码器中随机选定的码集有分组编码器中随机选定的码集有分组编码器中随机选定的码集有q qNMNM种种种种 n n第第第第mm个码集个码集个码集个码集(记作记作记作记作ccmm)被随机选中的概率是被随机选中的概率是被随机选中的概率是被随机选中的概率是n

18、n设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是P Pe e(c(cmm)n n全部码集的平均差错概率是全部码集的平均差错概率是全部码集的平均差错概率是全部码集的平均差错概率是17普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.1.3随机编码随机编码n n必定存在某些码集必定存在某些码集必定存在某些码集必定存在某些码集n n某些码集某些码集某些码集某些码集n n若若若若 ，就必然存在一批码集，就必然存在一批码集，就必然存在一批码集，就必然存在一批码集 即差错概率趋于零的好码一定存在即差错概

19、率趋于零的好码一定存在即差错概率趋于零的好码一定存在即差错概率趋于零的好码一定存在 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的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增加时，平均而言码

20、字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。n n当当当当F F0 0即即即即(N-KN-K)时，能否让平均差错概率时，能否让平均差错概率时，能否让平均差错概率时，能否让平均差错概率？n nGallagerGallager在在在在19651965年推导了年推导了年推导了年推导了的上边界，并证明这的上边界，并证明这的上边界，并证明这的上边界，并证明这个上边界是按指

21、数规律收敛的。个上边界是按指数规律收敛的。个上边界是按指数规律收敛的。个上边界是按指数规律收敛的。19普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n nE(R)为为可靠性函数可靠性函数，也叫误差指数，也叫误差指数n n码率码率：R=(lbM)/Nn nMM是可能的信息组合数，是可能的信息组合数，是可能的信息组合数，是可能的信息组合数，MM=q qK Kn nN N是每码字的码元数，是每码字的码元数，是每码字的码元数，是每码字的码元数，n nR R表示每码元携带的信息量，单位是每符号比表示每码元携带的信息量，单位是每符号比表示每码元携带的信息量，单位是每符号比表示每码元携带的信息

22、量，单位是每符号比特（特（特（特（bit/symbolbit/symbol）6.1.4信道编码定理信道编码定理20普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n nR R在在在在0,0,R R0 0 区间时区间时区间时区间时E E(R R)R R曲线是斜率为曲线是斜率为曲线是斜率为曲线是斜率为-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的关系曲线

23、的关系曲线6.1.4信道编码定理信道编码定理21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n正定理正定理：只要传信率：只要传信率R小于信道容量小于信道容量C，总，总存在一种信道码（及解码器），可以以所存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。要求的任意小的差错概率实现可靠的通信。n n逆定理逆定理：信道容量：信道容量C是可靠通信系统传信率是可靠通信系统传信率R的上边界，如果的上边界，如果R C，就不可能有任何，就不可能有任何一种编码能使差错概率任意小。一种编码能使差错概率任意小。6.1.4信道编码定理信道编码定理22普通高等教育“十五”国家

24、级规划教材信息论与编码 曹雪虹等编著6.2 纠错编译码的基本原理与分析纠错编译码的基本原理与分析n n纠错编码的基本思路纠错编码的基本思路 n n译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码 23普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2.1纠错编码的基本思路纠错编码的基本思路n nR R不变不变不变不变，信道容量大者，信道容量大者，信道容量大者，信道容量大者其可靠性函数其可靠性函数其可靠性函数其可靠性函数E E(R R)也也也也大；大；大；大；n nC C不变不变不变不变，码率减小时其，码率减小时其，码率减小时其，码率减小时其可靠性函数可靠性函数可靠性

25、函数可靠性函数E E(R R)增大增大增大增大 E(R)R0R1R2 C1 C2增大增大E(R)的途径的途径24普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2.1纠错编码的基本思路纠错编码的基本思路n n增大信道容量增大信道容量C n n扩展带宽扩展带宽扩展带宽扩展带宽n n加大功率加大功率加大功率加大功率n n降低噪声降低噪声降低噪声降低噪声n n减小码率减小码率R n nQQ、NN不变而减小不变而减小不变而减小不变而减小K K n nQQ、K K不变而增大不变而增大不变而增大不变而增大NNn nNN、K K不变而减小不变而减小不变而减小不变而减小QQn n增大码长增大码

26、长N 25普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.2.2最优译码与最大似然译码最优译码与最大似然译码n n译码器的任务译码器的任务是从受损的信息序列中是从受损的信息序列中尽可能正确地恢复出原信息。尽可能正确地恢复出原信息。n n译码算法的已知条件是：译码算法的已知条件是：n n实际实际接收到的码字序列接收到的码字序列r,r=(r1,r2,rN)n n发端所采用的编码算法和该算法产生的发端所采用的编码算法和该算法产生的码集码集XN,满足满足 n n信道模型及信道参数。信道模型及信道参数。26普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n最佳译码最佳译码

27、，也叫最大后验概率译码，也叫最大后验概率译码(MAP)n n最大似然译码最大似然译码(MLD)6.2.2最优译码与最大似然译码最优译码与最大似然译码消息组消息组mi码字码字ci接收码接收码r估值估值 消息消息编码器编码器 信道信道 译码译码 消息还原消息还原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)对

28、于任何对于任何对于任何对于任何r r都有相同的值，满足都有相同的值，满足都有相同的值，满足都有相同的值，满足P P(r r)=1/2)=1/2KK n n则则P(ci/r)最大等效于最大等效于P(r/ci)的最大，在此的最大，在此前提下最佳译码等效于最大似然译码。前提下最佳译码等效于最大似然译码。6.2.2最优译码与最大似然译码最优译码与最大似然译码28普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n对于无记忆信道，对于无记忆信道，n n例：例：BSC信道的最大似然译码可以简化为信道的最大似然译码可以简化为最最小汉明距离译码小汉明距离译码。n n汉明距离译码是一种硬判决译码。

29、由于汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。概，汉明距离译码也就是最佳译码。6.2.2最优译码与最大似然译码最优译码与最大似然译码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

30、 k维维维维n n重子空间？重子空间？重子空间？重子空间？n n如何寻找最佳的码空间？如何寻找最佳的码空间？如何寻找最佳的码空间？如何寻找最佳的码空间？n nq qk k个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。n n码率编码效率：码率编码效率：码率编码效率：码率编码效率：R Rc c =k k/n n 30普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6.3.1生成矩阵和校验矩阵生成矩阵和校验矩阵cmG1n1kkn码字码字消息消息生成矩阵生成矩阵Ggk-

31、1g1g0T，有，有k个个(1n)行行矢量，如何选择呢？矢量，如何选择呢？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个个个个基基基基底底底底的线性组合的线性组合的线性组合的线性组合n n由由由由于于于于k k个个个个基基基基底底底底即即即即GG的的的的k k个个个个行行行行矢矢矢矢量量量量线线线线

32、性性性性无无无无关关关关，矩矩矩矩阵阵阵阵GG的的的的秩一定等于秩一定等于秩一定等于秩一定等于k k。n n当当当当信信信信息息息息元元元元确确确确定定定定后后后后，码码码码字字字字仅仅仅仅由由由由GG矩矩矩矩阵阵阵阵决决决决定定定定，因因因因此此此此我我我我们们们们称称称称这这这这k k n n 矩矩矩矩阵阵阵阵GG为为为为该该该该(n,kn,k)线线线线性性性性分分分分组组组组码码码码的的的的生生生生成成成成矩矩矩矩阵。阵。阵。阵。32普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著生成矩阵生成矩阵G(kn)的特点的特点n n想要保证想要保证(n,k)线性分组码能够构成线性分组

33、码能够构成k维维n重子空间，重子空间，G的的k个行矢量个行矢量g gk k-1-1,g,g1 1,g,g0 0必必须是线性无关的，只有这样才符合作为基须是线性无关的，只有这样才符合作为基底的条件。底的条件。n n由于基底不是唯一的，所以由于基底不是唯一的，所以G也就不是唯一也就不是唯一的。的。n n不同的基底有可能生成同一码集，但因编不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。映射方法不同也不能说是同样的码。33普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著系统形式的生成矩阵系统形式的

34、生成矩阵(n,kn,k)码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算（以及列置换）简化成（以及列置换）简化成（以及列置换）简化成（以及列置换）简化成“系统形式系统形式系统形式系统形式”。G=IG=Ik k P=P=I Ik k是是是是kkkk单位矩阵，单位矩阵，单位矩阵，单位矩阵，P P是是是是k k(n-kn-k)矩阵。矩阵。矩阵。矩阵。34普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著生成的码字生成的码字Cn n前前前前k k位由单位矩阵位由单位矩阵位由单位矩阵位由单位矩阵I Ik k决定，等

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

36、则生成的码叫做不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做非系统码非系统码非系统码非系统码。n n系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。35普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著系统码系统码n n若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵GG互等，互等，互等，互等，则称这两个则称这两个则称这两个则称这两个GG等效等

37、效等效等效。n n非系统码的非系统码的非系统码的非系统码的GG可通过运算转变为系统码的可通过运算转变为系统码的可通过运算转变为系统码的可通过运算转变为系统码的GG。n n等效的两个等效的两个等效的两个等效的两个GG生成的两个生成的两个生成的两个生成的两个(n,kn,k)线性码也是等效的。线性码也是等效的。线性码也是等效的。线性码也是等效的。n n因此，每个因此，每个因此，每个因此，每个(n,kn,k)线性码都可以和一个系统的线性码都可以和一个系统的线性码都可以和一个系统的线性码都可以和一个系统的(n,kn,k)线性码等效。线性码等效。线性码等效。线性码等效。36普通高等教育“十五”国家级规划教

38、材信息论与编码 曹雪虹等编著空间构成空间构成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=0n维维n重空间重空间Vk维维k重重k维维n重重n-k维维信息组信息组码空间码空间n重重H空间空间mC37普

39、通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著校验矩阵校验矩阵n n将将将将HH空空空空间间间间的的的的n-kn-k个个个个基基基基底底底底排排排排列列列列起起起起来来来来可可可可构构构构成成成成一一一一个个个个(n-n-k k)n n矩矩矩矩阵阵阵阵，称称称称为为为为校校校校验验验验矩矩矩矩阵阵阵阵HH。用用用用来来来来校校校校验验验验接接接接收收收收到到到到的码字是否是正确的；的码字是否是正确的；的码字是否是正确的；的码字是否是正确的；n nGG是是是是(n,kn,k)码的生成矩阵，码的生成矩阵，码的生成矩阵，码的生成矩阵，HH是它的校验矩阵；是它的校验矩阵；是它的校验矩阵；是

40、它的校验矩阵；n nHH是是是是(n,n-kn,n-k)对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是一个基底。一个基底。一个基底。一个基底。GG则是它的校验矩阵。则是它的校验矩阵。则是它的校验矩阵。则是它的校验矩阵。n nGHGHT T=0=0，HH PPT TI In-kn-k，二进制时，负号，二进制时，负号，二进制时，负号，二进制时，负号可省略。可省略。可省略。可省略。38普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n例例6-2(6,3)线性分组码，其生成矩阵是线性分组码，其生成矩阵是 G=求：

41、求：(1)(1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。(2)(2)将该码系统化处理后，计算系统码码集并列出将该码系统化处理后，计算系统码码集并列出将该码系统化处理后，计算系统码码集并列出将该码系统化处理后，计算系统码码集并列出映射关系。映射关系。映射关系。映射关系。(3)(3)计算系统码的校验矩阵计算系统码的校验矩阵计算系统码的校验矩阵计算系统码的校验矩阵HH。若收码。若收码。若收码。若收码r=100110,r=100110,检验它是否码字？检验它是否码字？检验它是否码字？检验它是

42、否码字？(4)(4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。11101011000101110139普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6-2 码集与映射关系码集与映射关系信息码字系统码字00000000000000000101110100101101011000101011001110110001110110011101010011110110011110110011000101111000111101011011101040普通高等教育“十五”国家级规

43、划教材信息论与编码 曹雪虹等编著例例6-2 二元二元(6,3)线性分组码编码器线性分组码编码器 m0m1m2输入输出 c0c1c241普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著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,r r0 0c c0

44、 0)二进制码中模二进制码中模二进制码中模二进制码中模2 2加与模加与模加与模加与模2 2减是等同的，因此有减是等同的，因此有减是等同的，因此有减是等同的，因此有E=RE=RCC及及及及R=CR=CEE 42普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著伴随式伴随式S的定义的定义因为因为因为因为CHCHT T=0=0所以所以所以所以RHRHT T(C(CE)HE)HT TCHCHT TEHEHT T=EH=EHT T如果收码无误：必有如果收码无误：必有如果收码无误：必有如果收码无误：必有R RC C即即即即E E0 0，则则则则EHEHT T=0RH=0RHT T=0=0。如果收

45、码有误：即如果收码有误：即如果收码有误：即如果收码有误：即EE 0 0，则则则则RHRHTT=EH=EHT T 0 0。在在HT固定的前提下，固定的前提下，RHT仅仅与差仅仅与差错图案错图案E有关，而与发送码有关，而与发送码C无关。定义无关。定义伴随式伴随式SS=(sn-k-1,s1,s0)=RHT=EHT43普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n从物理意义上看，伴随式从物理意义上看，伴随式从物理意义上看，伴随式从物理意义上看，伴随式S S并不反映发送的码字是并不反映发送的码字是并不反映发送的码字是并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。什么，

46、而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。n n差错图案差错图案差错图案差错图案E E是是是是n n重矢量，共有重矢量，共有重矢量，共有重矢量，共有2 2n n个可能的组合，而个可能的组合，而个可能的组合，而个可能的组合，而伴随式伴随式伴随式伴随式S S是是是是(n-kn-k)重矢量，只有重矢量，只有重矢量，只有重矢量，只有2 2n-kn-k个可能的组合，个可能的组合，个可能的组合，个可能的组合，因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。因此不同

47、的差错图案可能有相同的伴随式。n n接收端收到接收端收到接收端收到接收端收到R R后，因为已知后，因为已知后，因为已知后，因为已知HHT T，可求出，可求出，可求出，可求出SSRHRHT T；如果能知道对应的如果能知道对应的如果能知道对应的如果能知道对应的E E，则通过，则通过，则通过，则通过C=RC=RE E而求得而求得而求得而求得C C。RHRHT T=S=S?C=R?C=REERSECRSEC只要只要只要只要E E正确，译出的码也就是正确的。正确，译出的码也就是正确的。正确，译出的码也就是正确的。正确，译出的码也就是正确的。伴随式伴随式S的意义的意义44普通高等教育“十五”国家级规划教材

48、信息论与编码 曹雪虹等编著差错图案差错图案E的求解的求解(1)可以通过解线性方程求解可以通过解线性方程求解可以通过解线性方程求解可以通过解线性方程求解E E：S=(S=(s sn-k-n-k-1 1,s s1 1,s s0 0)=EH)=EHT T=(=(e en n-1-1,e e1 1,e e0 0)得到线性方程组：得到线性方程组：得到线性方程组：得到线性方程组：s sn-k-n-k-1 1=e en n-1-1h h(n-k-n-k-1)(1)(n n-1)-1)+e e1 1h h(n-k-n-k-1)11)1+e e00h h(n-k-n-k-1)01)0 s s11=e en n-

49、1-1h h1(1(n n-1)-1)+e e11h h1111+e e00h h1010s s00=e en n-1-1h h0(0(n n-1)-1)+e e11h h0101+e e00h h000045普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n上述方程组中有上述方程组中有上述方程组中有上述方程组中有n n个未知数个未知数个未知数个未知数e en n1 1,e,e1 1,e,e0 0，却，却，却，却只有只有只有只有n-kn-k个方程，可知方程组有多解。个方程，可知方程组有多解。个方程，可知方程组有多解。个方程，可知方程组有多解。n n在有理数或实数域中，少一个方程

50、就可能导致在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少n-n-(n-k n-k)=)=k k个方程导致每个未知数有个方程导致每个未知数有个方程导致每个未知数有个方程导致每个未知数有2 2k k个解。个解。个解。个