南邮信息论复习.pdf

结构： 一、填空题（20 分，每空 1 分） 二、判断题（10 分，每题 2 分，对的写“” ，错的写“” ） 三、计算题（70 分，每题 10 或 15 分） 分布： 第 2 章：离散单符号信源熵、条件熵、平均互信息量、马尔可夫信源极限熵的计算，30% 第 3 章：对称、准对称 DMC 信道、限时限频限功率加性高斯白噪声信道容量的计算，25% 第 4 章：离散信源信息率失真函数 R(D)的性质，定义域和值域，10% 第 5 章：无失真和限失真信源编码定理，二进制 Huffman 编码方法及编码效率计算，15% 第 6 章：信道编码定理，线性分组码编译码，循环码编码，20% 示例： 一、填空题 1从信息论的研究角度出发，通常可以将通信系统的性能指标归纳为：有效性、可靠性和 安全性，它们可以用三种不同的编码方法来实现，依次为：_ 信源编码 _、 信道编 码 和 加密编码 。 2同时掷两个正常的骰子，也就是各面呈现的概率都是 1/6，则“3 和 5 同时出现”事件的 自信息为 4.17 bit ， “两个 5 同时出现”事件的自信息为 5.17bit ，两个点数中至 少有一个是 1 的自信息为 1.7105bit 。 3如果X、Y相互独立，则I（X;Y）= 0 。另一方面，如果Y是X的一一对应函数，则 I（X;Y）= H(X) 或 H(Y) 。 4 带限AWGN波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公 式为： )1log( 0W N P WC S += ；若通频带W为 2MHz，信道上的信噪比为 10，则其信道容量为 6.91886 Mbps 。 5 设输入符号表为X0，1，输出符号表为Y0，1。输入信号的概率分布为p(1/2， 1/2)，失真函数为d(0，0) = d(1，1) = 0，d(0，1) =1，d(1，0) = 1.5，则Dmin 0 ， R(Dmin) 1bit/symbol ，相应的编码器转移概率矩阵p(y/x) 10 01 ；Dmax 1/2 ，R(Dmax) 0 ，相应的编码器转移概率矩阵p(y/x) 10 10 。 6若(7,3)循环码的 432 ( )1=+g xxxx，则对应校验多项式 h(x)= 32 1xx+ 。 7信源发出的消息在送入信道传输之前要经过信源编码、加密编码和信道编码，这分别是 为了保证通信系统的 有效性 、 安全性 和 可靠性 。 8在无失真的信源中，信源输出由 H(X) 来度量；在有失真的信源中，信源输出由 R(D) 来度量。 9. 带限AWGN波形信道在平均功率受限条件下信道容量的基本公式， 也就是有名的香农公式 为：_log(1)CWSNR=+_；当归一化信道容量Ct/W0 时，也即信道完全丧失了通信 能力，此时SNR为 -1.6dB ，我们将它称作香农限。 10. 已知信源 = 8 . 02 . 0 10 xx P X ， 转移概率矩阵 = 9 . 01 . 0 1 . 09 . 0 P ， 输出符号集 01 ,Yyy= ， 则 p(y0) 0.26 ，p(y1) 0.74 ，H(X) 0.7219 ，H(Y) 0.8267 ，H(Y/X) 0.4690 ；H(X/Y) 0.3642 ；I(X；Y) 0.3577 。 11已知n7 的循环码 42 ( )1=+g xxxx，则信息位长度k为 3 。 二、判断题 1唯一可译码一定是即时码。 （） 2连续信源的相对熵可以为负值。 （ ） 3只要传信率 R 大于信道容量 C，总存在一种信道码，并以所要求的任意小的 差错概率实现可靠的通信。 （） 4信息率失真函数 R(D)给出了保真度条件下，信源信息率可被压缩的最低限度。 （ ） 5只要传信率 R 小于信道容量 C，总存在一种信道码，并以所要求的任意 小的差错概率实现可靠的通信。 （ ） 6唯一可译码一定为非延长码。 （） 7信息率失真函数研究的是信道传输问题。 （） 8线性分组码的最小距离等于码集中码字的最小重量。 （） 三、计算题 1. 设信道的转移概率矩阵为 P 0 750 25 0 250 75 . . ， (1) 若p(x0)=0.8，p(x1)=0.2，求H（X） ，H（Y） ，H（X/Y） ，H（Y/X） 和 I（X；Y） ； (2) 求该信道的信道容量及其达到信道容量时输入符号的概率分布。 解: (1) () 0.60.2 0.050.15 p xy = , p(y)=0.65 0.35 ()()0.8,0.20.72H XH= 比特/符号 ( )()0.65,0.350.93H YH= 比特/符号 ()()/0.75,0.250.81H YXH=比特/符号 (8) (/)()(/)( ) 0.6/ H X YH XH YXH Y=+ =比特符 号 ()( )();/0.12I X YH YH YX=比特/符号 (2) C=1H(Y|X)= 0.19 比特/符号 p0=p1=0.5 (7) 2. 设某信道的转移概率矩阵 P = ， (1) 求该信道的信道容量； (2) 达到信道容量时的输入符号的概率分布。 解：(1) 分解为 log2(0.1,0.8,0.1)0.1log0.20.9log0.9 0.447/ CH bit = =符号 (7) (2) 输入等概分布，p0=p1=0.5 (3) 3. 一马尔可夫信源消息集 X 321 ,aaa，状态集 S 321 ,SSS。条件转移概率为 = 214141 412141 313131 )/( ij SaP， (1) 画出该马氏链的状态转移图； (2) 计算)/( 1 SXH、)/( 2 SXH、)/( 3 SXH； (3) 计算信源的极限熵。 解： (1) S1 S2S3 1 4 1 3 1 31 4 1 4 1 4 1 2 1 2 1 3 （4） (2) H(X|S1)=H(1/3,1/3,1/3)=1.58 比特/符号 H(X|S2)=H(1/4,1/2,1/4)=1.5 比特/符号= H(X|S3) （4） (3) 111 1231344 111 1232324 111 1233342 123 1 wwww wwww wwww www += += += += 3 111 4 211 4 311 w w w = = = 3 34 1111 1 (|)1.581.5 21.5232 ii i Hw H X S = =+= 比特/符号 （7） 4. 设有离散无记忆信源 123456 1/31/61/61/121/81/8 aaaaaa ， (1) 求信源的符号熵()H X; (2) 求相应的哈夫曼编码（写出编码过程，否则不得分）和对应的编码效率； (3) 求相应的香农编码（写出编码过程，否则不得分）和对应的编码效率。 解：(1) (X)(1/3,1/6,1/6,1/12,1/8,1/8)2.44HH= bit/符号 （2） (2) a1 a2 a3 a5 a6 a4 1/3 1/6 1/6 1/8 1/8 1/12 0 1 1/3 5/24 1/6 1/6 1/8 0 1 1/3 7/24 5/24 1/6 0 1 3/8 1/3 7/24 5/8 3/8 0 1 0 1 1 00 11 010 011 100 101 （7） 7 1 () ii i Kp a K = = 2.5 码元/符号 () 97.6% H X K = (3) 符号 概率 -log(p(ui) 码长 累加概率 码字 a1 1/3 1.6 2 0 00 a2 1/6 2.6 3 1/3 010 a3 1/6 2.6 3 1/2 100 a5 1/8 3.0 3 2/3 101 a6 1/8 3.0 3 19/24 110 a4 1/12 3.6 4 11/12 1110 7 1 () ii i Kp a K = = 2.75 码元/符号 （6） () 88.73% H X K = 5. 已知（7，3）线性分组码的生成矩阵 0111001 1110010 0101110 G = ， (1) 求该码的码集； (2) 求对应的系统形式生成矩阵 s G和校验矩阵 H； (3) 该码的最小码距 min d是多少？纠错能力t =？ (4) 列出可纠差错图案 E 和对应伴随式 S（针对系统码） ； (5) 若收到 R1110101，请译出发码估值 C。 解：(1) 消息 m 码字 c 系统码字 c 000 0000000 0000000 001 0101110 0010111 010 1110010 0101110 011 1011100 0111001 100 0111001 1001011 101 0010111 1011100 110 1001011 1100101 111 1100101 1110010 （3） (2) 1001011 0101110 0010111 S G = 1101000 0110100 1110010 1010001 H = （5） (3) dmin=4 ,t=1 （2） (4) S E 0000 0000000 0001 0000001 0010 0000010 0100 0000100 1000 0001000 0111 0010000 1110 0100000 1011 1000000 （5） (5) RHT=0111 E=0010000 C=R+E= 1100101 (发码) 6. 设输入符号表为X0, 1， 输出符号表为Y0, 1。 输入信号的概率分布为p(1/2， 1/2)， 失真函数为 d(0，0) = d(1，1) = 0，d(0，1) =1，d(1，0) = 1.6. (1) 求Dmin，R(Dmin)，相应的编码器转移概率矩阵p(y/x)； (2) 求Dmax，R(Dmax)，相应的编码器转移概率矩阵p(y/x)。 解：(1) Dmin0 ， R(Dmin) H(1/2,1/2)=1bit/symbol ， 相应的编码器转移概率矩阵p(y/x) 10 01 （7） (2) Dmax = n i iji j dp 1 min,min 222121212111 2 , 1 dpdpdpdp j + = 1,2 min0.8,0.50.5 j= = R(Dmax) 0 相应的编码器转移概率矩阵p(y/x) 01 01 （8） 7. 随机变量 X 表示信号 x(t)的幅度，均匀分布， (1) 若1)(0tx，求信源熵)(XHc； (2) 若5 . 0)(0tx，求信源熵)(XHc。 解：(1) ( )1 01 x pxx= = 1 0 01log1)()(log)()(dxxdxpxpXH xxc （比特） （5） (2) ( )2 00.5 x pxx= 0.5 0 ()( )log( ) ( )2 log21 cxx HXpxpx d xdx= = （比特） （5） 8. 某一离散无记忆信源的符号集为0，1，已知信源的概率空间为： = 8/78/1 10 P X (1) 求消息符号的信源熵； (2) 由 80 个符号构成的序列，求某一包含 m 个“0”和 80-m 个“1”的特定序列的信息量； (3) 计算 80 个符号组成序列X 的熵()H X 。 解：(1) 1 7 ()( , )0.54 / 8 8 H XHbit symbol= （3） (2) 80 01 log() 17 log(80)log 88 15.42.81 mm Ipp mm m = = =+ （7） (3) 1280 ()80() 43.2 bit/sequence H X XXH X= = 3 （5） 9. 某信源有 7 个符号a1, ,a7,概率分别为 0.49,0.26,0.12,0.04,0.04,0.03,0.02，求 (1) 求该信源的熵； (2) 对此信源做二进制哈夫曼编码，写出相应码字，并求出编码效率； (3) 对此信源做二进制费诺编码，写出相应码字，并求出编码效率。 解：(1) (X)(0.49,0.26,0.12,0.04,0.04,0.03,0.02)2.01HH= bit/符号（2） (2) a1 a2 a3 a4 a5 a6 a7 0.49 0.26 0.12 0.04 0.04 0.03 0.02 0 1 0.49 0.26 0.12 0.05 0.04 0.04 0 1 0.49 0.26 0.12 0.08 0.05 0 1 0.49 0.26 0.13 0.12 0.49 0.26 0.25 0 1 0.51 0.49 0 1 0 1 1 1 00 011 01000 01001 01010 01011 7 1 ( ) ii i Kp a K = = 2.02 码元/符号 （7） () 99.5% H X K = (3) 符号 P 码长 a1 0.49 0 0 1 a2 0.26 1 0 10 2 a3 0.12 1 0 110 3 a4 0.04 1 0 0 11100 5 a5 0.04 1 11101 5 a6 0.03 1 0 11110 5 a7 0.02 1 11111 5 7 1 () ii i Kp a K = = 2.02 码元/符号 （6） () 99.5% H X K = 10. 某系统（7，3）码 65432102103210 ()()cccccccmmmcccc=c其四位校验位 与信息位的关系为： (1) 求对应的生成矩阵和校验矩阵； (2) 求该码的码集， (3) 计算该码的最小距离，纠错能力； (4)