信息论06.ppt

分析： 完全依赖于 ，则 完全依赖 于 ，对于由 m 个符号构成的状态而言，为有限齐 次的马尔可夫链，相应的信源称为 m 阶马尔可夫信 源。 m 阶马尔可夫信源的输出序列可以看作关于状态 的一阶马尔可夫链。其状态总数为 。 M阶马尔可夫信源的熵率 2.2 马尔可夫信源的熵率 遍历齐次稳恒的m阶马尔可夫链的熵率为： 有限齐次的马尔可夫链统计特性的状态转移图表示 状态：过渡态，吸收态，常返态，周期性，遍历态 到达：如果状态 经过若干步后总能到达状态 即存在 二态相通：若两个状态相互可到达，称此二态相通。 过渡态：若从某一个状态经过若干步后总能到达某一其他状态，但不能返回，则称此状态为过渡态。 常返态：经过有限步后总能返回的状态。 闭集：设 C 为状态空间的一个子集，如果从 C 内 任何一个状态不可能 C 外的任何一个状态，则称 C 为闭集。 不可约性：如果马尔可夫链的状态空间是闭集，而 任何子集为非闭集，则称马尔可夫链是不可约的。 周期性： 非周期性： 从状态转移图可以判断马尔可夫链是否具有遍历性。 遍历的马尔可夫链： 不可约的，非周期的，有限状态的马尔可夫链。 注：用于信源建模的马尔可夫链一般都是各态历经的。 例：信源由二进制2阶马尔可夫链描述，且符号的条件转移概率为： 状态转移图： 状态的概率转移矩阵： 00 01 － － － － 10 11 00 01 － － － － 10 11 0 0 1 1 2.3 最优编码 编码 按 得最优编码方法： 由 确定状态。 对每个状态 i，分别按 作最优变长编码。 即按条件概率 进行编码。 马尔可夫信源的最优编码，就是按条件概率进行 的最优编码，所以也可简称条件编码。 编码器 单符号信源 N次扩展信源 N长 共有KN个 M长 共有JM个 单个符号 共有K个 M长 共有JM个 变长编码 等长信源编码定理 编码器 单符号信源 N次扩展信源 变长编码 变长信源编码定理 Kraft理 任何一个离散随机序列信源当序列长度N→∝时,信源序列会产 生两极分化.大概率事件集合 与小概率事件集合 ,即KN= ∪ 对于 有性质: ①???????? ②???????? ③? 对于 有性质: 渐进等分割性 信源序列集合 物理意义： 又称无噪信道编码定理 编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大 要做到无失真编码，变换每个信源符号平均所需最少的J元码元数就是信源的熵率 信源的熵率是描述信源每个符号平均所需最少的比特数 定理说明： 是存在性定理－－具有理论指导意义 是构造性定理－－设计出多种具体编码方法 Shannon 第一定理 1/2=0.5 1/4 =0.25, 1/8=0.125 0.39 1/2=0.5, 小数点后第一位0 0.39 1/4 =0.25,小数点后第一位1 0.39-0.25=0.14 1/8=0.125,小数点后第一位1 0.39=(0.011…)2 香农编码方法 费诺编码方法 Fano编码是前缀码， 不一定是最优码 1. 信源的最优变长编码 1.1 最优码及其特性 1.2 编码方法—— Huffman 码 1.3 其他编码方法 2. 马尔可夫信源的熵率与最优编码 2.1 马尔可夫信源 2.2 马尔可夫信源的熵率 2.3 最优编码 第三章 信源熵率、冗余度与冗余度压缩编码 1.1 编码方法—— Huffman码 最优前缀码－用缩减信源构造最优码 特点： 码长与符号概率大小匹配 缩减信源的最后两个符号的码字长度相同，区别只在最后位 平均码长： 霍夫曼编码方法 （解法二）但组合的方法和解法一有所不同，所得编码过程和编码结果，如下图 霍夫曼编码方法 最优前缀码长的界 1.2