第四章：无失真信源编码.ppt

1、第四章：无失真信源编码,无失真信源编码,无失真编码概述 定长信源编码 变长信源编码 实用的无失真信源编码方法举例,4.1无失真编码概述1,离散、无失真、无记忆信源编码的一般模型：,总组合数：,总码组合数：,入,出,取值于同一个符号集， 符号集大小为n,取值于同一个符号集， 符号集大小为m,4.1无失真编码概述2,问题：能否进行无失真编码?怎样进行无失真编码? (前提：不考虑信源统计特性),应满足条件：,无失真条件变换,相互矛盾！,结论：当 n = m 时，KL 不有效。 当K = L 时，mn，亦不满足有效性,解决办法： 引入信源统计特性。,无失真：,有效：,4.1无失真编码概述3,考察无失真

2、条件：,等概条件下的消息符号熵,等概条件下的码字符号熵,考虑信源的实际统计特性（非等概），实际消息熵为：,代入无失真条件得：,结论：即使m=n,只要 就有可能实现KL。 即无失真与有效性同时满足。,具体实现方法：定长与变长编码,4.2定长编码定理1-描述,定长（等长）码信源编码定理： 对离散，无记忆、平稳、遍历信源其符号序列：S =(S1S2 .SL)， 可用K个符号C =(C1C2CK) 进行等长编码，对任意0,0， 只要满足： 则：当L足够大时，可使译码差错小于， 反之，当 时，译码一定出错。,解释： 定长编码定理给出了信源进行等长编码所需码长的理论极限值。,结论：对信源进行二元等长编码时

3、，每个信源符号所需码长的极限值为,结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。,4.2定长编码定理2-进一步理解,若要求所得的等长码是唯一可译的，则必须：,若L1，则：,当采用二元码编码时，m2，则：,4.2定长编码定理2-进一步理解,每个码字（码序列）所能携带的平均信息量,每个源序列所包含的平均不确定性。即：信源序列携带的信息量,等长有效性的无失真编码的条件：,码长下限：,为实现有效：,误码率任意小的方向：?,结论：只要码字能够携带的信息量大于信源序列携带的信息 量，总可以实现几乎无失真编码,考虑信源统计特性,讨论：第三章：在考虑符号出现的概率和符号间相关性前提下,每个 英

4、文符号平均携带的信息量是1.4bit/符号5bit/码符号。,4.2 定长编码定理3-举例,例1：英文电报有32个符号（266），即n=32， 若m=2，L1（即对信源的逐个符号进行二元编码）， 则：,bit,解释：每个英文电报符号至少需要用5位二元符号编码 （每位二元符号可以携带1bit信息，即每个英文电报符号用了可以携带 5bit信息的码符号即5位二元码表示）,问题：如何提高效率？如何体现有效性？,结论：若不考虑信源统计特性等长编码效率极低!,4.2定长编码定理4-进一步理解,解决方法：,字母个数为n，字母之间相关长度为L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的

5、字母组合，而且随着L的增加，这种无意义序列的总数越来越大。,进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 ,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。,考察：,方法：,问题：,会引入一定的误差！但当L足够长后，误差可以任意小。,4.2定长编码定理5证明,考察离散、随机序列信源的统计特性 渐进等分割性（AEP） AEP描述： 渐进等分割定理： （熵定理，遍历性定理） 设 是离散无记忆信源输出的一个特定序列，则任给 和 ，总可以找到一个整数 ，使当 时，有：,引入：渐进等分割性（AEP: Asymptotic Equiparti

6、tion Property ）,特定序列的平均符号自信息,随机矢量的平均符号熵,任何一个离散随机序列信源当序列长度L时,信源序列会产 生两极分化.小概率事件集合 与大概率事件集合 ,即nL= 对于 有性质: 对于 有性质:,由此可见，信源编码只需对信源中少数落入典型大概率事件的集合的符号进行编码即可。而对大多数属于非典型小概率事件集合中的信源符号无需编码.,4.2定长编码定理6 AEP物理意义,信源熵,大概率事件熵,4.2定长编码定理7 AEP证明,集合 和 中的序列分别称为 典型序列和 非典型序列,表示 中所有 典型序列的集合,表示 集合中序列的个数,可以证明：对于任意小的正数 ， ，当L足

7、够大时，,4.2定长编码定理7 AEP证明,还可以证明：对于任意小的正数 ， ，当L足够大时，,表示序列 出现的概率,由切比雪夫不等式可得：,表示S中每个符号携带的信息量的方差,例2 p(1)=p,p(0)=q,统计独立L长的序列: 当L8时，序列11000101和序列011100101 的概率为 和 显然，这两个序列不等概, 当L 时，有一些序列1出现的次数接近Lp，这些序列的概率为 且这些序列近似等概分布。,4.2定长编码定理8 AEP举例,L长的序列 ，对于任意小的正数 满足式 的序列称为 典型序列 即：典型序列集是哪些平均自信息任意小地接近信源熵的N长序列的集合,4.2定长编码定理9-

8、 AEP应用,AEP结论：当L足够大时， 所有 典型序列出现的概率近似相等，即 典型序列为渐进等概序列 可粗略认为 典型序列出现的概率为 所有 典型序列的概率和接近为1，即 典型序列总数占信源序列的总数,4.2定长编码定理9- AEP应用,AEP应用： 提出、证明都是基于离散无记忆序列信源 平稳遍历信源有类似结果 体现信源统计特性 用以证明定长编码定理,4.2定长编码定理10 证明,定长编码定理证明思路： 将取自S，长为L的信源符号序列分为集合 和,几个概念：,编码信息率：,编码后对应于每个信源符号平均能载荷的最大信息量,编码效率：,编码前后平均每个信源符号能载荷的最大信息量之比,只对集合 中

9、的序列进行一一对应的等长编码,此时的误差为 ，计算误差,证明当 ，且 (K/L)log mH(S)+ 时，,4.2定长编码定理11（物理意义）,结论： 可推广至离散、非平稳无记忆信源和有记忆信源（即H(S)=H (S)）情况 只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码,二元码时，m2：,最佳等长码时：,4.2定长编码定理12（实际应用问题）,编译码同步问题 问题：如何使译码端知道码字起点 解决办法：1、每个码字加短同步前缀 2、每若干码字加较长同步前缀,分组长度与编译码复杂性、编译码延时等的关系 问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加 解决办法

10、：目前没有理想的解决办法,定长信源编码的理论意义远大于其实用价值,4.2定长编码定理13（举例),例3：设有一简单离散信源：L=1,n=2 对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低 于10-5，试求符号联合编码长度L=？,解：,由编码效率：,而：,则：,且：,则：,结论：可见,需要4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的.,一般来说：当L有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码,改变信源,定长编码,无失真信源编码实现方法一,无失真信源编码实现方法二,适应信源,变长编码,大概率短码；小概率

11、长码,4.3变长信源编码-1,几个码类的概念 非奇异码（单义码） 唯一可译码 前缀码（即时码、非延长码、异前置码） 最佳码（紧致码） Kraft定理即时码码长必须满足的条件 唯一可译码存在定理 变长编码定理（香农第一定理）,4.3变长信源编码-2(几个码类的概念),非奇异码（单义码）： 每一个码字仅对应信源中的一个信源符号（序列）。 编码是单义的。 反之为奇异码或非单义码。,4.3变长信源编码-3(几个码类的概念),唯一可译码 编码单义、译码单义 对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。 非奇异码=唯一可译码？,4.3变长信源编

12、码-4(几个码类的概念),前缀码 是唯一可译码中的一类 在一个变长码中，没有任何一个码字是其他码字的前缀。 译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。 又称即时码、非延时码 例如逗点码：1，01，001，0001,4.3变长信源编码-5(几个码类的概念),最佳码 唯一可译码的一类 其平均码长小于其他唯一可译码的平均长度,所有的码,非奇异码,唯一可译码,前缀码,最佳码,4.3变长信源编码-6（几种类型的信源编码举例）例4：,定长 唯一可译,奇异,非奇异,前缀,唯一可译,4.3变长信源编码-7(Kraft定理),引出 码树构造即时码方法 Kraft定理描述即时码码长须满足的条件

13、Kraft定理证明略,实时唯一可译、可分离,A,B,A,B,B,B,B,B,A,A,C,D,D,E,D,100010111010111101010111001001101110,要求：须严格同步,4.3变长信源编码-8(Kraft定理引出),问题：寻求实时唯一可译码 方法：研究实时唯一可译码的码字可分离条件 简单信源：“码树”概念（直观） 一般信源：通过Kraft定理给出实时唯一可译码（前缀码）存在 的条件,码树变长码的树图表示,将变长码与码树建立“一一对应”关系： 树根码字起点 树枝数码的进制数 节点码字或码字的一部分 终止节点码字 节数码长 非满树变长码 满树等长码,利用码树构造前缀码,s

14、1,s2,s3,s4,0,1,1,1,0,0,0,10,110,111,s1,0.04,s4,s3,0.16,0.64,s2,0.16,4.3变长信源编码-9(Kraft定理),问题： 比较简单信源，码树方法可直接且直观构造前缀码 较复杂信源，直接画码树复杂且困难 解决方法： 为便于分析，特别对含有很多符号种类的复杂信源，寻找一种与上述“树图”等效的解析式表达式-Kraft不等式。 结论： Kraft定理给出码字可分离或前缀码存在的充要条件,4.3变长信源编码-10(Kraft定理),kraft定理：长度为Ki（i=1,2,n）的m （码字母表长度）进制前缀码存在的充要条件为： 证明：略 物理

15、意义： 给定信源个数N和码字母数m，只要允许码字长度可以足够长，就总可以满足Kraft不等式，从而得到前缀码。 只要适当选取码长，码字一定可以即时分离。,例5：,3 2 1 0,4 个叶子: 代表序列 1, 01, 001 和 000是前缀码,4.3变长信源编码-11(唯一可译码定理),Kraft不等式给出的限制也是所有唯一可译码都必须满足的。 定理描述： 任何唯一可译码均满足Kraft不等式。 结论： 唯一可译码一定满足kraft不等式 满足kraft不等式的码不一定是唯一可译码，但一定存在至少一种唯一可译码 对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码,4.3变长编码定理1

16、2,问题： 对于已知信源S可用码符号集X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则。 引入：码的平均长度。 离散无记忆平稳信源,信源熵率为 ，码字个数为M，信源符号对应码长分别为：ki,i=1,2,.n,则前缀码平均码长：,4.3变长编码定理13,定理： 离散无记忆平稳信源S，其熵为 ，并有码符号集C=c1,cm。对信源S进行编码,总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足: 另一方面,必可以找到前缀码，使其平均码长满足

17、,对于给定的信源和码符号集，若有一个唯一可译码，其平均长度小于所有其他唯一可译码，则称这种码为紧致码或最佳码。,唯一可译码存在性,紧致码的存在性,证明：,Jensen不等式,平均码长=下限值,由右边不等式,香农第一定理（变长无失真信源编码定理）： 设离散无记忆信源的熵为 H(S) ，它的N次扩展信源为 ，对扩展信源 进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：,其中,当 时，有,当 时，有,代表平均到每个信源符号所需的码长,当 时，每个码符号能够携带的信息量为：,4.3变长编码定理14,物理意义： 又称无噪信道编码定理 编码后的码符号信源尽可能为等概分布，使每个码符号平均

18、所含的信息量达到最大 要做到无失真编码，变换每个信源符号平均所需最少的m元码元数就是信源的熵率（以m进制信息量单位测度，对应离散无记忆信源） 信源的熵率是描述每个信源符号平均所需最少的比特数 定理说明： 是存在性定理具有理论指导意义 是构造性定理设计出多种具体编码方法,构造：,1、扩展信源至,2、取,3、则：k(s)满足kraft不等式，存在前缀码,4、用树图法构造前缀码香农编码,4.3变长编码定理15编码效率,变长码编码效率：衡量各种编码方法的优略，判断是否最佳码。 编码前平均每个信源符号携带的信息量为： 编码后平均每个信源符号携带的最大的信息量为： 定义变长码编码效率为： 另一种理解： 最

19、佳码（极限时）每个信源符号的平均码长为： 某一方法得到的每个信源符号的平均码长为： 定义变长码编码效率为：,4.3变长编码定理16编码效率,比较： 定长编码的编码效率： 变长编码的编码效率：,注意到： 是指平均到每个信源符号所需的码长，而 也是平均到每 个信源符号的码长，所以它们是一致的，均表示无失真信源 编码的效率。,例6：一离散无记忆信源,其熵为：,用二元符号（0，1；m=2）构造一个前缀码：,此时每个信源符号平均码长为：,编码效率为：,为提高编码效率，对S的2次扩展信源进行2维联合编码：,构造一个扩展信源S2的前缀码：,此时平均码长为：,此时信源S中每个符号对应的平均码长为：,编码效率为

20、：,同样可得：,定长编码与变长编码效率比较：,例6与例3相比： 同一个信源，当要求编码效率达到96时， 等长码需要4100万个信源符号联合编码； 变长码只需2个符号（二次扩展信源）联合编码；,结论：采用变长编码，L不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着L的增大，编码效率越来越接近于1。,无失真信源编码,等长编码,变长编码,完全无失真 效率差,较好的效率、 一定的误差,可实现、有实用,难实现、无实用,无失真、较好 的效率,可实现、有实用,总结：,定长编码定理 近似无失真等长编码的条件,有效性、无失真性无法兼得,考察信源统计特性,利用信源序列的AEP特性,定长编码定理

21、研究思路,变长编码定理研究思路,无失真唯一可译码,工程可实现前缀码,码树构造简单前缀码,KRAFT不等式前缀码存在条件,香农定理最佳码存在条件,定长编码定理,变长编码定理,1、存在码长为K的定长编码方法 2、L足够大时，几乎无失真,条件,1、存在无失真的变长编码方法 2、最佳码的码长上界：,条件,结论,结论,4.4 最优编码,定理1:对每一给定的离散无记忆信源,存在一个最优的二元前缀码.这个码中最少发生的两个码字必具有相同的长度,且码中相同长度的码字有两个或两个以上时,其中必有两个码字的差别只在最后一位.,4.4 最优编码,定理说明 没给出编码全过程 最优二元前缀码，两个最小概率信源字母对应的

22、码字等长，且差别在最后一位。 两个最小概率信源字母对应的码字相同部分的最后一位可以通过缩减信源的方法得到。 缩减方法： 原信源 缩减信源,4.4 最优编码,定理2:设C是某信源经缩减后所得的缩减信源的最优前缀码，将C中由原信源中的最小概率的两个字母缩减得到的字母所对应的码字后各加0和1,作为原信源的最小概率的两个码字,而其余码字不变,则这样得到的码C对原信源也是最优的.,4.5实用的无失真信源编码方法举例,香农（Shannon)码 费诺（Fano）码 霍夫曼（Huffman）编码 编码方法 特点 应用 问题,思路：平均码长与信源特性相匹配 适用数据源：离散无记忆信源,香农编码、费诺编码、霍夫曼

23、编码,4.5实用的无失真信源编码方法举例,香农编码步骤,以二进制香农码为例： 排序 将信源符号按概率从大到小的顺序排列，为方便起见，令 p(x1) p(x2) p(xn) 概率累加 令p(x0)=0，设i=0,1,n-1,用pa(xj)，j=i+1表示前i个码字的累加概率，则： 确定码长 求满足下列不等式的整数ki ，并令ki为第i个码字的长度 log2 p(xi)ki1 log2 p(xi) 编码 将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。,4.5实用的无失真信源编码方法举例,例7有一单符号离散无记忆信源 对该信源编二进制香农码。其编码过程如下表所示。,香农编码举

24、例1,0.25,0.00,0.50,0.70,0.85,0.95,(0.000)2,(0.010)2,(0.100)2,(0.101)2,(0.1101)2,(0.11110)2,2,2,3,3,4,5,00,01,100,101,1101,11110,编码效率 离散无记忆信源的熵： 平均码长： 采用香农编码后的信息率： 编码效率： 结论： 1、香农编码对信源进行了压缩。若对该信源采用等长编码， 要做到无失真译码，每个符号至少要用3个比特表示。 2、编码效率并不是很高。,香农编码举例2,以二进制费诺编码为例，编码步骤如下： 排序： 将概率按从大到小的顺序排列，令 p(x1) p(x2) p(x

25、n) 分组： 按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二 进制码就分成两组，编m进制码就分成m组。 编码： 给每一组分配一位码元。 重复： 将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分 为止。,费诺编码步骤,4.5实用的无失真信源编码方法举例,例8 设有一单符号离散信源 对该信源编二进制费诺码。编码过程如下表所示。,费诺编码举例1,0,1,0,1,0,1,0,1,0,1,00,01,10,110,1110,1111,2,2,2,3,4,4,编码效率 该信源的熵: 平均码长: 编码效率: 结论： 费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相

26、等的信源进行编码时，可达到理想的编码效率。,费诺编码举例3,4.5实用的无失真信源编码方法举例,霍夫曼编码,编码规则： 1)排序： 将信源消息U按概率大小排序（由大至小） p(x1) p(x2) p(xn) 2)定规则并编码： 从最小概率的两个符号开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。若两支路概率相等，仍为下支为“1”上支为“0”。 3) 概率合并：将已编码两支路概率合并，重新排队，编码。 4) 重复：重复步骤3）直至合并概率归一时为止。 5)确定最终码子：从概率归一端沿树图路线逆行至对应消息编码。,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0

27、,1,0,1,0,1,10,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,000,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,000,001,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,000,001,010,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,000,001,010,0110,霍夫曼编码举例1,例

28、9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,000,001,010,0110,01110,霍夫曼编码举例1,例9：,0,1,0,1,0,1,1,0,0,1,0,1,0,1,10,11,000,001,010,0110,01110,01111,霍夫曼编码举例2,特点： 编码不是唯一的 保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用 每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况） 每次缩减信源的最长两个码字具有相同码长 后三个特点保证了所得到的huffman码一定是最佳码（证明见李亦农信息论基础教程2005年

29、1月第一版p114）,每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。 不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长 也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。,霍夫曼编码举例3,例10 单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。 方法一：合并后的新符号排在其它相同概率符号的后面。,霍夫曼编码举例4,

30、对应该图画出树图,霍夫曼编码举例6,方法二：合并后的新符号排在其它相同概率符号的前面。,霍夫曼编码举例7,霍夫曼编码举例8,0,0,0,1,0,1,1,x,5,x,4,x,3,x,2,x,1,1,单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。 编法一的平均码长为 编法二的平均码长为 可见 ，本例两种编法的平均码长相同，所以编码效率相同。,霍夫曼编码举例9,思考题：哪种方法更好？,讨论： 1) 两种方法平均码长相等。 2) 计算两种码的码长方差：,第二种方法编出的码码字长度

31、变化较小，便于实现。,4.5实用的无失真信源编码方法举例 霍夫曼编码应用,考察例6和下例：例12：对以下平稳信源进行霍夫曼编码,信源字母,概率,码字,编码过程,a1,a2,a3,a4,1/2,1/4,1/8,1/8,0,10,110,111,0,1,0,1,0,1,编码效率：,4.5实用的无失真信源编码方法举例 霍夫曼编码应用,结论：,各信源字母的概率刚好取 的形式时，霍夫曼编码取得 理想的压缩效果,各信源字母的概率不能取 的形式时，霍夫曼编码压缩 效率不理想,扩展信源，可以提高压缩效率，当 时达到理想的压缩,霍夫曼编码应用,应用: 在不同领域得到广泛应用。 例：International d

32、igital facsimile coding standard(1980)US 、MPEG1、2 问题： 误差扩散 速率匹配 统计匹配（1、一般变长编码更适合大的消息集，而不大适合小且概率分布相差很大的集合；小消息集只有在很特殊情况下才能实现统计匹配 2、要求了解信源的统计分布；） 算法复杂度随着信源符号串长度的增加而迅速增长。,4.5实用的无失真信源编码方法举例,霍夫曼编码应用,解决： 工程上克服误差扩散的方法有两种：一是限制哈夫曼码仅能应用于优质信道（=10-6）以限制扩散的可能性；二是采用定期清洗，防止扩散区域增大。但是它是靠牺牲有效性换取的。 一是选择码长方差小的编码方法，工程上解决

33、速率匹配问题的方法是在两者之间加一个类似于水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。 小消息信源的匹配通过不断扩展信源实现；统计特性未知时可采用所谓通用编码的方法来解决 算法复杂度问题考虑采用算术编码方法解决。,4.5实用的无失真信源编码方法举例,4.5实用的无失真信源编码方法举例算术码,引出: Huffman码应用存在的问题： 分组编码，码字分离错误将导致错误扩散 提高编码效率不断扩展信源编、译码复杂度提高 引入算术码 与扩展信源不同的角度解决小消息集合统计匹配及提高编码效益问题,算术码 是一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它 不是将单个的信源符号映射

34、成一个码字，而是将整个输入序列的符号依据它 们的概率映射为实数轴上0,1)区间内的一个小区间，再在该小区间内选择 一个代表性的二进制小数，作为实际的编码输出。 它比霍夫曼编码、游程编码等编码算法都复杂，但它不需要传送像霍夫曼 码表一类的编码表。 算术编码具有自适应的能力，它的编码效率优于Huffman编码，所以算术编 码是实现高效数据压缩的有力工具。,PCM码 编码公式 对应量化层 归一化编码公式,4.5实用的无失真信源编码方法举例算术码编码1,上面例子是一个简单的三位PCM的例子 其编码可表示为：（简单算术表达式） 三位码共有八层:,如：码字110A1=1,A2=1,A3=0;,4.5实用的

35、无失真信源编码方法举例 算术码编码2,则：码字110 可见，这时信源编码过程就可以看作是上述对应二进制小数作移位相加的过程。故称它为算术编码。,4.5实用的无失真信源编码方法举例算术码编码3,分析：上述例子仅是一个特例，因为它没有考虑信源的统计特性，（它认为信源是遵从等概率分布的）所以编出的码字是等长码，而对应的算术运算则是简单的整数项相加。（即Ki为整数）。,4.5实用的无失真信源编码方法举例算术码编码4,问题：对一般的具有统计特性的信源的算术编码问题。,方法：将上述算术编码方式进一步拓广，其中最关键的是要将算术编码与信源的符号概率及累积概率建立一一对应关系，进而将累计概率与 区间的一个数C

36、联系起来。,新的问题：在引入统计特性后的算术编码中，每次移位的位数可以是非整数（精度有限的有理数），正是由于这种非整数的引入使算数编码变成了非分组码（当然，算术编码从全序列出发，考虑符号间的依赖关系来编码）。,算术码编码5,信源符号序列的累积分布函数 设信源符号集 ： 其相应的概率分布为： 信源符号累积分布函数： 对二元信源,算术码编码6,举例说明，二元无记忆信源为例。 区间由F(1)划分成两个子区间：,宽度A（0）=P（0）,宽度A（1）=P（1）,若输入第一个符号为S=“0”,即落入相应的区间 得,若输入第二个符号为1，S=“01”,相应的区间是在 进行分割，符号“00”对应的区间宽度为

37、符号“01”对应的区间宽度为,0,1,F(1),算术码编码7,符号S=“00”对应的区间为,符号S=“01”对应的区间为,是符号序列“01”对应区间的下界值（对应符号序列的累积分布函数）,0,1,F(1),算术码编码7,若输入第三个符号为1，S=“011”可以记作S+1=S1,相应的区间是在 进行分割，,符号S0=“010”对应的区间宽度为,对应的区间为,符号S1=“011”对应的区间宽度为,对应的区间为,符号序列s1=“011”的累积分布函数,若输入第三个符号为0，S=“010”下界仍为F(s),序列S0的累积分布函数为,算术码编码8,信源符号序列的累积分布函数迭代公式 已知当前输入符号序列

38、为S，若接着再输入一个0，序列S0累积分布函数： 区间宽度为 已知当前输入符号序列为S，若接着再输入一个1，序列S1累积分布函数： 区间宽度为,算术码编码9,举例说明S=“011”,接着输入1,对应区间宽度为,102,算术码编码10,信源符号序列的累积分布函数树图计算法 已知当前输入符号序列为S=(s1s2sn)，另一二元序列串为Y=(y1y2yn)对第一个i有si=1,yi=0,则SY。 把符号序列看成二进制小数0.S和0.Y，对第一个i有siyi,则0.S0.Y 将二元符号序列排成一棵n阶二元整树。可见所有小于S的序列都在同一阶S节点的左侧。,1,1,1,0,0,1,S=1101,0,1,

39、C 0.01111001,P(S)=(3/4)3(1/4) C=1000 (有尾数时进位）,1,1,0,1,0.10010100,0.00011011,算术码编码举例1,例14：,P(S)=(3/4)3(1/4),算术码编码举例2,算术码编码过程：,：累积概率码字,：区间长度（符号所落区间）,例：,算术码编码举例3,F(1)=F( )+A( )F(1)=0+0.01=0.01 A(1)=A( )p1=1x0.11=0.11 F(11)=F(1)+A(1)F(1)=0.01+0.11x0.01=0.0111 A(11)=A(1)p1=0.11x0.11=0.1001 F(110)=F(11)+A(11)F(0)=0.0111+0.1001x0=0.01