信息论第五章答案.doc

5.1 设信源(1) 求信源熵H(X)；(2) 编二进制香农码；(3) 计算平均码长和编码效率。解：(1)(2)xip(xi)pa(xi)ki码字x10.203000x20.190.23001x30.180.393011x40.170.573100x50.150.743101x60.10.8941110x70.010.9971111110(3)5.2 对信源编二进制费诺码，计算编码效率。解：xip(xi)编码码字kix10.200002x20.19100103x30.1810113x40.1710102x50.15101103x60.11011104x70.011111145.3 对信源编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。解：二进制哈夫曼码：xip(xi)编码码字kis61s50.610s40.391s30.350s20.261x10.20102x20.191112x30.1800003x40.1710013x50.1500103s10.111x60.1001104x70.01101114三进制哈夫曼码：xip(xi)编码码字kis31s20.540s10.261x10.2221x20.190002x30.181012x40.172022x50.150102x60.11112x70.0121225.4 设信源(1) 求信源熵H(X)；(2) 编二进制香农码和二进制费诺码；(3) 计算二进制香农码和二进制费诺码的平均码长和编码效率；(4) 编三进制费诺码；(5) 计算三进制费诺码的平均码长和编码效率；解：(1)=127/64 bit/symbol (2)二进制香农码：xip(xi)pa(xi)ki码字x10.5010x20.250.5210x30.1250.753110x40.06250.87541110x50.031250.9375511110x60.0156250.968756111110x70.00781250.98437571111110x80.00781250.992187571111111二进制费诺码：xip(xi)编码码字kix10.5001x20.2510102x30.125101103x40.06251011104x50.0312510111105x60.015625101111106x70.00781251011111107x80.0078125111111117(3)香农编码效率：费诺编码效率：(4)xip(xi)编码码字kix10.5001x20.25111x30.12520202x40.06251212x50.03125202203x60.01562512213x70.00781252022204x80.0078125122214(5)5.5 设无记忆二进制信源先把信源序列编成数字0，1，2，8，再替换成二进制变长码字，如下表所示。(1) 验证码字的可分离性；(2) 求对应于一个数字的信源序列的平均长度；(3) 求对应于一个码字的信源序列的平均长度；(4) 计算，并计算编码效率；(5) 若用4位信源符号合起来编成二进制哈夫曼码，求它的平均码长，并计算编码效率。序列数字二元码字10100001110010013101000013101100001411000000015110100000016111000000001711110000000080解：（1）满足Kcraft不等式：；由码树图可见，没有一个码字是其它码字的前缀，码字均在树的终结点。所以码字可分离。 （2）序列长度、序列概率及二元码长如下表所示：序列序列长度Li序列概率pi数字二元码长Li二元码字110.10410000120.10.914100100130.10.92341010000140.10.933410110000150.10.9444110000000160.10.95541101000000170.10.966411100000000180.10.977411110000000080.98810 （3） （4） , 此值表示无记忆二元信源采用游程长度编码后每个二元信源需要的平均码长。，（5）4位信源符号的联合概率、Huffman编码及码长如下表：（码字可以不同，但码长一样） S4P(Si)码字Wi码长LiS4P(s)码字Wi码长Li00000.65610110010.00811111010700010.0729110310100.00811111011700100.0729100311000.00811111110701000.0729101301110.0009111111100910000.07291110410110.0009111111101900110.0081111110611010.0009111111110901010.00811111000711100.000111111111101001100.00811111001711110.00011111111111105.6 有二元平稳马氏链，已知p(0/0) = 0.8，p(1/1) = 0.7，求它的符号熵。用三个符号合成一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率。解：平稳时马尔科夫状态的概率：解得：一阶马氏信源的熵：S1S2S3P(S1S2S3)LiWiS1S2S3P(S1S2S3)LiWi00048/1251101121/2504001111149/250300011021/2504010000112/12530110109/25050101010012/125400101013/1255010115.7 对题5.6的信源进行游程编码。若“0”游程长度的截止值为16，“1”游程长度的截止值为8，求编码效率。解：一阶马氏信源的熵同上题，二元平稳一阶记忆序列“0”游程的长度概率：二元平稳一阶记忆序列“1”游程的长度概率：“1”游程长度的熵：同理，“0”游程长度的熵：分别对“0”和“1”游程序列进行Huffman编码，并分别计算出它们的编码效率。“0”游程序列的长度、对应得概率、Huffman编码的二元码长及码字序列序列长度Li序列概率pi数字二元码长Li二元码字01P1/00211002P0/0 P 1/0130010003P0/02 P 1/02301100004P0/03 P 1/0331010000,05P0/04 P 1/04400010000,006P0/05 P 1/05401010000,0007P0/06 P 1/06410010000,00008P0/07 P 1/075000000000,0000,09P0/08 P 1/085010010000,0000,0010P0/09 P 1/095100010000,0000,00011P0/010 P 1/0A60000100000,0000,000012P0/011 P 1/0B61000000000,0000,0000,013P0/012 P 1/0C61000010000,0000,0000,0014P0/013 P 1/0D700001100000,0000,0000,00015P0/014 P 1/0E700001110000,0000,0000,000016P0/015F501000“1”游程序列的长度、对应得概率、Huffman编码的二元码长及码字：序列序列长度Ki序列概率pi数字二元码长Ki二元码字11P0/10201112P0/1 P 1/112101113P0/1 P 1/123300111114P0/1 P 115P0/1 P 1/144400011111,116P0/1 P 1/155411101111,1117P0/1 P 1/166411111111,11118P 1/17740000可见满足，这里的“0”游程编码效率高，因为游程长度长，而“1”游程编码效率受游程的长度限制显得比“0”游程编码效率略低一些，因此整体的编码效率介于两者之间。5.8 选择帧长N = 63(1) 对00100000,00000000,00000000,00000000,01000000,00000000,00000000,0000000编L-D码；(2) 对10000100,00101100,00000001,00100001,01001000,00000111,00000100,0000001编L-D码再译码；(3) 对0000000000000000000000000000000000000000000000000000000000000000编L-D码；(4) 对10100011010111000110001110100110000111101100101000110101011010010编L-D码；(5) 对上述结果进行讨论。解：（1）本帧内信息位数Q=2；各信息位位置值n1=3，n2=34；帧长N=63。Q位和T位需要的二进制自然码位数分别是：所以，L-D编码结果：000010,01000010010解码：已知N=63，故前6位为Q的自然码表示，所以Q=2；后11位为T的自然码表示，得T=530寻找某一值K，使得：K=33再令，再次寻找某一值L，使得：L=2所以解码出信息位的位置值是n1=3，n2=34(2) 对10000100,00101100,00000001,00100001,01001000,00000111,00000100,00000010编L-D码本帧内信息位数Q=15；各信息位位置值n1=1，n2=6，n3=11，n4=13，n5=14，n6=24，n7=27，n8=32，n9=34，n10=37，n11=46，n12=47，n13=48，n14=54，n15=63；帧长N=63。Q位和T位需要的二进制自然码位数分别是：所以，L-D编码结果：001111，1010110,11111101,01111111,10110101,00011000,11111110 解码：已知N=63，故前7位为Q的自然码表示，所以Q=15；后47位为T的自然码表示，得T= 95646769289470(a) 寻找某一值K，使 得：K=62(b)令，Q=Q-1重复步骤（a）（b）每次寻找出一个K值，得：解出的各信息位位置值：n1=1，n2=6，n3=11，n4=13，n5=14，n6=24，n7=27，n8=32，n9=34，n10=37，n11=46，n12=47，n13=48，n14=54，n15=63；(3) 本