H??H2???i?jp(si|sj)p(sj)logp(si)?23?0.75log32?13
?0.75log3?1?0.25log1??
第4章 无失真信源编码
一、信源编码的相关概念
1．编码
信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列，
对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码，完成编码功能的器件，称为编码器。接收端有一个译码器完成相反的功能。
信源编码器的输入是信源符号集S?{s1,s2,?,sq}，共有q个信源符号。同时存在
另一个符号集X?{x1,x2,?,xr}，称为码符号集，共有r个码符号，码符号集中的元素称为码元或码符号，编码器的作用就是将信源符号集S中的符号变换成由li个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为码字，并用
wi,i?1,2,?,q来表示，它与信源符号si,i?1,2,?,q之间是一一对应的关系。
码字的集合C称为码，即C?{w1,w2,?,wq}。信源符号si对应的码字wi包含li个
码符号，称为码字长度，简称码长。?
所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。 若要实现无
失真编码，那么这种映射必须是一一对应的、可逆的。 一般来说，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失真传递，所以首先要对信源实现无失真编码。
信源编码有以下3种主要方法：?
匹配编码：根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所
编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。这类编码主要有香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。
变换编码：先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针识别编码：识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编后两种信源编码均为有失真的信源编码。
无失真信源编码针对离散信源，连续信源在量化编码的过程中必然会有量化失真，对变换后的信号进行编码。包括DCT、DFT、DWT。
码，比如文字和语音的识别。
连续信源只能近似地再现信源的消息。
2．码的分类
1）分组码和非分组码
定义：将信源符号集中的每个信源符号固定地映射成一个码字wi，这样的码称为
分组码。
用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码，又称为树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。
2）奇异码与非奇异码
定义：若一种分组码中的所有码字都不相同，则称此分组码为非奇异码，否则称3）唯一可译码与非唯一可译码
定义：任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要
为奇异码。
可译码。
求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。
4）即时码与非即时码
定义：无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译定理：一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码唯一可译码存在的充分和必要条件，即各码字的长度Ki应符合克劳夫特不等式：
n码称为即时码。 字的前缀。
?mi?1?ki?1
其中：m是进制数，n是信源符号数。
二、定长编码定理
定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列
LX1X2?XL，可用KL个符号Y1Y2?YK(每个符号有m种可能，即每个符号取自m个码
元的集合)进行定长编码。对任意ε＞0，δ＞0，只要
KLLKLLlogm?HL(X)??，则当L
足够大时，必可使译码差错小于δ；反之，当
logm?HL(X)?2?时，译码差错一
定是有限值，而当L足够大时，译码几乎必定出错。
注：由于码元个数为m，在编码之后如果码元等概率分布，则平均每个码元能携带的最大信息量为logm，KL长的码字的最大信息量为KLlogm。由于信源符号序列与码字之间的一一对应关系，编码之后对于L长的信源序列，平均每个信源符号的最大信息量就为
KLLlogm(即信息速率)。而L长信源序列在编码之后平均符号熵为HL(X)。
即：只要码字所能携带的信息量大于信源序列输出的信息量
KLlogm?LHL(X)?H(X)，则可以使传输几乎无失真。
能达到差错率要求，源序列长度L需满足L?
?(X)??i22。
22p(xi))?[H(x)]为信源序
其中：?2(x)?D[I(xi)]?E{[I(xi)?H(X)]2}??p(x)(logi列的自信息方差；?为差错概率pe，?为一正数，可以通过最佳编码效率得出。
编码效率：??HL(X)K，其中：K?KLLlogm为编码器的信息输出率，即相对于每
个信源符号，编码器必须输出的信息量（或码长，二进制）。
最佳编码效率：??HL(X)HL(X)??
三、变长编码定理
1．单个符号变长编码定理
若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编
H(X)logmH(X)logm码，一定存在一种无失真编码方法，其码字平均长度K满足下列不等式：
?K??1
理解：H(X)是单符号信源熵，logm是平均每个码元的信息量。也就是说，在未编
码之前单个信源符号的平均信息量为H(X)，而每个码元所能携带的平均信息量为logm，则平均每个信源符号需要多少个码元（平均码长）来表示？
2．离散平稳无记忆序列变长编码定理
对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，
KLLlogm，KL为编码之后的平均码长）满足不等式：
使平均信息率K（平均信息速率
HL(X)?K?HL(X)??
四、几种编码方法
定义：能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集注意：最佳码一般都满足概率匹配准则，即对出现概率较大的信源符号（序列）合称为最佳码。
赋予较短的码字，而对出现概率较小的信源符号（序列）赋予较长的码字，以使得平均码字长度最短。
1．香农编码方法
香农第一定理指出，选择每个码字的长度Ki满足下式I(xi)?Ki＜I(xi)+1，就可以
得到这种码。这种编码方法称为香农编码。
具体编码方法如下：
(1) 将信源消息符号按其出现的概率大小依次排列
p(x1)?p(x2)?…?p(xn) ?
(2) 确定满足下列不等式的整数码长Ki：?
(3) 为了编成唯一可译码，计算第i个消息的累加概率：
i?1?log2(p(xi))?Ki??log2(p(xi))?1pi??k?1p(k)
(4) 将累加概率Pi变换成二进制数。?
(5) 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。
2．费诺码编码方法
(1) 将信源消息符号按其出现的概率大小依次排列：
p(x1)?p(x2)?…?p(xn)
(2) 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，(3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于(4) 如此重复，直至每个组只剩下一个信源符号为止。? (5) 信源符号所对应的码字即为费诺码。 并对各组赋予一个二进制码元―0‖和―1‖。?
相同，并又赋予两个组一个二进制符号―0‖和―1‖。?
3．哈夫曼编码方法
(1) 将n个信源消息符号按其出现的概率大小依次排列，
p(x1)?p(x2)?…?p(xn)
(2) 取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个(3) 对重排后的两个概率最小符号重复步骤(2)的过程。 (4) 不断继续上述过程，直到最后两个符号配以0和1为止。
(5) 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码新字母的概率，与未分配的二进符号的字母重新排队。
字。