第3章 无失真信源编码.pdf

日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6章章 无失真信源编码无失真信源编码 第第1 1 1 1节节 几个概念几个概念 第第2 2 2 2节节 单义可译码单义可译码 第第3 3 3 3节节 非延长码及其构造非延长码及其构造 第第4 4 4 4节节 单义可译性定理单义可译性定理 第第5 5 5 5节节 编码长度和编码效率编码长度和编码效率 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 第第7 7 7 7节节 HuffmanHuffmanHuffmanHuffman编码编码 第第8 8 8 8节节 香农编码香农编码 第第9 9 9 9节节 费诺编码费诺编码 第第10101010节节 行程编码行程编码 Lemple ZivLemple ZivLemple ZivLemple Ziv编码编码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 1 信源符号信源符号信源符号信源符号对应的信源有效对应的信源有效对应的信源有效对应的信源有效码字码字码字码字 用来表示信源符号的数字序 列W 简称信源有效码字 本章也可简称为有效码字 如在ASCII码中 a编码成 110 0001 扩展ASCII码中 a编码成 0110 0001 BCD编码中 8编码成 1000 2 信源符号码字长度码字长度 用来表示信源符号的数字序列长度 如 第第1 1 1 1节节 几个概念几个概念 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 1111111111111111H H H H100100100100D D D D 1110111011101110G G G G011011011011C C C C 110110110110F F F F010010010010B B B B 101101101101E E E E00000000A A A A 信源码字信源码字符号符号信源码字信源码字符号符号 4 变长码 各信源符号用不同长度的有效码字表示 第第1 1 1 1节节 几个概念几个概念 111111111111H H H H011011011011D D D D 110110110110G G G G010010010010C C C C 101101101101F F F F001001001001B B B B 100100100100E E E E000000000000A A A A 信源码字信源码字符号符号信源码字信源码字符号符号 3 定长码 所有的信源符号用相同长度的码字表示 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 00221H001D 00220G000C 0021F02B 0020E01A 信源码字符号信源码字符号 第第1 1 1 1节节 几个概念几个概念 111H011D 110G010C 101F001B 100E000A 信源码字符号信源码字符号 5 信源码符号 信源编码中构成信源有效码字的符号集 A 0 1 A 0 1 2 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 q s s s 2 1 q w w w 2 1 12 iii aaa k 信源 信源 编码器 21r aaaX 1 1 1 1 信源编码原理方框图 信源编码原理方框图 设信源发出的符号集S s1 s2 sq 每个信源符号编码成一 个信源码字 对应的码字集为W w1 w2 wq 每个码字均 由信源码码符号集A a1 a2 ar 中的元素组成 第第2 2 2 2节节 单义可译码单义可译码 信源符号信源符号信源符号信源符号 信源码字信源码字信源码字信源码字 信源信源信源信源码码码码符号符号符号符号 信道 编码器 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 如 信源码符号集为A 0 1 信源符号s1对应的有效码字可以 为1001 若信源码符号集为A 0 1 2 信源符号s1对应的有效 码字可以为1201 2 2 2 2 无失真信源编码 无失真信源编码 如果所有的有效码字与信源符号一一对应 并且连续的 码字符号也与连续的信源符号一一对应 则称信源编码单 义可译 1 定义 第第2 2 2 2节节 单义可译码 无失真信源编码 单义可译码 无失真信源编码 单一可译是对一种无失真信源编码的最基本的要求 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第2 2 2 2节节 单义可译码单义可译码 111H011D 110G010C 101F001B 100E000 A 码字符号码字符号 1111H100D 1110G011C 110F010B 101E00A 码字符号码字符号 例 若信源符号为 A BAD CAB 则可编码为 Total bits 1800 010 00 100 011 00 010VLC Total bits 21000 001 000 011 010 000 001FLC FLCVLC 这两种编码都是单义可译码 VLCVLCVLCVLC比比FLCFLCFLCFLC效率高效率高 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 111H01D 000G00C 11F1B 10E0A 符号字母符号字母 0 1 0 01 00 0 1 A B A D C A B 01 00 10 00 1 D C E C B 01 00 1 000 1 D C B G B 若接收符号序列为 010010001 则可能有很多种可能的 译码 如 3 例子 第第2 2 2 2节节 单义可译码单义可译码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第2 2 2 2节节 单义可译码单义可译码 说明 说明 说明 说明 1 单义可译码的要求 信源码字与信源符号一一对应 信源符号序列与信源码字序列一一对应 2 通常情况下 变长码具有较高的效率 平均码字长度小 问题 问题 问题 问题 如何判断及构造单义可译码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第2 2 2 2节节 单义可译码单义可译码 1 前缀编码条件前缀编码条件前缀编码条件前缀编码条件 任何一个有效信源码字不可能是其它 有效码字的前缀 3 3 3 3 前缀编码条件 前缀编码条件 前缀编码条件 前缀编码条件 2 前缀编码 满足前缀编码条件的信源编码一定单义可 译 例子 例子 0001000100010001D D D D 001001001001C C C C 01010101B B B B 1 1 1 1A A A A 码字码字码字码字符号符号符号符号 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 1 非延长码定义 第第3 3 3 3节节 非延长码及其构成非延长码及其构成 1000100010001000D D D D 100100100100C C C C 10101010B B B B 1 1 1 1A A A A 码字码字码字码字符号符号符号符号 0000000000001 1 1 1D D D D 001001001001C C C C 01010101B B B B 1 1 1 1A A A A 码字码字码字码字符号符号符号符号 这两种编码都是单义可译码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第3 3 3 3节节 非延长码及其构成非延长码及其构成 例 1001011001101 非延长码 也叫即时码 是指接收到码字后能立刻确定对应 的符号 信源符号信源符号A AB BC CD D 编码1110100101 编码2101001000 编码1 100 10 1 100 1 10 1 编码2 1 001 01 1 001 1 01 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第3 3 3 3节节 非延长码及其构成非延长码及其构成 2 2 2 2 说明 说明 1 非延长码也叫即时码 是一种单义可译码 2 非延长码一定满足前缀编码条件 3 任何一种单义可译码总可以找到至少一种对应的具有相同 码字长度的非延长码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 0 0 0 0 0 0 0 1 1 1 1 1 1 任何一个有效码字所对应的点 不能经过另外一个有效码字 对应的点 第第3 3 3 3节节 非延长码及其构成非延长码及其构成 3 3 3 3 非延长码的树图构造法 非延长码的树图构造法 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 1 Kraft不等式 若ni代表一种单义可译信源编码中信源符号si对应的码字wi的 长度 r代表信源码符号数 则下面不等式一定成立 1 1 q i n i r 如信源码符号集 1 0 X则 2 r 如信源码符号集 2 1 0 X 则3 r 第第4 4 4 4节节 单义可译定理单义可译定理 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第4 4 4 4节节 单义可译定理单义可译定理 2 单义可译性定理 任何一种单义可译编码 必满足克拉夫不等式 同样 只 要码字长度满足克拉夫不等式 至少可以找到一种单义可 译编码 说明 单义可译码一定满足Kraft不等式 满足kraft不等式的编码不一定不一定为单义可译码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 111H011D 110G010C 101F001B 100E000A 码字符号码字符号 11110H100D 1110G011C 110F010B 101E00A 码字符号码字符号 1222 8 333 1 q i ni r 233 15 45 222 31 221 32 i q n i r 第第4 4 4 4节节 单义可译定理单义可译定理 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第4 4 4 4节节 单义可译定理单义可译定理 3 图解 0 0 0 0 0 0 0 1 1 1 1 1 1 r 2r 2r 2r 2 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第4 4 4 4节节 单义可译定理单义可译定理 例题 例题 1 已知信源码字长度分别为以下各值 至少能够找到一 种单义可译码的是 A 1 1 3 4 B 1 2 2 3 C 1 3 3 2 D 1 2 2 2 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 2 下面哪种说法是不正确不正确不正确不正确的 A 任何满足Kraft不等式的编码一定是前缀编码 B 任何前缀编码一定满足Kraft不等式 C 前缀编码条件是 任何一个有效信源码字不能是其它有效 信源码字的前缀 D 若某信源编码要求的编码长度满足Kraft不等式 则至少可 以找到一种单义可译编码 第第4 4 4 4节节 单义可译定理单义可译定理 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 2 平均码字长度 平均每个信源符号对应有效码字的长度 1 模型 q q q q nnnn wwww pppp ssss 321 321 321 321 码字长度 码字 概率 符号 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 信源码符号 信源码字 物理意义 平均每个信源码字由几个信源码符号组成 平均 每个信源符号编码成几个信源码符号 信源码符号 信源符号 q i iin pn 1 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 3 3 3 3 信源编码码率 信息率 信源编码码率 信息率 1 信源的熵 q i ii ppXH 1 log 物理意义 平均每个信源符号所携带的信息量 2 信源编码信息率 物理意义 平均每个信源码码符号携带多少比特的信息量 比特 信源符号 n XH R 比特 信源码符号 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 4 4 4 4 说明 说明 1 假设信源码符号集为A 0 1 则每个信源码符号最多携 带1比特的信息量 2 假设信源码符号集为A 0 1 2 则每个信源码符号最多携 带log3比特的信息量 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 例 p414 已知信源空间为 8 1 8 1 4 1 2 1 4321 SP ssssS PS 信源符号空间 1 0 X 对应的码字长度分别为n1 n2 n3 n 4 写出一种有效编码 并求对应的信息率 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 75 1log 4 1 4 1 i ii i ii spspsIspXH 0 1 0 0 1 1 1 01 001000 1 利用二叉树单义可译码 码长 码字 概率 符号 3 001 1 8 s3 000011 1 81 41 2 321 s4s2s1 2 信源的熵 3 平均码字长度 4 信息率 比特 信源符号 75 1 4 1 i ii nspn 信源码符号 信源符号 1 n XH R 比特 信源码符号 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第7 7 7 7节节 无失真信源编码定理无失真信源编码定理 NNpNpNpNpN ssss 875 0 3210 4321 0 讨论 码字 概率 符号 001 1 8 s3 000011 1 81 41 2 s4s2s1 由频率与概率的关系可知 编码后信源码符号0和信源码符号1出现的概率 相等 此时得到的信源编码效率应该最大 符合最大信息熵定理 设信源总共要发出N N趋近于无穷大 个信源符号 则编码后出现0的个数 和1的个数应分别为 NNpNpNpNpN ssss 875 00111 4321 1 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 3 1 3 3 8 1 3 2 8 1 2 1 4 1 2 1 0 0 p 分析 码长 码字 概率 符号 3 001 1 8 s3 000011 1 81 41 2 321 s4s2s1 编码后输出的信源码符号序列中 0 1 的概率为 0 的概率 3 2 8 1 3 1 8 1 2 1 4 1 2 1 1 01 p 1 的概率 这样计算为什不对 这样计算为什不对 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 码长 码字 概率 符号 2 10 1 8 s3 110100 1 81 41 2 222 s4s2s1 如对应的编码为 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 则有 平均码字长度 信息率 2 4 1 i ii nspn 信源码符号 信源符号 875 0 n XH R比特 信源码符号 NNpNpNpNpN ssss 375 10112 4321 0 由频率与概率的关系可知 编码后信源码符号0和信源码符号1出现的概率 有较大差距 NNpNpNpNpN ssss 625 0 2110 4321 1 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 码长 码字 概率 符号 2 01 1 8 s3 1001000 1 81 41 2 133 s4s2s1 讨论 第第5 5 5 5节节 平均码长与编码有效性平均码长与编码有效性 则有 平均码字长度 信息率 625 2 4 1 i ii nspn信源码符号 信源符号 67 0 n XH R 比特 信源码符号 NNpNpNpNpN ssss 125 20123 4321 0 由频率与概率的关系可知 编码后信源码符号0和信源码符号1出现的概率 有很大差距 NNpNpNpNpN ssss 500 01110 4321 1 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 P444 T4 P445 T6 作业 作业 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 平均码字长度越小越好 但是对于一种给定信源 其平均码 字长度是受到该信源的熵影响的 1 平均码字长度的界限定理 123 123 123 123 q q q q ssss pppp wwww nnnn 符 号 概 率 码 字 码 字 长 度 1 lo glo g HXHX n rr 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 2 2 2 2 证明下界 证明下界 证明下界 证明下界 1 分析n r XH log 0log rnXH 2 证明 q i ii q i i i rnp p prnXH 11 log 1 loglog q i n i q i i i i rp p p 11 log 1 log q i i n i p r p i 1 log 01log log log 11 q i n q i i n i i i r p r p 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 3 上界证明 思路 我们需要证明 对于特定信源 至少可以找到一种至少可以找到一种无 失真信源编码方法 使得 1 log H X n r 虽然 的单义可译编码也找得到 但是由于效 率低 我们并不采用 1 log H X n r 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 取码字wi长度为ni 假设假设 1 11 q i i q i n pr i 1 ii nn i rpr 即 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 1 i n i rp log1 rii pn 1log iri pn r i i q i i i q i ii p r p pnp 111 log log 1 log r XH n 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 1 i n i rp 因为满足的单义可译码是找得到的 所以满足 的单义可译码也一定是找得到的 1 log r XH n 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 说明 说明 平均码字长度小于该量的单义可译码一定可以找到 平均码字大于该量的信源编码效率低 无论采用何种无失真信源编码方法 都不能使得 平均码字长度小于该量 平均每个信源符号携带的信息量 平均每个码符号最多携带的信息量r XH n log 1 log r XH n 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 例 考虑一个信源 X 发出四种符号的概率分别为 p1 0 5 p2 0 3 p3 0 1 p4 0 1 其非延长码编码为 0 10 110 111 找出这种编码的平均码字长度及信道的信息率 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第6 6 6 6节节 平均码长的界限定理平均码长的界限定理 122222 3321 4 11 i n q i n ii r 比特 信源符号 信源码符号 信源码字 比特 信源码符号 685 1log 4 1 4 1 i ii i ii spspsIspXH 700 1 4 1 i ii nspn 9912 0 n XH R 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 4 推广到一般情况 假设同时对N个信源符号编码 则得到 1 log log r SH n r SH N N N NrN SH N n rN SH N N N 1 log log 信源码符号 信源符号 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 5 5 5 5 扩展信源符号编码 扩展信源符号编码 一种更有效的编码方法是同时对N个信源符号进行编码 例 考虑一个信源 各符号及相应的概率如下所示 信道符号集为X 0 1 01 00 1 码字 22 00000 25s3 21 51460 35s2 11 32190 40s1 码字长度自信量概率符号 第8节 Huffman 编码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第8节 Huffman 编码 信源的熵为 信源符号比特 559 1log 3 1 i ii ppXH 3 1 1 0 420 3520 25 1 600 ii i nn p 信源码符号 信源符号 0 9743 H S R n 比特 信源码符号 平均码字长度为 信息率 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 400003 32190 1000s3 s1 31113 32190 1000s1 s3 30113 02910 1225s2s2 411014 00000 0625s3 s3 411003 51460 0875s3 s2 400013 51460 0875s2 s3 30102 83650 1400s2s1 001 10 码字 32 83650 1400s1 s2 22 64390 1600s1 s1 码字长度自信量概率符号 第8节 Huffman 编码 如果同时对两个符号进行编码 其概率密度及Huffman编码如下图所示 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 信源符号比特 个信源符号比特 5589 1 21177 3log 9 1 2 2 XH ppXH k kk 9 1 3 1775 2 1 5888 2 Nii i N nn p n n 信源码符号 个信源符号 信源码符号 信源符号 0 9812 H S R n 比特 信源码符号 平均每个信源符号对应的信源码符号数 信息率 第8节 Huffman 编码 信源的熵为 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 结论 同时对同时对N N N N个符号进行编码 编码效率更高 个符号进行编码 编码效率更高 HuffmanHuffmanHuffmanHuffman编码小结编码小结 1 二进制编码 讨论 0 1互换时情况 几个符号具有相同概率情况 2 多进制情况 3 扩展信源符号同时编码 第8节 Huffman 编码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 作业 P445 T11 P444 T5 1 2 N 2 3 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第9 9 9 9节节 香农编码香农编码 1 信源 q q ppppSP ssssS PS 321 321 按降序排列得到 因此该假设不失一般性 假设 121 01 qq pppp 若不是可通过将符号 2 编码步骤 若对符号si编码 则按以下步骤进行 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第9 9 9 9节节 香农编码香农编码 1 计算符号si的自信量 并求整数li 满足 1 iii sIlsI 2 计算 1 1 i j ji pP 3 将Pi用二进制表示 取小数点后的li为作为符号si的编码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 例 例 111111076 66 0 99 10 0 01 s7 111043 34 0 89 10 0 10 s6 10132 74 0 74 10 0 15 s5 10032 56 0 57 10 0 17 s4 01132 48 0 39 10 0 18 s3 00132 41 0 2 10 0 19 s2 00032 34 0 10 0 20 s1 码字 码长 自信 量 累加概 率Pi 概率符号 累加概率的二进 制表示 0 000000 0 0011 0 011 0 1001 0 101 0 1110 0 1111110 第第9 9 9 9节节 香农编码香农编码 日日 思思 日日 睿睿 笃笃 志志 笃笃 行行信息论与编码 湖北大学物电学院蒋碧波 第第9 9 9 9节节 香农编码香农编码 例 写出例 写出s s s s4 4 4 4对应的码字对应的码字w w w w4 4 4 4 1 计算符号s4的自信量 并求整数l4 bitspsI56 217 0loglog 44 3 4 l 2 计算 1 1 i ij j Pp