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

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元码，能够选择的不同码字的个数为DN，不等长D元码的个数,能够选择的不同码字的个数为D1+D2+…+DN=D(DN-1)/(D-1)

7 pe= P{(U1U2…UL)=(u1u2…uL)| (u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。
离散无记忆源的等长编码 编码速率 R=NlogD/L。 无错编码 (U1U2…UL)的不同事件用不同的码字来表示。能够实现无错编码的充要条件是DN≥KL。（即编码速率R=NlogD/L≥logK） 有错编码 (U1U2…UL)的有些不同事件用相同的码字来表示。 有错编码的译码方法与 “译码错误”概率 当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）。“译码错误”的概率定义为 pe= P{(U1U2…UL)=(u1u2…uL)| (u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。

8 离散无记忆源的等长编码 关于编码速率的说明：
编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 ：R=NlogD/L≤R0。 当编码速率R比较高时，可以选择比较大的N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。 当编码速率R比较低时，意味着使用低成本的编码设备。此时只能选择不大的N，因此更需要编码的技巧。

9 离散无记忆源的等长编码 在无错编码的前提下，编码的最低代价 当R≥logK时，能够实现无错编码。
当R<H(U1)时，无论怎样编码都是有错编码。这是因为R<H(U1)≤logK。 （如果H(U1)=logK，则以上两种情形已经概括了全部情形。但如果H(U1)<logK，则还有一种情形） 当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。

10 离散无记忆源的等长编码 渐进无错编码 （简单地说就是：当R>H(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：） 设给定了编码设备的编码速率R0，R0>H(U1)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的等长编码和对应的译码方法，满足 ①实际的编码速率R=NlogD/L≤R0， ②译码错误的概率pe<ε。 （11）渐进无错编码的原理 大数定律。随着L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越来越小（→0），其发生的概率却越来越大（→1）。

11 离散无记忆源的等长编码 不能渐进无错的编码 （简单地说就是：当R<H(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是： ） 设给定了编码设备的编码速率R0，R0<H(U1)。则无论怎样编码和译码都不能同时满足 ①实际的编码速率R≤R0， ②译码错误的概率pe任意小。

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

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

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

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

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

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

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

19 编码速率和等长编码定理 编码速率：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

20 DMS的等长编码 例 设

21 DMS的等长编码 设给定编码设备的编码速率R0=0.5。则 R0>0.037587148=H(U)。 希望：
②译码错误的概率不超过ε。其中取 ε=0.1； ε=0.05； ε=0.01。

22 P{(U1U2…UL)=(u1u2…uL)| -0.1≤IL-H(U) ≤0.1}≥0.9。
DMS的等长编码 取ε=0.1。找L0使得 即L0=253。当L≥253时总有 P{(U1U2…UL)=(u1u2…uL)| -0.1≤IL-H(U) ≤0.1}≥0.9。 另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，

23 DMS的等长编码 事件(u1u2…uL)属于典型序列集TU(L, 0.1)；当且仅当 -0.1≤IL-H(U) ≤0.1；当且仅当

24 DMS的等长编码 设L=253。此时 L= 。 当事件(u1u2…u253)中a1的个数不超过4时， (u1u2…u253)∈TU(253, 0.1)； 否则(u1u2…u253)不属于TU(253, 0.1)。 (u1u2…u253)∈TU(253, 0.1)的概率不小于0.9； (u1u2…u253)∈TU(253, 0.1)的个数为

25 P((u1u2…u253)不属于TU(253, 0.1))≤ε=0.1。
DMS的等长编码 对L=253，对应地取整数N=[R0L]=126。则N/L<R0，这就是说2元编码的实际编码速率并未超出编码设备的编码速率。 2元编码的编码方法： 将TU(253, 0.1)中的事件用不同的126长码字表示；将TU(253, 0.1)外的事件用同一个126长码字表示，该码字已经用于表示了TU(253, 0.1)中的一个事件。由于|TU(253, 0.1)|≤ <2126，码字足够用。 2元编码的译码方法： 将码字译为它所表示的TU(253, 0.1)中的事件(u1u2…u253) 。于是，译码错误的概率为 P((u1u2…u253)不属于TU(253, 0.1))≤ε=0.1。

26 P{(U1U2…UL)=(u1u2…uL)| -0.05≤IL-H(U) ≤0.05}≥0.95。
DMS的等长编码 取ε=0.05。找L0使得 即L0=2020。当L≥2020时总有 P{(U1U2…UL)=(u1u2…uL)| -0.05≤IL-H(U) ≤0.05}≥0.95。 另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，

27 DMS的等长编码 事件(u1u2…uL)属于典型序列集TU(L, 0.05)；当且仅当 -0.05≤IL-H(U) ≤0.05；当且仅当

28 DMS的等长编码 设L=2020。此时 L= 。 当事件(u1u2…u2020)中a1的个数不超过20时， (u1u2…u2020)∈TU(2020, 0.05)； 否则(u1u2…u2020)不属于TU(2020, 0.05)。 (u1u2…u2020)∈TU(2020, 0.05)的概率不小于0.95； (u1u2…u2020)∈TU(2020, 0.05)的个数为

29 P((u1u2…u2020)不属于TU(2020, 0.05))≤ε=0.05。
DMS的等长编码 对L=2020，对应地取整数N=[R0L]=1010。则N/L=R0，这就是说2元编码的实际编码速率等于编码设备的编码速率。 2元编码的编码方法： 将TU(2020, 0.05)中的事件用不同的1010长码字表示；将TU(2020, 0.05)外的事件用同一个1010长码字表示，该码字已经用于表示了TU(2020, 0.05)中的一个事件。由于|TU(2020, 0.05)|≤ <21010，码字足够用。 2元编码的译码方法： 将码字译为它所表示的TU(2020, 0.05)中的事件(u1u2…u2020) 。于是，译码错误的概率为 P((u1u2…u2020)不属于TU(2020, 0.05))≤ε=0.05。

30 P{(U1U2…UL)=(u1u2…uL)| -0.01≤IL-H(U) ≤0.01}≥0.99。
DMS的等长编码 取ε=0.01。找L0使得 即L0=252435。当L≥252435时总有 P{(U1U2…UL)=(u1u2…uL)| -0.01≤IL-H(U) ≤0.01}≥0.99。 另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，

31 DMS的等长编码 事件(u1u2…uL)属于典型序列集TU(L, 0.01)；当且仅当 -0.01≤IL-H(U) ≤0.01；当且仅当

32 DMS的等长编码 设L=252435。此时 0.00274372L=692.61096 ； 0.00525628L=1326.8690 。
当事件(u1u2…u252435)中a1的个数不超出闭区间[693，1326]内时， (u1u2…u252435)∈TU(252435, 0.01)； 否则(u1u2…u252435)不属于TU(252435, 0.01)。 (u1u2…u252435)∈ TU(252435, 0.01)的概率不小于0.99； (u1u2…u252435)∈ TU(252435, 0.01)的个数为

33 P((u1u2…u252435)不属于TU(252435, 0.01))≤ε=0.01。
DMS的等长编码 对L=252435，对应地取整数N=[R0L]=126217。则N/L<R0，这就是说2元编码的实际编码速率小于编码设备的编码速率。 2元编码的编码方法： 将TU(252435, 0.01)中的事件用不同的126217长码字表示；将TU(252435, 0.01)外的事件用同一个126217长码字表示，该码字已经用于表示了TU(252435, 0.01)中的一个事件。由于|TU(252435, 0.01)|≤ < ，码字足够用。 2元编码的译码方法： 将码字译为它所表示的TU(252435, 0.01)中的事件(u1u2…u252435) 。于是，译码错误的概率为 P((u1u2…u252435)不属于TU(252435, 0.01))≤ε=0.01。

34 3.3 DMS的不等长编码

35 DMS的不等长编码 （1）不等长编码的优越性 总体上减少码字的长度。 （2）不等长编码的特殊问题 唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。 解决方案：适当地编码，使得每个码字都具有识别标记。 （注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2) 连接成的字母串c(1)c(2) 不能是码字）

36 平均码长 希望平均码长小。 解决方案：概率大的事件用短码字。

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

38 几个定义 唯一可译码 逗点码，无逗点码：若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。（逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。） 字头或前缀 异字头码或异前缀码：①若事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。（异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。） 树码，满树，非满树，全树 树码构造异字头码

39 例子 信源字母集 概率 码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

40 例 观察表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。

41 异字头码的第一种构造方法：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组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。 ）

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

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

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

45 不等长编码定理

46 不等长编码定理 任一唯一可译的D元不等长码总满足 存在唯一可译的D元不等长码满足

47 不等长编码定理 证明 设信源随机变量U的概率分布为 如果唯一可译的D元不等长码的码字长度为 则

48 不等长编码定理 因此 。 另一方面，取n1、n2、…、nK， 则: 由于 , 存在码字长度为 的唯一可译的D元不等长码。

49 不等长编码定理 对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则

50 不等长编码定理 任一唯一可译的D元不等长码总满足 存在唯一可译的D元不等长码满足

51 关于不等长编码的几个概念 不等长编码的速率： 不等长编码的效率：h=H(U)/R 码的多余度：1-h
注解 不等长编码与等长编码具有相似的性质：当L增大时，对UL的编码可以使用更短的平均码长，因而更加节省编码速率。但节省编码速率的下限是H(U)。

52 3.4最佳不等长编码

53 最佳不等长码 寻找最佳不等长编码，就是在唯一可译的前提下，使得2元码的平均码长最小。实际上是求解整数规划问题

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

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

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

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

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

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

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

61 序号 字典位置 字典内容 码字 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

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

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

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

65 算术编码 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位

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

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

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

69 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

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

71 第三章结束