第五章：无失真编码1

1、第五章：无失真信源编码信源n信息论对信源研究的内容：n信源的建模：用恰当的随机过程来描述信号n关心角度：信号中携带的信息n信源输出信号中携带信息的效率的计算n熵率、冗余度n信源输出信息的有效表示n信源编码信源n信源的特性与分类n实际信源举例信源特性与分类n信源的统计特性信源的统计特性n1）什么是信源？n信源是信息的来源，实际通信中常见的信源有：语音、文字、图像、数据。在信息论中，信源是产生消息（符号）、消息（符号）序列以及连续消息的来源，数学上，信源是产生随机变量随机变量U，随机序列随机序列U和随机随机过程过程U(t,)的源。n2）信源的主要特性n信源的最基本的特性是具有统计不确定性，它可用概

2、率统计特性来描述。信源特性与分类n信源的描述与分类信源的描述与分类n单消息（符号）信源：n离散信源n连续变量信源n平稳信源n无/有记忆信源n马尔可夫信源n随机波形信源n实际信源实际信源信源特性与分类n单消息（符号）信源n它是最简单也是最基本的信源，是组成实际信源的基本单元。它可以用信源取值随机变量的范围U和对应概率分布P(u)共同组成的二元序对U,P(u)来表示。n当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。所以，概率空间能表征这离散信源的统计特性，因此有时也把这个概率空间称为信源空间。 单消息（符号）信源离散信源n这些信源可能输出的消息数是有限的或

3、可数的，而且每次只输出其中一个消息。因此，可以用一个离散型随机变量X来描述这个信源输出的消息。这个随机变量X的样本空间就是符号集A；而X的概率分布就是各消息出现的先验概率，信源的概率空间必定是一个完备集。n在实际情况中，存在着很多这样的信源。例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的。我们可用一维离散型随机变量离散型随机变量X来描述这些信源的输出。它的数学模型就是离散型的概率空间：单消息（符号）信源离散信源n对离散信源例：对于二进制数据、数字信源：U=0,1，则有 21,211 ,0,1, 021

4、p101110pppuuPU当ninipppuUuUuUPU11单消息（符号）信源连续变量信源n有的信源虽输出是单个符号(代码)的消息，但其可能出现的消息数是不可数的无限值，即输出消息的符号集A的取值是连续的，或取值是实数集(-，)。例如，语音信号、热噪声信号某时间的连续取值数据，遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值是连续的，但又是随机的。我们可用一维的连续型随机变量连续型随机变量X来描述这些消息。这种信源称为连续信源，其数学模型是连续型的概率空间： 单消息（符号）信源连续变量信源 upbaPU,其中： 的概率密度为连续变量 u, 01upRUu对于连续变量信源平稳信源

5、n很多实际信源输出的消息往往是由一系列符号序列所组成的。可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量，即为随机矢量。这时，信源的输出可用N维随机矢量随机矢量X=(X，XXN)来描述，其中N可为有限正整数或可数的无限值。这N维随机矢量X有时也称为随机序列。n一般来说，信源输出的随机序列的统计特性比较复杂，分析起来也比较困难。为了便于分析，我们假设信源输出的是平稳的随机序列，也就是序列的统计性质与时间的推移无关。很多实际信源也满足这个假设。n若信源输出的随机序列X=(，)中，每个随机变量 Xi (i=1,2,，N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的

6、或可数的。而且随机矢量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻随机矢量X的各维概率分布都相同。这样的信源称为离散平稳信源。如中文自然语言文字，离散化平面灰度图像都是这种离散型平稳信源。无记忆信源n在某些简单的离散平稳信源情况下，信源先后发出的一个个符号彼此是统计独立的。也就是说信源输出的随机矢量X=(XXX）中，各随机变量Xi (i=1,2,N)之间是无依赖的、统计独立的，则N维随机矢量的联合概率分布满足P(X)=P（）P（）P（）n我们称由信源空间X，P(x)描述的信源X为离散无记忆信源。这信源在不同时刻发出的符号之间是无依赖的，彼此统计独立的。离散无记忆信源X的N次扩展信

7、源n我们把这信源X所输出的随机矢量X所描述的信源称为离散无记忆信源X的N次扩展信源。可见，N次扩展信源是由离散无记忆信源输出N长的随机序列构成的信源。n离散无记忆信源的N次扩展信源的数学模型是X信源空间的N重空间。有记忆信源n 一般情况下，信源在不同时刻发出的符号之间是相互依赖的。也就是信源输出的平稳随机序列X中，各随机变量Xi之间是有依赖的。例如，在汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。其他如英文，德文等自然语言都是如此。这种信源称为有记忆

8、信源。n我们需在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。马尔可夫信源n表述有记忆信源要比表述无记忆信源困难得多。实际上信源发出的符号往往只与前若干个符号的依赖关系强，而与更前面的符号依赖关系弱。为此，可以限制随机序列的记忆长度。n当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。时齐马尔可夫信源n设马尔可夫信源各时刻随机变量的取值为xk，xkXk，k=1,2,，i-1,i,i+1,N，则描述随机序列中各随机变量之间依赖关系的条件概率为P(xi|xi+2xi+1xi-1xi-2xi-3xi-mx1

9、）=（xi|xi-1xi-2x-3xi-m） （i=1,2,N）n如果上述条件概率与时间起点i无关，即信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可信源。离散序列信源总结时齐马氏链信源平稳序列信源离散有记忆信源平稳无记忆一般无记忆离散无记忆信源离散序列信源随机波形信源n更一般地说，实际信源输出的消息常常是时间和取值都是连续的。例如，语音信号X(t)、热噪声信号n(t)、电视图像信号X(x0,y0,t)等时间连续函数。同时，在某一固定时间t，它们的可能取值又是连续的和随机的。对于这种信源输出的消息，可用随机过程随机过程来描述。称这类信源为随机波形信源。n分析一般随机波形信源比较

10、复杂和困难。常见的随机波形信源输出的消息是时间上或频率上为有限的随机过程。根据取样定理，只要是时间上或频率上受限的随机过程，都可以把随机过程用一系列时间(或频率)域上离散的取样值来表示，而每个取样值都是连续型随机变量。这样，就可把随机过程转换成时间(或频率)上离散的随机序列来处理。甚至在某种条件下可以转换成随机变量间统计独立的随机序列。如果随机过程是平稳的随机过程，时间离散化后可转换成平稳的随机序列。这样，随机波形信源可以转换成连续平稳信源来处理。若再对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换成有限的或可数的离散值。也就可把连续信源转换成离散信源来处理。 实际信源n实际信源

11、在离散情况下是消息序列信源，在连续情况下是随机过程信源，它们分别代表数字与模拟信源。离散序列信源其中，i=1,2,n为每个消息（符号）取值的种类数l=1,2,L为消息（符号）序列的长度应注意的是i和l是代表两个不同范畴的变量，表示不同的概念，切勿混淆。LliLiliiUUUUUUUUU2121简记i=1,2,nl=1,2,L离散序列信源信源输出是一组随机序列（矢量）：其样值为：对应概率为：由于每个随机变量U=1,2,n有n种取值，则 有 种可能取值。维取值范围LUUUUULLl1LlLuuuu1LlLuuupup1LnLU离散序列信源n例：最简单L=3的三位PCM信源：这时L=3, n=2,

12、即i=0,1，则有：818181812131120303,111,010,001,000,111,001,000)(10时当ppppppUUUupU连续信源n在实际的连续信源中，可以采用两种方法进行分析n一类是将连续信源离散化随机序列信源n另一类是仍然采用随机过程来分析n什么样的信源可以进行离散化处理？n实际上，只要满足一个非常宽松的条件，即满足限时(T)、限频(F)的连续消息信源，即满足物理可实现条件下，均可离散化为随机序列。实际信源举例实际信源举例n1）图像信源图像信源一般可以引用一个五元的随机场来表示： （简化）主要统计特性：初步可以认为是一个近似的平稳遍历过程),(),(txUtzyx

13、U扫描时实际信源举例实际信源举例n对于数字型图像信号，可以采用马氏链模型 而 为相邻像素之间的相关系数。111112122NNxX实际信源举例实际信源举例n2）语音信源 可以近似用一个一维随机过程U(, t)表示。严格的讲，它是一个非平稳过程，但是对于短时段(5-50ms)可认为是平稳的，且某些是随机噪声（清辅音）而某些时段则呈现周期性特征（浊音），还有一些短时段是二者的混合。熵率n对于离散平稳信源，考察其输出信息量例：p44例2。6XP（x） 0 1 211/36 4/9 1/4ajai01201/41/18011/181/31/18201/187/36ajai01209/111/8012/

14、113/42/9201/87/9P(ai,aj)P(ai/aj)当信源符号间无依赖性时：542. 1)(log)()()()(3121iiiapapXHXHXH当考虑信源符号间的依赖性时：870. 0)|(log),()|(313112ijjijiaapaapXXH条件熵：联合熵：41. 2),(log),()(313121jijijiaapaapXXH可见：)|()()(12121XXHXHXXH且：)|()(12XXHXH考察信源符号间有依赖性时联合信源的平均符号熵：2 . 1)()(21212XXHXH可见：)()(2XHXH比特/符号比特/符号比特/二个符号比特/符号分析：)()(2X

15、HXH)|()(12XXHXH结论：符号间的相关性使得信源的平均符号熵减少，即 每个符号平均携带的信息量减少。问题：H2(X)和H(X2|X1)哪一个值更能接近实际二维平稳 信源的熵？即：用哪一个值来表示二维平稳信源 每个符号平均携带的信息量比特/符号考察：离散平稳有记忆信源符号之间的依赖长度为N的信源XP（x） a1 a2 an p1 p2 pn定义：N长的信源符号序列的平均符号熵平均符号熵即平均每个信源符号 所携带的信息量为)()(211NNNXXXHXH比特/符号当 时，存在以下性质：条件熵 随N的增加是非递增的平均符号熵 随N的增加是非递增的N给定时，平均符号熵=条件熵。即： 存在，且

16、：)(1XH)|(121NNXXXXH)(211NNXXXH)|()(121NNNXXXXHXH)(limXHHNN)|(lim)(lim121NNNNNXXXXHXHH结论：对于有限记忆长度的平稳信源可用有限记忆长度的条件熵来对平稳 信源进行信息测度。熵率n对于离散平稳信源，考察其输出信息量n假设字母序列长度为N，则有限长度的序列可看成随机矢量（ ）的熵，可用联合熵表示，平均每个字母的熵 可以表示为 当 时，若 存在，则：n定义： 为该平稳信源的熵率，又称平稳信源的极限熵或极限信息量n对于一般的平稳信源，可以证明，极限 一定存在。Nuuu,.,21).()(211NNNUUUHUH)(UHN

17、N)(limUHHNN)(UH)(UH 冗余度冗余度1n它表征信源信息率的多余程度，是描述信源客观统计特性的一个物理量。 由广义Shannon不等式有：n可见对于有记忆信源，最小单个消息熵应为 ，即从理论上看，对有记忆信源只需传送 即可。n但是这必需要掌握信源全部概率统计特性。这显然是不现实的。实际上，往往只能掌握有限的维，这时需传送 ，那么与理论值 相比，就多传送了 。0)()/(lim.)/()()(log111210UHUUHUUHUHUHnLLL)(UH)(UH)(UHL)()(UHUHL)(UH冗余度冗余度2n 为了定量描述信源有效性，可定义： 信源效率： 信源冗余度：（相对剩余）n

18、或者定义： 冗余度logK 相对冗余度1 /logKLHH/LLLHHHHHR/11)(UH)(UH冗余度3n正由于信源存在着冗余度，即存在着不必要传送的信息，因此信源也就存在进一步压缩信息率的可能性。冗余度越大，压缩潜力也就越大。可见它是信源编码，数据压缩的前提与理论基础。 字母 字母 字母 空格ETOANIR0.20.1050.0720.06540.0630.0590.0550.054SHDLCF.UMP0.05020.0470.0350.0290.0230.0225 0.0210.0175Y.WGBVKXJ.QZ0.0120.0110.01050.0080.0030.0020.0010.001冗余度冗余度4（举例：计算英文文字信源的冗余度）首先给出英文字母（含空格）出现概率如下：iPiPiP冗余度冗余度5（举例：计算英文文字信源的冗余度）n首先求得独立等概