第五章 信源编码

1、第第2 2章：信源熵章：信源熵 第第3 3章：信道容量章：信道容量 第第4 4章：信息率失真函数章：信息率失真函数 第第5 5章：信源编码章：信源编码 第第6 6章：信道编码章：信道编码 第第7 7章：密码体制的安全性测度章：密码体制的安全性测度 信源编码信源编码 信源编码是以提高通信的有效性为目的编码。信源编码是以提高通信的有效性为目的编码。 通常通过压缩信源的冗余度来实现。通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平均比采用的一般方法是压缩每个信源符号的平均比 特数或信源的码率。同样多的信息用较少的码特数或信源的码率。同样多的信息用较少的码 率来传送，使单位时间内

2、传送的平均信息量增率来传送，使单位时间内传送的平均信息量增 加，从而提高通信的有效性。加，从而提高通信的有效性。 信源编码的基本途径有两个：信源编码的基本途径有两个： 使序列中的各个符号尽可能地互相使序列中的各个符号尽可能地互相 独立，即解除相关性；独立，即解除相关性； 使编码中各个符号出现的概率尽可使编码中各个符号出现的概率尽可 能地相等，即概率均匀化。能地相等，即概率均匀化。 信源编码的基础是信息论中的两个编码定理：信源编码的基础是信息论中的两个编码定理： 无失真编码定理无失真编码定理 限失真编码定理限失真编码定理 无失真编码无失真编码只适用于离散信源只适用于离散信源 对于连续信源，只能在

3、失真受限制的情况下进对于连续信源，只能在失真受限制的情况下进 行行限失真编码限失真编码 下面介绍几种典型的离散信源编码方法。下面介绍几种典型的离散信源编码方法。 5.1 5.1 离散信源编码离散信源编码 5.2 5.2 连续信源编码连续信源编码 5.3 5.3 相关信源编码相关信源编码 5.4 5.4 变换编码变换编码 5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件 如何分离码字？ 充要条件。 是异前置码的满足克劳夫特不等式1 1 n i ki m 如果0，01都是码字，译码时如何分离？ 1001110 ？ ？ 1110 110 10 0 0111 011 01 0 11 00

4、1 0 10 1 0 0 125. 0 125. 0 25. 0 5 . 0 4 3 2 1 DCBA a a a a 码码码码概率消息 判断以下码字是否可分离？ 异前置码 即时码 可分离 有延时 可分离 分离 不可 分离 不可 例 2.4.1 m XLH K m XLH log )( log )( 1 对离散无记忆信源，消息长度为L，符 号熵为H(X),对信源进行m元变长编码，一 定存在无失真的信源编码方法， 满足：满足：其码字平均长度其码字平均长度 满足：满足：其码字平均信息率其码字平均信息率R R )()(XHRXH 5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件 5.1.

5、2 5.1.2 香农编码香农编码 5.1.2 香农编码香农编码 n i i n n xp xpxpxp xxx 121 21 1)(, )(.)()( . 设有离散无记忆信源设有离散无记忆信源 )(log1)(log 22iii xpkxp 的码字位作为点后的 用二进制表示，用小数把 i ja xk xp)( 1 2 3 4 香农编码方法的步骤香农编码方法的步骤 按信源符号的概率从大到小的顺序排队 )(.)()( 21n xpxpxp不妨设不妨设 个码字的累加概率表示第 ，用令 i ijxpxp ja 1),(0)( 0 1 1 1)()( j i ija xpxp 例例 05. 01 . 0

6、15. 02 . 025. 025. 0)( 65432 1xxxxxx XP X 设有一单符号离散无记忆信源设有一单符号离散无记忆信源 试对该信源编二进制香农码。试对该信源编二进制香农码。 11110595. 005. 0 1101485. 01 . 0 10137 . 015. 0 10035 . 02 . 0 01225. 025. 0 002025. 0 )( 6 5 4 3 2 1 x x x x x x kxp ija 码字 编码过程编码过程 1 0 )()( j i ija xpxp （1） 6 1 7 .2)( i ii kxpK Km L K R 2 log 42. 2)(X

7、H %63.89 )( R xH 5.1.3 5.1.3 费诺编码费诺编码 5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件 5.1.3 5.1.3 费诺编码费诺编码 对概率按m进行分组，使每组概率尽 可能相等 给每个分组分配一个码元 对每个分组重复2、3步，直到不可分 为止 1 2 3 4 按信源符号的概率从大到小的顺序排队 )(.)()( 21n xpxpxp不妨设不妨设 04. 008. 016. 018. 022. 032. 0)( 65432 1xxxxxx XP X 设有一单符号离散无记忆信源设有一单符号离散无记忆信源 试对该信源编二进制费诺码。试对该信源编二进制费诺码

8、。 例例 1 x 2 x 3 x 4 x 5 x 6 x 32. 0 22. 0 18. 0 16. 0 08. 0 04. 0 0 0 1 0 1 0 0 1 1 00 01 10 110 1110 1111 1 编码过程编码过程 )/(35. 2)(symbitXH m L K R 2 log %92.97 )( R xH 6 1 )/(4 .2)( i ii kxpK符号比特 可以看出本例中费诺码有较高的编码效率。可以看出本例中费诺码有较高的编码效率。 费诺码比较适合于每次分组概率都很接近的信源。费诺码比较适合于每次分组概率都很接近的信源。 0 0 0 0 0 1 1 1 1 1 1 x

9、 2 x 3 x 4 x 5 x 6 x 5.1.4 5.1.4 赫夫曼编码赫夫曼编码 5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件 将信源符号按概率由大到小顺序排队 给两个概率最小的符号各分配一个码位， 将其概率相加后合并作为一个新的符号， 与剩下的符号一起，再重新排队 给缩减信源中概率最小的符号各分配 一个码元 重复步骤2、3直至概率和为1 2 1 4 3 5.1.4 5.1.4 赫夫曼编码赫夫曼编码 04. 005. 006. 007. 01 . 01 . 018. 04 . 0)( 8765432 1xxxxxxxx XP X 设有一单符号离散无记忆信源设有一单符号离散

10、无记忆信源 试对该信源编二进制哈夫曼码。试对该信源编二进制哈夫曼码。 例例 09. 0 13. 0 19. 0 23. 0 37. 0 6 . 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 04. 0 05. 0 06. 0 07. 0 1 . 0 1 . 0 18. 0 4 . 0 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 1 001 011 0000 0100 0101 00010 00011 0 00010 0 1 0 0 7 x 编码过程编码过程 ()2.55(/)H Xbit sym 2.61K ( ) 97.7% H x R 。率提高了可见，哈夫

11、曼编码的效 则编码效率若采用定长编码，码长 7 .12 85 3 55. 2 , 3 K 说明：说明： Huffman码的编码方法不是唯一的。首先，每码的编码方法不是唯一的。首先，每 次对缩减信源两个最小的符号分配次对缩减信源两个最小的符号分配“0”和和“1”码码 元试任意的，所以可得到不同的码字。只要在元试任意的，所以可得到不同的码字。只要在 各次缩减信源中保持码元分配的一致性，即能各次缩减信源中保持码元分配的一致性，即能 得到可分离码字。不同的码元分配，得到的具体得到可分离码字。不同的码元分配，得到的具体 码字不同，但码长，平均码长都不变，所以没有码字不同，但码长，平均码长都不变，所以没有

12、 本质区别。其次，若合并后的新符号的概率与其本质区别。其次，若合并后的新符号的概率与其 他符号的概率相等，从编码的方法上来说，这几他符号的概率相等，从编码的方法上来说，这几 个符号的次序可任意排列，编出的码都是正确的，个符号的次序可任意排列，编出的码都是正确的， 但得到的码字不同。不同的编法得到的码字长度但得到的码字不同。不同的编法得到的码字长度 也不尽相同。也不尽相同。 对信源进行缩减时，两个概率最小的符号合对信源进行缩减时，两个概率最小的符号合 并后的概率与其它信源符号的概率相同时，这并后的概率与其它信源符号的概率相同时，这 两者在缩减信源中进行概率排序，其位置放置两者在缩减信源中进行概率

13、排序，其位置放置 次序是可以任意的，故会得到不同的哈夫曼码。次序是可以任意的，故会得到不同的哈夫曼码。 此时将影响码字的长度，一般将此时将影响码字的长度，一般将合并的概率放合并的概率放 在上面在上面，这样可获得，这样可获得较小的码方差较小的码方差。 如下面的例子如下面的例子 例例 设有离散无记忆信源设有离散无记忆信源 1 . 01 . 02 . 02 . 04 . 0)( 54321 xxxxx XP X 用两种不同的方法对其编二进制用两种不同的方法对其编二进制huffmanhuffman码码 方法一方法一 方法二方法二 信源符号信源符号 xi 概率概率p(xi)码字码字Wi1码长码长Ki1码

14、字码字Wi2码长码长Ki2 x10.411002 x20.2012102 x30.20003112 x40.1001040103 x50.1001140113 两种不同的编码方法得到的码字和码长的对比两种不同的编码方法得到的码字和码长的对比 平均码长和编码效率平均码长和编码效率 两种编码方法编出的码字的码长方差比较两种编码方法编出的码字的码长方差比较 可以看出第二种编码方法的码长方差要小可以看出第二种编码方法的码长方差要小 许多。这意味着第二种编码方法的码长变许多。这意味着第二种编码方法的码长变 化较小，比较接近平均码长。由此可以得化较小，比较接近平均码长。由此可以得 到一个结论到一个结论(

15、(怎样得到码方差较小的怎样得到码方差较小的huffmanhuffman 编码编码) )。 结论：结论： 进行赫夫曼编码时，为得到进行赫夫曼编码时，为得到码方差码方差最小的最小的 码，应使合并的信源符号位于缩减信源序码，应使合并的信源符号位于缩减信源序 列列尽可能高的位置尽可能高的位置上，以减少再次合并的上，以减少再次合并的 次数，充分利用短码。次数，充分利用短码。 5.1.3 5.1.3 费诺编码费诺编码 5.1.5 5.1.5 游程编码游程编码 5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件 5.1.5 游程编码游程编码 前面的几种编码方法主要时针对无记忆信源，对有前面的几种编

16、码方法主要时针对无记忆信源，对有 记忆信源，这些编码方法的效率并不高，特别是对二记忆信源，这些编码方法的效率并不高，特别是对二 元相关信源，需要一些其它的方法。游程编码就是这元相关信源，需要一些其它的方法。游程编码就是这 样的方法，对相关信源的编码更有效。样的方法，对相关信源的编码更有效。 游程：游程：指数字序列中连续出现相同符号的一段。在指数字序列中连续出现相同符号的一段。在 二元信源中，连续的一段二元信源中，连续的一段00称为一个称为一个00游程，游程， 00的个数称为此游程的长度，同样，也有的个数称为此游程的长度，同样，也有11 游程。游程。 游程序列：游程序列：用交替出现的用交替出现的

17、00游程、游程、11游程的游程的 长度，来表示任意二元序列而产生的一个新序列。它长度，来表示任意二元序列而产生的一个新序列。它 和二元序列是一个一一对应的变换。和二元序列是一个一一对应的变换。 000101110010001 31132131 二元序列二元序列 赫夫赫夫 曼编码曼编码 多元序列也存在相应的游程序列多元序列也存在相应的游程序列 多元序列变换成游程序列再进行压缩编多元序列变换成游程序列再进行压缩编 码没有多大意义码没有多大意义 游游程编码只适用于二元序列，对于多游游程编码只适用于二元序列，对于多 元信源，一般不能直接利用游程编码元信源，一般不能直接利用游程编码 因为游程变换是一一对

18、应的可逆 变换，所以游程变换后，熵不变。 组合编码可获得较高的编码效率： 游程编码赫夫曼编码 5.1.3 5.1.3 费诺编码费诺编码 5.1.6 5.1.6 冗余位编码冗余位编码 5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件 冗余位冗余位 信源序列中不携带信息的符号。 多元信源序列： , 211121 yxxyyxxx mmm 111000,000111,100,111 , 211121mmm xxxxx 上面二元上面二元1表示信息位，表示信息位，0表示冗余位表示冗余位 冗余位序列游程编码 信息序列赫夫曼编码 分帧传送冗余位序列的编码 方法。N个符号为一帧，编成一个L-D码

19、字，每个码字含有两个数：Q和T。 ： 本帧内。 ：信息位的 。 L-D编码编码 Q j j j n T 1 1 TQ : j nj 第个信息位的位置序号。 T Q、 K1KnQ Q K TT 1 L 1Q n 1 nQ、T 1 例例 001000000010000，N=15,编L-D码。 编码。 2Q3 1 n11 2 n 编码位数： Q N NAlog) 1log( Q的位数的位数 T的位数的位数 1 T=47。 4 Q A7 T A、计算出 00100101111 译码。 , 2QT=47,11 2 n3 1 n ：冗余位和信息位数目相差较 大的情况。 2 5.1 5.1 离散信源编码离散

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

21、是将各个采样时刻的信号值逐个进 行量化，称为标量量化；另一种是将个采样时刻的信号值 组成一组，将其看作一个维矢量，将这些维矢量逐个进行 量化，称为矢量量化。 脉冲编码调制（PCM，pulse code modulation）是研 究最早、使用最广的一种最佳标量量化编码。 PCMPCM的编码原理：的编码原理： 采样采样量化、编码量化、编码 x(iTs) x(t) C(iTs) 5.2.1 最佳标量量化最佳标量量化 模拟信号 经过采样，成为时间离散的信号序 列 ；将各个采样时刻的信号值逐个量化、 编码，得到与取值也是离散的信号量化值序 列 相对应的二进制编码序 列 。 )(tx , 2 , 1),

22、(iiTx s , 2 , 1),(iiTx sq , 2 , 1),(iiTC s 由于每个采样时刻的量化、编码过程相同，为方便，我们 可去掉时标。将量化、编码的输入信号值记为 ，量化、 编码中的信号量化值记为 ，量化、编码的编码输出记 为 。 x q x C 一、均匀量化一、均匀量化 均匀量化是指在整个量化范围内的量化间隔都是相等的， 均匀量化也称为线性量化，均匀量化的特性： 其中，(a)为中平量化，(b)为中升量化，主要以有无零量 化值来加以区别。 x1x2x3x4 xq1 xq2 xq3 xq4 x1x2x3x4 xq1 xq2 xq3 xq4 (a)(b) 以中平量化为例讨论均匀量化

23、，引入四舍五入原则的中平 量化特性 ： x1x2x3x4 xq1 xq2 xq3 xq4 由于均匀量化正反两个方向的对称性，可以将其分为极性 判断和信号绝对值量化两个步骤。 由于归一化信号绝对值满足 ，如果信号绝对值的量 化数目为 ，取 ， ，则量化间隔 ，相 应 。 1x 1 M 1 M x M 1 0 0 x Miiixxi, 2 , 1, 0 当信号绝对值 及 时，将其量化为 ；当信号绝对值 时， 将其量化为 。 1, 2 , 1, 2 1 2 1 Mixxx ii MM xxx 2 1 Mixqi, 2 , 1, 2 1 x 0 0 q x 量化后，最常用的编码是定长折叠二进制码，其码

24、元安排 为：最高位为极性码，用以表示信号极性，当信号值 时，极性码取1； 时，极性码取0。次高位以下为量 化码，用以表示 的量化值 。 0 x 0 x x Mixqi, 2 , 1 , 0, 当 的量化间隔为 时，码长 。x 1 1 log 2 k 在编码电路或编码程序中，一般编码过程是： (1)对信号值进行极性判断，确定极性码； (2)通过信号绝对值与量化码各位权值组合的逐次比较， 确定量化码； (3)将极性码和量化码组合起来，得到均匀量化编码。 【例5.2.1】已知某一采样时刻的归一化信号值 ，设量化 间隔 ，求其均匀量化编码。 16 3 .10 x 8 1 确定码长： ； 41318lo

25、g1 1 log 22 k 确定极性码：由于信号值 ，所以极性码 ； 0 x 1 3 C 确定量化码：确定量化码：信号绝对值与量化码最高位权值比较，由 于 ，所以 ；与量化码最高位和次 高位权值之和比较，由于 ，所 以 ；与量化码最高位和最低位权值之和比较，由 于 ，所以 ； 16 7 16 1 8 4 28 4 16 3 .10 x 1 2 C 16 11 16 1 8 2 8 4 28 2 8 4 16 3 .10 x 0 1 C 16 9 16 1 8 1 8 4 28 1 8 4 16 3 .10 x 1 0 C 101 012 CCC故量化码 ； 将其组合，归一化信号值 的均匀量化编

26、码为 16 3 .10 x 1101 0123 CCCC 量化值与信号值之间由于四舍五入而产生的量化误差一般 也称为量化噪声。 量化噪声与信号值一样，也是随机变量，记为 Mixxe qi , 2 , 1 , 0, 例如，例6.2.1的量化噪声 。 16 3 . 0 16 3 .10 16 10 6 xxe q 均匀量化的量化噪声 。 2 1 e 如果我们采用平方误差失真函数 ，则量化 噪声直接反映了信息失真的程度；根据限失真编码的要求 就可以决定均匀量化的量化噪声水平。 2 )(),( qiqi xxxxd 二、非均匀量化二、非均匀量化 只要在量化范围内的量化间隔不完全相等，就将其称为非 均匀

27、量化；非均匀量化也叫做非线性量化。 采用压扩技术的非线性量化原理： 均匀量化、编码均匀量化、编码 x 信道信道译码译码 f(x)C 在发送端，信号值首先通过一个电路或程序进行压缩，然 后再进行均匀量化、编码；而在接收端，译码后也需通过 一个电路或程序进行扩张；只要压缩和扩张特性相互补偿， 压扩过程就不会引入新的信息失真。 以语音信号为例，了解非线性量化的主要概念和方法。 目前，在语音信号的非线性量化编码中，采用了两种压缩 特性：一种称为 律特性，另一种称为 律特性。 A 欧洲和中国大陆等地的数字电话通信中采用的 律特性：A 1 1 ln1 ln1 1 0 ln1 )( x AA xA A x

28、A xA xf A 式中：x为归一化信号值，当 时函数取正，否则取 负，一般取 。 0 x 6 .87A 为实现方便，大多采用13折线来逼近 律特性。 A 量化范围的13折线 律特性：10 A 1 f(x) 7/8 6/8 5/8 4/8 3/8 2/8 1/8 0 11/21/41/8 x 划分为8个不均匀的段落：其中第8段占 量化范围 的 ，除第1段外，其余各段的宽度均按倍率 减小，即 第7段占 ，第6段占 ，第2段占 ；第1段也 占 。 x 10 2 1 2 1 4 1 8 1 128 1128 1 每个段落再均匀地分为16份，每一份作为一个量化间隔。 这样， 量化范围内共划分出了 个不

29、均匀的量 化间隔；如果将最小的量化间隔记为 ， 则 ，相应最大的量化间隔 为 。 10128168 2048 1 16128 1 32 1 162 1 64 13折线 律非均匀量化编码也采用定长折叠二进制码，并 将码长确定为8位；其8位码元安排如下：最高位 为极性 码，用以表示信号极性，其准则与均匀量化相同；以下三位 为段落码，用以表示 落在正方向的第几个段落；最 后四位 为段内码，用以表示 在段内落在第几个量 化间隔。 A 7 C 456 CCC x 0123 CCCC x 在编码电路或编码程序中，13折线 律非均匀量化编码过 程是： (1)对信号值进行极性判断，确定极性码 ； (2)通过段

30、落码起始量化值的中位搜索，确定段落码 ； (3)信号绝对值与所确定段落起始量化值之差通过与段内码 各位权值组合的逐次比较，确定段内码 ； (4)组合起来即得到13折线 律非线性量化编码。 A 7 C 456 CCC 0123 CCCC A 由于每个段落的宽度不同，每个段落内段内码各位的权值 也不同。 【例5.2.2】已知某一采样时刻的归一化信号值 求其13折线 律非均匀量化编码。 286x A 确定极性码 ，由于信号值 ， ； 7 C0 x0 7 C 确定段落码 ：取第1段与第8段的中位第5段进行比 较，由于 ，所以 ；取第5段与第8段 的中位第7段进行比较，由于 ，所 以 ；取第7段与第5段

31、的中位第6段进行比较，由 于 ，所以 ；故段落码 即落在第6段； 456 CCC 128286x1 6 C 512286x 0 5 C 256286x1 4 C101 456 CCC 确定段内码 ：第6段的起始量化值为 ， 量化间隔为 ； 0123 CCCC256 16 将其组合，归一化信号值 的13折线 律非线性量 化编码为 。 与段内码最高位权值比较，由 于 ，所以 ；与 段内码次高位权值比较，由 于 ，所以 ；与 段内码第三位权值比较，由 于 ，所以 ；与 段内码第三位和最低位权值之和比较，由 于 ，所以 ； 故段内码 ； 120812830256286256x 0 3 C 568643

32、0256286256x0 2 C 2483230256286256x1 1 C 408163230256286256x 0 0 C0010 0123 CCCC 286xA 01010010 01234567 CCCCCCCC 由于每个段落的量化间隔不同，13折线 律非线性量化的 量化噪声随着信号值落在不同段落而不同。 A 例如，例6.2.2的量化码所代表的量化值为 ，相 应的量化噪声 。 288 2, 6 q x 256 1 8 1024 1 2286288 2, 6 xxe q 显然，信号绝对值越小，13折线 律非线性量化的量化噪 声也越小，当信号绝对值落在第1段或第2段 时， 。 A 40

33、96 1 2 1 e 虽然当信号绝对值落在其他段落时，量化噪声会大于 ； 但由于语音信号小信号出现的概率远大于大信号出现的概 率，所以13折线 律非线性量化的量化噪声功率与码长为 12的均匀量化的量化噪声功率相差并不太大。 4096 1 A 换句话说，对于语音信号而言，码长为8的13折线 律非 线性量化编码与码长为12的均匀量化编码的量化噪声水 平基本相当，而编码效率却提高了 。 A %50 矢量量化是在图像、语音信号编码中研究得较多的量化编 码方法，它的出现不仅仅是作为量化，更多的是作为压缩 编码而提出的。 在矢量量化中，将 个采样时刻的信号值组成一组，将其 看作一个 维矢量，以这些 维矢量

34、为单位逐个进行量 化编码。 L L L 5.2.2 矢量量化矢量量化 以 为例讨论矢量量化。 2L 对于时间离散的信号序列 ，如果将每2 个采样时刻的信号值构成一个2维矢量，就形成 个2维 矢量 ； niiTx s , 2 , 1),( 2 n 2 , 2 , 1),( 21 n iaaX iii )( s Tx)2( s Tx 1 X 2 X 6 X )12( s Tx 由于每个2维矢量的矢量量化过程相同，为方便，我们也 去掉时标，将2维矢量记为 。 X 所有可能的2维矢量构成一个平面，矢量量化最重要的工 作是将这个平面划分为 块（相当于标量量化中的量化 数目），记为 ；这些块可以是均匀的，

35、 也可以是非均匀的（相当于标量量化中均匀或非均匀的的 量化间隔）；一般将这些块称为胞腔（Cell）。 N NiSi, 2 , 1, 平面的划分： 1 S 2 S 3 S 4 S 5 S 6 S 1 a 2 a 然后对于所划分的每一块给定一个量化矢量（相当于标量 量化中的量化值），记为 ；通常将其取 为所划分块的形心。 NiX qi , 2 , 1, 在矢量量化中，一般将每个量化矢量 称 为码字或码矢，将所有 个量化矢量构成的集合 称为码书；因此，矢量量化中 这项最重要的工作称为码书的建立。 NiX qi , 2 , 1, N , 21qNqq XXX 码书建立之后，矢量量化过程就成了在给定码书

36、中搜索一 个与信号矢量最接近的码字的过程。 矢量量化原理： 码书码书 搜索搜索 Xi信道信道i 码书码书 检索检索qi X 在发送端，信号矢量 与码书中的每一个码字 通过计算误差失真函数进行比较，搜索到失真最小的码字 及其相应的序号（该码字在码书中的地址） ；在接收端， 由于设置了一个与发送端相同的码书，故只需根据序号就 可检索到与 最接近的码字 。 X NiX qi , 2 , 1, i X qi X 当码书长度为 时，传输码字序号所需的比特数为 ；由于矢量维数为 ，相当于每个信号值所对应 的比特数仅为 ，可见其压缩比可以很高。 N N 2 log L N L 2 log 1 要做到最佳矢量

37、量化，怎样建立一个合理的码书？当码书 较大时，如何快速有效地搜索到与信号矢量最接近的码字？ 这是矢量量化的两个关键问题。 一、一、LBGLBG算法算法 利用训练序列建立码书的LBG算法的流程是： (1)给定码书长度 ，置 、初始平均失真 ， 给定初始码书 ，给定计算停止门 限 ； N0n )1(n D , )()( 2 )( 1 n qN n q n q XXX ) 1 , 0( (2)用码书 为已知形心，利用信号序列构成 的 维训练序列 ，根据最佳划分原 则 ， 划分 出 个胞腔； , )()( 2 )( 1 n qN n q n q XXX L m XXX 21 ),(),( )( jiX

38、XdXXdXS qirqjrr n j Njimr, 2 , 1,;, 2 , 1 N (3)计算平均失真 和相对失 真 ，如 ，则停止计算，当前码书 就是设计好的码书；否则，进行第(4)步； m r qir i n XXd m D 1 )( ),(min 1 )( )()1( )( n nn n D DD D )( n D (4)计算各胞腔的形心 ， ，置 ， 返回第(2)步。 )( )( )1( 1 n i SX n i n qi X S X Ni, 2 , 11 nn 该流程还有两个问题，第一是初始码书的选取，第二是空 胞腔的处理。 初始码书的选取常用的方法是随机选取法和分裂法 ；处 理

39、空胞腔常用的方法是去空胞腔分裂法。 二、全搜索算法和树搜索算法二、全搜索算法和树搜索算法 常用时间复杂度和空间复杂度来衡量矢量量化的特点：时 间复杂度是指每量化一个信号矢量所需的计算量，它主要 取决于搜索过程中乘法运算的次数；空间复杂度是指码书 所需的存储容量。 全搜索算法的特点是信号矢量与码书中的码字逐一进行比 较，根据采用的误差失真函数找到失真最小的码字作为其 量化矢量，采用全搜索算法的矢量量化也称为基本矢量量 化。 对于基本矢量量化而言，如其矢量维数为 ，码书长度 为 ，采用平方误差失真函 数 ，那么时间复杂度 （次/信号矢量），空间复杂度 （单元）。 L N NiaaXXd L j j

40、qijqi , 2 , 1,)(),( 1 2 LNb LNu 采用树搜索算法的矢量量化称为树搜索矢量量化，在树搜 索矢量量化的发送端，需要建立树型码书以方便进行树搜 索；而在接收端，由于只需根据序号检索，可以仍然是数 组型码书。 以以3层二叉树为例，其搜索步骤：层二叉树为例，其搜索步骤： (1)信号矢量 分别与第二层的中间节点 通过计算误 差失真函数进行比较，如 ，则走上子树， 送0至信道；否则走下子树，送1至信道； X 10,qq XX ),(),( 10qq XXdXXd (2)如走的是上子树，信号矢量 分别与第三层的中间节 点 通过计算误差失真函数进行比较， 如 ，则走上上子树，送0至

41、信道；否则 走上下子树，送1至信道，结束搜索；如走的是下子树， 信号矢量 分别与第三层的中间节点 通过计算误 差失真函数进行比较，如 ，则走下上 子树，送0至信道；否则走下下子树，送1至信道，结束搜 索。 X 0100,qq XX ),(),( 0100qq XXdXXd X 1110,qq XX ),(),( 1110qq XXdXXd 在信道中传输的是树型码书中树叶的序号，因此，在接收 端，其数组型码书只需包含树叶就可根据序号检索。 对于二叉树矢量量化而言，如其矢量维数为 ，码书树叶 数为 ，则树的层数 ，采用平方误差失真函 数，那么时间复杂度 （次/信号矢量），空 间复杂度 （单元）。

42、L 1 N 12 log1Nm )log2( 12 NLb )2( 1 1 m j j Lu 与基本矢量量化相比，二叉树矢量量化的特点就是以空间 复杂度的提高来换取时间复杂度的降低。 5.1 5.1 离散信源编码离散信源编码 5.2 5.2 连续信源编码连续信源编码 5.3 5.3 相关信源编码相关信源编码 5.4 5.4 变换编码变换编码 对于有记忆信源，采样后的信号序列存在时间相关性，仍 然对各个采样时刻的信号值逐个进行量化，会造成码长的 冗余。 为提高编码效率，对于时间相关的信号序列，通常用两类 方法进行编码：第一类方法是利用信号序列的时间相关性， 通过预测以减少信息冗余后再进行编码，这

43、类方法称为预 测编码；另一类方法则是引入某种变换，将信号序列变换 为另一个域上彼此独立或者相关程度较低的序列，同时将 能量集中在部分样值上，再对这个新序列进行编码，这类 方法称为变换编码。 5.3 相关信源编码相关信源编码 现在讨论预测编码。 为方便，将第 个时刻的信号值 记为 ，相应第 个时刻的信号值记为 。 n )( s nTx n x , 2, 1nn , 21nn xx 对于时间相关的信号序列，由于 与 相关， 故只要知道 ，就可对 进行预测。 n x, 21nn xx , 21nn xx n x 设预测值为 ，则 ， 称为预测误差。 n x nnn dxx n d 5.3.1 预测编

44、码预测编码 通过预测，我们将 所携带的信息量分成了两部分：一部 分为 所携带的信息量，它实际上是 所携带 的信息量；另一部分是 所携带的信息量，它才是 所携 带信息量的新增加部分。只要预测足够准确， 就足够小。 n x n x , 21nn xx n d n x n d 因此，如果是对 进行量化、编码而不是对 进行量化、 编码，就会减少信息冗余，从而提高编码效率。 n d n x 由于预测编码是对 进行量化、编码，接收端译码后也只 能得到 ；接收端必须重建 ，而 ，因此接 收端也同样需要进行预测。 n d n d n x nnn dxx 线性预测是最常用的预测方法，其表达为 ， 式中 ，称为预

45、测阶数， 为加权系数。 p i inin xwx 1 1 np piwi, 2 , 1, 预测阶数应该取多大，加权系数又应该怎样选取，才能在 性能和简单上得到合理的折中？为此，人们提出了许多方 案，最常用的是增量调制（或DM，Differential Modulation）、差分脉冲编码调制（DPCM，Differential Pulse Code Modulation）和自适应差分脉冲编码调制 （ADPCM，Adaptive Differential Pulse Code Modulation），这类方案通常也称为差值编码。 一一、增量调制增量调制 增量调制是预测编码中最简单的一种，增量调制

46、原理如下， 其中(a)为发送端，(b)为接收端。 1比特量化比特量化 + n x n x qn d - n i iqn d 1 编码编码 n c n d + + + qn d n x n i in x 1 n x n c 译码译码 (a)(b) 5.3.2 差值编码差值编码 在发送端，将信号值 与量化预测值 之差 进行1比特 量化，所谓1比特量化，就是只对差值的符号而不是大小 进行量化，即当 时， ，否则， 。 n x n d 0 n d qn d qn d n x 同时，在 的基础上加减一个量化增量 ，以形成下一个 采样时刻的量化预测值，备下一个采样时刻求差值之用。 n x 编码则当 时，

47、； 时， ；其码长 为1。 qn d1 n c qn d0 n c 在接收端，通过译码将 还原为量化增量 后，将量化 增量 与量化预测值 相加即可得到量化值 。 n c qn d qn d n x n x 同时，在 的基础上加上一个量化值 ，以形成下一个 采样时刻的量化预测值，备下一个采样时刻相加之用。 n x n x 【例例5.3.1】已知某归一化信号序 列 ，设初始量化 ，量 化增量 ，求其增量调制编码和量化值。 2 . 0 ,23. 0 ,15. 0 ,05. 0, 4321 xxxx0 0 q d 125. 0 0 01 q dx0005. 0 111 xxd125. 0 1 q d

48、1 1 c125. 00125. 0 111 xdx q 125. 0125. 00 11102 qqq dxddx 0125. 015. 0 222 xxd125. 0 2 q d 1 2 c25. 0125. 0125. 0 222 xdx q 25. 0125. 0125. 0 222103 qqqq dxdddx 025. 023. 0 333 xxd125. 0 3 q d 0 3 c125. 025. 0125. 0 333 xdx q 125. 0125. 025. 0 3332104 qqqqq dxddddx 0125. 02 . 0 444 xxd125. 0 4 q d

49、1 4 c25. 0125. 0125. 0 444 xdx q 的编码 ； M1 , 0 , 1 , 1, 4321 cccc 的量化值 。 M25. 0 ,125. 0 ,25. 0 ,125. 0, 4321 xxxx 在增量调制中，量化噪声分为一般量化噪声和过载量化噪 声；一般量化噪声 ， 即1比特量化的量化噪声，其幅度不会超过量化增量 。 nqnnnnqnnnn ddxdxdxxe) () ( 过载量化噪声则是由信号斜率过大而产生的；因为在增量 调制中，每个采样间隔只允许一个量化增量的变化，所以 当信号斜率比这个固定斜率大时，就会产生过载量化噪声。 过载量化噪声： xx , t 由于

50、 的最大斜率是 ，因此，为了避免产生过载量化 噪声，最大信号斜率必须满足 。 x s T s Tdt dx max 对于正弦信号 ，避免产生过载量化噪声的条 件是 ，即 ；通常取 ， 所以为了避免产生过载量化噪声，增量调制的采样频率要 远远大于奈奎斯特采样定理的要求。 tAtxsin)( s s f T A dt dx max A f s A 二、差分脉冲编码调制二、差分脉冲编码调制 差分脉冲编码调制原理如下，其中(a)为发送端，(b)为接 收端。 + + + qn d n x n i in x 1 n x n c 译码译码 (a)(b) 量化量化 + n x n d n x qn d + +

51、 - 编码编码 n c 寄存寄存 在发送端，将信号值 与量化预测值 之差 进行量化； 量化可以采用均匀量化，也可以采用非均匀量化；由于差 值 的动态范围一般比较小，通常用均匀量化且量化码的 长度取3就可以了，因此量化间隔 。 n x n x n d n d 8 1 编码 一般也与均匀量化相同，在量化码基础上增加一位 极性码，故码长为4。 n c 同时，在 的基础上加减一个量化值 ，以形成下一个 采样时刻的量化预测值，备下一个采样时刻求差值之用。 n x qn d 在接收端， 通过译码将还原为量化值 后，将量化值 与量化预测值 相加即可得到量化信号值 。 n c qn d n x n x 同时，

52、在 的基础上加上一个量化信号值 ，以形成下一 个采样时刻的量化预测值，备下一个采样时刻相加之用。 n x n x 【例例5.3.2】已知某归一化信号序 列 ，设初始值 ， ， 采用码长为4的均匀量化，量化间隔 ，求其差 分脉冲编码调制的编码和量化信号值。 2 . 0 ,23. 0 ,15. 0 ,05. 0, 4321 xxxx0 0 q d0 0 x 03125. 0 000 001 xdx q 05. 0005. 0 111 xxd 21 )1010(0625. 0 q d 1010 1 c0625. 000625. 0 111 xdx q 0625. 000625. 0 112 xdx

53、q 0875. 00625. 015. 0 222 xxd 22 )1011(0938. 0 q d 1011 2 c1563. 00625. 00938. 0 222 xdx q 1563. 00625. 00938. 0 223 xdx q 0737. 01563. 023. 0 333 xxd 23 )1010(0625. 0 q d 1010 3 c2188. 01563. 00625. 0 333 xdx q 2188. 01563. 00625. 0 334 xdx q 0188. 02188. 02 . 0 444 xxd 24 )0001(0313. 0 q d 0001 4

54、c1875. 02188. 00313. 0 444 xdx q DPCM的编码 ； 0001,1010,1011,1010, 4321 cccc DPCM的量化信号值 。 1875. 0 ,2188. 0 ,1563. 0 ,0625. 0, 4321 xxxx 在差分脉冲编码调制中，量化噪 声 ，即均匀量化的量化 噪声，其幅度不会超过量化间隔的一半 。 nqnnnnqnnnn ddxdxdxxe) () ( 2 5.1 5.1 离散信源编码离散信源编码 5.2 5.2 连续信源编码连续信源编码 5.3 5.3 相关信源编码相关信源编码 5.4 5.4 变换编码变换编码 5.4 变换编码变换

55、编码 所谓变换编码变换编码，就是引入某种变换，通常是正交变换，将 时间相关的信号序列变换为另一个域上彼此独立或者相关 程度较低的序列，同时将能量集中在部分样值上，再对这 个新序列进行编码，给能量较大的分量分配较多的比特， 给能量较小的分量分配较少的比特，从而提高编码整体效 率的方法。 变换编码的关键关键是找到一种合适的变换，使时间相关的信 号序列成为变换域上彼此独立或者相关程度较低的序列， 同时将能量集中在部分样值上。 满足这样条件的变换有傅立叶变换傅立叶变换、余弦变换余弦变换、哈达玛变哈达玛变 换换、 变换、小波变换小波变换等。 LK 5.4.1 子带编码子带编码 子带编码首先将信号分割成若

56、干个不同的频带分量（一般 称其为子带信号），然后再分别对子带信号进行时间采样 和量化编码；可见，子带编码既与频域有关，也与时域有 关，是一种基于时频分析的变换编码。 子带编码原理如下，其中(a)(a)为发送端，(b)(b)为接收端。 量化编码量化编码1带通滤波带通滤波 1 量化编码量化编码2带通滤波带通滤波 2 量化编码量化编码 M 带通滤波带通滤波 M 信号信号 编码编码 合合 成成 频率搬移频率搬移 1 频率搬移频率搬移 2 频率搬移频率搬移 M 采样采样1 采样采样2 采样采样M (a) 带通滤波 1 译码译码1 带通滤波 2 译码译码2 带通滤波 M 译码译码M 编码编码 重建信号 分

57、分 路路 D/A变换变换 1 D/A变换变换 2 D/A变换变换 M 频率搬移 1 频率搬移 2 频率搬移 M (b) 在发送端，用一组带通滤波将信号分割成若干个不同的频 带分量，将这些子带信号通过频率搬移为基带，再对其分 别采样，采样频率应满足奈奎斯特定理；如果将各子带带 宽记为 ， ，则采样频率可 取 ， 。 i WMi, 2 , 1 isi Wf2Mi, 2 , 1 采样后的各信号序列分别进行量化编码形成子带码，将其 合并成一个总码通过信道传送到接收端。 在接收端，将总码分路为子带码，分别通过译码重建信号 序列，经 变换重建基带，再通过将频率搬移重建子带 信号，经带通滤波，最后得到重建信号。 AD/ 在子带编码中，如果各子带的带宽 ， 相同， 称为等带宽子带编码，否则，称为变带宽子带编码。 i WMi, 2 , 1 以语音信号为例，信号的分割通常采用二叉树结构：首先 根据整个音频信号的带宽将信号分割成两个相等带宽的子 带高频子带和低频子带，然后将这两个子带或其中一 个子带用同样的方法分割成4个或3个子带，这个过程可按 需要