第5章 信源编码 第1讲 无失真信源编码 定长编码定理 2016.pdf

余 映 云南大学 1 62 第5章 信源编码 前面介绍了信源熵和信息率失真函数的概念 弄 清了传送信源信息只需要具有信源极限熵或信息传送信源信息只需要具有信源极限熵或信息 率失真函数大小的信息率率失真函数大小的信息率 但在实际通信系统中 用来传送信源信息的信息 率远大于信源极限熵或信息率失真函数 在传送信源信息时能否能否达到达到或或接近信源接近信源熵或率失熵或率失 真函数真函数这样的最小这样的最小信息率信息率呢 这就是信源编码信源编码要解决的问题 余 映 云南大学 2 62 第5章 信源编码 编码分为信源编码和信道编码 其中信源编码又分为无失 真和限失真 由于无失真信源编码定理和限失真信源编码 定理都要求符号数很大 以便其值接近所规定的值 因而 这些定理被称为极限定理 一般称 无失真信源编码定理为第一极限定理 信道编码定理称为第二极限定理 限失真信源编码定理为第三极限定理 余 映 云南大学 3 62 第5章 信源编码 信源符号之间存在分布不均匀性和相关性 使得 信源存在冗余度 信源编码的主要任务信源编码的主要任务 针对针对信源输出符号序列的统计特性 设法把信源输出信源输出符号序列的统计特性 设法把信源输出 符号序列变换为尽可能短的码字符号序列变换为尽可能短的码字序列 从而减少序列 从而减少冗余 冗余 提高编码效率提高编码效率 信源编码信源编码的基本的基本途径途径 使序列使序列中各个中各个符号符号尽可能相互尽可能相互独立 即独立 即消除相关性消除相关性 使编码中各个符号出现的概率使编码中各个符号出现的概率尽可能相等尽可能相等 即 即概率概率 均匀化均匀化 余 映 云南大学 4 62 第5章 信源编码 信源编码的理论基础是信源编码的两个定理 无失真信源编码定理 是离散信源编码的基础 限失真信源编码定理 是连续信源编码的基础 无失真编码可理解为可逆编码 可逆编码是指当信源符号转换成代码后 可从这些代 码无失真地恢复出原来的信源符号 余 映 云南大学 5 62 第5章 信源编码 编码定理不但证明了必定存在一种编码方法 可 使代码的平均长度可任意接近 但不低于 信源 符号熵 而且还阐明达到这一目标的途径 就是 使概率与码长匹配 对于离散信源 可做到无失真编码 可逆编码 对于连续信源 只能做到限失真编码 因为连续信源的取值可有无限多个 所以编成代码后 就无法无失真地恢复原来的连续值 余 映 云南大学 6 62 第5章 信源编码 本章讨论离散信源编码 首先从无失真信源编码定理出发 重点讨论以香 农码 费诺码和哈夫曼码为代表的最佳变长码 然后再介绍其他几种常用的信源编码方法 如LZ编码 游程编码 以及用于图像压缩的 JPEG编码标准 余 映 云南大学 7 62 第5章 信源编码 5 1 编码的定义 5 2 无失真信源编码 5 3 限失真信源编码定理 5 4 常用信源编码方法简介 余 映 云南大学 8 62 5 1 编码的定义 余 映 云南大学 9 62 5 1 编码的定义 将信源消息分成若干组 即符号序列 xi xi1 xi2 xil xiL 序列中的每个符号取自于符号 集 A 即 xil a1 a2 ai an 而每个符号序 列 xi 依照固定的码表码表映射成一个码字码字 这样的码 称为分组码分组码 余 映 云南大学 10 62 5 1 编码的定义 如图5 1所示 如果信源输出的符号序列长度L 1 则信源 符号集为 A a1 a2 an 信源概率空间为 12 12 n n aaaX p ap ap aP 信源 编码器 码表 信道 X Y 图5 1 信源编码器示意图 余 映 云南大学 11 62 5 1 编码的定义 常用二元信道来传输 信道符号集为 0 1 须把信源符 号变换成由 0 1 组成的码符号序列 该过程就是信源编 码 采用不同的码符号如下表 信源符号 出现概率 码1 码2 a1 a2 a3 a4 p a1 p a2 p a3 p a4 00 01 10 11 0 01 001 111 表5 1 变长码与定长码 余 映 云南大学 12 62 5 1 编码的定义 码可分为如下两类 定长码 定长码 所有码字的长度都相同 变长码变长码 码字长短不一 信源符号 出现概率 码1 码2 a1 a2 a3 a4 p a1 p a2 p a3 p a4 00 01 10 11 0 01 001 111 表5 1 变长码与定长码 余 映 云南大学 13 62 5 1 编码的定义 采用分组编码方法 需要分组码具有某些属性 以保证在接收端能够迅速准确地将码译出 下面讨论分组码的属性 余 映 云南大学 14 62 5 1 编码的定义 1 奇异码奇异码和非奇异码非奇异码 若信源符号和码字是一一对应的 则该码为非奇异码 若信源符号和码字是一一对应的 则该码为非奇异码 反之为奇异码 反之为奇异码 例如表中码1是奇异码 其他是非奇异码 信源符号 出现概率 码1 码2 码3 码4 a1 a2 a3 a4 1 2 1 4 1 8 1 8 0 0 1111 0000 1111 0 0 1010 0000 0101 1 1 1010 100100 10001000 1 1 0101 001001 00010001 余 映 云南大学 15 62 5 1 编码的定义 2 唯一可译码唯一可译码和非唯一可译码非唯一可译码 若任意有限长的码元序列 只能被唯一地分割成一个若任意有限长的码元序列 只能被唯一地分割成一个 个的码字 则称为唯一可译码个的码字 则称为唯一可译码 例如 0 10 11 是一种唯一可译码 因为任意一串有限长码序列 如100111000 余 映 云南大学 16 62 5 1 编码的定义 2 唯一可译码唯一可译码和非唯一可译码非唯一可译码 若任意有限长的码元序列 只能被唯一地分割成一个若任意有限长的码元序列 只能被唯一地分割成一个 个的码字 则称为唯一可译码个的码字 则称为唯一可译码 例如 0 10 11 是一种唯一可译码 因为任意一串有限长码序列 如100111000 只能被分割成10 0 11 10 0 0 任何其他分割方法都会产生一些非定义的码字 余 映 云南大学 17 62 5 1 编码的定义 2 唯一可译码唯一可译码和非唯一可译码非唯一可译码 显然 奇异码不是唯一可译码 而非奇异码中有非唯非奇异码中有非唯 一可译码和一可译码和唯一可译码唯一可译码 表中码3 码4是唯一可译码 信源符号 出现概率 码1 码2 码3 码4 A B C D 1 2 1 4 1 8 1 8 0 0 1111 0000 1111 0 0 1010 0000 0101 1 1 1010 100100 10001000 1 1 0101 001001 00010001 余 映 云南大学 18 62 5 1 编码的定义 2 唯一可译码唯一可译码和非唯一可译码非唯一可译码 码2不是唯一可译码 例如系列1000010010000100 本来它是 用来表示 BAADC 的 但在译码时 也可分组为 10 0 00 10 010 0 00 10 0 代表 BACBA 或 10 00 0 10 010 00 0 10 0 代表 BCABA 译码会出问题 信源符号 出现概率 码1 码2 码3 码4 A B C D 1 2 1 4 1 8 1 8 0 0 1111 0000 1111 0 0 1010 0000 0101 1 1 1010 100100 10001000 1 1 0101 001001 00010001 余 映 云南大学 19 62 5 1 编码的定义 3 即时即时码码和非即时非即时码码 唯一可译码又分为非即时码和即时码 即时即时码是一种没有码是一种没有一个码字构成另一码字前缀的码一个码字构成另一码字前缀的码 在译码时没有延迟 收到一个完整码字后就能立即译 码 如果收到一个完整码字后 不能立即译码 还需等下 一个码字开始接收后才能判断是否可以译码 这样的 码叫做非即时码非即时码 余 映 云南大学 20 62 5 1 编码的定义 3 即时即时码码和非即时非即时码码 例如表中码3是非即时码 而码4是即时码 用码4译码时 只要收到符号1就表示该码字已完整 可以立即译码 而码3收到符号1后 还需观察后面紧 跟着几个0 才能做译码判决 信源符号 出现概率 码1 码2 码3 码4 A B C D 1 2 1 4 1 8 1 8 0 0 1111 0000 1111 0 0 1010 0000 0101 1 1 1010 100100 10001000 1 1 0101 001001 00010001 余 映 云南大学 21 62 5 1 编码的定义 综上所述 可将码作如下有层次的分类 非分组码 分组码分组码 码 奇异码 非奇异码非奇异码 非唯一可译码 唯一可译码唯一可译码 非即时码 即时即时码码 余 映 云南大学 22 62 5 1 编码的定义 通常用树来用树来表示即时码的构成表示即时码的构成 每个终端节点互不为前缀 A A 余 映 云南大学 23 62 5 1 编码的定义 唯一可译码存在 的 唯一可译码存在 的充分必要条件充分必要条件 各码字的 长度 Ki 应满足克劳夫特不等式克劳夫特不等式 L G Kraft 1949 即 必要性 如果是唯一可译码 则各码字长度必定满足 该不等式 充分性 如果满足该不等式 则符合这种码字长度的 唯一可译码一定存在 并不是说所有满足该不等式的 码都是唯一可译码 1 1 i n K i m m 是进制数 n 是信源符号数 余 映 云南大学 24 62 5 1 编码的定义 例例5 1 设二进制码树中 X a1 a2 a3 a4 各码字长度为 K1 1 K2 2 K3 2 K4 3 判断 因此不存在满足这种码字长度的唯一可译码 如果各码字长度为 K1 1 K2 2 K3 3 K4 3 则 符合该码字长度的唯一可译码是存在的 比如 0 10 110 111 4 1223 1 9 222221 8 i K i 4 1233 1 222221 i K i 余 映 云南大学 25 62 5 1 编码的定义 需要注意 克劳夫特克劳夫特不等式只能不等式只能用来判断符合某用来判断符合某 码字长度的唯一可译码码字长度的唯一可译码是否存在 并不是否存在 并不能作为能作为唯唯 一可译码的判据 一可译码的判据 如果不满足不等式 那么肯定不是唯一可译码 如果满足不等式 那么还不一定是唯一可译码 如码字 0 10 010 111 虽然满足克劳夫特不等式 但它不是唯一可译码 余 映 云南大学 26 62 5 2 无失真信源编码 余 映 云南大学 27 62 5 2 无失真信源编码 若信源符号信源符号序列序列的长度 L 1 即 X X1 X2 Xl XL Xl a1 a2 an 变换成由 KL 个符号组成的码符号序列码符号序列 即 Y Y1 Y2 Yk YKL Yk b1 b2 bm 变换要求变换要求 能够无能够无失真地失真地从从 Y 恢复恢复 X 即即能能正确正确 地译码地译码 同时希望 同时希望传送传送 Y 所需的所需的信息率最小 信息率最小 余 映 云南大学 28 62 5 2 无失真信源编码 Yk 有 m 种可能取值 平均每个码符号码符号能输出最大 信息量为 log m KL 长码符号序列码符号序列能输出的最大 信息量为 KL log m 用该码符号序列表示 L 长的 信源序列 则每个每个信源符号所需信源符号所需的信息率的信息率平均平均为为 希望找到一种编码方法能够使上述信息率的值达使上述信息率的值达 到最小到最小 log L K Km L 余 映 云南大学 29 62 5 2 无失真信源编码 然而 最小信息率为多少 才能无失真的译码 最小信息率为多少 才能无失真的译码 无失真信源编码定理的研究内容 无无失真信源编码失真信源编码定理定理分为 定定长长编码定理编码定理 变变长长编码定理编码定理 余 映 云南大学 30 62 5 2 1 定长编码定理 余 映 云南大学 31 62 5 2 1 定长编码定理 在定长编码中 码字的长度为定值 在定长编码中 码字的长度为定值 编码目的编码目的 寻找最小的码字长度 寻找最小的码字长度 要实现无失真信源编码 必须满足 信源信源符号与码字一一对应符号与码字一一对应 由码字组成的码符号码符号序列唯一可译序列唯一可译 由一个码表编出的任意一串码符号序列只能 被唯一地译成对应的信源符号序列 余 映 云南大学 32 62 5 2 1 定长编码定理 定长编码定理定长编码定理 由 L 个符号组成的平稳无记忆信源符 号序列 X1 X2 XL 其平均每个信源符号的熵为HL X 将该序列用 KL个码符号Y1 Y2 YKL 进行定长编码 每个 码字符号有 m 种可能值 对任意 0 0 只要 则当 L 足够大时 必可使译码差错小于 反之 当 时 译码差错一定是有限值 而当 L 足够大时 译码几乎 必定出错 log L L K mH L X log 2 L L K mH L X 余 映 云南大学 33 62 5 2 1 定长编码定理 定理说明 当编码器容许的输出信息率 也就 是当当平均平均每个每个信源信源符号所需要的码字长度符号所需要的码字长度 时时 编码器就可以做到 编码器就可以做到几乎无几乎无失真 条件是失真 条件是 L 足足 够大够大 log L L K mH L X 余 映 云南大学 34 62 5 2 1 定长编码定理 若上式改写为 左边为 KL 长的码符号序列所能携带的最大信息量 右边为 L 长的信源符号序列所携带的信息量 这意味着 只要只要码符号序列所能码符号序列所能携带的信息量大携带的信息量大 于信源于信源序列携带的序列携带的信息量 则可以使传输几乎无信息量 则可以使传输几乎无 失真失真 条件 条件是是 L 足够大 足够大 log LL KmLHH XX 余 映 云南大学 35 62 5 2 1 定长编码定理 反之 当 时 不可能实现无失真编码 而当 时 为临界状态 可能无失真