当前位置：文档之家 › 第五章 无失真信源编码-习题课-2013

第五章 无失真信源编码-习题课-2013

  • 格式：pdf
  • 大小：196.92 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

第五章 信源编码-习题答案

第五章 信源编码-习题答案

00000000 8 0 5.6 有二元平稳马氏链，已知 p(0/0) = 0.8，p(1/1) = 0.7，求它的符号熵。用三个符号合成一个来编写二进 制哈夫曼码，求新符号的平均码字长度和编码效率。 5.7 对题 5.6 的信源进行游程编码。若“0”游程长度的截至值为 16， “1”游程长度的截至值为 8，求编码 效率。 5.8 选择帧长 N = 64 (1) 对 0010000000000000000000000000000001000000000000000000000000000000 遍 L-D 码； (2) 对 1000010000101100000000010010000101001000000001110000010000000010 遍 L-D 码再译码； (3) 对 0000000000000000000000000000000000000000000000000000000000000000 遍 L-D 码； (4) 对 10100011010111000110001110100110000111101100101000110101011010010 遍 L-D 码； (5) 对上述结果进行讨论。
x3 x4 x5 x 6 x 7 X x1 x2 5.1 设信源 P ( X ) 0.2 0.19 0.18 0.17 0.15 0.1 0.01
(1) 求信源熵 H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率。
解： (1)
H ( X ) p ( xi ) log 2 p( xi )
K ki p( xi ) 3 0.2 3 0.19 3 0.18 3 0.17 3 0.15 4 0.1 7 0.01

李梅李亦农《信息论基础教程》-教案-第五章无失真信源编码PPT课件

李梅李亦农《信息论基础教程》-教案-第五章无失真信源编码PPT课件

第五章：无失真信源编码
一、信源编码的相关概念
6. 唯一可译性（续2）
例1：
1) 奇异码
s1 0 s 2 11 s 3 00 s 4 11
译码
s2
11
s4
奇异码一定不是唯一可译码
第五章：无失真信源编码
一、信源编码的相关概念
6. 唯一可译性（续3）
2) 非奇异码
s1 0 s 2 10 s 3 00 s 4 01
二次扩展信源符号
sj(j1,2,...,16)
s1 s1s1 s2 s1s2 s3 s1s3
二次扩展码码字
wj(j1,2,...,16)
w1 w1w1 00 w2w1w2001 w3w1w30001
s16 s4s4
w 16w 4w 4111111
第五章：无失真信源编码
一、信源编码的相关概念
4. 关于编码的一些术语
编码器输出的码符号序列 w i 称为码字；长度 l i 称为码
字长度，简称码长；全体码字的集合C称为码。 若码符号集合为X={0,1}，则所得的码字都是二元序
列，称为二元码。
将信源符号集中的每个信源符号 s i 固定的映射成某
一个码字 w i ，这样的码称为分组码。
若一个码中所有码字的码长都相等，则称为定长码； 否则为变长码。
Ss1 ,s2, ,sq
编码器
C{w1,w2, ,wq}
X:{x1,x2,..x.r,}
码字 wi xi1xi2 xili
将信源符号集中的符号s （i 或者长为N的信源符号序
列）映射成由码符号x i 组成的长度为l i 的一一对应的码
符号序列w i 。
第五章：无失真信源编码

信息论基础与应用-李梅-第五章 无失真信源编码解析

信息论基础与应用-李梅-第五章 无失真信源编码解析
s1 s1s1 s 2 s1s2 s3 s1s3 s16 s4 s4
二次扩展码码字 w j ( j 1, 2,...,16)
w1 w1w1 00 w 2 w1w2 001 w3 w1w3 0001 w16 w4 w4 111111
第五章：无失真信源编码
一、信源编码的相关概念
4. 关于编码的一些术语

编码器输出的码符号序列 wi称为码字；长度 li 称为码 字长度，简称码长；全体码字的集合C称为码。 若码符号集合为X={0,1}，则所得的码字都是二元序 列，称为二元码。

将信源符号集中的每个信源符号
si 固定的映射成某
一个码字 wi ，这样的码称为分组码。
码字与信源符号一一对应
2) 不同的信源符号序列对应不同的码字序列
第五章：无失真信源编码
一、信源编码的相关概念
6. 唯一可译性（续2）
例1：
1) 奇异码
s1 s2 s3 s4
0 11 00 Байду номын сангаас1
译码 11
s2 s4
奇异码一定不是唯一可译码
第五章：无失真信源编码
一、信源编码的相关概念
6. 唯一可译性（续3）
译码 0 0 0 1 1 0 1 1
s1s2 s3 s4
第五章：无失真信源编码
一、信源编码的相关概念
6. 唯一可译性（续5）
4)
唯一可译码 1 1 0 1 0 0 1 0 0 0 0
s1 s2
1 10
1 0
1
s2 / s3 ?
s3 100 s4 1000

为非即时码
第五章：无失真信源编码
一、信源编码的相关概念

信息论第五章 信源编码习题答案

信息论第五章 信源编码习题答案
0
1111110
7
x8
0.0078125
1
1111111
7
(3)
香农编码效率：
费诺编码效率：
(4)
xi
p(xi)
编码
码字
ki
x1
0.5
0
0
1
x2
0.25
1
1
1
x3
0.125
2
0
20
2
x4
0.0625
1
21
2
x5
0.03125
2
0
220
3
x6
0.015625
1
221
3
x7
0.0078125
2
0
2220
100
x5
0.15
0.74
3
101
x6
0.1
0.89
4
1110
x7
0.01
0.99
7
1111110
1)
0.0 --- 0.000000
2)
0.2*2 = 0.4 0
0.4*2 = 0.8 0
0.8*2 = 1.6 1
3)
0.39 * 2 = 0.78 0
0.78 * 2 = 1.56 1
0.56 * 2 = 1.12 ki
x1
0.2
0
0
00
2
x2
0.19
1
0
010
3
x3
0.18
1
011
3
x4
0.17
1
0
10
2
x5
0.15
1

第5章-无失真信源编码-题与答案

第5章-无失真信源编码-题与答案
码字中有2个“1”，错误概率：
码字中有3个“1”，错误概率：
5.9设有离散无记忆信源
码符号集 ，现对该信源 进行三元哈夫曼编码，试求信源熵 ，码平均长度 和编码效率 。
解：
满树叶子节点的个数： ， ，不能构成满树。
11
222
212
202
022
012
0003
0013
5.1有一信源，它有6个可能的输出，其概率分布如题5.1表所示，表中给出了对应的码 和 。
题表 5.1
消息
p(ai)
A
B
C
D
E
F
a1
1/2
000
0
0
0
0
0
a2
1/4
001
01
10
10
10
100
a3
1/16
010
011
110
110
1100
101
a4
1/16
011
0Hale Waihona Puke 1111101110
1101
110
a5
(1) 求码字所需要的长度；
(2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率 是多少？
解：
(1)
码字中有0个“1”，码字的个数：
码字中有1个“1”，码字的个数：
码字中有2个“1”，码字的个数：
码字中有3个“1”，码字的个数：
(2)
码字中有0个“1”，错误概率：
码字中有1个“1”，错误概率：
1/16
100
01111
11110
1011
1100
111
a6
1/16

信息论基础第5章无失真信源编码

信息论基础第5章无失真信源编码
进行霍夫曼编码时，应把合并后的概率总是放在 其他相同概率的信源符号之上，以得到码长方差最小 的码。
r 元霍夫曼编码步骤：
1) 验证所给 q 是否满足 q (r 1) r ，若不满足该式，
可以人为地增加 t 个概率为零的符号，满足式
n (r 1) r ，以使最后一步有 r 个信源符号；
2) 取概率最小的 r 个符号合并成一个新符号，并分别用 0， 1，…，(r 1) 给各分支赋值，把这些符号的概率相加作为该新 符号的概率；
上述不等式只是即时码存在的充要条件，而不能作为判别的依据。
需要注意的是，克拉夫特不等式是即时码存在的充要条件，而 不能作为判别的依据。后来麦克米伦（B. McMillan）证明唯一可译 码也满足克拉夫特不等式。这说明在码长选择的条件上，即时码与 唯一可译码是一致的。
【例】 对于二元码，即 r 2 ，如果 q 4 ， L1 2 ， L2 2 ，
原始信源普遍存在剩余度，香农信息论认为信源的剩余度主 要来自两个方面：一是信源符号间的相关性，二是信源符号概率 分布的不均匀性。为了去除信源剩余度，提高信源的信息传输率， 必须对信源进行压缩编码。
目前去除信源符号间相关性的主要方法是预测编码和变换编 码，而去除信源符号概率分布不均匀性的主要方法是统计编码。
《信息论基础》
第5章 无失真信源编码
第 2 章已经讨论了离散信源的信息度量—信源熵， 本章将讨论信源的另一个重要问题：如何对信源的输出 进行适当的编码，才能用尽可能少的码元来表示信源信 息，做到以最大的信息传输率无差错地传输信息呢？即 无失真信源编码，它解决的是通信的有效性问题。
本章将首先介绍信源编码器；然后从理论上阐述无 失真信源编码定理，得出“平均码长的理论极限值就是

(信息论)第5章无失真信源编码

(信息论)第5章无失真信源编码
这就是说，每个英文电报符号至少要用5位二元符号进行 编码才能得到唯一可译码。 12
定长编码定理
定长信源编码定理讨论了编码的有关参数对译 码差错的限制关系
sq p s q
定理 5.3.1 设离散无记忆信源
S s1 P p s 1 p s 2 s2
的熵为H S ，其 N 次扩展信源为
S N 1 p 1 P
2 q p 2 p q

N N

现在用码符号集 X x1 , x2 ,, xr 对N次扩展信源 S N 进行长度为 l 的定长编码，对于 0, 0 ，只要满足
l H S N log r
则当 N 足够大时，译码错误概率为任意小，几乎可以实 现无失真编码。 反之，若满足
l H S 2 N log r
则不可能实现无失真编码。而当N足够大时，译码错误概 14 率近似等于1。

以上的定理5.3.1 和定理5.3.2实际上说明的是一个 问题，虽然该定理是在平稳无记忆离散信源的条件下 证明的，但它也同样适合于平稳有记忆信源，只要要 2 求有记忆信源的极限熵 H S 和极限方差 存在 即可。对于平稳有记忆信源，式(5.6)和式(5.7 ) 中 H S 应该为极限熵 H S 。
变长码(可变长度码)
2
奇异码：若码中所有码字都不相同，则称此码为非
奇异码。反之，称为奇异码。
同价码：每个码符号所占的传输时间都相同的码。定
长码中每个码字的传输时间相同。而变长码中的每个码 字的传输时间不一定相等。
表 5.1
信源符号si
信源符号出现概率 si p

信息论与编码第五章课后习题答案

信息论与编码第五章课后习题答案

第五章课后习题【5.1】某信源按43)0(=P ，41)1(=P 的概率产生统计独立的二元序列。

（1）试求0N ，使当0N N >时有01.005.0)()(≤≥−S H N I P i α 式中，)(S H 是信源的熵。

（2）试求当0N N =时典型序列集N G ε中含有的信源序列个数。

解：（1）该信源的信源熵为811.0)(log )()(=−=∑i i s p s p S H 比特/符号自信息的方差为4715.0811.04log 4134log 43)()]([)]([22222=−+=−=S H s I E s I D i i 根据等长码编码定理，我们知道δεα−≤≥−1)()(S H N I P i 根据给定条件可知，05.0=ε，99.0=δ。

而[]2)(εδN s I D i =因此[]5.19099.0*05.04715.0)(220==≥δεi s I D N 取1910=N 。

（2）ε典型序列中信源序列个数取值范围为：])([])([22)1(εεεδ+−<<−S H N N S H N G代入上述数值得451.164351.1452201.0<<×N G ε【5.2】有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A 、B 、C 、D 、E 和F 。

表5.2消息 )(i a P A B C D E F 1a 1/2 000 0 0 0 0 0 2a 1/4 001 01 10 10 10 100 3a 1/16 010 011 110 110 1100 101 4a 1/16 011 0111 1110 1110 1101 110 5a 1/16 100 01111 11110 1011 1110 111 6a1/1610101111111111011011111011（1） 求这些码中哪些是惟一可译码； （2） 求哪些码是非延长码（即时码）； （3） 求对所有惟一可译码求出其平均码长L 。

第五章 无失真信源编码

第五章 无失真信源编码

第五章 无失真信源编码在第二章与第三章，我们给出了计算信源信息量的方法，在这一章，我们要讲 如何用二进制符号（当然也可采用别的方式）来表示各个信源符号（这个过程 叫信源编码）。

在这个过程中，我们要思考的问题主要是：如何给出一种好的信源编码方法？ 我们要解决这样两个问题：1：从理论上来讲，信源编码的编码效率最好能好到什么程度？2：从设计算法的角度来讲，如何使得你的编码算法的效率非常接近最佳的编码效率？ 首先我们要谈谈评价信源编码好坏的标准：一：编码的正确性 一个好的信源编码方法首先必须是正确的。

也就是说， 当信宿接收到信源发出的经过信源编码的信息后，它能正确地译码成 信源符号。

为了保证能正确译码，在编码时必须让一个信源符号或 多个信源符号构成的串对应的二进制符号串是唯一的（我们把这种编码 称为唯一可译码）。

唯一可译码要满足什么条件呢？设一个信源符号在信源编码时称为一个码字，首先唯一可译码要求任何两个不同 的信源符号在信源编码时不能用同一个码字表示：如下面的四种编码方法中，码1c 就不是一种唯一可译码。

因为在码1c 中，2s 与4s 的编码都为11，这样信宿就不知道该把11翻译成4s 还是2s （我们把码1c 这种编码方法称为奇异码）。

那么是否所有的非奇异码都是唯一可译的呢？不一定，因为在对某些非奇异码进行译码时我们无法确定一串二进制符号 对应的是一个码字还是多个码字。

如对于码2c 来说，00既可以翻译成11s s ，也可翻译成3s ，所以码2c 还不是唯一可译码。

我们的结论是：若对于任意有限的整数N ，其N 阶扩展码均为非奇 异的，则是唯一可译码。

二：译码的效率高低在编码时不仅要考虑能否正确译码，还要考虑译码的速度是否很快。

讲个例子说明这个问题。

上面的码3c 与码4c 都是唯一可译码，但两种码在译码的时候效率是不一样的。

对于码3c 来说，当信宿接收到符号1时，它不能马上对1进行译码，它必须 等接收到1后面的符号再译码，若1后的符号是1，则可把前一个1翻译成1s ；若1后的符号是0，则信宿也不能马上对10进行译码。

信息论基础与应用-李梅-第五章 无失真信源编码资料

信息论基础与应用-李梅-第五章 无失真信源编码资料
p(s2)=1/4 p(s3)=1/8 p(s4)=1/8
00
01 10 11
0
01 001 111
第五章：无失真信源编码
一、信源编码的相关概念
3. N次扩展码
S s1 , s2 ,, sq


siBiblioteka C {w1 , w2 ,
, wq }
wi
S s1 , s2 ,
N

, sqN

s jN
计匹配编码，根据信源的不同概率分布而选用与之相 匹配的码。
第五章：无失真信源编码
一、信源编码的相关概念
1. 信源编码概述（续2）

信源的统计剩余度主要决定于以下两个因素 ： 1）无记忆信源中，符号概率分布的非均匀性； 2）有记忆信源中，符号间的相关性及符号概率分布 的非均匀性。

怎样压缩信源的冗余度？
C N {w1 , w 2 ,, w q N }
w j w j1 w j2 w jN
s j s j1 s j2
j 1,2,, q N
j1 , j2 ,, jN 1,2,, q
第五章：无失真信源编码
一、信源编码的相关概念
3. N次扩展码（续1）
二次扩展信源符号 s j ( j 1, 2,...,16)
若一个码中所有码字的码长都相等，则称为定长码；
否则为变长码。
第五章：无失真信源编码
一、信源编码的相关概念
5. 奇异性
若一个码中所有码字互不相同，则称为非奇异码； 否则为奇异码。
信源符号si 码1 码2
s1 s2 s3 s4
0 11 00 11
0 10 00 01
第五章：无失真信源编码

第五章 无失真信源编码定理

第五章 无失真信源编码定理
则不可能实现无失真编码。
第三节 等长信源编码定理
•定理5.3的条件式可写为：
长为l 的码符号所能 载荷的最大信息量 长为N的序列平均携带的信息量
l log r > NH ( S )
只要码字传输的信息量大于信源序列携带的 信息量，总可以实现无失真编码。 l •定理5.3的条件式也可写成： log r H ( S ) e N
i
N
1
2
N
是一一对应的：
i Bi (Wi1 ,Wi2 , ,WiN ), i S ,Wil C
N
4）惟一可译码 若任意一串有限长的码符号序列只能被惟 一地译成所对应的信源符号序列，则此码称 为惟一可译码（或称单义可译码）；否则就 称为非惟一可译码或非单义可译码。
例：对于二元码 C1 {1, 01, 00} ，当任意给定一串 码字序列，例如“10001101”，只可唯一地划 分为1,00,01,1,01，因此是惟一可译码；而对 另一个二元码 C 2 {0,10, 01} ，当码字序列为 “01001”时，可划分为0,10,01或01,0,01，所 以是非惟一可译的。
P(G eN )
-
(2) 若 i (si1, s i2 ,...,s iN ) GeN，则 2 - N [ H ( s )e ] < P( i ) < 2 - N [ H ( s ) -e ] (3) || GeN || 表示e典型序列集中 e典型序列的个数，则 (1 - )2 N [ H ( s )-e ] <|| GeN ||< 2 N [ H ( s ) e ]
1 N - log P ( si ) 以概率收敛于均值 H ( s ) 熵定义 N i 1 1 N 1 即 - log P ( s i ) - log[ P ( s i ) P ( s 2 ) L P ( s N )] N次扩展信源 N i 1 N 1 - log P ( si s 2 L s N ) H ( S ) 以概率收敛 N 因为 i1 ( si1 si 2 L s i N ) S1 S 2 L S N , (i 1, 2 , L , q N i1 , i2 , L , i N 1, 2 , L , q )

信源编码(数据压缩)课程课后题与答案(第五章)

信源编码(数据压缩)课程课后题与答案(第五章)

信源编码Assignment of CH51、（a）人类视觉特性中空间频率灵敏度、对比度灵敏度和色彩灵敏度分别表示什么意思？空间频率灵敏度可以表示为人眼所能识别的落在视网膜上的光栅数量的范围，这个数量和人眼距离图像的距离有关。

距离越近，人眼所能识别到的最大光栅密集程度（频率）越高；距离越远，所能识别到的最大光栅密集程度（频率）越低。

对比度灵敏度可以表示在某一光栅频率上，为人眼所能识别到的黑白区域对比度的范围（也可以说是对比度的最小值）。

这个识别灵敏度与光栅的频率有关，当频率过高或过低，人眼的对比度灵敏度都会有所下降。

图1. 人眼空间频率灵敏度与对比度灵敏度的关系色彩灵敏度可以表示为人眼能够观察到的色域范围或对色彩光的感知范围。

这个范围取决于各色光的频率和亮度，人眼只能观察到一定频率范围内的各种色彩。

可见光的波长约在380至780 nm之间，其中黄绿色对人眼的敏感度最高。

波长为480nm的蓝色光和波长为650nm的红色光的敏感度最低。

图2. 人眼能够识别的色彩范围（b）JPEG编码算法是如何利用这些灵敏度特性的？比如在JPEG编码算法中，利用到了人眼的空间频率灵敏度特性在高频处不敏感的特点。

对图像进行DCT离散余弦变换时，将图像的低频分量进行重点保护，采用高量化精度的压缩编码或者无失真熵编码等方式，对于DC直流分量直接采取单独差分编码的方式。

而对高频分量来说，可以采取低量化精度的编码方式，适量地放弃一部分高频信息，而对图片的整体视觉效果产生很小的影响。

再如利用人眼的色彩灵敏度特性对色彩信号的灵敏度低于亮度信号的特点，对图像的每个像素点采用4:2:2或4:2:0的灰度：色差：色差信号压缩比，减小了色彩信号的数据量，既能保证数据压缩效果又可以保持较好的视觉效果。

2、（a）图像编码算法常用的知名算法有那些？首先，常用的图像编码算法中的无失真压缩算法主要有：霍夫曼编码、LZW 编码、游程编码和算术编码。

其主要用在编码器后端对已经经过分析、变换和量化的图像信息进行最后的压缩处理，然后传输到信道编码端。

第五章 无失真信源编码13

第五章 无失真信源编码13
H ( S ) LN H ( S ) 1 log r N log r N
N 其中， 为 S中每个信源符号序列 编码所对应的码字的平均 LN i 码长。
LN p( i )i , i为 i 所对应的码字的长度
i 1
qN
LN : 离散无记忆信源 S中每个信源符号 S i 所对应的平均码长 N
li r 1 i 1 q
(kraft不等式）
2.McMillan不等式
在满足kraft不等式的条件下，唯一可译码存在的充要条 q 件是：
li r 1 i 1
( McMillan 不等式）
三.唯一可译码判断准则
设S0为原始码字的集合。再构造一系列集合S1,S2,…Sn。 构造S1,S2,… Sn的方法： 1、首先考察S0中所有的码字。若码字Wj是码字Wi的前缀， 即Wi = WjA，则将后缀A列为S1中的元素，S1就是由所有 具有这种性质的A构成的集合。 2、当n>1，则将S0于Sn-1比较，看是否S0中的码字是Sn-1的 前缀，如果是，则取后缀为Sn中元素，且看Sn-1中码字是否 为S0中码字的前缀，如果是，则取后缀为Sn中元素，如此构 成集合Sn。
3.编码器的数学模型
信源发出的消息符号集
S S1 , S 2 ,..., S q


信源编码器
信道的基本符号集合
输出的码字集合C（代码组）
C W1 ,W2 ,...,Wq


X x1 , x2 ,..., xq


其中：Wi称为码字，如果码字由N个码元组成，则码长为N。
xi 称为码元,或码符号
第二节 离散无记忆信源的定长编码
一.离散无记忆信源的唯一可译码存在条件

信息论与编码第五章习题参考答案

信息论与编码第五章习题参考答案

信息论与编码第五章习题参考答案5.1某离散⽆记忆信源的概率空间为采⽤⾹农码和费诺码对该信源进⾏⼆进制变长编码，写出编码输出码字，并且求出平均码长和编码效率。

解：计算相应的⾃信息量1)()(11=-=a lbp a I ⽐特 2)()(22=-=a lbp a I ⽐特 3)()(313=-=a lbp a I ⽐特 4)()(44=-=a lbp a I ⽐特 5)()(55=-=a lbp a I ⽐特 6)() (66=-=a lbp a I ⽐特 7)()(77=-=a lbp a I ⽐特 7)()(77=-=a lbp a I ⽐特根据⾹农码编码⽅法确定码长1)()(+<≤i i i a I l a I平均码长984375.164/6317128/17128/1664/1532/1416/138/124/112/1L 1=+=?+?+?+?+?+?+?+?=由于每个符号的码长等于⾃信息量，所以编码效率为1。

费罗马编码过程5.2某离散⽆记忆信源的概率空间为使⽤费罗码对该信源的扩展信源进⾏⼆进制变长编码，(1) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

(2) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

(3) 扩展信源长度，写出编码码字，计算平均码长和编码效率，并且与(1)的结果进⾏⽐较。

解：信息熵811.025.025.075.075.0)(=--=lb lb X H ⽐特/符号（1）平均码长11=L ⽐特/符号编码效率为%1.81X)（H 11==L η（2）平均码长为84375.0）3161316321631169（212=?+?+?+?=L ⽐特/符号编码效率%9684375.0811.0X)（H 22===L η（3）当N=4时，序列码长309.3725617256362563352569442569242562732562732256814=?+?+??+??+??+?+??+?=L平均码长827.04309.34==L %1.98827.0811.0X)（H 43===L η可见，随着信源扩展长度的增加，平均码长逐渐逼近熵，编码效率也逐渐提⾼。

信息论无失真信源编码

信息论无失真信源编码
含义：无论码由多少个码字组成，总是能 够正确译码，不存在二义性。
即时码
ABCD 1 10 100 1000
ABCD 1 01 001 0001
10110 010 →BACB
10110 0 01→ABAD
无需知道下一个码字的码符号，即可译码， 这样的唯一可译码成为即时码。
命题5.2.1 一个唯一可译码成为即时码的充 要条件是其中任何一个码字都不是其他码 字的前缀。
信源 信源编码器 纠错编码器 调制器
干扰源
信 道
信宿 信源译码器 纠错译码器 解调器
无失真信源编码：解码之后可以得到原始 信息，例如霍夫曼编码。它相对简单，是 本章的重点。
有失真信源编码：解码之后的信息与原始 信息有一定的差别，例如JPEG、MPEG
5.1 编码器
S=(s1,s2,…,sq) 编码器 C=编码，编码器的映射必须是一一对 应、可逆的。
码的分类
根据码长
固定长度码（定长码）：所有码字的长度相同。 可变长度码（变长码）：码字长短不一。
码字是否相同
非奇异码：所有码字都不相同。 奇异码：存在相同的码字。
5.2 分组码
s1,…,si-1 si si+1,…,sq
无关
无关
5.3 定长码
编码速率：R
l
log N
r
，其中l是码字长度，r是码符号的个
数，N代表N次扩展信源。
编码效率：η=H(S)/R，其中H(S)是扩展之前信源的熵。
例如：S={A,B,C}, 等概率出现，N=2, SN={AA,…,CC}，对 SN进行二元编码，则r=2，编码方式如下，则l=4。
AA AB AC BA BB BC CA CB CC

信息论第5章 无失真信源编码

信息论第5章 无失真信源编码
若码长l1, l2, …, lq 不满足Kraft不等式à 不是惟一可译码；反之， l1, l2, …, lq 满 足Kraft不等式的码，不一定是惟一可译码。 结论：不能用克拉夫特不等式，只能根据定义 判断码C是否是惟一可译码。 判别依据：非惟一可译变长码 有限长的码 符号序列能译成两种不同的码字序列。
66
香农第一定理的物理意义
无失真信源编码的实质：对离散信源进行变换 变换后信源符号(信道的输入信源)尽可能为等概 率分布 新信源符号平均所含的信息量达到最大 à 使信道的信息传输率R达到信道容量C，实现 信源与信道理想的统计匹配。 无失真信源编码定理通常又称为无噪信道编码定 理。表述为：若信道的信息传输率R不大于信道 容量C，总能对信源的输出进行适当的编码，使 得在无噪无损信道上能无差错地以最大信息传输 率C传输信息，但要使信道的信息传输率R大于C 而无差错地传输信息则是不可能的。
62
63
64
65
定理4.8（香农信息论的主要定理之一）的结论：
要做到无失真的信源编码，编码每个信源符号平均所 需最少的r元码元数为信源的熵Hr(S) 。即Hr(S) 是无 失真信源压缩的极限值。 若编码的平均码长小于信源的熵值Hr(S) ，则惟一可 译码不存在，在译码或反变换时必然要带来失真或差 错。 通过对扩展信源进行变长编码，当N ∞时，平均码长 Hr(S) 。
4
几个术语： 信源符号：信源输入S={s1,s2,…,sq} 码符号 (码元)：X={x1,x2,…,xr} 码字Wi： 由xj (j=1,2,…,r)组成的长度为 li 的序列，Wi与si一一对应。 码字长度 (码长)： Wi的长度li 码 (码书)：码字Wi的集合 C={W1,W2,…,Wq} 编码器：将信源符号si变换成Wi的设备

第5章 无失真信源编码定理优秀课件

第5章 无失真信源编码定理优秀课件
现的概率为0，此信源只有4个字符，可得码长 l ' 2 ，
但平均每个信源符号所需码符号为
l' 1 N
5.2 等长码
我们仍以英文电报为例，在考虑了英文字母间的相关性 之后，我们对信源作N次扩展，在扩展后形成的信源（也 就是句子）中，有些句子是有意义的，而有些句子是没有 意义的，我们可以只对有意义的句子编码，而对那些没有 意义的句子不进行编码，这样就可以缩短每个信源符号所 需的码长。
原始信源的符号 S i 变换为相应的码字符号w i ，所以编码器
输出端的符号集为 C:{W1,W2,...,Wq}
S{S1,S2,...,Sq} 编码器
C:{W 1,W2,...,Wq}
X{x1,x2,...,xr}
w
i 称为码字，L
i 为码字w
i
的码元个数，称为码字w
的码字
i
长度，简称码长。
5.1 编码器
5.2 等长码
若不考虑符号间的依赖关系，可得码长l＝2
若考虑符号间的依赖关系，则对此信源作二次扩展
S P 2 (s2) s P 1s (2 s1s2)
s2s1 P (s2s1)
s3s4 P (s3s4)
s4s3 P (s4s3)
P(sisj ) 1
ij
可见，由于符号间依赖关系的存在，扩展后许多符号出
q N r l ， 两边取对数表示平均每个信源符号所需的码符号个数。
5.2 等长码
例：对英文电报得32个符号进行二元编码，根据上述关系：
l log 32 5 log 2
我们继续讨论上面得例子，我们已经知道英文的极限 熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带 1.4bit的信息量，实际上，5个二元符号最多可以携带5bit 信息量。我们可以做到让平均码长缩短，提高信息传输率
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

R log M n
19
4
“码长”与“唯一可译码/即时码是否存在”之间关系
Kraft 和 McMillan不等式 q
r li 1
i 1
5
3 定长编码
唯一可译定长码的存在条件
码字需要满足的条件
r、l、q需要满足的关系
定长编码定理
ε典型序列集的性质（渐近等分割性）
这类序列出现的概率趋于1 每个典型序列接近等概分布2-NH(S) 序列数目占信源序列的比值很小
要求：平均码长必须相等

方差计算公式、方差的含义
2

q

pi
li

L
2
i 1
8
作业讲解 - 8
定长编码定理的应用
如何定义待编码的序列个数？
长度100的序列中含有3个或小于3个‘1’的序列
如何确定译码错误？
未参与编码的序列的出现概率
9
补充作业 （10分）有下列三种码字长度： 码长 l1 l2 l3 l4 l5
C1 2 1 2 4 1 C2 2 2 2 3 1 C3 1 4 6 1 1 1. 设编码符号集为X＝{0, 1, 2}，上表中哪种
码长可用来构造出唯一可译码？ 2. 对每种可用的码长，构造出一个即时码。
10
作业讲解 – 3.5
1. “消息的符号熵”就是“信源熵”
2. “平均码长”和“二进制码的熵”
4. 若每秒可以传输100个码元，则上述三种情
况对于的编码后的码元个数与传输时间如
下所示
300 3s

17
相关重要公式
返回
q
平均码长
:
L


psi
l
码符号
i
/
信源符号
i 1
编码后的信息传输率: R HX HS比特/码符号
L
编码效率 : R H S / L Hr S H S
编码器
代码组C / 码C
C W1,W2 ,,Wq
码符号集
X :{x1, x2 ,..., xr}
码元 / 码符号
r元码
码字
平均码长
Wi xi1 xi2 xili
ቤተ መጻሕፍቲ ባይዱ码长
L p si li 定长码、变长码；奇异码、非奇异码
i
4
2 分组码
分组码：将信源符号集中的每个信源符号映射成一个 固定的码字 。
S
PS



A 0.4
B 0.2
C 0.2
D 0.1
E 0.06
F 0.02
G 0.02
3. 考虑像素间的依赖关系后，根据平均码长界定定 理和香农第一定理可知：平均码长会进一步降低
另：从信源的剩余度亦可分析还存在压缩空间
信源 符号
AB
AC
AD
EC
FC
GC
概率
码字
码长
16
作业讲解 – 补充（续）
编码过程 树根在上面； 每个节点都要圈起来，圈内
标明对应的信源符号或概率值。 编码结果要给出 所得码字一定是即时码
5.3、最佳二元和三元码
Huffman码 – 最佳码、紧致码 多元Huffman编码的注意事项！
12
2
作业讲解 – 6、12
5.6、给定信源符号集
1. 信源熵、信息传输率
实际熵
实际编码，每个信源
7
符号需要的码元数
作业讲解 – 1、15
5.1、对给定信源的六种编码结果
唯一可译码、即时码如何判断
必须有过程！即时码是唯一可译码的子集！
平均码长的求解
5.15、对给定信源构造两种不同的即时码
如何构造即时码 – 树图法
只能选择叶子节点作为码字 – 杜绝前缀！
H(S) LN H(S) 1 log r N log r N
编码算法
lim LN N N
Hr(S)
Huffman - 二元/多元、Fano、香农编码
编码过程、生成码字、编码效率
H S / L Hr S H S
log r
L L *log r
信息传输率的小结
2. Huffman编码及编码效率
5.12、对Huffman编码方法的练习巩固
1. 信源熵和信源剩余度 – 第三章内容 2. 单符号信源的紧致码及平均码长 3. 对N次扩展信源生成紧致码，当N=2、3、
无穷时对应的平均码长（单符号）？ 4. N=1, 2, 3时对应的编码效率和码剩余度
l H(S)
l H (S)－2
N log r
N log r
6
1
4 变长编码方法 – 匹配编码
基本概念
最佳码/紧致码、信息传输率、编码效率、码剩余度
重要定理
平均码长界定定理
H(S) L H(S) 1
log r
log r
变长无失真信源编码定理 – 香农第一定理
log r log r
L L *log r
码剩余度 : 1
18
3
各章涉及到的“信息传输率” 返回
第四章：信道的信息传输率
R I X ;Y Rt C
第五章：信源编码后的信息传输率
定长编码
R l log r N
变长编码 R H S
L
第六章：信道编码后的信息传输率
第五章 无失真信源编码
复习、作业讲解
1.1、概述 – 编码器概论
信源编码 – 有效地表示
使信源适合于信道的传输，用信道能传输 的符号来代表信源发出的消息。
在不失真或允许一定失真的条件下，用尽 可能少的符号来传递信源消息。
信源编码目的 – 提高通信有效性
通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平
均比特数。
2
1.1、概述 – 信源编码器模型
信源编码：将信源符号序列按一定的数 学规律映射成码符号序列的过程。
S s1 , s2 , , sq
X {x1, x2,, xr}
S
信源
X
X’
S’
编码器
信道
译码器
信宿
信源编码器模型
3
1.2、概述 – 基本术语
信源符号集
S s1, s2,, sq
随着参与编码的消息个数的增加 （N=2，3，……），编码输出的‘0’和‘1’ 趋近等概出现；编码后的信息传输率也 增大了，编码效率……
对于常见的对称信道，等概出现时，信 道实际传输的信息量可达到信道容量！
15
作业讲解 – 补充
1. 二进制等长编码，则 q rl l 3
2. 霍夫曼编码：信源的概率空间如下

1.6218 1.6875

0.9611
bit / 二元符号
编码后发出i‘0’、‘1’码元的无条件概率
p0

i
psi
* si 对应码字含有'0' 码元的个数

9 16

3 16

3 16

5
L2
27
149
16
作业讲解 – 5.11的说明
可以定义新信源，也可以看作原信源的 扩展信源。区别：符号的写法不同。
3. 求0、1出现的无条件概率
p0

pu0
1
pu1 1
pu2
1/
L

1 2
p1

pu1 1
pu2

2

pu3

3/
L

1 2
或者：令N个信源符号参与编码，计算按 照该编码方法编码后所获得的0和1的个 数，即可计算对应的概率。
11
作业讲解 – Huffman编码 树图法表示Huffman编码过程，要求：
唯一可译码：任意一串有限长的码符号序列只能被唯一地译
为对应的信源符号序列，则此码为唯一可译码。没有二义性
充要条件：编码的任意次扩展均为非奇异码 如何判别：
即时码：唯一可译码接收到一个完整码字后，无需参 考后续的码符号就能立即译码。
如何判别：唯一可译码 + 无前缀；单独无前缀亦可 如何构造：树图法
13
作业讲解 – 7、11
5.7、香农码 － log4 = 2
各信源符号的自信息是用于确定对应码字的长 度，不需要算出一个确切的数值。
5.11、Fano和Huffman编码
“二重延长” = 二次扩展消息
编码后的平均传输率
R H S 2 L2

2* H S psi li