香农编码
-
2023年3月17日发(作者：hdcopy)第五章信源编码（第十讲）
（2课时）
主要内容：（1）编码的定义（2）无失真信源编码
重点：定长编码定理、变长编码定理、最佳变长编码。
难点：定长编码定理、哈夫曼编码方法。
作业：5。2，5。4，5。6；
说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另
外，注意，解题方法。多加一些内容丰富知识和理解。
通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将
信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两
个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信
息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率
最大。为了解决这两个问题，就要引入信源编码和信道编码。
一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价
的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息
论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决
上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重
大的理论指导意义。
§3.1编码的定义
编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。
讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图3.1是
一个信源编码器，它的输入是信源符号
},,,{
21q
sssS
，同时存在另一符号
},,,{
21r
xxxX，一般来说，元素小姐xj是适合信道传输的，称为码符号（或者码元）。
编码器的功能就是将信源符号集中的符号s
i
（或者长为N的信源符号序列）变换成由
x
j
(j=1,2,3,…r)组成的长度为l
i
的一一对应的序列。
输出的码符号序列称为码字，长度l
i
称为码字长度或简称码长。可见，编码就是从信
源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且
是可逆的。
码符号的分类：
下图是一个码分类图
即时码（非延长码）
非即时码
唯一可译码
非唯一可译码
非奇异码
奇异码
分组码
非分组码
码
下面，我们给出这些码的定义。
1.二元码
若码符号集为X={0;1}，所有码字都是一些二元序列，则称为二元码。二元码是数字
通信和计算机系统中最常用的一种码。
2.等长码：
若一组码中所有码字的码长都相同，即l
i
=l(i=1,2,…q)，则称为等长码。
3.变长码：
若一组码组中所有码字的码长各不相同，则称为变长码。
4.非奇异码：
若一组码中所有码字都不相同，则称为非奇异码。
5.奇异码：
若一组码中有相同的码字，则称为奇异码。
6.唯一可译码：
若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此
码称为唯一可译码，否则就称为非唯一可译码。
7.非即时码和即时码：
如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才
能判断是否可以译码，这样的码叫做非即时码。
如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何
一个码字都不是其他码字的前缀部分，也叫做异前缀码。
码树：
即时码的一种简单构造方法是树图法。对给定码字的全体集合C={W
1
,W
2
,…W
q
}来说，
可以用码树来描述它。所谓树，就是既有根、枝，又有节点，如图5.2（80业）所示，图
中，最上端A为根节点，A、B、
C、D、E皆为节点，E为终端节点。A、B、C、D为中间节点，中间节点不安排码字，
而只在终端节点安排码字，每个终端节点所对应的码字就是从根节点出发到终端节点走过
的路径上所对应的符号组成，如图5.2中的终端节点E，走过的路径为ABCDE，所对应的
码符号分别为0、0、0、1，则E对应的码字为0001。可以看出，按树图法构成的码一定
满足即时码的定义（一一对应，非前缀码）。
从码树上可以得知，当第i阶的节点作为终端节点，且分配码字，则码字的码长为i。
任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是
唯一的。如图3.2中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。
对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即
时码。
每个节点上都有r个分支的树称为满树，否则为非满树。
即时码的码树图还可以用来译码。当收到一串码符号序列后，首先从根节点出发，根
据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走
的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字。
然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的
信源符号序列。
克拉夫特（Kraft）不等式
定理3.1对于码符号为X={x
1
,x
2
,…x
r
}的任意唯一可译码，其码字为W
1
,W
2
,…W
q
，所
对应的码长为l
1
,l
2
…l
q
，则必定满足克拉夫特不等式
1
1
q
i
l
ir
反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。
注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据
（可以排除，不能肯定）。如{0，10，010，111}满足克拉夫特不等式，但却不是唯一可译
码。
例题：设二进制码树中X={x
1
,x
2
,x
3
,x
4
}，对应的l
1
=1,l
2
=2,l
3
=2,l
4
=3，由上述定理，可
得
1
8
9
222223221
4
1
i
l
i
因此不存在满足这种码长的唯一可译码。可以用树码进行检查。
唯一可译码的判断法（变长）：
将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，
则可判断此码C为唯一可译码。
集合F的构成方法：
首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾
随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新
的尾随后缀列出，
然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依
此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引
起的所有尾随后缀，接着，按照上述步骤将次短码字、…等等所有码字可能产生的尾随后
缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。
例题：设码C={0,10,1100,1110,1011,1101}，根据上述测试方法，判断是否是唯一可译
码。
解：1.先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。
2.再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀。
所以，集合F={11，00，10，01}，其中“10”为码字，故码C不是唯一可译码。
§3.2定长编码定理
前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。设信
源输出符号序列长度为L，码字的长度为K
L
，编码的目的，就是要是信源的信息率最小，
也就是说，要用最少的符号来代表信源。
在定长编码中，对每一个信源序列，K
L
都是定值，设等于K，我们的目的是寻找最小
K值。要实现无失真的信源编码，要求信源符号X
i
(i=1,2,…q)
与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）。
定长编码定理：
由L个符号组成的、每个符号熵为H
L
(X)的无记忆平稳信源符号序列X
1
X
2
X
3
…X
L
用
K
L
个符号Y
1
Y
2
…Y
KL
（每个符号有m中可能值）进行定长变码。对任意0,0，只要
)(logXHm
L
K
L
L则当L足够大时，必可使译码差错小于；反之，当
2)(logXHm
L
K
L
L
时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。
式中，左边是输出码字每符号所能载荷的最大信息量
所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总
可以实现几乎无失真的编码。条件时所取得符号数L足够大。
设差错概率为
P，信源序列的自方差为
22)]}()({[)(XxIEX
i
则有：
2
2)(
L
X
P
当
)(2X和2均为定值时，只要L足够大，
P可一小于任一整数，即
2
2)(
L
X
此时要求：
2
2)(X
L
只要足够小，就可以几乎无差错地译码，当然代价是L变得更大。
令
m
L
K
KLlog
为码字最大平均符号信息量。
定义编码效率为：
K
XH
L
)(
最佳编码效率为
)(
)(
XH
XH
L
L
无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使
输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L
非常大进行统一编码才行，这往往是不现实的。
例如：
例题：设离散无记忆信源概率空间为
04.005.006.007.01.01.018.04.0
87654321
xxxxxxxx
P
X
信源熵为
符号/55.2log)(
8
1
2
bitppXH
i
ii
自信息方差为
82.7)]([)(log
)]([log)(2)(log
})]([log)(2){(log
)](log[})]()({[)(
8
1
22
2
8
1
8
1
8
1
2
2
2
2
8
1
2
2
2
2
8
1
2
2
22
i
ii
iii
iiiii
i
iii
i
iii
XHpp
pXHppXHpp
XHpXHpp
XHppXHxIEX
对信源符号采用定长二元编码，要求编码效率%90，无记忆信源有
)()(XHXH
L
，因此%90
)(
)(
XH
XH
可以得到28.0
如果要求译码错误概率610，则87
2
2
10108.9
(
）X
L
由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要
810L个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。
如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无
差错，但编码效率只有2.55/3=85%。因此，一般说来，当L有限时，高传输效率的定长码
往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。
§3.3最佳编码
最佳码：对于某一信源和某一码符号集来说，若有一唯一可译码，
其平均码长K小于所有其他唯一可译码的平均长度
为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均
码字长度最短。能获得
最佳码的编码方法：香农（Shannon）
费诺（Fano）
哈夫曼（Huffman）
1、香农编码方法
香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均
码长达到极限值，这是一个很重要的极限定理。
香农第一定理指出，选择每个码字的长度K
i
满足下式：
K
i
=[
i
p
1
log]——取整
即：－log
2
p
i
≤K
i
≤1－log
2
p
i
就可以得到这种码。这种编码方法称为香农编码。
例：设无记忆信源的概率空间为：
8
1
8
1
4
1
2
1
)(
4321
uuuu
up
U
计算各符号的码字长度：
K
1
=log2=1
K
2
=log4=2
K
3
=K
4
=log8=3
用图示码树，可得各自的码字：
u
1
:（0），u
2
:（10），u
3
:（110），u
4
:（111）
信息熵H(U):
75.1
4
7
8
1
log
8
1
8
1
log
8
1
4
1
log
4
1
2
1
log
2
1
)(log)()(
4
1
i
ii
upupUH
信源符号的平均码长:
75.123
8
1
2
4
1
1
2
1
K
编码效率
%100
75.1
75.1)(
K
UH
对于这种信源，香农编码是最佳编码。码树达到满树。
香农编码法多余度稍大，实用性不大，但有重要的理论意义。
编码方法如下：
⑴将信源消息符号按其出现的概率大小依次排列
p(u
1
)≥p(u
2
)≥…≥p(u
n
)
⑵确定码长K
i
(整数)：
K
i
=[
i
p
1
log]——取整
⑶为了编成唯一可译码，计算第i个消息的累加概率
1
1
)(
i
k
ki
upp
⑷将累加概率P
i
变换成二进制数。
⑸取p
i
二进制数的小数点后K
i
位即为该消息符号的二进制数。
例：
05.005.02.03.04.0
)(
54321
uuuuu
up
U
信源
符号u
i
符号概率
p(u
i
)
累加
概率P
i
-log
p(u
i
)
码字长
度K
i
码
字
u
1
0.40
1.
32
2
0
0
u
2
0.30.4
1.
73
2
0
1
u
3
0.20.72.31
3201
u
4
0.050.9
4.
3
5
1
1100
u
5
0.050.95
4.
3
5
1
1101
以i=3为例，计算各符号的码字长度：
K
3
=[－log0.2]=3
累加概率P
4
=0.7——0.10110…——101
由图，这些码字没有占满所有树叶，所以是非最佳码。
95.1
05.0log05.022.0log2.03.0log3.04.0log4.0)(
UH
平均码长：
5.2
2505.032.023.024.0
)(
5
1
i
ii
KupK
编码效率：
%78
5.2
95.1)(
K
UH
为了提高编码效率，首先应达到满树；例如把u
4
u
5
换成A、B这些前面的节点，就
可减小平均码长。所以不应先规定码长，而是由码树来规定码字，可得更好的结果。
2、费诺编码方法
费诺编码属于概率匹配编码，但它不是最佳的编码方法。编码过程如下：
⑴将信源符号接概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一
个二进制码元“0”和“1”。
⑵将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，
并又赋予两个组一个二进制符号“0”和“1”。
⑶如此重复，直至每个组只剩下一个信源符号为止。
信源符号所对应的码字即为费诺码。
例：
05.005.02.03.04.0
)(
54321
uuuuu
up
U
信源符号
u
i
符号概率
p(u
i
)
第1次
分组
第2次
分组
第3次
分组
码字码长
u
1
0.4
0
0002
u
4
0.05
1
00103
u
5
0.0510113
u
2
0.3
1
0102
u
3
0.21112
该费诺码的平均码长
1.2)305.0(222.023.024.0
)(
7
1
i
ii
KupK
编码效率：
.%93
1.2
95.1)(
K
UH
显然，费诺码比香农码的平均码长小，编码效率高。其实这样编码的效率还不是最高
的，现用另一种分割方法：
信源符号
u
i
符号概率
p(u
i
)
第1次
分组
第2次
分组
第3次
分组
第4次
分组
码字码长
u
1
0.4001
u
2
0.3
1
0102
u
3
0.2
1
01103
u
4
0.05
1
011104
u
5
0.05111114
该费诺码的平均码长
0.2)405.0(232.023.014.0
)(
7
1
i
ii
KupK
编码效率：
%5.97
0.2
95.1)(
K
UH
可见编码效率又有所提高。事实上这已是最佳编码，就是说编码效率已不能再提高。
但这样试探寻找分割方法总不是办法，因而赫夫曼提出一种编码方法，并证明这种编码在
块码中已是最佳的。
3、哈夫曼编码方法
哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始，把各节点分给某
子集；若子集已是单点集，它就是一片叶而作为码字。而赫夫曼编码是先给每一符号一片
树叶，逐步合并成节点直到树根。
哈夫曼编码的步骤如下：
⑴将信源消息符号按其出现的概率大小依次排列
p(u
1
)≥p(u
2
)≥…≥p(u
n
)
⑵取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字
母的概率，与未分配的二进符号的字母重新排队。
⑶对重排后的两个概率最小符号重复步骤⑵的过程。
⑷不断继续上述过程，直到最后两个符号配以0和1为止。
⑸从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。
例：给定离散信源如下：
01.010.015.017.018.019.020.0
)(
7654321
uuuuuuu
up
U
61.2
01.0log01.010.0log10.015.0log15.0
17.0log17.018.0log18.019.0log19.02.0log2.0)(
UH
平均码长：
72.2
401.0410.0315.0317.0318.0219.022.0
)(
7
1
i
ii
KupK
编码效率
%96.95
72.2
61.2)(
K
UH
哈夫曼编码方法得到的码并非是唯一的。非唯一的原因：
·每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意意的，
所以可以得到不同的哈夫曼码，但不会影响码字的长度。
·对信源进行缩减时两个概率最小的符号合并后的概率与其它信源符号的概率相同时，
这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫
曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。
例：给定离散信源如下：
1.01.02.02.04.0
)(
54321
uuuuu
up
U
有两种哈夫曼编码方法如下图所示：
平均码长：
2.2231.0222.024.0
)(
5
1
1
i
ii
KupK
2.2241.032.022.014.0
)(
5
1
2
i
ii
KupK
因为这两种码有相同的平均码长，所以有相同的编码效率，但每个信源符号的码长却
不相同。
在这两种不同的码中，选择哪个码好呢？我们引进码字任度K
i
偏离平均码长K的方
差σ2，即
5
1
222))((])[(
i
iii
KKupKKE
分别计算上例中两种码的方差
16.0
2)2.23(1.02)2.22(2.0)2.22(4.02222
1
36.1
2)2.24(1.0)2.23(2.0)2.22(2.0)2.21(4.022222
2
可见，第一种编码方法的方差要小许多。所以，对于有限长的不同信源序列，用第一
种方法所编得的码序列长度变化较小。因此相对来说选择第一种编码方法要更好些。
由此得出，在哈夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得来
的概率和尽量处于是高的位置。这样可使合并的元素重复编码次数减少，使短码得到充分
利用
从以上实例中可以看出，哈夫曼码具有以下三个特点：
⑴哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，
即p
i
＞p
j
有K
i
＜K
j
，充分利用了短码。
⑵缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情
况），从而保证了哈夫曼是即时码。
⑶每次缩减信源的最长两个码字有相同的码长。
这三个特点保证了所得的哈夫曼码一定是最佳码。
第五章信源编码（第十一讲）
（2课时）
主要内容：（1）限失真信源编码定理（2）常用信源编码方法简介（游程编码、矢量量
化编码、算术编码）
重点：常用信源编码方法简介。
难点：限失真信源编码定理、限失真信源编码定理。
特别提示：运用
说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另
外，注意，解题方法。多加一些内容丰富知识和理解。
作业：灵活运用。课外仍以学生复习。
§限失真信源编码定理
定理（限失真信源编码定理）设R(D)为离散无记忆信源X的信息率失真函数，R为
信息传输率，则当信息率R>R（D），只要信源序列长度L足够长，一定存在一种编码方法，
其译码失真小于或等于D＋ε，ε为任意小的正数；反之，若R 样的编码方法，其译码失真必大于D。 如果是二元信源，对于任意小的ε>0，每一个信源符号的平均码长满足如下公式： ()()RDKRD 该定理指出，在失真限度内使信息率任意接近R（D）的编码方法存在,然而，若信息 率小于R（D），平均失真一定会超过失真限度D。 对于连续平稳无记忆信源，虽然无法进行无失真编码，但在限失真情况下，有与该定 理一样的编码定理。 该定理只说明最佳编码是存在的，但对于如何进行编码却一无所知，因而就不能像无 损编码那样从证明过程中引出概率匹配的编码方法，一般只能从优化的思路去求最佳编码。 这个定理证明了允许失真D确定后，总存在一种编码方法，使信息传输率R大于R（D） 且可任意接近R（D），而平均失真小于允许失真D。反之，若R 均失真将大于D。如果用二进制符号进行编码的话，在允许一定失真D的情况下，平均每 个信源符号所需的二元码符号的下限值就是 R（D）。由此可见，信息率失真函数R（D）确实是在允许失真度为D的情况下信源 信息压缩的下限值。当信源给定后，无失真信源压缩的极限值是信源熵H（U）；有失真信 源压缩的极限值是信息率失真函数R（D）。 在给定某D后，一般R（D） 同样，该定理只是一个存在定理。至于如何寻找最佳压缩编码方法，定理中并没有给 出。在实际应用中，该定理主要存在以下两大类问题。 第一类问题是,符合实际信源的R(D)函数的计算相当困难。首先，需要对实际信源的 统计特性有确切的数学描述。其次，需要对符合主客观实际的失真给予正确的度量，否则 不能求得符合主客观实际的R(D)函数。 例如，通常采用均方误差来表示信源的平均失真度。但对于图像信源来说，均方误差 较小的编码方法，人们视觉感到失真较大。所以，人们仍采用主观观察来评价编码方法的 好坏。因此，如何定义符合主客观实际情况的失真测度就是件较困难的事。第三，即便对 实际信源有了确切的数学描述，又有符合主客观实际情况的失真测度，而信息率失真函数 R(D)的计算还是比较困难的。 第二类问题是，即便求得了符合实际的信息率失真函数，还需研究采用何种实用的最 佳编码方法才能达到R(D)。 目前，这两方面工作都有进展。尤其是对实际信源的各种压缩方法，如对语音信号、 电视信号和遥感图像等信源的各种压缩方法有了较大进展。相信随着数据压缩技术的发展， 限失真编码理论中存在的问题将会得到解决。 §限失真信源编码常用信源编码方法 一、游程编码 游程：指数字序列中连续出现相同符号的一段。 二元序列只有两种符号：“0”和“1”： 连“0”段称为“0”游程，游程长度为L(0) 连“1”段称为“1”游程，游程长度为L(1) 由于是二进制序列，“0”游程和“1”游程总是交替出现。若规定二元序列总是从“0” 开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程…… 对于随机序列，游程的长度是随机的，其取值为1，2，3…自至无穷。 游程序列：用交替出现的“0”游程和“1”游程的长度，来表示任意二元序列。 例如二元序列 00l… 可变换成如下游程序列 31132131… 己规定游程序列从“0”开始，由上述游程序列，很容易恢复出原来的二元序列。 游程序列已是多元序列，各长度就可按哈夫曼编码或其它方法处理以达到压缩码率的 目的。这种从二元序列转换成多元序列的方法，在实现时比以前的并元法简单；因为游程 长度的计数比较容易，得到游程长度后就可从码表中找出码字输出，同时去数下一个游程 长度。此外，在减弱原有序列的符号间的相关性方面采用游程变换一般也比并元法更有效。 当然，要对二元序列进行哈夫曼编码时应先测定“0”游程长度和“1”游程长度的概 率分布，或由二元序列的概率特性去计算各种游程长度的概率。 设二元序列为独立序列，“0”和“1”的概率分别为p 0 和p 1 ，则“0”游程长度L(0) 的概率为 1 1)0( 0 )]0([ppLpL 式中L(0)=1，2，…，游程长度至少是1。从理论上来说，游程长度可以是无穷，但很 长的游程实际出现的概率非常小。 1)0( 0 11 1 )]0([ L p p Lp 则“1”游程长度L(1)的概率为 0 1)1( 1 )]1([ppLpL 1)1( 1 01 1 )]1([ L p p Lp “0”游程长度的熵： 1 0 1)0( 1 1)0( 021 1)0( 0 1)0( 2 )( ][log)]0([log)]0([)]0([ p pH ppppLpLpLH L LL L “0” 游程序列的平均游程长度 1 1)0( 1 1)0( 0 1)0( 0 1 )0()]0([)]0([)]0([ p ppLLpLLEl L L L 同理，“1”游程长度的熵和平均游程长度： 变换后的游程序列是独立序列 0 1 0 1 1 )]1([ )( )]1([ p LEl p pH LH )()( )]1([)]0([ )( 10 10 pHpH ll LHLH XH 游程变换后符号熵没有变。——因为游程变换是一一则应的可逆变换。所以变换后熵 值不变。 由于游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码，可获得较高的 编码效率。 假设“0”游程长度的哈夫曼编码效率为η 0 ，“1”游程长度的哈夫曼编码效率为η 1 , 由编码效率的定义得二元序列的编码效率 10 )]1([)]0([ )]1([)]0([ LHLH LHLH 假设η 0 ＞η 1 ，则有η 0 ＞η＞η 1 当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不 会低于较小的那个效率。要想编码效率η尽可能高，应使上式的分母尽可能小，这就要求 尽可能提高熵值较大的游程的编码效率，因为它在往分母中占的比重较大。 理论上来说游程长度可从1到无穷。要建立游程长度和码字之间的一一对应的码表是 困难的。一般情况下，游程越长，出现的概率就越小；当游程长度趋向于无穷时，出现的 概率也趋向于0。 按哈夫曼码的编码规则，概率越小码字越长，但小概率的码字对平均码长影响较小， 在实际应用时常对长码采用截断处理的方法 取一个适当的n值，游程长度为1,2,…,2n-1,2n，所有大于2n者都按2n来处理。然后 按照哈夫曼码的编码规则，将上列2n种概率从大到小排队，构成码树并得到相应的码字。 二、矢量量化编码 要想得到性能好的编码，仅采用标量量化是不可能的。在最佳编码中，如将离散信源 的多个符号进行联合编码可提高效率，这对连续信源也是如此。当把多个信源符号联合起 来形成多维矢量，再对矢量进行标量量化时，自由度将更大，同样的失真下，量化级数可 进一步减少，码率可进一步压缩。这种量化叫做矢量量化。 实验证明，即使各信源符号相互独立，多维量化通常也可压缩信息率。因而矢量量化 引起人们的兴趣而成为当前连续信源编码的一个热点。可是当维数较大时，矢量量化尚无 解析方法，只能求助于数值计算；而且联合概率密度也不易测定，还需采用诸如训练序列 的方法。一般来说，高维矢量的联合是很复杂的，虽已有不少方法，但其实现尚有不少困 难，有待进一步研究。 设矢量量化器输入集为X＝{X 1 ，X 2 ，…，X N }，X j ∈X，X j ＝（x j1 ，x j2 ，…,x jk ），X ∈R k （k维欧几里德空间），把Rk划分成J＝2n个互不相交的子空间R 1 ，R 2 ，…，R Ｊ ， 求出每个子空间的质心Y i ，所有的Y i 构成Y＝{Y 1 ，Y 2 ，…，Y Ｊ }，Y为量化器的输出空 间，也叫码书（或码本），Y i 叫码字或码矢，J叫码书的长度。 对J阶K维的矢量量化，实质上是判断输入X j ∈R k 属于哪个子空间R i ，然后输出该 子空间代表码字Y i ，即： Y i ＝Q（X j ）,1≤i≤J，1≤j≤N（4―42） 这里Y i 就是X j 的编码。 实际编码时，在发送端只需记录代表码字Y i 的下标i，所以编码过程是把X映射到I ＝{1，2，…，J}；而译码过程是在接收端依据收到的I代码，查找码书Y，获得码字Y i ， 用来代替X j 。由于总的码字个数J一般远小于总的输入信号N×K，所以矢量量化的压缩 能力非常大。 传输或存储一个矢量所需比特为lbJ（一般J＝2 n ），它是一个K维矢量，就是K个输 入信号，所以每个输入信号的平均比特只有lbJ/K，称之为压缩比。适当选取码书长度J 和码字维数K，可以获得很大压缩比。矢量量化中码书的码字越多，维数越大，失真就越 小。只要适当地选择码字数量，就能控制失真量不超过某一给定值，因此码书控制着矢量 的大小。矢量量化时每输入一个X j ，都要和J个码字Y i 逐一比较，搜索与其最接近的码 字Y i 。由于两者均为K维矢量，所以工作量很大。矢量量化是定长码，容易处理。 矢量量化由码书Y和划分R i 的条件惟一确定。当码书确定后，通过最近邻域准则可 以惟一确定区域分割。因此，最佳量化器的设计也就是最佳码书Y的设计。前面，在讨论 一维标量的最佳设计时，引入了MaxLivod的迭代算法，1980年Linde、Buzo和Gray 将此算法推广到了多维空间，称作LBG算法。因LBG算法由于理论上的严密性和实现的 简便性以及较好的设计效果而得到了广泛的应用，并成为各种改进算法的基础。有关LBG 算法等知识请参阅有关文献。 三、算术编码 1、算术码的主要概念： 把信源输出序列的概率和实数段[0，1]中的一个数ρ联系起来。设信源字母表为{a 1 ,a 2 }， 其发生概率为p(a 1 )=0.6,p(a 2 )=0.4。将[0，1]分成两个与概率比例相应的区间，[0，0.6][0.6， l]当信源输出的第一个符号s 1 =a 1 时，数ρ的值处在[0，0.6]，s 1 =a 2 时，[0.6，l]。 根据信源字母s 1 的情况,把ρ所在的段再次按概率比例分成 [0，1]→[0，0.6][0.6，l] [0,0.36][0.36,0.6][0.6,0.84][0.84,1] s 1 =a 1 s 1 =a 2 根据信源输出的第二个字母s 2 的取值情况，可以更精确地确定出数ρ所在的区间位置。 在信源输出第n－1个符号后，若ρ所在的位置为 [A n-1 ，B n-1 ] 则当信源输出的第n个符号为： s n =a 1 时，s n =a 2 A n =A n-1 A n =A n-1 +0.6(B n-1 －A n-1 ) B n =A n-1 +0.6(B n-1 －A n-1 )B n =B n-1 按照这一方法，序列的概率刚好等于ρ所在区间的长度。随着序列的长度不断增加， ρ所在区间的长度就越短，也就可以更加精确地确定ρ的位置。当信源字母序列长度趋于 无限时，ρ所在区间成为一点。 2、累积概率 设信源字母表为A={a 1 ,a 2 ,…,a i ,…a m },字母a i 的概率p(a i ) 修正的累积概率为 )( 2 1 )()( 1 1 k k i ik apapaF 定义字母a k 的累积概率为 1 1 )()( k i ik apaF F(a 1 )=0，F(a 2 )=p(a 1 )，F(a 3 )=p(a 1 )+p(a 2 ) p(a k )=F(a k+1 )－F(a k ) 当A={0，l}二元信源时： F(0)=0，F(1)=p(0) 计算信源序列s=（s 1 ,s 2 ,……,s n ）的累积概率 以二元无记忆信源为例： 初始时：在[0，l]由F(1)划分成二个子区间： [0，l]→[0,F(1)][F(1),1]，F(1)=p(0) 01 子区间[0,F(1)][F(1),1]的宽度为 A(0)=p(0)A(1)=p(1) 若输入序列的第一个符号为s=“0”，即落入对应的区间[0,F(1)] F(s=“0”)=F(0)=0 当输入第二个符号为“1”,s=“01”对应的区间在[0,F(1)]中进行分割 A(00)=A(0)p(0)=p(0)p(0)=p(00) A(01)=A(0)p(1)=p(0)p(1)=p(01) =A(0)－A(00) “00”对应的区间[0,F(01)]；“01”对应的区间[F(01),F(1)] s=“01”的累积概率 F(s=“01”)=F(01)=p(0)p(0) 当输入第三个符号为“1”， s1=“011”，所对应的区间在[F(01),F(1)]中进行分割 对应的区间[F(s),F(s)+A(s)p(0)] 对应的区间[F(s)+A(s)p(0),F(1)] A(010)=A(01)p(0)=A(s)p(0) A(011)=A(01)p(1)=A(s)p(1) =A(01)－A(010) =A(s)－A(s0) F(s1)=F(s)+A(s)p(0) F(s0)=F(s) 现已输入三个符号串，将这符号序列标为s，接着输入第四个符号为“0”或“1”。 可计算出s0=“0110”或s1=“0111”对应的子区间及其累积概率。 当已知前面输入符号序列为s，若接着再输入一个符号“0” 累积概率 区间宽度 F(s0)=F(s) A(s0)=A(s)p(0) 若接着输入的一个符号是“1”，对序列s1的累积概率为 F(s1)=F(s)+A(s)p(0) A(s1)=A(s)p(1)=A(s)－A(s0) 由前分析又知，符号序列对应的区间宽度为 A(0)=p(0) A(1)=1－A(0)=p(1) A(00)=p(00)=A(0)p(0)=p(0)p(0) A(01)=A(0)－A(00)=p(01)=A(0)p(1)=p(0)p(1) A(10)=p(10)=A(1)p(0)=p(1)p(0) A(11)=A(1)－A(10)=p(11)=A(1)p(1)=p(1)p(1) A(010)=A(01)p(0)=p(01)p(0)=p(010) A(011)=A(01)－A(010)=A(01)p(1)=p(01)p(1)=p(011) ┊ 信源符号序列s所对应区间的宽度等于符号序列s的概率p(s) 二元信源符号序列的累积概率的递推公式为 F(sr)=F(s)+p(s)F(r)（r=0,1） 其中sr表示已知前面信源符号序列为s接着再输入符号为r。而F(r)：[F(0)=0，F(1) =p(0)] 同样可得信源符号序列所对应区间的宽度的递推公式为 A(sr)=p(sr)=p(s)p(r)（r=0,1） 已输入的二元符号序列为s=“011”，若接着输入符号为1得序列的累积概率： F(s1)=F(0111)=F(s=011)+p(011)p(0) =F(s=01)+p(01)p(0)+p(011)p(0) =F(s=0)+p(0)p(0)+p(01)p(0)+p(011)p(0) =0+p(00)+p(010)+p(0110) 其对应区间宽度 A(s1)=A(s=011)p(1)=p(011)p(1)=p(0111) 由于 F(sr)=F(s)+p(s)F(r) A(sr)=p(sr)=p(s)p(r) 是可递推运算，因此适合于实用。实际中，只需两个存储器，把p(s)和F(s)存下来， 然后根据输入符号和上式，更新两个存储器中的数值。 因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算 术编码。 将上式推广到多元信源序列，得一般的递推公式 F(sa k )=F(s)+p(s)F(a k ) A(sa k )=p(sa k )=p(s)p(a k ) 通过关于信源符号序列的累积概率的计算，F(s)把区间[0,1]分割成许多小区间，不 同的信源符号序列对应于不同的区间为[F(s),F(s)+p(s)]。可取小区间内的一点来代表这序 列。 代表大于等于的最小整数。 L L sF.0)( 令 )( 1 log sp L 把累积概率F(s)写成二进制的小数，取小数点后L位，以后如果有尾数，就进到第L 位，这样得到一个数C。 例F(s)=0.10110001，p(s)1/17，则L=5， 得C=0.10111，s的码字为10111 这样选取的数值C，一般根据二进小数截去位数的影响,得 C－F(s)＜2-L 当F(s)在L位以后没有尾数时C=F(s)。而由)(logspL可知F(s)≥2-L 则信源符号序列s对应区间的上界 F(s)+p(s)≥F(s)+2-L＞C 可见数值C在区间[F(s),F(s)+p(s)]内。信源符号序列对应的不同区间是不重叠的，所 以编得的码是即时码。 实用中，采用累积概率F(s)表示码字C(s)，符号概率p(s)表示状态区间A(s)，则有 C(sr)=C(s)+A(s)F(r) A(sr)=A(s)p(r) 因为信源符号序列s的码长满足)(logspL，所以得 若信源是无记忆的 H(Sn)=nH(S) n SH n L SH 1 )()( sss spspsLspLspsp1)(log)()()()(log)( 平均每个信源符号的码长 nn SH n L n SHnn1)()( 例：设二元无记忆信源A={0,1}，p(0)=1/4，p(1)=3/4 对二元序列s=11111100做算术编码 解：根据上述的编码规则，可得 p(s=11111100)=p2(0)p6(1)=(3/4)2(1/4)6 )( 1 log sp L=7 1 1 )()( k i ik apaF F(a 3 )=p(a 1 )+p(a 2 ) F(s)=p(00000000)+p(00000001)+p(00000010)+… +p(11111011) =1－p(11111111)－p(11111110) －p(11111101)－p(11111100) =1－p(111111)=1－(3/4)6=0.11 得C=0.1101010s的码字为1101010 编码效率%7.92 8/7 811.0)( L sH 这种按全序列进行编码，随着信源序列n的增长，效率还会增高。 递推编码过程可列表如下： 得s的码字为1101010。此时s=11111100对应的区间为 ［0.11,0.1101］。可见C是区间内一点。 实际编码是用硬件或计算机软件实现,所以采用速推公式来进行编码。只要存储量允 许，这种编码，可以不论s有多长，一直进行计算下去，直至序列结束。 本例题中p(0)=2-2，又F(0)=0，F(1)=p(0)=2-2在递推公式中每次需乘以2-2或 乘以（l－2-2）。在计算机中，乘以2-Q（Q为正整数），就可用右移Q位采取代；乘以1－ 2-Q就可用此数减去右移Q位数取代。这样简捷快速。 译码就是一系列比较过程。每一步比较C－F(s)与p(s)p(0) 若C－F(s)＜p(s)p(0)则译输出符号为“0” 若C－F(s)＞p(s)p(0)则译输出符号为“1” s为前面已译出的序列串 p(s)是序列串s对应的宽度 F(s)是序列串s的累积概率，即为s对应区间的下界。 p(s)p(0)是此区间内下一个输入为符号“0”所占的子区间宽度。 由上面分析可知，算术编码效率高，编译码速度也快。 前面叙述了算术编码的基本方法。在实用中还需考虑计算精度问题、存储量问题、近 似相2-Q中Q的选择问题等等。 所以，算术编码的编码效率很高、当信源符号序列很长时。很大时，平均码长接近信 源的 一般情况下，F(ak)为实数，若用二进制数精确表示，则有可能需要无穷多位，但作为 码字只需有足够的位数，使其能与ak一一对应就够了，所以只需用L位来表示F(ak)，即 取 L L k aF.0)( 例：设离散无记忆信源字母表为{a1,a2,a3,a4}，p(a1)=0.25p(a2)=0.5，p(a3)=0.125， p(a4)=0.125。 求：字母ak的累积概率F(ak)及F(ak)的二进制表示和相应的码字。如表所示： a k p (ak) F (ak) F(ak)二进制 表示 码 字 )( k aF)( k aF a 1 a 2 a 3 a 0 .25 0 .50 0 .125 0 0 0 .25 0 .75 0 .875 0 0.01 0.11 0.111 4.125 在上面两个例子中，算术编码的效果并不很好，这是因为仅用算术编码方法对婚 字母进行编码、若对源字母序列进行编码，则算术编码有独特的优点它和以随若序列长度 N的增加而自然地改进压缩效果。 第五章信源编码（第十二讲） （2课时） 主要内容：（1）常用信源编码方法简介（预测编码）（2）常用信源编码方法简介（变 换编码）。 重点：常用信源编码方法简介（预测编码）。 难点：常用信源编码方法简介（预测编码）。 特别提示：运用 说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另 外，注意，解题方法。多加一些内容丰富知识和理解。 作业：灵活运用。课外仍以学生复习。 §限失真信源编码常用信源编码方法 四、预测编码 预测编码的基本原理 对于有记忆信源，信源输出的各个分量之间是有统计关联的，这种统计关联性可以加 以充分利用。 预测编码：在这种编码方法中，编码器和译码器都存贮有过去的信号值，并以此来预 测或估计未来的信号值。 在编码器发出的不是信源信号本身，而是信源信号与预测值之差；在译码端，译码器 将接收到的这一差值与译码器的预测值相加，从而恢复信号。 设信源第i瞬间的输出为u i ，根据信源u i 的前K个样值，给出的预测值为 )( ˆ 21kiiii uuufu 其中f为预测函数，它可以是线性也可以是非线性函数，线性预测函数实现比较简 单，比如图5-4-2所示，这时预测值为： k j jiji uau 1 ˆ 则第i个样值的预测误差值为 k j jijiiii uauuue 1 ˆ 根据信源编码定理，若直接对信源输出进行编码，则其平均码长K u 应趋于信源熵： Ui u ii upupUH)(log)()( 若对预测变换后的误差值e进行编码，其平均码长K e 应趋于误差信号熵： Ui u ii epepEH)(log)()( 显然，从信息论观点，预测编码能压缩信源数码率的必要条件为： )()(UHEHKK ue 这里 u K表示预测前的信源编码平均码长， e K表示预测后误差信号编码的码长。 由于信息熵是概率分布的泛函数，故概率分布越均匀，熵越大；概率分布越不均匀， 比如越集中，熵就越小，即)()(UHEH，信源通过预测以后数据压缩（或连续时的频 带压缩）倍数就越大。 实现预测编码要进一步考虑3个方面的问题： ⑴预测误差准则的选取： ⑵预测函数的选取： ⑶预测器输入数据的选取。 预测误差准则：预测误差所依据的标准 如何选取预测值 i u ˆ ，以使预测误差e i 满足某种意义上的最佳是预测编码设计中的核心 问题。按照不同的最佳准则，可得到比较重要的3种最佳预测器： 最小均方误差预测器：最佳准则：使预测误差的均方值达到最小 最小平均绝对误差预测器最佳准则：使预测器的绝对误差的均值达到最小 最大零误差概率预测器最佳准则：预测值具有零误差的概率或概率密度为最大 预测编码的基本原理 1、 DPCM 信源的话音信号为u(t)，其iTs时刻的抽样值为u(iTs)，简写为u i 。 DPCM基本思想： 将“话音信号样值同预测样值的差”作量化、编码。 K和a j 是预测器的参数，为常数。 该式表示 i u ˆ 是先前K个样值的加权和，{a j }称为预测器系数。 i u ˆ ：u i 的预测值。 发端的预测器和相加器用来获得当前的预测值 i u ˆ 预测器的输出样值 i u ˆ 与其输入样值 i u ~ 的关系满足下式： k j jiji uau 1 ~ ˆ 图中编码器的“预测器和相加器”组成结构同解码器的“预测器和相加器”的组成结 构完全一样： ii yu ˆˆ 显然，信道信息传输无误码时，两个相加器输入端的信号完全一样： x i =y i 。 此时图中解码器的输出信号 i u ~ 与编码器信号 i u ~ 是相同的： ii uu ~~ DPCM系统的量化误差应该定义为输入信号样值u i 与解码器输出信号样值 i u ~ 之差。 ii iiiiiii ye yyueuuq ) ˆ () ˆ ( ~ DPCM系统信噪比 Qp e e u ui SNRG E uE SNB 2 2 2 2 2 2 2 2 2 ][ ][ G P ：预测增益 SNR Q ：量化器所产生的信噪比 五、变换编码 众所周知，信源序列往往具有很强的相关性，要提高信源的效率首先要解除信源的相 关性。解除相关性可以在时域上进行(这就是上节中介绍的预测编码)，也可以在频域，甚 至在广义频域内进行，这就是要在本节中介绍的变换编码。 在信号分析中，对连续的模拟信号，如果它是周期性的,则可采用傅氏级数展开，若是 非周期性的,则可采用傅氏积分(变换)来表示，但无论是级数还是积分,都属于一类正交变 换，是从时域展开成频域的变换。同理,对离散的数据序列信号也可引入同样的离散傅氏变 换。而且，还可以进一步将其推广为广义的频域变换。 在这一节中，首先从解除相关性的需求入手，寻求最佳的域变换。上一节讨论的在空 间和时间域上压缩信源数据冗余量的预测编码的最大特点是直观、简洁、易于实现，特别 是容易设计出具有实时性的硬件结构。但是预测编码的不足在于压缩能力有限。具有更高 压缩能力的方法和目前最为成熟的方法是变换编码，特别是正交变换编码方法和目前尚处 于研究阶段的小波变换编码，这两种方法都具有很强的数据压缩能力。 变换编码的基本原理就是将原来在空间域上描述的信号，通过一种数学变换(例如，傅 里叶变换、正交变换等)变换到变换域(如频率域、正交矢量空间)中进行描述。简单地讲， 即把信号由空间域变换到变换域中，用变换系数来描述。这些变换系数之间的相关性明显 下降，并且能量常常集中于低频或低序系数区域中，这样就容易实现码率的压缩，而且还 大大降低了实现的难度。 变换编码的基本原理 设信源输出为一个一维消息U＝(u1，u2，…，un)，经变换后输出为X＝(x1，x2，…， xn)，故有： X＝PU 由正交性ATA＝A－1A＝I，则有： U＝P－1X＝PTX 式中：P——实正交变换矩阵； PT——矩阵P的转置矩阵； P－1——矩阵P的逆矩阵； I——单位矩阵。 如果经正交变换后，只传送M（M 这时接收端恢复的信号为 TuPx 式中： 1 (,,);Mxxxuu 如何选择正交矩阵P，使M值较小，且使被丢弃的n－M个取值足够地小，以至于既 能得到最大的信源压缩率，同时又使丢弃掉n－M个取值以后，所产生的误差不超过允许 的失真范围是我们关心的问题。因此，正交变换的主要问题可归结为在一定的误差准则下， 寻找最佳或准最佳的正交变换，以达到最大限度地消除原消息源之间的相关性。正交变换 为什么能解除相关性呢？下面讨论这个问题。 由矩阵代数理论可知：对于任意两个随机变量x,y间的相关性可以用x,y的协方差(相 关距)表示。一个信源U的各分量间的相关性可以用信源各分量间协方差矩阵ΦU表示， 其定义为 11121 21222 12 [([])([]) n n T U nnnn EUEUUEU 式中：Φ U ——信源输出U的协方差矩阵； E［·］——数学期望； φ ij ——u i 、u j 协方差。 可以证明U的协方差矩阵ΦU是一个实对称矩阵，它能反映矢量U各分量间的相关 性。若各分量之间互不相关，则协方差矩阵ΦU只在主对角线上有非零元素。主对角线上 的非零元素代表各分量间的方差，即自相关性；非对角线上的元素表示各分量之间的协方 差，即互相关性。 由矩阵代数可知，对于一个实对称矩阵A(A＝AT的矩阵)，必存在一个正交矩阵P， 使得： 1 2 1 12 00 00 00 T n n PAPPAPdig 式中：λ 1 ,λ 2 ,…,λ n ——实对称矩阵A的n个特征根。 可见正交变换能解除相关性。 信源U经正交变换后的输出X协方差矩阵可定义为 ΦX＝E［(X-E［X］)(X-E［X］)T］ ＝E［(PU-E［PU］)(PU-E［PU］)T］ =PE［(U-E［U］)(U-E［U］)T］PT =PΦ U PT 式中：ΦX——信源U正交变换后的信号X的协方差矩阵； X——信源U经正交变换后的矢量； P——正交变换矩阵； PT——正交变换矩阵P的转置矩阵。 为了达到信源压缩的目的，希望通过矩阵P的正交变换后，Φ X 只保留主对角线上的 部分自相关值，即希望其值随i与j值的增大而迅速减小，从而只需取M（M 同时希望各互相关分量均为0，即最大限度地消除原来信源间的相关性。这也就是研究正 交变换的主要指导思想。下面给出最佳正交变换和准最佳正交变换的概念。 这也就是研究正交变换的主要指导思想。下面给出最佳正交变换和准最佳正交变换的 概念。所谓最佳是指在一定的条件（即准则）下的最佳，而这些准则有客观的也有主观的。 这里是按照客观统计上的最小均方误差准则(MMSE)寻求最佳的正交变换。最佳变换是指变 换后的协方差矩阵Φ X 为理想对角线矩阵,这表明经正交交换后完全消除了互相关性。所谓 准最佳变换,是指变换后的协方差矩阵Φ X 是近似对角形矩阵。由矩阵代数的相似变换理论 可知，任何矩阵都可相似于约旦(Jordan)标准型所构成的矩阵。 而约旦标准型就是准对角形矩阵，即矩阵的主对角线上均为特征值λ i,i ＝1，2，…，n， 而在对角线下仅有若干个不为0的1值。所谓相似变换，是指总能找到一非奇异矩阵P使 得P－1AP＝B，这时称A与B相似，如果P为正交矩阵，则有： P－1AP＝PTAP＝B 这个式子从理论上说明，总能找到对角化或准对角化的正交变换矩阵。根据矩阵代数 理论，正交矩阵P不是惟一的。常用的几种正交变换方法有：卡胡南―列夫变换(KLT)、 离散余弦(DCT)变换。 卡胡南―列夫变换(KLT) KLT变换在均方误差准则下是最佳的正交变换，但是由于以下两个主要原因，实际很 少被采用。首先，在KLT变换中，特征矢量与信源统计特性密切相关，即对不同的信源统 计特性，协方差矩阵应该对应不同的特征值才能达到最佳化，这显然是不大现实的。其次， KLT变换运算很复杂，而且目前尚无快速算法，所以很少实际应用，通常仅作为理论上的 参考。 正因为KLT变换的实现比较困难，实用意义不大，因而人们将眼光逐步转向寻找准最 佳的有实用价值的正交变换。目前人们已寻找到不少这类准最佳正交变换，它们分别是离 散傅里叶变换（DFT）、哈尔变换(HRT)、WalshHadamard变换(WHT)、斜变换(SLT)、 离散余弦变换(DCT)、离散正弦变换(DST)等。相比较发现DCT和DST虽然在理论上不是 最优，但是它们在去相关与能量集中性上仅次于KLT变换，而且均具有快速算法。 离散余弦(DCT)变换 使用KLT变换需要知道信源的协方差矩阵，再求出协方差矩阵的特征值和特征矢量， 然后据此构造正交变换矩阵；但求特征值和特征矢量是相当困难的，特别是在高维信源情 况下，甚至求不出来。即使借助于计算机求解，也难于满足实时处理的要求。DCT变换在 压缩效率上略逊于KLT变换，但由于其算法的高效性及结构上的规律性，且有快速算法, 它已经成为H.261、JPEG及MPEG等国际标准的主要环节。 变换编码方法的特性 下面以图像信源为例，说明变换编码的特性。正交变换方法最重要的特点是能量主要 集中分布在信号的低频或低序区域，使大多数变换系数为零或很小的数值。若在信源质量 允许的条件下，可以舍弃能量较小的系数，或者分配其很少的比特，这就是正交变换能实 现高压缩率的根本原因所在。虽然DPCM方法也能使变换系数出现很多的零或小幅值系 数，但是它的这些幅值分布在全空间范围内，对每个系数均需要编码。正交变换方法按统 计规律集中分布在一定的区域上，无需对每个系数编码。 可以证明二维Passevel定理成立，即对于二维酉变换下式成立： 1111 22 0000 (,)(,) MNMN mnij XmnYij 式中：Ｘ——变换前的信号； Ｙ——变换后的信号。 也就是说变换域中的能量与原来空间域中的信号能量保持不变。式子对于数据压缩的 指导意义在于：只有当空间域信号能量全部转换到某个变换域后，有限个空间取样值才能 完全由有限个变换系数对基矢量加权来恢复。正交变换可以使相关的空间样值变为不相关 或弱相关的变换系数，即正交变换能消除存在相关性中的冗余度。实践已经证明正交变换 能使矢量信号的各个分量互不相关，即变换域信号的协方差矩阵为对角线型；在一定条件 下甚至可以使这些系数相互独立，这样就使有记忆信源变成了无记忆信源。 因为归一化正交变换的雅可比(Jacobin)行列式的值等于1，这说明经过正交变换不丢 失信息，因此可以用传输变换系数来达到传输信息的目的。由于归一化正交变换具有熵不 变性，因此可得到图像原始数据块的极限熵H∞，或接近于Ｈ∞。这就保证了用正交变换对 原图像作霍夫曼编码、DPCM编码将有更大的压缩能力。事实上，DPCM方法由于受到图 像扫描因果关系的限制，采用m阶预测器一般得不到H m＋1 ，这是因为图像并不是理想的 马尔可夫链，只会与前几个像素或与周围的部分像素有关。若用正交变换，可对块内的全 部数据进行变换(去相关性)，因此，可使变换域内的像素出现高阶熵，该高阶熵由数据块 内的相关性决定。 根据信息熵知识：lbM＝H0≥H1≥H2≥…≥HM>H∞可知，高阶熵总是低于一阶熵， 根据信息的率失真函数R(D)理论，数码率可降低。KLT算法在理论上是最 佳的，因此可作为其他离散正交变换好坏的参照点。另外对KLT算法人们一直在寻找其特 征值与特征矢量的快速算法，但进展不大。另一方面人们不断地探求一些其他变换方法， 虽然它们不是“最佳”的方法，但是也有很好的去相关性与能量集中性，且实现方法方便、 快速。下面简单介绍这些方法的优缺点。 离散傅里叶变换(DFT)不对信源本身编码，只对变换系数进行编码和传输，具有蝶形 快速算法，但是DFT是一种复数变换，运算量大，实用困难大。WHT变换与DFT相比， 运算量明显减少，这是因为WHT具有DFT的快速算法结构，且只有加、减运算而无乘法， 但是实践证明经WHT变换后，其能量集中程度不如DFT。HRT变换具有比WHT更快的 运算速度，但其能量集中的程度比WHT更差。DCT／DST既具有运算速度较快(具有快速 算法)，而且经DCT／DST后的能量集中性仅次于KLT。 DCT的变换矩阵的基矢量近似于托伯利兹(Toeplitz)矩阵的特征矢量。由于托伯利兹矩 阵能体现人类语音和图像信号的相关特性，因此，对于大多数相关性很强的图像数据，DCT 是KLT目前最好的替代，所以称DCT为次最优正交变换。从变换后的能量集中程度的优 劣来看，各种正交变换的由优至劣的顺序为 KLT→DCT→SLT→DFT→WHT→HRT 若从运算量的大小，它们由小到大的顺序依次为 HRT→WHT→SLT→DCT→DFT→KLT 下面介绍变换矩阵阶数的选择。在图像变换编码中，通常把图像数据分成若干个子数 据块，然后对子数据块实施某种正交变换。因为若变换矩阵阶数取小，虽然便于自适应， 计算速度快，实现简单，但方块效应严重。严重时会使恢复的图像出现“波纹”。若变换矩 阵阶数取大，虽然去相关效果好(因为DFT、DCT、DST等正弦型变换均具有渐近最佳性， 即当变换点数趋于无穷大时，其去相关性能将趋于KLT的，可把图像等数据的协方差矩阵 对角化，但HRT，WHT等除外)，但渐趋饱和。若阶数太大，由于图像本身的相关性将很 小，反而使其压缩效果不明显，却使运算的复杂性增加，造成变换的实时性差。因此子数 据块取4×4，8×8，16×16为好。 对变换后的系数,保留哪些用作编码和传输将直接影响信号恢复的质量。变换系数的选 择原则是保留能量集中的、方差大的系数。系数选择方法通常有区域法和阈值控制系数选 择法两种方法。区域法就是对设定形状区域内的变换系数进行量化编码，区域外的系数就 被舍去。一般来说，变换后的系数值较大的都会集中在区域的左上部，低频率分量都集中 在此部分，需要保留这一部分。其他部分的系数将被舍去，恢复信号时再对它们补以零。 这样，由于保留了大部分信号能量，在恢复信号后，其质量不会产生显著变化。 研究表明，以均方误差为准则的最佳区域是所谓的最大方差区域。区域法编码的明显 缺陷是高频分量完全丢失，由其恢复的图像的轮廓及细节模糊。克服这一缺陷的方法是, 可以预先设定几个区域，根据实际系数分布的情况自动选取能量最大的区域。阈值控制系 数选择法根据系数分布的实际情况设定阈值的大小，若变换系数超过该阈值，则保留这些 系数进行编码传输，对于小于阈值的则补以零。这样，多数低频成分被编码输出，而且少 数超过阈值的高频成分也将被保留下来进行编码输出，这在一定程度上弥补了区域法的不 足。 但这种选择系数的方法有两个问题需要解决：一个是被保留下来进行编码的系数在矩 阵中的位置是不确定的，因此，尚需增加“地址”编码比特数，其码率相对地要高一些；另 一个问题是“阈值”需要通过实验来确定，当然也可以根据总比特数，进行自适应阈值选择， 但这样做需要一定的技术，并且将增加编码的复杂程度。