《信息论与编码原理第6章信源编码》由会员分享,可在线阅读,更多相关《信息论与编码原理第6章信源编码(91页珍藏版)》请在金锄头文库上搜索。
1、第1页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,信息论与编码原理,(第六章) 信源编码,第2页,2019/1/20,Department 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 信源编码总结,第3页,2019/1/20,Department of Electronics and
2、 Information, NCUT Song Peng,6.1 引 言,6.1.1 编码的目的,6.1.2 信源编码概论,第4页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.1 编码的目的,香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法; 编码理论正是为了解决这一问题而发展起来的科学理论; 编码的目的是为了优化通信系统,使这些指标达到最佳; 通信系统的性能指标主要是有效性、可靠性、安全性和经济性,除了经济性外,这些指标正是信息论研究的对象。 按不同的编码目的,编
3、码分为三类:信源编码、信道编码和安全编码(密码)。,6.1 引 言,第5页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.1 编码的目的,信源编码:提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩 每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。 信道编码:提高信息传输的可靠性为目的的编码。通常通过增加 信源的冗余度来实现。采用的一般方法是增大码率(带宽)。与信源编码正好相反。 保密编码:
4、提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发,“加密”可视为增熵的过程,“解密”可视为减熵的过程。,返回目录,6.1 引 言,第6页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.2 信源编码概述,(1) 信源编码的理论基础 信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。 无失真信源编码定理:是离散信源/数字信号编码的基础; 限失真信源编码定理:是连续信源/模拟信号编码的基础。,6.1 引 言,第7页,2019/1/20,Department
5、 of Electronics and Information, NCUT Song Peng,6.1.2 信源编码概述,(2) 信源编码的分类 根据信源特性 离散信源编码:独立信源编码,可做到无失真编码; 连续信源编码:独立信源编码,只能做到限失真信源编码; 相关信源编码:非独立信源编码。 根据压缩的特性 冗余度压缩编码:可逆压缩,经编译码后可以无失真地恢复。 熵压缩编码:不可逆压缩。,6.1 引 言,第8页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.2 信源编码概述,(3) 数据压缩概貌
6、KLT:Karhunen-Loeve Transform DCT:Discrete Cosine Transform DST:Discrete Sinusoid Transform DFT:Discrete Fourier Transform WHT:Walsh-Hadamard Transform SLT:Slant Transform HAAR:Haar Transform LPC-10:Government Standard Linear Predictive Coding Algorithm: LPC-10 MELP:Mixed Excited Linear Predictive Co
7、ding CELP:Codebook Excited Linear Predictive Coding ACELP:Algebraic Cocebook Excitation LPC QCELP:Qualcom Cocebook Excitation LPC EVRC:Enhanced Variable Rate Codec LD-CELP:Low Delay-CELP,28 种,6.1 引 言,第9页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.2 信源编码概述,(3) 数据压缩概貌 CS-A
8、CELP:Conjugate-Structure Algebraic CELP VSELP:Vector Sum Excitation LPC RPE-LT:Long Time Predictive Regular-Pulse Excitation LPC MPLPC:Multi-Pulse Excitation LPC MP-MLQ:Multipulse Maximum Likelihood Quantization MBE:Multi-Band Excitation Speech Coder STC:Sinusoid Transform Cocing CVSD:Continuously V
9、ariable Slope Delta Modulator SB-ADPCM:Sub-Band Adaptive Differential Pulse Code Modulation PTC:PictureTel Transform Coder AC-2;AC-3:Digital Audio Compression Standard,美国 Dolby公司 AAC:Advanced Audio Coding, 日本138187, MPEG-2 MUSICAM:Masking Pattern Adapted Universal Subband Integrated Coding and Multi
10、plexing ATRAC:Adaptive Transform Acoustic Coder,6.1 引 言,第10页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.2 信源编码概述,(3) 数据压缩概貌,6.1 引 言,第11页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.1.2 信源编码概述,有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如:,返回目录,连续信源编码:脉冲编码调制
11、 (PCM)、矢量量化技术,相关信源编码: 预测编码:增量编码、差分脉冲调制 (DPCM)、自适应差分脉冲调制(ADPCM)、线性预测声码器; 变换编码:KL 变换、离散变换、子带编码、小波变换。,6.1 引 言,第12页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.2 香农编码,设离散无记忆信源: 二进制香农码的编码步骤如下: 将信源符号按概率从大到小的顺序排列,为方便起见,令: p(x1) p(x2) p(xn) 令 p(x0)=0,用 pa(xj),j=i+1 表示第 i 个码字的累加概率,则
12、:,第13页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.2 香农编码,设离散无记忆信源: 二进制香农码的编码步骤如下: 确定满足下列不等式的整数 ki ,并令 ki 为第 i 个码字的长度 log2 p(xi) ki 1 log2 p(xi) 将 pa(xj) 用二进制表示,并取小数点后 ki 位作为符号 xi 的编码。,第14页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.2 香农编码,例6.1.1
13、:有一单符号离散无记忆信源: 对该信源编二进制香农码。其编码过程如表5.2.1 所示。,第15页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.2 香农编码,例6.1.1 : 计算出给定信源香农码的平均码长: 若对上述信源采用等长编码,要做到无失真译码,每个符号至少要用 3 个比特表示。相比较,香农编码对信源进行了压缩。,第16页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.2 香农编码,例6.1.1 :
14、由离散无记忆信源熵定义,可计算出信源上熵为: 对上述信源采用香农编码的信息率为: 编码效率为信源熵和信息率之比。则: 可以看出,编码效率并不是很高。,返回目录,第17页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.3 费诺编码,将概率按从大到小的顺序排列,令: p(x1) p(x2) p(xn) 按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编 m 进制码就分成 m 组。 给每一组分配一位码元。 将每一分组再按同样原则划分,重复步骤 2 和 3,直至概率不再可分为止。,
15、第18页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.3 费诺编码,例6.3.1:设有一单符号离散信源 对该信源编二进制费诺码。编码过程如表5.3.1。,第19页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.3 费诺编码,例6.3.1 该信源的熵为: 平均码长为: 对上述信源采用费诺编码的信息率为: 编码效率为: 本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组
16、概率都相等的信源进行编码时,可达到理想的编码效率。,第20页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.3 费诺编码,例6.3.2:有一单符号离散无记忆信源 对该信源编二进制费诺码,编码过程如表5.3.2。,第21页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.3 费诺编码,例5.3.2 信源熵为:H(X)=2.75(比特/符号) 平均码长为: 编码效率为=1。之所以如此,因为每次所分两组的概率恰好相等。,返回目录,第22页,2019/1/20,Department of Electronics and Information, NCUT Song Peng,6.4 哈夫曼编码,哈夫曼(Huffman) 编