信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考试知识点复习

1、第五章无失真信源编码定理与编码5. 1. 1信源编码和码的类型1.信源编码设信源吕八八码符号集X三肋7：“*英儿称为码符号<码兀几将 儿八W, m （不严：兀）工U W X（I = 1*2，q、或4 =（$,一）%弓将厲！狀=a严* > r X这种一一对应变换称为僖源编瓯 M称为码字，长度/为码氐 叭的集合称为分组科*r元码。2码的类型若码符号集中符号数r=2称为二元码，r=3称为三元码，若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。若每个码符号Xi X的传输时间都相同则称为同价码，否则称为非同价码。若分组码的

2、任意一串有限长的码符号只能被唯一地译成所对应的信源符号 序列则称为唯一可译码，否则称为非唯一可译码。若分组码中，没有任何完整的码字是其他码字的前缀，则称为即时码（又称 非延长码或前缀条件码），否则称为延长码。本章主要研究的是同价唯一可译码。5. 1. 2即时码及其树图构造法即时码（非延长码或前缀条件码）是唯一可译码的一类子码。即时码可用树图法来构造。构造的要点是:（1）最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头为节点。(2)从每个节点再伸出r枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。一直继续进行，直至都不能伸枝为止。每个节点所伸出的树枝标上码符号，从根

3、出发到终端节点所走路径对应的码符号序列则为终端节点的码字。即时码可用树图法来进行编码和译码。从树图可知，即时码可以即时进行译码。当码字长度给定，即时码不是唯一的。可以认为等长唯一可译码是即时码的一类子码。5. 1. 3唯一可译码存在的充要条件(1)对含有q个信源符号的信源用含r个符号的码符号集进行编码，各码字的码长为li, 12,，Iq的唯一可译码存在的充要条件是，满足Kraft不等式£八篷1I 一 ！(2)苦宦一组码氏为A的唯一可译码，则一定存框具有«同码検的即时码. 所rb Kraft不等式也是即时码存在的充要条件"5. 1. 4 唯一可译码的判断法唯一可译码

4、的判断步骤:首先,观察是否是非奇异码。若是奇异码则一定不是唯一可译码。其次,计算是否满足Kraft不等式。若不满足一定不是唯一可译码。再次,将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是唯一可译码。或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾随后缀集合F,观察F中有没有包含任一码字，若无则为唯一可译码；若有则一 定不是唯一可译码。上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是 否是唯一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。设离散无记忆信源5. 1. 5渐近等分割性和£典型序列扎.其

5、侑息靖为H(S).它的N次扩展信源为：具中於-小讥. a,=(环屍J ) (I = 1 .氛% ! 肾i .2叩*b渐近等分性(AEP)若M机序列S屈是服从彼此统计独立且等同分布P(八则有-=ioKPG)=专际弘宀心 以既車收a于H(s>2. 型序列和E典型序列*E典«序列N民|的序列£ 5%) 6 S仁对于任意小的正数皿足如j则称此V艮序列耳为£典型序列.To炉J-H头T迸笄-Jg <e则称此N长序列a i为非£典型序列。(2) £典型序列集护中所有百典別序列6的樂合为E典型序列執以以表轧歹中所有性典型序列。的 集合为井卡典型浮列

6、集以FL表示.削HfS)' <£= fa,:并11有烷、门6、=0 G、玄e*型序列篥的特性若a.-（片几则有2 如心i < P3J <2 fdF当N足够大时则右HG ）> 1=5P（心）M 5站为任意小的lEft）I.氐II <护"血搖中III G料（I衷示集合仏 中£典呦坪列的亍（I）t典型呼列的总数占信源呼列的比m为a 2內畅 T.5. 1. 6无失真等长信源编码定理离散信源S,其信息熵为HX,用含r个字母的码符号集对N长信源符号序列进行等长编码，若满足l/N > Hx/log叶£ （ £ &g

7、t;0的任意小数），则当N足够大时,可实现几乎无失真编码。其中，当S为离散无记忆信源时，HX=H（S）;当S为离散平稳信源，HX为信源的极限熵;当S为马尔可夫信源，HX为马尔可夫信源的极限熵。5. 1. 7无失真变长信源编码定理（香农第一定理）用含r个字母的码符号集对N长信源符号序列进行变长编码，总能找到一种无失真的唯一可译码，使信源符号所需平均码长满足:<n«»无记忆信源（Z）离»平稳信源（3）尔可夬信源N =时.有H.1 匸、.HiS）1 H（5乱弘）甞、1 H（邑$注心 1_亍卞_両 .VJ f T 1 L H .1而TyAw豪阪怦+1"二斡

8、logr- iQBr离融无记忆信源离»平稳（和马尔町夫e源 其中上人=工尸八 而儿是信源斥列所对应的W字艮度.LJ4 !所UI= /-I > PG 'Jfi又”.为离»平稳信（或岛氏信源的极m爛n5. 1. 8无失真信源编码定理和数据压缩1.无失真数据压缩的极限值无失真信源编码定理（无论等长码还是变长码）在理论上指出离散信源的信 息熵是信源无失真数据压缩的极限值。在实际应用上，变长码与等长码相比较，当N不很大时，变长码能更快地 接近这极限值，更快地获得较好的压缩效果。无失真的信源数据压缩是实现减少或消除信源的剩余度，所以在工程实用中 又称为冗余度压缩编码。通过

9、无失真数据压缩编码可使信道的信息传输率提高, （提高了信息传输系统的有效性）达到信源与信道的匹配，使信道得到充分利用。2编码后信源信息率、码率和编码效率（1）编码后信源信息率信源编码后平均每个信源符号能载荷的最大信息量，即(2)码率信源编码后平均梅个码元携带的信fitt即编码忘借道的信fi传输*-即 R =严(等长码的R W务疋 比持'码符号当N = 1离散无记忆信源.有K =比待/码符号(3)编硏效率衡«各种编码距扱限压締俺的W况.即衡各种编码的优劣耳弋 氏二器-器(其中工弋 为各W编码的平均码长)当N - 1离敝无记忆信源有 q -=号92码的啊余码的剩余度=1 一7 当

10、广一2即二元编码时.有Rw臥注意可是无单5. 1. 9 最佳二元码平均码长为最短的即时码称为最佳码(又称紧致码)。对于某个给定分布的离散信源，存在一个二元最佳码，此码满足如下性质:(1) 概率大的信源符号所对应的码长不大于概率小的信源符号所对应的码 长。(2) 两个最小概率的信源符号所对应的码字必具有相同码长。(3) 两个最小概率的信源符号所对应的码字的差别，必与最后一位码元不同。-对每一种信源编码需掌握其编码方法及其平均码长的极限值范围。-所讨论的信源编码方法都是针对离散无记忆信源的。对于离散平稳信源只 需将。N重概率空间看成无记忆信源进行编码即可。对于马尔可夫信源，可考虑不同状态下进行信源

11、符号编码，压缩效果可得 到改善。5. 1. 10 香农(Shannon)码1 .编码方法(1)确定信源符号所对应的码怏其中符号代表不小巴的整数2.4)依化仃=1 汉* Q人fflW图法构造厂元树，町得厂元即时码匚 平均码长的®«5.1. 11 费诺(Fano)码1.编码方法(r元费诺码)将信源符号以概率递减的次序排列。(2) 将它们划分成r个组，使每组的概率和接近相同，并各赋予一位码元。(3) 再将每一组按同样原则划分，重复步骤(2)，直至各组不再可分为止。这 样，所对应的码符号序列则为所编码字。2.平均码长的极限5. 1. 12 霍夫曼(Huffman)码1 .编码方法(

12、r元霍夫曼码)(1)信源符号个数q必须满足q=(r-1) 0 +r( 0表示缩减次数)。不满足时，设一些概率为零的虚假符号，使其满足。当r=2时，任意整数q 定满足。将信源符号以概率递减的次序排列。(3)给r个概率最小的信源符号各分配一位码元，并将它们合并成一个新符号，r个最小的概率之和作为新符号的概率，从而得到只包含q-(r-1)个信源符号 的新缩减信源S1。(4) 把缩减信源S1重新按概率递减的次序排列(若此时把所得的新符号尽可能 排列在靠前位置上，所得码的方差最小)，重复步骤(3)，得只含q-2(r-1)个信源符 号的缩减信源S2。（5）以此继续，直至缩减信源只剩r个符号为止。然后，从最

13、后一级缩减信源 起，依编码路径向前返回，所得码符号序列就是所对应的码字。2.平均码长的极限信源给定情况下，霍夫曼码是最佳即时码。其各码字的码长是唯一的，但具 体码字不是唯一的。平均码长的界限为5. 1. 13 香农-费诺-埃利斯码1 .编码方法（1）将信源符号X=a 1，32，aq）依次排列（不要求以概率大小排序）。计出丼借符号的正累积分摘函数值.FS =丈PG（3）确定各信源符号所对应码字的码氏；（恥求出LR血）S的二进瓠 用这小后心门位二进数作为符号尙的码字*（ "h 我示取/位便小于等于左的数.）2平均玛长的®限此码为二元即时码*其冇亠I乓L（O < HCS）

14、+35. 1. 14 游程编码和MH编码1.游程编码（RLC）游程编码是一种针对相关信源的有效编码方法，尤其适用于二元相关信源。有时实际工程技术中常将游程编码和其他编码方法混合使用，能获得更好的压缩 效果。信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串, 称这种字符串的长度为游程，又称游长。游程编码就是将信源字符序列映射成串 的字符、串的长度和串的位置的标志序列。(1)二元信源游程编码编码方法: 将一维二元序列中，分出一段一段的“ 0”符号串和“ 1”符号串，对应段 中的符号个数标记为“ 0”游程长度L(0)和“1”游程长度L(1) 0 对串的长度即游程长度用自然数标记，并一

15、般规定信源序列从“0”游程 起始，所以二元信源序列总是“ 0”游程和“ T游程交替出现。(即为对应将二元信源序列映射成交替出现的表示游程长度的自然数序列 的游程长度的标志序列)0一般情况，对“ 0”游程长度和“ 1”游程长度也可分别编码，建立各自的码 字和码表(如霍夫曼编码)0编码效率n (游程编码和霍夫曼编码)其中P0, P1为“0”和“ 1”符号的概率。n 0和n 1为游程长度为“ 0”和“1”霍 夫曼编码效率。(2)多元信源游程编码将多元信源输出的多元序列映射成一一对应的标志序列。一维多元信源序列需选用表示串的字符、串的长度的两个标志参量。二维多元信源序列需选用表示串的字符、串的长度及串

16、的位置三个标志参 量。2. MH编码MH编码是用于黑白二值文件传真的数据压缩码。它是一维编码方案。它是 游程编码和霍夫曼码相结合的一种标准的改进霍夫曼码。根据“黑”、“白”的不同游程长度有两张结尾码(终端码)表和两张组合码(形 成码)表。(1)编码方法游程长度在063时，直接查表用相应的结尾码为码字。游程长度在641728时，用组合码加上结尾码为相应码字。 规定每行从白游程开始，每行结束用结束码 (EOL)。用于传输时，每页文件开始第一数据前加一结束码， 每页结尾连续用6个 结束码。为了传输还要考虑实现同步的操作。(羽平均码枪的极限值 A邓WL的V血H彳上rtv 时其中丹".用占为平

17、均白、«游程检度T为白、黑像素出«的槪是ffl*白址计誉均R毎牛像*的爛值；Lut.白统计平均后每个像素所需二兀码的平的码心5. 1. 15算术编码算术编码是非分组码，它从全信源序列出发，考虑符号之间的依赖关系直接 对信源符号序列进行的编码。算术编码的主要概念是将信源符号序列的累积分布函数和0，1)区间中的一 个数C联系起来，不同的信源符号序列对应于不同的无重叠小区间中的数。所 以，这个码是即时码。1.编码方法(1)用递推公式计算信源序列的累积分布函数F(s)和所对应区间的宽度 A(s):名元仃源为j sji)二 F(s) F(s)Jt中佰符号累枳分布瞋数2尸3）3 丸八而

18、F（2 源符序列$的ft11 I率.对于二帀信孤 可从一无»数来计算Fd）F® 二2 化丁）二 1 = 丫卩（刃=I 一 S P（T）（器确宦信源序列”的WKhfu 1昭册d）将F（昇写成二进位小数*取小若有俚数.进位到第他 得M勺码字（二实际编码町用软、5件实现"2華均码长的®限电呂民W i k H民SJ丄丄rr金卉 frtn若信源无记忆有/Jil（S） IKS） +«是信源序列怏® n所L几算术编码的编码敢率很髙.5. 1. 16 字典码字典码又称LZ码，是一种通用编码方法，无需知道信源的统计特性，而且 编码效率很高。基本算法是，将长度不同的符号串编成一个个新的短语 （符号串），形成短语 词典的索引表，进行编译码。1. LZ-77 编码编码算法的主要思想是设一个滑动窗口， 将已输入的数据流存储起来，作为 字典使用。然后用三元标识（K，l，d）即（移位数，