信源编码（ 2）
数学与计算机科学学院 朱西平
(xpzhu188@163.com )
信源及其分类信源就是信息的来源
在一个固定的时刻，信源发出的是一个随机变量
随着时间的延续，信源发出的是一个随机过程信源及其分类离散信源 信源 每隔一个定长时间段就发出一个随机变量 ；
随着时间的延续，信源发出的是随机变量序列
… U-2U-1U0U1U2…,
其中
Uk为第 k个时间段发出的随机变量；
每个 Uk都是一个离散型的随机变量 。
离散无记忆信源 离散无记忆信源是这样的离散信源,随机变量 …,U-2,U-1,U0,U1,U2,… 相互独立 。
离散无记忆简单信源 离散无记忆简单信源是这样的离散无记忆信源,随机变量 …,U-2,U-1,U0,U1,U2,…
具有 相同的概率分布 。
信源及其分类总结
离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。
信源及其分类
连续信源,有时间连续的信源，也有事件连续的信源
有记忆信源,信源在不同时刻发出的随机变量相互依赖
有限记忆信源,在有限时间差内的信源随机变量相互依赖
非简单信源,信源在不同时刻发出的随机变量具有不同的概率分布
马尔可夫信源,信源随机过程是马尔可夫过程离散无记忆（简单）信源的等长编码
设有一个离散无记忆简单信源，信源发出的随机变量序列为,… U-2U-1U0U1U2… 。设信源随机变量 U1的事件有 K个,{a1,a2,…,aK}，则 L维信源随机向量
(U1U2… UL)的事件有 KL个：
{(u1u2… uL)|其中每个分量 ul跑遍 {a1,a2,…,aK}}。
设有一个含 D个字母的字母表 {b1,b2,…,bD}。需要用字母串来表示 (U1U2… UL)的事件，每一个事件都要用一个字母串来表示。
这种表示方法称为 D元编码 ；
每一个事件所对应的字母串称为一个 码字离散无记忆（简单）信源的等长编码例,离散无记忆简单信源发出的随机变量序列为,… U-2U-
1U0U1U2… 。其中 U1的事件有 3个,{晴,云,阴 }。
(U1U2)有 9个事件
{（晴晴），（晴云），（晴阴），（云晴），（云云），
（云阴），（阴晴），（阴云）,（阴阴） }。
用字母表 {0,1}对 (U1U2)的事件进行 2元编码如下：
（晴晴） → 0000，（晴云） → 0001，（晴阴） → 0011，
（云晴） → 0100，（云云） → 0101，（云阴） → 0111，
（阴晴） → 1100，（阴云） → 1101，（阴阴） → 1111。
离散无记忆（简单）信源的等长编码
如果限定码字的长度为 N（即每个码字都是一个 N维向量），则称此编码为 等长编码,能够选择的不同码字的个数为 DN。
如果限定码字的长度为 ≤N（即每个码字都是一个 ≤N维的向量），则称此编码为 不等长编码,能够选择的不同码字的个数为
D1+D2+…+ DN=D(DN-1)/(D-1)。
注意：在不等长编码中，并不能同时使用 D(DN-1)/(D-1)
个不同的码字。一个长度为 2的字母串究竟是两个长度为 1的码字相连，还是一个长度为 2的码字？无法识别。
在等长编码中不存在这样的识别问题 ）
离散无记忆（简单）信源的等长编码
编码速率,R=NlogD/L。
无错编码 (U1U2… UL)的不同事件用不同的码字来表示。
能够实现无错编码的充要条件是 DN≥KL。（即编码速率
R=NlogD/L≥logK）
有错编码 (U1U2… UL)的有些不同事件用相同的码字来表示。
有错编码的译码方法与,译码错误,概率 当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）。,译码错误,的概率定义为
pe= P{(U1U2… UL)=(u1u2… uL)
| (u1u2… uL)的码字在译码时并不译为 (u1u2… uL)}。
离散无记忆（简单）信源的等长编码
编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率 R0，然后选择 N和 L，使得实际的编码速率 NlogD/L不能超过编码设备的编码速率
R0,
R=NlogD/L≤R0。
当编码速率 R比较高时，可以选择比较大的 N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。 当编码速率 R比较低时，
意味着使用低成本的编码设备。此时只能选择不大的 N，
因此更需要编码的技巧。
离散无记忆（简单）信源的等长编码在无错编码的前提下，编码的最低代价
当 R≥logK时，能够实现无错编码。
当 R<H(U1)时，无论怎样编码都是有错编码。这是因为
R<H(U1)≤logK。
（如果 H(U1)=logK，则以上两种情形已经概括了全部情形。但如果 H(U1)<logK，则还有一种情形）
当 logK>R>H(U1)时，虽然无论怎样编码都是有错编码，
但可以适当地编码和译码使译码错误的概率 pe任意小。
这就是所谓,渐进无错编码,。
离散无记忆（简单）信源的等长编码
渐进无错编码 （简单地说就是：当 R>H(U1)时，可以适当地编码和译码使得译码错误的概率 pe任意小。严格地说就是：） 设给定了编码设备的编码速率 R0，
R0>H(U1)。则对任意的 ε>0，总存在一个 L0，使得对任意的 L>L0，都有对 (U1U2… UL)的等长编码和对应的译码方法，满足
①实际的编码速率 R=NlogD/L≤R0，
②译码错误的概率 pe<ε。
渐进无错编码的原理 大数定律。随着 L的增加，
(U1U2… UL)的所有事件中，某些事件所占的比例越来越小（ → 0），其发生的概率却越来越大（ → 1）。
离散无记忆（简单）信源的等长编码
不能渐进无错的编码 （简单地说就是：当 R<H(U1)时，
无论怎样编码和译码都不能使译码错误的概率 pe任意小。严格地说就是,） 设给定了编码设备的编码速率
R0,R0<H(U1)。则无论怎样编码和译码都不能同时满足
①实际的编码速率 R≤R0，
②译码错误的概率 pe任意小。
离散无记忆（简单）信源的等长编码设 … U-2U-1U0U1U2… 是离散无记忆（简单）信源的输出随机变量序列。设 U1的概率分布为取 Vl是 Ul的如下函数：当 Ul=ak时,Vl=loga(1/qk)。则
①随机变量序列 … V-2V-1V0V1V2… 相互独立，具有相同的概率分布；
②
K
K
qqq
aaaU
21
21
1 ~
)(1l o g 1
1
1 UHqqEV
K
k k
ak
离散无记忆（简单）信源的等长编码取 IL是 (V1V2… VL)的如下函数：
则
① IL最终是 (U1U2… UL)的函数；
②
③因此有切比雪夫不等式：对任意 ε>0有
P{(U1U2… UL)=(u1u2… uL)|H(U1)-ε≤IL≤H(U1)+ε}≥
L
l
lL VLI
1
1
)(1 1
1
UHEVLEI
L
l
lL
1
1
2
1
111 DV
LDVLVLDDI
L
l
l
L
l
lL
2
11
L
DV?
离散无记忆（简单）信源的等长编码取 L0使得则当 L≥L0时总有因此当 L≥L0时总有
P{(U1U2… UL)=(u1u2… uL)|H(U1)-ε≤IL≤H(U1)+ε}
≥1-ε。
2
0
1
L
DV
21LDV
离散无记忆（简单）信源的等长编码定义 1 定义
TU(L,ε)={(u1u2… uL)|H(U1)-ε≤IL≤H(U1)+ε}，
称 TU(L,ε)为 ε-典型序列集。
称 TU(L,ε)的补集为非 ε-典型序列集。
（综上所述有）
定理 1(信源划分定理 ) 对任意 ε>0，取 L0使得则当 L≥L0时总有 P{(U1U2… UL)∈ TU(L,ε)}≥1-ε。
2
0
1
L
DV
2005-7-18 18
离散无记忆（简单）信源的等长编码
（简记 H(U)=H(U1)。设以下的对数都是以 2为底的。）
特定典型序列出现的概率 若一个特定的事件
(u1u2… uL)∈ TU(L,ε)，则
2-L(H(U)+ε)≤P{(U1U2… UL)=(u1u2… uL)}≤2-L(H(U)-ε)。
证明（略）
典型序列的数量
(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)
证明（略）
离散无记忆（简单）信源的等长编码设给定一个 R0>H(U)。对每个正整数 L，对应地取整数
N=[R0L]（ R0L的下取整）。则
N/L≤R0，
limL→ +∞N/L=R0。
任取正数 ε≤(R0 -H(U))/2，存在正整数 L0，当 L>L0时
（ 1） N/L≥R0-(R0 -H(U))/2=H(U)+(R0-H(U))/2≥H(U)+ε。
（ 2） P{(U1U2… UL)∈ TU(L,ε)}≥1-ε。
离散无记忆（简单）信源的等长编码无错编码正定理给定编码设备的编码速率 R0,R0>H(U)。则对任意的
ε>0，总存在一个 L0，使得对任意的 L>L0，都有对
(U1U2… UL)的 2元等长编码方法和对应的译码方法，
①实际的编码速率 R满足
R0≥R>H(U)，
②,译码错误,的概率 pe<ε。
无错编码反定理设给定编码设备的编码速率 R0，满足 R0<H(U)。当限制实际的编码速率 R≤R0时，无论怎样编码和译码都不能使,译码错误,的概率任意小
§ 3.2 离散无记忆（简单）信源的等长编码例 设
996.0004.0~
21 aaU
l
2
1
0 0 5 7 4 7.0
9 9 6.0
1
l o g
9 6 5 7 8 4.7
0 0 4.0
1
l o g
aU
aU
V
l
l
l其中：
996.0004.0
005747.0965784.7~
lV
)(0 3 7 5 8 7 1 4 8.0 UHEV l
2 5 2 4 3 4 9 6.0
)0 3 7 5 8 7 1 4 8.0()0 0 5 7 4 7.0(996.0)9 6 5 7 8 4.7(004.0
)(
222
22
lll EVEVDV
离散无记忆（简单）信源的等长编码设给定编码设备的编码速率 R0=0.5。则
R0>0.037587148=H(U)。
希望：
① 2元编码的实际编码速率 R≤R0；
②译码错误的概率不超过 ε。其中取
ε=0.1；
ε=0.05；
ε=0.01。
离散无记忆（简单）信源的等长编码取 ε=0.1。找 L0使得即 L0=253。当 L≥253时总有
P{(U1U2… UL)=(u1u2… uL)| -0.1≤IL-H(U) ≤0.1}≥0.9。
另一方面，当事件 (u1u2… uL)中 a1的个数为 k,a2的个数为 L-k时，
2
0
1
L
DV 43496.252
3
1
0
DVL
0 05 74 7.09 60 03 7.70 05 74 7.09 65 78 4.7 LkL kLLkI L
03 18 40 14 8.096 00 37.7)( LkUHI L
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.1)；当且仅当
-0.1≤IL-H(U) ≤0.1；当且仅当；当且仅当1.00 31 8 40 1 48.09 60 0 37.71.0 Lk；当且仅当LkL 0 1 6 5 6 2 7 6.00 0 8 5 6 2 7 6.0
Lk 0 1 6 5 6 2 7 6.00
离散无记忆（简单）信源的等长编码设 L=253。此时 0.01656276L=4.19037828。
当事件 (u1u2… u253)中 a1的个数不超过 4时，
(u1u2… u253)∈ TU(253,0.1)；
否则 (u1u2… u253)不属于 TU(253,0.1)。
(u1u2… u253)∈ TU(253,0.1)的概率不小于 0.9；
(u1u2… u253)∈ TU(253,0.1)的个数为
6.2 1 92 5 33 5 5 5 5 7 4 4 4.33
3 5 5 5 5 7 4 4 4.33)1.0)((
4
0
2 5 3
22/2
22
占全部事件的比例为；UHL
k
kC
离散无记忆（简单）信源的等长编码对 L=253，对应地取整数 N=[R0L]=126。则 N/L<R0，这就是说 2
元编码的实际编码速率并未超出编码设备的编码速率。 2元编码的编码方法,将 TU(253,0.1)中的事件用不同的 126长码字表示；将 TU(253,0.1)外的事件用同一个 126长码字表示，
该码字已经用于表示了 TU(253,0.1)中的一个事件。由于
|TU(253,0.1)|≤233.355557444<2126，码字足够用。 2元编码的译码方法,将码字译为它所表示的 TU(253,0.1)中的事件
(u1u2… u253) 。于是，译码错误的概率为
P((u1u2… u253)不属于 TU(253,0.1))≤ε=0.1。
离散无记忆（简单）信源的等长编码取 ε=0.05。找 L0使得即 L0=2020。当 L≥2020时总有
P{(U1U2… UL)=(u1u2… uL)| -0.05≤IL-H(U) ≤0.05}≥0.95。
另一方面，当事件 (u1u2… uL)中 a1的个数为 k,a2的个数为 L-k时，
2
0
1
L
DV 4 7 9 6 8.2 0 1 9
3
1
0
DVL
0 05 74 7.09 60 03 7.70 05 74 7.09 65 78 4.7 LkL kLLkI L
03 18 40 14 8.096 00 37.7)( LkUHI L
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.05)；当且仅当
-0.05≤IL-H(U) ≤0.05；当且仅当；当且仅当05.003 18 40 14 8.096 00 37.705.0 Lk；当且仅当LkL 0 1 0 2 8 1 3 7.00 0 2 2 8 1 3 7.0
Lk 0 1 0 2 8 1 3 7.00
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.05)；当且仅当
-0.05≤IL-H(U) ≤0.05；当且仅当；当且仅当05.003 18 40 14 8.096 00 37.705.0 Lk；当且仅当LkL 0 1 0 2 8 1 3 7.00 0 2 2 8 1 3 7.0
Lk 0 1 0 2 8 1 3 7.00
离散无记忆（简单）信源的等长编码对 L=2020，对应地取整数 N=[R0L]=1010。则 N/L=R0，这就是说 2元编码的实际编码速率等于编码设备的编码速率。 2元编码的编码方法,将 TU(2020,0.05)中的事件用不同的 1010
长码字表示；将 TU(2020,0.05)外的事件用同一个 1010长码字表示，该码字已经用于表示了 TU(2020,0.05)中的一个事件。由于 |TU(2020,0.05)|≤2176.92603896<21010，码字足够用。 2
元编码的译码方法,将码字译为它所表示的 TU(2020,0.05)
中的事件 (u1u2… u2020) 。于是，译码错误的概率为
P((u1u2… u2020)不属于 TU(2020,0.05))≤ε=0.05。
离散无记忆（简单）信源的等长编码取 ε=0.01。找 L0使得即 L0=252435。当 L≥252435时总有
P{(U1U2… UL)=(u1u2… uL)| -0.01≤IL-H(U) ≤0.01}≥0.99。
另一方面，当事件 (u1u2… uL)中 a1的个数为 k,a2的个数为 L-k时，
2
0
1
L
DV 96.2 5 2 4 3 4
3
1
0
DVL
0 05 74 7.09 60 03 7.70 05 74 7.09 65 78 4.7 LkL kLLkI L
03 18 40 14 8.096 00 37.7)( LkUHI L
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.01)；当且仅当
-0.01≤IL-H(U) ≤0.01；当且仅当；当且仅当01.003 18 40 1 48.096 00 37.701.0 Lk
LkL 0 0 5 2 5 6 2 8.00 0 2 7 4 3 7 2.0
离散无记忆（简单）信源的等长编码设 L=252435。此时
0.00274372L=692.61096 ； 0.00525628L=1326.8690 。
当事件 (u1u2… u252435)中 a1的个数不超出闭区间 [693,1326]内时,(u1u2… u252435)∈ TU(252435,0.01)；
否则 (u1u2… u252435)不属于 TU(252435,0.01)。
(u1u2… u252435)∈ TU(252435,0.01)的概率不小于 0.99；
(u1u2… u252435)∈ TU(252435,0.01)的个数为
34.2 4 04 2 22 5 24 3 56 6 17.1 2 01 2
6 6 17.1 2 01 2)01.0)((
1 3 26
693
2 5 24 3 5
22/2
22
占全部事件的比例为；UHL
k
kC
数学与计算机科学学院 朱西平
(xpzhu188@163.com )
信源及其分类信源就是信息的来源
在一个固定的时刻，信源发出的是一个随机变量
随着时间的延续，信源发出的是一个随机过程信源及其分类离散信源 信源 每隔一个定长时间段就发出一个随机变量 ；
随着时间的延续，信源发出的是随机变量序列
… U-2U-1U0U1U2…,
其中
Uk为第 k个时间段发出的随机变量；
每个 Uk都是一个离散型的随机变量 。
离散无记忆信源 离散无记忆信源是这样的离散信源,随机变量 …,U-2,U-1,U0,U1,U2,… 相互独立 。
离散无记忆简单信源 离散无记忆简单信源是这样的离散无记忆信源,随机变量 …,U-2,U-1,U0,U1,U2,…
具有 相同的概率分布 。
信源及其分类总结
离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。
信源及其分类
连续信源,有时间连续的信源，也有事件连续的信源
有记忆信源,信源在不同时刻发出的随机变量相互依赖
有限记忆信源,在有限时间差内的信源随机变量相互依赖
非简单信源,信源在不同时刻发出的随机变量具有不同的概率分布
马尔可夫信源,信源随机过程是马尔可夫过程离散无记忆（简单）信源的等长编码
设有一个离散无记忆简单信源，信源发出的随机变量序列为,… U-2U-1U0U1U2… 。设信源随机变量 U1的事件有 K个,{a1,a2,…,aK}，则 L维信源随机向量
(U1U2… UL)的事件有 KL个：
{(u1u2… uL)|其中每个分量 ul跑遍 {a1,a2,…,aK}}。
设有一个含 D个字母的字母表 {b1,b2,…,bD}。需要用字母串来表示 (U1U2… UL)的事件，每一个事件都要用一个字母串来表示。
这种表示方法称为 D元编码 ；
每一个事件所对应的字母串称为一个 码字离散无记忆（简单）信源的等长编码例,离散无记忆简单信源发出的随机变量序列为,… U-2U-
1U0U1U2… 。其中 U1的事件有 3个,{晴,云,阴 }。
(U1U2)有 9个事件
{（晴晴），（晴云），（晴阴），（云晴），（云云），
（云阴），（阴晴），（阴云）,（阴阴） }。
用字母表 {0,1}对 (U1U2)的事件进行 2元编码如下：
（晴晴） → 0000，（晴云） → 0001，（晴阴） → 0011，
（云晴） → 0100，（云云） → 0101，（云阴） → 0111，
（阴晴） → 1100，（阴云） → 1101，（阴阴） → 1111。
离散无记忆（简单）信源的等长编码
如果限定码字的长度为 N（即每个码字都是一个 N维向量），则称此编码为 等长编码,能够选择的不同码字的个数为 DN。
如果限定码字的长度为 ≤N（即每个码字都是一个 ≤N维的向量），则称此编码为 不等长编码,能够选择的不同码字的个数为
D1+D2+…+ DN=D(DN-1)/(D-1)。
注意：在不等长编码中，并不能同时使用 D(DN-1)/(D-1)
个不同的码字。一个长度为 2的字母串究竟是两个长度为 1的码字相连，还是一个长度为 2的码字？无法识别。
在等长编码中不存在这样的识别问题 ）
离散无记忆（简单）信源的等长编码
编码速率,R=NlogD/L。
无错编码 (U1U2… UL)的不同事件用不同的码字来表示。
能够实现无错编码的充要条件是 DN≥KL。（即编码速率
R=NlogD/L≥logK）
有错编码 (U1U2… UL)的有些不同事件用相同的码字来表示。
有错编码的译码方法与,译码错误,概率 当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）。,译码错误,的概率定义为
pe= P{(U1U2… UL)=(u1u2… uL)
| (u1u2… uL)的码字在译码时并不译为 (u1u2… uL)}。
离散无记忆（简单）信源的等长编码
编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率 R0，然后选择 N和 L，使得实际的编码速率 NlogD/L不能超过编码设备的编码速率
R0,
R=NlogD/L≤R0。
当编码速率 R比较高时，可以选择比较大的 N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。 当编码速率 R比较低时，
意味着使用低成本的编码设备。此时只能选择不大的 N，
因此更需要编码的技巧。
离散无记忆（简单）信源的等长编码在无错编码的前提下，编码的最低代价
当 R≥logK时，能够实现无错编码。
当 R<H(U1)时，无论怎样编码都是有错编码。这是因为
R<H(U1)≤logK。
（如果 H(U1)=logK，则以上两种情形已经概括了全部情形。但如果 H(U1)<logK，则还有一种情形）
当 logK>R>H(U1)时，虽然无论怎样编码都是有错编码，
但可以适当地编码和译码使译码错误的概率 pe任意小。
这就是所谓,渐进无错编码,。
离散无记忆（简单）信源的等长编码
渐进无错编码 （简单地说就是：当 R>H(U1)时，可以适当地编码和译码使得译码错误的概率 pe任意小。严格地说就是：） 设给定了编码设备的编码速率 R0，
R0>H(U1)。则对任意的 ε>0，总存在一个 L0，使得对任意的 L>L0，都有对 (U1U2… UL)的等长编码和对应的译码方法，满足
①实际的编码速率 R=NlogD/L≤R0，
②译码错误的概率 pe<ε。
渐进无错编码的原理 大数定律。随着 L的增加，
(U1U2… UL)的所有事件中，某些事件所占的比例越来越小（ → 0），其发生的概率却越来越大（ → 1）。
离散无记忆（简单）信源的等长编码
不能渐进无错的编码 （简单地说就是：当 R<H(U1)时，
无论怎样编码和译码都不能使译码错误的概率 pe任意小。严格地说就是,） 设给定了编码设备的编码速率
R0,R0<H(U1)。则无论怎样编码和译码都不能同时满足
①实际的编码速率 R≤R0，
②译码错误的概率 pe任意小。
离散无记忆（简单）信源的等长编码设 … U-2U-1U0U1U2… 是离散无记忆（简单）信源的输出随机变量序列。设 U1的概率分布为取 Vl是 Ul的如下函数：当 Ul=ak时,Vl=loga(1/qk)。则
①随机变量序列 … V-2V-1V0V1V2… 相互独立，具有相同的概率分布；
②
K
K
qqq
aaaU
21
21
1 ~
)(1l o g 1
1
1 UHqqEV
K
k k
ak
离散无记忆（简单）信源的等长编码取 IL是 (V1V2… VL)的如下函数：
则
① IL最终是 (U1U2… UL)的函数；
②
③因此有切比雪夫不等式：对任意 ε>0有
P{(U1U2… UL)=(u1u2… uL)|H(U1)-ε≤IL≤H(U1)+ε}≥
L
l
lL VLI
1
1
)(1 1
1
UHEVLEI
L
l
lL
1
1
2
1
111 DV
LDVLVLDDI
L
l
l
L
l
lL
2
11
L
DV?
离散无记忆（简单）信源的等长编码取 L0使得则当 L≥L0时总有因此当 L≥L0时总有
P{(U1U2… UL)=(u1u2… uL)|H(U1)-ε≤IL≤H(U1)+ε}
≥1-ε。
2
0
1
L
DV
21LDV
离散无记忆（简单）信源的等长编码定义 1 定义
TU(L,ε)={(u1u2… uL)|H(U1)-ε≤IL≤H(U1)+ε}，
称 TU(L,ε)为 ε-典型序列集。
称 TU(L,ε)的补集为非 ε-典型序列集。
（综上所述有）
定理 1(信源划分定理 ) 对任意 ε>0，取 L0使得则当 L≥L0时总有 P{(U1U2… UL)∈ TU(L,ε)}≥1-ε。
2
0
1
L
DV
2005-7-18 18
离散无记忆（简单）信源的等长编码
（简记 H(U)=H(U1)。设以下的对数都是以 2为底的。）
特定典型序列出现的概率 若一个特定的事件
(u1u2… uL)∈ TU(L,ε)，则
2-L(H(U)+ε)≤P{(U1U2… UL)=(u1u2… uL)}≤2-L(H(U)-ε)。
证明（略）
典型序列的数量
(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)
证明（略）
离散无记忆（简单）信源的等长编码设给定一个 R0>H(U)。对每个正整数 L，对应地取整数
N=[R0L]（ R0L的下取整）。则
N/L≤R0，
limL→ +∞N/L=R0。
任取正数 ε≤(R0 -H(U))/2，存在正整数 L0，当 L>L0时
（ 1） N/L≥R0-(R0 -H(U))/2=H(U)+(R0-H(U))/2≥H(U)+ε。
（ 2） P{(U1U2… UL)∈ TU(L,ε)}≥1-ε。
离散无记忆（简单）信源的等长编码无错编码正定理给定编码设备的编码速率 R0,R0>H(U)。则对任意的
ε>0，总存在一个 L0，使得对任意的 L>L0，都有对
(U1U2… UL)的 2元等长编码方法和对应的译码方法，
①实际的编码速率 R满足
R0≥R>H(U)，
②,译码错误,的概率 pe<ε。
无错编码反定理设给定编码设备的编码速率 R0，满足 R0<H(U)。当限制实际的编码速率 R≤R0时，无论怎样编码和译码都不能使,译码错误,的概率任意小
§ 3.2 离散无记忆（简单）信源的等长编码例 设
996.0004.0~
21 aaU
l
2
1
0 0 5 7 4 7.0
9 9 6.0
1
l o g
9 6 5 7 8 4.7
0 0 4.0
1
l o g
aU
aU
V
l
l
l其中：
996.0004.0
005747.0965784.7~
lV
)(0 3 7 5 8 7 1 4 8.0 UHEV l
2 5 2 4 3 4 9 6.0
)0 3 7 5 8 7 1 4 8.0()0 0 5 7 4 7.0(996.0)9 6 5 7 8 4.7(004.0
)(
222
22
lll EVEVDV
离散无记忆（简单）信源的等长编码设给定编码设备的编码速率 R0=0.5。则
R0>0.037587148=H(U)。
希望：
① 2元编码的实际编码速率 R≤R0；
②译码错误的概率不超过 ε。其中取
ε=0.1；
ε=0.05；
ε=0.01。
离散无记忆（简单）信源的等长编码取 ε=0.1。找 L0使得即 L0=253。当 L≥253时总有
P{(U1U2… UL)=(u1u2… uL)| -0.1≤IL-H(U) ≤0.1}≥0.9。
另一方面，当事件 (u1u2… uL)中 a1的个数为 k,a2的个数为 L-k时，
2
0
1
L
DV 43496.252
3
1
0
DVL
0 05 74 7.09 60 03 7.70 05 74 7.09 65 78 4.7 LkL kLLkI L
03 18 40 14 8.096 00 37.7)( LkUHI L
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.1)；当且仅当
-0.1≤IL-H(U) ≤0.1；当且仅当；当且仅当1.00 31 8 40 1 48.09 60 0 37.71.0 Lk；当且仅当LkL 0 1 6 5 6 2 7 6.00 0 8 5 6 2 7 6.0
Lk 0 1 6 5 6 2 7 6.00
离散无记忆（简单）信源的等长编码设 L=253。此时 0.01656276L=4.19037828。
当事件 (u1u2… u253)中 a1的个数不超过 4时，
(u1u2… u253)∈ TU(253,0.1)；
否则 (u1u2… u253)不属于 TU(253,0.1)。
(u1u2… u253)∈ TU(253,0.1)的概率不小于 0.9；
(u1u2… u253)∈ TU(253,0.1)的个数为
6.2 1 92 5 33 5 5 5 5 7 4 4 4.33
3 5 5 5 5 7 4 4 4.33)1.0)((
4
0
2 5 3
22/2
22
占全部事件的比例为；UHL
k
kC
离散无记忆（简单）信源的等长编码对 L=253，对应地取整数 N=[R0L]=126。则 N/L<R0，这就是说 2
元编码的实际编码速率并未超出编码设备的编码速率。 2元编码的编码方法,将 TU(253,0.1)中的事件用不同的 126长码字表示；将 TU(253,0.1)外的事件用同一个 126长码字表示，
该码字已经用于表示了 TU(253,0.1)中的一个事件。由于
|TU(253,0.1)|≤233.355557444<2126，码字足够用。 2元编码的译码方法,将码字译为它所表示的 TU(253,0.1)中的事件
(u1u2… u253) 。于是，译码错误的概率为
P((u1u2… u253)不属于 TU(253,0.1))≤ε=0.1。
离散无记忆（简单）信源的等长编码取 ε=0.05。找 L0使得即 L0=2020。当 L≥2020时总有
P{(U1U2… UL)=(u1u2… uL)| -0.05≤IL-H(U) ≤0.05}≥0.95。
另一方面，当事件 (u1u2… uL)中 a1的个数为 k,a2的个数为 L-k时，
2
0
1
L
DV 4 7 9 6 8.2 0 1 9
3
1
0
DVL
0 05 74 7.09 60 03 7.70 05 74 7.09 65 78 4.7 LkL kLLkI L
03 18 40 14 8.096 00 37.7)( LkUHI L
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.05)；当且仅当
-0.05≤IL-H(U) ≤0.05；当且仅当；当且仅当05.003 18 40 14 8.096 00 37.705.0 Lk；当且仅当LkL 0 1 0 2 8 1 3 7.00 0 2 2 8 1 3 7.0
Lk 0 1 0 2 8 1 3 7.00
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.05)；当且仅当
-0.05≤IL-H(U) ≤0.05；当且仅当；当且仅当05.003 18 40 14 8.096 00 37.705.0 Lk；当且仅当LkL 0 1 0 2 8 1 3 7.00 0 2 2 8 1 3 7.0
Lk 0 1 0 2 8 1 3 7.00
离散无记忆（简单）信源的等长编码对 L=2020，对应地取整数 N=[R0L]=1010。则 N/L=R0，这就是说 2元编码的实际编码速率等于编码设备的编码速率。 2元编码的编码方法,将 TU(2020,0.05)中的事件用不同的 1010
长码字表示；将 TU(2020,0.05)外的事件用同一个 1010长码字表示，该码字已经用于表示了 TU(2020,0.05)中的一个事件。由于 |TU(2020,0.05)|≤2176.92603896<21010，码字足够用。 2
元编码的译码方法,将码字译为它所表示的 TU(2020,0.05)
中的事件 (u1u2… u2020) 。于是，译码错误的概率为
P((u1u2… u2020)不属于 TU(2020,0.05))≤ε=0.05。
离散无记忆（简单）信源的等长编码取 ε=0.01。找 L0使得即 L0=252435。当 L≥252435时总有
P{(U1U2… UL)=(u1u2… uL)| -0.01≤IL-H(U) ≤0.01}≥0.99。
另一方面，当事件 (u1u2… uL)中 a1的个数为 k,a2的个数为 L-k时，
2
0
1
L
DV 96.2 5 2 4 3 4
3
1
0
DVL
0 05 74 7.09 60 03 7.70 05 74 7.09 65 78 4.7 LkL kLLkI L
03 18 40 14 8.096 00 37.7)( LkUHI L
离散无记忆（简单）信源的等长编码事件 (u1u2… uL)属于典型序列集 TU(L,0.01)；当且仅当
-0.01≤IL-H(U) ≤0.01；当且仅当；当且仅当01.003 18 40 1 48.096 00 37.701.0 Lk
LkL 0 0 5 2 5 6 2 8.00 0 2 7 4 3 7 2.0
离散无记忆（简单）信源的等长编码设 L=252435。此时
0.00274372L=692.61096 ； 0.00525628L=1326.8690 。
当事件 (u1u2… u252435)中 a1的个数不超出闭区间 [693,1326]内时,(u1u2… u252435)∈ TU(252435,0.01)；
否则 (u1u2… u252435)不属于 TU(252435,0.01)。
(u1u2… u252435)∈ TU(252435,0.01)的概率不小于 0.99；
(u1u2… u252435)∈ TU(252435,0.01)的个数为
34.2 4 04 2 22 5 24 3 56 6 17.1 2 01 2
6 6 17.1 2 01 2)01.0)((
1 3 26
693
2 5 24 3 5
22/2
22
占全部事件的比例为；UHL
k
kC
