信息论与编码ch5 信源编码

1、第第2 2章：信源熵章：信源熵第第3 3章：信道容量章：信道容量第第4 4章：信息率失真函数章：信息率失真函数第第5 5章：信源编码章：信源编码第第6 6章：信道编码章：信道编码第第7 7章：密码体制的安全性测度章：密码体制的安全性测度2022-4-2812022-4-282编码n信息传输需要解决的两个问题：n在不失真或允许一定失真的条件下，如何用尽可能少的信息率来传送信源信息？n在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大？n有效性和可靠性n提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；n反之，要提高信息传输率常常又会使抗干扰能力减弱。 20

2、22-4-283编码n信源编码：以提高通信系统的有效性为目的的编码n信源符号之间存在分布不均匀和相关性，使得信源存在冗余度。n主要任务：减少冗余，提高编码效率。即用较少的码率传送较多的信息，使单位时间内传送的平均信息量增加，从而提高通信的有效性。n针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。n解除相关性：解除相关性：使序列中的各个符号尽可能地互相独立n概率均匀化：概率均匀化：使编码中各个符号出现的概率尽可能地相等2022-4-284n编码的分类n信道编码：以提高信息传输的可靠性提高信息传输的可靠性为目的的编码n通常通过增加信源的冗余度来实现。n采用的一

3、般方法是增大码率/带宽。n密码：以提高通信系统的安全性提高通信系统的安全性为目的的编码n通常通过加密和解密来实现。n从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。无失真信源编码信源编码限失真信源编码编码信道编码加密编码编码2022-4-285编码n无失真编码定理n可逆编码的基础。当信源符号转换成代码后，可从代码无失真地恢复原符号。n适用于离散信源离散信源/数字信号编码。n限失真编码定理n对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为取值可以有无限多个。此时只能根据限失真编码定理进行限失真编码。n适用于连续信源连续信源/模拟信号编码。5.1 5.1 离散信

4、源编码离散信源编码 5.2 5.2 连续信源编码连续信源编码 5.3 5.3 相关信源编码相关信源编码 5.4 5.4 变换编码变换编码2022-4-2865.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件2022-4-2872022-4-288术语n码字：n码长：n码元：n码：n编码：12,ina aaa12,jmb bbb12lLX XXX1 2LjKYYYY如何分离码字？如果0，01都是码字，译码时如何分离？1001110？如果一个码的任何一个码字都不是其它码字的前缀，则称该码为前缀码、异前置码、异字码、逗点码，也称为即时码2022-4-2892022-4-2810码树n码树用

5、来表示各码字的构成。A01000000000000111111111110120000011111222222022-4-2811码树n中间节点不安排码字，只在终端节点安排码字n每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成n当第i阶的节点作为终端节点，且分配码字，则码字的码长为in按树图法构成的码一定满足即时码的定义n树码的各个分支都延伸到最后一级端点，则称为满树，否则为非满树 n满树码是定长码，非满树码是变长码1110110100 0111011010 110010 10100 125. 0125. 025. 05 . 04321DCBAaaaa码码码码码码码码

6、概率概率消息消息判断以下码字是否可分离？异前置码即时码可分离有延时可分离分离不可分离不可例2.4.12022-4-2812mXLHKmXLHlog)(log)(1 对离散无记忆信源，消息长度为L，符号熵为H(X),对信源进行m元变长编码，一定存在无失真的信源编码方法，满足：满足：其码字平均长度其码字平均长度满足：满足：其码字平均信息率其码字平均信息率R R)()(XHRXH2022-4-2813克劳夫特不等式克劳夫特不等式1 1充要条件：充要条件：的异前置码的的异前置码的) ), , ,2 2, ,1 1( (元长度为元长度为1 1- - n ni ik ki ii im mn ni ik k

7、m m2022-4-28145.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件5.1.2 5.1.2 香农编码香农编码2022-4-28155.1.2 5.1.2 香农编码niinnapapapapaaa121211)(,)(.)()(.设有离散无记忆信源设有离散无记忆信源2022-4-2816)(log1)(log22iiiapkap的码字位作为点后的用二进制表示，用小数把iijaakap)(1234香农编码方法的步骤香农编码方法的步骤按信源符号的概率从大到小的顺序排队)(.)()(21napapap不妨设不妨设njiijapapja，个码字的累加概率表示第，用令,2, 11),(

8、0)(011)()(jiijaapap2022-4-2817例例05. 015. 01 . 025. 025. 02 . 0)(654321aaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制香农码。试对该信源编二进制香农码。2022-4-2818a2a3a1a5a4a600.250.50.70.850.950.250.250.20.150.10.050001100101110111110223345pa(aj)ki码字编码过程：编码过程：p(ai)0.000000.010000.100000.101000.110100.11110(pa(aj)22022-

9、4-2819617.2)(iiikapKKmLKR2log符号）（比特/42. 2)(XH%63.89)X(RHL=1, m=2,单符号2进制码编码效率2022-4-28205.1.3 5.1.3 费诺编码费诺编码5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件2022-4-28215.1.3 5.1.3 费诺编码费诺编码对概率按m进行分组，使每组概率和尽可能相等给每个分组分配一个码元对每个分组重复2、3步，直到不可分为止1234按信源符号的概率从大到小的顺序排队)(.)()(21napapap不妨设2022-4-282204. 008. 016. 018. 022. 032. 0

10、)(654321aaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制费诺码。试对该信源编二进制费诺码。例例2022-4-28231a2a3a4a5a6a32. 022. 018. 016. 008. 004. 00000000011011011101111编码过程编码过程2022-4-2824)/(35. 2)(符号比特XHmLKR2log%92.97)(RXH 6 61 1) )符号符号/ /比特比特( (4545. .2 2) )( (i ii ii ik ka ap pK K 可以看出本例中费诺码有较高的编码效率。可以看出本例中费诺码有较高的编码效率。

11、费诺码比较适合于每次分组概率都很接近的信源。费诺码比较适合于每次分组概率都很接近的信源。2022-4-2825000001a2a3a4a5a6a2022-4-28265.1.4 5.1.4 赫夫曼编码赫夫曼编码5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件2022-4-2827将信源符号按概率由大到小顺序排队。给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队。给缩减信源中概率最小的符号各分配一个码位。重复步骤2、3直至概率和为1。21435.1.4 5.1.4 赫夫曼编码赫夫曼编码2022-4-282804. 005. 006.

12、 007. 01 . 01 . 018. 04 . 0)(87654321aaaaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制赫夫曼码。试对该信源编二进制赫夫曼码。例例2022-4-282909. 013. 019. 023. 037. 06 . 0000000004. 005. 006. 007. 01 . 01 . 018. 04 . 01a2a3a4a5a6a7x8a00101100000100010100010000110001000007a编码过程编码过程2022-4-2830()2.55(/)H Xbit sym2.61K( )97.7%H

13、xR2022-4-2831。率提高了可见，哈夫曼编码的效则编码效率若采用定长编码，码长7 .1285355. 2, 3K2022-4-2832！-Huffman码的编码方法不是唯一的。码的编码方法不是唯一的。-每次分配每次分配“0”和和“1”码元是任意的，所以可得码元是任意的，所以可得到不同的码字。但码长，平均码长都不变，所以到不同的码字。但码长，平均码长都不变，所以没有本质区别。没有本质区别。-若合并后的新符号的概率与其他符号的概率相等，若合并后的新符号的概率与其他符号的概率相等，从编码的方法上来说，这几个符号的次序可任意从编码的方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但

14、得到的码字不同。排列，编出的码都是正确的，但得到的码字不同。不同的编法得到的码字长度也不尽相同。不同的编法得到的码字长度也不尽相同。2022-4-2833例例 设有离散无记忆信源设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用两种不同的方法对其编二进制用两种不同的方法对其编二进制huffmanhuffman码码2022-4-2834方法一方法一方法二方法二2022-4-2835信源符号信源符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.41 1002a20.2012102a30.20003112a40

15、.1001040103a50.1001140113两种不同的编码方法得到的码字和码长的对比两种不同的编码方法得到的码字和码长的对比2022-4-2836平均码长和编码效率平均码长和编码效率2022-4-2837 对信源进行缩减时，两个概率最小的符号合对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将此时将影响码字的长度，一般将合并的概率放

16、合并的概率放在上面在上面，这样可获得，这样可获得较小的码方差较小的码方差。2022-4-2838两种编码方法编出的码字的码长方差比较两种编码方法编出的码字的码长方差比较2022-4-2839可以看出第二种编码方法的码长方差要小可以看出第二种编码方法的码长方差要小许多。这意味着第二种编码方法的码长变许多。这意味着第二种编码方法的码长变化较小，比较接近平均码长。由此可以得化较小，比较接近平均码长。由此可以得到一个结论到一个结论( (怎样得到码方差较小的怎样得到码方差较小的HuffmanHuffman编码编码) )。2022-4-2840结论：结论：进行赫夫曼编码时，为得到进行赫夫曼编码时，为得到码

17、方差码方差最小的最小的码，应使合并的信源符号位于缩减信源序码，应使合并的信源符号位于缩减信源序列列尽可能高的位置尽可能高的位置上，以减少再次合并的上，以减少再次合并的次数，充分利用短码。次数，充分利用短码。 2022-4-28415.1.3 5.1.3 费诺编码费诺编码5.1.5 5.1.5 游程编码游程编码5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件2022-4-2842游程序列游程5.1.5 游程编码游程编码 前面的几种编码方法主要时针对无记忆信源，对有前面的几种编码方法主要时针对无记忆信源，对有记忆信源，这些编码方法的效率并不高，特别是对二记忆信源，这些编码方法的效率并不

18、高，特别是对二元相关信源，需要一些其它的方法。游程编码就是这元相关信源，需要一些其它的方法。游程编码就是这样的方法，对相关信源的编码更有效。样的方法，对相关信源的编码更有效。 指数字序列中连续出现相同符号的一段。在指数字序列中连续出现相同符号的一段。在二元信源中，连续的一段二元信源中，连续的一段00称为一个称为一个00游程，游程，00的个数称为此游程的长度，同样，也有的个数称为此游程的长度，同样，也有11游程。游程。 用交替出现的用交替出现的00游程、游程、11游程的游程的长度，来表示任意二元序列而产生的一个新序列。它长度，来表示任意二元序列而产生的一个新序列。它和二元序列是一个一一对应的变换

19、。和二元序列是一个一一对应的变换。2022-4-2843二元序列：二元序列：000101110010001游程序列：游程序列：31132131二元序列二元序列赫夫赫夫曼编码曼编码2022-4-2844多元序列也存在相应的游程序列多元序列也存在相应的游程序列 多元序列变换成游程序列再进行压缩编多元序列变换成游程序列再进行压缩编码没有多大意义码没有多大意义 需要增加标志位来区分码元需要增加标志位来区分码元游游程编码只适用于二元序列，对于多元信源，游游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码一般不能直接利用游程编码 2022-4-284500010111001000131132

20、131因为游程变换是一一对应的可逆变换，所以游程变换后，熵不变。游程编码哈夫曼编码组合编码可获得较高的编码效率：2022-4-2846 0：长度为1的“0”游程0000：长度为4的“0”游程 111：长度为3的“1”游程 长度为n的“1”游程11:1n2022-4-2847“0”、“1”的概率分别为的概率分别为p0、p1长度长度i的的“0”游程概率：游程概率： 01001 iilp lpp长度长度j的的“1”游程概率：游程概率： 11110 jljp lpp00110 11iilpp lp11011 11jjlpp lp0p2022-4-2848000000123012010101100112

21、3,()0( )1,( )1iiiliillllliLP Lpp pp pppp lp l11111112311210101100111123,()0()1,()1jjjljjllllljLP Lpp pp pppp lp l2022-4-2849010.6,0.4pp例例“0”游程长度信源游程长度信源二元序列：00010111001000011110011000101110001234()0.40.240.1440.0864LP L2022-4-2850010203040.40.240.1440.0864llll0001111000100112022-4-2851“1”游程长度信源游程长度信

22、源111234()0.60.240.0960.0384LP L111213140.40.240.0960.0384llll0101011011100112022-4-2852000101110010000111100110001011100,100,11000,0101111100001000100110,1111111010011100000111110010010011101信号序列码序列2022-4-28535.1 5.1 离散信源编码离散信源编码 5.2 5.2 连续信源编码连续信源编码 5.3 5.3 相关信源编码相关信源编码 5.4 5.4 变换编码变换编码2022-4-2854n

23、 对于连续信源输出的消息，首先要在时间上进行采样，然后在取值上进行量化并进而编码。 n 连续信源编码属于限失真编码，根据保真度准则下的信源编码定理，其编码效率受限于信息率失真函数 。 )(DRn 在符合采样定理的条件下，采样所带来的信息失真可以忽略不计。 n 量化是用值域上有限个称为量化值中的一个来代替信号值，量化必然带来误差；如果量化后采用无失真编码，那么连续信源编码中的信息失真就都来自量化过程。 5.2 连续信源编码连续信源编码2022-4-2855p 量化有多种方法：量化有多种方法： 标量量化标量量化：将各个采样时刻的信号值逐个进行量化； 矢量量化矢量量化：将多个采样时刻的信号值组成一组

24、，将其看作一个多维矢量，将这些矢量逐个进行量化。 p标量量化均匀量化非均匀量化p矢量量化2022-4-2856脉冲编码调制（PCM，pulse code modulation）是研究最早、使用最广的一种最佳标量量化编码。 PCMPCM的编码原理：的编码原理：采样采样量化、编码量化、编码x(iTs) x(t) C(iTs) 标量量化标量量化2022-4-2857p 均匀量化在整个量化范围内的量化间隔（步长）都是相等的，均匀量化也称为线性量化。x1x2x3x4xq1xq2xq3xq42022-4-2858p 非均匀量化非均匀量化 只要在量化范围内的量化间隔不完全相等，就将其称为非均匀量化；非均匀量

25、化也叫做非线性量化。 矢量量化是在图像、语音信号编码中研究得较多的量化编码方法，它的出现不仅仅是作为量化，更多的是作为压缩编码而提出的。 在矢量量化中，将 L个采样时刻的信号值组成一组，将其看作一个L 维矢量，以这些 L维矢量为单位逐个进行量化编码。 矢量量化矢量量化2022-4-28595.1 5.1 离散信源编码离散信源编码 5.2 5.2 连续信源编码连续信源编码 5.3 5.3 相关信源编码相关信源编码 5.4 5.4 变换编码变换编码2022-4-28605.3 相关信源编码 n数据压缩三大经典技术数据压缩三大经典技术n统计编码统计编码n预测编码预测编码n变换编码变换编码2022-4

26、-2861n预测编码预测编码是数据压缩理论的一个重要分支。根据信号之间存在一定是数据压缩理论的一个重要分支。根据信号之间存在一定相关相关性性的特点，利用前面的的特点，利用前面的一个一个或或多个信号多个信号对下一个信号进行预测，然后对对下一个信号进行预测，然后对实际值和预测值的差（实际值和预测值的差（预测误差预测误差）进行编码。）进行编码。n第第n n个符号个符号X Xn n的熵满足：的熵满足：nn n越大考虑更多元素之间的依赖关系时，熵值进一步降低，得到的熵越接越大考虑更多元素之间的依赖关系时，熵值进一步降低，得到的熵越接近于实际信源所含的实际熵（极限熵）。近于实际信源所含的实际熵（极限熵）。

27、n所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低。数码率就可以降低。).|(.)|()|()(121211xxxxHxxxHxxHxHnnnnnnnnn).|(lim)(lim121xxxxHxHnnnnnnn5.3.1 预 测 编 码 2022-4-2862 预测器对样本的预测，通常是利用样值的线性或非线性函数关系预测现时的系统输出。 要实现最佳预测就是要找到计算预测值的预测函数。 由于非线性的复杂性，大部分预测器均采用线性预测函数。2022-4-2863 一、 预测编码的基本原理n利用以往的样本值

28、对新样本值进行预测，将新样本值的实际值与利用以往的样本值对新样本值进行预测，将新样本值的实际值与其预测值相减，得到其预测值相减，得到误差值误差值，对该误差值进行编码，传送此编码，对该误差值进行编码，传送此编码即可。即可。n理论上数据源可以准确地用一个数学模型表示，使其输出数据总理论上数据源可以准确地用一个数学模型表示，使其输出数据总是与模型的输出一致，因此可以准确地预测数据，但是实际上预是与模型的输出一致，因此可以准确地预测数据，但是实际上预测器不可能找到如此完美的数学模型测器不可能找到如此完美的数学模型；n预测预测本身不本身不会会造成失真。造成失真。误差值误差值的編的編码码可以可以采采用用无

29、无失真失真压压縮法或縮法或失真失真压压縮法。縮法。2022-4-2864图 预测编码原理图 编码器编码输出预测器ui信源输出iiiuueiu 2022-4-2865二、二、 预测方法预测方法 预测就是从已收到的符号来提取关于未收到的符号信息，从而预测其最可能的值作为预测值；并对它与实际值之差进行编码，达到进一步压缩码率的目的。由此可见，预测编码是利用信源的相关性来压缩码率的；对于独立信源，预测就没有可能，因而预测编码也就无用了。 预测的理论基础主要是估计理论预测的理论基础主要是估计理论。估计就是用实验数据组成一个统计量，作为某一物理量的估值或预测值。 2022-4-28661.线性预测 若样值

30、和预测值之间呈线性关系,这种预测称为线性预测,否则称为非线性预测。常用的几种线性预测方案有：（1）前值预测，即 （2）一维预测，即用ur的前面已知的k个已知样值预测ur的值，即（3）二维预测，也称为非线性预测，即预测值与样值之间为非线性关系。1rruau1kijijjua u2022-4-2867KN表示x1, x2, xN 的时序在xk 之前。线性预测是指预测方程式的右方是各个xi的线性函数： 如果ai i (k)是常数，则为时不变线性预测为时不变线性预测。最简单的预测方程：最简单的预测方程：11)(kiiikxkaxNkkxxxxfxNk),.,(3211kkxx预测方程式预测方程式: 2

31、.最优预测2022-4-2868 2.最优预测使误差函数达到最小值的预测方程式叫做最佳线性预测。求最佳线性预测的各个参数ai，列方程组： 2 2 ) )( (m mi in nm mi in nk kk kx xx xE Em ms se e)1,.,2,1(,0)(2niaxxEikk代入得到联立方程组，解方程定出ai。11kiiikxax2022-4-2869三、预测编码的基本类型 预测编码，特别是线性预测编码已在信息与通信系统的信息处理中被广泛地采用，主要由预测阶数和权值决定，其中最常用的三种:p增量调制（增量调制（DM， Differential Modulation）p差分脉冲编码调

32、制差分脉冲编码调制（DPCM, Differential Pulse Code Modulation)p自自适应差分脉冲编码调制适应差分脉冲编码调制（ADPCM， Adaptive DPCM）2022-4-2870增量调制n最简单的有损预测编码方法是增量调制最简单的有损预测编码方法是增量调制(DM(DM或或M) M) 方法，早期在数字方法，早期在数字电话中采用，是一种最简单的差值脉冲编码电话中采用，是一种最简单的差值脉冲编码 。n其预测器和量化器分别定义为其预测器和量化器分别定义为 其中其中a a是预测系数是预测系数( (一般小于等于一般小于等于1)1)，c c是是1 1个正的常数。个正的常数

33、。n因为量化器的输出可用因为量化器的输出可用单个位符表示单个位符表示( (输出只有输出只有2 2个值个值) )，所以编码器，所以编码器中的符号编码器可以只用长度固定为中的符号编码器可以只用长度固定为1 1比特的码。由比特的码。由DMDM方法得到的码方法得到的码率是率是1 1比特像素。比特像素。2022-4-2871示例：示例： 取a1和c5。设输入序列为12，16，12，14，20、32，46，52，50，51，50。编码开始时先将第1个输入像素直接传给编码器。2022-4-2872图 DPCM型原理图 解码器信道编码器yiiu 预测器iy 量化器uiei预测器iu iu xi差分脉冲编码调制

34、（DPCM） 在ADPCM中所用的量化间隔的大小还可按差值信号的统计结果自动适配，达到最佳量化，从而使因量化造成的失真亦最小 它的核心想法是：它的核心想法是：利用自适应的思 想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶 去编码大的差值,使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预 测值之间的差值总是最小。2022-4-2873 5.4 变 换 编 码 信源序列往往具有很强的相关性，要提高信源的效率首先要解除信源的相关性。解除相关性可以在时域上进行解除相关性可以在时域上进行( (如：预测编码如：预测编码) )，也可以在，也可以在频域，甚

35、至在广义频域内进行频域，甚至在广义频域内进行。域变换编码：2022-4-2874 对连续的模拟信号，如果它是周期性的,则可采用傅氏级数展开，若是非周期性的,则可采用傅氏积分(变换)来表示，但无论是级数还是积分,都属于一类正交变换，是从时域展开成频域的变换。同理,对离散的数据序列信号也可引入同样的离散傅氏变换。而且，还可以进一步将其推广为广义的频域变换。 2022-4-2875一、 变换编码的基本原理 设信源输出为一个一维消息U(u1，u2，un)，经变换后输出为X(x1，x2，xn)，故有：由正交性 A T AA 1 AI，则有： UA 1XA T X 式中： A实正交变换矩阵； A T 矩阵P的转置矩阵； A 1矩阵P的逆矩阵； I单位矩阵。 2022-4-2876n 如何选择正交矩阵 A? 使M值较小，且使被丢弃的nM个取值足够地小，以至于既能得到最大的信源压缩率，同时又使丢弃掉nM个取值以后，所产生的误差不超过允许的失真范围。 因此，正交变换的主要问题可归结为在一定的误差准则下，寻找最佳或