第二章 无失真信源编码4.ppt

2.4 算术编码,Huffman编码更适合于大消息集信源，对于小消息集信源使用算术编码和游程编码压缩效果更好主要内容：积累概率的递推公式算术编码原理算术编码的码长递推公式的应用不做乘法的算术编码,2.4.1 积累概率的递推公式,信源符号积累概率,设信源,信源符号积累概率：,,2.4.1 积累概率的递推公式,信源序列积累概率传递公式,设独立信源序列,信源序列的积累概率F(S)与信源符号的积累概率一样，可用[0,1)区间内的个点来表示，因此积累概率F(S)将区间[0,1)分成许多不同的小区间，他们互不重叠，序列S的概率p(S)就是两点间小区间的长度小区间内的一个点可用来表示序列的概率2.4.2 算术编码原理,基本思路：,把信源序列的积累概率映射到[0,1)区间上，使每个序列对应该区间内的一点，这些点把区间[0,1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配算术编码的主要任务是计算信源序列对应的小区间2.4.2 算术编码原理,小区间划分的递推计算公式,小区间左端点递推公式：,小区间右端点递推公式：,新序列Sur对应区间的左端点值。

信源序列S对应区间的左端点值信源序列S对应区间的宽度值信源符号ur对应区间的左端点值新序列Sur对应区间的右端点值信源序列S对应区间的左端点值信源序列S对应区间的宽度值信源符号ur对应区间的右端点值2.4.2 算术编码原理,计算小区间端点值的步骤,（1）给出信源符号对应的区间；（2）初始时，设S=Ø（Ø代表空集），low(Ø)=0，high(Ø)=1， range(Ø)=1（3）输入ur，根据公式计算序列Sur的左右端点值，依次下去，直到全部信源序列对应的区间被确定为止2.4.2 算术编码原理,[例2-10]设信源 求信源序列S=abda对应的小区间,2.4.2 算术编码原理,信源序列对应区间的划分,,,不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点作为对应序列的编码即时码,,S=abda的编码,2.4.2 算术编码原理,译码步骤：（1）判断码字落在哪个符号区间，翻译出1个符号；（2）将码字减去刚翻译出的符号的左端点值；（3）用刚翻译出的符合对应的区间的长度去除步骤2的结果，判断此值落在哪个符号区间，翻译出一个新符号；（4）反复步骤（2）（3）直至全部信源序列被翻译完为止。

2.4.2 算术编码原理,,,2.4.3 算术编码的码长,码字长度应与序列的概率匹配,取信源序列码字的前L位，若后面有尾数，就进位到第L位根据信源编码定理可知信源序列S的平均码长满足：,平均每个信源符号的码长：,对于DMS有,2.4.4 递推公式的应用,用序列积累概率的递推公式进行序列的算术编码的计算步骤：（1）根据信源符号积累概率公式计算信源符号的积累概率；（2）初始时，设S=Ø，F(Ø)=0，p(Ø)=1；（3）根据序列的积累概率递推公式，计算序列的积累概率F(ur)和序列的概率p(ur)；（4）计算码长；（5）将F(s)写成二进制数形式，取其前L位作为序列S的码字，若后面有尾数就进位到第L位2.4.4 递推公式的应用,例[2-12] 设二元独立信源求信源序列S=1010的算术编码解：信源符号的积累概率 F(0)=0；F(1)=0.25,S=Ø，F(Ø)=0，p(Ø)=1,,2.4.4 递推公式的应用,算术编码具有渐近最佳性：当序列无限增长时，平均码长渐近地等于序列的熵值实际存在问题：递推运算中都有乘法——运算量大解决办法：1）编码对象是二元序列，符号概率较小的 一个为2-k的形式，则乘以2-k等于移位，乘以1-2-k等于移位相减。

2）不做乘法的算术编码2.4.5 不做乘法的算术编码,二元信源序列积累概率的递推公式为： F(S0)=F(S)+p(S)F(0)=F(S) F(S1)=F(S)+p(S)F(1) p(S1)=p(S)p(1) p(S0)=p(S)p(0) p(S)=p(S0)+p(S1)，F(1)=p(0),如果令p(S1)≈2-qp(S)，则不做乘法的二进制算术编码的递推公式为 p(S0)=p(S)-p(S1) F(S0)=F(S) F(S1)=F(S)+p(S)F(1) =F(S)+p(S)p(0) =F(S)+p(S0),即： p(S1)≈2-qp(S) p(S0)=p(S)-p(S1) F(S0)=F(S) F(S1)=F(S)+p(S0),不做乘法的算术编码步骤：（1）初始时，设S=Ø，p(Ø)=0.111….1，F(Ø)=0.000…0;（2）输入一个信源符号，用递推公式计算p(S1)， p(S0)， F(S0)， F(S0)；（3）重复步骤（2），直至信源序列结束。

2.4.5 不做乘法的算术编码,实际应用时， 由p(S1)≈2-qp(S)，一般2-q近似等于二元序列中小概率符号的概率值通常取p(0)≈2-q2.5 游程编码（RLC）,游程编码属于无损压缩编码1) 二元信源序列 将“白”、“黑”二元信源用｛0，1｝表示2) 游程和游程序列 1°游程：规定以“0”开始的二元序列， 例 000 1 0 111 00 1 000 1… 2°游程长度： 序列中连续“0”段称“0” 游程或“白” 游程，其 0 的个数称“0” 游程长度，记lW；序列中连续“1”段称“1” 游程或“黑” 游程，其1的个数称“1” 游程长度，记lB 3°游程序列: 将二元序列中的lW、lB按其在二元序列 中的顺序排列的序列称游程序列 上例 3113213…,3) 游程编码将游程变换成游程序列后 , 二元序列就变换成多元序列.下面分别对“白” 游程L(0)和黑” 游程L(1)的编码进行讨论 1°白游程的熵 lW : 白游程的长度 p(lW) : 白游程长度的概率 L白游程的最大长度 2°黑游程的熵 lB: 黑游程的长度 p(lB) : 白游程长度的概率 L白游程的最大长度,2.5 游程编码（RLC）,2.5 游程编码（RLC）,3°白、黑游程编码的平均码长 4°白、黑游程的平均长度 5°白、黑像素的熵hW hB 与平均码长,6°像素的熵 h01与平均码长 pW: 黑像素的概率 pB: 白像素的概率,2.5 游程编码（RLC）,2.6 改进的Huffman码（MH）,机信源编码应用于文件：如文件、手写稿、表格、报纸、图纸等“白”、“黑”像素点的信息。

CCITT(国际电报咨询委员会)为了保证文件的清晰度 , 对于A4 幅面的文件（210mm×297mm）规定 1°行扫描线共有： 297mm×4线/mm = 1188 线 或 297mm×8线/mm = 2376 线 2°每条扫描线： 1728像素点/线 ，8像素点/mm 3°对于 A4 幅面的文件像素点 1728 像素点/线 × 1188 线 = 2052864像素点 1728 像素点/线 × 2376 线 = 4105728像素点,直接编码 , 以码率 2400 bit/s 或 4800 bit/s 传输时间至少需5min以上 .,2.6 改进的Huffman码（MH）,2.6 改进的Huffman码（MH）,方法介绍：,Huffman编码＋游程编码,MH编码：l=K+R，查表,对游程编码之前 , 先要测得白、黑游程的概率分布 , 作为编码的依据. CCITT(国际电报咨询委员会)推荐8种样张 我国原邮电部推荐7种样张,为了减少码表数 , 采用截断Huffman编码(MH) 一类为结尾码 , 白、黑游程的长度为0--63 另一类为基干码 , 游程长度为64的整倍数,2.6 改进的Huffman码（MH）,例．一行中一段,解：①lW＝131=2×64+3: K=10010 R=1000 ∴100101000 （l1=9）②lB=0×64+4 : R=011 （l2=3）③lW=0×64+6: R=1110 （l3=4）④lB=1×64+6 : K=0000001111 R=0010 （l4=14）比较：MH：码元表：9+3+4+14=30bit 直接编码：131+4+6+70=211bit 压缩比211/30=7.03,A．比较：码元表：MH：2×(64+1728/64)＝182个 直接Huffman：2×1729=3458个 性能：P（lW<61）＝80% P（lB<6）＝80% ∴工程上性能不差 B．极限压缩比,②  性能分析,2.6 改进的Huffman码（MH）,。