霍夫曼码、算术码和LZW码

发布于:2021-06-11 06:14:18

第6节 霍夫曼码 节 1. 1952 年霍夫曼(Huffman)提出的,是历史记录中第一个最优即时码。 2. 二元霍夫曼码的构造方法:根据信源符号的概率自底向上地构造码树,步骤 二元霍夫曼码的构造方法:根据信源符号的概率自底向上地构造码树, 如下: 如下: (1) 将信源 U 的 n 个符号 ui 按概率 p(ui)从大到小排列, 构成码树的叶节点。 (2) 将两个最小的概率值相加,构成二者的父节点。 (3) 将所有没有父节点的概率值按从大到小重新排列。 (4) 重复(2)与(3)直到根节点出现,即步骤(2)中两个概率值相加=1. 例 6-11 0.5, 0.25, 0.125, 0.125 解: 1)画出码树包括各节点对应的概率值。 2)*均码长: 2) 编码效率: ) : 3) 信源熵(信源的信息传输率) ) 4) 信源的相对熵率(信源的信息传输效率) : ) 3. 二分组霍夫曼码 0.7,0.3 例 6-12 结论:对于“小消息信源” ,必须用分组长度较大的霍夫曼码,才能获得较大 结论 的编码效率与较好的压缩效果。这是提高编码效率的重要途径。 4. 最优分组码 定义 1. 令 S 为一离散信源,用一个新符号取代 S 中两个概率最小的信源符号, 并把这两个最小概率合并为该新符号的概率,而其它信源符号及其概率不变,所 得的信源 S(1)称为信源 S 的(一次)缩减信源 ,并称 S 为 S(1)的扩展信源。n-步 扩展信源。 步 缩减信源 扩展信源 (n) 缩减信源 S . 2. 令 C 是信源 S 的一个即时码, 其中有两个码字 w’与 w’’长度最大且相等, 用其最大真前缀替换 C 中的 w’与 w’’所得的即时码 C(1)称为 C 的 (一次) 缩减码, 缩减码, (1) 扩展码。 并称 C 为 C 的扩展码。与 n-步缩减码分别记为和 Cn。 扩展码 步缩减码分别记为和 显然,信源每缩减一次,其符号总数减 1;即时码每缩减一次其码字总数减 1. C 则两个码的*均码长之间有如 引理 1 令 C 为即时码, (1)是码 C 的一个缩减码, 下关系: LC = L C(1) + p’+p’’ 其中 p’与 p’’分别是 C 中被合并的两个码字的概率。 证明 设 S 有 q 个符号,概率分别为 pi,码 C 中对应的码字长为 li ,其中对应于 概率 p’的码字长记为 l’,则

LC = ∑ pi li
i =1

q

= ∑ pi li + ( p '+ p '')(l '? 1) + p '+ p ''
i =1

q?2

= LC1 + p '+ p '' 引理 2 设 C 为某信源 S 的即时码,C1 是码 C 的一个缩减码,则 C 是最优码 ? C1 是最优码。 把码 C1 所对应的缩减信源记为 S1,并设 S1 中的信源符号 s 是由 S 中两 证明 个信源符号合并而成。再令被合并的两个信源符号的概率为 p’与 p’’。由前面的 引理 3, LC = LC1 + p’+ p’’ (1) (?) 令 D 为 S1 的一个最优即时码, 由前面的引理 2, S 上存在 D 的扩展码 D’, 在 从而由引理 3 得 LD’ = LD+ p’+p’’ (2) 比较(1)与(2),由 C 的最优性可得 LC1 ≤ LD,从而 C1 是最优码。 (?) 令 E 为 S 的一个最优即时码,由前面的定理 4,E 是正规码,从而在 S1 上 存在缩减码 E1,再由引理 3 得 LE = LE1+ p’+p’’ (3) 比较(1)与(3),由 C1 的最优性可得 LC ≤ LE ,从而 C 是最优码。 □ 定理 二元分组码 C 是最优分组码,当且仅当,其码树是二分杈的,且 C 的每次 缩减码都是“概率匹配码” 。 证明 推论 霍夫曼码是最优分组码。 5. 讨论 讨论:同一个信源,不同分组的二元霍夫曼码相比较:分组长度越大,编码 效率越高;编码效率随分组长度增加而增加,并趋向最大值 1。 6. 霍夫曼编码的不唯一性 例 6-13 *均码长相同,但码长方差不同,选择码长方差较小的一个,可使编 码时输出码符号的速度更*稳。 7. 多元霍夫曼码 1)码树的构造方法类似于二元霍夫曼码的码树构造方法。 2)码元数越大,编码效率小。 8. 应用 应用:传真、卫星通信、MP3 程序设计 2:构造二元霍夫曼码 : 输入:一个概率分布。 输入 输出:该分布的熵。 输出 9. 变长分组码的缺点 (1)码长不同导致信源编码器不能匀速输出码元符号,因此不能直接与信道

连接。解决办法是添加缓冲寄存器。 (2)存在差错扩散的问题。解决办法是使用纠错码提高数据的抗干扰能力。 (3) 霍夫曼码的编译码都需要查找码本, 码本太大的话, 占用内存大且费时。 因此,不能对太大的扩展信源进行编码。为进一步提高编码效率,需要改用 非分组码,例如算术码、字典码。 (4)霍夫曼码属于概率匹配码,需要知道信源的统计特性,且不能适应信源 概率变化。可改用具有自适应性的算术编码,或字典码。 第7节 算术码 节 算术码 仍设 U 为离散无记忆信源。 1. 特点: 特点: 1) 非分组码,全序列编码:是一个 ) 非分组码,全序列编码:是一个双射 f : U * → {0,1}* ,可将任意长的 信源序列编码为“一个”码字。 2) 用信源序列 S 的累积概率 F(S)的一个*似值作为 S 的码字,该*似 ) 值的长度由 S 的自信息量或概率 p(S)确定。 2. 累积概率

F(S) = ∑ p(T)
T<lex S |T|=|S|

注意,累积概率值中不含 p(S)。 注意 递推公式:(用树图说明) 递推公式

F(Su) = F(S) + p(S)F(u)
3. 累积概率区间 长度相同的信源序列的累积概率有如下关系:

0 = F(S1) < F(S2) <?< F(Sm) <1, F(Si+1) = F(Si ) + p(Si )
将单位区间[0,1]划分为若干不相交的小区间: 称 IS =[F(S),

F(S) + p(S)) 为序列 S 的累积概率区间 累积概率区间。 累积概率区间

用树图说明各累积概率区间的包含与不相交关系。 用树图说明各累积概率区间的包含与不相交关系 4. 编码方法 基本思想: 基本思想 (1) 计算信源序列 S 的“累积概率”F(S); (2) 计算 S 的码长

L = ? ? log p( S ) ? + 1 ? ?
(3) 取码字 C ( S ) = ? F ( S ) ? L ,其中 F(S)采用二进制表示。 ? ? 定义(*似运算) 定义(*似运算)设 x 为两个二进制实数。*似值表达式 a = ? x ? k 表示 ? ?

a 是 x 的一个有理*似值,a 共有 k 位二进制小数 位二进制小数,且
x ≤ a ≤ x + 2?k

注:满足上述*似关系的有理数 a 不唯一,即*似运算 ( x , k ) ? ? x ? k 是 ? ? 多值函数。 命题 1. *似运算 ( x , k ) ? ? x ? k 是可计算的,即可以编程实现的。 ? ? □

证明 可以编写一个 C 语言程序实现该运算。 命题 2. 任意实数相等关系 x=y 是不可判定的。

算术码的编码方法: 算术码的编码方法: 输入:信源序列 s1s2 ? sn 输入 输出:一个码字。 输出 (1) 按信源符号的给定次序,计算各信源符号 u 的累积概率 F(u); (2) 令 S = ε , F ( S ) = 0, p ( S ) = 1; (3) 从 i=1 到 i=n 重复执行下面的赋值语句: p ( S ) = p ( S ) p ( si ); F ( S ) = F ( S ) + p ( S ) F ( si ); (4) 计算码长 L = ? ? log p( S ) ? + 1 ; ? ? (5) 取码字 C ( S ) = ? F ( S ) ? L ,其中 F(S)采用二进制表示。 ? ? 注:取码长 L = ? ? log p( S ) ? + 1 可以保证 ? ?
C ( S ) ∈ [ F ( S ), F ( S ) + p ( S ))

在教材所介绍的编码方法中,取码长为

L = ? ? log p( S ) ? ? ?
所取的码字为 F(S)中 L 位小数, “若尾数不为 0,则在末尾加 1” 。这样从数学上 来说,也有
C ( S ) ∈ [ F ( S ), F ( S ) + p ( S ))

但是,在计算机中很难判断尾数是否为 0。因为随着序列长度增长,序列的概率 在计算机中很难判断尾数是否为 在计算机中很难判断尾数 越来越小,从而尾数越来越长,受到计算机存储空间的限制,长到一定程度时, 必然被截断,从而引入截断误差。

例 6-16

0.25,0.75

5. 唯一可译性 命题 1 C ( S ) ∈ [ F ( S ), F ( S ) +
1 p ( S )] 2

证明 依算法,显然A ≥ F (S )。 由 L = ?? log p(S )? + 1,得 ? ? 2? L ≤ 故 C (S ) ≤ F (S ) + 1 p(S ). 2 1 p( S ) 2 □

由命题 1 知,长度相同的两个信源序列的码字是不同的。 命题 2 若 S 是 T 的前缀,则
[ F (T ), F (T ) + p (T )) ? [ F ( S ), F ( S ) + p ( S ))

证明 设 T=Su,则
F ( Su ) > F ( S ); F ( Su ) + p ( Su ) = F ( S ) + p ( S ) F (u ) + p ( S ) p (u ) < F ( S ) + p ( S ).

根据上述结果,用数学归纳法,可以证明该命题。 定理 3 设信源符号概率都≤0.5,则算术码是唯一可译码。 证明 设 S 与 T 是任意两个信源序列,只要证明 C ( S ) ≠ C (T ) 即可。



1) S 是 T 的前缀, p(T) ≤0.5p(S), 若 则 从而 LS+1≤LT , C ( S ) ≠ C (T ) 故 2) S 不是 T 的前缀, 若 由命题 2 和命题 1 可得 C ( S ) ≠ C (T )



6. 渐*最优性 讨论: 讨论: 算术码 f:U*→C 限制在 Un 上是 n 分组码,记 fn:Un→C; fn 的*均码长满足如下关系 2 H (S ) ≤ L < H (S ) + n 其证明与信源编码定理的证明类似。 因此,随着信源序列长度 n 不断增长,fn 的*均码长不断缩短,趋向信源 熵,从而编码效率趋向 1。所以,称算术码具有“渐*最优性” 。 因此,信源序列越长,算术码的压缩效果越好。 问题:试比较同一个信源的算术码与霍夫曼码的优劣。 问题

7. 算术码的译码方法 (1) 根据码字长计算 p(S)所在的区间 [21? L , 22 ? L ) ; (注:此步是对教材 中的算法的补充,为步骤(5)做准备。 ) (2) 计算各信源符号的累积概率区间 Iui,并令 A = C ( S ) ; (3) 判断 A 位于哪一个信源符号的累积概率区间,若 A ∈ I u ,则翻译出 符号 u; (4) 计算新值 A = A ? F (u ) ; p (u )

(5) 重复(3)(4)直到 p(S) ∈ [21? L , 2 2? L ) . 、 例 6-17 对例 6-16 中所得的码字 01010 进行译码。

8. 译码方法的正确性 命题 1. C ( S ) ∈ [ F (ui ), F (ui +1 )) 由当且仅当 ui 是 S 的第一个符号。 由累积概率的递推公式可得,

F(uS) = F(u) + p(u)F(S), F(uS) ? F(u) F(S) = , p(u)
命题 2. 若 A ∈ [ F (uS ), F (uS ) +
A' =

(1)

1 p (uS )] 且 2

A ? F (u ) , p (u )

则 A ' ∈ [ F ( S ), F ( S ) +

1 p ( S )] 2

证明 由于 A ≥ F (uS ) ,根据(1)可得 A ' ≥ F ( S ). 由于 A ≤ F (uS ) + p (uS ) / 2 ,

A ? F (u ) p (u ) F (uS ) + p (uS ) / 2 ? F (u ) ≤ p (u ) ( F (u ) + p (u ) F ( S )) + p (uS ) / 2 ? F (u ) = p (u ) = F ( S ) + p( S ) / 2 A' =



第 8 节 LZW 码 特点: 1. 特点 (1) 自适应码,不需要知道信源符号的概率分布。 (2) 字典码:在编码过程中,根据信源序列中出现的新的字符串(单词) 构造一个字符串表(字典) ,用定长的单词序号作为该单词的码字。 (3) 定长码,但编码对象长度不定。 2. 编码方法 (1) 将信源序列中的所有符号登记到字符串表中,并用其在字符串表中的 序号作为每个符号的码字; (2) 读入信源序列的第一个字符,赋给“前缀变量”P; (3) 读入下一个字符,赋给“扩展变量”S; (4) 若 S 存入符号为空格, 则输出 P 中字符串的码字, 停止; 否则执行 (5) ; (5) 若 PS 不在串表中,则将 P 对应的码字输出,并将 PS 存入串表,分配 一个码字给该串,并将字符 S 赋给 P 取代中存放的字符串;否则,将 PS 赋给 P; (6) 重复(3) 。 例 6-18 对信源序列 XYXYZYXYXYXXXXXXX 进行 LZW 编码。

3. 编码效率 随码字长增加而趋向 1.


相关推荐

最新更新

猜你喜欢