第5章 信源编码.

Presentation on theme: "第5章 信源编码."— Presentation transcript:

1 第5章 信源编码

2 5.2 无失真信源编码

3 5.2.3 最佳变长编码 最佳码： 能获得最佳码的编码方法主要有: 在信源满足无失真编码定理的编码方式中,
最佳变长编码 最佳码： 在信源满足无失真编码定理的编码方式中, 若存在一种唯一可译码,其平均码长小于所有其 他唯一可译码的平均长度。 能获得最佳码的编码方法主要有: 香农（Shannon） 费诺（Fano） 哈夫曼（Huffma ）

4 1、香农编码 I(xi)≤ Ki <I(xi)+1
香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。 香农第一定理指出,任意一个符号Xi的码字的 长度Ki满足下式： I(xi)≤ Ki <I(xi)+1 就可以得到这种码。 这种编码方法称为香农编码

5 ⑷将Pi用二进制表示,并取小数点后Ki位作为 符号xi的码字。
二进制香农码的编码步骤如下： ⑴将信源符号按概率从大到小的顺序排列, 　　　　p(x1)≥ p(x2)≥…≥ p(xn) ⑵确定每个符号的码字长度Ki , －log2 p(xi)≤ Ki <1－log2 p(xi) ⑶令p1=0,用Pi表示第i个码字的累加概率， ⑷将Pi用二进制表示,并取小数点后Ki位作为 符号xi的码字。

6 对该信源编二进制香农码。其编码过程如表所示
例 有一单符号离散无记忆信源 对该信源编二进制香农码。其编码过程如表所示 以i = 3为例: 码字长度： K4 = [－log0.2] = 3 累加概率 Pi=0.70 → … 信源 符号 xi 概率 p(xi) 累加 Pi -log p(xi) 码长 码字 x1 0.4 1.32 2 00 x2 0.3 1.73 01 x3 0.2 0.7 2.32 3 101 x4 0.05 0.9 4.3 5 11100 x5 0.95 11110 00 01 101 11100 11110 这些码字没有占满所有码树,所以是非最佳码

7 香农码的平均码长 熵 x1 编码效率 x2 x5 x3 x4 为提高编码效率,首先应达到满树;如把x4x5换成前面的节点,可减小平均码长。

8 2、费诺编码 费诺编码属于概率匹配编码。 编码步骤如下： 将概率按从大到小的顺序排列,令 p(x1)≥ p(x2)≥…≥ p(xn)
按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编m进制码就分成m组。 给每一组分配一位码元。 将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止。

9 例 设有一单符号离散信源 对该信源编二进制费诺码。 平均码长： K= 2.0 编码效率: η=97.5% 平均码长： K= 2.1
例 设有一单符号离散信源 平均码长： K= 2.0 编码效率: η=97.5% 平均码长： K= 2.1 编码效率: η=93% 对该信源编二进制费诺码。 信源符号 xi 符号概率 p(xi) 第1次 分组 第2次分组 第3次 码 字 长 x1 0.4 00 2 x4 0.05 1 010 3 x5 011 x2 0.3 10 x3 0.2 11 信源符号 xi 符号概率 p(xi) 第1 分组 第2分组 第3 第4 码 字 长 x1 0.4 1 x2 0.3 10 2 x3 0.2 110 3 x4 0.05 1110 4 x5 1111

10 平均码长 编码效率 费诺码比较适合于每次分组概率都很接近的信源 特别是对每次分组概率都相等的信源进行编码时, 可达到理想的编码效率。

11 例 有一单符号离散无记忆信源 对该信源编二进制费诺码,编码过程如表:

12 信源熵为 H(X)=2.75(比特/符号) 平均码长为 编码效率为 η=1 之所以如此,因为每次所分两组的概率恰好相等。

13 3、哈夫曼编码 哈夫曼编码也是用码树来分配各符号的码字。 哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。

14 哈夫曼编码的步骤如下： ⑴ 将信源消息符号按其出现的概率大小依次排列 p(x1)≥p(x2)≥…≥ p(xn) ⑵ 取两个概率最小的符号分别配以0和1两码元,并 将这两个概率相加作为一个新符号的概率,与未 分配的二进符号的字母重新排队。 ⑶ 对重排后的两个概率最小符号重复步骤⑵的过 程。 ⑷ 不断继续上述过程,直到最后两个符号配以0和1 为止。 ⑸ 从最后一级开始,向前返回得到各个信源符号所 对应的码元序列,即相应的码字。

15 在图中读取码字的时候,要从后向前读,此时编出来的码字是哈夫曼码。
例5-7 设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表 在图中读取码字的时候,要从后向前读,此时编出来的码字是哈夫曼码。 信源符号xi 符号概率p(xi) 编码过程 x1 0.20 x2 0.19 x3 0.18 x4 0.17 x5 0.15 x6 0.10 x7 0.01 码字 10 11 000 001 010 0110 0111 0.20 0.19 0.18 0.17 0.15 0.11 0.26 0.20 0.19 0.18 0.17 0.35 0.26 0.20 0.19 0.39 0.35 0.26 0.61 0.39 1 1 1 1 1 1

16 熵 平均码长为 编码效率

17 3、哈夫曼编码 哈夫曼的编法并不惟一。 每次对缩减信源两个最小概率的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到哈夫曼码字。 不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别；

18 3、哈夫曼编码 缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。 此时得到的码字长度Ki也不相同，但平均码长相同，即编码效率相同。

19 例5-8 单符号离散无记忆信源 编码过程 x1 x2 x3 x4 x5 码字 1 01 000 0010 0011 码字 00 10 11
信源符号xi 符号概率p(xi) 编码过程 x1 0.4 x2 0.2 x3 x4 0.1 x5 码字 1 01 000 0010 0011 码字 00 10 11 010 011 0.4 0.2 0.4 0.2 0.6 0.4 1 1 1 1

20

21 3、哈夫曼编码 编法一的平均码长为 编法二的平均码长为 两种编法的平均码长相同,所以编码效率相同。

22 讨论：同一种编码方法，概率相同、放置位置
不同，哪种方法更好？ 定义码字长度的方差σ2： 第二种编码方法的码长方差要小许多。 第二种编码方法的码长变化较小,比较接近于 平均码长。

23 第一种方法编出的5个码字有4种不同的码长； 第二种方法编出的码长只有两种不同的码长； 第二种编码方法更简单、更容易实现,所以更好。 结论： 在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。

24 3、哈夫曼编码 哈夫曼编码总结： 对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同。 平均码长越短,编码效率就越高。

25 r进制哈夫曼编码 在编r进制哈夫曼码时为了使平均码长最短,就要使长码的符号数尽量少、概率尽量小。 希望信源符号数满足: m=n(r－l)＋r
其中r是进制数，n是缩减的次数： 若信源符号数m无法满足上式，那么必须在最后添加概率为0的虚拟符号，以满足条件，使得长码的符号数最少；

26 例: 对如下单符号离散无记忆信源编三进制哈
夫曼码 这里：r=3，m=8 令n=3，r+n(r－1)=9，则需要添加一个需要 符号来满足条件 设符号x9，概率为0.

27 编码过程 x1 x2 x3 x4 x5 x6 x7 x8 x9 码字 10 11 12 21 22 200 201 202 信源符号xi
符号概率p(xi) 编码过程 x1 0.40 x2 0.18 x3 0.10 x4 x5 0.07 x6 0.06 x7 0.05 x8 0.04 x9 0.00 码字 10 11 12 21 22 200 201 202 0.40 0.18 0.10 0.09 0.07 0.06 0.40 0.22 0.18 0.10 0.40 0.38 0.22 1 2 1 2 1 2 1 2

28 平均码长为 平均信息量为 编码效率为 哈夫曼的编码效率相当高,对编码器的要 求也简单得多。

29 结论 香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使概率大的信源符号对应较短的码字,缩短信源的平均码长,从而实现了对信源的压缩；
香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高； 费诺码和哈夫曼码的编码方法都不唯一；

30 结论 费诺码比较适合于对分组概率相等或接近的信源编码,费诺码也可以编m进制码,但m越大,信源的符号数越多,可能的编码方案就越多,编码过程就越复杂,有时短码未必能得到充分利用； 哈夫曼码对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。

31 5.3 限失真信源编码定理

32 限失真信源编码定理 设离散无记忆信源X的信息率失真函数为R(D) , 当信息率R＞R(D)时,只要信源序列长度 L
足够长,一定存在一种编码方法,其译码失真 小于或等于 D+ε,ε为任意小的正数； 反之,若R＜R(D) ,则无论采用什么样的编 码方法,其译码失真必大于D。 如是二元信源,则对于任意小的ε＞0,每一个 信源符号的平均码长满足如下公式：

33 5.4 常用信源编码方法

34 常用信源编码 香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。 香农编码、费诺编码、哈夫曼编码属于无失真信源编码；
当信源有记忆时上述编码效率不高； 香农编码、费诺编码、哈夫曼编码属于无失真信源编码； 游程编码对有记忆信源编码更有效； 游程编码属于限失真信源编码。

35 游程编码 游程： 数字序列中连续出现相同符号的一段。 二元序列的游程：只有“0”和“1”两种符号。 连“0”这一段称为“0”游程,它的长度称
为游程长度L(0)； 连“1”这一段称为“1”游程,它的游程长 度用L(1)表示。

36 游程编码 二进制序列进行游程编码的规则： 若规定二元序列总是从“0”开始,第一个游程 是“0”游程,则第二个游程必为“1”游程,第
三个又是“0”游程……。 对于随机序列,游程长度是随机的其取值可为 1,2,3,…，直至无穷。 游程变换： 是一种一一对应的变换,也是可逆变换。 例如：二元序列 … 可变换成如下游程序列

37 游程编码 游程变换减弱了原序列符号间的相关性。 游程变换将二元序列变换成了多元序列；
在此基础上还可以利用哈夫曼编码,进一步压缩信源,提高通信效率。 编码方法： 首先测定“0”游程长度和“1”游程长度的概率分布,即以游程长度为元素,构造一个新的信源； 对新的信源(游程序列)进行哈夫曼编码。

38 算术编码的主要理念 算术编码利用了累积概率的概念。 算术码主要的编码方法是计算输入信 源符号序列所对应的区间。
把信源输出序列的概率和实数段[0,1]中 的一个数C联系起来。

39 设信源字母表为{a1, a2},其概率p(a1)=0.6, p(a2)=0.4 将[0,1]分成与概率比例相应的区间,[0,0.6]
[0.6,l] p(a1) p(a2) 随着序列的长度不断增加,C所在区间的长度就越短,也就可以更加精确地确定C的位置 p(a1a1) p(a1a2) p(a2a1) p(a2a2) 设信源输出序列S=S1S2S3…Sn 当信源输出的第一个符号S1 = a1时,数C的值处在[0,0.6] 当信源输出的第一个符号S1 = a2时,数C的值处在[0.6,l] 根据信源S1的情况,把C所在的段再次按概率 比例划分

40 累积概率 设信源符号集A={a1,a2,…,an},其相应概率分 布为p(ai)或pi,p(ai)>0(i=1,2, …,n)
信源符号的累积概率为 显然 P0= 0; P1= p(a1)=p1 ; P2= p(a1)+p(a2)= p1 +p2; … 而且 p(ar) =pr= Pr － Pr-1

41 累积概率Pr和Pr-1都是小于1的正数,可用[0,1] 区间内的两个点来表示;
p(ar)就是这两点间的小区间的长度,如图: P0 P1 P2 P3 1 … p(a1) p(a2) P(a3) … 当A={0,1}二元信源时： P0=0; P1=p(0) P0 P1 1 p(0) p(1)

42 算术编码 计算二元无记忆信源序列的累积概率 初始时：在[0,1)区间内由P1划分成二个子区 间[0,P1)和[P1,1),P1=p(0) 。
若输入符号序列的第一个符号为S=“0”, 落入[0,P1)区间,得累积概率 P (S =“0”)= P0 = 0；

43 若输入第二个符号为“1”,S=“01”, S=“01”所对应的区间是在区间[0, P1 ) 中进行分割； 符号序列“00”对应的区间为 [0,P(S=“01”)) 符号序列“01”对应的区间为 [P(S =“01”),P1) 累积概率: P(S =“01”)=p(00)= p(0)p(0)

44 设输入符号序列S=011 P0= 0 p(0)= p(00)+p(01) P(01)= p(00) p(01)= p(010)+p(011)
P0 P1 1 p(0) p(1) P1 P0 P(01) p(01) p(00) P(01) P(011) P1 p(010) p(011) P0= 0 P(01)= p(00) P(011)= P(01)+p(010) = P(01)+ p(01) P1 p(0)= p(00)+p(01) p(01)= p(010)+p(011)

45 算术编码 一般多元信源序列的累积概率递推公式 序列的概率公式

46 算术编码 在编码过程中,每输入一个符号要进行乘法和加法运算,所以称为算术编码。
通过关于信源符号序列的累积概率的计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为[P(S), P(S)+p(S))。可取小区间内的一点来代表这序列。

47 算术编码 编码方法： 将符号序列的累积概率写成二进位的小 数，取小数点后L位,若后面有尾数,就进位 到第L位,这样得到的一个数C,并使L满足
取整

48 P(S) == 0.110100100111 例：设二元无记忆信源S={0,1},其p(0)=1/4,p(1)=3/4。
对二元序列 做算术编码。 解：p(S= )=p2(0)p6(1)=(1/4)2 (3/4)6 经过计算得到序列的累计概率经过二进制编码得到： P(S) == 得 C = S的码字为

49 信源编码总结 我们学习了几种信源编码：香农编码、费诺编码、哈夫曼编码、游程编码、算术编码。 游程编码和算术编码是非分组编码；
游程编码是限失真信源编码。 本章介绍的都是离散信源变长编码。 优点：提高编码效率； 缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。