《信息论与编码原理_第6章_信源编码》由会员分享，可在线阅读，更多相关《信息论与编码原理_第6章_信源编码（91页珍藏版）》请在金锄头文库上搜索。
1、信息论与编码原理（第六章） 信源编码Date1Department of Electronics and Information, NCUT Song Peng第六章 信源编码6.1 引 言6.2 香农编码6.3 费诺编码6.4 哈夫曼编码6.8 LZW 码6.7 LZ 码6.6 算术编码6.5 游程编码6.9 信源编码总结Date2Department of Electronics and Information, NCUT Song Peng6.1 引 言6.1.1 编码的目的6.1.2 信源编码概论Date3Department of Electronics and Informatio
2、n, NCUT Song Peng6.1.1 编码的目的香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法；编码理论正是为了解决这一问题而发展起来的科学理论；编码的目的是为了优化通信系统，使这些指标达到最佳；通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指标正是信息论研究的对象。按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码（密码）。6.1 引 言Date4Department of Electronics and Information, NCUT Song Peng6.1.1 编码的目的信源编码：提高通信有效性为目的的编
3、码。通常通过压 缩信源的冗余度来实现。采用的一般方法是压缩 每个信 源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从 而提高通信的有效性。信道编码：提高信息传输的可靠性为目的的编码。通常 通过增加 信源的冗余度来实现。采用的一般方法是增大 码率（带宽）。与信源编码正好相反。保密编码：提高通信系统的安全性为目的的编码。通常 通过加密和解密来实现。从信息论的观点出发，“加密”可 视为增熵的过程，“解密”可视为减熵的过程。返回目录6.1 引 言Date5Department of Electronics and Information, NCUT
4、Song Peng6.1.2 信源编码概述(1) 信源编码的理论基础信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。6.1 引 言Date6Department of Electronics and Information, NCUT Song Peng6.1.2 信源编码概述(2) 信源编码的分类根据信源特性q离散信源编码：独立信源编码，可做到无失真编码；q连续信源编码：独立信源编码，只能做到限失真信源编码；q相关信源编码：非独立信源编码。根据压缩的特性q冗余度压缩编码
5、：可逆压缩，经编译码后可以无失真地恢复。q熵压缩编码：不可逆压缩。 6.1 引 言Date7Department of Electronics and Information, NCUT Song Peng6.1.2 信源编码概述(3) 数据压缩概貌KLT：Karhunen-Loeve TransformDCT：Discrete Cosine TransformDST：Discrete Sinusoid TransformDFT：Discrete Fourier TransformWHT：Walsh-Hadamard TransformSLT：Slant TransformHAAR：Haar
6、TransformLPC-10：Government Standard Linear Predictive Coding Algorithm: LPC-10MELP：Mixed Excited Linear Predictive CodingCELP：Codebook Excited Linear Predictive Coding ACELP：Algebraic Cocebook Excitation LPCQCELP：Qualcom Cocebook Excitation LPCEVRC：Enhanced Variable Rate CodecLD-CELP：Low Delay-CELP2
7、8 种6.1 引 言Date8Department of Electronics and Information, NCUT Song Peng6.1.2 信源编码概述(3) 数据压缩概貌CS-ACELP：Conjugate-Structure Algebraic CELPVSELP：Vector Sum Excitation LPC RPE-LT：Long Time Predictive Regular-Pulse Excitation LPCMPLPC：Multi-Pulse Excitation LPC MP-MLQ：Multipulse Maximum Likelihood Quant
8、izationMBE：Multi-Band Excitation Speech CoderSTC：Sinusoid Transform CocingCVSD：Continuously Variable Slope Delta ModulatorSB-ADPCM：Sub-Band Adaptive Differential Pulse Code Modulation PTC：PictureTel Transform CoderAC-2；AC-3：Digital Audio Compression Standard，美国 Dolby公司AAC：Advanced Audio Coding, 日本13
9、8187, MPEG-2 MUSICAM：Masking Pattern Adapted Universal Subband Integrated Coding and MultiplexingATRAC：Adaptive Transform Acoustic Coder6.1 引 言Date9Department of Electronics and Information, NCUT Song Peng6.1.2 信源编码概述(3) 数据压缩概貌6.1 引 言Date10Department of Electronics and Information, NCUT Song Peng6.1
10、.2 信源编码概述有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如：返回目录连续信源编码：脉冲编码调制 (PCM)、矢量量化技术相关信源编码： 预测编码：增量编码、差分脉冲调制 (DPCM)、自 适应差分脉冲调制(ADPCM)、线性预测声码器； 变换编码：KL 变换、离散变换、子带编码、小波变换。6.1 引 言Date11Department of Electronics and Information, NCUT Song Peng6.2 香农编码 设离散无记忆信源： 二进制香农码的编码步骤如下：q 将信源符号按概率从大到小的顺序排列，为方便起见，令： p(x1) p(x2
11、) p(xn)q 令 p(x0)=0，用 pa(xj)，j=i+1 表示第 i 个码字的累加概率，则：Date12Department of Electronics and Information, NCUT Song Peng6.2 香农编码 设离散无记忆信源： 二进制香农码的编码步骤如下：q 确定满足下列不等式的整数 ki ，并令 ki 为第 i 个码字的长度log2 p(xi) ki 0(i=1,2, ,n)信源符号的累积分布函数为：所得累积分布函数为每台级的下界值，则其区间为 0,1) 左闭右开区间。F(a1)=0F(a2)=P(a1)F(a3)=P(a1)+P(a2)当 A=0,1二
12、元信源时： F(0)=0F(1)=P(0)6.6 算 术 编 码Date57Department of Electronics and Information, NCUT Song Peng6.6.2 累积分布函数 F(s) 及对应的区间 计算二元无记忆信源序列的累积分布函数q 初始时：在 0,1) 区间内由 F(1) 划分成二个子区间 0,F(1) 和 F(1),1)，F(1)= P(0)。 子区间 0,F(1) 的宽度为：A(0)= P(0)，对应于信源符号“0”； 子区间 F(1),1) 的宽度为：A(1)= P(1)，对应于信源符号“1”； 若输入符号序列的第一个符号为 s=“0”，落
13、入0,F(1)区间，得累积分布函数 F(s=“0”)= F(0)=0； 图示6.6 算 术 编 码Date58Department of Electronics and Information, NCUT Song Peng6.6.2 累积分布函数 F(s) 及对应的区间 计算二元无记忆信源序列的累积分布函数q 输入第二个符号为“1”，s=“01” s=“01”所对应的区间是在区间 0,F(1) 中进行分割； 符号序列“00”对应的区间宽度为： A(00)=A(0)P(0)=P(0)P(0)=P(00)对应的区间为：0,F(s=“01”) 符号序列“01”对应的区间宽度为： A(01)=A(0
14、)P(1)=P(0)P(1)=P(01)对应的区间为：F(s=“01”),F(1) 累积分布函数 ：F(s=“01”)=P(0)P(0)= P(00)图示6.6 算 术 编 码Date59Department of Electronics and Information, NCUT Song Peng6.6.2 累积分布函数 F(s) 及对应的区间 计算二元无记忆信源序列的累积分布函数q 输入第三个符号为“1”： 输入序列可记做 s1=“011” ，对应的区间是对区 间 F(s),F(1) 进行分割； 序列 s0=“010” 对应的区间宽度为：A(s=“010”)=A(s=“01”)P(0)=
15、A(s)P(0)其对应的区间为：F(s), F(s)+ A(s)P(0) 序列 s1=“011” 对应的区间宽度为： A(s=“011”)=A(s)P(1)其对应的区间为：F(s)+A(s)P(0),F(1) 符号序列 s1=“011”的累积分布函数为： F(s1)=F(s)+A(s)P(0) 若第三个符号输入为“0”，符号序列s0=“010”的 区间下界值仍为F(s)，得符号序列 s0=“010”的累积分布函 数为F(s0)=F(s)。图示6.6 算 术 编 码Date60Department of Electronics and Information, NCUT Song Peng6.6
16、.2 累积分布函数 F(s) 及对应的区间 计算二元无记忆信源序列的累积分布函数q 归纳 当已知前面输入符号序列为 s，若接着再输入一个符号“0”，序列 s0 的累积分布函数为：F(s0)=F(s) 对应区间宽度为：A(s0)=A(s)P(0) 若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0) 对应区间宽度为：A(s1)=A(s)P(1)图示6.6 算 术 编 码Date61Department of Electronics and Information, NCUT Song Peng6.6.2 累积分布函数 F(s) 及对应的区间 计算二元无记忆信源序列的累积分布函数q 归纳 符号序列对应的区间宽度A(s=“0
