信息论与编码第六章课后习题答案(曹雪虹).doc

第六章：信道编码(本章复习大纲我重新修改了一下，尤其要关注红色内容)
1、基本概念：差错符号、差错比特；差错图样：随机差错、突发差错；纠错码分类：检错和纠错码、分组码和卷积码、线性码与非线性码、纠随机差错码和纠突发差错码；矢量空间、码空间及其对偶空间；
有扰离散信道的编码定理：（掌握信道编码定理的内容及减小差错概率的方法）；线形分组码的扩展与缩短（掌握奇偶校验码及缩短码的校验矩阵、生成矩阵与原线形分组码的关系）。
2、线性分组码(封闭性)：生成矩阵及校验矩阵、系统形式的G和H、伴随式与标准阵列译码表、码距与纠错能力、完备码(汉明码)、循环码的生成多项式及校验多项式、系统形式的循环码。
作业：6-1、6-3、6-4、6-5和6-6选一、6-7 6-8和6-9选一
6-1 二元域上4维4重失量空间的元素个数总共有24=16个，它们分别是(0,0,0,0),(0,0,0,1)…(1,1,1,1)，它的一个自然基底是(0,0,0,1),(0,0,1,0),(0,1,0,0)和(1,0,0,0)；其中一个二维子空间含有的元素个数为22个，选取其中一个自然基底为(0,0,0,1)和(0,0,1,0)，则其二维子空间中所包含的全部矢量为(0,0,0,0,),(0,0,0,1),(0,0,1,0)和(0,0,1,1)(注选择不唯一)；上述子空间对应的对偶子空间可以有三种不同的选择：(0,0,0,0) ,(0,1,0,0),(1,0,0,0)，(1,1,0,0)或(0,0,0,0) ,(0,1,0,0)或(0,0,0,0) (1,0,0,0)。(注意本题中所包含的关于矢量空间的一些基本概念)
6-3 由题设可以写出该系统(8,4)码的线形方程组如下：
(注：系统码高四位与信息位保持一致，ui为信息位)
把上述方程组写成矩阵形式，可以表示为 V=UG，其中V为码字构成的矢量，即V=(v7,v6,v5,v4,v3,v2,v1,v0)，U为信息位构成的矢量，即U=( u3,u2,u1,u0)，观察方程组可得系统生成矩阵为：

由系统生成矩阵和校验矩阵的关系可得：

由校验矩阵可以看出，矩阵H的任意三列都是线性无关的(任意三列之和不为0)，但存在四列线性相关的情况(如第1、5、6、8列，这四列之和为0)，即校验矩阵H中最小的线性相关的列数为4，从而得该线性分组码的最小码距为4。(注意：书上定理6.3的结论是错误的，正确的结论是线性分组码的最小码距为校验矩阵中最小的线性相关的列数)。
该编码器的硬件逻辑连接图略(用WORD画图比较麻烦，希望同学们自己把硬件电路图画一下，主要考查数字电路一些知识点，其他画硬件逻辑电路图题目也要自己画)。
6-4 在例6-4中，该(7,4)汉明码对应的校验矩阵为：
由(7,4)码进行第一次缩减可得(6,3)码，该(6,3)校验矩阵为(校验矩阵H删除第一列)：；对缩减后的(6,3)码再进行一次缩减可得(5,2)码，(5,2)码的校验矩阵(H1删除第一列)：(系统形式)，其系统形式的生成矩阵为：。
6-6 (1)(系统形式的生成矩阵);
(2) 由系统形式的生成矩阵和校验矩阵的关系可得，校验矩阵为
(系统形式)；
(3) 由标准阵列译码表的构造可知，该码表应该有2(n-k)=16行(伴随式的个数)和2k=8列(发送码字的个数)，由C=mG可以得出发送的码字为(0,0,0,0,0,0,0)、(0,0,1,1,1,1,0)、(0,1,0,0,1,1,1)、(0,1,1,1,0,0,1)、(1,0,0,1,1,0,1)、(1,0,1,0,0,1,1)、(1,1,0, 1,0,1,0)和(1,1,1,0,1,0,0)。该(7,3)码的伴随式为(0,0,0,0)、(0,0,0,1)、(0,0,1,0)…(1,1,1,1)(16个)。由伴随式和差错图案的对应关系S=EHT可得：当差错图案为E0=(0,0,0,0,0,0,0)(全零)时，伴随式为S0=(0,0,0,0)；当差错图案中有一位发生错误时(共有种可能)，差错图案与伴随式的对应关系为：E1=(0,0,0,0,0,0,1) S1=(0,0,0,1)
E2=(0,0,0,0,0,1,0) S2=(0,0,1,0)
E3=(0,0,0,0,1,0,0) S3=(0,1,0,0)
E4=(0,0,0,1,0,0,0) S4=(1,0,0,0)
E5=(0,0,1,0,0,0,0) S5=(1,1,1,0)
E6=(0,1,0,0,0,0,0) S6=(0,1,1,1)
E7=(1,0,0,0,0,0,0) S7=(1,1,0,1);
当差错图案中有两位发生错误时(共有种可能，只需列出其中的16-8=8种可能即可)，这时差错图案与伴随式(必须与已求出的伴随式不同)的对应关系为：E8=(0,0,0,0,0,1,1) S8=(0,0,1,1)
E9=(0,0,0,0,1,1,0) S9=(0,1,1,0)
E10=(0,0,0,1,1,00) S10=(1,1,0,0)
E11=(0,1,1,0,0,0,0) S11=(1,0,0,1)
E12=(1,1,0,0,0,0,0) S12=(1,0,1,0)
E13=(1,0,0,1,0,0,0) S13=(0,1,0,1)
E14=(1,0,1,0,0,0,0) S14=(1,0,1,1)
E15=(1,0,0,0,0,1,0) S15=(1,1,1,1)
按照标准阵列译码表的构造，列出该(7,3)码的结构为：
S0(0000)
C0+E0=C0
(0000000)
C1+E0=C1
(0011110)
C2+E0=C2
(0100111)
C3+E0=C3
(0111001)
C4+E0=C4
(1001101)
C5+E0=C5
(1010011)
C6+E0=C6
(1101010)
C7+E0=C7
(1110100)
S1(0001)
C0+E1=E1
(0000001)

S2(0010)
C0+E2=E2
(0000010)

S3(0100)
C0+E3=E3
(0000100)

S4(1000)
C0+E4=E4
(0001000)

S5(1110)
C0+E5=E5

(0010000)

S6(0111)
C0+E6=E6
(0100000)

S7(1101)
C0+E7=E7
(1000000)

S8(0011)
C0+E8=E8
(0000011)

S9(0110)
C0+E9=E9
(0000110)

S10(1100)
C0+E10=E10
(0001100)

S11(1001)
C0+E11=E11
(0110000)

S12(1010)
C0+E12=E12
(1100000)

S13(0101)
C0+E13=E13
(1001000)

S14(1011)
C0+E14=E14
(1010000)

S15(1111)
C0+E15=E15
(1000010)

表格中的元素(第一列除外)为所有可能接收到的码序列，共有2n=128种可能，其中接收码序列(表格空白地方需同学们自己计算)。表格第一行为发送码字，第一列和第二列为伴随式及其最小汉明距离对应的差错图案。表中每一行称为一个陪集，陪集头为对应的差错图案；每一列为一个子集，子集首为对应的发送码字。
(4) 由校验矩阵可以看出该校验矩阵的任意3列线性无关，存在4列(如第1、4、5、7)线性相关，即矩阵H的最小的线性相关的列数为4，故最小码距dmin为4。
(5) 由系统形式的生成矩阵和C=mG’可得，当信息序列m=(101)时，对应的码字为C=(1010011)，这时CHT=(0000)，故码字与校验矩阵H正交。(标准阵列译码表是重点，请务必掌握这种题型！)
6-7 (1)设计系统(15,11)汉明码：
对于(15,11)汉明码，其校验矩阵H为4行15列矩阵，即H每一列有4个元素，在二元域内，4个元素共有24=16种组合，除去全0(即0000)组合外，所有不为零组合共有15种可能。所以校验矩阵每一列可全部排列4个元素中所有不为零组合，所以校验矩阵为：
，通过列置换转换为系统形式可得，再由线性分组码系统形式的生成矩阵和校验矩阵的关系，可得该汉明码的系统生成矩阵为：

(2)设计(15,11)循环汉明码
由题设知 (15,11)循环码的生成多项式为: g(x)=x4+x+1
(a) 将信息多项式m(x)乘上xn-k(这里n=15, k=11), 不妨选取m=(10000000000), 即m(x)= x10，这时m(x)xn-k=x14；
(b) 将m(x)xn-k除以g(x)得余式r(x)：r(x)=x3+1；
(c) 信息序列m=(10000000000)对应的码多项式为：
C(x)= m(x)xn-k+r(x)= x14+x3+1，对应码矢量为(100000000001001)。按照同样的方法，可以求出由信息位组成的10种其他自然基底及它们对应的码字，从而得到该循环码的11个线性无关的基底。(这样选择信息位有什么好处？)信息位和基底的对应关系如下：
信息位 系统码字
(10000000000) (100000000001001)
(01000000000) (010000000001101)
(00100000000) (001000000001111)
(00010000000) (000100000001110)
(00001000000) (000010000000111)
(00000100000) (000001000001010)
(00000010000) (000000100000101)
(00000001000) (000000010001011)
(00000000100) (000000001001100)
(00000000010) (000000000100110)
(00000000001) (000000000010011)
把上述11个码字(线性无关的)作为基底构成循环码的生成矩阵(系统的)，即：
(未填元素为0)，由生成矩阵G’即可生成系统形式的循环汉明码，可以验证由G’生成的汉明码既是系统的，码字又具备循环特性；而由G生成的汉明码尽管也是系统的，但码字不具备循环特性。
说明：因为第6章作业没有进行讲解，所以答案比较详细需要说明的是：课后作业类似的习题，参考答案只给出了其中一道题的答案，并不说明只考有答案的题目，其他类题自己结合参考答案自行解决！