信息论编码第四章答案

信息论与编码信息论与编码 第四章作业解析第四章作业解析 1.有一信源，它有6个可能的输出，其概率分布如下表所示， 表中给出了对应的码A、B、C、D、E和F。表中给出了对应的码 、 、 、 、 和 消息 () i p a 消息 1/200000000 1/400101101010100 1 a a () i p 1/400101101010100 1/160100111101101100101 1/160110111111011101101110 2 a 3 a a 1/160110111111011101101110 1/16100011111111010111110110 4 a 5 a 1/16101011111 11111011011111011 6 a (1)、求这些码中哪些是唯一可译码； (2)、求哪些是非延长码（即时码）； 对所有唯译码求出其平均码长和编码效率(3)、对所有唯一可译码求出其平均码长和编码效率。 解： 唯一可译码是， 非延长码为A，C，E唯可译码是，,非延长码为A，C，E 的平均码长：)16/116/116/116/14/12/1 (3)( 6 +=nspn的平均码长： 信源符号码符号/3 )16/116/116/116/14/12/1 (3)( 1 = += =i ii nspn 编码效率：%67.66%100* 3 2 log )( = rn sH 的平均码长： 6 信源符号码符号/125.28/17 16/1*616/1*516/1*416/1*34/1*22/1*1)( 1 = += =i ii nspn 编码效率%1294%100* 2)( = sH 编码效率%12.94%100 125.2log = rn 6 的平均码长： 信源符号码符号/125. 2)( 6 1 = =i ii nspn %12.94 log )( = rn sH 编码效率： logrn 的平均码长： 16/1*416/1*44/1*22/1*1)( 6 += nspn 信源符号码符号/216/1*416/1*4 16/1*416/1*44/1*22/1*1)( 1 =+ += =i ii nspn 编码效率： 信源符号码符号/216/1416/14+ %100%100* 2 2 log )( = sH 2logrn 判唯可译码的方法 判唯一可译码的方法： 给定一有限长码元序列，可采用下面方法判断是给定有限长码元序列，可采用下面方法判断是 否为唯一可译码: 判断是否为非奇异码 判断是否为非奇异码; 等长的非奇异码一定是唯一可译码;等长的非奇异码定是唯可译码; 对于非等长的非奇异码，先剔除不满足Kraft不 等式的码等式的码; 用定义判断.用定义判断 -2003级 程华 2. 有一个信源X如下： 123456 ( )0.320.220.180.160.080.04 Xxxxxxx p x = (1)、求信源熵; ( )0.320.220.180.160.080.04p x (2)、用Shannon编码法编成二进制变长码，并计算其编码效 率； (3)用Fano编码法编成二进制变长码并计算其编码效率(3)、用Fano编码法编成二进制变长码，并计算其编码效率； (4)、用Huffman码编码成二进制变长码，并计算其编码效率； (5)、用Huffman码编码成三进制变长码，并计算其编码效率；(5)、用Huffman码编码成三进制变长码，并计算其编码效率； (6)、比较三种编码方法的优缺点。 6 1 (1)()( )log2 3522/H Xp xbit= 信源符号 解： 1 (1)()( )log2.3522/ ( ) i i i H Xp xbit p x = = 信源符号 11 (2)loglog1 ( )( ) rir n p xp x + ( )( ) ii p xp x 由于每个码长肯定是正整数，上式给出了码长选择范围。 符号p(xi)累加概 率 -log p(xi)码字 长度 码字 率 长度 x 0.3201.6439 x2 0.220.322.1844 x3 0.180.542.4739 x4 0.160.722.6439 x5 0.080.883.6439 5 x6 0.040.964.6439 平均码长码符号/信源符号84. 2=n 编码效率 %82.82%100 2log84.2 3522.2 log )( = rn XH FANO编码 符 号 P(xi) 码字码字 长度 0 320 540 0002 x1 0.320.54 0 0002 x2 0.221012 x3 0.180.18 0102 x4 0.160.1601103 x4 0.160.16 01103 x5 0.080.46 1 0.28 10.12 1011104 x6 0.04111114 平均码字长度码符号/信源符号 35222)(XH 4 . 2=n 编码效率%98%100 2log4 . 2 3522 . 2 log )( = rn XH 二进制Huffman编码 符号 p(xi) 码字码字 0 p(xi) 长度 X . 0 X . 0 0 1 1 X . X . 0 0 1 1 X . X 0 1 1 X .1 平均码字长度码符号/信源符号42平均码字长度码符号/信源符号 编码效率 %98%100 2l42 3522. 2 l )( = XH 4 . 2=n 编码效率 2log4 . 2logrn 三进制Huffman编码 ? 首先, 判断 322) 13(6 ) 1( ? = =rrq 个虚假符号选择123) 1( 322) 13(6 = rqrm 符号 p(xi)码字码字长度符号 p(xi) 码字码字长度 x10.32 0.320.4811 0 x20.22 0.220.3221 x30.18 0.180.22002 0 1 2 x40.16 0.16012 0 1 2 x50.08 0.120203 x60.04 0213 0 1 2 X 0022舍去 2 平均码字长度码符号/信源符号 编效率 3522. 2)(XH 58. 1=n 编码效率%93.93%100 3log58. 1 3522. 2 log )( = rn XH 3 现有现有一一幅已离散量化后的图像幅已离散量化后的图像，图像的灰度量化分图像的灰度量化分3. 现有幅已离散量化后的图像现有幅已离散量化后的图像，图像的灰度量化分图像的灰度量化分 成成8级，如下表所示。表中数字为相应像素上的灰度级级，如下表所示。表中数字为相应像素上的灰度级 另有一无噪无损二元信道，单位时间(秒)内传输100个 二元符号二元符号。 (1)、现将图像通过给定的信道传输，不考虑图像的任何 统计特性并采用二元等长码问需要多长时间才能传统计特性，并采用二元等长码，问需要多长时间才能传 送完这幅图像？ (2)若考虑图像的统计特性(不考虑图像的像素之间的(2)、若考虑图像的统计特性(不考虑图像的像素之间的 依赖性)，求这幅图像的信源熵H(S)，并对每个灰度级进 行Huffman最佳二元编码问平均每个像素需用多少二行Huffman最佳二元编码，问平均每个像素需用多少二 元码符号来表示？这时需多少时间才能传送完这幅图像？ (3)从理论上简要说明这幅图像还可以压缩而且平均(3)、从理论上简要说明这幅图像还可以压缩，而且平均 每个像素所需的二元码符号数可以小于H(S)比特。 解解： (1)一幅已离散化后的图象，其灰度划分成级， 先不考虑图象的任何统计特性采用元等长码因为 82l 先不考虑图象的任何统计特性，采用二元等长码，因为 q=8,所以要满足 82= q l 3l故二元码符号灰度级3=l故二元码符号灰度级 即每个灰度等级需采用三位二元符号来传输。 这幅图象空间离散化后共有 100个像素每这一幅图象空间离散化后共有=100个像素，每 个像素的灰度需用三个二元符号来编码，所以这幅图象 采用二元等长码后共需300个二元符号来描述所传输采用二元等长码后共需300个二元符号来描述。所传输 的信道是无噪无损信道，其每秒钟传输100个二元符号。 因此需秒钟才能传送完这幅图象因此，需秒钟才能传送完这幅图象。 (2)考虑图象的统计特性(不考虑图象的像素之间的依赖( )( 性)时，根据此图象进行统计，把像素的灰度值作为信 源，可得 12345678 S 401710107655 ( ) 100100100100100100100100 i S P s = 100100100100100100100100 8 所以比特灰度级572. 2)(log)()( 8 1 = = i i i spspSH 对此灰度进行哈夫曼最佳二元编码： 码 长 码 字 灰度 级 概率 i l)( i sP 长字 1 0.400.40 0.17 0.40 0.20 0.40 0.23 0.40 0.37 0 0.60 0 0.40 1 001 2 0 17 i )( i 0.13 0.10 0.17 0.13 0 0.20 0 0.17 1 0.23 1 001 2 0.17 0000 3 0.10 0.10 0 0.10 1 0.10 1 0001 4 0.10 0100 5 0.07 0 5 0101 6 0.06 1 0110 0110 7 0.05 0 0111 8 0.05 1 得二元符号灰度级 632)( 8 lsPL 得二元符号灰度级 63. 2)( 1 = = i i i lsPL 通过哈夫曼最佳二元编码后，每个像素平均需要用 2.63个二元符号，则此图象平均共需要用263个二元符 号来表示。因此，需2.63秒才能传送完这幅图象。 (3)在(2)题中计算时没有考虑图象的像素之间的依赖 关系，但实际此图象的像素之间是有依赖的。例如，若 考虑像素前后之间灰度的依赖关系