信息论与编码_第五、六章习题

1 第五章习题 张亚飞 信息工程教研室 张亚飞 信息工程教研室 2011-2012学年第学年第1学期学期 2 第五章习题5-1 ?5-1 将下表所列的某六进制信源进行二进制编 码，试问： 将下表所列的某六进制信源进行二进制编 码，试问： 01 001 100 101 110 111 1 000 001 010 110 110 0 10 1101 1100 1001 1111 0 10 110 1110 11110 111110 0 01 011 0111 01111 011111 000 001 010 011 100 101 1/2 1/4 1/16 1/16 1/16 1/16 u1 u2 u3 u4 u5 u6 C6C5C4C3C2C1 概率消息概率消息 3 第五章习题5-1 ?C5是奇异码，所以，一定不是唯一可译码是奇异码，所以，一定不是唯一可译码 3 1 123456 2 3 124 4 13 5 23 6 :6 21 63 :2222221 64 63 :1 64 :224 21 :25 21 :25 21 C C C C C C += + 4 第五章习题5-1 ?C1是定长的非奇异码，所以，一定是唯一可 译码 是定长的非奇异码，所以，一定是唯一可 译码 ?C1、C3、C6是即时码，所以，一定是唯一可 译码 是即时码，所以，一定是唯一可 译码 ?C2和和C4的判断需利用萨得纳斯的判断需利用萨得纳斯-彼得森准则彼得森准则 5 第五章习题5-1 111011 11110111 011111 1111101111 1101 10 S1C2 C2是唯一可译码是唯一可译码 6 第五章习题5-1 111 001 100 101 0 S3 1 S2 01101 1100 1111 1001 110 01010 S4S1C2 C4不是唯一可译码不是唯一可译码 7 第五章习题5-1 ?C1、C2、C3、C6是唯一可译码是唯一可译码 ?C1、C3、C6是非延长码是非延长码 222 111 ()log 2log 44*log 162/ 2416 H Xbit=+=符号 6 1 ( ) ii i KK p a = = () log H X Km = 8 第五章习题5-1 1 3/K = 码元 符号 1 0.667= 23 111 1*2*(3456)*2.125/ 2416 KK=+ +=码元 符号 23 0.941= 6 11 2*3*2.5/ 22 K =+=码元 符号6 0.8= 9 第五章习题5-11 1111054.6440.960.04x6 111043.6440.880.08x5 10132.6440.720.16x4 10032.4740.540.18x3 01032.1840.320.22x2 0021.64400.32x1 码字码长码字码长Ki-logp(xi)累加概率累加概率 Pi 符号概率符号概率 pi 信源符号信源符号 xi （2）香农编码）香农编码 10 第五章习题5-11 ()(0.32,0.22,0.18,0.16,0.08,0.04)2.35/H XHbit=符号 6 1 ( )2.84/ ii i KK p a = = 码元 符号 () 0.827 log H X Km = 11 第五章习题5-11 4111110.04x6 411100 1 0.08x5 31100 1 0.16x4 2100 1 0.18x3 2011 0.22x2 2000 0 0.32x1 码长编码码长编码4321 符号 概率 符号 概率 pi 信源 符号 信源 符号 xi （3）费诺编码）费诺编码 12 第五章习题5-11 6 1 ( )2.4/ ii i KK p a = = 码元 符号 () 0.979 log H X Km = 13 第五章习题5-11 （4）哈夫曼二进制编码）哈夫曼二进制编码 i K 14 第五章习题5-11 6 1 ( )2.4/ ii i KK p a = = 码元 符号 () 0.979 log H X Km = 15 第五章习题5-11 （5）哈夫曼三进制编码）哈夫曼三进制编码 这里：这里：m=3，n=6 令令=2，m+(m1)=7，则，则 t=7n=76=1 所以所以,需要增加一个虚假符号，或第一次取需要增加一个虚假符号，或第一次取m-t=2个符号进行编码个符号进行编码 16 第五章习题5-11 哈夫曼三进制编码哈夫曼三进制编码 i K 17 第五章习题5-11 6 1 ( )1.58/ ii i KK p a = = 码元 符号 2 ()2.35 0.938 log1.58*log 3 H X Km = 18 第五章习题5-11 （6）若逐个符号进行二进制定长编码，要求不出差错）若逐个符号进行二进制定长编码，要求不出差错 log/log3Knm= 3/K = 码元 符号 log3bit/RKm=符号 () 0.783 log H X Km = 19 第五章习题5-11 （7）若）若10-3，=0.979，求定长编码L，=0.979，求定长编码L () 0.979,0.05 () H X H X = + 信息序列的自信息方差为信息序列的自信息方差为 6 2 22 1 ()(log)()0.523 ii i XppH X = = 2 5 2 () 2.1 10 X L 作业作业 ?1、若有一信源、若有一信源 12 0.80.2 Xaa P = 每秒钟发出每秒钟发出2.66个信源符号，将此信源的输出符号 送入某一个二元信道中进行传输（假设信道是无噪 无损的），而信道每秒钟只传递 个信源符号，将此信源的输出符号 送入某一个二元信道中进行传输（假设信道是无噪 无损的），而信道每秒钟只传递2个二元符号，试问 信源不通过编码能否直接与信道连接？若通过适当 编码能否在此信道中进行无失真传输？若能，试说明 如何编码并说明原因。 个二元符号，试问 信源不通过编码能否直接与信道连接？若通过适当 编码能否在此信道中进行无失真传输？若能，试说明 如何编码并说明原因。 作业作业 ()(0.8,0.2)0.722/H XHbit=符号信源熵 信源每秒发出 信源熵 信源每秒发出2.66个符号，所以信源输出的信息速率为个符号，所以信源输出的信息速率为 2.66()1.92/ t RH Xbit=秒 对于一个无噪无损的二元信道，信道的信道容量对于一个无噪无损的二元信道，信道的信道容量 C=1bit/符号。而信道每秒只传送两个二元符号， 所以信道的最大信息传输速率为 符号。而信道每秒只传送两个二元符号， 所以信道的最大信息传输速率为 22/ t CCbit=秒 作业作业 Rt2二元码元二元码元/秒秒 作业作业 对三次扩展信源进行哈夫曼编码对三次扩展信源进行哈夫曼编码 3 1 1 11 1 21 2 12 1 11 222 1 222 1222 ()0.5120.1280.1280.1280.0320.0320.0320.008 ijk Xaaaaaaaa aa aaaa aa aaa a aa a a p x x x = 哈夫曼码哈夫曼码1 000 001 010 01100 01101 01110 01111 _ 3 2.184/K =二元码元 三个信源符号 _ 0.728/K =二元码元 信源符号 二次扩展编码后，送入信道的传输率为二次扩展编码后，送入信道的传输率为 0.728*2.66=1.94二元码元二元码元/秒秒2二元码元二元码元/秒秒 此时，就可以在信道中进行无失真传输了。此时，就可以在信道中进行无失真传输了。 作业作业 ?2、现由一幅数字图像，图像的灰度分成、现由一幅数字图像，图像的灰度分成8个等级 ，如下表所示，表中数字表示相应像素的灰度值 个等级 ，如下表所示，表中数字表示相应像素的灰度值 1111111111 1111111111 1111111111 1111111111 2222222222 2222222333 3333333444 4444444555 5555666666 7777788888 作业作业 ?另有一无噪无损二元信道，单位时间（秒）内传输另有一无噪无损二元信道，单位时间（秒）内传输100 个二元符号个二元符号 ?（1）现将图像通过给定的信道传输，不考虑图像的任 何统计特性，并采用二元定长码，问需多长时间才能 传送完这幅图像 ）现将图像通过给定的信道传输，不考虑图像的任 何统计特性，并采用二元定长码，问需多长时间才能 传送完这幅图像 ?（2）若考虑图像的统计特性（不考虑图像像素之间的 依赖性）求图像的信源熵，并对每个灰度级进行哈夫 曼二元编码，问平均每个像素需用多少个二元码来表 示？这时需多少时间才能传送完这幅图像 ）若考虑图像的统计特性（不考虑图像像素之间的 依赖性）求图像的信源熵，并对每个灰度级进行哈夫 曼二元编码，问平均每个像素需用多少个二元码来表 示？这时需多少时间才能传送完这幅图像 ?（3）从理论上简要说明这幅图像还可以压缩，并且平 均每个像素所需的二元码数可以小于信源熵 ）从理论上简要说明这幅图像还可以压缩，并且平 均每个像素所需的二元码数可以小于信源熵H(X) 作业作业 （1）一幅已离散化后的图像，其灰度量化分成）一幅已离散化后的图像，其灰度量化分成8级 ，现不考虑图像的任何统计特性，采用二元定长 编码，因为信源符号数 级 ，现不考虑图像的任何统计特性，采用二元定长 编码，因为信源符号数n=8，所以码长 即每个灰度级需采用三位二元符号来传输。 这幅图像共有 ，所以码长 即每个灰度级需采用三位二元符号来传输。 这幅图像共有N=100个像素，所以共需个像素，所以共需300个二元 符号来描述 。无噪无损信道每秒传输 个二元 符号来描述 。无噪无损信道每秒传输100个二元 符号， 个二元 符号，因此，需因此，需3秒钟才能传送完秒钟才能传送完。 log/log3Knm= 3/K = 二元码元 灰度级 作业作业 （2）考虑信源的统计特性）考虑信源的统计特性 12345678 ()0.40.170.10.10.070.060.050.05 X p X = 哈夫曼码哈夫曼码1 001 0000 0001 0100 0101 0110 0111 ()2.572/H Xbit=灰度级 2.63/K =二元码元 灰度级 通过哈夫曼编码后，每个像素平均需通过哈夫曼编码后，每个像素平均需2.63个二元码元， 则此图像共需 个二元码元， 则此图像共需263个二元码元来描述，个二元码元来描述，因此需因此需2.63秒 才能传送完这幅图像 秒 才能传送完这幅图像 作业作业 （3）在（）在（2）的计算中没有考虑像素之间的相关性， 实际上此图像的像素之间是有相关性的，如灰度 ）的计算中没有考虑像素之间的相关性， 实际上此图像的像素之间是有相关性的，如灰度 “1”后面只可能出现后面只可能出现“1”或或“2”，灰度，灰度“2”后面只可能 出现 后面只可能 出现“2”或或“3”等。因此在考虑灰度之间的相关性后 ，灰度值的熵小于 等。因此在考虑灰度之间的相关性后 ，灰度值的熵小于H(X)。 根据无失真编码定理，总可以找到一种编码方法使 平均码长，所以这幅图像可以进 一步压缩， 。 根据无失真编码定理，总可以找到一种编码方法使 平均码长，所以这幅图像可以进 一步压缩，平均每个像素灰度值所需的码元数小于平均每个像素灰度值所需的码元数小于 H(X) ()KH极限熵 31 第六章练习 123 1/ 21/31/6 1/61/ 21/3 1/31/61/ 2 ()()1/ 4, ()1/ 2 (1) (2) P p xp xp x = = 已知信道矩阵， 按最大后验概率译码准则确定译码规则， 并计算此时的错误译码概率 按最大似然译码准则确定译码规则， 并计算此时的错误译码概率 32 第六章练习 ?最大后验概率译码准则最大后验概率译码准则 1/81/121/ 24 ()( ) (|)1/ 241/81/12 1/61/121/ 4 ijiji P x yP x P yx = 123 1 ()()()1/3, ()7/ 24, ()9/ 24 n jij i P yP x yP yP yP y = = 得 )( )( )|( j ji ji yP yxP yxP= 111213 212223 313233 321 (|),(|),(|), 879 132 (|),(|),(|) 879 126 (|),(|),(|) 279 P xyP xyP xy P xyP xyP xy P xyP xyP xy = = = 33 第六章练习 ?最大后验概率译码准则最大后验概率译码准则 则可以确定最佳译码规则为：则可以确定最佳译码规则为： 132233 ();();()F yx F yx F yx= 在此规则下的译码平均错误概率为：在此规则下的译码平均错误概率为： min (1/8 1/ 24)(1/12 1/12)(1/ 24 1/12) 11/ 24 E P=+ = 34 第六章练习 ?最大似然译码准则最大似然译码准则 则可以确定最佳译码规则为：则可以确定最佳译码规则为： 112233 ();();()F yx F yx F yx= 在此规则下的译码平均错误概率为：在此规则下的译码平均错误概率为： 111111111 *()*()*() 463463263 1/ 2 E P =+ = 第六章习题6-3 系统（系统（8，4）码，码字为）码，码字为 32103210 Cu u u u v v v v= 3023 vuuu=+ 2013 vuuu=+ 1012 vuuu=+ 0123 vuuu=+ 32103210 3210 10001101 01001011 00100111 00011110 CmG u u u u v v v v u u u u = = v3v2v1v0 第六章习题6-3 10001101 01001011 00100111 00011110 G = 11011000 10110100 01110010 11100001 H = 第六章习题6-3 11011000 10110100 01110010 11100001 H = 任意3列之和都不为0，最少4列才能组合出0，所以 H线性无关的列数为3，即dmin-1=3,则dmin=4 任意3列之和都不为0，最少4列才能组合出0，所以 H线性无关的列数为3，即dmin-1=3,则dmin=4 第六章习题6-6 0011101 0100111 1001110 G = 系统化，将系统化，将G的第一行和第三行交换即可，所以 系统形式的生成矩阵为 的第一行和第三行交换即可，所以 系统形式的生成矩阵为 1001110 0100111 0011101 G = 第六章习题6-6 1011000 1110100 1100010 0110001 H = 任意3列之和都不为0，最少4列才能组合出0，所以 H线性无关的列数为3，即dmin-1=3,则dmin=4 任意3列之和都不为0，最少4列才能组合出0，所以 H线性无关的列数为3，即dmin-1=3,则dmin=4 101对应的码字对应的码字C=1010011 CHT=0000 第六章习题6-6 E7=0000001S7=0001 E6=0000010S6=0010 E5=0000100S5=0100 E4=0001000S4=1000 E3=0010000S3=1101 E2=0100000S2=0111 E1=1000000S1=1110 E0=0000000S0=0000 第六章习题6-6 E15=1100010S15=1011 E14=1000001S14=1111 E13=0001100S13=1100 E12=0001010S12=1010 E11=0001001S11=1001 E10=0100001S10=0110 E9=0100010S9=0101 E8=1010000S8=0011 第六章习题6-6 3643 26542 1651 0540 seee seeee seee seee =+ =+ =+ =+ 6 5 4 3 2 1 0 T Se e e e e eeH= 第六章习题6-8 3242 ( )(1)(1)1g xxxxxxx=+=+ 1100101111 1110010110 1001011101 1011100100 0111001011 0101110010 0010111001 0000000000 循环码字信息组循环码字信息组 第六章习题6-8 3242 ( )(1)(1)1g xxxxxxx=+=+ 2 ( ) 1 m