信息论与编码试题集与答案讲解

1、一填空题（本题20分，每小题2分）Hg = -fpdjbgp（叩1平均自信息为-表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。 心）=-yy?（口）bg p;?平均互信息-:表示从丫获得的关于每个X的平均信息量，也表示发X前后丫的平均不确定性减少的量，还表示通信前 后整个系统不确定性减少的量。2、最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。3、最大熵值为4、通信系统模型如下:噪声bitfs为保证足够大的信道容量,可采用（1）用频带换信噪比;Ct lim =障log1 +5、香农公式为I（2）用信噪比换频带6、只要;，当N足够长时，一定存在一种无失真编码。7、当Rv C

2、时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8在认识论层次上研究信息的时候，必须同时考虑到 形式、含义和效用 三个方面的因素。9、1948年，美国数学家 香农 发表了题为“通信的数学理论”的长篇论文，从而创立了信息论 按照信息的性质，可以把信息分成 语法信息、语义信息和语用信息 。按照信息的地位，可以把信息分成客观信息和主观信息。人们研究信息论的目的是为了 高效、可靠、安全 地交换和利用各种各样的信息。信息的 可度量性 是建立信息论的基础。统计度量是信息度量最常用的方法。熵 是香农信息论最基本最重要的概念。事物的不确定度是用时间统计发生概率的对数来描述的。10

3、、 单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量 描述。11、 一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对数的负值。12、自信息量的单位一般有 比特、奈特和哈特。13、必然事件的自信息是0。14、 不可能事件的自信息量是s。15、 两个相互独立的随机变量的联合自信息量等于两个自信息量之和。16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均 互信息量趋于变小 。17、离散平稳无记忆信源X的N次扩展信源的熵等于离散信源 X的熵的N倍。18、 离散平稳有记忆信源的极限熵，出：=何：屮风以必2 X。19、对于n

4、元m阶马尔可夫信源，其状态空间共有 nm个不同的状态。20、 一维连续随即变量X在a，b区间内均匀分布时，其信源熵为log2 (b-a)。1log 2 2二 eP21、 平均功率为P的高斯分布的连续信源，其信源熵，Hc (X) =2。22、对于限峰值功率的N维连续信源，当概率密度 均匀分布 时连续信源熵具有最大值。23、 对于限平均功率的一维连续信源，当概率密度高斯分布 时，信源熵有最大值。24、 对于均值为0,平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值P和信源的熵功率P之比25、若一离散无记忆信源的信源熵 H (X)等于2.5，对信源进行等长的无失真二进制编码，则编码长度至少

5、为3nZ m n 1对应的二元序 列的编码效率为n，则三者的关系是 n 0 n n 1。在实际的游程编码过程中，对长码一般采取截断 处理的方法。“0”游程和“ 1”游程可以分别进行哈夫曼编码，两个码表中的码字可以重复，但C码 必须不同。在多符号的消息序列中，大量的重复出现的，只起占时作用的符号称为“冗余变换”即：将一个冗余序列转换成一个二元序列和一个L-D编码是一种分帧传送冗余位序列的方法。L-D编码适合于冗余位较多或较少的情况。信道编码的最终目的是提高信号传输的可靠性狭义的信道编码即：检、纠错编码BSC信道即：无记忆二进制对称信道n位重复码的编码效率是1/n。等重码可以检验 全部的奇数位错和

6、部分的偶数位错85、86、87、8889、90、91、92、93、94、95、96、97、9899、任意两个码字之间的最小汉明距离有称为码的最小距若纠错码的最小距离为若检错码的最小距离为线性分组码是同时具有dmin，冗余位缩短了的多元序列。,mi nd(c,c)贝U dmin= cdmin -12-个差错dmi n,则可以纠正任意小于等于t=dmi n，则可以检测出任意小于等于l= dmi n-1 个差错。 分组特性和线性特性的纠错码。100、循环码即是采用循环移位特性界定的一类线性分组码。1. 信息的基本概念在于它的不确定性 。2. 按照信源发出的消息在时间和幅度上的分布情况，可将信源分成离

7、散 信源和 连续信源两大类。3. 个随机事件的自信息量 定义为其出现概率对数的负值。4. 按树图法构成的码一定满足 即时码的定义。5. 有扰离散信道编码定理称为香农第二极限定理。6. 纠错码的检、纠错能力是指 检测、纠正错误码元的数目。7. 信道一般指传输信息的物理媒介，分为有线 信道和 无线 信道。8. 信源编码的主要目的是 提高通信系统的有效性。1 .设X的取值受限于有限区间a,b ,则X服从 均匀 分布时，其熵达到最大；如 X的均值为, 方差受限为二2，则X服从 高斯 分布时，其熵达到最大。2. 信息论不等式：对于任意实数 z 0，有In z汐一1，当且仅当z = 1时等式成立。3. 设

8、信源为X=0，1，P （0） =1/8，则信源的熵为1/8呱8 7/8log2（7/8）比特/符号，如信源发出由m个“0”和（100-m）个“ 1”构成的序列，序列的自信息量为mlog2 8 （100一 m）Iog2（7/8）比特/符号。4. 离散对称信道输入等概率时，输出为等概 分布。5. 根据码字所含的码元的个数，编码可分为定长 编码和 变长 编码。6. 设DM助U1U2U3U4U5U6用二元符号表X=X1=0x=1对其进行定Pu 一 0.37 0.250.18 0.10 0.07 0.03_长编码，若所编的码为000,001,010,011,100,101，则编码器输出码元的一维概率 P

9、（xJ= 0.747 ,P（x2）二 0.253。1. 在现代通信系统中，信源编码主要用于解决信息传输中的有效性，信道编码主要用于解决信息传输中的可靠性，加密编码主要用于解决信息传输中的安全性 。2. 离散信源 X = X1X2 X3 X4 ，则信源的熵为1.75bit/ 符号 。|p（x） 1/2 1/4 1/8 1/83. 对称DMC信道的输入符号数为n,输出符号数为 m,信道转移概率矩阵为pj，则该信道的容量为mC =log m 亠二 pij log pij。n4. 采用m进制编码的码字长度为K，码字个数为n,则克劳夫特不等式为Ki 2进制的哈夫曼码时，要考虑是否需要增加概率为0的码字，

10、以使平均码长最短。对42、 游程序列的熵（“0”游程序列的熵与“ 1”游程序列的熵的和）大于等于原二元序列的熵。错43、 在游程编码过程中，“0”游程和“ 1”游程应分别编码，因此，它们的码字不能重复。错44、 L-D编码适合于冗余位较多和较少的情况，否则，不但不能压缩码率，反而使其扩张。对45、 狭义的信道编码既是指：信道的检、纠错编码。对46、 对于BSC言道，信道编码应当是一对一的编码，因此，消息m的长度等于码字c的长度47、 等重码和奇（偶）校验码都可以检出全部的奇数位错。对48、汉明码是一种线性分组码。对49、 循环码也是一种线性分组码。对50、 卷积码是一种特殊的线性分组码。错三、

11、计算题1. 设随机变量X =x1, x2 =0,1和 - y1, y2 - 0,1的联合概率空间为(xi,y2)gyj3/83/8XY _ (心)_PxY = _ 1/8定义一个新的随机变量z二X Y（普通乘积）1)计算熵 H (X), H (Y), H (Z), H (XZ,H (YZ,以及 H (XYZ；2)计算条件熵 H (X|Y), H( Y|X), H (X|Z), H (Z|X), H (Y|Z), H (Z|Y), H (X|YZ),以及 H ( Z|XY);3)计算平均互信息量I (X; Y), I (X: Z), I(Y: Z), I (X; Y|Z), I (Y; Z|X)

12、以及 I(Y|XZ),Z|Y)解：（1）XY0101/83/81/213/81/81/21/21/2H(X) =1/2log22 1/2log22=1H(Y) =1/2log22 1/2log22 =1110 111XYZ 000001010011100 1011/803/803/800 1/8Z 017/8 1/8H(Z) =7/8log2(8/7) 1/8log2 8XZ 000110111/203/8 1/8H(XZ) =1/2log2 2 3/8log2(8/3) 1/8log281/203/8 1/8H(YZ) =1/2log22 3/8log2(8/3) 1/8log28(2)H(

13、X|Y) -1/2(1/4log24 3/4log2(4/3) 1/2(1/4log2 4 3/4log2(4/3)H(Y|X) -1/2(1/4log24 3/4log2(4/3) 1/2(1/4log24 3/4log2(4/3)XZ0101/201/213/81/81/27/81/8H(X|Z)=7/8(4/7log2(7/4) 3/7log2(7/3) 1/8(0log20 1log21)H(Z |X) -1/2(1 log21 0log20) 1/2(3/4log2(4/3) 1/4log24)YZ0101/201/213/81/81/27/81/8H(Y|Z) =7/8(4/7lo

14、g2(7/4) 3/7 log2 (7/3) 1/8(0log2 0 1log2 1)H(Z |Y1/2(1log21 0log20) 1 /2(3/4log2(4/3) 1/4log24)H(X |YZ) =1/2(1/4log24 3/4log2(4/3) 3/8(1 log21 Olog?。)1/8(1 也1 OgO)H(Y | XZ) =1/2(1/4log2 4 3/4log2(4/3)3/8(1log21 0log20) - 1/8(1log2 V 0log20) H(Z | XY 0I(X;Y)二 H (X) -H (X |Y)I(X;Z) =H(X) -H(X |Z)l(Y;Z

15、) =H(Y) _H(Y|Z)I(X;Y|Z)二H(X |Z) -H(X |YZ)I(X;Z |Y) = H (X |Y) _H (X |ZY)2.设二元对称信道的输入概率分布分别为Px =3/41/4，转移矩阵为Pyix丄2/31/31/32/3(1) 求信道的输入熵，输出熵，平均互信息量;(2) 求信道容量和最佳输入分布;(3)求信道剩余度解：(1)信道的输入熵 H(X)=3/4log2(4/3) 1/4log2 4 ；_1/21/4Pxy电/12 1/6一PY二7/12 5/12H(Y) =7/12log2(12/7) 5/12log2 (12/5)H (Y | X) =3/4H(1/2

16、,1/4)1 /4H (1/12,1 /6)I(X;Y)二H(Y) -H(Y|X)(2)最佳输入分布为Px二1/2 1/2，此时信道的容量为C =1-H(2/3,1/3)信道的剩余度：C - l(X;Y)1/23.设有DMC，其转移矩阵为札x】=1/61/3 1/61/2 1/3，若信道输入概率为Px 1 - 0.5 0.25 0.251，.1/3 1/6 1/2试确定最佳译码规则和极大似然译码规则，并计算出相应的平均差错率11/41/61/12解: Pxy =1/241/81/121/121/241/8 一工(bjp最佳译码规则：F(b2)=a1，平均差错率为1-1/4-1/6-1/8=11

17、/24、F(b3)十3极大似然规则:F(bJ*F(b2)理)=二a2，平均差错率为=a3某系统(7, 4)码C =(C6C5C4C3C2C1Co) =(m3m2mo C2 C1 Co)其三位校验位与信息位的关系为:c2 = m3 mi m0* q = m3 十 m2 十 gc 0 = m2 + mo(1) 求对应的生成矩阵和校验矩阵；(2) 计算该码的最小距离；(3) 列出可纠差错图案和对应的伴随式;(4) 若接收码字R=111QQ11，求发码解：1.2.dmin = 3-100010G =001000Q11QQQ11Q11111Q13.SE00000000000010000001010000

18、0010100000010010100010001110010000011010000011010000004. RHt=OO1接收出错xY0101/31/31亠1/3E=QQQQQQ1R+E=C 1110010 (发码)四、计算题已知X,Y的联合概率p x, y为：求 H X，H Y，H X,Y，I X;Yp(y =0) =1/ 3 p(y =1) =2/3H X =H Y 二h(1/3,2/3) =0.918 bit/symbolH x,Y 二H(1/3,1/3,1/3)=1.585 bit/symbolI X;Y =H(x)H(Y)-H(X,Y) =0.251 bit/symbol五、计

19、算题一阶齐次马尔可夫信源消息集 X a1,a2,a3,状态集S S1,S2,S3，且令Sai,i =1,2,3，条件转移概率为P(aj/S|v3 13 1j3 ， (1)画出该马氏链的状态转移图;(2)计算信源的极限熵。解：(1)H(X|S1) = H1/4,1/4,1/2)=1.5比特/符号比特/符号H(XS) =H1/3,1/3,1/3)=1.585H = f wH (X |S. )=0.4 X1.5 +0.3x1.585+0.3x0.918 丄.351 比特 / 符号 i =1六、计算题若有一信源X2 I,每秒钟发出2.55个信源符号 P 一 p.8 0.2 一将此信源的输出符号送入某一

20、个二元信道中进行传输（假设信道是无噪无损的，容量为 1bit/二元符号），而信道每秒钟只传递2个二元符号。1）试问信源不通过编码（即X1 0,X2 1在信道中传输）2）能否直接与信道连接？3）若通过适当编码能否在此信道中进行无失真传输？4）试构造一种哈夫曼编码（两个符号一起编码），5）使该信源可以在此信道中无失真传输。解：1.不能，此时信源符号通过0,1在信道中传输，2.55二元符号/s2二元符号/s2.从信息率进行比较，2.55* H (0.8,0.2) = 1.84 1*2可以进行无失真传输0X1X1 0.6411X1X2 0.16100XX10.160101沁 0.0410.64 0.6

21、40* 0.361-0.200.13._4KpK =0.64 0.16*20.2*3 =1.56 二元符号 /2 个信源符号i i此时 1.56/2*2.55=1.989 二元符号 /s 2 二元符号 /s七、计算题两个BSC信道的级联如右图所示:(1) 写出信道转移矩阵；(2) 求这个信道的信道容量。解:(1)一1 一 ez 一1一P叮名 1一(1一 名)2+21- ； 2；(1 - ；)2(1 - )2 2 (1E)+ Z(2) C =log2 -H(1 - ；)2；2)4.设有DMC，其转移矩阵为lPY|X 11/21/61/31/31/21/61/61/3，若信道输入概率为1/2Px

22、丨二 0.5 0.25 0.251，试确定最佳译码规则和极大似然译码规则，并计算出相应的平均差错率。(1/41/61/12解: Pxy =1/241/81/121/121/241/8 一最佳译码规则：F(b2Ha1，平均差错率为1-1/4-1/6-1/8=11/24iF (b3)= a3极大似然规则：F(b2)=a2，平均差错率为1-1/4-1/8-1/8=1/2。iF (b3)= a31.设有一个二进制一阶马尔可夫信源，其信源符号为X (0,1)，条件概率为p(0/0)= p (1/0)=0.5 p(1/1)=0.25p(0/1)=0.75画出状态图并求出各符号稳态概率。(15分)0.75W

23、0 -0.5W00.75W1W0 W =1W0 =0.6W1 =0.42. 设输入符号与输出符号为X= 丫 0,1,2,3，且输入符号等概率分布。设失真函数为汉明失真。求Dnax和 Dnin 及 R( Dna)和 & gn)( 20 分)1解：P X。二 p 捲二 p X2 二 P X340 11110 11D =110 1.11 1 0 一失真矩阵的每一行都有0,因此din=0R Dmin 二R 0 二H X =log24=2bit/符号311113Dmax二qinp(Gd(Xi,yj) =411 1,4111,41 1 1i=0L444丿4R Dmax =0设随机变量X =X1,X2二0,

24、1和丫 =%,y2 =0,1的联合概率空间为XY_(X1,y1)(X1, y2)(X2,y1)(X2,y2)1H1/83/83/81/8 一定义一个新的随机变量Z=X Y(普通乘积)计算熵 H (X)，H (Y)，H (Z)，H (XZ)，H( YZ)，以及 H (XYZ ；计算条件熵 H (X|Y), H( Y|X)，H (X|Z)，H (Z|X)，H (Y|Z)，H (Z|Y)，H (X|YZ)，H (Y|XZ)以及 H (Z|XY)；计算平均互信息量 I (X；Y)，I (X：Z)，I (Y：Z)，I(X；Y|Z)，I(Y；Z|X)以及 I(X:,Z|Y )。解: (1)XY0101/8

25、3/81/213/1/1/8821/21/2H(X) =1/2log22 1/2log22=1H(Y) =1/2log22 1/2log22 =1XYZ 0000010100111001011101111/803/803/8001/8Z 017/8 1/8H(Z) =7/8log2(8/7) 1/8log2 8XZ000110111/203/81/8H(XZ) =1/2log2 2 3/8log2(8/3) 1/8log28YZ000110111/203/8 1/8H(YZ) =1/2log22 3/8log2(8/3) 1/8log28(2)H(X |Y) -1/2(1/4log24 3/4

26、log2(4/3) 1/2(1/4log2 4 3/4log2(4/3)H(Y|X) -1/2(1/4log24 3/4log2(4/3) 1/2(1/4log24 3/4log2(4/3)Z0101/201/213/81/81/27/81/8H(X|Z) =7/8(4/7log2(7/4) 3/7log2(7/3) 1/8(0log20 1log21)H(Z|X) =1/2(1log21 0log20) 1/2(3/4log2(4/3) 1/4log24)Z0101/201/213/81/81/27/81/8H(Y|Z) =7/8(4/7log2(7/4) 3/7log2(7/3) 1/8(

27、0log2。Ilog?。H(Z |Y) =1/2(1log21 0log20) 1 /2(3/4log2(4/3) 1/4log24)H(X |YZ) =1/2(1/4log24 3/4log2(4/3) 3/8(1 log21 Olog?。)1/8(1 也1 Olog?。)H(Y | XZ) =1/2(1/4log2 4 3/4log2(4/3)3/8(1log21 0log20)1/8(1log2 V 0log20) H (Z | XY0I(X;Y)二 H(X) -H(X |Y) I (X;Z)二 H (X) -H(X |Z)I (Y;Z) =H (Y) -H (Y |Z) l(X;Y|Z

28、) =H(X |Z) -H(X |YZ)I(X;Z |Y) =H (X |Y) -H (X |ZY)设二元对称信道的输入概率分布分别为Px打3/4 1/4，转移矩阵为_ 2/3 1/3-1/3 2/3一求信道的输入熵，输出熵，平均互信息量; 求信道容量和最佳输入分布；求信道剩余度。解：(1)信道的输入熵 H(X)=3/4log2(4/3) 1/4log24 ；Pxy二1/21/4Jj/12 1/6 一PY二7/12 5/12H(Y) =7/12log2(12/7) 5/12log2 (12/5)H (Y | X) =3/4H(1/2,1/4)1/4H (1/12,1/6)l(X;Y) =H(Y) -H(Y| X)2)最佳输入分布为Px二1/2 1/2，此时信道的容量为C =1-H(2/3,1/3)信道的剩余度：C l(X;Y)1/2 1/3 1