3.1离散无记忆信源等长编码
几乎无失真等长编码
选择L 足够长，使
N log D ≥L [H (U ) +εL ]
εL 为与L 有关的正数，且当L →∞时有εL →0, 才其中，
能不损失信息。然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。反之，若N log D
3.2 离散无记忆（简单）信源的等长编码
编码速率
R =N log D /L R =N log D /L ≥log K
关于编码速率的说明：
表示一个长度为N 的D 元码字给一个长度为L 的消息的每个符号所提供的信息量。
3.2 离散无记忆（简单）信源的等长编码
一个消息序列U L 每符号含有信息量算术平均为：
I L =I (u L ) /L =∑I (u l ) /L
l
信源的熵为H(U)
E (I (u l ))=∑p (a k ) I (a k ) =H (U )
k
设I (u l ) 的方差为σI 2
σ=D (I (u l ))=∑p (a k ) (I (a k ) −H (U ))
2I
k
2
3.2 离散无记忆（简单）信源的等长编码
例信源发出的消息序列长度L=8。
a 2⎞⎛a 1
u l ~⎜⎟
⎝1/43/4⎠
⎛I (a 1)I (a 2)⎞
I (u l )~⎜⎟
3/4⎠⎝1/4
2
H (U )=0.81bit
σ=D (I (u l ))=∑p (a k ) (I (a k ) −H (U ))=0.471
2
I
k
长为8的序列是(a1+a2) 8的展开式的所有项，共28个。消息序列的概率是(p1+p2) 8的二项展开式中的各项。
I 8(a 18)=I (a 18)/8=I (a 1)
5
I 8(a 13a 2)=(3I (a 1)+5I (a 2))/8
3.2 离散无记忆（简单）信源的等长编码
3.2.2 信源划分定理
•典型序列集的定义
•令H(U)是集{U , p (a k ) }的熵，ε>0，
T U (L , ε) ={u L :H (U ) −ε≤I L ≤H (U ) +ε}
(I
L
=I (u L )/L , u L ∈U
L
)
•定义为给定信源U 输出长为L 的典型序列集
T U (L , ε) 的补集它称作弱ε典型序列集；相应地，
为非典型序列集。
令u L 是信源{U , p (a k ) }的长为L 的输出序列，ε>0
T U (L , ε) ={u L :L [p (a k ) −ε]≤L k ≤L [p (a k ) +ε]}
其中，L k 是序列中a k 出现的次数。称为强典型序列集。
例4次掷硬币试验强典型序列有{0011}, {1001}, {1100}, {1100}, {0011}, {1010}.
例信源发出的消息序列长度L=8,对其二元随机编码。U ~⎛⎜a 1a 2⎞
⎝1/43/4⎟
⎠
H (U )=0.81bit
σ2I =D (I (a k ))=0.471
I 8的数值：
a 8,a 7a 1,a 6a [**************]12,a 1a 2,a 1a 2,a 1a 2,a 1a 2,a 1a 2,a
2
2, 1.80, 1.60, 1.41, 1.21, 1.01, 0.811, 0.61, 0.415
ε=0.2弱典型序列是a a ,a a ,a a
4412
3512
2612
[1**********]2
1712
82
ε=0.4弱典型序列是a a ,a a ,a a ,a a ,a
44122
3512
2612
1712
82
若对a a ,a a ,a a ,a a ,a 共163个序列编码,错误概率上限是
σ/(L ε
2I
08
)=0.3679.
8
18
7
28
6
2
38
5
3
P e =C (1/4)+C (1/4)(3/4)+C (1/4)(3/4)+C (1/4)(3/4)=0.027
a ,a a ,a a ,a a
[1**********]312
3.2 离散无记忆（简单）信源的等长编码
3.2.3 离散无记忆信源编码定理
•可达
•对于给定的信源和编码速率R 以及任意ε>0存在有L 0，
E ()和D ()，使当L >L 0时，p e
，若
复习
无失真等长编码的充要条件
信源符号{a1,a 2,…,aK } 码字符号{0,1,…,D-1}长l 的消息序列a i1a i2…ail 长为N 的码字n 1n 2…nN
D N ≥K L
N log D /L ≥log K
编码速率R =N log D /L R ≥log K
典型序列集
T U (L , ε) ={u L :H (U ) −ε≤I L ≤H (U ) +ε}
典型序列的数量
(1-ε
L (H (U )-ε) )2≤|T U (L ,
εL (H (U )+ε) )|≤2
特定典型序列出现的概率
若一个特定的事件(u 1u 2…u L ) ∈T U (L , ε) ，则
2-L (H (U )+ε) ≤P {(u 1u 2…u L )=(a i 1a i 2…a i L )}≤2-L (H (U )-ε)
Asymptotic EquipartitionProperty
3.2 离散无记忆（简单）信源的等长编码
3.2.3 离散无记忆信源编码定理编码效率
η=H (U ) /R ≤1
最佳编码时η=H (U ) /[H (U ) +ε]，其
中，
ε>0。
作业
3.1 3.2
3.1离散无记忆信源等长编码
几乎无失真等长编码
选择L 足够长，使
N log D ≥L [H (U ) +εL ]
εL 为与L 有关的正数，且当L →∞时有εL →0, 才其中，
能不损失信息。然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。反之，若N log D
3.2 离散无记忆（简单）信源的等长编码
编码速率
R =N log D /L R =N log D /L ≥log K
关于编码速率的说明：
表示一个长度为N 的D 元码字给一个长度为L 的消息的每个符号所提供的信息量。
3.2 离散无记忆（简单）信源的等长编码
一个消息序列U L 每符号含有信息量算术平均为：
I L =I (u L ) /L =∑I (u l ) /L
l
信源的熵为H(U)
E (I (u l ))=∑p (a k ) I (a k ) =H (U )
k
设I (u l ) 的方差为σI 2
σ=D (I (u l ))=∑p (a k ) (I (a k ) −H (U ))
2I
k
2
3.2 离散无记忆（简单）信源的等长编码
例信源发出的消息序列长度L=8。
a 2⎞⎛a 1
u l ~⎜⎟
⎝1/43/4⎠
⎛I (a 1)I (a 2)⎞
I (u l )~⎜⎟
3/4⎠⎝1/4
2
H (U )=0.81bit
σ=D (I (u l ))=∑p (a k ) (I (a k ) −H (U ))=0.471
2
I
k
长为8的序列是(a1+a2) 8的展开式的所有项，共28个。消息序列的概率是(p1+p2) 8的二项展开式中的各项。
I 8(a 18)=I (a 18)/8=I (a 1)
5
I 8(a 13a 2)=(3I (a 1)+5I (a 2))/8
3.2 离散无记忆（简单）信源的等长编码
3.2.2 信源划分定理
•典型序列集的定义
•令H(U)是集{U , p (a k ) }的熵，ε>0，
T U (L , ε) ={u L :H (U ) −ε≤I L ≤H (U ) +ε}
(I
L
=I (u L )/L , u L ∈U
L
)
•定义为给定信源U 输出长为L 的典型序列集
T U (L , ε) 的补集它称作弱ε典型序列集；相应地，
为非典型序列集。
令u L 是信源{U , p (a k ) }的长为L 的输出序列，ε>0
T U (L , ε) ={u L :L [p (a k ) −ε]≤L k ≤L [p (a k ) +ε]}
其中，L k 是序列中a k 出现的次数。称为强典型序列集。
例4次掷硬币试验强典型序列有{0011}, {1001}, {1100}, {1100}, {0011}, {1010}.
例信源发出的消息序列长度L=8,对其二元随机编码。U ~⎛⎜a 1a 2⎞
⎝1/43/4⎟
⎠
H (U )=0.81bit
σ2I =D (I (a k ))=0.471
I 8的数值：
a 8,a 7a 1,a 6a [**************]12,a 1a 2,a 1a 2,a 1a 2,a 1a 2,a 1a 2,a
2
2, 1.80, 1.60, 1.41, 1.21, 1.01, 0.811, 0.61, 0.415
ε=0.2弱典型序列是a a ,a a ,a a
4412
3512
2612
[1**********]2
1712
82
ε=0.4弱典型序列是a a ,a a ,a a ,a a ,a
44122
3512
2612
1712
82
若对a a ,a a ,a a ,a a ,a 共163个序列编码,错误概率上限是
σ/(L ε
2I
08
)=0.3679.
8
18
7
28
6
2
38
5
3
P e =C (1/4)+C (1/4)(3/4)+C (1/4)(3/4)+C (1/4)(3/4)=0.027
a ,a a ,a a ,a a
[1**********]312
3.2 离散无记忆（简单）信源的等长编码
3.2.3 离散无记忆信源编码定理
•可达
•对于给定的信源和编码速率R 以及任意ε>0存在有L 0，
E ()和D ()，使当L >L 0时，p e
，若
复习
无失真等长编码的充要条件
信源符号{a1,a 2,…,aK } 码字符号{0,1,…,D-1}长l 的消息序列a i1a i2…ail 长为N 的码字n 1n 2…nN
D N ≥K L
N log D /L ≥log K
编码速率R =N log D /L R ≥log K
典型序列集
T U (L , ε) ={u L :H (U ) −ε≤I L ≤H (U ) +ε}
典型序列的数量
(1-ε
L (H (U )-ε) )2≤|T U (L ,
εL (H (U )+ε) )|≤2
特定典型序列出现的概率
若一个特定的事件(u 1u 2…u L ) ∈T U (L , ε) ，则
2-L (H (U )+ε) ≤P {(u 1u 2…u L )=(a i 1a i 2…a i L )}≤2-L (H (U )-ε)
Asymptotic EquipartitionProperty
3.2 离散无记忆（简单）信源的等长编码
3.2.3 离散无记忆信源编码定理编码效率
η=H (U ) /R ≤1
最佳编码时η=H (U ) /[H (U ) +ε]，其
中，
ε>0。
作业
3.1 3.2