2,2,2 变长码
若要实现无失真编码，不但要求信源符号与每个符号
的码字一一对应，而且要求码符号序列与信源符号序
列也一一对应。也就是要求所编的码为惟一可译码。
我们首先分析等长编码，再分析变长编码，以做比较。
一、等长码基本问题
等长码特点：
C2={000,001,100,101,111},l2=3 code/sig
ill?
要求：
iis( 1 ) ??
问题,l?？
例 1．
1 2 3 4 5
1 2 1 4 1 8 1 1 6 1 1 6i
S s s s s s
P ( s ) / / / / /
?? ???
?? ??????
C1={00,01,10,11,10},l1=2 code/sig
(2)高效
一、等长码基本问题
可能的码字数 ≥消息数
对基本信源编码：
对 N长源编码：
1{,,} { }qiS s s W??
112{,,,} { (,,) }N l
N i i i
qS x x? ? ? ?? ? ?
消息数
码字数,rl 12
1
()
{,}
i i i il
ij r
W x x x
x x x
?
?
∴ r l≥q (l≥logrq)
（对例 1,q=5,∴ 要求,2l≥5，即 l ≥ 3）
∴ r l≥qN (l/N≥logrq)
一、等长码基本问题
则, q=53=125种 <128=27
∴ l=7 code/3_sigs
平均码长,l/N=7/3=2.33 code/sig <l2
例 1（续）
S的三次扩展：
※ 等长码码长要求 l/N?logrq（ 保证唯一可译码, 无失真 ）
※ logrq为下限
※ 扩展信源编码的平均码长 <基本源编码的平均码长
? ?33 1 1 1 1 5 5 55,( ),,( )S s s s s s s? ? ? ?
一、等长码基本问题
例 2,英文源 S,{26个字母 +空格符号 }, q=27
由 q=27≤2l,得 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,设信源
4
1 2 3 4
11 2 3 4
,,,,( ) 1
( ) ( ) ( ) ( ) ( ) iii
S s s s s Ps
P s P s P s P s P s ?
? ? ? ???
? ? ? ?? ? ? ? ?
2 1 1 2 4 3 3 4( | ) ( | ) ( | ) ( | ) 1
( | ) 0ji
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
ij
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个码元组成 。 对于任意 ?
>0,只要满足：
则当 N足够大时, 可实现几乎无失真编码, 即译码
错误概率可为任意小 。
则不可能实现无失真编码，
且当 N足够大时译码错误概率近似等于 1。
反之，若：
lb m
UH
N
L ??? )(
lb mUHNL ?2)( ??
※ 适用于 DMS及平稳有记忆信源
※ 平均码长下限：
※ 基本方法,N长源、变长编码
N? ? ? ? ? ?则※ 对等长编码,若要实现几乎无失真编码,
则信源长度必满足,
二、等长信源编码定理
lbm
UH )(
lb mNL
UH
R
UH )(
'
)(,???其中
epUH
N 222 2 )1()( ??? ??
2
1
22 )]([]
)(
1)[( UH
uplbup
N
i i
i ?? ?
?
?
当 δ≤10-5（ 即 PE<10-5）
解,H(S)=0.811 bit/sig
例 4,DMS 进行等长编码
12
() 3 4 1 4i
S ss
Ps //
?? ????? ??
????
? ? ? ?? ? 22 0 4 7 1 5i i iD I ( s ) E I ( s ) E I ( s ),??? ? ???
则有,η=0.5 得 N≥71687
η =0.8 得 N≥1146990
η =0.9 得 N≥5806641
η =0.96 得 N≥41291672
定理 2-2,（ Kraft不等式 ）
设信源符号 S=｛ s1,…,sN｝,码符号 X＝ {x1,…,xm },又设码
字 W1,W2,… Wn的码长分别为 l1,l2,…, ln,则存在惟一可
译码的充要条件是：
三、惟一可译码的判断
※ 码长结构～惟一可译码1,Kraft不等式 编码码元
数目
?
?
? ?
n
i
l im
1
1
1,Kraft不等式 —— 惟一可译码存在的必要条件
例 1．考察：
① l1=1,l2=2,l3=l4=3的二元码
如,C1={1,01,001,000}
C2={0,10,110,111}
② l1=1,l2=l3=l4=2的二元码
∴ 必存在惟一可译码
4
1
74il
i
r/?
?
??
∴ 必不存在惟一可译码
C3={0,00,000,000} 非惟一可译
?
?
? ?4
1
1
i
lim
符号 码 1 码 2 码 3 码 4
等长码 变长码
u1 00 0 0 1
u2 01 10 11 01
u3 10 00 00 001
u3 11 01 11 0001
惟一可译码 非惟一可译 码 非惟一可译 码 惟一可译码
12
1
??
?
?n
i
li
4
52
1
??
?
?n
i
li 452
1
??
?
?n
i
li 1
16
152
1
???
?
?n
i
li
2、根据定义判断
等长码 —— 若为非奇异码，则为唯一可译码；
变长码 —— 码本身及任意次扩展码均非奇异。
? 树图法 （即时码必为惟一可译码）
? 尾随后缀法 （尾随后缀集合 F中不含任一码字）
0
10 11
00
10
01
0
11
1
0
100
110
011
101
0
1
11
1
例 2,C1={0,10,1100,1110,1011,1101}
F:{11,00,10,01,0,11,
1,100,110,011,101}
10
eg:1011001110...
例 2,C2={1,10,100,1000} 1
10
100
0
00
0? F={0,00}
C3={1,01,001,0001}
? F=?
一般离散无记忆信源输出的各消息（符号）的概率是不相等
的。对出现频率大的信源符号采用较短的码字；而对出现概
率小的信源符号采用较长的码字。
从整个信源来看，编成的信源码字的平均码长最短，也实现
了与信源统计特性相匹配。
定义码字的平均码长度：
s i gco d elupL
n
i
ii /,)(
1
?
?
??
平均码长是每个信源符号平均需用的码元数。它和编码后的
压缩效果密切相关。平均码长大，则压缩效果差，系统有效
性差。因此，我们一般选用平均码长最短的编码。
编码后每个码元携带的信息量
就是 信道的信息传输率：
.,,
/,)(
信息传输效率越高越大越短 RL
co d eb i t
L
UHR ?
4
1
( ) / 2 0 843 75ii
i
L P ( s ) l, c ode / si g
?
???
H ( S )R H ( X ),
L 0 9 6? ? ?
LR??则
例 3,对 DMS进行无失真编码 。
12
3 4 1 4i
S S,S
P ( s ) //
?? ????? ??
????
?编码一：基本源编码 —— L=1 code/sig
?编码二,N长源编码
ai P(ai) 码 C li
S1S1 9/16 0 1
S1S2 3/16 10 2
S2S1 3/16 110 3
S2S2 1/16 111 3 L ?目 标,
四、变长信源编码定理
若一个离散无记忆信源 U具有 熵为 H(U)，并有 m个码元的
码符号 X＝｛ x1,x2,? xm｝。则总可以找到一种无失真编
码方法，构成惟一可译码，使信源 S中每个信源符号所需的
平均码长满足：
紧致码,若有一个唯一可译码, 其平均码长小于所
有其他唯一可译码的平均码长, 称此码为 紧
致码 或 最佳码 。
定理 2-3,变长编码定理
四、变长信源编码定理
lb m
UHL
lb m
UH )(1)( ???
证明 若 xi 按如下不等式取所对应码字的码长为 L,
若 为整数,则上述不等式左边取等号,
故可得
1)()( ????? l b m xl b pLl b m xl b p ii
)()()()()()( iiiiii xpl b m xl b pxpLxpl b m xl b pxp ?????
lbm
xlbp i )(?
????
????
????? n
i
i
n
i
iin
i
i
n
i
ii xplbm xlbpxpLxplbm xlbpxp
1111
)()()()()()(
1)()( ??? lb mXHLlb mXH
四、变长信源编码定理
因为
所以
所有码字长度满足 Kraft不等式
如何降低平均码长：
（ 1） 减少信源熵 H(X)
（ 2） 增加信道码元数 m
)()( ii xl bpl bmLl bm xl bpL ????
)()( iLi xl b pl b mxl b pl b mL ??? ?
1)()(
11
??? ??
??
??
n
i
i
n
i
L
i
L xpmxpm
四、变长信源编码定理
注意到 li∈ Z,∴ 取其整数部分
例 3．
1
,( )
i
iPs r
?
???
??
??
设
,iil ??若 1 iiiiL P ( s ) l ( )r ?? ? ???则
1 1 1,( ) ( )i i i
ii
i
H ( S ) P log log r log rP r r? ? ?? ? ? ?? ? ?又
()HSL
l og r??
()i
i
l o g P sl
l o g r
????
??
四、变长信源编码定理
DMS的 N次扩展信源 UN＝｛ ?1,?2,?? nN｝，其熵为
H(UN)，并有码符号 X＝｛ x1,x2,? xn｝。对信源 UN进行编
码，总可以找到一种编码方法，构成惟一可译码，使信源 U
中每个信源符号所需的平均码长满足：
定理 2-4,香农第一定理 （无失真 变长 信源编码定理）
四、变长信源编码定理
且当 N??时, 有：
其中,为 N长源编码的平均码长,?i是 ?i所对
应的码字长度。
l b m
UH
NN
L
l b m
UH N )(1)( ???
)()(lim UHl b mUHNL mNN ????
??? Nni iiN pL 1 )( ??
信源 X 的 N次扩展信源 XN
XN 的信源熵为 H(XN) bit/N个信源符号
XN 所对应码字的码长 码符 /N个信源符号
NL
1)()( ??? l b mXHLl b mXH
N
N
N
N
LL N?)(1)( NXH
NXH ?
1)()( ??? l b m XNHLNl b m XNH
Nlb m
XHL
lb m
XH 1)()( ??? lbmXHL )(?
① 平均码长的下限
即信源熵是无失真信源编码的最小平均码长 ！
② 存在性定理
方法,N长源, 变长码
③ 适用于平稳有记忆信源, H(U)=H∞
四、变长信源编码定理
)()( UHlb mUHL m??
)(,UHLLN m???? 理
表述三,（ 无噪信道编码定理 ）
若信道的信息传输率 R不大于信道容量, 总能
对信源的输出进行适当编码, 使得在无损无噪信
道上能无差错地以最大信息传输率 C传输信息；
但要使信道信息传输率 R大于 C而无差错地传输则
是不可能的 。
表述二,若 R? >H(S),就存在唯一可译变长编码；若
R?<H(S),唯一可译变长编码不存在, 不能实现无
失真编码 。
四、变长信源编码定理
编码后每个信源符号能载荷的最大信息量为：
c o d eb itlb mNLR N /,'?
表述四：
设信源熵为 H（比特 /符号），无噪无
损信道的信道容量为 Ct（比特 /秒），则总
可以找到一种编码方法对信源的输出进行无
失真编码，使得在信道上传输的平均码速率
为（ Ct /H-ε ）（符号 /秒），其中 ε 为任意
小的正数，但要使传输的平均码速率大于 Ct
/ H（符号 /秒）是不可能的。
四、变长信源编码定理
四、变长信源编码定理
若对信源 U进行编码所得到的平均码长，因为平均码长一定
大于或等于 Hm(U)，所以定义编码的效率为：
1)( ?? L UH m?
对同一信源来说，码的平均码长越短，越接近极限值 Hm(U)，信道
的信息传输率就越高，越接近无噪无损信道容量。
码剩余度定义：
L
UH m )(11 ??? ?
对于二元无噪无损信道 m=2,Hm(U)=H(U)
L
UHR )(?? ?
αi P(αi) 码 C λi
s1s1 9/16 0 1
s1s2 3/16 10 2
s2s1 3/16 110 3
s2s2 1/16 111 3
例 3,比较 N长源编码的效率。
12
3 4 1 4i
S ss
P ( s ) //
?? ???
?? ??????
解,H(S)=0.811 bit/sig
121 0 1 1N s,s,L,? ? ? ?对, 0 8 1 1
H ( S )R.
L? ? ? ?
4
2
1
27 16 2ii
i
L P ( ) / c ode / _ si gs
?
? ? ? ??
2 27 0 8 42 3 2L, c o d e / si g??
() 0 9 6 1HSR.
L? ? ? ?
四、变长信源编码定理
五、统计匹配编码
离散无失真编码实质上是一种统计匹配编码，是根据信源
符号的不同概率分布分配与之相对应码字，对出现概率大
的符号分配短的码字，对出现概率小的符号分配长的码字，
这样可以使信源符号的平均码长最短。
编码器输入,),,,(),,,,,( 211 nlLl uuussssS ??? ??
编码器输出的码字为,),,,(),,,,,( 211 mkKk bbbxxxxX ??? ??
要实现无失真信源编码，必须同时满足无失真和有效性两
个条件，只能从信源统计特性上去考虑。
m
UH
m
n
L
K
aa
a
lo g
)(
lo g
lo g ??
若要实现无失真编码，不但要求信源符号与每个符号
的码字一一对应，而且要求码符号序列与信源符号序
列也一一对应。也就是要求所编的码为惟一可译码。
我们首先分析等长编码，再分析变长编码，以做比较。
一、等长码基本问题
等长码特点：
C2={000,001,100,101,111},l2=3 code/sig
ill?
要求：
iis( 1 ) ??
问题,l?？
例 1．
1 2 3 4 5
1 2 1 4 1 8 1 1 6 1 1 6i
S s s s s s
P ( s ) / / / / /
?? ???
?? ??????
C1={00,01,10,11,10},l1=2 code/sig
(2)高效
一、等长码基本问题
可能的码字数 ≥消息数
对基本信源编码：
对 N长源编码：
1{,,} { }qiS s s W??
112{,,,} { (,,) }N l
N i i i
qS x x? ? ? ?? ? ?
消息数
码字数,rl 12
1
()
{,}
i i i il
ij r
W x x x
x x x
?
?
∴ r l≥q (l≥logrq)
（对例 1,q=5,∴ 要求,2l≥5，即 l ≥ 3）
∴ r l≥qN (l/N≥logrq)
一、等长码基本问题
则, q=53=125种 <128=27
∴ l=7 code/3_sigs
平均码长,l/N=7/3=2.33 code/sig <l2
例 1（续）
S的三次扩展：
※ 等长码码长要求 l/N?logrq（ 保证唯一可译码, 无失真 ）
※ logrq为下限
※ 扩展信源编码的平均码长 <基本源编码的平均码长
? ?33 1 1 1 1 5 5 55,( ),,( )S s s s s s s? ? ? ?
一、等长码基本问题
例 2,英文源 S,{26个字母 +空格符号 }, q=27
由 q=27≤2l,得 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,设信源
4
1 2 3 4
11 2 3 4
,,,,( ) 1
( ) ( ) ( ) ( ) ( ) iii
S s s s s Ps
P s P s P s P s P s ?
? ? ? ???
? ? ? ?? ? ? ? ?
2 1 1 2 4 3 3 4( | ) ( | ) ( | ) ( | ) 1
( | ) 0ji
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
ij
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个码元组成 。 对于任意 ?
>0,只要满足：
则当 N足够大时, 可实现几乎无失真编码, 即译码
错误概率可为任意小 。
则不可能实现无失真编码，
且当 N足够大时译码错误概率近似等于 1。
反之，若：
lb m
UH
N
L ??? )(
lb mUHNL ?2)( ??
※ 适用于 DMS及平稳有记忆信源
※ 平均码长下限：
※ 基本方法,N长源、变长编码
N? ? ? ? ? ?则※ 对等长编码,若要实现几乎无失真编码,
则信源长度必满足,
二、等长信源编码定理
lbm
UH )(
lb mNL
UH
R
UH )(
'
)(,???其中
epUH
N 222 2 )1()( ??? ??
2
1
22 )]([]
)(
1)[( UH
uplbup
N
i i
i ?? ?
?
?
当 δ≤10-5（ 即 PE<10-5）
解,H(S)=0.811 bit/sig
例 4,DMS 进行等长编码
12
() 3 4 1 4i
S ss
Ps //
?? ????? ??
????
? ? ? ?? ? 22 0 4 7 1 5i i iD I ( s ) E I ( s ) E I ( s ),??? ? ???
则有,η=0.5 得 N≥71687
η =0.8 得 N≥1146990
η =0.9 得 N≥5806641
η =0.96 得 N≥41291672
定理 2-2,（ Kraft不等式 ）
设信源符号 S=｛ s1,…,sN｝,码符号 X＝ {x1,…,xm },又设码
字 W1,W2,… Wn的码长分别为 l1,l2,…, ln,则存在惟一可
译码的充要条件是：
三、惟一可译码的判断
※ 码长结构～惟一可译码1,Kraft不等式 编码码元
数目
?
?
? ?
n
i
l im
1
1
1,Kraft不等式 —— 惟一可译码存在的必要条件
例 1．考察：
① l1=1,l2=2,l3=l4=3的二元码
如,C1={1,01,001,000}
C2={0,10,110,111}
② l1=1,l2=l3=l4=2的二元码
∴ 必存在惟一可译码
4
1
74il
i
r/?
?
??
∴ 必不存在惟一可译码
C3={0,00,000,000} 非惟一可译
?
?
? ?4
1
1
i
lim
符号 码 1 码 2 码 3 码 4
等长码 变长码
u1 00 0 0 1
u2 01 10 11 01
u3 10 00 00 001
u3 11 01 11 0001
惟一可译码 非惟一可译 码 非惟一可译 码 惟一可译码
12
1
??
?
?n
i
li
4
52
1
??
?
?n
i
li 452
1
??
?
?n
i
li 1
16
152
1
???
?
?n
i
li
2、根据定义判断
等长码 —— 若为非奇异码，则为唯一可译码；
变长码 —— 码本身及任意次扩展码均非奇异。
? 树图法 （即时码必为惟一可译码）
? 尾随后缀法 （尾随后缀集合 F中不含任一码字）
0
10 11
00
10
01
0
11
1
0
100
110
011
101
0
1
11
1
例 2,C1={0,10,1100,1110,1011,1101}
F:{11,00,10,01,0,11,
1,100,110,011,101}
10
eg:1011001110...
例 2,C2={1,10,100,1000} 1
10
100
0
00
0? F={0,00}
C3={1,01,001,0001}
? F=?
一般离散无记忆信源输出的各消息（符号）的概率是不相等
的。对出现频率大的信源符号采用较短的码字；而对出现概
率小的信源符号采用较长的码字。
从整个信源来看，编成的信源码字的平均码长最短，也实现
了与信源统计特性相匹配。
定义码字的平均码长度：
s i gco d elupL
n
i
ii /,)(
1
?
?
??
平均码长是每个信源符号平均需用的码元数。它和编码后的
压缩效果密切相关。平均码长大，则压缩效果差，系统有效
性差。因此，我们一般选用平均码长最短的编码。
编码后每个码元携带的信息量
就是 信道的信息传输率：
.,,
/,)(
信息传输效率越高越大越短 RL
co d eb i t
L
UHR ?
4
1
( ) / 2 0 843 75ii
i
L P ( s ) l, c ode / si g
?
???
H ( S )R H ( X ),
L 0 9 6? ? ?
LR??则
例 3,对 DMS进行无失真编码 。
12
3 4 1 4i
S S,S
P ( s ) //
?? ????? ??
????
?编码一：基本源编码 —— L=1 code/sig
?编码二,N长源编码
ai P(ai) 码 C li
S1S1 9/16 0 1
S1S2 3/16 10 2
S2S1 3/16 110 3
S2S2 1/16 111 3 L ?目 标,
四、变长信源编码定理
若一个离散无记忆信源 U具有 熵为 H(U)，并有 m个码元的
码符号 X＝｛ x1,x2,? xm｝。则总可以找到一种无失真编
码方法，构成惟一可译码，使信源 S中每个信源符号所需的
平均码长满足：
紧致码,若有一个唯一可译码, 其平均码长小于所
有其他唯一可译码的平均码长, 称此码为 紧
致码 或 最佳码 。
定理 2-3,变长编码定理
四、变长信源编码定理
lb m
UHL
lb m
UH )(1)( ???
证明 若 xi 按如下不等式取所对应码字的码长为 L,
若 为整数,则上述不等式左边取等号,
故可得
1)()( ????? l b m xl b pLl b m xl b p ii
)()()()()()( iiiiii xpl b m xl b pxpLxpl b m xl b pxp ?????
lbm
xlbp i )(?
????
????
????? n
i
i
n
i
iin
i
i
n
i
ii xplbm xlbpxpLxplbm xlbpxp
1111
)()()()()()(
1)()( ??? lb mXHLlb mXH
四、变长信源编码定理
因为
所以
所有码字长度满足 Kraft不等式
如何降低平均码长：
（ 1） 减少信源熵 H(X)
（ 2） 增加信道码元数 m
)()( ii xl bpl bmLl bm xl bpL ????
)()( iLi xl b pl b mxl b pl b mL ??? ?
1)()(
11
??? ??
??
??
n
i
i
n
i
L
i
L xpmxpm
四、变长信源编码定理
注意到 li∈ Z,∴ 取其整数部分
例 3．
1
,( )
i
iPs r
?
???
??
??
设
,iil ??若 1 iiiiL P ( s ) l ( )r ?? ? ???则
1 1 1,( ) ( )i i i
ii
i
H ( S ) P log log r log rP r r? ? ?? ? ? ?? ? ?又
()HSL
l og r??
()i
i
l o g P sl
l o g r
????
??
四、变长信源编码定理
DMS的 N次扩展信源 UN＝｛ ?1,?2,?? nN｝，其熵为
H(UN)，并有码符号 X＝｛ x1,x2,? xn｝。对信源 UN进行编
码，总可以找到一种编码方法，构成惟一可译码，使信源 U
中每个信源符号所需的平均码长满足：
定理 2-4,香农第一定理 （无失真 变长 信源编码定理）
四、变长信源编码定理
且当 N??时, 有：
其中,为 N长源编码的平均码长,?i是 ?i所对
应的码字长度。
l b m
UH
NN
L
l b m
UH N )(1)( ???
)()(lim UHl b mUHNL mNN ????
??? Nni iiN pL 1 )( ??
信源 X 的 N次扩展信源 XN
XN 的信源熵为 H(XN) bit/N个信源符号
XN 所对应码字的码长 码符 /N个信源符号
NL
1)()( ??? l b mXHLl b mXH
N
N
N
N
LL N?)(1)( NXH
NXH ?
1)()( ??? l b m XNHLNl b m XNH
Nlb m
XHL
lb m
XH 1)()( ??? lbmXHL )(?
① 平均码长的下限
即信源熵是无失真信源编码的最小平均码长 ！
② 存在性定理
方法,N长源, 变长码
③ 适用于平稳有记忆信源, H(U)=H∞
四、变长信源编码定理
)()( UHlb mUHL m??
)(,UHLLN m???? 理
表述三,（ 无噪信道编码定理 ）
若信道的信息传输率 R不大于信道容量, 总能
对信源的输出进行适当编码, 使得在无损无噪信
道上能无差错地以最大信息传输率 C传输信息；
但要使信道信息传输率 R大于 C而无差错地传输则
是不可能的 。
表述二,若 R? >H(S),就存在唯一可译变长编码；若
R?<H(S),唯一可译变长编码不存在, 不能实现无
失真编码 。
四、变长信源编码定理
编码后每个信源符号能载荷的最大信息量为：
c o d eb itlb mNLR N /,'?
表述四：
设信源熵为 H（比特 /符号），无噪无
损信道的信道容量为 Ct（比特 /秒），则总
可以找到一种编码方法对信源的输出进行无
失真编码，使得在信道上传输的平均码速率
为（ Ct /H-ε ）（符号 /秒），其中 ε 为任意
小的正数，但要使传输的平均码速率大于 Ct
/ H（符号 /秒）是不可能的。
四、变长信源编码定理
四、变长信源编码定理
若对信源 U进行编码所得到的平均码长，因为平均码长一定
大于或等于 Hm(U)，所以定义编码的效率为：
1)( ?? L UH m?
对同一信源来说，码的平均码长越短，越接近极限值 Hm(U)，信道
的信息传输率就越高，越接近无噪无损信道容量。
码剩余度定义：
L
UH m )(11 ??? ?
对于二元无噪无损信道 m=2,Hm(U)=H(U)
L
UHR )(?? ?
αi P(αi) 码 C λi
s1s1 9/16 0 1
s1s2 3/16 10 2
s2s1 3/16 110 3
s2s2 1/16 111 3
例 3,比较 N长源编码的效率。
12
3 4 1 4i
S ss
P ( s ) //
?? ???
?? ??????
解,H(S)=0.811 bit/sig
121 0 1 1N s,s,L,? ? ? ?对, 0 8 1 1
H ( S )R.
L? ? ? ?
4
2
1
27 16 2ii
i
L P ( ) / c ode / _ si gs
?
? ? ? ??
2 27 0 8 42 3 2L, c o d e / si g??
() 0 9 6 1HSR.
L? ? ? ?
四、变长信源编码定理
五、统计匹配编码
离散无失真编码实质上是一种统计匹配编码，是根据信源
符号的不同概率分布分配与之相对应码字，对出现概率大
的符号分配短的码字，对出现概率小的符号分配长的码字，
这样可以使信源符号的平均码长最短。
编码器输入,),,,(),,,,,( 211 nlLl uuussssS ??? ??
编码器输出的码字为,),,,(),,,,,( 211 mkKk bbbxxxxX ??? ??
要实现无失真信源编码，必须同时满足无失真和有效性两
个条件，只能从信源统计特性上去考虑。
m
UH
m
n
L
K
aa
a
lo g
)(
lo g
lo g ??
