信息论2015-5分析.ppt

4.3.3 Huffman算法 ⑵q元Huffman算法 【例4-7】设单符号离散无记忆信源的信源空间 对其进行 q=3，A: {0, 1, 2}的Huffman编码。 解：如果按上面介绍的通常的二元Huffman编码方法进行编码，其过程如图 可知：平均码长为 =2 码元/信源符号。 * S: s1 s2 s3 s4 s5 s6 p(S): 0.24 0.20 0.18 0.16 0.14 0.08 s1 s2 s3 s4 s5 s6 0.24 0.20 0.18 0.16 0.14 0.08 1 2 0 (0.38) 0 2 1 (0.62) 1 2 (1.0) W1=10 W6=11 W7=12 W5=20 W4=21 W8=22 4.3.3 Huffman算法 通过直观的观察，这种编码方法似乎不是最佳的，下面我们看看一种改进方法。 还是这一个信源，我们在6个信源符号的后面再加一个概率为0的符号，记为s7’，同时有p(s7’)=0，这个符号称为虚假符号，如果将此信源按7个符号进行三元编码，其编码过程如图 计算可知这种编码方法的平均码长为 =1.76 码元/信源符号。可以看到通过这种增加虚假符号的方法可以提高q元Huffman编码的编码效率。 * s1 s2 s3 s4 s5 s6 s7’ 0.24 0.20 0.18 0.16 0.14 0.08 0.0 1 2 0 (0.22) 0 2 1 (0.54) (1.0) W1=1 W2=00 W3=01 W4=02 W5=20 W6=21 W7’=22 1 2 0 解释两个问题 一、在推导连续信道的转移概率等于噪声概率密度函数的时候，坐标变换及雅克比行列式计算的问题。 根据概率理论有 对于一维AWGN连续信道模型我们分析 概率p(x,y), p(y/x), p(n), p(x)的关系。 * 解释两个问题 二、为什么对于N维连续信道模型[X, p(y/x), Y]，当加性高斯白噪声信道n=[n1,n2,…,nN]是无记忆的，仍然有 原因是有这样的定理。 定理1：对于N维连续无记忆信源（即X=[X1,X2,…,XN]个分量统计独立），则有 定理2：对于N维连续无记忆信道（即n=[n1,n2,…,nN]个分量统计独立），则有 定理3：对于N维连续无记忆信源和N维连续无记忆信道，则有 * 多维信息量大于等于一维信息量之和，当信道也无记忆时等号成立。 多维信息量小于等于一维信息量之和，当信源也无记忆时等号成立。 第四章 信源编码与率失真函数 4.1 离散信源编码 4.2 无失真信源编码定理 4.3 Huffman编码 4.4 率失真函数 * 4.1 离散信源编码 4.1 离散信源编码 * 通信系统的有效性最直观的体现方式就是信息传输速率，也就是单位时间内传递的信息量。 信息传输速率主要取决于三个方面的因素，分别是符号速率，信源熵和噪声熵。根据通信理论的知识我们知道，符号速率与信道带宽有关，一般根据应用需求来确定，噪声熵与信道条件有关，由应用环境确定，而且两者也与系统成本有关。 提高信源熵是提高通信系统有效性的一个重要途径。这里所说的提高信源熵是指提高信源单位符号所携带的信息量。 信息理论的研究表明，通过编码（某种变换）可以达到提高信源熵的目的，这类编码我们称为信源编码。 本章的主要内容就是介绍信源编码的基本原理和基本方法，包括无失真信源编码，限失真信源编码及信源编码定理。 4.1.1 编码器 编码器可以看作这样一个系统，编码器的输入端为原始信源S，其符号集为S:{s1,s2,…,sn}。而信道所能传输的符号集为A:{a1,a2,…,aq}；编码器的功能是用符号集A中的元素，将原始信源的符号si变换为相应的码字符号Wi (i=1,2,…,n)。因此，编码器输出端的符号集为W:{W1,W2,…,Wn}。 可以看出，编码器就是建立一种一一对应的映射关系，将原始信源符号集S中的符号变换为由信道码元符号集A的符号所构成的码字符号集W的符号。 * 4.1.1 编码器 信道输出的码字符号集W也称为码组，码组中的元素成为码字，每个码字由可能不同个数的A集合中的元素组成，称为码元。每个码字可以表示为 其中，Li为码字Wi所包含码元的个数，称为码字Wi的码字长度，简称码长。 当码组W中的所有码字的码长相等时，我们称其为等长码，否则称为不等长码。 q=2时，称为二元编码，否则称为q元编码。 * 4.1.2 单义可译码 定义4-1：如果一个码组的任一有限长的码字序列（一串码字），只能唯一地被译成一个一个码字，则称其为单义可译码，也称异前置码。 例如：S: {s1,s2,s3}；A:{0,1}；W: {w1=0, w2=