《信息论与编码原理第6章信源编码.ppt》由会员分享，可在线阅读，更多相关《信息论与编码原理第6章信源编码.ppt（91页珍藏版）》请在三一办公上搜索。
1、第1页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,信息论与编码原理,（第六章）信源编码,第2页,2023/9/5,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页,2023/9/5,Department of Electronics and Infor
2、mation,NCUT Song Peng,6.1 引 言,6.1.1 编码的目的,6.1.2 信源编码概论,第4页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.1.1 编码的目的,香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法；编码理论正是为了解决这一问题而发展起来的科学理论；编码的目的是为了优化通信系统，使这些指标达到最佳；通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指标正是信息论研究的对象。按不同的编码目的，编码分为三类：信源编码、信道
3、编码和安全编码（密码）。,6.1引言,第5页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.1.1 编码的目的,信源编码：提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩 每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信道编码：提高信息传输的可靠性为目的的编码。通常通过增加 信源的冗余度来实现。采用的一般方法是增大码率（带宽）。与信源编码正好相反。保密编码：提高通信系统的安全性为目的的编码。通常
4、通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,返回目录,6.1引言,第6页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.1.2 信源编码概述,(1)信源编码的理论基础信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。,6.1引言,第7页,2023/9/5,Department of Electronics and Informatio
5、n,NCUT Song Peng,6.1.2 信源编码概述,(2)信源编码的分类根据信源特性离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。根据压缩的特性冗余度压缩编码：可逆压缩，经编译码后可以无失真地恢复。熵压缩编码：不可逆压缩。,6.1引言,第8页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.1.2 信源编码概述,(3)数据压缩概貌KLT：Karhunen-Loeve TransformDCT：Discrete Cosi
6、ne TransformDST：Discrete Sinusoid TransformDFT：Discrete Fourier TransformWHT：Walsh-Hadamard TransformSLT：Slant TransformHAAR：Haar TransformLPC-10：Government Standard Linear Predictive Coding Algorithm:LPC-10MELP：Mixed Excited Linear Predictive CodingCELP：Codebook Excited Linear Predictive Coding ACE
7、LP：Algebraic Cocebook Excitation LPCQCELP：Qualcom Cocebook Excitation LPCEVRC：Enhanced Variable Rate CodecLD-CELP：Low Delay-CELP,28 种,6.1引言,第9页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.1.2 信源编码概述,(3)数据压缩概貌CS-ACELP：Conjugate-Structure Algebraic CELPVSELP：Vector Sum Excitati
8、on LPC RPE-LT：Long Time Predictive Regular-Pulse Excitation LPCMPLPC：Multi-Pulse Excitation LPC MP-MLQ：Multipulse Maximum Likelihood QuantizationMBE：Multi-Band Excitation Speech CoderSTC：Sinusoid Transform CocingCVSD：Continuously Variable Slope Delta ModulatorSB-ADPCM：Sub-Band Adaptive Differential
9、Pulse Code Modulation PTC：PictureTel Transform CoderAC-2；AC-3：Digital Audio Compression Standard，美国 Dolby公司AAC：Advanced Audio Coding,日本138187,MPEG-2 MUSICAM：Masking Pattern Adapted Universal Subband Integrated Coding and MultiplexingATRAC：Adaptive Transform Acoustic Coder,6.1引言,第10页,2023/9/5,Departm
10、ent of Electronics and Information,NCUT Song Peng,6.1.2 信源编码概述,(3)数据压缩概貌,6.1引言,第11页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.1.2 信源编码概述,有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如：,返回目录,连续信源编码：脉冲编码调制(PCM)、矢量量化技术,相关信源编码：预测编码：增量编码、差分脉冲调制(DPCM)、自适应差分脉冲调制(ADPCM)、线性预测声码器；变换编码：KL 变换、离散变换、
11、子带编码、小波变换。,6.1引言,第12页,2023/9/5,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 个码字的累加概率，则：,第13页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.2 香农编码,设离散无记忆信源：二进制香农码的
12、编码步骤如下：确定满足下列不等式的整数 ki，并令 ki 为第 i 个码字的长度log2 p(xi)ki 1 log2 p(xi)将 pa(xj)用二进制表示，并取小数点后 ki 位作为符号 xi 的编码。,第14页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.2 香农编码,例6.1.1：有一单符号离散无记忆信源：对该信源编二进制香农码。其编码过程如表5.2.1 所示。,第15页,2023/9/5,Department of Electronics and Information,NCUT Song P
13、eng,6.2 香农编码,例6.1.1：计算出给定信源香农码的平均码长：若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3 个比特表示。相比较，香农编码对信源进行了压缩。,第16页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.2 香农编码,例6.1.1：由离散无记忆信源熵定义，可计算出信源上熵为：对上述信源采用香农编码的信息率为：编码效率为信源熵和信息率之比。则：可以看出，编码效率并不是很高。,返回目录,第17页,2023/9/5,Department of Electronics and
14、 Information,NCUT Song Peng,6.3 费诺编码,将概率按从大到小的顺序排列，令：p(x1)p(x2)p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编 m 进制码就分成 m 组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤 2 和 3，直至概率不再可分为止。,第18页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.3 费诺编码,例6.3.1：设有一单符号离散信源对该信源编二进制费诺码。编码过程如表。,第19页,2023/9/5,
15、Department of Electronics and Information,NCUT Song Peng,6.3 费诺编码,例6.3.1该信源的熵为：平均码长为：对上述信源采用费诺编码的信息率为：编码效率为：本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,第20页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.3 费诺编码,例6.3.2：有一单符号离散无记忆信源对该信源编二进制费诺码，编码过程如表。,第
16、21页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.3 费诺编码,例5.3.2信源熵为：H(X)=2.75(比特/符号)平均码长为：编码效率为=1。之所以如此，因为每次所分两组的概率恰好相等。,返回目录,第22页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4 哈夫曼编码,哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。,6.4.1 编码步骤,6.4.2 二进制哈夫曼编码,6.4.3 m 进
17、制哈夫曼编码,第23页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.1 编码步骤,(1)将信源符号按概率从大到小的顺序排列，令：p(x1)p(x2)p(xn)(2)信源的第一次缩减信源：给两个概率最小的信源符号 p(xn1)和 p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源，用 S1 表示。(3)将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含(n2)个符号的缩
18、减信源 S2。(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,6.4哈夫曼编码,返回目录,第24页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,例6.4.1 设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。编码过程如图。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。,6.4哈夫曼编码,第
19、25页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,例6.4.1,6.4哈夫曼编码,第26页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,例6.4.1信源熵为：平均码长为：编码效率为：若采用定长编码，码长 K=3，则编码效率：哈夫曼的编码效率提高了 12.7%。,6.4哈夫曼编码,第27页,2023/9/5,Department of Electronics a
20、nd Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,注意：哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长 ki 不变，平均码长 也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度 ki 也不尽相同。,6.4哈夫曼编码,第28页,2023/9/5,Depart
21、ment of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,例6.4.2：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。,6.4哈夫曼编码,第29页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,例6.4.2：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。方法二：合并后的新符号排在其它相同概率符号的前面。,6.4哈夫曼编码,第30页
22、,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,例6.4.2：单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。编法一的平均码长为：编法二的平均码长为：可见，本例两种编法的平均码长相同，所以编码效率相同。,6.4哈夫曼编码,第31页,2023/9/5,Department of Electronics and Information,NCUT Song Peng
23、,6.4.2 二进制哈夫曼编码,讨论：码字长度的方差2：长度 ki 与平均码长 之差的平方的数学期望，即：编法一码字长度方差：编法二码字长度方差：,哪种方法更好？,6.4哈夫曼编码,第32页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.2 二进制哈夫曼编码,比较：第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的 5 个码字有 4 种不同的码长；第二种方法编出的码长只有两种不同的码长；第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程
24、中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,返回目录,6.4哈夫曼编码,第33页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.3 m 进制哈夫曼编码,(1)“全树”概念,(2)举 例,(3)结 论,6.4哈夫曼编码,第34页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.3 m 进制哈夫曼编码,(1)
25、“全树”概念定义：码树图中每个中间节点后续的枝数为 m 时称为全树；若有些节点的后续枝数不足 m，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是 1 时，这个枝就可以去掉使码字长度缩短。m 进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为 m+k(m1)。k 为信源缩减次数。若信源所含的符号数 n 不能构成 m 进制全树，必须增加 s 个不用的码字形成全树。显然 sm1，若 s=m1，意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略。,6.4哈夫曼编码,第35页,2023/9/5,Department of Electronics and Informa
26、tion,NCUT Song Peng,6.4.3 m 进制哈夫曼编码,(1)“全树”概念 在编 m 进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有 m 个信源符号。非全树时，有 s 个码字不用：第一次对最小概率符号分配码元时就只取(ms)个，分别配以 0,1,ms1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。以后每次就可以取 m 个符号，分别配以 0,1,m1；如此下去，直至所有概率相加得 1 为止，即得到各符号的 m 进制码字。,返回目录,6.4哈夫曼编码,第36页,2023/9/5,Department of Electronics and Infor
27、mation,NCUT Song Peng,6.4.3 m 进制哈夫曼编码,(2)举例对如下单符号离散无记忆信源（例）编三进制哈夫曼码.这里：m=3，n=8令 k=3，m+k(m1)=9，则 s=9n=98=1所以第一次取 ms=2 个符号进行编码。,6.4哈夫曼编码,第37页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.3 m 进制哈夫曼编码,(2)举例,6.4哈夫曼编码,第38页,2023/9/5,Department of Electronics and Information,NCUT So
28、ng Peng,6.4.3 m 进制哈夫曼编码,(2)举例平均码长为：信息率为：编码效率为：可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。,返回目录,6.4哈夫曼编码,第39页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.4.3 m 进制哈夫曼编码,(3)结论香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高;费诺码和哈夫曼码的编码方法都不惟一；费诺码比
29、较适合于对分组概率相等或接近的信源编码，费诺码也可以编 m 进制码，但 m 越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。,返回目录,6.4哈夫曼编码,第40页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5 游程编码,6.5.1 游程编码对象和性质,6.5.2 游程编码的定义,6.5.3 二元独立序列,6.5.4 游程编码的效率,6.5.5 长
30、码的截断处理方法,第41页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.1 游程编码对象和性质,香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；游程编码对相关信源编码更有效；香农编码、费诺编码、哈夫曼编码属于无失真信源编码；游程编码属于限失真信源编码。,6.5游程编码,返回目录,第42页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.2 游程编码的定义,游程：数字序列中连
31、续出现相同符号的一段。二元序列的游程：只有“0”和“1”两种符号。连“0”这一段称为“0”游程，它的长度称为游程长度L(0)；连“1”这一段称为“1”游程，它的游程长度用 L(1)表示。,返回目录,6.5游程编码,第43页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.3 二元独立序列,(1)基本概念,(2)二元独立序列游程长度的概率和熵,(3)二元独立序列的平均游程长度,(4)二元独立序列的熵,6.5游程编码,第44页,2023/9/5,Department of Electronics and I
32、nformation,NCUT Song Peng,6.5.3 二元独立序列,(1)基本概念若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程。对于随机序列，游程长度是随机的，其取值可为 1,2,3,，直至无穷。游程长度序列（游程序列）：用交替出现的“0”游程和“1”游程长度表示任意二元序列。游程变换：是一种一一对应的变换，也是可逆变换。例如：二元序列：可变换成如下游程序列：31132131游程变换减弱了原序列符号间的相关性。,6.5游程编码,第45页,2023/9/5,Department of Electronics and Infor
33、mation,NCUT Song Peng,6.5.3 二元独立序列,(1)基本概念 游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。编码方法 首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；对新的信源（游程序列）进行哈夫曼编码。多元序列也可以变换成游程序列，如 m 元序列可有 m 种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是 m 种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行游程变换的意义不大。,返回目
34、录,6.5游程编码,第46页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.3 二元独立序列,(2)二元独立序列游程长度的概率和熵若二元序列的概率特性已知，由于二元序列与游程变换序列的一一对应性，可计算出游程序列的概率特性。令“0”和“1”的概率分别为 p0 和 p1，则“0”游程长度 L(0)的概率为：pL(0)=p0L(0)1p1 式中 L(0)=1,2,在计算 pL(0)时必然已有“0”出现，否则就不是“0”游程，若下一个符号是“1”，则游程长度为 1，其概率是 p1=1p0；若下一个符号为“0
35、”、再下一个符号为“1”，则游程长度为 2，其概率将为 p0p1；依此类推。,6.5游程编码,第47页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.3 二元独立序列,(2)二元独立序列游程长度的概率和熵游程长度至少是 1，理论上，游程长度可以是无穷，但很长的游程实际出现的概率非常小。同理可得“1”游程长度 L(1)的概率为：PL(1)=p1L(1)1p0,6.5游程编码,第48页,2023/9/5,Department of Electronics and Information,NCUT Song
36、 Peng,6.5.3 二元独立序列,(2)二元独立序列游程长度的概率和熵“0”游程长度的熵：,6.5游程编码,第49页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.3 二元独立序列,(2)二元独立序列游程长度的概率和熵“0”游程长度的熵,返回目录,6.5游程编码,第50页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.3 二元独立序列,(3)二元独立序列的平均游程长度“0”游程序列的平均游程长度：同理可得
37、“1”游程长度的熵和平均游程长度：,返回目录,6.5游程编码,第51页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.3 二元独立序列,(4)二元独立序列的熵“0”游程序列的熵与“1”游程序列的熵之和除以它们的平均游程长度之和，即为游程变换后的熵 H(X)游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，所以变换后熵值不变，这也说明变换后的游程序列是独立序列。,6.5游程编码,第52页,2023/9/5,Department of Electronics and Information,NCU
38、T Song Peng,6.5.3 二元独立序列,(4)二元独立序列的熵对于有相关性的二元序列，也可以证明变换后的游程序列是独立序列，并且也有如下结论：但此时 HL(0)，HL(1)，l0 和 l1 的具体表达形式不同，它们是相关符号的联合概率和条件概率的函数。,返回目录,6.5游程编码,第53页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.4 游程编码的效率,游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码可获得较高的编码效率。假设“0”游程长度的哈夫曼编码效率为0，“1”游程长度的哈夫曼
39、编码效率为1，由编码效率的定义和式(5.4.9)可得对应二元序列的编码效率（信源熵和信息率之比为编码效率=H(X)/R）当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不会低于较小的那个效率。要想编码效率尽可能高，应尽可能提高熵值较大的游程编码效率。,返回目录,6.5游程编码,第54页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.5.5 长码的截断处理方法,理论上，游程长度可从 1 到无穷，要建立游程长度和码字之间的一一对应的码表是困难的。一般情况下，游程越长，出现的概率越小；
40、当游程长度趋向于无穷时，出现的概率也趋于 0。按照哈夫曼编码规则，概率越小，码字越长。但小概率的码字对平均码长影响较小。所以在实际应用时，常对长码采用截断处理的方法。,6.5游程编码,第55页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6 算术编码,6.6.1 算术编码特点及应用,6.6.2 累积分布函数 F(s)及对应的区间,6.6.3 累积分布函数的递推公式,6.6.4 算术编码方法,6.6.5 算术编码的译码,第56页,2023/9/5,Department of Electronics and
41、 Information,NCUT Song Peng,6.6.1 算术编码的特点及应用,算术编码不同于哈夫曼码，它是非分组（非块）码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。二元序列的算术编码可用于黑白图像的编码，例如传真。,6.6算术编码,返回目录,第57页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.2 累积分布函数 F(
42、s)及对应的区间,设信源符号集 A=a1,a2,an，其相应概率分布为 P(ai)，P(ai)0(i=1,2,n)信源符号的累积分布函数为：所得累积分布函数为每台级的下界值，则其区间为 0,1)左闭右开区间。F(a1)=0 F(a2)=P(a1)F(a3)=P(a1)+P(a2)当 A=0,1二元信源时：F(0)=0 F(1)=P(0),6.6算术编码,第58页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.2 累积分布函数 F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数 初始时：在 0,
43、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”，落入0,F(1)区间，得累积分布函数 F(s=“0”)=F(0)=0；,图示,6.6算术编码,第59页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.2 累积分布函数 F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数
44、 输入第二个符号为“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)P(1)=P(0)P(1)=P(01)对应的区间为：F(s=“01”),F(1)累积分布函数：F(s=“01”)=P(0)P(0)=P(00),图示,6.6算术编码,第60页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.2 累
45、积分布函数 F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数 输入第三个符号为“1”：输入序列可记做 s1=“011”，对应的区间是对区间 F(s),F(1)进行分割；序列 s0=“010”对应的区间宽度为：A(s=“010”)=A(s=“01”)P(0)=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”的
46、区间下界值仍为F(s)，得符号序列 s0=“010”的累积分布函数为F(s0)=F(s)。,图示,6.6算术编码,第61页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.2 累积分布函数 F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数 归纳 当已知前面输入符号序列为 s，若接着再输入一个符号“0”，序列 s0 的累积分布函数为：F(s0)=F(s)对应区间宽度为：A(s0)=A(s)P(0)若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)对应区间宽
47、度为：A(s1)=A(s)P(1),图示,6.6算术编码,第62页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.2 累积分布函数 F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数 归纳 符号序列对应的区间宽度 A(s=“0”)=P(0)A(s=“1”)=1A(0)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=P
48、(11)=A(1)P(1)=P(1)P(1)A(s=“010”)=A(01)P(0)=P(01)P(0)P(010)A(s=“011”)=A(01)P(1)=P(01)P(1)=P(011)信源符号序列 s 所对应区间的宽度等于符号序列 s 的概率 P(s)。,返回目录,6.6算术编码,第63页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,6.6.3 信源序列累积分布函数的递推公式,6.6算术编码,二元信源符号序列的累积分布函数的递推公式F(sr)=F(s)+P(s)F(r)(r=0,1)(5.6.1)sr
49、 表示已知前面信源符号序列为 s，接着再输入符号为 rF(0)=0，F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)=F(s)+P(s)P(0)A(sr)=P(sr)=P(s)P(r)(r=0,1)(5.6.2)A(s0)=P(s0)=P(s)P(0)A(s1)=P(s1)=P(s)P(1),第64页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,举例：已输入二元符号序列为 s=“011”，接着再输入符号为“1”，得序列累积分布函数为：F(s1)=F(0111)=F(s=“011”
50、)+P(011)P(0)=F(s=“01”)+P(01)P(0)+P(011)P(0)=F(s=“0”)+P(0)P(0)+P(01)P(0)+P(011)P(0)=0+P(00)+P(010)+P(0110)对应的区间宽度为：A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)F(s1)=F(s)+P(s)P(0)A(s1)=P(s1)=P(s)P(1),6.6.3 信源序列累积分布函数的递推公式,图示,6.6算术编码,第65页,2023/9/5,Department of Electronics and Information,NCUT Song Peng,上述整
