信息论与编码-第13讲-信源编码2

第1页2024/4/14ElectronicsEngineeringDepartment,NCUTSongPeng第13讲：信源编码1第14讲：信源编码2第15讲：信道编码概论第16讲：线性分组码第17讲：循环码第18讲：卷积码第19讲：习题课2第20讲：上机1第21讲：上机2第22讲：上机3第23讲：上机4第24讲：总复习目录第2页2024/4/14第六章信源编码6.1信源编码概论6.2变长编码方法6.3实用的无失真信源编码方法6.4信源编码总结ElectronicsEngineeringDepartment,XXXXXxxXxxx第3页2024/4/146.3实用的无失真信源编码方法6.3.1游程编码6.3.2算术编码6.3.3通用信源编码第4页2024/4/146.3.2算术编码(1)算术编码特点及应用(2)累积分布函数F(s)及对应的区间(3)累积分布函数的递推公式(4)算术编码方法(5)算术编码的译码第5页2024/4/14(1)算术编码的特点及应用算术编码不同于霍夫曼码，它是非分组（非块）码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术编码主要的编码方法是计算输入信源符号序列所对应的区间。因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。二元序列的算术编码可用于黑白图像的编码，例如传真。6.3.2算术编码第6页2024/4/14(2)累积分布函数F(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)=0F(1)=P(0)6.3.2算术编码第7页2024/4/14(2)累积分布函数F(s)及对应的区间

计算二元无记忆信源序列的累积分布函数初始时：在[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”，落入[0,F(1))区间，得累积分布函数

F(s=“0”)=

F(0)=06.3.2算术编码第8页2024/4/14(2)累积分布函数F(s)及对应的区间

计算二元无记忆信源序列的累积分布函数输入第二个符号为“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.3.2算术编码第9页2024/4/14(2)累积分布函数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”的区间下界值仍为F(s)，得符号序列s0=“010”的累积分布函数为F(s0)=F(s)。6.3.2算术编码第10页2024/4/14(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)

对应区间宽度为：A(s1)=A(s)

P(1)6.3.2算术编码第11页2024/4/14(2)累积分布函数F(s)及对应的区间

计算二元无记忆信源序列的累积分布函数

归纳符号序列对应的区间宽度

A(s=“0”)=P(0)A(s=“1”)=1－A(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(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.3.2算术编码第12页2024/4/14(3)累积分布函数的递推公式6.3.2算术编码

二元信源符号序列的累积分布函数的递推公式

F(sr)=F(s)+P(s)

F(r)(r=0,1)(6-20)sr表示已知前面信源符号序列为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)(6-21)A(s0)=P(s0)=P(s)

P(0)A(s1)=P(s1)=P(s)

P(1)第13页2024/4/14举例：已输入二元符号序列为s=“011”，接着再输入符号为“1”，得序列累积分布函数为：

F(s1)=F(0111)=F(s=“011”)+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)(3)累积分布函数的递推公式6.3.2算术编码第14页2024/4/14上述整个分析过程可用下图描述(3)累积分布函数的递推公式6.3.2算术编码AAA第15页2024/4/14式(6-20)和(6-21)是可递推运算，在实际中，只需两个存储器，把P(s)和F(s)存下来，然后，根据输入符号和式(6-20)、(6-21)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码。F(sr)=F(s)+P(s)

F(r)(r=0,1)(6-20)A(sr)=P(sr)=P(s)

P(r)(r=0,1)(6-21)(3)累积分布函数的递推公式6.3.2算术编码第16页2024/4/14

通过信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间。可取小区间内的一点来代表这序列。(4)算术编码方法6.3.2算术编码第17页2024/4/14编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后l位，若后面有尾数，就进位到第l位，这样得到的一个数C，并使l满足：举例：(4)算术编码方法6.3.2算术编码第18页2024/4/14

编码效率

算术编码的编码效率很高。当信源符号序列很长时，N很大时，平均码长接近信源的熵。(4)算术编码方法6.3.2算术编码第19页2024/4/14译码就是一系列比较过程，每一步比较C－F(s)与P(s)P(0)。

F(s0)=F(s)F(s1)=F(s)+P(s)

P(0)s—前面已译出的序列串

P(s)—序列串s对应的宽度F(s)是序列串s的累积分布函数，即为s对应区间的下界；P(s)P(0)是此区间内下一个输入为符号“0”所占的子区间宽度；若C－F(s)<P(s)P(0)则译输出符号为“0”；若C－F(s)>P(s)P(0)则译输出符号为“1”。(5)算术编码的译码6.3.2算术编码第20页2024/4/14举例：设二元无记忆信源S={0,1}，其中P(0)=1/4，P(1)=3/4。对二元序列11111100做算术编码。[解]：P(s=11111100)=P2(0)P6(1)=(1/4)2(3/4)6F(sr)=F(s)+P(s)

F(r)F(s0)=F(s)F(s1)=F(s)+P(s)

F(1)=F(s)+P(s)

P(0)F(s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0)=0.82202=0.110100100111(5)算术编码的译码6.3.2算术编码第21页2024/4/14举例：设二元无记忆信源S={0,1}，其P(0)=1/4，P(1)=3/4。对二元序列11111100做算术编码。[解]：得C＝0.1101010，得s的码字为1101010。编码效率：(5)算术编码的译码6.3.2算术编码第22页2024/4/14举例：(5)算术编码的译码6.3.2算术编码第23页2024/4/146.3.3通用信源编码(1)概述(2)LZ

(Lempel-Ziv)编码(3)LZW编码第24页2024/4/14(1)概述①通用编码和统计编码②基于字典的编码方法6.3.3通用信源编码第25页2024/4/14①通用编码和统计编码

统计编码需要精确知道信源的概率分布{pi}。统计编码对于实际分布与假设分布的偏差非常灵敏；许多场合不知道实际信源的统计特性，或者信源不存在统计特性。

通用信源编码：与信源统计特性无关而且有效的编码方法。(1)概述6.3.3通用信源编码第26页2024/4/14②基于字典的编码方法LZ码是1977年两位以色列研究人员，齐费(J.Ziv)和兰佩尔(A.Lempel)提出的，它是一种基于字典的编码方法。至今，几乎日常使用的所有通用压缩工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR⋯⋯甚至许多硬件如网络设备中内置的压缩算法，都可以最终归结为这两个以色列人的杰出贡献。字典模型的思路：在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行查询操作。字典压缩模型正是基于这一思路设计实现的。(1)概述6.3.3通用信源编码第27页2024/4/14②基于字典的编码方法

静态字典模型的算法：对一篇中文文章压缩，已有一本《现代汉语词典》。首先扫描要压缩的文章，对其中的句子进行分词操作，对每一个独立的词语查找它的出现位置，如果找到，就输出页码和该词在该页中的序号，如果没有找到，就输出一个新词。静态字典模型的缺点适应性不强，必须为每类不同的信息建立不同的字典；必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。(1)概述6.3.3通用信源编码第28页2024/4/14②基于字典的编码方法自适应字典模型：把已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。几乎所有通用的字典模型都使用这种方式。根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。(1)概述6.3.3通用信源编码第29页2024/4/14①LZ编码原理②举例③计算LZ78码的平均码长的界限(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第30页2024/4/14①LZ编码原理

LZ78的基本算法：将长度不同的符号串编成一个个新的短语（单词），形成短语字典的索引表，短语字典由前面已见到的文本来定义，是一个潜在的无限列表。(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第31页2024/4/14①LZ编码原理

LZ78的编码算法：设信源符号集A={a0,a1,a2,…,aq－1}共q个符号设输入信源序列为s1,s2,s3,…,snsi∈A

将此序列分成不同的C段。分段规则：尽可能取最少个连着的信源符号，并保证各段都不相同。不同段内的信源符号可看成一短语，可得不同段对应的短语字典表。(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第32页2024/4/14①LZ编码原理

LZ78的编码算法：码字组成：段号＋后面一个符号二元码：段号码长：，每个信源符号码长：。单符号码字的段号为0。

n—信源序列的输入长度

C(n)—输入长度为n

的信源序列被分解成字符片段的数目(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第33页2024/4/14②举例设q=4，信源序列为：a0a0a2a3a1a1a0a0a0a3a2…分段为：a0,a0a2,a3,a1,a1a0,a0a0,a3a2

共7段编码字典如下表：字典共7段，段号l=3位二元码符号；q=4，每个符号需要2位二元码符号：a000，a101，a210，a311。得序列符号：00000001100001100001100000010001110(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第34页2024/4/14②举例(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码码符号序列译码：一边译码一边又建成字典表，字典表无需传送。在本例中，二元序列共35位，似乎比不编码还坏。当序列n

增长时段内短语的符号数也增长，尤其是某些符号重复出现的话，编码效率将会提高。第35页2024/4/14③计算LZ78码的平均码长的界限信源符号序列长度n；段的数目：C(n)；每段二元码符号长度：每个信源符号码长：每段二元码符号数：n长信源符号序列数：平均每个信源符号所需码长：因此：(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第36页2024/4/146.3.3通用信源编码③计算LZ78码的平均码长的界限设长度为k

的段有qk

种，最长的段的长度为K，所有长度≤K的段型都存在，则：(2)LZ

(Lempel-Ziv)编码第37页2024/4/14③计算LZ78码的平均码长的界限平稳无记忆r元信源序列，设信源pi(i=0,1,2,…,q－1)当K很大时，典型段中ai

出现piK

个，这种段型有NK

种，则：(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第38页2024/4/14③计算LZ78码的平均码长的界限结论：LZ78码的平均码长仍以信源熵为极限，当n

很长时（即K很大时），平均码长渐进地接近信源的熵。

(2)LZ

(Lempel-Ziv)编码6.3.3通用信源编码第39页2024/4/14①什么是LZW码？②LZW码的格式规定③LZW码的编码方法④LZW码的译码⑤LZW码的应用(3)LZW编码6.3.3通用信源编码第40页2024/4/14①什么是LZW码？

LZW

算法是韦尔奇（T.A.Welch）对LZ算法的一种修正，它保留了LZ算法原有的自适应性。为了使长短不一的“单词”更便于处理，专门为“单词”建立了一种通用的格式。(3)LZW编码6.3.3通用信源编码第41页2024/4/14②LZW码的格式规定每个“单词”均由前缀字符串和尾字符串两部分组成。前缀字符串为字典中已有的“单词”，尾字符是本“单词”的最后一个字符。对本身已经是单节的“单词”，没有前缀词时则在前面加上一个空前缀，并规定字典最后一个“单词”为“空”。(3)LZW编码6.3.3通用信源编码第42页2024