长江大学信息论与编码典型例题

1、例题例1简述最大离散熵定理。对于一个有m个符号的离散信源，其最大熵是多少?解：最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。最大熵值为H max log2 m。例2什么是平均自信息(信息熵)？什么是平均互信息？比较一下两个概念的异同之处。解：平均自信息为 H(X)p(Xi) log p(Xi)iP(Xiyj)logP(x I yj)P(Xi)平均互信息为l(X;Y)表示从Y获得的关于每个表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。x的平均信息量，也表示发X前后丫的平均不确定性减少的量,还表示通信前后整个系统不确定性减少的量。例3解释等长信源编码定理和无失真变长信源编码

2、定理，说明对于等长码和变长码，最佳 码的每符号平均码长最小为多少？编码效率最咼可达多少？解：等长信源编码定理：对于任意 时必可使译码差错<。>0,K>0,只要 log mLHl(X)，则当L足够长变长信源编码定理：只要H(X)log m等长码和变长码的最小平均码长均为K ()1, 一定存在一种无失真编码。log mH (X)，编码效率最咼可达 100%。log m例4解释最小错误概率译码准则，最大似然译码准则和最小距离译码准则，说明三者的关 系。解：最小错误概率译码准则下，将接收序列译为后验概率最大时所对应的码字。最大似然译码准则下，将接收序列译为信道传递概率最大时所对应的码

3、字。最小距离译码准则下，将接收序列译为与其距离最小的码字。三者关系为：输入为等概率分布时，最大似然译码准则等效于最小错误概率译码准则。 在二元对称无记忆信道中，最小距离译码准则等效于最大似然译码准则。源，其失真矩阵DP例5什么是保真度准则？对二元信P(X)求a 0a>0时率失真函数的 Dmin和Dmax ？ 解：1)保真度准则为：平均失真度不大于允许的失真度。2)因为失真矩阵中每行都有一个0,所以有Dmin 0，而Dmax min( 1 p)a, pa。例6 一平稳二元信源，它在任意时间，不论以前发出过什么符号，都按p(0)0.4, p(1) 0.6发出符号，求H(X2),H(X3以必2

4、)和平均符号熵1lim H (X1X2 XN)N N解: H(X2)2H(X)1.942 bit/2 个符号H(X3 | X1X2) H(X3)0.971 bit/ 符号1 1lim H (X1X2 Xn ) lim NH (X) H(X) 0.971 bit/ 符号 N NN N例7分别说明信源的概率分布和信道转移概率对平均互信息的影响，说明平均互信息与信 道容量的关系。解：平均互信息相对于信源概率分布为上凸函数，相对于信道传递概率分布为下凹函数。平 均互信息的最大值为信道容量。例8二元无记忆信源，有p(0)0.25, p(1) 0.75求:(1 )某一信源序列由100个二元符号组成，其中有

5、 m个“ 1”，求其自信息量?(2) 求100个符号构成的信源序列的熵。解: 1)p(a) p(0)100 m p(1)m 0.25100 m 0.75mI (a) log 2 p(a) 200 mlog2 3log2 42 bit/ 符号。C1 maxH(X)P2为具有归并性能的信道，因此有 C2P3为具有发散性能的信道，因此有 C3max H (Y) log2 3 1.5995 bit/ 符号。 max H (X) log2 31.5995 bit/ 符号。例10写出香农公式，并说明其物理意义。当信道带宽为5000Hz，信噪比为30dB时求信道容量。解：香农公式为CtTim 1 N0Wbi

6、t/s，它是高斯加性白噪声信道在单位时间内的信道2)H(X100 )100H(X)81.128 bit/ 序列1000010100例9求以下三个信道的信道容量：P11000P2010000101001000010010.10.2 0.3 0.4000000P300000.30.700000 0 0 0000.40.20.10.3解：R为一一对应确定信道，因此有容量，其值取决于信噪比和带宽。由 10lgPN0WP30dB 得 NW1000，则 Ct5000 log 2(1 1000)49836bit / s例11二元平稳马氏链，已知P(0/0)=0.9，P( 1/1)=0.8，求：(1) 求该马

7、氏信源的符号熵。(2) 每三个符号合成一个来编二进制Hufman码，试建立新信源的模型，给出编码结果。(3) 求每符号对应的平均码长和编码效率。解：1)由眾常罗P(1)P(0|1)得极限概率P(0)2/3P(1)1/3则符号熵为H H0.5533bit/符号2)新信源共8个序列，各序列的概率为 P(X1X2X3) P(X1)P(X2 | X1)P(X3 |X1X2)信源模型为0000010100111001011101110.540.060.0130.053 0.060.0070.0530.313一种编码结果（依信源模型中的序列次序）100011为 0, 11, 1001, 1010, 101

8、1, 10000, 100010,3) K1P(aJKj0.682 bit/ 符号3 i 1HK log 2 281.1%X例12信源空间为s1 s2S3S4S5S6S7s8试分别构P(X)0.4 0.20.10.10.050.050.050.05造二兀和三兀霍夫曼码，计算其平均码长和编码效率。解：1）二元码的码字依序为：10, 11,010,011 ,1010,1011,1000,1001 o平均码长L=2.6bit/符号，编码效率=0.972）三元码的码字依序为：1, 00,02,20,2122,010,011 o平均码长L=1.7bit/符号，编码效率=0.93(6100101例13设线

9、性分组码的生成矩阵为G010110 ,求:001011（1 ）此（n, k）码的n= ? k= ?，写出此（n, k）码的所有码字。（2）求其对应的一致校验矩阵Ho（3）确定最小码距，问此码能纠几位错？列出其能纠错的所有错误图样和对应的伴随式。（4）若接收码字为000110，用伴随式法求译码结果。解：1） n=6, k=3，由C=mG可得所有码字为：000000, 001011, 010110, 011101 , 100101, 101110, 110011, 1110001012)此码是系统码，由G知，P110，则01111 0 100H PT|01 1 01010 1 0013)由H可知，

10、其任意2列线性无关，而有3列线性相关，故有dmin3，能纠一位错。错误图样E伴随式SEHT1000001010100001100010000110001001000000100100000010014)由 S rH T 110知 E= 010000,则 R r E 0101100.9 0.1例14二元对称信道的信道矩阵为，信道传输速度为1500二元符号/秒，设信源0.1 0.9为等概率分布，信源消息序列共有13000个二元符号，问：(1) 试计算能否在10秒内将信源消息序列无失真传送完？(2) 若信源概率分布为p(0) 0.7, p(1)0.3，求无失真传送以上信源消息序列至少需要多长时间？解

11、：1)信道容量为C 1 H (0.9.0.1)0.531bit/符号信源序列信息量为13000 H (0.5,0.5)7965bit而10秒内信道能传递的信息量为1500 10 0.53仁7965bit故不能无失真地传送完。2)此时信源序列信息量为13000 H (0.3,0.7)11456.77bit信息传输率为Rp(Xiyj)log2i 1 j 1p(yj |Xi)20.4558 bit/ 符号p(Xkyj)k 1则 T 11456.7716.7567s0.4558 1500例15已知(7，4)循环码的生成多项式 g(x) X3 X 1，求:(1) 求该码的编码效率？(2) 求其对应的一致

12、校验多项式h(x)解：1) n7,k4,k 57.14%n2) h(x)x714 X2XX1g(x)6 X43XX1011005 X32XX0101103) G(x)42 1 XX，G001011X3 XX 1000101(3) 写出该码的生成矩阵，校验矩阵。(4) 若消息码式为 m(x) 1 x x2，求其码字。00而011110 10 00 1110 100 0 1110 14) C(X)54m(x)g(x) x x 1,C0110001例16黑白气象传真图的消息只有黑色和白色两种，求:1)黑色出现的概率为0.3，白色出现的概率为0.7。给出这个只有两个符号的信源X的数学模型。假设图上黑白

13、消息出现前后没有关联，求熵；0.8，求其熵 H2(X)； a2白0.72)假设黑白消息出现前后有关联，其依赖关系为：P(白/白)0.9，P(黑/白)0.1，P(白/黑)0.2，P(黑/黑)一q 黑解：1)信源模型为0.3H(X)p(aj log? p(aj 0.881bit/ 符号i 122)由 P(ai)r P(aj)P(ai laj)，l 1,2 得 p(白) 2 / 3, p(黑)1/3 p) p®)12 2则 H2(X)p(ajp(aj lajlog? p(aj |aj 0.5533 b it/ 符号i 1 j 1例17二元对称信道如图。1) 若 p(0)0.73, p(1)

14、0.25，求 H (X)和l(X;Y);2）求该信道的信道容量和最佳输入分布。解：1)H (X)0.8113 bit/ 符号可=0=0I(X;Y) 0.0616 bit/ 符号2)C 0.082 b it/符号，最佳输入概率分布为等概率分卜布。1000011101000100例18已知一（8，5）线性分组码的生成矩阵为°01000100001000100001111求：1）输入为全00011和10100时该码的码字；2）最小码距。解：1）输入为00011时，码字为00011110;输入为10100时，码字为10100101。75%是身高160厘米以上的，“身高160厘米以上的某女孩X

15、X1 （是大学生）X2 （不是大学生）P(X)0.250.752）d min 2例19居住某地区的女孩子有 25%是大学生，在女大学生中有 而女孩子中身高160厘米以上的占总数的一半。假如我们得知是大学生”的消息，问获得多少信息量？解：设随机变量X代表女孩子学历设随机变量Y代表女孩子身高Yy (身高 >160cm)y2 (身高 <160cm)P(Y)0.50.5已知：在女大学生中有 75%是身高160厘米以上的，即:p(y1 / 咅)0.75 bit即：1（为/力）logp（X1/yJ.p(X1)p(yJX1), 0.25 0.75bitloglog1.415 bitP(%)0.5

16、X例20设离散无记忆信源P（X）x-! 0 x2 1 x3 2 x4 31234，其发出的信息为3/81/41/41/8身高160厘米以上的某女孩是大学生的信息量，求(1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？解：(1)此消息总共有14个0、13个1、12个2、6个3，因此此消息发出的概率是:14253184此消息的信息量是:618I log p87.811 bit(2)此消息中平均每符号携带的信息量是：|/n 87.811/45 1.951 bit例21同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求：(1) “3和5同时出现”这事件的自信息；(2

17、) “两个1同时出现”这事件的自信息； 两个点数的各种组合(无序)对的熵和平均信息量；(4) 两个点数之和(即2, 3,，12构成的子集)的熵；(5) 两个点数中至少有一个是1的自信息量。p( Xi)11 111解：(1)66 6618I(Xi)log p(Xi)1 log 184.170 bit11 1p(Xi)6636I(Xi)log p(Xi)1log365.170 bit两个点数的排列如下：111213141516212223242526313233343536414243444546515253545556616263646566共有21种组合:1 1 1其中11, 22, 33, 44, 55, 66的概率是6 6361 1 1其他15个组合的概率是2 -6 6 181 1 1 1H (X)p(xjlog p(xj6 log 15 log 4.337 bit / symboli36361818(4)参考上面的两个点数的排列，可以得出两个点数求和的概率分布如下：X2345678910 1112zx丄丄丄1_5_1_5_11 1丄P(X)36 18 12936636912 1