信息导论-第12讲-信源编码1.pptVIP

第五章 信源编码 5.1 引言 5.2 香农编码 5.3 费诺编码 5.4 哈夫曼编码 5.5 游程编码 5.6 冗余编码 5.7 信源编码总结 5.1.1 编码的目的 香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法； 编码理论正是为了解决这一问题而发展起来的科学理论； 编码的目的是为了优化通信系统，就是使这些指标达到最佳； 通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指标正是信息论研究的对象。 按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码/密码。 5.1.1 编码的目的 信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。 5.1.2 信源编码概述 信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。 5.1.2 信源编码概述 有些编码原理和技术在相关课程中已经介绍过。例如： 连续信源编码：脉冲编码调制(PCM)、矢量量化技术； 相关信源编码： 预测编码：增量编码、差分脉冲调制(DPCM)、自适应差分脉冲调制(ADPCM)、线性预测声码器； 变换编码：K－L变换、离散变换、子带编码、小波变换。 5.2 香农编码 设离散无记忆信源 二进制香农码的编码步骤如下： 将信源符号按概率从大到小的顺序排列，为方便起见，令 p(x1)≥ p(x2)≥…≥ p(xn) 令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则 5.2 香农编码 确定满足下列不等式的整数ki ，并令ki为第i个码字的长度 －log2 p(xi)≤ki1－ log2 p(xi) 将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。 5.2 香农编码 [例5.1.1]有一单符号离散无记忆信源 对该信源编二进制香农码。 5.2 香农编码 计算出给定信源香农码的平均码长 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。 5.2 香农编码 由离散无记忆信源熵定义，可计算出： 对上述信源采用香农编码的信息率为 编码效率为信源熵和信息率之比。则 5.3 费诺编码 费诺编码也是一种常见的信源编码方法。 1. 将概率按从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) 2. 按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。 3. 给每一组分配一位码元。 4. 将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。 [例5.3.1] 设有一单符号离散信源 对该信源编二进制费诺码。 上述码字还可用码树来表示，如图5.2.1所示。 该信源的熵为 平均码长为 编码效率为 本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。 [例5.3.2] 有一单符号离散无记忆信源 对该信源编二进制费诺码。 码树图如图5.3.2。 信源熵为 H(X)=2.75(比特/符号) 平均码长为 编码效率为η=1。之所以如此，因为每次所分两组的概率恰好相等。 5.4 哈夫曼编码 哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。 5.4.1 编码步骤 5.4.2 二进制哈夫曼编码 5.4.3 m进制哈夫曼编码 5.4.1 编码步骤 1. 将信源符号按概率从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) 2. 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 3. 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，