吉首大学：《编码理论》第二章（2-2-2）变长码

2.2.2变长码 若要实现无失真编码,不但要求信源符号与每个符号 的码字一一对应,而且要求码符号序列与信源符号序 列也一一对应。也就是要求所编的码为惟一可译码。 我们首先分析等长编码,再分析变长编码,以做比较

2．2．2 变长码 若要实现无失真编码，不但要求信源符号与每个符号 的码字一一对应，而且要求码符号序列与信源符号序 列也一一对应。也就是要求所编的码为惟一可译码。 我们首先分析等长编码，再分析变长编码，以做比较

等长码基本问题 等长码特点:4= 要求: (1)s;4>o 惟一可铧鸸 (2)高效 问题: 例1.「S P(s)u2141/81/161/16 等长竭鸸 C1=0.01010120big奇异码 C2=(00010101701g

一、等长码基本问题 等长码特点： C2={000,001,100,101,111}，l 2 =3 code/sig i l l = 要求： i i (1)s   问题： l =？ 例1． 1 2 3 4 5 1 2 1 4 1 8 1 16 1 16 i S s s s s s P( s ) / / / / /     =         C1={00,01,10,11,10}，l 1=2 code/sig (2)高效

等长码基本问题 要求:可能的码字数消息数 消息数 对基本信源编码:S∈{1…,SW} 码字数念r(ogA) W=(x1x12…x) ∈x 1 (对例1,q=5,…∴要求:225,即1≥3) 对N长源编码:S={a1,a2,…}分团=(x,…x ∴r≌q(LNog,q)

一、等长码基本问题 可能的码字数≥消息数 对基本信源编码： 对N长源编码： 1 { , , } { } S s s W  q i 1 1 2 { , , , } { ( , , )} N l N S x x =  =     q i i i 消息数 码字数：r l 1 2 1 ( ) { , } i i i il ij r W x x x x x x =  ∴ r l≥q (l≥logr q) （对例1，q=5, ∴要求：2 l≥5，即l ≥ 3） ∴ r l≥q N (l/N≥logr q)

、等长码基本问题 例1(续) S的三次扩展:s:{(1=(ss,…,2=(s55 则,q=53=125种<128-27 7 code/ sigs 平均码长:IN=7/3=233 code/sig<l2 ※等长码码长要求lN≥logA(保证唯一可译码,无失真) ※logg为下限 ※扩展信源编码的平均码长<基本源编码的平均码长

一、等长码基本问题 则，q=5 3=125种<128=2 7 ∴ l=7 code/3_sigs 平均码长：l/N=7/3=2.33 code/sig <l 2 例1（续） S的三次扩展： ※ 等长码码长要求l/Nlogr q（保证唯一可译码，无失真） ※ logr q为下限 ※ 扩展信源编码的平均码长<基本源编码的平均码长  3  3 1 1 1 1 5 5 5 5 S s s s s s s : ( ), , ( )  =  =

等长码基本问题 例2.英文源S:{26个字母+空格符号},q=27 由q=27<2,得l B5 code/sig 寨效率 H(S=1.4 bit/sig ∴编码后信息传输率:R=H(S)∥=1.4/5=0.28 bitcode 二元信源0,1:H(X)ma2=1 bit/code 編鸡觉余熹式

一、等长码基本问题 例2．英文源S：{26个字母+空格符号} ，q=27 由q=27≤2 l ，得l≥5 code/sig ∴编码后信息传输率：R=H(S)/l=1.4/5=0.28 bit/code 二元信源[0,1]：H(X)max =1 bit/code ➢ H∞ (S)=1.4 bit/sig 平均码长太 长

等长码基本问题 例3:设信源 S S,)P(S)P()P(S3)P(s)l ,∑P)=1h2 code/sig H P(S,1S1)=P(s, 1s2)=P(S41S3)=P(S3154)=1 其余PS|)=0 则二次扩展信源为: L2=2 code/2 sigs 15 F=1 code/sig P(S S, ) P(S, 2)P(25, P(S3S4)P(SS3) ∑P()=∑P(s)PS)|s)=1

例3：设信源 4 1 2 3 4 1 2 3 4 1 , , , , ( ) 1 ( ) ( ) ( ) ( ) ( ) i i i S s s s s P s P s P s P s P s P s =     = =          2 1 1 2 4 3 3 4 ( | ) ( | ) ( | ) ( | ) 1 ( | ) 0 j i P s s P s s P s s P s s P s s = = = = = 且 其余 则二次扩展信源为： 2 1 2 2 1 3 4 4 3 1 2 2 1 3 4 4 3 , , , , ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( | ) 1 i j i j i j i ij ij S s s s s s s s s P s s P s s P s s P s s P s s P s s P s P s s       =          = = l=2 code/sig L2=2 code/2_sigs l=1 code/sig 信源有记忆时，采用N长源编码，l减小 一、等长码基本问题

、等长信源编码定理 定理2-1(等长信源编码定理) 个熵为H(U的离散无记忆信源,若对信源 长为N的符号序列进行等长编码,设码字是从m个 字母的码符号集中选取L个码元组成。对于任意E >0,只要满足:LH(/)+E N lbm 则当N足够大时,可实现几乎无失真编码,即译码 错误概率可为任意小。 反之,若:≥ H(O)-28 lbm 不可能实现无失真编码, 且当N足够大时译码错误概率近似等于1

二、等长信源编码定理 定理2-1（等长信源编码定理） 一个熵为H(U)的离散无记忆信源，若对信源 长为N的符号序列进行等长编码，设码字是从m个 字母的码符号集中选取L个码元组成。对于任意 >0，只要满足： 则当N足够大时，可实现几乎无失真编码，即译码 错误概率可为任意小。 则不可能实现无失真编码， 且当N足够大时译码错误概率近似等于1。 反之，若： lbm H U N L +   ( ) lbm H U N L ( ) − 2 

等长信源编码定理 ※适用于DMS及平稳有记忆信源 ※平均码长下限:Q ※基本方法:N长源、变长编码 ※对等长编码,若要实现几乎无失真编码8↓n个则N个 则信源长度必满足:下2ma-mn 其中, H()H() R b 2=∑p(1)b p(u)IH(UI

※ 适用于DMS及平稳有记忆信源 ※ 平均码长下限： ※ 基本方法：N长源、变长编码 ※ 对等长编码,若要实现几乎无失真编码,       则N 则信源长度必满足: 二、等长信源编码定理 lbm H(U) lbm N L H U R H U ( ) ' ( ) 其中, = = H U pe N 2 2 2 2 ( ) (1 )   −  2 1 2 2 ] [ ( )] ( ) 1 ( )[ H U p u p u lb N i i = i − = 

例4.DMS P)L3/41/4 进行等长编码 解:H(S)=0.811 bit/sig D(s=E[(-{E[(小 0.4715 当8≤105(即P105) 则有:y=0.5得N≥71687 y=0.8得N≥1146990 n=09得N≥5806641 =096得N41291672

当 δ≤10-5（即PE<10-5） 解：H(S)=0.811 bit/sig 例4．DMS 进行等长编码 1 2 ( )i 3 4 1 4 S s s P s / /       =            2 2 0 4715 D I( s ) E I ( s ) E I( s ) . i i i = − =     则有：η=0.5 得N≥71687 η =0.8 得N≥1146990 η =0.9 得N≥5806641 η =0.96 得N≥41291672

字长码的款点得长寓长 攻富道豪北 猪扩袁 襄长他梅点:事个骨字长度可不月 要求:~可聲