无失真信源编码 定理 通信的实质是信息的传输 而高效率 高质量地传送 信息却又是信息传输的基本问题 将信源信息通过信道传输给信宿 怎样才能做到尽 可能不失真而又快速呢 这就要解决两个问题 第一 在不失真或允许一定失真条件下 如何尽 可能少的符号来表示信源信息 以便提高信息传 输率 第二 在信道受干扰的情况下 如何增加信号的 抗干扰能力 提高信息传输的可靠性 同时又使 得信息传输率最大 为此 我们引入信源编码和信道编码 一般来说 提高抗干扰的能力 降低失真或错误概 率 往往是增加冗余度以降低信息传输率为代价 的 反之 要提高信息传输率往往通过压缩信源的 冗余度来实现而常常又会使抗干扰能力减弱 二者 是有矛盾的 然而在信息论的编码定理中 已从理论上证明 至 少存在某种最佳的编码或信息处理方法 能够解决 上述矛盾 做到既可靠又有效地传输信息 这些结论对各种通信系统的设计个估价具有重大的 理论指导意义 本章将重点讨论对离散信源进行无失真信源 编码的要求 方法以及理论极限 并得出一 个极为重要的极限定理 香农第一定理 目录 5 1编码器 5 2 等长码 5 3渐进等分割性和 典型序列 5 4等长信源编码定理 5 4变长码 5 变长信源编码定理 5 1 编码器 编码实质上是对信源的原始符号按照一定的数学规 则进行一种变换 为了分析方便和突出问题的重点 当研究信源编码 时 我们将信道编码和译码看成是信道的一部分 而突出信源编码 同样 研究信道编码时 将信源 编码和译码看成是信源和信宿的一部分 突出信道 编码 图5 1无失真信源编码器 编码器 S s1 s2 sq C W1 W2 Wq X x1 x2 xr Wi是由li个xj xj X 组成的序 列 并与si一一对应 上述模型中 输入符号集S s1 s2 sq 同时存 在另一符号集X x1 x2 xr 一般元素xj是适合 信道传输的 称为码符号 或者码元 编码器是将信源符号集中的符号si 或者长为N的 信源符号序列 i 变换成由xj j 1 2 r 组成 的长度为li的一一对应序列 即 1 1 21 lkXxxxxWqis k i l iiiiii 2 1 2 1 2 1 2121 iii N iiiiiiii lkXxNkSs qixxxWsss kk i lN 或者 这种码符号序列Wi 称为码字 长度li称为码字长 度或简称码长 所有这些码字的集合C称为码 或 称码书 此码为r元码或称r进制码 编码就是从信源符号到码符号的一种映射 若要实现无失真编码 必须这种映射是一一 对应的 可逆的 二元码 若码符号集为X 即r 2 所得码字就是 一些二元序列 则称为二元码 或称二进制码 若将信源通过一个二元信道进行传输 为使信源适 合信道传输 就必须把信源符号变换成0 1符号组成 的码符号序列 二元序列 这种编码所得的码为二 元码 二元码是数字通信和计算机系统中最常用的一种 码 等长码 若一组码中所有的码字的码长都相同 即 li l i 1 2 q 则称为等长码 变长码 若一组码中所有的码字的码长各不相同 即 任意码字由不同长度li的码符号序列组成 则称为变长码 非奇异码 若一组码中所有的码字都不相同 即所有信源符 号映射到不同的码符号序列 CWWSssWWss jijijiji CWWSssWWss jijijiji 则称码C为非奇异码 若一组码中有相同的码字 即 奇异码 则称码C为奇异码 同价码 若码符号集X x1 x2 xr 中每个码符号xi所占的 传输时间相同 则所得的码C为同价码 一般二元码是同价码 本章讨论的都是同价码 对 同价码来说 等长码中每个码字的传输速度都相 同 而变长码中每个码字的传输时间就不一定相 同 电报中用的莫尔斯码是非同价码 其码符号点 和划 所占的传输时间不相同 码的N次扩展码 假定某码C 它把信源S中的符号si一一变换成码C 中的码字Wi 则称码C的N次扩展码是所有N个码字 组成的码字序列的集合 XxxxxWSs i l i l iiiiii 21 若码C W1 W2 Wq 其中 则N次扩展码 N Niiii qi qiiiWWWB B N 1 1 21 21 可见 码C的N次扩展码B中 每个码字Bi i 1 2 qN 与N次扩展信源SN中每个信源序列符号 i一一对应 而 21N iiii sss 举例 设信源S的概率空间为 1 121 21 q i i q q sP sPsPsP sss sP S 若把它通过一个二元信道进行传输 为使信源适合 信道传输 就必须把信源符号si变换成0 1符号组成 的码符号序列 二元序列 我们可以采用不同的 二元序列使其与信源符号si一一对应 这样就得到 不同的二元码 表 信源符号si符号概率P si 码 码 s1P s1 000 s2P s2 0101 s3P s3 10001 s4P s4 11111 码 是等长非奇异码 码 是变长非奇异码 N次扩展码 我们可以求得表5 1中码 和码 的任意N次扩展 码 例如求码 的二次扩展码 因为信源S的二次扩展信源 S2 1 s1s1 2 s1s2 3 s1s3 16 s4s4 所以码 的二次扩展码为 信源符号码字信源符号码字信源符号码字 00 W1W1 B1 5 010 W2W1 B5 001 W1W2 B2 0001 W1W3 B3 0111 W1W4 B4 16 111111 W4W4 B16 惟一可译码 若码的任意一串有限长的码符号序列只能被惟一地 译成所对应的信源符号序列 则此码称为惟一可译 码 或单义可译码 否则称为非惟一可译码或非单 义可译码 若要所编的码是惟一可译码 不但要求编码时不同 的信源符号变换成不同的码字 而且还要求任意有 限长的信源序列所对应的码符号序列各不相同 即 要求码的任意长N次扩展码都是非奇异码 因为只 有任意有限长的信源序列所对应的码符号序列各不 相同 才能把该码符号序列唯一地分割成一个个对 应的信源符号 从而实现惟一地译码 所以 某码的任意有限长N次扩展码都是非奇异 码 则该码为唯一可译码 例如 表5 1中码 是惟一可译码 而码 是 非惟一可译码 因为对于码 其有限长的码符号序列能译 成不同的信源符号序列 如 0010 可译成 s1s2s1或s3s1 显然不是惟一的 下面 我们分别讨论等长码和变长码的最佳 编码问题 也就是是否存在一种惟一可译编 码方法 使平均每个信源符号所需的码符号 最短 也就是无失真信源压缩的极限值 5 2 等长码 一般来说 若要实现无失真的编码 这不但要求信源 符号si i 1 2 q 与码字Wi i 1 2 q 是一一 对应的 而且要求码符号序列的反变换也是惟一的 所编的码必须是惟一可译码 否则 所编的码不具有 惟一可译码性 就会引起译码带来的错误与失真 对于等长码来说 若等长码是非奇异码 则它的任意 有限长N次扩展码一定也是非奇异码 因此等长非奇异码一定是惟一可译码 表5 2 等长码 信源符号码1码2 s1 s2 s3 s4 00 01 10 11 00 11 10 11 在上表中 码2不是惟一可译码 比如11 码1是等长非奇异码 所以是惟一可译码 若对信源进行等长编码 则必须满足 1 5 l rq 式中 l是等长码的码长 r是码符号集中码元数 例如表5 2中 信源S共有q 4个信源符号 现进行 二元等长编码 其中码符号个数为r 2 根据式 5 1 可知 信源S存在惟一可译等长码的条件是 码长l必须不小于2 如果我们对信源S的N次扩展信源进行等长编码 设信源 有q个符号 那么它的N次 扩展信源共有qN个符号 其中 是长度 为N的信源符号序列 21q sssS 21 N q N S 2 1 21 NkSssss kN iiiii 设码符号集为 21r xxxX 现在需要把这些长为N的信源符号序列 变换成长度为l的码符号序列 1 N i qi 121 XxxxxxW ll iiiiii 根据前面的分析 若要求得编得的等长码是惟一 可译码则必须满足 2 5 lN rq 此式表明 只有当l长的码符号序列数 rl 大于或 等于N次扩展信源的符号数 qN 时 才可能存在等 长非奇异码 对式 5 2 两边取对数 则有 r q N l log log 是平均每个信源符号所需要的码符号个数 N l 对于等长惟一可译码 每个信源符号至少需要用 个码符号来变换 r q log log 当r 2 logr 1 则 q N l log 这结果表明 对于二元等长惟一可译码 每个信源符 号至少需要logq个二元符号来变换 这也表明 对信源进行二元等长不失真编码时 每个 信源符号所需要码长的极限值为logq个 英文符号至少需要5个二元符号编码才行 是不是可以用更少的符号表示 是 接下来的例子说明为什么每个信源符号平均所需 的码符号个数可以减少 设信源 4 14321 4321 1 i i sP sPsPsPsP ssss sP S 而其依赖关系为P s1 s2 P s2 s1 P s3 s4 P s4 s3 1 其余P sj si 0 若不考虑符号之间依赖关系 此信源q 4 那么 进行 等长二元编码 由前面可知 l 2 若考虑符号之间依赖关系 此特殊信源的二次扩展 信源为 4 3 2 1 1 34431221 34431221 2 jissPsPssP ssP ssPssPssPssP ssssssss ssP S ijiji ij ji ji 又 由上述依赖关系可以知道 除了P s1 s2 P s2 s1 P s3 s4 P s4 s3 不等于0 其余sisj出现的概率皆为0 因此二次扩展信源S2由16个符号缩减到4个符号 因 此对它进行等长编码 所需码长仍为l 2 由此可见 当考虑信源符号之间依赖关系后 有 些信源符号序列不会出现 这样信源符号序列 个数会减少 再进行编码时 所需平均码长就可 以缩短 英文 等长编码定理给出了信源进行等长编码所需 码长的理论极限值 5 3 渐进等分割性和 典型序列 渐近等分割性指出 随机变量S1 S2 SN独立同分 布 联合概率为P S1S2 SN 只要N足够大 N个 变量自信息的平均值接近于信息熵 H S 自信息的数学期望 n i i X n 1 1 log 1 21N SSSP N 2 SNH log 1 SSlogP S N 1 1 N21 n i i SP N 注意 渐进等分割性AEP是弱大数定理的直接推论 大数定理 若X1 X2 Xn是独立同分布的随机变 量 只要n足够大 接近于数学期望E X 即 P S1S2 SN 接近于 定理5 1 渐近等分割性 若随机序列S1S2 SN相互独立并且都 服从同一概率分布P s 则 q q PPP sss P S 21 21 对离散无记忆信源 1 1 q i i P SN S1S2 SN 为其N次扩展信源 表示扩展信源 21N iiii sss log 1 log 1 21N iiii sssP N P N 依概率收敛于H S 也就是N足够大时 N个变量自信息的平均值接 近于信息熵H S 自信息的数学期望 1 21N iii sssP N 即 对任意 0 有 的输出 1 log 1 lim SHP N P i N 典型序列 定义 N长的序列 对于任意小的正数 满足 N iiii Ssss N 21 log 1 SHP N i 则称 为 典型序列 i 反之 若满足 则称为 非典型序列 log 1 SHP N i i 记 log 1 0 0 当N足够 大时 则 N GP 1 1 N GP 2 若 Niiii Gsss N 21 则 2 2 SHN i SHN P 3 设 N G 表示 N G 中 典型序列的个数 则有 2 2 1 SHN N SHN G 该定理指出 N次扩展信源中信源序列可分为两类 一类是 典 型序列 它是经常出现的 N趋于无穷大时 出现的概率接近于 1 且每个序列出现的概率接近于2 NH S 另一类是 非典型序 列 其出现的概率很低 随N的增大 出现