2.8 无失真信源编码(3).ppt

1第二章 基本信息论2.8 无失真信源编码(三)2.8 无失真信源编码无失真信源编码(三三)九、游程长度编码九、游程长度编码十、算术编码十、算术编码2第二章 基本信息论2.8 无失真信源编码(三)九、游程长度编码九、游程长度编码1.一维游程长度编码一维游程长度编码(Run Length Encoding)(共需共需 228=176 bits)(共共需需 128=96 bits)例例 a=100，b=1，c=23，d=254，e=54，f=25 aaaa bbb cc d eeeee fffffff 输入字符串输入字符串 4 3 2 1 5 7 游程长度游程长度 4 a 3 b 2 c 1 d 5 e 7 f 输出字符串输出字符串 176/96=1.83 压缩比压缩比 3第二章 基本信息论2.8 无失真信源编码(三)2.二维游程长度编码二维游程长度编码 二维游程长度编码要解决的二维游程长度编码要解决的核心问题核心问题是：是：的像素，采用某种方式转化成一维排列的方式。的像素，采用某种方式转化成一维排列的方式。一维一维游程长度编码游程长度编码方式进行编码。方式进行编码。九、游程长度编码九、游程长度编码将二维排列将二维排列 然后按照然后按照 4第二章 基本信息论2.8 无失真信源编码(三)两种典型的二维行程编码的排列方式：两种典型的二维行程编码的排列方式：2.二维游程长度编码二维游程长度编码 九、游程长度编码九、游程长度编码5第二章 基本信息论2.8 无失真信源编码(三)D A A B C B B AB C C DA D D C基于基于 Helbert 曲线曲线的排列方式：的排列方式：2.二维游程长度编码二维游程长度编码 递归规则递归规则 A B C D D DDA C 演化举例演化举例 九、游程长度编码九、游程长度编码6第二章 基本信息论2.8 无失真信源编码(三)B BBA C 演化举例演化举例 D A A B C B B AB C C DA D D C基于基于 Helbert 曲线曲线的排列方式：的排列方式：2.二维游程长度编码二维游程长度编码 递归规则递归规则 A B C D 九、游程长度编码九、游程长度编码7第二章 基本信息论2.8 无失真信源编码(三)基于基于 Helbert 曲线曲线的排列方式：的排列方式：2.二维游程长度编码二维游程长度编码 九、游程长度编码九、游程长度编码B BBA C 演化举例演化举例 8第二章 基本信息论2.8 无失真信源编码(三)基于基于 Helbert 曲线曲线的排列方式：的排列方式：2.二维游程长度编码二维游程长度编码 九、游程长度编码九、游程长度编码9第二章 基本信息论2.8 无失真信源编码(三)三维三维 Helbert 曲线曲线：3.三维游程长度编码三维游程长度编码 九、游程长度编码九、游程长度编码10第二章 基本信息论2.8 无失真信源编码(三)十、算术编码十、算术编码基本原理基本原理 根据输入信息可能出现的根据输入信息可能出现的各种符号串各种符号串的概率，把的概率，把 0,1 区间划分为互不重叠的子区间，各子区间的宽度恰好等于各区间划分为互不重叠的子区间，各子区间的宽度恰好等于各 符号串的概率。符号串的概率。这样就将输入信息的各种不同的符号串与各子区间一一这样就将输入信息的各种不同的符号串与各子区间一一的符号串，将这个实数的小数位用二进制表示出来，就得到的符号串，将这个实数的小数位用二进制表示出来，就得到 对应，从而每个子区间内的任意一个实数都可用来表示对应对应，从而每个子区间内的任意一个实数都可用来表示对应 该符号串对应的码字。该符号串对应的码字。11第二章 基本信息论2.8 无失真信源编码(三)输出输出 1解解求字符串求字符串 的算术编码的算术编码。例例 设消息的概率分布如下，设消息的概率分布如下，a2a3a1p(a1)=0.5，p(a2)=0.25，p(a3)=0.125，p(a4)=0.1250.01.00.50.750.875a2a4a3a10.01.00.10.110.1110.50.750.6250.68750.71875a2a2a2a4a2a3a2a10.10.110.1010.10110.101110.68750.718750.7031250.71093750.71484375a2a3a2a2a3a4a2a3a3a2a3a10.1011000.101110.1011010.10110110.1011011110110码字码字输出输出 011输出输出 012第二章 基本信息论2.8 无失真信源编码(三)十、算术编码十、算术编码 符号序列对应到一个实区间，该区间的任何一个实数符号序列对应到一个实区间，该区间的任何一个实数 算术编码仍遵循算术编码仍遵循“概率大码短，概率小码长概率大码短，概率小码长”的原则。的原则。算术编码被用于算术编码被用于 MPEG-4 标准中。标准中。算术码字是赋给整个符号序列的，源符号与码字之间算术码字是赋给整个符号序列的，源符号与码字之间 不存在一一对应关系。不存在一一对应关系。都可以用来表示此符号序列。都可以用来表示此符号序列。符号串中某一个符号出现的概率占绝对优势的情况下，符号串中某一个符号出现的概率占绝对优势的情况下，算术编码的优势相当明显。算术编码的优势相当明显。数表示一个符号串，减少了存储空间。数表示一个符号串，减少了存储空间。即用一个二进制的浮点即用一个二进制的浮点