第四章 离散信源编码
- 格式：ppt
- 大小：251.00 KB
- 文档页数：28
下载文档原格式
合集下载
信息论与编码2016(第4章)
§4.2 离散无记忆信道 对称DMC容量的计算
P的所有列都是第一列的一种置换，信 道是关于输出对称的
0 .8 0 .2 P 0 .5 0 .5 0 .2 0 .8
§4.2 离散无记忆信道
命题2 若DMC关于输出为对称的，则当输入分布等概时，输 出分布等概。 证明 此时{p(y|x)，x=0~ K-1}与{p(0|x)，x=0~ K-1}互为置换。 设q(x)=1/K，x∈{0, 1, …, K-1}。则
q( z ) p( y | z )
都取一个相同的值；对任何满足q(k)=0的k，I(X=k; Y)都 不大于此相同的值。 （2）此时此相同的值恰好就是信道容量C。
§4.2 离散无记忆信道
注解
如果对DMC信道没有任何简化，要计算最佳输 入分布并不容易。但是，通常使用的DMC是很简单 的（比如，以下的准对称信道和对称信道），最佳 输入分布很容易求出。
§4.2 ቤተ መጻሕፍቲ ባይዱ散无记忆信道
定理4.2.2(p91) （1）输入概率分布{x, q(x), x∈{0, 1, …, K-1}}是最佳输入分 布的充分必要条件为：对任何满足q(k)>0的k，
I ( X k ; Y ) p( y | k ) log K 1
y 0 z 0 J 1
p( y | k )
第四章：信道及其容量
§4.1 §4.2 §4.5 §4.6 §4.7 信道分类 离散无记忆信道 信道的组合 时间离散的无记忆连续信道 波形信道
5
§4.1 信道分类
所有信道都有一个输入集A，一个输出集B以及 两者之间的联系，如条件概率P(y│x)，x∈A， y∈B。这些参量可用来规定一条信道。
信息论与编码 第四章
4. 信息率失真函数 R（D）
R( D) = min I ( X ; Y )
PD '
�
说明:
n pij ∈pD ' m
对于离散无记忆信源， R（D）函数可写成
R(D) = min ∑∑ p(xi ) p( y j / xi ) log
i=1 y j )
例4－1－2
�
说明: Dk是第k个符号的平均失真。
4.1.3 信息率失真函数 R（D）
�
1. 信息率失真函数R（D）问题产生? 对于信息容量为 C 的信道传输信息传输率为 R的信源时，如果R＞C，就必须对信源压缩， 使其压缩后信息传输率R 小于信道容量 C ，但 同时要保证压缩所引人的失真不超过预先规定 的限度,信息压缩问题就是对于给定的信源，在 满足平均失真
■
2. R(D)函数的下凸性和连续性
定理 R（D）在定义域内是下凸的 证明: 令
�
D = αD'+(1 − α)D' ' , 0 ≤α ≤1 R(D' ) = min I ( pij ) = I ( p'ij )
pij∈pD'
α
其中： p 是使I（Pij）达到极小值的 证D≤D’。
' ij
p ij ，且保
说明: (1) 由于xi和yj都是随机变量，所以失真函 数d(xi,yj)也是随机变量，限失真时的失真 值，只能用它的数学期望或统计平均值，因 此将失真函数的数学期望称为平均失真。
�
�
(2) p（xi,yj）, i=1,2,…,n， j=1,2,…,m是联合分布； p（xi）是信源 符号概率分布； p（yj ／xi），i= l， 2，…，n，j＝ l，2，…，m是转移概率 分布；d（xi,yj），i=1，2，…， n,j=1，2，… ，m是离散随机变量的 失真函数. (3)平均失真 D是对给定信源分布 p（xi） 在给定转移概率分布为 p（yj／xi）的信 道中传输时的失真的总体量度。
《信号处理原理》 第4章 信息失真率
d(0,2)=d(1,2)=0.5
则得失真矩阵
d
0 1
1 0
0.5 0.5
4.1 平均失真和信息率失真函数
说明：失真函数d (xi, yj) 的数值是依据实际应 用情况，用 yj代替xi, 所导致的失真大小是人为决 定的。比如上例中，用y=2代替x=0和x=1所导致 的失真程度相同，用0.5表示；而用y=0代替x=1 所导致的失真程度要大，用1表示。失真函数d (xi, yj) 的函数形式可以根据需要任意选取，例如平方 代价函数、绝对代价函数、均匀代价函数等。
信源编码器的目的是使编码后所需的信 息传输率R尽量小，然而R越小，引起的平 均失真就越大。给出一个失真的限制值D，
在满足平均失真 D D的条件下，选择一种
编码方法使信息率R尽可能小。信息率R就 是所需输出的有关信源X的信息量。
16
4.1 平均失真和信息率失真函数
将此问题对应到信道，即为接收端Y需要 获得的有关X的信息量，也就是互信息 I(X;Y)。这样，选择信源编码方法的问题就 变成了选择假想信道的问题，符号转移概 率p(yj/xi)就对应信道转移概率。
输入符号集 X:{a1, a2, …, an}中有n种不同的符 号xi (i =1, 2, …, n) ；输出符号集Y:{b1, b2, …, bm}中有m种不同的符号yj (j =1, 2, …, m)；对于 图所示的系统，对应于每一对(xi, yj)(i = 1, 2, …,n；j=1, 2, …, m)，定义一个非负实值函数
平均失真D是对给定信源分布p(ai)经过某一种 转移概率分布为p(bj|ai)的有失真信源编码器后产 生失真的总体量度。
13
4.1 平均失真和信息率失真函数
信息论基础与编码课件第四章 信息率失真函数
同样，可得Pij时的平均互信息为 I''(X;Y)0.37b9i/t符号
从此例我们可以看到，若固定P(x)不变时，平均互信息量随信
道的转移概率的变化而变化。这是因为信道受到干扰的作用 不同，传递的信息量也不同。可以证明这样一个结论：P(x)一 定时，平均互信息量I(X;Y)是关于信道的转移概率的下凸函数， 即存在一极小值。
m × n个 p i j 的值，代入平均失真的公式中，可解出随S参数值变
化的D值，即
D (S ) p ip j id ij p ip ij ie S d ijd ij （4-16）
ij
ij
25
离散信源的R(D)函数及其计算(续)
信源的信息率失真函数R(D)为
R (S ) i
j
pi p j i e Sdij
源输出符号序列 X (X 1 ,X 2 , ,X L ) ，其中L长符号序列样
值 Y(Y 1,Y 2, ,Y L) ，经信源编码后，输出符号序
列 x i (x i1 ,x i2 , ,x iL )
，其中L长符号序列样
值 y i (y i1 ,y i2 , ,y iL )，则失真函数定义为：
1L
dL(xi,yj)Ll1d(xil,yjl)
其中d(xil，yjl)是信源输出L长符号样值 x i 中的第l个符号xil时，
编码输出L长符号样值 中的y i 第l个符号yjl的失真函数。
7
平均失真
定义平均失真度为失真函数的数学期望，即 d ( xi , yj ) 在 X 和 Y的 联合概率空间 P(XY ) 中的统计平均值
nm
D E [d (x i,y j)] p (x i)p (y j|x i)d (x i,y j) （4-4） i 1j 1
信息论.第4章无失真信源编码
S N
1
P
p(1 )
2 ... p(2 ) ...
qN
p(qN )
扩展信源熵为H(SN)，
5
用码符号集X=(x1,…,xr)对SN 编码，则总可以找到
一种编码方法，构成唯一可译码，使信源S中的一
个信源符号所需要的码字平均长度满足
H (S) 1 LN H (S) log r N N log r
N log r 则当N足够大时，译码错误概率趋于1。
3
信源编码效率 编码速率：对于定长编码，编码速率定义为
R L log r N
编码效率：
H(S)
R
4
变长无失真信源编码定理（香农第一定理）
设离散无记忆信源
S
P
s1 p( s1 )
s2 p(s2 )
... ...
sq
p(
sq
)
其信源熵为H(S)，它的N次扩展信源SN为
l log q log r
2
定长信源编码定理
设有离散无记忆信源，熵为H(S) ，若对信源的长为N 的符号序列进行定长编码，设码字是从r个码符号集中选 取L个码元构成，对于 > 0 只要满足
L H(S)
N log r 则当N足够大时，可实现译码错误概率任意小的等长编
码，近似无失真编码。
反之，若 满足 L H (s) 2
i 1
克拉夫特证明不等式为即时码存在的充要条件； 麦克米伦证明不等式为唯一可译码存在的充要条件。
1
简单信源S存在唯一可译定长码的条件为：
q r l l log q
log r
N次扩展信源SN存在唯一可译定长码的条件为：
qN rL
L log r N log q来自L log q N log r
4-第四章-多符号离散信源与信道
P(Xi ) P(X j )
P( X i X i1) P( X j X j1)
P( X i X i1 X i2 X iN ) P( X j X j1 X j2 X jN )
信源
信道
信宿
X X1X2 X3...
X k X :{a1, a2 ,..., ar} (k=1,2,…)
p( X k ) { pk (a1), pk (a2 ),..., pk (ar )}
p(a3a1)
p(a3) p(a1)
1 4
1 4
1 16
p(8 )
p(a3a2 )
p(a3) p(a2 )
1 4
1 2
1 8
p(9 )
p(a3a3 )
p(a3) p(a3)
1 4
1 4
1 16
信源X2的信源空间：
X2: a1a1 a1a2 a1a3 a2a1 a2a2 a2a3 a3a1 a3a2 a3a3
rN
rr
r
p(i )
... p(ai1ai2...aiN )
i1
i11 i21 iN 1
rr
r
... p(ai1) p(ai2 )... p(aiN )
i11 i 21 iN 1
r
r
r
p(ai1) p(ai2 )... p(aiN )
i11
i 21
iN 1
1
记：X N X1X 2... X N
p( X Q ai1, X Q1 ai2 ,...,X QN 1 aiN ) p( XW ai1, XW 1 ai2 ,...,XW N 1 aiN ) p(ai1ai2...aiN )
(ai1, ai2,...,aiN {a1, a2,...,ar}; i1,i2,...,iN 1,2,...,r)
P( X i X i1) P( X j X j1)
P( X i X i1 X i2 X iN ) P( X j X j1 X j2 X jN )
信源
信道
信宿
X X1X2 X3...
X k X :{a1, a2 ,..., ar} (k=1,2,…)
p( X k ) { pk (a1), pk (a2 ),..., pk (ar )}
p(a3a1)
p(a3) p(a1)
1 4
1 4
1 16
p(8 )
p(a3a2 )
p(a3) p(a2 )
1 4
1 2
1 8
p(9 )
p(a3a3 )
p(a3) p(a3)
1 4
1 4
1 16
信源X2的信源空间：
X2: a1a1 a1a2 a1a3 a2a1 a2a2 a2a3 a3a1 a3a2 a3a3
rN
rr
r
p(i )
... p(ai1ai2...aiN )
i1
i11 i21 iN 1
rr
r
... p(ai1) p(ai2 )... p(aiN )
i11 i 21 iN 1
r
r
r
p(ai1) p(ai2 )... p(aiN )
i11
i 21
iN 1
1
记：X N X1X 2... X N
p( X Q ai1, X Q1 ai2 ,...,X QN 1 aiN ) p( XW ai1, XW 1 ai2 ,...,XW N 1 aiN ) p(ai1ai2...aiN )
(ai1, ai2,...,aiN {a1, a2,...,ar}; i1,i2,...,iN 1,2,...,r)
第四章 信息率失真函数
即:离散无记忆信源的N次扩展信源， 通过离散无记忆信 的N次扩展信道的平均失真度是单符号信源， 通过单符号 信道的N倍。 相应的保真度准则为：
D (N ) ND
例:设信源X取值于{0,1},失真函数数分别
为d(0,0)=d(1,1)=0,d(0,1)=d(1,0)=1.其N=3次
扩展信源的输入X=X1X2X3,经信道传导输 后,输出为Y=Y1Y2Y3,求失真矩阵[D(N)].
译码必定出错。
K L
log 2
m
H
(X
)
2
• 变长编码定理
– 若一离散无记忆信源的符号熵为H(X)，对信源 符号进行m元变长编码，一定存在一种无失真
编码方法，其码字平均长度满足下列不等式
1 H(X) K H(X)
log 2 m
log 2 m
信道编码定理
• 信道编码定理：若有一离散无记忆平稳信道，其
那么在允许一定程度失真的条件下，能 够把信源信息压缩到什么程度，也就是，允 许一定程度失真的条件下，如何能快速的传 输信息，这就是本章所要讨论的问题。
1、失真函数
信源
信源 编码
信道 信道 编码
信道 译码
信源 译码
信宿
干扰
根据信道编码定理，我们可以把信道编码、信道和信道 解码等价成是一个没有任何干扰的广义信道，这样收信者收 到消息后，所产生的失真只是由信源编码带来的。我们也可
(N)
I
(X
;Y
)
RN (D) NR(D)
§4.1.3 率失真函数性质
R(D)
连续
H(X)
离散
D D Dmax D
1 定义域：0, Dmax
D=0 R(D)=H(X)
D (N ) ND
例:设信源X取值于{0,1},失真函数数分别
为d(0,0)=d(1,1)=0,d(0,1)=d(1,0)=1.其N=3次
扩展信源的输入X=X1X2X3,经信道传导输 后,输出为Y=Y1Y2Y3,求失真矩阵[D(N)].
译码必定出错。
K L
log 2
m
H
(X
)
2
• 变长编码定理
– 若一离散无记忆信源的符号熵为H(X)，对信源 符号进行m元变长编码，一定存在一种无失真
编码方法，其码字平均长度满足下列不等式
1 H(X) K H(X)
log 2 m
log 2 m
信道编码定理
• 信道编码定理：若有一离散无记忆平稳信道，其
那么在允许一定程度失真的条件下，能 够把信源信息压缩到什么程度，也就是，允 许一定程度失真的条件下，如何能快速的传 输信息，这就是本章所要讨论的问题。
1、失真函数
信源
信源 编码
信道 信道 编码
信道 译码
信源 译码
信宿
干扰
根据信道编码定理，我们可以把信道编码、信道和信道 解码等价成是一个没有任何干扰的广义信道，这样收信者收 到消息后，所产生的失真只是由信源编码带来的。我们也可
(N)
I
(X
;Y
)
RN (D) NR(D)
§4.1.3 率失真函数性质
R(D)
连续
H(X)
离散
D D Dmax D
1 定义域：0, Dmax
D=0 R(D)=H(X)
第4章_无失真信源编码-zuoye
第一节 引言
信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个 定理。从编码结果使信源消息的信息量有无损失角度 无失真信源编码定理：香农第一定理 是离散信源/数字信号编码的基础； 限失真信源编码定理：香农第三定理 是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。
l •定理5.3的条件式也可写成： N log r H ( S ) l ' R log r 称之为编码信息率。可见，编码信息 令： N
率大于信源的熵，才能实现无失真编码。
第三节 等长信源编码定理
H (S ) H (S ) l R' log r N
为了衡量编码效果，引进
最佳编码效率为： R'
第四节 变长信源编码定理
定理5.8 无失真变长信源编码定理（香农第一定理） 离散无记忆信源S的N次扩展信源 S N ，其熵为 H (S N ) ，并且
{1 , 2 ,..., q } 对信源 S N 进行编 编码器的码元符号集为A：
码，总可以找到一种编码方法，构成唯一可译码，使信源S 中每个符号si所需要的平均码长满足 H ( S ) L N H ( S ) 1
li r 1 i 1 q
反之，若码长满足上式，则一定存在这样的即时码 。 可以根据即时码的树图构造法来证明。 后来，B.McMillan证明了对于唯一可译码也必须满足 上面的不等式，
第四节 变长信源编码定理
定理5.6 若存在一个码长为 l1 , l2 , , lq 唯一可译码，则一 定存在一个同样长度的即时码。 这说明，其他唯一可译码在码长方面并不比即时码 占优。所以在讨论唯一可译码时，只需要讨论即时码就 可以了。
信息论 第4章(哈夫曼编码和游程编码)
我们介绍的哈夫曼编码方法是对具有多个 独立消息的信源进行二进制编码,如果编码符 号（码元）不是二进制的0和1,而是D进制，同 样可以按照哈夫曼编码的方法来完成：只要将 哈夫曼编码树由二叉树换成D叉树,每次合并的 节点由两个改为D个,分配码元时,从左到右将0 到D－1依次分配给各个路段,最后从根节点到 各个叶节点（消息）读出编码结果即可.
游程编码的基本原理
很多信源产生的消息有一定相关性,往往 连续多次输出同样的消息,同一个消息连续输 出的个数称为游程(Run-Length).我们只需要 输出一个消息的样本和对应重复次数,就完全 可以恢复原来的消息系列.原始消息系列经过 这种方式编码后,就成为一个个编码单元(如下 图),其中标识码是一个能够和消息码区分的特 殊符号.
文件传真压缩方法具体流程
主要利用终止码和形成码(见书本P43-44), 一般A4的纸每行的像素为1728,具体编码规则 如下: （1）当游程长度小于64时，直接用一个对应 的终止码表示。 （2）当游程长度在64到1728之间时，用一个 形成码加一个终止码表示。 例如:白游程为662时用640形成码(白)加22终 止码(白)表示,即:01100111 0000011. 黑游程为256时用256形成码(黑)加0终止码(黑) 表示,即:000001011011 0000110111.
哈夫曼（Huffman） （3）哈夫曼（Huffman）编码
哈夫曼编码：将信源中的各个消息按概率排序， 不断将概率最小的两个消息进行合并，直到合 并为一个整体，然后根据合并的过程分配码字， 得到各个消息的编码。 该方法简单明了，并且可以保证最终的编 码方案一定是最优编码方案。
哈夫曼（Huffman） 哈夫曼（Huffman）编码的例子
香农编码的例子
游程编码的基本原理
很多信源产生的消息有一定相关性,往往 连续多次输出同样的消息,同一个消息连续输 出的个数称为游程(Run-Length).我们只需要 输出一个消息的样本和对应重复次数,就完全 可以恢复原来的消息系列.原始消息系列经过 这种方式编码后,就成为一个个编码单元(如下 图),其中标识码是一个能够和消息码区分的特 殊符号.
文件传真压缩方法具体流程
主要利用终止码和形成码(见书本P43-44), 一般A4的纸每行的像素为1728,具体编码规则 如下: （1）当游程长度小于64时，直接用一个对应 的终止码表示。 （2）当游程长度在64到1728之间时，用一个 形成码加一个终止码表示。 例如:白游程为662时用640形成码(白)加22终 止码(白)表示,即:01100111 0000011. 黑游程为256时用256形成码(黑)加0终止码(黑) 表示,即:000001011011 0000110111.
哈夫曼（Huffman） （3）哈夫曼（Huffman）编码
哈夫曼编码：将信源中的各个消息按概率排序， 不断将概率最小的两个消息进行合并，直到合 并为一个整体，然后根据合并的过程分配码字， 得到各个消息的编码。 该方法简单明了，并且可以保证最终的编 码方案一定是最优编码方案。
哈夫曼（Huffman） 哈夫曼（Huffman）编码的例子
香农编码的例子
信息论与编码理论-第4章无失真信源编码-习题解答-20071202
信息论与编码理论-第4章无失真信源编码-习题解答-20071202信息论与编码理论第4章无失真信源编码习题及其参考答案4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F（1）求这些码中哪些是唯一可译码；（2）求哪些码是及时码；（3）对所有唯一可译码求出其平均码长。
?X??s14-2 设信源????p(s)P(X)???1s6?p(s2)?p(s6)???s2?p(s)?1。
对此次能源进行m元唯一ii?16可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。
（提示：用kraft不等式）?s?X??14-3设信源为??1??p(X)???2?（1）信源的符号熵；（2）这种码的编码效率；s214s3s411816s5132s6s7s8?，编成这样的码：（000，001，111???64128128?010，011，100，101，110，111）。
求（3）相应的仙农码和费诺码。
4-4求概率分布为(,11122信)源的二元霍夫曼编码。
讨论此码对于概率分布为355151511111(,,,,)的信源也是最佳二元码。
555554-5有两个信源X和Y如下：1信息论与编码理论s2s3s4s5s6s7??X??s1??p(X)??0.200.190.180.170.150.100.01?????s2s3s4s5s6s7s8s9??Y??s1??p(Y)??0.490.140.140.070.070.040.020.02 0.01?????（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率；（2）从X，Y两种不同信源来比较三种编码方法的优缺点。
4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样霍夫曼码的信源的所有概率分布。
4-7设信源为?码。
信息论--第四章第五节 变长码 第六节 变长信源编码定理
4.5 变长码
即时码
唯一可译码成为即时码的充要条件：
一个唯一可译码成为即时码的充要条件是其中任何一个
码字都不是其他码字的前缀。
所有的码 非奇异码 唯一可译码 即时码
4.5 变长码
即时码的构造方法
用树图法可以方便地构造即时码。树中每个中间节
点都伸出1至r个树枝，将所有的码字都安排在终端
节点上就可以得到即时码。
H H (S )
从而
LN H lim N N log r
4.6变长信源编码定理
对一般离散信源，无失真信源编码定理证 明
S S1S2 S N
H (S) H (S) LN 1 log r log r
H (S) LN H (S) 1 N log r N N log r N
H (S ) L logr 0
p(si ) log p( si ) p( si )li log r
i 1 i 1 q q
p( si ) log p( si ) p( si ) log r
i 1 i 1
q
q
li
4.6变长信源编码定理
紧致码平均码长界限定理证明
4.5 变长码
2. 变长唯一可译码判别方法（续）
例5.4 ： C a c ad F1 d bb F2 eb cde F3 de F4 b F5 ad bcde
abb
bad deb bbcde 结论：F5中包含了C中的元素，因此该变长码不是唯一可译码。 问题： 判断 C={1,10,100,1000}是否是唯一可译码？
信道传信率
H (S ) H (S ) log r R H (S ) L log r
2.4 离散无失真信源编码定理
i i 1
8
8
2
pi 2.55bit / 符号
2 [ I ( xi )] E[ I 2 ( xi )] H 2 ( X ) 自信息方差为:
pi [ log2 pi ]2 H 2 ( X )
i 1
1.3082
对信源符号采用定长二元编码，要求编码效率 90% ，无记忆信源有 H L ( X ) H ( X ) ， 因此 可以得到
(2)正定理指出：当信息率 R 略大于单符号熵H(X)时可 做到几乎无失真译码，条件是L足够大。
即编码后发送一个消息符号所需的平均信息量大于信源
平均每消息符号的信息量时，可以使传输几乎无失真。
2 ( x) 可以证明，只要 L 2 ，译码差错率必小于。
2 ( x) E{[ I ( xi ) H ( X )]2}
H(X ) 90% H(X )
0.2836
如果要求译码错误概率
2 Βιβλιοθήκη 06 [ I ( xi )] 则 L 1.6256 107 2
由此可见，在对编码效率和译码错误概率的要求不 是十分苛刻的情况下，就需要1600多万个信源符号一起 进行编码，这对存储和处理技术的要求太高，目前还无 法实现。 如果对上述信源中8种可能的取值编定长码，每种取 值为3比特时，可实现译码无差错，但编码效率只有 2.55/3=85%。因此，一般说来，当L有限时，高传输效 率的定长码往往要引入一定的失真和译码错误。解决的 办法是可以采用变长编码。
2
变长编码定理：
对离散无记忆信源，消息长度为L，符号熵为 H(X),对信源进行m元变长编码，一定存在无失真的 信源编码方法，
其码字平均长度
K 满足：
8
8
2
pi 2.55bit / 符号
2 [ I ( xi )] E[ I 2 ( xi )] H 2 ( X ) 自信息方差为:
pi [ log2 pi ]2 H 2 ( X )
i 1
1.3082
对信源符号采用定长二元编码，要求编码效率 90% ，无记忆信源有 H L ( X ) H ( X ) ， 因此 可以得到
(2)正定理指出：当信息率 R 略大于单符号熵H(X)时可 做到几乎无失真译码，条件是L足够大。
即编码后发送一个消息符号所需的平均信息量大于信源
平均每消息符号的信息量时，可以使传输几乎无失真。
2 ( x) 可以证明，只要 L 2 ，译码差错率必小于。
2 ( x) E{[ I ( xi ) H ( X )]2}
H(X ) 90% H(X )
0.2836
如果要求译码错误概率
2 Βιβλιοθήκη 06 [ I ( xi )] 则 L 1.6256 107 2
由此可见，在对编码效率和译码错误概率的要求不 是十分苛刻的情况下，就需要1600多万个信源符号一起 进行编码，这对存储和处理技术的要求太高，目前还无 法实现。 如果对上述信源中8种可能的取值编定长码，每种取 值为3比特时，可实现译码无差错，但编码效率只有 2.55/3=85%。因此，一般说来，当L有限时，高传输效 率的定长码往往要引入一定的失真和译码错误。解决的 办法是可以采用变长编码。
2
变长编码定理：
对离散无记忆信源，消息长度为L，符号熵为 H(X),对信源进行m元变长编码，一定存在无失真的 信源编码方法，
其码字平均长度
K 满足：
第四章无失真信源编码
一般来说H：(S当) L有限时，高传输效率的等长码往往要 2
而：引入H(S一) 定i的1 p失i lo真g pi和 0错.81误1(b，it/信它源不符能号）象变长编码那样可以
则：实现0.8真11正的0.无811失真0.9编6码 0.96 0.034
且：
2
2
pi(log
p2 i)
[H(S)]2
P(
A
)
1
2 L
2 表示S中每个符号携带的信息量的方差
本次您浏览到是第十四页，共一百一十四页。
2E 2{I(si)E [I(si)]}
E { I 2 ( s i) 2 I ( s i) • E [ I ( s i) ] E 2 [ I ( s i) ] } E[I2(si)]E2[I(si)]
第四章无失真信源编 码
本次您浏览到是第一页，共一百一十四页。
无失真信源编码
• 无失真编码概述 • 定长信源编码 • 变长信源编码 • 实用的无失真信源编码方法举例
本次您浏览到是第二页，共一百一十四页。
§4.1无失真编码概述－1
离散、无失真、无记忆信源编码的一般模型：
S (S1SL)
入
信源 编码
§4.3变长信源编码-1
• 几个码类的概念 – 非奇异码（单义码） – 唯一可译码 – 前缀码（即时码、非延长码、异前置码）
– 最佳码（紧致码）
• Kraft定理－－－即时码码长必须满足的条件
• 唯一可译码存在定理
• 变长编码定理（香农第一定理）
本次您浏览到是第二十四页，共一百一十四页。
§4.3变长信源编码-2(几个码类的概念)
方法： 进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列
而：引入H(S一) 定i的1 p失i lo真g pi和 0错.81误1(b，it/信它源不符能号）象变长编码那样可以
则：实现0.8真11正的0.无811失真0.9编6码 0.96 0.034
且：
2
2
pi(log
p2 i)
[H(S)]2
P(
A
)
1
2 L
2 表示S中每个符号携带的信息量的方差
本次您浏览到是第十四页，共一百一十四页。
2E 2{I(si)E [I(si)]}
E { I 2 ( s i) 2 I ( s i) • E [ I ( s i) ] E 2 [ I ( s i) ] } E[I2(si)]E2[I(si)]
第四章无失真信源编 码
本次您浏览到是第一页，共一百一十四页。
无失真信源编码
• 无失真编码概述 • 定长信源编码 • 变长信源编码 • 实用的无失真信源编码方法举例
本次您浏览到是第二页，共一百一十四页。
§4.1无失真编码概述－1
离散、无失真、无记忆信源编码的一般模型：
S (S1SL)
入
信源 编码
§4.3变长信源编码-1
• 几个码类的概念 – 非奇异码（单义码） – 唯一可译码 – 前缀码（即时码、非延长码、异前置码）
– 最佳码（紧致码）
• Kraft定理－－－即时码码长必须满足的条件
• 唯一可译码存在定理
• 变长编码定理（香农第一定理）
本次您浏览到是第二十四页，共一百一十四页。
§4.3变长信源编码-2(几个码类的概念)
方法： 进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列
第四章：无失真信源编码
符号集大小为m
总码组合数：mK
§4.1无失真编码概述－2
• 问题：能否进行无失真编码?怎样进行无失真编码?
(前提：不考虑信源统计特性)
• 应满足条件：
nL mK
消息数码字数
无失真： nLmK 有效： nLmK
相互矛盾！
无失真条件变换
nLmKKlong L lom g
结论：①当 n = m 时，K≥L 不有效。
结论：可见,需要4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的.
无失真信源编码实现方法一
Sp
s1 43
s2
1 4
改变信源
S pL s n 1L 1
sL2 sL3
11 nn
sLn
1 n
sL nm
0
sL
定长编码
1~ n
cK 1~ n
无失真信源编码实现方法二
S
p
s1
的集合
§4.2定长编码定理－9- AEP应用
• AEP结论：当L足够大时，
– 所有 典型序列出现的概率近似相等，即 典型序列为渐
进等概序列
– 可粗略认为 典型序列出现的概率为 2LH(S) – 所有 典型序列的概率和接近为1，即 p(A)1 – 典型序列总数占信源序列的总数
G L nL
2
（每位二元符号可以携带1bit信息，即每个英文电报符号用了可以携带
5bit信息的码符号即5位二元码表示）
讨论：第三章：在考虑符号出现的概率和符号间相关性前提下,每个 英文符号平均携带的信息量是1.4bit/符号<<5bit/码符号。
结论：若不考虑信源统计特性等长编码效率极低! 问题：如何提高效率？如何体现有效性？
总码组合数：mK
§4.1无失真编码概述－2
• 问题：能否进行无失真编码?怎样进行无失真编码?
(前提：不考虑信源统计特性)
• 应满足条件：
nL mK
消息数码字数
无失真： nLmK 有效： nLmK
相互矛盾！
无失真条件变换
nLmKKlong L lom g
结论：①当 n = m 时，K≥L 不有效。
结论：可见,需要4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的.
无失真信源编码实现方法一
Sp
s1 43
s2
1 4
改变信源
S pL s n 1L 1
sL2 sL3
11 nn
sLn
1 n
sL nm
0
sL
定长编码
1~ n
cK 1~ n
无失真信源编码实现方法二
S
p
s1
的集合
§4.2定长编码定理－9- AEP应用
• AEP结论：当L足够大时，
– 所有 典型序列出现的概率近似相等，即 典型序列为渐
进等概序列
– 可粗略认为 典型序列出现的概率为 2LH(S) – 所有 典型序列的概率和接近为1，即 p(A)1 – 典型序列总数占信源序列的总数
G L nL
2
（每位二元符号可以携带1bit信息，即每个英文电报符号用了可以携带
5bit信息的码符号即5位二元码表示）
讨论：第三章：在考虑符号出现的概率和符号间相关性前提下,每个 英文符号平均携带的信息量是1.4bit/符号<<5bit/码符号。
结论：若不考虑信源统计特性等长编码效率极低! 问题：如何提高效率？如何体现有效性？
通信技术基础 第四章 数字编码技术
提高编码效率的角度出发，L的取值应尽量的小。例如，对26个英文字
母进行二进制编码时，Lmin=log226=4.7，因此可取L=5。 常用信息码有ASCII码、Morse码、BCD码等。 大连理工大学出版社
第4章 数字编码技术 4.1.2 语音编码
模拟信息的数字化原因：
由于数字通信在信号的传输质量、信号的处理等方面具
缺点：收发双方的压扩特性不易做得一致，且温度等因素的影响大。
大连理工大学出版社
第4章 数字编码技术
均匀量化存在的问题是： 小信号时信噪比太小，大信号时信噪比浪费。
非均匀量化的 均匀量化的 量化信噪比 量化信噪比
动态范围 动态范围 要求的量化 信噪比
大连理工大学出版社
信号电平
第4章 数字编码技术
3 编码(Coding) 用一组代码来表示每一个量化后的样值。量化以后每一个样值都
0
比较电平
取样值
取样值
c11 c1 c9 c8 c7 c5 c4 c3 c2 c1 c0
0
量化值
量 化 后 信 号 波 形
大连理工大学出版社
第4章 数字编码技术
量化可以有均匀量化和非均匀量化两种
均匀量化:各量化电平之间的间隔是固定的，这种量化被称为均匀量化；
均匀量化的量化噪声功率与量化台阶的平方成正比，出现话音弱时的 信噪比低、干扰大，而话音强时的信噪比高、干扰小的反常情况，
样信号的小样值部分被充分放大，
大样值部分被适当压缩。被压缩 的抽样信号虽然再经过均匀量化；
接收端相应增加非线性放大器 （扩张），以消除压缩带来的信 号失真：对小信号放大量小，对
大信号放大量大。
大连理工大学出版社
第4章 数字编码技术
编码理论第4章
4.1.2 信源编码器 为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，这样 信息传输系统模型变为图4-1所示。
u1
信源
u2 un
信源编码器
w1 a1 w2 a 2
信道
信源译码器
信宿
wn a r
图4-1 简化信息系统传输模型
概念 信源符号 二元信源 n元信源 码符号集
码符号 码元 码字 码组 码长
4.2 无失真信源编码原理
• 4.2.1 等长码及其编码定理 • 4.2.2 变长码的平均码长及编码效率
• 对n元基本离散信源，设编码后各码字的码长分别为l1 ,l2 ,…，ln, 则定义码的平均码长度为
L p(ui )（码符合/ 信源符号） li
i 1
n
• 编码的效率η为
H m (U ) L
符号 概率 u 1 0 .4 u2 u3 u4 u5 0 .2 0 .2 0 .1 0 .1
0 1
码字
码长 2 2 2 3 3
0 .4 0 .2 0 .2 0 .2
0 1
0 .4 0 .4 0 .2
0 1
0 .6 0 .4
0 1
1 .0
00 10 11 010 011
(a)
图5-2 例5-2 两种霍夫曼编码
• 4.1.6 即时码的树图构造 • 树图法是构造即时码的一种简单方法。树是n个 结点的集合，这n个结点中有且仅有一个作为根 的结点，其余的结点可分为m个互不相交的子集， 每个子集本身又是一棵树，称为根的子树，也叫 根的树枝数。 • 树图与信源符号编码之间对应关系： • 树根 码字的起点 • 树的度 码的进制数 • 分支结点 码的符号的一部分 • 终端结点 待编码符号 • 满树 等长码 • 非满树 变长码