限失真信源编码--6讲

D=0时，R（0）=H（p），这就是无损编码
时，所需的信息率不能小于信源的符号熵。
2/7/2019 5
1、离散无记忆信源R(D)的计算
例：已知离散无记忆信源
x2 X x1 0 1 ，求 P( X ) p 1 p ，其中p 2 ，失真矩阵为D 0 , 输出Y 0,1 Dmax，率失真函数R( D)。
| x| 1 1 p( x) e 时， R( D) log , Dmax 2 D
可直接当结论来应用
2/7/2019 13
3、 信道容量和信息率失真函数的比较 • 相同点：二者都是求平均互信息的极值 • 不同点：
1、（1）信道容量：选择某一信源分布的情况下，
求平均互信息的极大值。 依据：平均互信息I是信源概率分布p(xi)的严格上 凸函数。 （2）信息率失真函数：求选择某一试验信道（转移 概率分布）的情况下，依据保真度准则，求平均 互信息的极小值。 依据：平均互信息I是信道转移概率分布p(yj/xi)的 严格下凸函数。
2/7/2019 19
• 说明:
对二元序列进行哈夫曼编码时，应先测定 “0”游程长度和“l”游程长度的概率分布， 或由二元序列的概率特性去计算各种游程长度 的概率。
2/7/2019
20
• 什么叫多元序列游程和游程长度? 对于多元序列也存在相应的游程序列。 例如m元序列中，可有m种游程。连着出现 符号ar的游程，其长度L（r）就是“r”游程 长度。这也是一个随机变量。用L（r）也可
y

min[ x 2 p( x)dx 2 y xp( x)dx y 2 p( x)dx]
y
D
min[ 2 0 y 2 ]
y

2
11
上题的扩展：若连续信源服从（μ，σ2）的高斯分布， 则再求上题。
服从(0, 2 )的高斯分布的概率密度 函数为： p( x) 1 e 2
构成游程序列。但是这种变换必须再加一些
符号，才能成为一一对应或可逆的。
2/7/2019 21
• 说明:
(1) 与二元序列变换所得的游程序列不同，这 里每个“r”游程的前面和后面出现什么符号 是不确定的，除r外的任何符号都是可能的， 因此这一游程之后是何种符号的游程就无法确
定，除非插人一个标志说明后一游程的类别。
2/7/2019 33
• 什么叫量化噪声?
当一个样值x经量化后所产生的误差为
zi=x-yi 或 yi=x-zi
也就是在信号值x上叠加了一个样值为-zi，的 噪声信号。这种噪声通常称为量化噪声。
2/7/2019
34
什么叫做矢量量化?
连续信源也是如此，当把多个信源 符号联合起来形成多维矢量，再对矢量
y
2/7/2019 2
12
结论：
1）若失真函数为均方失真，即d(x,y)=(x-y)2时,连
1 Dmax ) 续信源的信息率失真函数 R( D) ln( 2 D
y
，且
Dmax min[ p( x)d ( x, y)dx]
2）同理：当失真函数为绝对失真即d(x,y)=|x-y|时 ，指数分布的连续信源，当概率密度函数为
上述的附加标志可能抵销压缩编码所得的好
处，对原来的多元序列直接编码，或许会更有
效一些,所以把多元序列变换成游程序列再进行 压缩编码是没有多大意义的。
2/7/2019 22
(2) 一般情况下，游程长度越大，其概率越小； 这在以前的计算中也可看到，而且将随长度的 增大渐趋向零。
对于小概率的码字，其长度未达到概率匹
2 y 2
p( x)dx]
D
而 （x ）p( x)dx 2，即 x 2 p ( x)dx 2 xp( x)dx 2 2 xp( x)dx x 2 p( x)dx 2 2 Dmax min[ 2 2 2 y y 2 ]
时，

D
x y,
p(x)=
x e 2
时，
R（ D） =
1 log D
2
2/7/2019
(3) 当D(x,y)= ( x, y), p( x 0) p, p( x 1) 1 p 时，R（D）=H（p）- H （D）
2/7/2019
3
分析：
(1) 它们都有一最大失真值 Dmax．对应 R（D）＝0。当允许的平均失真D大于这最大 值时，R（D）当然也是零，也就是不用传送 信息已能达到要求。上述三种情况的 Dmax分别
2/7/2019
6
X x1 x2 0 1 ，其中 p ，失真矩阵为 D , 输出Y 0,1 P( X ) p 1 p 2 0
Dmax min D j • 解：（1） j 0 min p 1 p j 0 min(1 p ) , p
2、连续无记忆信源R(D)的计算
例：求失真函数为d(x,y)=(y-x)2的连续 信源的Dmax和信息率失真函数R(D)。
Dmax min [ p( x)d ( x, y )dx] • 解：连续信源的Dmax， y
Dmax min p( xi )dij
Y X
因为离散ቤተ መጻሕፍቲ ባይዱ源：
均方失真的连续信源的R(D)
进行标量量化时，自由度将更大，同样
的失真下，量化级数可进一步减少，码
1 Dmax R ( D) ln( ) 2 D
2/7/2019
可直接当结论来应用
10
例：设某连续信源X服从高斯分布，均值μ=0，方差σ2 ，失真函数为均方失真即d(x,y)=(y-x)2 • 求它的信息率失真函数R(D)和Dmax。
是均方失真 • 解： Dmax 1 R( D) ln ( ) 2 D
p ( xi ) 1 , 其中 i 1, n n
d ij ， i
j
此时下式成立：
Dmax
D / D D R( D) ln(n) ln (1 ) ln(1 ) (n 1) D
1 (1 ) n
可直接当结论来应用
2/7/2019 9
服从(0, 2 )的高斯分布的概率密度 函数为： 因此，需求Dmax： p( x) 1 e 2
y x2 2 2
代入得
1 2 R ( D ) ln( ) 2 D ln
2/7/2019
Dmax min[ p( x)d ( x, y )dx] min[ p( x)(x y ) 2 dx]
2/7/2019
。
15
第三节 限失真信源编码定理
限失真信源编码定理： 设离散无记忆信源X的信息率失真函数为 R（D），则当信息率R＞R（D），只要信 源序列长度 L足够长，一定存在一种编码方 法，其译码失真小于或等于D＋ ， 为任 意小的正数；反之，若R＜R（D），则无论 采用什么样的编码方法,其译码失真必大于D。
第二节 离散信源和连续信源的R(D)计算
问题:
假设已给定信源概率Pi和失 真函数dij，在约束条件下，求信
源的R（D）函数的极小值问题 ?
2/7/2019
1
• R（D）三种特殊表示 (1) 当d(x,y)=(x-y)2, p(x)= R（ D） = (2) 当d(x,y)=
log
1 x2 2 exp( ) 2 2

2/7/2019
16
• 说明:
号的平均码长满足如下公式
(1)如果是二元信源，对于任意小的 ＞0，每一个信源符

R(D) K R(D)
则 在失真限度内使信息率任意接近R（D）的编码方法存在。 (2) 该定理只能说明最佳编码是存在的，而具体构造编码方 法却一无所知，因而就不能像无损编码那样从证明过程 中引出概率匹配的编码方法。一般只能从优化的思路去 求最佳编码。实际上，迄今尚无合适的可实现的编码方 法来接近R（D）这个界。
配或较长，损失不会太大，也就是对平均码字 长度影响较小。这样就可对长游程不严格按哈 夫曼码步骤进行；在实际应用时，常采用截断
处理的方法。
2/7/2019 23
(3) 游程编码只适用于二元序列，对于 多元信源，一般不能直接利用游程编码。
2/7/2019
24
5.4.2 算术编码
• 算术编码的基本思路：
26
2/7/2019
27
这种比较一直进行到两个符号不相同为止，然后进入步骤3，
2/7/2019
28
[例3] 假设有4个符号的信源，它门的概率如表4-07所示： 表4-07 符号概率
2/7/2019
29
2/7/2019
30
2/7/2019
31
图4-04 算术编码概念
2/7/2019
32
5.4.3 矢量量化
从全序列出发，将各信源序列的概率映射 到[0,1]区间上，使每个序列对应这区间内的一 点，也就是一个二进制的小数。这些点把[0,1] 区间分成许多小段，每段的长度等于某一序列
的概率。再在段内取一个二进制小数，其长度
可与该序列的概率匹配，达到高效率编码的目 的。
2/7/2019 25
2/7/2019
• 什么叫标量量化? 连续信源进行编码的主要方法是量化，即将连续的样值x 离散化成为yi，i＝l，2，3，… ，n。n是量化级数，yi是某 些实数。 这样就把连续值转化为n个实数，可用0,1,2,…,n-1等n个 数字来表示。 离散信源也会涉及量化的问题，比如当提供的量化级数 少于原来的量化级数时，也需要对该信源信号进行再次量 化。 在上述的这些量化中，由于x是一个标量，因此称为标量 量化。
为 2 ,1 /
和p（若p＜1/2，不然就是1-p）
2/7/2019 4
(2) 当D＜Dmax时，R（D）就已不是零，随着
D的减小，R（D）单调地增加； 这就是说，大于信息量无限大的连续信源符
(3) 当D=0，前两种情况下R（D）趋于无限， 号，无法进行无损编码，除非信息率R趋向
无限大。
对于离散信源就不同，在第三种情况下，
2/7/2019 17
第四节 常用信源编码方法简介
5.4.1 游程编码
游程编码基本思想: 将任何(二元)序列变换成一一对应的 游程长度序列，按哈夫曼编码或其他方 法处理以达到压缩码率的目的 。
2/7/2019 18
• 什么叫二元序列游程和游程长度?
在二元序列中，只有两种符号，即“0”和“1”， 这些符号可连续出现，连“0”这一段称为“0”游程， 连“1”这一段称为“1”游程。它们的长度分别称为 游程长度L（0）和L（l）。“0”游程和“l”游程总 是交替出现的。如果规定二元序列是以“0”开始，第 一个游程是“0”游程，第二个必为“1”游程，第三 个又是“0”游程等等。对于随机的二元序列，各游程 长度将是随机变量，其取值可为1，2，3，…，直到无 限。 游程长度编码的主要思想是将一个相同值的连续申 用其值和申长(重复的个数)的数对二元组来替代。
y ( x )2 2 2
• 解：先求Dmax：
代入得
1 2 R ( D ) ln( ) 2 D ln
2
Dmax min[ p( x)d ( x, y )dx] min[ p( x)(x y ) 2 dx]
y

min[ x p( x)dx 2 y xp( x)dx y
2/7/2019 14
2、（1）信道容量C一旦求出来，则与信源分布无关（
只是证明存在这样的满足信道容量的信源分布），只
和信道转移概率分布p(yj/xi)有关。 即信道容量和信源特性无关，反映信道特性。 • （2）信息率失真函数R(D)一旦求出来，则与信道 转移概率分布无关（只是证明存在达到最小信息率 的试验信道），只和信源概率分布p(xi)有关。 • 即信息率失真函数和信道特性无关，反映信源特性
j
1 (1 p ) , 当p 2 时 1 p , 当p 时 2

2/7/2019
（2）
D R( D) H ( p) H ( )

7
• R(D)随D的变化曲线
2/7/2019
8
结论：
• 对于n元等概信源，有 ，当失真函数为对称失真时， 即 0, i j时