第5章 信源编码2.ppt

1,信源编码（主要内容）,信源编码定理 信源编码概念 香农第一定理（变长编码） 香农第三定理 信源编码方法 离散信源编码 连续信源编码* 相关信源编码* 变换编码*,2,特点： 在符号序列长度L不很大时，能达到较高的编码效率 完全无失真 要求： 变长码要满足唯一可译码条件，则它必须是非奇异码，而且任意有限长L次扩展码也应该是非奇异码 为了能够即时译码，变长码还必须是即时码变长编码,3,1、克拉夫特不等式,信源符号数、码符号数和码字长度之间应满足什么条件，才能构成即时码？,4,2、麦克米伦不等式,将克拉夫特不等式推广到唯一可译码的情况 定理 在前一定理所给定的条件下，唯一可译码存在的充要条件是,5,说明,如果码字长度和码符号数满足克拉夫特（或麦克米伦）不等式，则一定可以构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码） 但是该定理并不能作为判断一种码是否为即时码（或唯一可译码）的依据 例如：码中，有两个码字长度相同，则这两个码字无论是否相同，都可能使不等式成立但是，两个码字相同时显然不可能是唯一可译码6,3、平均码长,定义 设信源 编码后的码字分别为W1 ，W2，…，Wn，相应的码长分别为k1，k2，…，kn。

因为是唯一可译码，信源符号xi和码字Wi一一对应，则平均码长为,7,,4、信息传输率与信息传输速率,8,变长无失真信源编码定理,即香农第一定理 定理 设离散无记忆信源为,9,,,变长无失真信源编码定理（续）,10,,变长无失真信源编码定理－理解,11,推广到普通信源,变长无失真信源编码定理可以推广到平稳遍历的有记忆信源，一般离散信源或马尔可夫信源，有 其中，H∞为有记忆信源的极限熵 定长编码作为变长编码的特例，可统一到香农第一定理之中12,变长编码的编码信息率R’,定义变长编码的编码信息率为 它表示编码后平均每个信源符号能载荷的最大信息量 香农第一定理可表述为： 若H(X)≤R’H(X)+ε，就存在唯一可译的变长编码 若R’H(X)，则不存在唯一可译的变长编码不能实现无失真的信源编码13,信息传输率R,从信道角度看，信道的信息传输率,14,,编码效率和剩余度,定义码的剩余度为,,15,,,变长编码举例,16,,变长编码举例—续,17,变长编码举例—续,18,变长编码举例—续,用同样方法可进一步对信源X的三次和四次扩展信源进行编码，并求出其编码效率为： η1=0.811比特/二元码符号 η2=0.961比特/二元码符号 η3=0.985比特/二元码符号 η4=0.991比特/二元码符号 对于同一信源，要求编码效率都达到96％，比较 变长码只需对二次扩展信源（L = 2）进行编码； 而等长码则要求L大于4.13X107 . 变长码编码效率更高，L不需很大就可以达到比较高的编码效率，而且可实现无失真编码。

19,小结,介绍了变长码基本特征和平均码长的概念； 通过克拉夫特不等式和麦克米伦不等式，给出了构成即时码和唯一可译码时，信源符号数和码字长度之间应满足的条件； 讨论了香农第一定理：变长编码定理；,20,信源编码（主要内容）,信源编码定理 信源编码概念 香农第一定理 香农第三定理 信源编码方法 离散信源编码 连续信源编码* 相关信源编码* 变换编码*,21,,,,,,,,,限失真信源编码定理,22,对信源编码定理的统一理解,定长信源无失真编码定理 变长信源无失真编码定理（香农第一定理） 保真度准则下的信源编码定理（香农第三定理） 从编码信息率的角度，当 时，则信源编码无失真或失真可控23,信源编码（主要内容）,信源编码定理 信源编码概念 香农第一定理 香农第三定理 信源编码方法 离散信源编码 连续信源编码 相关信源编码 变换编码,24,常见的方法： 香农编码 费诺编码 霍夫曼编码 游程编码 冗余位编码,,变长码的编码方法,25,1、香农编码,26,,香农编码－举例,27,香农编码－举例（续）,28,,香农编码－举例（续）,由上表可以看出，一共有5个三位的代码组，各代码组之间至少有一位数字不相同，故是唯一可译码。

还可以判断出，这7个代码组都属于即时码 平均码长、信息传输率、编码信息率和编码效率,29,,2、霍夫曼编码-方法,30,,霍夫曼编码－举例,31,,,霍夫曼编码－举例（续）,该霍夫曼码的平均码长 从编码表可以看出，霍夫曼是即时码，从右图的码树中也可以清楚看出32,,霍夫曼编码并不唯一,霍夫曼编码方法非唯一，原因： 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的； 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序时，其位置放置次序可以任意33,,,另一种霍夫曼编码,合并后的概率与其它信源符号的概率相同时，改变这两者在缩减信源中的排序，可以得到另一种霍夫曼编码34,另一种霍夫曼编码（续）,该霍夫曼码的平均码长 编码效率与前一种霍夫曼码的效率相同 但后一种编码的码长方差 方差比第一种方法小，即码长变化小，简单，易实现故在霍夫曼编码过程中，对缩减信源符号以概率重新排列时，应使合并符号尽量靠前，可使合并符号重复编码次数减少，使短码得到充分利用35,r元霍夫曼码,二进制霍夫曼码的编码方法可以很容易推广到r进制的情况只是编码过程中构成缩减信源时，每次都是将r个概率最小的符号合并，并分别用0, 1, …, (r-1)码符号表示。

例 设有离散无记忆信源 码符号集X＝(0,1,2)，试构造一种三进制霍夫曼码36,,,,r元霍夫曼码－举例,编码过程见下表，其中信源s9是增补的，令其概率为零.,37,,,,r元霍夫曼码－举例（续）,,r3元霍夫曼编码,38,,霍夫曼编码－总结,霍夫曼编码是用概率匹配方法进行的信源编码，它有两个明显特点： 1、编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码； 2、每次缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码39,,3、费诺编码,40,,,,费诺编码－举例,41,,费诺编码－举例（续）,42,4、游程编码与游程变换,前面三种方法针对无记忆信源，对于有记忆信源的编码效率不高，一般采用其它编码如：游程编码 二元序列：…000101110010001… “0”游程、“1”游程；游程长度L(0)、L(1) 多元序列/游程长度序列：…31132131… 游程变换规定游程序列从“0”开始，是可逆变换它减弱了二元序列的相关性对变换后的多元序列可采用其它编码方法，比如：哈夫曼编码 多元序列也可以变换成游程序列，但是需要增加标志位，可能会抵消压缩编码得到的好处，意义不大。

43,游程序列的概率特性,若二元序列的概率特性已知，可计算出游程序列的概率特性 假设二元序列为独立序列，则 0游程长度概率：p[L(0)]= p0 L(0)-1 p1 ; 0游程长度的熵：H[L(0)]=H(p0 )/ p1 ; 0游程序列的平均长度：l0=E[L(0)]=1/ p1 p[L(1)]= p1 L(1)-1 p0 ; H[L(1)]=H(p0 )/ p0 ; l1=E[L(1)]=1/ p0 p0和p1分别为二元序列中 “0”和“1”的概率 H(X) = { H[L(0)]+ H[L(1)] } / (l0+l1) = H(p0 ) = H(p1 ),44,0/ 1游程长度的概率：p[L(0)]、 p[L(1)],45,平均游程长度：E[L(0)]、 E[L(1)],46,0/ 1游程长度的熵：H[L(0)]/ H[L(1)],47,原二元序列的熵H(X),0游程序列的熵与1游程序列的熵之和除以它们的平均游程长度之和 H(X) = { H[L(0)]+ H[L(1)] } / (l0+l1) = { H(p0 ) /p1 + H(p0 ) /p0 } / (1/ p1 +1/ p0 ) = H(p0 ) = H(p1 ) 游程变换后符号熵没有变。

当0游程和1游程的编码效率都很高时，采用游程编码的效率也会高48,相关性二元序列的游程变换,若原二元序列是二阶马氏链，由它变换而来的游程序列将也是独立序列 0游程：10X； 1游程：01X 对于高阶马氏链，若阶数大于2，经变换的游程序列将不再是独立序列 如三阶马氏链：Y10X→一阶马氏链 一般k阶马氏链，由之变换而来的游程序列将为k-2阶马氏链 通过游程变换可有效的解除或减弱二元序列的相关性，再对游程长度进行编码可达到较高的编码效率49,游程长度与码字之间的 码表,取适当值n，游程长度为1, 2, …, 2n-1, 2n，所有大于2n者，都按2n处理 所有长度大于等于2n的游程，只有一个码字C，需要按右表进一步区分 当游程长度大于或等于2n+1时，需要两个或两个以上的C 概率小，码字长 0游程和1游程应分别编码，建立各自的码字和码表码字可重复， C必须不同如： C0 或 C1,50,冗余位编码（Lynch-Davission）,冗余位：信源序列中不携带信息的符号，除了符号数目或所占时长外，可不必传送 语音中的话语间歇、图像的单一背景部分 去掉部分冗余信息可以提高通信效率 设有多元信源序列：x 为信息位；y 冗余位 x1 , x2 ,…xm1 ,y,y,…,y, xm1+1 , xm1+2 ,…, xm2 ,y,y,… 可用下面两个序列来代替： 冗余位序列：111,…,100,…,000111,…,111000 信息位序列：x1 , x2 ,…xm1 , xm1+1 , xm1+2 ,…, xm2 , …,51,冗余位编码思路,多元信源序列分解：一个二元序列和一个缩短了的多元序列。

对两个序列分别编码，有效压缩信源 如：对二元序列进行游程编码；对多元序列直接采用哈夫曼编码 要求同时传送两个序列，才能在接收端实时恢复出原来的多元信源序列 实际应用有困难，通常采用分帧传送的方式52,分帧传送冗余位序列：L-D编码,在冗余位序列中取N个符号作为一帧，编成一个码字，其后就把本帧中的信息位按序排列，再取下一帧作同样处理在接收端根据这些码字和信息序列进行译码 每个码字中含有：信息位的数量Q和位置信息T,53,L-D编码的译码过程,收端收到Q和T后，如下译码：,54,编码Q和T,Q可以取0到N的各种值，共N+1种，故,55,例：对一冗余位序列编L-D码,一冗余位序列：001000000010000，N=15 这里Q=2，n1=3，n2=11，则,56,Q=2和T=47的译码过程,收端收到Q=2和T=47后，如下译码：,57,Q=2和T=47的译码过程-续,58,对例题的说明,当Q为0或N时，相当于全0或全1序列，此时T值为0，在编码时只需编Q值，对于N=15，得0000或1111 L-D编码与哈夫曼码不同，不需要已知概率特性也就是编成的码字与概率特性无关，而与一帧内的信息位的数目有关，即码字长度与Q有关。

59,码字长度与Q的关系,概率未知，无法计算熵，也无法计算编码效率，一般只能用压缩率来表达编码增益 当Q接近N/2时，L-D编码是无效的；当Q接近0或N时，可得很小的压缩率，N很大时更有效60,编码方法小结,介绍了几种变长码的编码方法： 香农编码、哈夫曼编码和费诺编码 游程编码和冗余位编码 变长码的缺点： 1.高概率符号和低概率符号出现的不均匀与信源符号恒速输出的矛盾信道可能无信息可送，或信息溢出而丢失需要很大的缓存） 2.差错的扩散因为它采用异前置码来分解码字，一旦传送中出现误码，则某个码字的前置部分可能成为另一个码字，因而错译为另一个符号需要采用差错控制）,61,本章小结,介绍了变长码基本特征和平均码长的概念； 通过克拉夫特不等式和麦克米伦不等式，给出了为构成唯一可译码，信源符号数和码字长度之间应满足的条件； 给出了一种唯一可译码的判别准则； 讨论了香农第一定理：变长编码定理； 学习。