信息基础与编码理论 第四章.ppt

信息论与编码Information Theory Coding 第四章????? 离散信源的信源编码 为什么要对进行编码？ 1. 信源发出的消息符号可能不适合信道的传输。将信 源发出的消息符号转换为适合信道传输的符号。 2. 信源消息确定后，提高通信的有效性--信源编码。 3. 提高通信的可靠性 , 编码具有发现错误或纠正错误 的抗干扰能力---信道编码 。 4. 提高通信的安全性---加密编码。 4.1 信源编码的基本概念 ? 4.1.1 信源的符号集和符号序列 1°信源符号集:信源发出的符号消息的集合，记为X； 设 X 有n个符号：X ={ x1 , x2 , … , xn } 2°信源符号序列:由信源符号集合 X 中的符号组成长度 为L的符号序列，记为 L为信源符号序列长 , 不同的符号序列共有 nL 若L=1，则信源符号序列为信源符号集合中的符号. 4.1.2 码元和码字 1°码元(符)集 信道可传输的基本符号的集合, 记为Y; 设 Y 有m个符号： Y={ y1 , y2 , … , ym } 其中 y i 称为码元或码符. m 元信道: 可传输m个基本符号的信道； 二元信道: 可传输 2个基本符号的信道. 这是一种最常用的信道, 其基本符号常用 0 , 1 表示. 2° 码字: 由码元组成的序列称为码字，记为Y i 码字Y i 的码元个数 Ki 称为Y i的码长. 所有码字Y i 的码长 Ki 均相等称为码长为 K 定长码. 码字Y i 的码长 Ki 不全相等称为变长码. 4.1.3 编码与译码 1°信源编码：将信源符号 xi 或符号序列 XLi 按一种规则 映像成码字Y i的过程。 2°无失真编码：信源符号到码字的映射必须一一对应。 3°译码：从码符号到信源符号的映射。 4°码表：所有映射规则的集合. 4.1.4 许用码和禁用码 1°许用码字：信源的符号xi或符号序列XLi与码字Y i定义 了对应关系的码字。 2°禁用码字：信源的符号xi或符号序列XLi与码字Y i未定 义对应关系的码字。 3°许用码字的全体称为码集。 4.1.5 分组码（块码）分类 ?1°按码字的码长分类 定长码：码集中所有码字的码长相等。 变长码：码集中所有码字的码长不全相等。 ?2°按信源符号与码字对应关系分类 非奇异码：信源符号与码字是一一对应的。 奇异码：信源符号与码字不是一一对应的。 ?3°按译码唯一性分类 唯一可译码：对于多个码字组成的有限长码流，只能 唯一地分割一个个的码字。唯一可译码又称为单义码. 例 码流 100111000 … 码1 x1→0 x2→10 x3→11 可分割10, 0, 11, 10, 0, 0 码2 x1→1 x2→10 x3→11 则无法唯一分割 唯一可译码在传输过程中不需要同步码。 非唯一可译码：对有限长码流，不能唯一地分割一个个的码字。 4°按译码的即时性分类 非即时码：接收端收到一个完整的码字后，不能立即 译码；还需要等到下一个码字开始接收后才能判断是 否可以译码; 又称为延长码。 即时码：接收端收到一个完整的码字后，就能立即译 码；即时码又称为非延长码或异前缀码。 例 非即时码 码流 … x1→0 x2→01 x3→11 译码为 x2, x1, x1, x3, x1, x1 即时码 码流 … x1→0 x2→10 x3→11 译码为 x1, x2, x1, x3, x1, x1 异前缀码(即时码)指的是码集任何一个码不能是其他码 的前缀. 即时码必定是唯一可译码, 唯一可译码不一定是即时码. 5°有实用价值的分组码 分组码是非奇异码、唯一可译码、即时码 4.1.6 码树图 1°码树图: 用码树来描述给定码集各码字的方法. 2°码树图有树根、树枝、叶节点： 中间节点（一级节点、二级节点… ）用○表示, 终端节 点用●表示 3°传输m个