Chap10图象压缩与编码课件

Chap10图象压缩与编码要点：信息量，熵，联合熵，率失真函数编码效率，冗余度，压缩比无失真编码，有失真编码霍夫曼编码行程编码预测编码DCT编码混合编码Chap10图象压缩与编码要点：信息量，熵，联合熵，率1图象压缩与编码数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。如一幅512x512的黑白图象的比特数为512x512x8=2,097,152bit=256k。再如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R、G、B三分量分别占8bit，总比特数为图象压缩与编码数字图象通常要求很大的比特数，这给图象2图象压缩与编码90x60x24x3x512x512x8bit=97,200M。如一张CD光盘可存600兆字节数据，这部电影光图象（还有声音）就需要160张CD光盘用来存储。

对图象数据进行压缩显得非常必要。本章讨论的问题：在满足一定条件下，能否减小图象bit数，以及用什么样的编码方法使之减少。图象压缩与编码90x60x24x3x512x3英文字母出现相对频率字母ABCDEFGHIJKLM百分比8.21.52.84.312.72.22.06.17.00.20.84.02.4字母NOPQRSTUVWXYZ百分比6.77.51.90.16.06.39.12.81.02.40.22.00.1英文字母出现相对频率字母百分比字母百分比4英文字母出现相对频率英文字母出现相对频率5图象编码—密码点击图片播放视频某个图形或物品也可以作为密码。图象编码—密码点击图片某个图形或物品也可以作为密码。6图象编码—密码虹膜与指纹。图象编码—密码虹膜与指纹。7图象压缩与编码1．图象数据压缩是可能的：一般原始图象中存在很大的冗余度。用户通常允许图象失真。当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。用户对原始图象的信号不全都感兴趣，可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。图象压缩与编码1．图象数据压缩是可能的：8图象压缩与编码2．原始图象越有规则，各象素之间的相关性越强，它可能压缩的数据就越多。值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。图象压缩与编码2．原始图象越有规则，各象素之间的相关性越强，9图象压缩与编码3．图象结构的性质，大体上可分为两大类，一类是具有一定图形特征的结构，另一类是具有一定概率统计特性的结构。基于不同的图象结构特性，应采用不同的压缩编码方法。图象压缩与编码3．图象结构的性质，大体上可分为两大类，一类是10图象压缩与编码4．全面评价一种编码方法的优劣，除了看它的编码效率、实时性和失真度以外，还要看它的设备复杂程度，是否经济与实用。常采用混合编码的方案，以求在性能和经济上取得折衷。

随着计算方法及VLSI的发展，使许多高效而又比较复杂的编码方法在工程上有实现的可能。图象压缩与编码4．全面评价一种编码方法的优劣，除了看它的编码11信源编码的基本概念图象数据压缩的目的是在满足一定图象质量条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为信源编码。信源编码可分为两大类，一类是无失真编码，另一类是有失真编码或称限失真编码。信源编码的基本概念图象数据压缩的目的是在满足一定图象12无失真编码

无失真编码又称信息保持编码或可逆的无误差编码。

信息量：从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为信息量。无失真编码无失真编码又称信息保持编码或可逆的无误差编13无失真编码

要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可以得到1bit信息量（二进制位）。这里共需5次，因此所需的信息量为。例无失真编码要辨识1到32中选定的某一个数，可先提问14无失真编码定义信息量：从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。熵：设信源符号表为s={s1,s2,…,

sq}，其概率分布为P(s)={p(s1),p(s2),…,p(sq)}，则信源的熵为无失真编码定义信息量：从N个数选定一个数s的概率为p15无失真编码s作为灰度，共q级，出现概率均等时，p(si)=1/q，当灰度只有两级时，即si=0,1，且0出现概率为p1，1出现概率为p2=1-p1

，其熵无失真编码s作为灰度，共q级，出现概率均等时，p(s16无失真编码当p1=1/2，p2=1-p1=1/2时，H(s)=1为最大值。如图所示。无失真编码当p1=1/2，p2=1-p1=1/17无失真编码熵的性质：（1）熵是一个非负数，即总有H(s)≥0。（2）当其中一个符号sj的出现概率p(sj)=1时，其余符号si(i≠j)的出现概率p(si)

=0，H(s)=0。（3）当各个si出现的概率相同时，则最大平均信息量为log2

q。（4）熵值总有H(s)≤log2

q。无失真编码熵的性质：18无失真编码(一)无失真编码定理

可以证明，在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度

L与信源的熵H(s)任意地接近，即L=H(s)+ε，其中ε为任意小的正数，但以H(s)为其下限，即L≥H(s)，这就是香农(Shannon)无干扰编码定理。

无失真编码(一)无失真编码定理19无失真编码(二)熵与相关性、冗余度的关系对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。

原始图象冗余度定义为：无失真编码(二)熵与相关性、冗余度的关系20无失真编码

将编码效率定义为：

冗余度接近于0，或编码效率接近于1的编码称为高效码。无失真编码将编码效率定义为：冗余度接近于0，21无失真编码若原始图象的平均比特率为n，编码后的平均比特率为nd，则压缩比C定义为：由Shannon定理，无失真编码最大可能的数据压缩比为：无失真编码若原始图象的平均比特率为n，编码后的平均比22无失真编码

独立信源的熵与马尔可夫信源的熵令q=2L，其中L等于自然二进制码的长度。可以证明，对于独立信源，等概率分布时，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能压缩。讨论（1）独立信源，又称无记忆信源，符号si的出现，与其他的符号无关。无失真编码独立信源的熵与马尔可夫信源的23无失真编码非等概率分布时的熵，一般有H1(s)<HM(s)=L，因而冗余度r=L/H1(s)-1>0，还有可能压缩。（2）有限马尔可夫(Markov)信源的熵又称有限记忆信源，它的统计特性要用转移概率或条件概率来描述。

m阶Markov信源，是指某个符号si出现的概率只与前面m个符号有关。无失真编码非等概率分布时的熵，一般有H1(s)<H24无失真编码

设s={s1,s2,…,sq}，则转移概率

p(si/si1,si2,…,sim)乃是前m个符号为si1,si2,…,sim时，第m+1个符号为si的概率。

信息量

I(si/si1,si2,…,sim)=-log2p(si/si1,si2,…,sim)无失真编码设s={s1,s2,…,sq}，则转移25无失真编码对符号表取平均的信息量

这是在给定序列si1,si2,…,sim的条件下，信源的条件熵。

无失真编码对符号表取平均的信息量这是在给定序26无失真编码

再考虑序列si1,si2,…,sim发生的概率，可将m阶Markov信源的熵定义为：无失真编码再考虑序列si1,si2,…,sim发27无失真编码

（四）高效的编码方法无干扰编码定理只指出存在一种无失真的编码，可使。它并没有指出具体的编码方法。下面介绍几种具体的编码方法。（1）Huffman码它是长度不均匀的，其平均长度最短的即时可译码。其要点是对经常出现的符无失真编码（四）高效的编码方法28英文字母出现相对频率字母ABCDEFGHIJKLM百分比8.21.52.84.312.72.22.06.17.00.20.84.02.4字母NOPQRSTUVWXYZ百分比6.77.51.90.16.06.39.12.81.02.40.22.00.1英文字母出现相对频率字母百分比字母百分比29英文字母出现相对频率英文字母出现相对频率30国际莫尔斯电码符号SymbolABCDEFGHIJKLMCode.--…-.-.-.....-.--.…....----.-.-..--SymbolNOPQRSTUVWXYZCode-.---.--.--.-.-.…-..-…-.---..--.----..Symbol0123456789Code-----.----..---…--….-…..-….--...---..----.Symbol.,?:;-/“Code.-.-.---..--..--..---…-.-.-.-…--..-..-..-.国际莫尔斯电码符号SymbolCodeSymbolCodeS31无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋予较长的码字，这样可使码的平均长度具有最小值，pi--si出现概率，li--对si编码的长度。无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋32无失真编码

信号源s={s1,s2,s3,s4,s5,s6}，其概率分布为p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman码。例方法：将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。无失真编码信号源s={s1,s2,s3,s433无失真编码方法：把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。重复上述做法，直到最后剩下两个概率为止。从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。无失真编码方法：34Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04Huffman编码例输入输入概率35Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman编码例输入输入概率第一步36Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman编码例输入输入概率第一步第二步37Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman编码例输入输入概率第一步第二步第三步38Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman编码例输入输入概率第一步第二步第三步第四步39Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman编码例输入输入概率第一步第二步第三步第四步0040Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman编码例输入输入概率第一步第二步第三步第四步0041Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman编码例输入输入概率第一步第二步第三步第四步0042Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman编码例输入输入概率第一步第二步第三步第四步0043Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman编码例输入输入概率第一步第二步第三步第四步0044Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman编码例输入输入概率第一步第二步第三步第四步0045Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011Huffman编码例输入输入概率第一步第二步第三步第四步0046无失真编码（2）B码

在某些应用中，编码器输入符号集合的概率分布服从乘幂律：pk=k-r,k=1,2,…,q。r为正常数，则用B码，它接近于最佳编码。B码是一种非等长码，由两部分组成，一部分叫“延续比特”，一部分叫“信息比特”。延续比特的作用是标注一个码字究竟延续多长，信息比特的作用是表示不同的信息符号。无失真编码（2）B码47无失真编码方法：将信源符号按出现概率从大到小排序，然后按B1码的前后顺序分别赋予相应符号，便得到各符号的B1码。其中信息码是按二进制的长度及数的顺序排列的，即0，1，00，01，10，11，000，001，…。延续码C是在编码过程中确定的，可将C=0赋予前一个码字，将C=1赋予后一个码字，再将C=0赋予下一个码字。无失真编码方法：48无失真编码方法：例如，编码器输入符号序列为s4s1s5s2…,则B1码为：

0001，10，0100，11，…或者1011，00，1110，01，…延续码改变，表示前一个码字结束，后一个码字开始。

B1码优点：编码方法简单，容易实现。无失真编码方法：49无失真编码（3）移位码S2对具有单调减小概率的输入信号相当有效的非等长码。

S2码由2bit长的码字组成，总共包含四个不同的码字：C1=00，C2=01，C3=10，C4=11，C4的个数用来表示该符号的序数超过3的次数。符号编码：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3，…这种编码方法更简单。无失真编码（3）移位码S250几种编码比较输入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04几种编码比较输入概率51几种编码比较输入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14几种编码比较输入概率霍夫曼码52几种编码比较输入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14几种编码比较输入概率霍夫曼码B1码53几种编码比较输入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14几种编码比较输入概率霍夫曼码B1码S2码54几种编码比较输入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14自然码00000101001110010130.7130.40212.14几种编码比较输入概率霍夫曼码B1码S2码自然码55限失真编码严格的无失真编码的压缩比一般是不大的。编码效率的提高往往要以采用较复杂的编码方法为代价；另一方面，用户通常允许图象有一定的失真，这为图象数据压缩提供了较大的可能性，因此人们非常注意限失真编码问题。在给定失真条件下，信源编码所能达到的压缩率的极限码率，称为率失真函数，R(D)

，

D为失真上限。限失真编码严格的无失真编码的压缩比一般是不大的。编码56限失真编码

R(0)≤H(Y)，收到的信号序列不存在相关性时，等号成立。D↑，R(D)↓。允许失真度D越小，则所需率失真函数值R(D)就越大，要求信源编码效率也越高。限失真编码R(0)≤H(Y)，收到的信号序列不存在57p.436p.43658图象编码模型映射变换器量化器编码器原始图象码字图象压缩编码的一般框图图象编码模型映射量化器编码器原始图象码字图象压缩编码的一般框59图象编码模型

映射变换：将输入数据从象素域变换到另一个域，在变换域中则能以较少的比特数对图象进行量化编码。对映射变换器的要求，要从数据压缩的有效性、保真度和经济实用方面考虑，应该是高度去相关的、可逆的、重现的均方误差最小、易于实现的。图象编码模型映射变换：将输入数据从象素域变换到另一个60图象编码模型（1）行程编码把沿着扫描行的象素序列x1,x2,…,xN映射为行程序列(g1,l1),

(g2,l2),…,(gk,lk)。

gi—灰度级li—gi的行程长度因为象素序列可以根据行程序列来重建，故行程映射变换是可逆的。因它包含灰度鉴别和行程计数，故它是非线性的。例图象编码模型（1）行程编码例61图象编码模型（2）差分映射编码矩阵形式：例图象编码模型（2）差分映射编码例62图象编码模型或矩阵A是非奇异的，因而这种映射变换是可逆的。差分编码是一种最简单的线性预测编码。图象编码模型或矩阵A是非奇异的，因而这种映射63图象编码模型（3）正交变换编码各种正交变换都是可逆的线性变换。应用正交变换的图象编码常称为变换编码。正交变换有傅立叶变换(FFT)、余弦变换(DCT)、沃尔什-哈达玛变换(WHT)、小波变换(DWT)等。例图象编码模型（3）正交变换编码例64Chap10图象压缩与编码要点：信息量，熵，联合熵，率失真函数编码效率，冗余度，压缩比无失真编码，有失真编码霍夫曼编码行程编码预测编码DCT编码混合编码Chap10图象压缩与编码要点：信息量，熵，联合熵，率65图象压缩与编码数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。如一幅512x512的黑白图象的比特数为512x512x8=2,097,152bit=256k。再如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R、G、B三分量分别占8bit，总比特数为图象压缩与编码数字图象通常要求很大的比特数，这给图象66图象压缩与编码90x60x24x3x512x512x8bit=97,200M。如一张CD光盘可存600兆字节数据，这部电影光图象（还有声音）就需要160张CD光盘用来存储。

对图象数据进行压缩显得非常必要。本章讨论的问题：在满足一定条件下，能否减小图象bit数，以及用什么样的编码方法使之减少。图象压缩与编码90x60x24x3x512x67英文字母出现相对频率字母ABCDEFGHIJKLM百分比8.21.52.84.312.72.22.06.17.00.20.84.02.4字母NOPQRSTUVWXYZ百分比6.77.51.90.16.06.39.12.81.02.40.22.00.1英文字母出现相对频率字母百分比字母百分比68英文字母出现相对频率英文字母出现相对频率69图象编码—密码点击图片播放视频某个图形或物品也可以作为密码。图象编码—密码点击图片某个图形或物品也可以作为密码。70图象编码—密码虹膜与指纹。图象编码—密码虹膜与指纹。71图象压缩与编码1．图象数据压缩是可能的：一般原始图象中存在很大的冗余度。用户通常允许图象失真。当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。用户对原始图象的信号不全都感兴趣，可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。图象压缩与编码1．图象数据压缩是可能的：72图象压缩与编码2．原始图象越有规则，各象素之间的相关性越强，它可能压缩的数据就越多。值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。图象压缩与编码2．原始图象越有规则，各象素之间的相关性越强，73图象压缩与编码3．图象结构的性质，大体上可分为两大类，一类是具有一定图形特征的结构，另一类是具有一定概率统计特性的结构。基于不同的图象结构特性，应采用不同的压缩编码方法。图象压缩与编码3．图象结构的性质，大体上可分为两大类，一类是74图象压缩与编码4．全面评价一种编码方法的优劣，除了看它的编码效率、实时性和失真度以外，还要看它的设备复杂程度，是否经济与实用。常采用混合编码的方案，以求在性能和经济上取得折衷。

随着计算方法及VLSI的发展，使许多高效而又比较复杂的编码方法在工程上有实现的可能。图象压缩与编码4．全面评价一种编码方法的优劣，除了看它的编码75信源编码的基本概念图象数据压缩的目的是在满足一定图象质量条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为信源编码。信源编码可分为两大类，一类是无失真编码，另一类是有失真编码或称限失真编码。信源编码的基本概念图象数据压缩的目的是在满足一定图象76无失真编码

无失真编码又称信息保持编码或可逆的无误差编码。

信息量：从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为信息量。无失真编码无失真编码又称信息保持编码或可逆的无误差编77无失真编码

要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可以得到1bit信息量（二进制位）。这里共需5次，因此所需的信息量为。例无失真编码要辨识1到32中选定的某一个数，可先提问78无失真编码定义信息量：从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。熵：设信源符号表为s={s1,s2,…,

sq}，其概率分布为P(s)={p(s1),p(s2),…,p(sq)}，则信源的熵为无失真编码定义信息量：从N个数选定一个数s的概率为p79无失真编码s作为灰度，共q级，出现概率均等时，p(si)=1/q，当灰度只有两级时，即si=0,1，且0出现概率为p1，1出现概率为p2=1-p1

，其熵无失真编码s作为灰度，共q级，出现概率均等时，p(s80无失真编码当p1=1/2，p2=1-p1=1/2时，H(s)=1为最大值。如图所示。无失真编码当p1=1/2，p2=1-p1=1/81无失真编码熵的性质：（1）熵是一个非负数，即总有H(s)≥0。（2）当其中一个符号sj的出现概率p(sj)=1时，其余符号si(i≠j)的出现概率p(si)

=0，H(s)=0。（3）当各个si出现的概率相同时，则最大平均信息量为log2

q。（4）熵值总有H(s)≤log2

q。无失真编码熵的性质：82无失真编码(一)无失真编码定理

可以证明，在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度

L与信源的熵H(s)任意地接近，即L=H(s)+ε，其中ε为任意小的正数，但以H(s)为其下限，即L≥H(s)，这就是香农(Shannon)无干扰编码定理。

无失真编码(一)无失真编码定理83无失真编码(二)熵与相关性、冗余度的关系对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。

原始图象冗余度定义为：无失真编码(二)熵与相关性、冗余度的关系84无失真编码

将编码效率定义为：

冗余度接近于0，或编码效率接近于1的编码称为高效码。无失真编码将编码效率定义为：冗余度接近于0，85无失真编码若原始图象的平均比特率为n，编码后的平均比特率为nd，则压缩比C定义为：由Shannon定理，无失真编码最大可能的数据压缩比为：无失真编码若原始图象的平均比特率为n，编码后的平均比86无失真编码

独立信源的熵与马尔可夫信源的熵令q=2L，其中L等于自然二进制码的长度。可以证明，对于独立信源，等概率分布时，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能压缩。讨论（1）独立信源，又称无记忆信源，符号si的出现，与其他的符号无关。无失真编码独立信源的熵与马尔可夫信源的87无失真编码非等概率分布时的熵，一般有H1(s)<HM(s)=L，因而冗余度r=L/H1(s)-1>0，还有可能压缩。（2）有限马尔可夫(Markov)信源的熵又称有限记忆信源，它的统计特性要用转移概率或条件概率来描述。

m阶Markov信源，是指某个符号si出现的概率只与前面m个符号有关。无失真编码非等概率分布时的熵，一般有H1(s)<H88无失真编码

设s={s1,s2,…,sq}，则转移概率

p(si/si1,si2,…,sim)乃是前m个符号为si1,si2,…,sim时，第m+1个符号为si的概率。

信息量

I(si/si1,si2,…,sim)=-log2p(si/si1,si2,…,sim)无失真编码设s={s1,s2,…,sq}，则转移89无失真编码对符号表取平均的信息量

这是在给定序列si1,si2,…,sim的条件下，信源的条件熵。

无失真编码对符号表取平均的信息量这是在给定序90无失真编码

再考虑序列si1,si2,…,sim发生的概率，可将m阶Markov信源的熵定义为：无失真编码再考虑序列si1,si2,…,sim发91无失真编码

（四）高效的编码方法无干扰编码定理只指出存在一种无失真的编码，可使。它并没有指出具体的编码方法。下面介绍几种具体的编码方法。（1）Huffman码它是长度不均匀的，其平均长度最短的即时可译码。其要点是对经常出现的符无失真编码（四）高效的编码方法92英文字母出现相对频率字母ABCDEFGHIJKLM百分比8.21.52.84.312.72.22.06.17.00.20.84.02.4字母NOPQRSTUVWXYZ百分比6.77.51.90.16.06.39.12.81.02.40.22.00.1英文字母出现相对频率字母百分比字母百分比93英文字母出现相对频率英文字母出现相对频率94国际莫尔斯电码符号SymbolABCDEFGHIJKLMCode.--…-.-.-.....-.--.…....----.-.-..--SymbolNOPQRSTUVWXYZCode-.---.--.--.-.-.…-..-…-.---..--.----..Symbol0123456789Code-----.----..---…--….-…..-….--...---..----.Symbol.,?:;-/“Code.-.-.---..--..--..---…-.-.-.-…--..-..-..-.国际莫尔斯电码符号SymbolCodeSymbolCodeS95无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋予较长的码字，这样可使码的平均长度具有最小值，pi--si出现概率，li--对si编码的长度。无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋96无失真编码

信号源s={s1,s2,s3,s4,s5,s6}，其概率分布为p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman码。例方法：将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。无失真编码信号源s={s1,s2,s3,s497无失真编码方法：把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。重复上述做法，直到最后剩下两个概率为止。从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。无失真编码方法：98Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04Huffman编码例输入输入概率99Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman编码例输入输入概率第一步100Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman编码例输入输入概率第一步第二步101Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman编码例输入输入概率第一步第二步第三步102Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman编码例输入输入概率第一步第二步第三步第四步103Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman编码例输入输入概率第一步第二步第三步第四步00104Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman编码例输入输入概率第一步第二步第三步第四步00105Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman编码例输入输入概率第一步第二步第三步第四步00106Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman编码例输入输入概率第一步第二步第三步第四步00107Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman编码例输入输入概率第一步第二步第三步第四步00108Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman编码例输入输入概率第一步第二步第三步第四步00109Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011Huffman编码例输入输入概率第一步第二步第三步第四步00110无失真编码（2）B码

在某些应用中，编码器输入符号集合的概率分布服从乘幂律：pk=k-r,k=1,2,…,q。r为正常数，则用B码，它接近于最佳编码。B码是一种非等长码，由两部分组成，一部分叫“延续比特”，一部分叫“信息比特”。延续比特的作用是标注一个码字究竟延续多长，信息比特的作用是表示不同的信息符号。无失真编码（2）B码111无失真编码方法：将信源符号按出现概率从大到小排序，然后按B1码的前后顺序分别赋予相应符号，便得到各符号的B1码。其中信息码是按二进制的长度及数的顺序排列的，即0，1，00，01，10，11，000，001，…。延续码C是在编码过程中确定的，可将C=0赋予前一个码字，将C=1赋予后一个码字，再将C=0赋予下一个码字。无失真编码方法：112无失真编码方法：例如，编码器输入符号序列为s4s1s5s2…,则B1码为：

0001，10，0100，11，…或者1011，00，1110，01，…延续码改变，表示前一个码字结束，后一个码字开始。

B1码优点：编码方法简单，容易实现。无失真编码方法：113无失真编码（3）移位码S2对具有单调减小概率的输入信号相当有效的非等长码。

S2码由2bit长的码字组成，总共包含四个不同的码字：C1=00，C2=01，C3=10，C4=11，C4的个数用来表示该符号的序数超过3的次数。符号编码：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3，…这种编码方法更简单。无失真编码（3）移位码S2114几种编码比较输入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.06