下载文档原格式
第三章 离散信源无失真编码3.2离散无记忆信源，熵为H[x]，对信源的L 长序列进行等长编码，码字是长为n 的D 进制符号串，问：（1）满足什么条件，可实现无失真编码。
（2）L 增大，编码效率 也会增大吗？ 解：（1）当log ()n D LH X ≥时，可实现无失真编码；（2）等长编码时，从总的趋势来说，增加L 可提高编码效率，且当L →∞时，1η→。
但不一定L 的每次增加都一定会使编码效率提高。
3.3变长编码定理指明，对信源进行变长编码，总可以找到一种惟一可译码，使码长n 满足D X H log )(≤n <D X H log )(+L 1,试问在n >D X H log )(+L1时，能否也找到惟一可译码？ 解：在n >D X H log )(+L1时，不能找到惟一可译码。
证明：假设在n >D X H log )(+L1时，能否也找到惟一可译码，则由变长编码定理当n 满足D X H log )(≤n <D X H log )(+L 1，总可以找到一种惟一可译码知：在n ≥DX H log )( ① 时，总可以找到一种惟一可译码。
由①式有：Ln ≥L X H )(logD ② 对于离散无记忆信源，有H(x)=LX H )( 代入式②得：n L≥ D x H log )(即在nL≥Dx H log )(时，总可以找到一种惟一可译码；而由定理给定熵H （X ）及有D 个元素的码符号集，构成惟一可译码，其平均码长满足D X H log )(≤n L <DX H log )(+1 两者矛盾，故假设不存在。
所以，在n >D X H log )(+L1时，不能找到惟一可译码。
3.7对一信源提供6种不同的编码方案：码1~码6，如表3-10所示（1） 这些码中哪些是惟一可译码？ （2） 这些码中哪些是即时码？（3） 对所有唯一可译码求出其平均码长。
解：码1： 其二次扩展码是奇异码，如u1u2和u5u1对应的码字均为010；码2： 是惟一可译码，非奇异等长码是惟一可译码，且是即时码，平均码长为3； 码3： 是延长码，是惟一可译码，但不是即时码，平均码长为n =∑=71iii n p =3.06 码4： 是非延长码，故是惟一可译码，也是即时码；平均码长n =∑=71iii n p =3.06 码5： 是数码，即非延长码，因此是即时码；平均码长n =∑=71iii n p =2.625 码6：是非延长码，故是惟一可译码，也是即时码；平均码长n =∑=71iii n p =3.125 综上所述，码2~6均为惟一可译码，码2、4、5、6是即时码。
信息论作业等长信源编码定理在信息传输过程中，绝大多数信道无法传输原始信息(比如汉字信息)，因此在传输信息时需要对信息进行编码转换，以便适合信道传输。
编码分为等长码和变长码，所谓等长码，就是对信源符号集的每个符号编码时的码字的长度是相同的。
本文主要针对等长信源编码进行相关讨论。
在对信源进行编码时，若要实现无失真的编码，这就要求信源符号与码字是一一对应的，即信源符号到码字的转换是唯一的，码字到信源符号的转换也是唯一的。
从理论上说，等长f非奇异码一定是唯一可译码，而且如果信源符号有q个，每个码元符号数为r个，则编码的码长l必须满足关系：l≥log q按照这个公式计算，英文电报有32个字符，如果采取二进制编码(码元符号为0和1)，则需要至少5位的码长，5位的码长所携带的信息量为5比特。
我们知道，当信源符号等概率分布，且信源符号之间无相关性时，信源所携带的平均信息量最大，如果32英文字符等概率出现，则携带的最大信息量正好是5比特，跟5位码长编码携带的信息量是一致的，但是，32个英文字符并不是等概率出现的，字符之间也是存在依赖性的，因此信源所携带的信息量则会远远低于5比特(实际应用中测量信息量为1.4比特)，那就意味着，如果考虑信源的实际概率分布空间和心愿符号之间的依赖性，若要携带信源的全部信息量，完全可以采用更短的码长进行编码，即对某一给定概率空间的信源，对其进行无失真等长编码时，必然存在一个码长的理论极限值。
等长信源编码定理则给出了这个理论极限值。
等长信源编码定理：一个熵为H(s)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中，选取l个码元组成，对于任意的ε>0，只要满足l≥H S+ε当N足够大时，可实现几乎无失真编码，即译码错误概率为任意小。
反之，若l N ≤H S−2εlog r则不可能实现无失真编码，而当N足够大时，译码错误概率近似于等于1 。
这个公式为最佳无失真等长编码指明了方向，即要求编码的码长最短而且保证译码的差错概率。
第三章 信源编码——离散信源无失真编码本章分析问题：在信宿要求无失真接收时，或所有信源信息无损的条件下，离散信源输出的表示——即信源编码问题。
内容：信源分类，信息速率的计算，编码定理，有效编码方法等。
一、信源及其分类 1． 离散信源和连续信源离散信源表示：…Ｕ－２Ｕ－１Ｕ０Ｕ１Ｕ２…其中ＵＬ随机变量，取值范围：Ａ＝｛ａ１，ａ２，…ａｋ｝ ２．无记忆源和有记忆源无记忆源：各ＵＬ彼此统计独立简单信源：各ＵＬ彼此统计独立且服从同一概率分布 Ｐ（ＵＬ＝ａｋ）＝Ｐｋ，ｋ＝１，２，…，Ｋ∑=Kk 1Ｐｋ＝１有记忆源：各ＵＬ取值相关。
ＵＬ＝（Ｕ１，Ｕ２，…，ＵＬ）∈ＵＬ，其概率分布由Ｌ维随机矢量表示，Ｐ（ＵＬ＝ａ）＝Ｐ（Ｕ１＝ａｋ１，…，ＵＬ＝ａｋＬ） ３．平稳信源：概率分布与起始下标无关Ｐ（Ｕ１＝ａｋ１，…，ＵＬ＝ａｋＬ）＝Ｐ（Ｕｔ＋１＝ａｋ１，…，ＵＬ＝ａｋＬ）４．各态历经源：信源输出的随机序列具有各态历经性。
５．有限记忆源：用条件概率Ｐ（ＵＬ，ＵＬ－１，ＵＬ－２，ＵＬ－ｍ）表述。
ｍ为记忆阶数。
６．马尔可夫源：有限记忆源可用有限状态马尔可夫链描述，当ｍ＝１时为简单马尔可夫链。
７．时间离散的连续源：各随机变量ＵＬ取值连续。
８．随机波形源：时间和取值上均连续的信源；由随机过程ｕ（ｔ）描述，时间或频率上有限的随机过程可展开成分量取值连续的随机矢量表示，即时间上离散，取值连续的信源。
９．混合信源二、离散无记忆源的等长编码离散无记忆源：ＤＭＳＬ长信源输出序列：ＵＬ＝（Ｕ１，Ｕ２，…，ＵＬ），Ｕｌ取值｛ａ１，ａ２，…ａｋ｝，共ＫＬ种不同序列。
对每个输出序列用Ｄ元码进行等长编码，码长为Ｎ，则可选码共有ＤＮ个。
１．单义可译码或唯一可译码：条件：ＤＮ≥ＫＬ＝Ｍ，即Ｎ≥ＬｌｏｇＫ／ｌｏｇＤＮ／Ｌ：每个信源符号所需的平均码元数；Ｎ／Ｌ→３．３２２；２．信息无损编码要求：设每个信源符号的信息量为Ｈ（Ｕ），则Ｌ长信源序列的最大熵值为ＬＨ（Ｕ），编码时由于Ｄ个码元独立等概时携带信息量最大，使码长最短。
3.1离散无记忆信源等长编码
几乎无失真等长编码
选择L 足够长，使
其中，
为与L 有关的正数，且当时有,才能不损失信息。
然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。
反之，若，编码误差变得任意大。
]
)([log L U H L D N ε+≥L ε∞→L 0→L ε])([log L U H L D N ε−<
3.2 离散无记忆（简单）信源的等长编码编码速率
R=N log D/L
R=N log D/L≥log K
关于编码速率的说明：
表示一个长度为N的D元码字给一个长度为L的消息的每个符号所提供的信息量。
一个消息序列U L 每符号含有信息量算术平均为：
信源的熵为H(U)
设I (u l )的方差为3.2 离散无记忆（简单）信源的等长编码
()/()/L L l l
I I L I u L
==∑u ()()()
()()l k k k
E I u p a I a H U ==∑2
I σ()()()()
2
2()()I
l k k k
D I u p a I a H U σ==−∑
3.2 离散无记忆（简单）信源的等长编码
例信源发出的消息序列长度L=8。
长为8的序列是(a 1+a 2)8的展开式的所有项，共28个。
消息序列的概率是(p 1+p 2)8的二项展开式中的各项。
1
2~1/43/4l a a u ⎛⎞⎜⎟
⎝⎠
()()()12~1/4
3/4l I a I a I u ⎛⎞
⎜⎟
⎝⎠()0.81H U bit
=()()()()2
2
()()0.471
I
l k k k
D I u p a I a H U σ==−=∑()()()
888111/8I a I a I a ==()()()()35
8121235/8
I a a I a I a =+
3.2.2 信源划分定理
•典型序列集的定义
•令H(U)是集的熵，，
•定义为给定信源U 输出长为L 的典型序列集
它称作弱ε典型序列集；相应地，
的补集为非典型序列集。
3.2 离散无记忆（简单）信源的等长编码
{})(,k a p U 0>ε{}
εεε+≤≤−=)()(:),(U H I U H L T L L U u ()
()/,L
L
L L I
I L U
=∈u u ),(εL T U
令u L 是信源的长为L 的输出序列，其中，是序列中出现的次数。
称为强典型序列集。
例4次掷硬币试验强典型序列有{0011}, {1001}, {1100}, {1100}, {0011}, {1010}.
ε>{}
(,):[()][()]U L k k k T L L p a L L p a εεε=−≤≤+u k L k a {},()k U p a
例信源发出的消息序列长度L=8,对其二元随机编码。
I 8的数值：
2, 1.80, 1.60, 1.41, 1.21, 1.01, 0.811, 0.61, 0.415
12~1/43/4a a U ⎛⎞
⎜⎟
⎝⎠
()0.81H U bit
=87162534435261781121212121212122
a ,a a ,a a ,a a ,a a ,a a ,a a ,a a ,a
()()20.471
I k D I a σ==
()4435261781212
12
12
2
22
a a ,a a ,a a ,a a ,a 163/0.3679.
I
L σε
=若对共个序列编码,错误概率上限是
()()()()()()()8
7
6
2
5
3
01238
8
8
8
C 1/4C 1/43/4C 1/43/4C 1/43/40.027
e P =+++=261735121212
0.2a a ,a a ,a a
ε=弱典型序列是44352617812
12
12
12
2
0.4a a ,a a ,a a ,a a ,a
ε=弱典型序列是87162531121212
a ,a a ,a a ,a a
3.2 离散无记忆（简单）信源的等长编码
3.2.3 离散无记忆信源编码定理
•可达
•对于给定的信源和编码速率R 以及任意，若
存在有，
和，使当时，就称R 是可达的，否则称此R 不可达。
例掷硬币实验R=1bit 可达；R=0.5bit 不可达。
0>ε0L ()E ()D 0L L >ε<e p
复习
无失真等长编码的充要条件
信源符号{a 1,a 2,…,a K } 码字符号{0,1,…,D-1}长l 的消息序列a i1a i2…a il 长为N 的码字n 1n 2…n N
D N ≥K L
N log D /L ≥log K
编码速率R =N log D /L R ≥log K
典型序列集
典型序列的数量
(1-ε
)2L (H (U )-ε)≤|T U (L ,
ε)|≤2
L (H (U )+ε)特定典型序列出现的概率
若一个特定的事件(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 Equipartition Property
{}
εεε+≤≤−=)()(:),(U H I U H L T L L U u
3.2 离散无记忆（简单）信源的等长编码
3.2.3 离散无记忆信源编码定理编码效率
最佳编码时，其
中，。
1
/)(≤=R U H η])(/[)(εη+=U H U H 0>ε
作业3.1 3.2。
