资源预览内容
第1页 / 共95页
第2页 / 共95页
第3页 / 共95页
第4页 / 共95页
第5页 / 共95页
第6页 / 共95页
第7页 / 共95页
第8页 / 共95页
第9页 / 共95页
第10页 / 共95页
亲,该文档总共95页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
无失真信源编码 定理 通信的实质是信息的传输 而高效率 高质量地传送 信息却又是信息传输的基本问题 将信源信息通过信道传输给信宿 怎样才能做到尽 可能不失真而又快速呢 这就要解决两个问题 第一 在不失真或允许一定失真条件下 如何尽 可能少的符号来表示信源信息 以便提高信息传 输率 第二 在信道受干扰的情况下 如何增加信号的 抗干扰能力 提高信息传输的可靠性 同时又使 得信息传输率最大 为此 我们引入信源编码和信道编码 一般来说 提高抗干扰的能力 降低失真或错误概 率 往往是增加冗余度以降低信息传输率为代价 的 反之 要提高信息传输率往往通过压缩信源的 冗余度来实现而常常又会使抗干扰能力减弱 二者 是有矛盾的 然而在信息论的编码定理中 已从理论上证明 至 少存在某种最佳的编码或信息处理方法 能够解决 上述矛盾 做到既可靠又有效地传输信息 这些结论对各种通信系统的设计个估价具有重大的 理论指导意义 本章将重点讨论对离散信源进行无失真信源 编码的要求 方法以及理论极限 并得出一 个极为重要的极限定理 香农第一定理 目录 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的增大 出现
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号