第四章 离散信源的无失真编码

1第四章离散信源的无失真编码Shannon三大定理：Shannon第一定理——可变长无失真信源编码定理Shannon第二定理——信道编码定理Shannon第三定理——限失真信源编码定理1第四章离散信源无失真编码4.1离散无记忆信源的不等长编码4.2最佳不等长编码4.3汉字编码方法及其讨论4.4图像的信源编码4.5误码对信源译码的影响2离散无记忆信源的不等长编码不等长编码的优越性

总体上减少码字的长度。不等长编码的特殊问题

①唯一可译性，或者叫做可识别性。解决方案：适当地编码，使得每个码字都具有识别标记。一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2)连接成的字母串c(1)c(2)不能是码字。3离散无记忆信源的不等长编码不等长编码的特殊问题②平均码字长度。设信源随机变量U的概率分布为{ak,p(ak),k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为希望小。解决方案：概率大的事件用短码字。4离散无记忆信源的不等长编码唯一可译性的两种解决方法Def.逗点码①每个码字的开头部分都是一个相同的字母串；②这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。5逗点码显然是唯一可译的，见到逗号就识别为一个码字的开始。离散无记忆信源的不等长编码Def.异字头码每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。6异字头码也是唯一可译的，见到一个码字就识别为一个码字。（即时性）离散无记忆信源的不等长编码信源字母集概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.12510111110111唯一可译:C,D逗点码：D异字头码：C7例离散无记忆信源的不等长编码构造方法一：Shannon-Fano编码法D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。理想情况I(ak)=nklogD8构造方法二：Huffman编码法Shannon-Fano编码例子cabcedeacacdeddaaabaababaaabbacdebaceada共40个字母频度a-16，b-7，c-6，d-6，e-51)将给定符号按照其频率从大到小排序。a-16，b-7，c-6，d-6，e-52)将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：(a,b),(c,d,e)Shannon-Fano编码例子3)第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记14)分别对左右子树重复2)、3)两步，直到所有的符号都成为二叉树的树叶为止。bacde00101011a00b01c10d110e111Shannon-Fano编码例子为什么Shannon-Fano码是异字头码？码树上的每个码字都在树梢。如果不是异字头码，则有的码字就不在树梢，而在中间节点。bacde00101011a00b01c10d110e111Shannon-Fano编码例子编码结果cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......长97bit采用3bit等长编码需120bit采用ASCII码需要320bit离散无记忆信源的不等长编码Th.

Kraft不等式

设信源随机变量共有K个事件。则：各码字长度分别为n1、n2、…、nK的D元异字头码存在的充分必要条件是Th.唯一可译码必满足Kraft不等式。13离散无记忆信源的不等长编码Th.

不等长编码定理（Shannon第一定理）14任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足离散无记忆信源的不等长编码Th.

不等长编码定理的推广现在对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则15任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足离散无记忆信源的不等长编码Def.

平均码长

(重新定义)16任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足离散无记忆信源的不等长编码Def.

编码速率R和编码效率η分别为

17任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足离散无记忆信源的不等长编码18不等长编码与等长编码具有相似的性质：当L增大时，对UL的编码可以使用更短的平均码长，因而更加节省编码速率。但节省编码速率的下限是H(U)。离散无记忆信源的不等长编码

例

2元编码。设；H(U)=0.811。19U概率码字平均码长编码速率编码效率a13/40(1×3/4+1×1/4)/1=110.811a21/41U2概率码字平均码长编码速率编码效率a1a19/160(1×9/16+2×3/16+3×3/16+3×1/16)/2=27/3227/320.961a1a23/1610a2a13/16110a2a21/16111第四章离散信源无失真编码4.1离散无记忆信源的不等长编码4.2最佳不等长编码4.3汉字编码方法及其讨论4.4图像的信源编码4.5误码对信源译码的影响20最佳不等长编码Huffman编码算术编码LZ编码21Huffman编码的最佳性所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。定理4.4.1：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。

Huffman编码的最佳性对信源可对aK-1和aK的码字的最后一位分别指定为1和0，然后作一辅助集

其中，ak’=ak,Pk’=Pk,当k<K-1

aK-1’=aK-1∪aK,PK-1’=PK-1+PK

Huffman编码的最佳性定理3.4.2

对辅助集U’为最佳的码，对原始消息集U也是最佳的。若C’1，C’2，…，C’K-1是对辅助集U'的最佳码，相应码长为n’1，n’2，…，n’K-1，则对U的码字C1，C2,…,CK的码长为nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1Huffman编码的最佳性概率大的采用短码，概率小的采用长码。与编码无关哈夫曼编码26

例

设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。哈夫曼编码27读取码字的时候，一定要从后向前读，此时编出来的码字异字头码。例设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。哈夫曼编码哈夫曼编码左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。哈夫曼编码哈夫曼编码和Shannon-Fano编码的对比31

例

对cabcedeacacdeddaaabaababaaabbacdebaceada

进行Huffman编码。a16b7c6d6e511132401010101a0b100c101d110e111总比特数88，信源熵为86.601bitShannon-Fano编码：总比特数97bit哈夫曼编码和Shannon-Fano编码的对比32Shannon-Fano编码构造二叉树是自树根到树叶，很难保证最佳性。Huffman编码则是从树叶到树根，是最佳的Huffman需要知道信源的概率分布，这在实际中有时是比较困难的。采用半静态模型、自适应模型、markov模型，部分匹配预测模型等等解决这一问题。哈夫曼编码对比33例

单符号离散无记忆信源，哈夫曼的编码方法并不唯一。哈夫曼编码对比34方法一：合并后的新符号排在其它相同概率符号后面。哈夫曼编码对比35方法二：合并后的新符号排在其它相同概率符号前面。哈夫曼编码对比36平均码长：2.2码长方差：1.360100011x5x4x3x2x110001011x5x4x3x2x11平均码长：2.2码长方差：0.16编码效率相同。第二种编码方法的码长变化较小，比较接近于平均码长。4种不同的码长2种不同的码长哈夫曼编码对比37在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使短码得到充分利用。

D进制哈夫曼编码38共有K个符号，概率最小的R个符号码长最长K+B=D+m(D-1)满树注意B<D-1K-2=m(D-1)+D-2-B

D-2-B=

(K-2)mod(D-1)B个R个B=D-2-((K-2)mod(D-1))R=D-B=2+((K-2)mod(D-1))D进制哈夫曼编码39例：对如下单符号离散无记忆信源编三进制哈夫曼码。第一次取D-s=mod(8-2,3-1)+2=2个符号进行编码。D进制哈夫曼编码4041平均码长为信息率为编码效率为00001211x5x4x3x2x1221x6x8x7令离散无记忆信源如上。(a)求对U（即U1）的最佳二元码、平均码长和编码效率。(b)求对U2

（即U1U2）的最佳二元码、平均码长和编码效率。(c)求对U3（即U1U2U3）的最佳二元码、平均码长和编码效率。例题（U1U2U3）~a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.008（U1U2）的最佳二元码（U1U2）的最佳二元码（U1U2）的最佳二元码（U1U2）的最佳二元码平均码长和编码效率：（U1U2U3）的码字a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30011010011100011110111100111110010100001010100101100010111（U1U2U3）的最佳二元码平均码长：（U1U2U3）的最佳二元码编码效率：第四章离散信源无失真编码4.1离散无记忆信源的不等长编码4.2最佳不等长编码4.3汉字编码方法及其讨论4.4图像的信源编码4.5误码对信源译码的影响7879考虑一幅8.5×11.0英寸的图像，若每平方英寸包含300个像素，则整个图像将有大约8.4×106个像素。假定该图像是彩色的，每个像素包含3色，每种颜色用8比特的码字表示，可以算出该幅图像将需用大约2×108比特来表示。与其他图像格式相比，一帧高清晰度的电视图像包含有大约1.8×106个像素，一幅标准电视图像包含大约0.33×106个像素，一个高档电脑显示器包含1.2~3.1×106个像素。4.4图像的信源编码4.4.1图像消息的信息特征80图像消息的像素量很大，每一像素还有灰度等级、色度、饱和度等，这些参数相互之间通常具有较强的关联性，存在着很大的冗余度统计冗余例如空间冗余、时间冗余、信息熵冗余等，它们主要取决于图像信息的统计特性除此之外，还有结构冗余、知识冗余、视觉冗余等。正是由于图像消息中存在着这些冗余，才使图像编码有着可观的压缩潜力。4.4图像的信源编码4.4.1图像消息的信息特征81图像压缩编码方法主要有两类，即无失真编码与限失真编码。压缩比都是衡量其性能的一个重要指标。定义4.9设信源消息初始编码的代码组平均长度为Ls，经压缩编码后代码组的平均长度为Ld，则称

为压缩编码的压缩比。无失真编码的任务是寻求最佳编码，主要手段是压缩信源的冗余度。4.4图像的信源编码4.4.2压缩编码的主要方法82限失真编码的方法是用小的失真换取大的压缩比，它在图像的压缩编码中得到了快速发展。在允许的失真度下减少信息熵的方法又称为熵压缩法，其理论根据是率失真理论和香农第三定理。霍夫曼编码等方法均可应用于无失真图像编码。随着图像通信需求的快速增长，新的编码方法也不断涌现，如预测编码、变换编码、矢量量化、子带编码、分形编码、模型编码、小波编码等。国际标准化组织和国际电信联盟先后提出了静止图像编码标准JPEG、电视电话/会议电视的视频编码标准H.261和活动图像的编码标准MPEG-1、MPEG-2和MPEG-4。4.4图像的信源编码4.4.2压缩编码的主要方法83算术编码是香农编码方法在图像编码中的应用。是一种无失真的非分组信源编码，基本思想是将一定的精度数值作为序列的编码。它是从全序列出发，采用递推形式的连续编码。以二进制为例，它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据其概率映射为实数轴上[0,1)区间内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际编码输出。假设信源为二元平稳的马尔可夫信源，需要预先存储的不再是码字，而是由信源序列状态确定的一些参数，因而算术编码不需要传送像霍夫曼码表一类的编码表。4.4.3算术编码4.4图像的信源编码84算术编码的具体方法：对初始信源进行K重扩展，即

…xi,…,

xK,P(xK

)对应于P(xK

)，有一个累积分布函数F(xK

)。在区间[F(xK

)–P(xK

),F(xK

)]，可以找到一个二进制小数，由于对应于不同的P(xK

)，区间的小数值一定不同，故可构成单义可译码。在区间找位数最少的二进制小数，用小数点后的数作为编码。4.4.3算术编码4.4图像的信源编码85算术编码把信源X的任一给定序列和[0,1]的一个子区间联系在一起，该子区间的长度等于这个序列的概率。编码过程从第一个符号开始，逐个处理。随着处理符号数目的增加，同序列联系在一起的区间长度越来越小。随着区间的缩小，区间首尾二进制代码相同位数增多，这些二进制代码惟一确定了输入符号序列，并可以惟一译码。概率大的符号对应区间大，描述所需比特少。随着输入序列长度增加，平均编码所用比特数趋向信源熵。它利用了关联信息，使得编码效率得到提高。4.4.3算术编码4.4图像的信源编码86传真之类的二值图像只有1、0两个灰度级，若直接对其编码，则比特数等于像素数，编码效率较低。在空白较多时则可以采用跳跃空白编码，即把行分段，如把8、10或12个像素分为一段，全白段用“0”表示，其他段则用标识“1”加上段中像素的直接编码表示。游程编码是一种对相关性的信源较为有效的扩展符号集的变换方法。在二元序列中，连“0”段称为“0”游程，连“1”段称为“1”游程，其长度分别称为游程长度L(0)和L(1)。“0”游程和“1”游程总是交替出现。可以把任何二元序列变换成游程长度的序列，简称游程序列。这种变换是一一对应的，也就是可逆的，如二元序列“000101110010001……”可变换成游程序列“3113213……”。4.4.4游程编码4.4图像的信源编码87游程序列已是多元序列，各长度就可以按Huffman编码或其他方法处理以达到压缩码率的目的。因为游程长度的计数比较容易，得到游程长度后就可以从码表中找出码字输出，同时去数下一个游程长度，因此这种从二元序列转换成多元序列的方法，在实现时比较简单。在减弱原有序列符号间的相关性方面，采用游程变换也较为有效。当然，要对二元序列进行Huffman编码时，应先测定“0”游程长度和“1”游程长度的概率分布，或由二元序列的概率特性去计算各种游程长度的概率。4.4.4游程编码4.4图像的信源编码88针对一幅图像中可能存在着若干具有相同灰度等级甚至相同图像区域的这一特征，人们提出了轮廓编码的方法来提高编码效率。轮廓编码的要点：（1）记录边界线，定义具有同一灰度等特征的图像区域的边界线为等值线，即找出“轮廓”；（2）发现、跟踪等值线；（3）确定一条等值线的起始点；（4）对等值线进行描述，分别对灰度级、等值线的初始位置、方向序列（上、下，左、右）等进行编码。轮廓编码的方法适合灰度级较少的图像。4.4.5轮廓编码4.4图像的信源编码第四