1.积累概率的计算

可得:Q0=0,Q1=p0,Q2=p0+p1=Q1+p1,…,Qr-1=Qr-2+pr-2

以r+1个点:0=Q0,Q1,Q2,…,Qr-1,1

可以完整地分割区间[0,1),如图7.7所示。可以发现:

图7.7　区间分割

(1)[Qi-1,Qi)与信源符号ai-1建立一一对应关系;

(2)用区间[Qi-1,Qi)内任一点可作为该对应信源符号ai-1的代码;

(3)只要代码长度与概率相匹配,就得到高效编码。

信源符号序列的积累概率递推计算:

信源X输出的N长序列为α=α1α2…αN,(αi∈X)

输出的可能序列的总数为rN

说明:算术编码时,一般N比较大,甚至是一个文件的长度。

实际中,很难得到对应信源序列的概率和积累概率,一般从已知的信源符号概率P=(p0,p1,…,pr-1)递推得到。为了简单,先讨论独立二元序列,再推广到一般。

设二元序列:α=011,3长二元序列共有8个,按自然二进数排列为

000、001、010、011、100、101、110、111,相当于α0,α1,α2,α3,α4,α5,α6,α7。比如α=011对应α3,其积累概率为

设想扩展序列长为4,则总序列数为16个。其中由α=011扩展的两个符号为0110或0111,按自然二进数排序,在0110前有6个序列,在0111前有7个序列,计算积累概率如下

可以证明对于多元序列,有一般的递推关系

其中,α为多元序列,ak为扩展字符,pk是字符ak的发生概率。

2.码区间分割与代码

(1)码区间分割:计算各个Qi值,完成在半开区间[0,1)上的码区间分割;每个Qi值是分割线,每个小区间的长度是信源符号概率。

(2)代码:小区间内任一点的坐标值,可以代表该信源符号;特别地,用二进数表示,就得到二元编码。类似地,对于字符串α,码区间分割用下式进行:

(3)具体的编码过程:

代码长度l的计算:其中,P(α)——字符串α出现的概率,[x]——大于等于x的最小整数。取积累概率Q(α)的二进小数前l位作为码字,若有尾数,则进位到第l位。

【例7.12】计算得Q(α)=0.10110001(二进数),P(α)=1/7,则l=[log7]=3,该字符序列α的算术码长为:110(有进位)。

3.码字的唯一性

可证明,上述规则编成的码字能唯一译出所代表的字符序列。

4.算术码的编码

计算步骤:(待编码信源序列为α1α2…αN,(αi∈X))

(1)初始化:α=∅,Q(∅)=0,P(∅=1),i=1(www.daowen.com)

(3)序列输入是否结束,若未结束,则i=i+1,转(2);否则,执行(4)。

【例7.13】设二元独立信源:

求信源序列10111101的算术编码。

解:信源符号的概率为p0=0.25,p1=0.75

累积概率为Q0=0,Q1=p0=0.25

信源序列10111101算术编码的相关数据如表7.5所示。得序列10111101的编码为0110001。图7.8为算术编码过程区间宽度减小图解。

表7.5　信源序列10111101的算术编码过程

续表

设Q(∅)=0,P(∅)=1,表中数据的计算过程如下(黑体数字表示二进小数):

图7.8　算术编码过程区间宽度减小图解

【例7.14】设四元无记忆信源:

求信源序列abdac的算术编码。

解:信源符号的概率为pa=0.5,pb=0.25,pc=pd=0.125

累积概率为Qa=0,　　　　　Qb=pa=0.5

信源序列abdac算术编码的相关数据如表7.6所示,得序列abdac的编码为0101110110。图7.9为算术编码过程区间宽度减小图解。

表7.6　信源序列abdac算术编码

设Q(∅)=0,P(∅)=1,表中数据的计算过程如下(黑体数字表示二进小数):

图7.9　算术编码过程区间宽度减小图解

5.算术码的译码

算术码的译码过程就是一系列的比较过程。接收到的编码w是信源序列累积概率的小数部分,则累积概率数值C一定满足:

以二元码为例,给出的译码规则为若C-Q(α)＜P(α)Q1,则译码输出符号为0;若CQ(α)＞P(α)Q1,则译码输出符号为1。