当前位置：文档之家 › 信息论基础与编码(第五章)

信息论基础与编码(第五章)

  • 格式：docx
  • 大小：399.04 KB
  • 文档页数：27

信息论基础与编码(第五章) 5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码

12345CCCCC、、、、和6C。 （1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）； （3） 对所有唯一可译码求出其平均码长。 消息 概率 1/2 000 0 0 0101 1/4 001 01 10 10 000 001

1/16 010 011 110 1101 001 100

1/16 011 0111 1110 1100 010 101

1/16 100 01111 11110 1001 110 110

1101111 /16 01 11111 11110 111 10 11 解：（1）1,2,3,6是唯一可译码； (2)1,3,6是即时码。 5-2证明若存在一个码长为12,,,qlll的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为的唯一可译码，则必定满足kraft不等式1。由定理4可知若码长满足kraft不等式，则一定存在这样码长的即时码。所以若存在码长的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。 5-3设信源126126()sssSpppPs，611iip。将此信

源编码成为r元唯一可译变长码（即码符号集12{,,,}rXxxx），其对应的码长为（126,,,lll）=（1，1，2，3，2，3），求r值的最小下限。

解：要将此信源编码成为 r元唯一可译变长码，其码字对应的码长 （l1 ,l2 ,l3, l4,l5, l6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即

LqLL,,2,1qilir1

4

LqLL,,2,1 132321161rrrrrrrili 所以要满足 122232rrr ，其中 r是大于或等于1的正整数。 可见，当r=1时，不能满足Kraft不等式。 当r=2, 1824222，不能满足Kraft。

当r=3, 127262729232，满足Kraft。 所以，求得r的最大值下限值等于3。 5-4设某城市有805门公务电话和60000门居民电话。作为系统工程师，你需要为这些用户分配电话号码。所有号码均是十进制数，且不考虑电话系统中0、1不可用在号码首位的限制。（提示：用异前缀码概念） （1）如果要求所有公务电话号码为3位长，所有居民电话号码等长，求居民号码长度1L 的最小值； （2）设城市分为A、B两个区，其中A区有9000门电话，B区有51000门电话。现进一步要求A区的电话号码比B区的短1位，试求A区号码长度2L的最小值。

解：(a) 805门电话要占用1000个3位数中的 805个，即要占用首位为0～ 7的所有数字及以8为首的5个数字。因为要求居民电话号码等长， 以9为首的数字5位长可定义10 000个号码，6位长可定义100 000 个号码。所以minL16。 或由Craft不等式，有

805106000010131L 解得

L1103180510600005488log.， 即 minL16

(b) 在(a)的基础上，将80为首的数字用于最后5个公务电话，81～86 为首的6位数用于B区51 000个号码，以9为首的5位数用于A区9 000 个号码。所以，minL25。或由Draft不等式，有 80510900010510001013122LL() 或 8051090005100010101312()L

解得L2103180510900051004859log. 即minL25 5-5求概率分布为)152,152,51,51,31(的信源的二元霍夫曼码。讨论此码对于概率分布为)51,51,51,51,51(的信源也是最佳二元码。 解：信源的概率分布为： )152,152,51,51,31()(isp 二元霍夫曼码：00，10，11，010，011，码长：2，2，2，3，3 当信源给定时，二元霍夫曼码是最佳二元码。所以对于概率分布为)51,51,51,51,51(的信源，其最佳二元码就是二元霍夫曼码。这二元霍夫曼码一定是三个信源符号的码长为2（码符号/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。因此，上述对概率分布为

)152,152,51,51,31(信源所编的二元霍夫曼码也是概略分布为)51,51,51,51,51(信源的最佳二元码。 5-6 设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这些霍夫曼码的信源的所有概率分布。

解：由题意 假设信源所发出的是个符号的概率为 )P(S)P(S)P(S)P(S1234 由霍夫曼编码的特点知：1)P(S)P(S)P(S)P(S1234 根据霍夫曼编码的方法，每次概率最小的两个信源符号合并成一个符号，构成新的缩减信源，直至最后只剩两个符号。而且当缩减信源中的所有符号概率相等时，总是将合并的符号放在最上面。所以，对于二元霍夫曼码为（00，01，10，11）来说，每个信源都要缩减一次，所以34()()PSPS 要大于1()PS和2()PS，这时必有 12111P(S)P(S),P(S)33

同理对于二元霍夫曼码为（0，10，110，111）有

34111P(S)P(S),P(S)>33

信源概率分布满足以上条件则其霍夫曼编码符合题意。 5-7 设一信源有K=6个符号，其概率分别为：123()1/2,()1/4,()1/8PsPsPs，45()()1/20PsPs，

6()1/40Ps，对该信源进行霍夫曼二进制编码，并求编码效率。 解：相应的Huffman编码是：{1,01,001,0001,00000,00001}。平均码长=1.95，熵=1.94 ()1.940.9951.95log2HXL

5-8 设信源概率空间为： sPS=

9.0,1.0,21ss

，

（1）求SH和信源冗余度； （2）设码符号为X={0,1}，编出S的紧致码，并求紧致码的平均码长L； （3）把信源的N次无记忆扩展信源NS编成 紧致码，试求N=2，3，4，时的平均码长NLN； （4）计算上述N=1，2，3，4这四种码的编码效率和码冗余度。

解：（1）信源 sPS

9.01.021ss

其 iiisPsPsHlog210.469 比特/符号 剩余度2log1sH0.531=53.1％ （2）码符号X={0,1}，对信源S编紧致码为：1s0，12s 其平均码长L=1 码符号/信源符号

(3) 当N=2时



iPS

2

=81.0,09.0,09.0,01.0,,,224133212111ssssssss

紧致码（即霍夫曼码）为 ,4 ,3 ,2 1 码字iW 0 , 10 , 110 , 111 码长il 1 , 2 , 3 , 3

平均码长NLN=21iiilP410.645 码符号/信源

符号 N=3时，iPS3= 

2222223876543219.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,1.0,,,,,,,

对信源3S进行霍夫曼编码，其紧致码为 ,8 ,7 ,6 ,5 ,4 ,3 ,2

1

码字iW 0 , 100 , 101 , 110 , 11100 , 11101 , 11110 , 11111 码长il 1 , 3 , 3 , 3 , 5 , 5 , 5 , 5 平均码长 NLN=31iiilP810.533 码符号

/信源符号 N=4时，iPS4=



,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,1.0,,,,,,,,

2222223333487654321



43333222222161514131211109

9.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0

,,,,,,,

对信源4S进行霍夫曼编码，其紧致码为 ,16 ,15

,14 ,13 ,12

,11

,10 ,9

码字iW 0 , 100 , 101 , 110 , 1110 , 111110 , 1111000 , 1111001, 码长il 1 , 3 , 3 , 3 ,

合集下载

信息论 第5章(基于字典编码和算术编码)

信息论 第5章(基于字典编码和算术编码)


P1=p(x1) P2=P1+p(x2)…
算术编码的基本原理
由于每个消息的起点位置等于前面各个消 息的概率累积，故将它定义为累积概率Pk. 反过来,也可以由累积概率来计算某个消 息的概率:pk＝Pk-Pk-1 ,即两个相邻起点之间的 距离等于这个线段的长度.每个消息所对应的 线段从起点开始,到下一个线段的起点为此,但 不包含下一个线段的起点,即消息Xk的对应区 间为[Pk-1,Pk). 任意选择一个小数,它必然落在某个消息 对应的线段上这说明,可以用一个具有大小概 念的小数来表示某个消息,这就是算术编码的 基本出发点.
当 前 单 词 前缀 FFF 041 FFF FFF 042 FFF 041 100 FFF 041 100 105 尾字符 A A B B B A B C A B C A 码字 041 107 042 042 109 041 100 105 041 100 105 10B
读入 字符 A B B B A B C A B C A 无
二元独立信源的算术编码原理
二元独立信源输出的消息是由0和1组成的 码流，其长度从1开始，逐步增加，直到全部 码元输出为止。 算术编码的过程和信源输出码元的过程同 步进行，一边读取码元，一边进行迭代计算。 迭代计算的内容为P（累积概率）和A（概率） 两个量，P就是当前消息区间的起点，A就是当 前消息区间的宽度。
二元独立信源的算术编码过程
设码元0的概率为p,则码元1的概率为1－p, 编码过程如下: (1)初始化:区间的起点P＝0,区间的宽度A＝1; (2)如果信源输出的码元已经全部处理,转到第 五步.否则从信源读入一个码元,如果读入的码 元为“0”,则转到第三步,如果读入的码元为 “1”,则转到第四步;
(3)读入的码元为0,则区间的起点P不变,区间 的宽度缩短为Ap.用公式 P = P
信息论与编码 曹雪虹 PPT 第第5章

信息论与编码 曹雪虹 PPT 第第5章

H L ( X) η= , ε >0 H L ( X) + ε
信息论基础B
25
5.2 无失真信源编码
编码定理从理论上阐明了编码效率接近1的理想 编码器的存在性，它使输出符号的信息率与信 源熵之比接近于1，即
H L ( X) →1 KL log m L
信息论基础B
L取无限长
26
5.2 无失真信源编码
R3＝0.985比特/二元码符号 L＝4 η = 0.991
4
R4＝0.991比特/二元码符号
信息论基础B
40
5.2 无失真信源编码
定长二元码编码，要求编码效率达到96％时 －5 ，允许译码错误概率 δ ≤ 10
σ (X ) =
2
∑ p (log p )
i i i =1
2
2
− [ H ( X )]
42
5.2 无失真信源编码
香农（Shannon）编码 将信源消息符号按其出现的概率大小依次 排列
p1 ≥ p2 ≥ L ≥ pn
确定满足下列不等式的整数码长Ki。
信息论基础B
7
5.1 编码的定义
如图5-1所示，如果信源输出符号序列长度L＝1，信源 符号集A(a1，a2，…，an) 信源概率空间为
X a1 = P p(a1 )
a2 L an p ( a 2 ) L p ( an )
若将信源X通过二元信道传输 ， 若将信源 通过二元信道传输， 就必须把信源符 通过二元信道传输 变换成由0， 符号组成的码符号序列 符号组成的码符号序列， 号 ai 变换成由 ， 1符号组成的码符号序列 ， 这个 过程就是信源编码
例 设离散无记忆信源概率空间为
信息论基础 第五章

信息论基础 第五章


5.1.2码的分类 分组码和非分组码 分组码:将信源符号集中的每个信源符号si固定地映射成一个码字wi， 这样的码称为分组码。 非分组码:又称树码，编码器输出的码符号通常与编码器的所有信源 符号都有关。 2.奇异码与非奇异码 非奇异码：若一种分组码中的所有码字都不相同，则称此分组码为非 奇异码，否则称为奇异码。 非奇异码是分组码能够正确译码的必要条件，而不是充分条件。
5.2定长码 定长非奇异码一定是唯一可译码。
若对一个有q个信源符号的信源S进行定长编码，那么信源S存在唯 一可译定长码的条件是
qr
N
l
其中，r是码符号集中的码元数，l 是定长码的码长。
q r
l
5.3变长码及变长编码定理
5.3.1 Kraft不等式和McMillan不等式 Kraft不等式
McMillan不等式
r li 1
i 1
q
定理5.3 设信源符号集为S={s1,s2,…sq},码符号集为X={x1,x2,…xr},对信 源进行编码，得到的码为C= {w1,w2,…wq},码长分别为l1，l2，…lq.即 q 时码存在的充要条件是 这称为Kraft不等式。 li
r
i 1
1
5.3.2
定理5.1一个唯一可译码成为即时码的充要条件是其中任何一个码 字都不是其他码字的前缀。
充要性：
如果任何一个码字都不是其他码字的前缀， 则在接收到一个相当于一个完整码字的码符号后便可立即译码，
无需考虑其后的码符号。
必要性： 如果设wi是wj的前缀，则在收到相当于wi的码符号序列后还不能立 即判定它是一个完整的码字，若想正确译码，还必须参考后续的码 符号，这与即时码的定义相矛盾，所以即时码的必要条件是其中任 何一个码字都不是其他码字的前缀。
信息论基础第五章课后答案

信息论基础第五章课后答案

5.1设有信源⎭⎬⎫⎩⎨⎧=⎪⎪⎭⎫ ⎝⎛01.01.015.017.018.019.02.0)(7654321a a a a a a a X P X （1）求信源熵H(X)（2）编二进制香农码（3）计算其平均码长及编码效率解：(1)H(X)=-)(log )(21i ni i a p a p ∑=H(X)=-0.2log 20.2-0.19log 20.19-0.18log 20.18-0.17log 20.17-0.15log 20.15-0.log 20.1-0.01log 20.01H(X)=2.61(bit/sign)(2)ia i P(ai)jP(aj)ki码字a 001a 10.210.0030002a 20.1920.2030013a 30.1830.3930114a 40.1740.5731005a 50.1550.7431016a 60.160.89411107a 70.0170.9971111110（3）平均码长：-k =3*0.2+3*0.19+3*0.18+3*0.17+3*0.15+4*0.1+7*0.01=3.14(bit/sign)编码效率：η=R X H )(=-KX H )(=14.361.2=83.1%5.2对习题5.1的信源二进制费诺码，计算器编码效率。

⎭⎬⎫⎩⎨⎧=⎪⎪⎭⎫ ⎝⎛0.01 0.1 0.15 0.17 0.18 0.19 2.0 )(7654321a a a a a a a X P X 解：Xi)(i X P 编码码字ik 1X 0.2000022X 0.191001033X 0.18101134X 0.17101025X 0.151011036X 0.110111047X 0.01111114%2.9574.2609.2)()(74.2 01.0.041.0415.0317.0218.0319.032.02 )(/bit 609.2)(1.5=====⨯+⨯+⨯+⨯+⨯+⨯+⨯===∑KX H R X H X p k K sign X H ii i η已知由5.3、对信源⎭⎬⎫⎩⎨⎧=⎪⎪⎭⎫ ⎝⎛01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制和三进制赫夫曼码，计算各自的平均码长和编码效率。