第三章 信源编码（一）离散信源无失真编码.

Presentation on theme: "第三章 信源编码（一）离散信源无失真编码."— Presentation transcript:

1 第三章 信源编码（一）离散信源无失真编码

2 3.1信源及其分类 3.2离散无记忆信源的等长编码 3.3离散无记忆信源的不等长编码 3.4最佳不等长编码

3 3.1 信源及其分类

4 信源及其分类 离散信源 连续信源 无记忆信源 有记忆信源 简单信源－独立同分布 平稳信源，各态历经源 M阶记忆源 时间离散连续源 随机波形源

5 3.2 离散无记忆源的等长编码

6 离散无记忆源 字母表A={a1,…,aK},概率分别为p1,…,pK,长为L的源输出序列uL={u1,…,uL}，共有KL种序列
码符号字母表B={b1,…,bD},以码符号表示源输出序列，D元码 等长D元码，不等长D元码的个数 单义可译码，每个消息都至少有一个码字与之对应。 单义等长可译码存在充要条件DN≥KL 由此可得，N≥LlogK/logD

7 DMS的等长编码 NlogD≥LH(U) H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)
选L足够长，使 NlogD≥L[H(U)+eL] L趋向于无穷，eL趋向于0，保证不降低效率。不能保证单义可译，但可以保证非单义可译引起的误差可以渐进的任意小。 如何证明？

8 弱、强e典型序列集 定义3.2.1：令H(U)是集{U, p(ak)}的熵，e是正数，集合 定义为给定源U输出的长为L的典型序列集。
定义为给定源输出的长为L的e－典型序列集，其中Lk 是在L长序列中符号ak出现的次数 ——强e-典型序列集

9 例3.2.2 典型二项序列出现的概率： 当L足够大，

10 信源划分定理 定理3.2.1:给定信源｛U, p(ak)｝和e>0,当L∞，Pr{T(L, e)}1,或对所有e>0，存在有正整数L0，使得当L>L0时有

11 信源划分定理 系1：特定典型序列出现的概率 若uL∈TU(L,e),则

12 信源划分定理 典型序列的数目： 系2：当L足够大时，对于给定的信源和e>0,典型序列的个数｜TU(L,e)｜满足

13 信源划分定理 信源消息可以分为2组：（渐进等同分割性） 1、典型序列 高概率集，渐进等概序列，AEP序列 2、非典型序列 低概率集

14 编码速率和等长编码定理 编码速率：R=(1/L)logM=(N/L)logD, M为码字总数
可达速率：对于给定信源和编码速率R以及任意e>0，若有L0,以及编译码方法，使得L>L0,错误概率小于e，R是可达的 等长编码定理： R>H(U),R是可达的，R<H(U)，R是不可达的 编码效率：h=H(U)/R

15 3.3 DMS的不等长编码

16 平均码长

17 不等长编码面临问题 同步问题 划分唯一性 译码延迟 缓存问题

18 几个定义 唯一可译码 逗点码，无逗点码 字头或前缀 异字头码或异前缀码 树码，满树，非满树，全树 树码构造异字头码

19 例子 信源字母集 概率 码A 码B 码C 码D a1 a2 a3 a4 0.5 0.25 0.125 1 10 00 11 110 111
1 10 00 11 110 111 01 011 0111

20 例 观察表3.3.1。 码A不是唯一可译的。码B不是唯一可译的。 码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码C是异字头码。 码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。 码C不是逗点码。码D不是异字头码。 码C的平均码长比码D的平均码长小： 码C的平均码长为1×0.5+2×0.25+3× ×0.125=1.75； 码D的平均码长为1×0.5+2×0.25+3× ×0.125=1.875。

21 异字头码的第一种构造方法：Shannon-Fano编码法 （D元编码，字母表为{0, 1, …, D-1}）
（1）将源随机变量的事件按概率从大到小排成一行。 （2）将此行切分为D段，分别赋予标号“0”到“D-1”，称为1级标号。 （3）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为2级标号。 （4）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为3级标号。 如此一直到每个段均含有至多一个事件为止。 此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。 为了使平均码长小，每次切分段时应使D段的概率尽可能相近。 （注解：当然可以把“切分段”操作换为“任意分组”操作，使D组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。 ）

22 Shannon－Fano编码 异字头码可以通过树图构成
D元码 将信源符号按出现概率从大到小排列 每次信源符号化为概率近似相等的D个子集 这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。 理想情况I(ak)=nklogD, p(ak)=D-nk

23 异字头码存在的充分必要条件 Kraft不等式 定理3.3.1: 长度为n1,n2,…,nk的D元异字头码存在的充分必要条件是：
异字头码不唯一，且满足上式的码不一定是异字头码

24 唯一可译码 定理3.3.2：唯一可译码必然满足Kraft不等式 系：任一唯一可译码可用各相应码字长度一样的异字头码代替

25 不等长编码定理

26 关于不等长编码的几个概念 不等长编码的速率： 不等长编码的效率：h=H(U)/R 码的多余度：1-h

27 3.4最佳不等长编码

28 两个定理 1.对于给定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同
2. 对辅助集为最佳的码，对原始集也是最佳的

29 二元Huffman编码 1、将符号（符号序列）概率从大到小排列 2、最后的2个符号分别分配为0，1
3、将最后的2个符号的概率值相加，合并起来作为一新的符号 4、重复第一步骤

30 Huffman编码 例(0.20,0.19,0.18,0.17,0.15,0.10,0.01)

31 Huffman编码 若pj>pk，则nj≤nk 最长的2个码字码长相同 最长的2个码字除了最后一位不同外其余位置的值都相同

32 多元Huffman编码 number = 1＋k (D - 1)

33 LZ编码 是否存在编码方法与信源的统计特性无关？ 基于字典编码的基本原理 定长码
LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，而且实际应用也很多。如计算机文件压缩。

34 Eg：对下面信息序列进行LZ编码 分段phrases：1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011

35 序号 字典位置 字典内容 码字 1 0001 00001 2 0010 00000 3 0011 10 00010 4 0100 11 00011 5 0101 01 00101 6 0110 00 00100 7 0111 100 00110 8 1000 111 01001 9 1001 010 01010 1010 01110 1011 011 01011 12 1100 001 01101 13 1101 110 01000 14 1110 101 00111 15 1111 10001 10101 16 11101

36 游程编码 信源产生消息具有相关性，同一个消息连续输出的个数称为游程
对信源序列BBBBBBXXXXXXXAAAAAAAAJJJJJJJJJJJ编码，可得到码序列：B#6X#7A#8J#11

37 算术编码 Huffman编码的局限性 算术编码无需计算信源序列分布，直接对信源符号序列编码，可达到渐进最佳性能
思想：计算输入信源符号序列所对应的区间，在区间内任取一点，以其二进制表示适当截断作为序列的编码结果 例题1：设无记忆源U={0，1},其概率分布矢量为{0.25, 0.75}。对信源序列u= 做算术编码 例题2：无记忆信源U={1,2,3,4}，概率矢量｛0.5,0.25,0.125,0.125}，对信源序列 算术编码

38 算术编码 经过算术编码，上例题的结果为 ，用7比特 的码字表示了8比特的信息

39 算术编码 1、初始化：起点P＝0，宽度A＝1 2、如码元全部处理，转第五步
3、读入的码元为0，区间的起点P不变，宽度缩短为Ap,用公式P=P，A=Ap迭代计算，转第二步 4、读入的码元为1，区间的起点右移Ap，宽度缩短为A(1-p)，用公式P=P+Ap，A=A(1-p)迭代计算，返回第二步 5、根据区间的最终宽度A，通过2-L≤A<2-(L-1)求得码字长度，将区间起点P截取小数点后L位，剩余部分若不为0，进位到小数点后第L位

40 Eg：s=011，说明U＝（000, 001, 010, 011, …, 111）, 所以 若 若 所以 其中

41 Eg：s= ，p(0)=1/4, p(1)=3/4, 所以有H(u)=0.81bit/符号； ，

42 A：通过计算来编码， F(s)=p( )+p( )+…+p( ) =1-p( )-p( )-p( ) -p( )=1-p( )-p( ) =1-p(111111) =1- = 所以C(s)=

43 B：用递推公式编码 输入符号 P(s) L(s) F(s) C(s) 1 0.11 0.01 0.1 0.1001 0.0111
2 3 0.111 5 7

44 C：用〔0,1）区间表示

45 第三章结束