第二章 无失真信源编码4

2.4.4 递推公式的应用
算术编码具有渐近最佳性：当序列无限增长时， 平均码长渐近地等于序列的熵值。
实际存在问题：递推运算中都有乘法——运算量大
解决办法：1）编码对象是二元序列，符号概率较小的 一个为2-k的形式，则乘以2-k等于移位，乘以1-2-k等于 移位相减。 2）不做乘法的算术编码。
2.4.5 不做乘法的算术编码
2.5 游程编码（RLC）
3) 游程编码 将游程变换成游程序列后 , 二元序列就变换成多元序列. 下面分别对“白” 游程L(0)和黑” 游程L(1)的编码进行讨论 L 1°白游程的熵 H p(l )lbp(l )
W LW 1

W
W
白游程的长度 p(lW) : 白游程长度的概率 L白游程的最大长度 2°黑游程的熵 L H B p(lB )lbp(lB )
2.5 游程编码（RLC）
6°像素的熵 h01与平均码长
hWB pW hW pB hB
pW: 黑像素的概率
kWB pW kW pB kB
pB pB hB pB k B pB hB lB
pB: 白像素的概率 p pW hW pW kW pW hW W lW
hWB kWB
0
0.75
ac
0.875
ad
1
0
aba 0.25 a 0.359 375
0.25
abb
0.375
0.5
abc
abd 0.375
0.359 375 b c d
S=abda的编码0.367 187 5
0.375
不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点 作为对应序列的编码。--------即时码
2.4.5 不做乘法的算术编码

不做乘法的算术编码步骤：
（1）初始时，设S=Ø，p(Ø)=0.111….1，F(Ø)=0.000…0;
（2）输入一个信源符号，用递推公式计算p(S1)， p(S0)， F(S0)， F(S0)；
（3）重复步骤（2），直至信源序列结束。 实际应用时， 由p(S1)≈2-qp(S)，一般2-q近似等于二元 序列中小概率符号的概率值。通常取p(0)≈2-q。
2.4.3 算术编码的码长

码字长度应与序列的概率匹配 1 L [loga ] p( S )
取信源序列码字的前L位，若后面有尾数，就进位到第L位。 根据信源编码定理可知信源序列S的平均码长满足：
p(S ) loga p(S ) p(S )l (S ) p(S ) loga p(S ) 1
求信源序列S=abda对应的小区间
信源符号对应区间端点值 符号 概率 区间 0.5 [0, 0.5) a 0.25 [0.5, 0.75) b 0.125 [0.75, 0.875) c 0.125 [0.875, 1) d
2.4.2 算术编码原理

信源序列对应区间的划分
a b 0.5 aa ab c d
2.4.2 算术编码原理

译码步骤：
（1）判断码字落在哪个符号区间，翻译出1个符号； （2）将码字减去刚翻译出的符号的左端点值； （3）用刚翻译出的符合对应的区间的长度去除步骤2的结果， 判断此值落在哪个符号区间，翻译出一个新符号；
（4）反复步骤（2）（3）直至全部信源序列被翻译完为止。
2.4.2 算术编码原理
应该区间内的一点，这些点把区间[0,1)分成许多不同的小
区间，这些小区间的长度等于对应序列的概率，在小区间 内取一个浮点小数，使其长度与该序列的概率相匹配。 算术编码的主要任务是计算信源序列对应的小区间。
2.4.2 算术编码原理

小区间划分的递推计算公式
小区间左端点递推公式：
low(Sur ) low(S ) range (S ) low(ur )
a 0 aa 0 aba 0.25 a b 0.25 abb 0.5 ab b 0.75 ac 0.375
c
0.875
d
1
ad 0.5
abc
abd 0.375
0.359 375 c d
0.359 375
0.367 187 5
0.375
0.359375 [0,0.5) a ( 0.359 375- 0) /0.5 0.71875 [0.5,0.75) b ( 0.71875 - 0.5) /0.25 0.875 [0.875,1) d ( 0.875 0.875) /0.1 25 0 [0,0.5) a
二元信源序列积累概率的递推公式为： 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)
直接编码 , 以码率 2400 bit/s 或 4800 bit/s 传输时间至少需5min以上 .
2.6 改进的Huffman码（MH）
2.6 改进的Huffman码（MH）
方法介绍：Huffman编码＋游程编码
对游程编码之前 , 先要测得白、黑游程的概率分布 , 作 为编码的依据. CCITT(国际电话电报咨询委员会)推荐8种样张 我国原邮电部推荐7种样张 为了减少码表数 , 采用截断Huffman编码(MH) 一类为结尾码 , 白、黑游程的长度为0--63 另一类为基干码 , 游程长度为64的整倍数
LW 1
L
HW LW HW 1 lW lW lW lW
H B LB H B 1 lB lB lB lB
5°白、黑像素的熵hW
hW HW lW kW LW lW
hB 与平均码长
hB HB lB kB LB lB
1 hW kW hW lW
1 hB k B hB lB
例[2-12] 设二元独立信源
解：信源符号的积累概率 F(0)=0；F(1)=0.25
信源序列
F(S)
1 0.01
p(S)
0.11
L
0 1
序列码字
1
10
101 1010
0.01
0.0011
2
3 5
01
011 01010
0.010011 0.001001 0.010011 0.00001001
2.4.2 算术编码原理

计算小区间端点值的步骤
（1）给出信源符号对应的区间； （2）初始时，设S=Ø（Ø代表空集），low(Ø)=0，high(Ø)=1， range(Ø)=1 （3）输入ur，根据公式计算序列Sur的左右端点值，依次下去， 直到全部信源序列对应的区间被确定为止。
2.4.2 算术编码原理
p(ui ) F (ui 1 ) F (ui )
2.4.1 积累概率的递推公式

信源序列积累概率传递公式 设独立信源序列 S s1 , s2 , , sk , sn u1 , u 2 , , u m
信源序列S添加一 概率。 积累概率。 个新的信源符号ur 信源符号ur 后所得新序列 Sur 信源序列S添加一 的概率。 信源序列的积累概率 F(S) 与信源符号的积累概率一样，可用 的积累概率。 个新的信源符号 ur 后所得新序列 Sur [0,1)区间内的个点来表示，因此积累概率 F(S)将区间[0,1) 的概率。 分成许多不同的小区间，他们互不重叠，序列S的概率p(S)
2.4.1 积累概率的递推公式

信源符号积累概率
设信源
u2 un U u1 P p( u ) p( u ) p( u ) 1 2 n
信源符号积累概率：
F (uk ) p(ui )
i 1
k 1
F (u1 ) 0 F (u2 ) p(u1 ) F (u3 ) p(u1 ) p(u2 )
S
平均每个信源符号的码长：
n 对于DMS有 H( S ) nH( S)
n H(S ) L H(S ) 1 n n n L 1 H ( S) H ( S) n n
S
n
S
2.4.4 递推公式的应用

用序列积累概率的递推公式进行序列的算术编码的 计算步骤：
（1）根据信源符号积累概率公式计算信源符号的积累概率； （2）初始时，设S=Ø ，F(Ø)=0，p(Ø)=1； （3）根据序列的积累概率递推公式，计算序列的积累概率F(ur) 和序列的概率p(ur)； （4）计算码长； （5）将F(s)写成二进制数形式，取其前L位作为序列S的码字， 若后面有尾数就进位到第L位。

[例2-10]设信源
b c d U a P 0.5 0.25 0.125 0.125
信源序列对应区间端点值 信源序列 low high 0 0.5 a 0.25 0.375 ab 0.375 abd 0.359 375 abda 0.359 375 0.367 187 5
F ( Sur ) F ( S ) p ( S ) F (u r ) Su信源符号 p (S )的 p (ur ) 的 ur r ) S p (信源序列
就是两点间小区间的长度。小区间内的一个点可用来表示 序列的概率。