当前位置：文档之家 › 第3章 离散信源

第3章 离散信源

  • 格式：ppt
  • 大小：771.00 KB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

第3章_离散信源()题与答案

第3章_离散信源()题与答案

该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。

求：(1)此消息的自信息量是多少？(2)此消息中平均每符号携带的信息量是多少？解：(1)此消息总共有14个0、13个1、12个2、6个3,因此消息发出的概率是：此消息的信息量是：I二-log p =87.811 bit3.2某一无记忆信源的符号集为｛0, 1｝，已知信源的概率空间为;x 口0 1:]P(X)」J/4 3/4：(1)求信息符号的平均熵；⑵ 由100个符号构成的序列，求某一特定序列(例如有m个“0”和(100 - m个“1”)的自信息量的表达式；⑶计算⑵中序列的熵。

解：(1)丁"133、H(X)二一p(X|) log p(X|) log log 0.811 biti\_4 4 4 4 J100 -m3—,10043〔00 -ml(xj - -log p(xj - -log 10厂=41.5 1.585m bit4H(X100) =100H(X) =100 0.811 =81.1 bit其概率空间为；X L X1 = 0 X2 =1 X3 = 2 X4 = 3J P(X)J '、3/8 1/4 1/41/8离散无记忆信源⑵此消息中平均每符号携带的信息量是: I /n =87.811/45=1.951 bitz-m 100 -mg盯(4〕3.5某信源的消息符号集的概率分布和二进制代码如题表 3.2所列(1)求信息的符号熵；(2)求每个消息符号所需要的平均二进制码的个数或平均代码长度。

进而用这一结果求码序列中的一个二进制码的熵；(3)当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现0和1的无条件概率P o和P i，求相邻码间的条件概率P o/1、P l/0、P i/1、P o/o。

解：(1)「1 1 1 1 1 1 1 1 \H(X) - p(xjlogp(x) log log log log 1.75 biti(2 2448888 丿⑵- 丁1111L =E(h)=為p(x)h 1 ——2 — 3 — 3=1.75i 2 4 8 81 1H N(X) H (X) H(X) =1 bitN L设消息序列长为N，则u0、u1、u2、u3的个数分别为N/2, N/4, N /8, N/8个。

《离散信源》课件

《离散信源》课件

3
哈夫曼编码的应用和优缺点
总结哈夫曼编码的应用和优缺点，以及如何使用哈夫曼编码进行无损展方向
列举几个离散信源理论在实际中 的应用案例，包括自然语言处理、 图像压缩等领域。
介绍离散信源理论在未来的发展 趋势，包括更精确的数据表示和 处理、更灵活的编码和压缩方法 等。
详细解释如何使用算术编码 对离散信源进行编码，以及 如何使用解码器进行解码。
算术编码的应用和局限 性
总结算术编码的应用场景， 并介绍算术编码的局限性。
哈夫曼编码
1
哈夫曼编码的定义及基本思想
介绍哈夫曼编码的定义和基本思想，以及如何根据概率分布构建哈夫曼树。
2
哈夫曼树的构建
深入阐述哈夫曼树的构建方法，包括如何从构建的树中获得每个符号的二进制哈 夫曼编码。
自信息、条件熵和相对熵
离散有记忆信源的定义
介绍自信息、条件熵和相对熵的 含义和计算方法，以帮助您更好 地理解信息论的基本概念及应用。
深入阐述离散有记忆信源的定义， 让您了解其如何在实际中应用。
算术编码
算术编码的基本思想
介绍算术编码的基本思想， 包括如何将符号映射到区间 和如何解码映射中的符号。
算术编码的实现
离散无记忆信源
1
离散无记忆信源的定义
解释什么是离散无记忆信源，提供实际
香农第一定理及其含义
2
例子，让您更好地理解此概念。
深入阐述香农第一定理，让您了解信息
是否可压缩的必要条件。
3
香农第二定理及其应用
介绍香农第二定理的应用，让您更好地 压缩信息并优化编码。
离散有记忆信源
马尔可夫链的概念及应用
详细解释马尔可夫链的概念和应 用，以便更好地理解离散有记忆 信源。

第3章 离散信源

第3章 离散信源
求解N次扩展信源的熵
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
H ( X1 X 2 X N )
58
59
60
61
62
由平稳信源的平稳性和条件熵的性质可知：
1 N H N ( X ) H ( X n / X n1 ) H ( X N / X 1 , X 2 ,, X N 1 ) N n1
1
2
3
4
5
6
7
8
9
10பைடு நூலகம்
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
离散信源和连续信源的数学模型
根据随机变量的取值和统计特性进行信源分类 离散无记忆信源信源熵
离散信源的N次扩展信源
另外：
1
1 H N j (X ) H ( X 1 , X 2 ,, X N 1 , X N , X N 1 ,, X N j ) N j 1 [ H ( X 1 , X 2 ,, X N 1 , X N , X N 1 ,, X N j 1 ) N j H ( X N j / X 1 , X 2 ,, X N 1 , X N , X N 1 ,, X N j 1 )]
Sj
k m 1 S j

第3章 离散信源

第3章 离散信源

时间长度为bi，则该信源的时间熵定义为：Ht(X)=H(X)/b. 其中b为信源符号的
平均时间长度。
M
b p( xi ) bi
i 1
s / 符号
离散信源的时间熵（续）
K重符号序列离散无记忆信源的时间熵：
K K Ht (X ) H(X ) / B
bit / s 其中B Kb
为K重符号序列消息的平均时间长度。由于信源无记忆，上式也可以写成：
bit / s
由于信源有记忆，所以有：
K ( H t X ) KH ( X ) (Kb) KH ( X ) /(Kb) H ( X ) / b
bit / s
有记忆信源与无记忆信源相比，对外提供信息量的速度下降了。
离散信源的时间熵（续）
马尔可夫信源的时间熵： 若信源从状态Si转移到状态Sj，发出的符号是xij，它的时间长度设为bij，则 信源从状态Si发生转移并发出一个符号时，符号的平均长度为：
信源分类
若离散信源输出符号彼此间相互独立，而且所有符号服从同一种概率分布，则称之 为简单无记忆信源；
若输出符号间彼此相关，且每个符号只与它前面的一个符号相关，而这种相关性可 以用符号间的转移概率来描述，则称之为马尔可夫信源。
离散信源的熵
单符号离散无记忆信源熵： 若信源X含有M个符号，而且每个符号相互独立，则当信源每次发送一个 符号代表一条消息时，其信源熵可以表示为:
H(X ) 100% H ( X )max
信源符号的相关性越大，信源效率越低，要提高信源效率，要设法降 低符号之间的相关性。
信源的效率与冗余度（续）
（2）信源冗余度：
H ( X )max H ( X ) H(X ) R 1 1 100% H ( X )max H ( X )max

第三章离散信源及离散熵

第三章离散信源及离散熵

电子科技大学
H(X) = −∑p(xi )lbp(xi )
i =1
4
1 1 1 1 1 1 = − lb − lb − lb × 2 2 2 4 4 8 8
2011-3-13
1 1 1 1 1 1 = lb2 + lb4 + lb8 = + × 2 + × 3 2 4 4 2 4 4 bol = 1.75(bit / sym )
2011-3-13
1、离散平稳信源及其数学模型 对于多符号离散信源发出的符号序列 X1X2 L 如果任意两个不同时刻k …， 如果任意两个不同时刻k和l，k=1,2, …， l=1,2, …，其概率分布相同，即 …，其概率分布相同， P(Xk ) = P(Xl ) 则称该多符号离散信源为一维离散平稳 信源。 信源。
该信源的离散熵
2011-3-13
H(X1X2 ) = −∑p(ai )lbp(ai )
= −∑∑p(xi1 xi 2 )lbp(xi1 xi 2 )
i1 =1i 2 =1 n n n n
n2
电子科技大学
i =1
= −∑∑p(xi1 xi 2 )lbp(xi1 )p(xi 2 / xi1 )
i1 =1i 2 =1
电子科技大学
H(X) = −∑p(i)lbp(i)
i =1
6
1 1 bol = − lb × 6 = lb6 = 2.585(bit / sym ) 6 6
2011-3-13
例2，求某一天简单的天气气象这一信源 的离散熵。 的离散熵。 该信源的数学模型为： 解： 该信源的数学模型为：
) ) ) 雨 x1(晴 x2(阴 x3( ) x4(雪 X 1 1 1 P(X) = 1 2 4 8 8

高等教育《信息论》第3章离散信源

高等教育《信息论》第3章离散信源

X
P
x1
px1
x2
px2
xq
p
xq
(3.5)8
信源输出信息量的度量
定义 3.2.2 设信源 X 中，事件 xi 发生的概率为 pxi ，
则所含有的自信息量定义为
de f
I xi log pxi
(3.6)
定义 3.2.2 给出的自信息量的函数形式有如下性质：
① 信源中信息的量度与输出符号发生的概率有关。
000, 001, 011, 111,100,110, 010,101
5
3.1.2 信源的分类 无记忆信源
① 离散无记忆信源 信源发出的消息符号彼此是统计独立的，并且具有
相同的概率分布，其 N 维随机矢量的联合概率分布为
N
N
p X p X k aik pik
k 1
k 1
i 1, 2, , q
其中 N 可为有限正整数或可数无穷值。通常，总限定 N 是有限的，故只限于讨论“有限离散信源”。若在这随机
矢量中的每个随机变量Xk , k 1, 2, , N 都是离散的，则可 用N重离散概率空间的数学模型来描述这类信源。
X
P
a1
pa1
a2
pa2
aqN p aqN
(3.4)
其中
9
自信息量 I xi 是指某一信源发出某一消息符号 xi 所含
有的信息量，所发出的信息符号不同，它们含有的信息量
也就各不相同，故自信息量 I xi 是一个随机变量，不能用
它来作为整个信源输出信息的信息测度。为此，需要引入 平均自信息量，即信息熵来作为信源输出信息的信息测度。
定义 3.2.3 信源输出的各消息的自信息量的数学期望为 信源的平均自信息量，或称为信源的信息熵。

信息论第3章 离散信源

信息论第3章 离散信源

随机波形信源在某一固定时间t0的可能取值是连续和随 机的。对于这种信源输出的消息，可用随机过程来描述。 例：语音信号X(t)、热噪声信号n(t)、电视图像信号 X(r(t),g(t),b(t))等时间连续函数。
3.2离散无记忆信源
消息符号的自信息量
自信息量与熵
信源熵
3.3离散无记忆信源的扩展信源 离散信源 单符号离散信源 离散序列信源 离散无记忆信源 一般无记忆 平稳无记忆 离散有记忆信源 平稳序列信源 齐次马尔可夫链信源
3.3.1最简单的离散信源
3.3.2 N次扩展信源
例如在电报系统中，若信源输出的是二个二元数字组成的符号序列，此 时可认为是一个新的信源，它由四个符号（00，01，10，11）组成，我 们把该信源称为二元无记忆信源的二次扩展信源。
3.3.3 N次扩展信源的熵
3.4离散平稳信源
3.4.1平稳信源
二维平稳信源的熵－条件熵
平稳信源的熵－熵的可加性
二维平稳信源的熵－例题
3.4.3极限熵
N维平稳有记忆信源的熵
条件熵随N增加而递减
矢量熵H（X）
平均符号熵与极限熵
极限熵的意义
极限熵存在定理
定理证明
极限熵的计算
小结
3.5马尔可夫信源
《和初始状态无关，不是时间起点（时齐性）》
3.1.2 信源的分类
平稳随机序列信源
总体特点：信源输出的消息由一系列符号序列所组 成，可用N维随机矢量 X＝(X1,X2,…,XN)描述，且 随机矢量X 的各维概率分布都与时间起点无关 平稳 ！！ 离散平稳信源：每个随机变量Xi (i＝1,2,…,N)都是 离散型随机变量 连续平稳信源：每个随机变量Xi (i＝1,2,…,N) 都是 取值连续的随机变量

信息论第三章离散信源无失真编码讲解

信息论第三章离散信源无失真编码讲解
2.等长码
在一组码字集合C中的所有码字cm (m = 1,2, …,M)，其码 长都相同，则称这组码C为等长码。
3.变长码
若码字集合C中的所有码字cm (m = 1,2, …,M)，其码长不 都相同，称码C为变长码。
4.奇异码
对奇异码来说，从信源消息到码 字的影射不是一一对应的。奇异码 不具备惟一可译性。
变长码分为即时码和延长码，为保证即时译码，要求变长 惟一可译码采用即时码。
对于变长码，要求整个码集的平均码长力求最小，此 时编码效率最高。
对于给定信源，使平均码长达到最小的编码方法，称 为最佳编码，得到的码集称为最佳码。
3.3.2 克拉夫特不等式
定理3.2
D进制码字集合C ={c1, c2,…, cM }，码集中
码C中每个码字cm( m = 1, 2, …，M)其码长的概率加权平均值为
M
n
nm p(c m )
(3-1)
m 1
式中nm是码字cm所对应的码字的长度，p ( cm )是码字cm出现的 概率。
对于等长码，由于码集C中的每个码字的码长都相同，平
均码长就等于每个码字的码长
n nm p(c m ) n p(c m ) n
信源编码包括两个功能： （1） 将信源符号变换成适合信道传输的符号； （2） 压缩信源冗余度，提高传输效率。
一般来说，信源编码可归纳为如图3-1所示的模型。
消息
信源
ui = ui1 ui2 … uiL
信源编码器
码字ci = ci1 ci2 … cin
信源符号 {a1,a2, …, aK}
图3-1
信道符号（码符号）{b1, b2, …, bD} 信源编码器模型
{a1, a2, …, aK}为信源符号集，序列中每一个符号uml都 取自信源符号集。

第三章离散信源

第三章离散信源

p(xi )
? 熵函数的自变量是X,表示信源整体，实质上是无
记忆信源平均不确定度的度量。试验后平均信息
量为熵
不确定性＝携载的信息
? 单位：以2为底，比特/符号
? 为什么要用熵这个词与热熵的区别？
例3.2.1二元熵函数是对0－1分布的随机变量所求的熵：
X
0
1
＝
P（x）
p
1-p
则： H(X) = -plogp-(1-p)log(1-p)=H(p)
? ?X
??P( X
? )??
?
? x1,
? ?
p(
x1
),
x2,? , p(x2 ),?
xi ,? , , p(xi
),?
,
p(
xn ? xn )??
,
n i?1
p(xi )
?
1
则信源X的N次扩展信源用 X N来表示,该新信源有 nN个元素(消息序列)
取值于同一集合
，且分量之间
统计{ 独x1 ,立x 2，, ? 则, x由n }随机矢量 X 组成的新信源称为
离散无记忆信源 X的N次扩展信源。
离散无记忆信源 X的N次扩展信源 (或称序列信 源)的熵就是离散信源 X的熵的N倍。
H ( X N ) ? NH ( X )
理解
若单符号离散信源的数 学模型为 :
qN
qN q
? P(? i ) ? ?? P(aik ) ? 1
i?1
i? 1 ik ? 1
有记忆信源：输出的随机序列 X中各随机变量 之间有依赖关系，但记忆长度有限。 m阶马尔可夫信源：信源每次发出的符号只与 前m个符号有关，与更前面的符号无关。
P(xi |? xi?2xi?1xi?1xi?2xi?3 ? xi?m ? xi?1)

离散信源

离散信源

32
初始 状态 状态 序列
00 02 10 30 00 02 22 20
10 01 11 12 23 31 30 03 33 32 21 13
状态分布
P(00)= 1 p( 其他) 0 P(02/22/20) =1/3 p( 其他)= 0 P(10/01/11/12/ 23/31) =1/6 p( 其他)= 0
35


定理3-3 设P为马尔可夫信源的一步状态转 移矩阵，该信源为平稳马尔可夫信源的充 要条件是存在一个正整数N，使矩阵PN中所 有的元素大于0。 例3-13
36

2.平稳马尔可夫信源的熵 平稳马尔可夫信源中nm个状态出现的概率能够 逐渐稳定下来，不再发生变化。设达到稳定发布 后，各个状态的概率为p（S1） ， p（S2） ，p（S nm ），那平稳马尔可夫信源的熵是－∑ p（Si）log p（Si）吗？当然不是。 因为信源的熵指信源符号带有的信息量的平均 值。并且它和离散无记忆信源的信源熵定义也是 有区别的，因为信源符号出现的概率与已经出现 的符号有关。
24

3.4.2有限状态马尔可夫链 马尔可夫链并不是信源，它体现的是一种 状态和状态之间的一环扣一环的性质，因 此称为链。 定义3-6 一个状态序列：s1,s2,…sl,…,若满足 以下条件 1.有限性 J<∞ 2.马氏性p(sl/sl-1sl-2…s1)=p(sl/sk) 则称此随机序列为有限状态马尔可夫链。
26


描述马尔可夫链的数学工具是状态转移矩 阵和状态转移图。 已知系统当前处于状态 sk ，则系统将要达 到的状态sl的概率为pkl=p(sl/sk),由于所有可 能的状态有J个，因此共有J*J个这样的概率 组成一个矩阵

第三章 离散信源

第三章 离散信源

2.1 离散无记忆信源
z 离散单符号信源：输出离散取值的单个符号
离散单符号信源是最简单、最基本的信源，是组 成实际信源的基本单元。
z 离散单符号信源X的概率空间：
⎡ ⎢ ⎣
X P( X
⎤ )⎥⎦
=
⎡ ⎢ ⎣
x1 p( x1 )
x2 L p(x2 ) L
xq ⎤ p(xq )⎥⎦
p(xi ) ≥ 0
q
3.1 预备知识
定义1：对于离散随机变量序列 X1X 2 L X n L，若任意 两个不同时刻i和j(大于1的任意整数)信源发出消息的 概率分布完全相同，即对于任意的 N = 0,1, 2,L，Xi Xi+1L Xi+N 和 X j X j+1L X j+N 具有相同的概率分布。也就是
P(X i ) = P(X j ) P( X i X i+1) = P( X j X j+1) P( Xi Xi+1 L Xi+N ) = P( X j X j+1 L X j+N )
离散
取值 离散 连续
信源种类
举例
消息的数学描述
离散信源 （数字信源 ）
连续信源
文字、数 据、数字 化图像
离散随机变量序列 连续随机变量序列
连续 连续
连续 离散
波形信源 （模拟信源 ）
语音、音 乐、图形 、图像
不常见
随机过程
1.1 信源的分类
z 根据信源发出的消息序列之间是否有统计依赖 关系，信源可分为有记忆信源/无记忆信源。
解： （1） ¾ 离散单符号信源熵
3
∑ H ( X ) = − p ( x i ) lo g 2 p ( x i ) = 1 .5 b it i =1

2014.信息论.第3章离散信源

2014.信息论.第3章离散信源

设信源输出符号集合，每次信源输
9
是⼀一个离散⽆无记忆信源，其概率空间为
其中
信源X的符号集合为
N次扩展信源X N符号集合为
15
的有记忆平稳信源（⼆二维平稳信源）输
23
当且仅当X 1和X 2统计独⽴立时等号成⽴立，此时信源相当于⼆二次⽆无记忆扩展；
当X 1和X 2之间相关时，联合熵⼩小于信息熵之和，即⼩小于单个消息符号X 熵的 2 倍。

由于
25
例：设某⼆二维离散信源X =的原始信源X 的信源模型为
中前后两个符号的条件概率
7/92/901/83/41/80
2/11
9/11
(1)若该信源为⼆二维⽆无记忆扩展信源，求信源的熵。

(2)若该信源为⼆二维平稳信源，如表，求信源的熵。

26
原始信源的熵为：
由条件概率确定的条件熵为：
由于符号之间的依赖性，条件熵⽐比信源熵减少了0.672bit
⼆二维离散⽆无记忆扩展信源的熵为：2H(X)=2*1.542=3.084(bit ）7/92/901/83/4
1/8
2/119/11
27
信源X=
平均每发⼀一个消息所能提供的信息量，即联合熵
则每⼀一个信源符号所提供的平均信息量
⼩小于信源X所提供的平均信息量H(X)=1.542bit，这是
由于符号之间的统计相关性所引起的。

28
维平稳信源输出序列每N个符号⼀一组；各
30
则有：
时：
随N的增加是⾮非递增的；
给定时，平均符号熵≥条件熵；
–平均符号熵随N增加是⾮非递增的；
34
解：
35
1,2,......,J 某时刻随机
……
43
44。

第3章_离散信源2(教育研究)

第3章_离散信源2(教育研究)
3.1.2 自然语信源
➢ 但无论是符号概率还是符号序列的联合概率都 具有先验概率的性质，只能描述静态的情形， 不能描述动态的过程。
➢ 条件概率描述了符号间的记忆特性，但它同时 给出了符号间的转移特性，故也称之为转移概 率。
✓ 以用第一个字母为T来构成3个字母的英文单词为例，第二个字母 为H的概率可以用条件概率 P(H|T)来表示，第三个字母为E的概率 可以用条件概率P(E|TH)来表示，其他各种可能的组合也都可用其 条件概率来表示。
可能低的数据速率来描述信源输出的消息。 ➢ 怎样的信源编码才是好的或者说是有效的? ➢ 信源参数测量 ➢ 离散信源的数学模型及其信息的度量
东南大学移动通信国家重点实验室
9
信息论与编码课件
3.1 离散信源的分类及其描述
3.1.2 自然语信源
➢ 可以简单地将自然语信源定义为以人类的自然语 言作为输出消息的信源。
20
信息论与编码课件
3.1 离散信源的分类及其描述
3.1.3 马尔可夫过程和马尔可夫链
➢ 定义3.4 设随机过程X(t)在时间域T={t1，t2，…，tn}的n 个时刻上的状态xk (k =1，2，…，n)都是离散型的随机 变量，并且xk有M个可能的取值s1，s2，…，sM，这M 个取值构成一个状态空间S，即S={s1，s2，…，sM}， 在n个时刻上的n个状态构成一个随机序列(x1，x2，…， xk－1，xk，…，xn－1，xn)，对此随机序列，若
统计的工作必然一直是有意义的。
➢与英文类似，汉字同样必须考虑其关联 性。
东南大学移动通信国家重点实验室
14
信息论与编码课件
3.1 离散信源的分类及其描述
3.1.2 自然语信源
➢ 可以用符号的联合概率或条件概率来描述自然语信源 的关联性。

第三章 离散信源(11)

第三章 离散信源(11)

第二节
1.概念 1.概念
离散无记忆信源及其扩展信源
一.离散无记忆信源
信源先后发出的一个个消息符号彼此独立。
2.数学模型 2.数学模型
, 信源输出随机变量X 信源输出随机变量X，可能的取值 xi ,i =1 2,..., q
[X
x2 ... xq x1 P] = p(x1) p(x2) ... p(xq )
第三章 离散信源及其信息测度
本章需要掌握的内容： 本章需要掌握的内容：
信源的分类 离散平稳无记忆信源及扩展信源的特点和信息√ 离散平稳无记忆信源及扩展信源的特点和信息√ 离散平稳有记忆信源的特点和信息 马尔可夫信源的特点和信息√ 马尔可夫信源的特点和信息√ 信源的相关性和剩余度√ 信源的相关性和剩余度√
三.信源分类 1.按信源发出的消息在时间上的分布划分： 1.按信源发出的消息在时间上的分布划分： 按信源发出的消息在时间上的分布划分
离散信源 连续信源 2.按信源发出的前后消息是否有关划分： 按信源发出的前后消息是否有关划分 2.按信源发出的前后消息是否有关划分： 无记忆信源 有记忆信源 有记忆平稳信源 有限长记忆信源(马尔可夫信源） 有限长记忆信源(马尔可夫信源）
依次推出N 依次推出N次扩展信源 X
N
N
X = X1X2...XN
X N的 学 型 ： 数 模 为
[X
N
α2 ... α2N α1 P = p(α1) p(α2) ... p(α2N )
]
其中α i = α i1α i 2 ...α iN , α ik ∈ A = (0,1) p(α i ) = p(α i1 ) p(α i 2 )...p(α iN ) = ∏ p(α iK )

第3章离散信源习题与答案

第3章离散信源习题与答案

3.1 设有一离散无记忆信源，其概率空间为⎭⎬⎫⎩⎨⎧=====⎥⎦⎤⎢⎣⎡8/14/1324/18/310)(4321x x x x X P X 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。

求：(1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？解： (1)此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是：62514814183⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=p此消息的信息量是：bit p I 811.87log =-=(2)此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/==3.2 某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡4/34/110)(X P X(1) 求信息符号的平均熵；(2) 由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100 - m ）个“1”）的自信息量的表达式； (3) 计算(2)中序列的熵。

解： (1)bit x p x p X H ii i 811.043log 4341log 41)(log )()(=⎪⎭⎫ ⎝⎛+-=-=∑(2)bit m x p x I x p mi i m mm i 585.15.4143log)(log )(434341)(100100100100100+=-=-==⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=---(3)bit X H X H 1.81811.0100)(100)(100=⨯==3.5 某信源的消息符号集的概率分布和二进制代码如题表3.2所列。

题表 3.2(1) (2) 求每个消息符号所需要的平均二进制码的个数或平均代码长度。

进而用这一结果求码序列中的一个二进制码的熵；(3) 当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ，求相邻码间的条件概率1/0p 、0/1p 、1/1p 、0/0p 。

信息论基础第3章

信息论基础第3章


则该信源称为离散平稳信源。 对于平稳信源来说，其条件概率也与时间起点 无关。
12
3.3 离散平稳信源

(m+1)维离散平稳信源

如果离散平稳信源某时刻发出什么符号只与 前面发出的m个符号有关联，而与更早些时 刻发出的符号无关联，则该信源称为(m+1) 维离散平稳信源。
P (x i +m | x 1 x i +m-1 ) = P (x i +m | x i x i +m-1 )
信息论基础
第3章 离散信源和熵
通信与信息工程学院 雷维嘉
本章内容

3.1 3.2 3.3 3.4 3.5
离散信源的分类 离散信源的N次扩展信源 离散平稳信源 马尔可夫信源 信源的相关性和剩余度
2
3.1 离散信源的分类


按照离散信源输出的是一个消息符号还是消息 符号序列，可分为单符号离散信源和多符号离 散信源。 按输出符号之间依赖关系分类，多符号离散信 源可分为无记忆信源和有记忆信源。 按照信源输出的符号序列的统计特性是否随时 间变化，多符号离散信源可分为平稳信源和非 平稳信源。
P (x 1 = 1) = 1/ 2, P (x 1 = 2) = 1/ 4, P (x 1 = 3) = 1/ 4
信源输出符号只与前一个符号有关，其条件概率 P (xl +1 | xl ) (l = 1,2, )具有时间推移不变性，如下表 所示。试问该信源是否为二维离散平稳信源？
xl xl+1 1 2 3
3.2 离散信源的N次扩展信源
6

N次扩展信源的数学模型

设单符号离散信源的数学模型为
é X ù é a ù a a 1 2 q ê ú=ê ú êP (x )ú êP (a ) P (a ) P (a )ú 1 2 q ú êë úû êë û

第三章 离散信源

第三章 离散信源
第三章 离散信源
Wuhan University
3.1 信源及其分类 3.2 离散无记忆信源的等长编码
1
信源的描述及分类
Wuhan University
信源的统计特性 信源是信息的来源,是产生消息(符号)或消 息序列的来源。 由于消息的不确定性，因此，信源是产生随 机变量、随机序列和随机过程的源。 客观信源的基本特性是具有随机不确定性。
Wuhan University
二进制无记忆信源的N次扩展：把每
N个二进制数字组成一组，则信源等 效成一个具有2N个符号的新信源，把 它称为单符号二进制无记忆信源的N 次扩展信源。
7
单符号信源的扩展
Wuhan University
例1：电报系统中，可以认为每二个二进制数
字组成一组。这样信源输出的是由二个二进 制数字组成的一组组符号。这时可以将它们 等效看成一个新的信源，它由四个符号00， 01，10，11组成，把该信源称为二进制无记 忆信源的二次扩展。
≥LlogK 没有考虑信源统计特性，认为每个 信源符号独立等概。 考虑信源统计特性时，无错编码的 条件： NlogD ≥LH(U) R≥H(U)
统计平均，仅当L 为无限时
22
离散无记忆信源的等长编码
Wuhan University
R ≥H(U) 在无错编码的前提下，编码的最低代价 当R≥logK时，能够实现无错编码。 当R<H(U)时，无论怎样编码都是有错 编码。 当logK>R>H(U)时，可以适当地编码 和译码使译码错误的概率pe任意小。 这就是所谓“渐进无错编码”。
K k 1 k
15
离散无记忆信源的等长编码
Wuhan University

第3章_离散信源(1)题与答案

第3章_离散信源(1)题与答案
解:
3、23 设信源产生A, B, C三种符号,,,,,,,。试计算冗余度。
解:
3、26 一阶马尔可夫信源得状态图如下图所示。信源X得符号集为{0, 1, 2}。
(1) 求平稳后信源得概率分布;
(2) 求信源得熵H∞。
解:
(1)
(2)
(3) 试计算H(X4)并写出X4信源中可能有得所有符号。
解:
(1)
这个信源就是平稳无记忆信源。因为有这些词语:“它在任意时间而且不论以前发生过什么符号……”
(2)
(3)
3、11 有一马尔可夫信源,已知转移概率为,,,。试画出状态转移图,并求出信源熵。
解:
3、21黑白传真机得信息元只有黑色与白色两种X={黑,白},一般气象图上黑色出现得概率为P(黑)= 0、3,白色出现得概率为P(白)= 0、7,黑白消息前后没有关联,其转白/黑)= 0、2,P(黑/黑)= 0、8。求该一阶马尔可夫信源得不确定性H(X/X),并画出该信源得状态转移图。
此消息得信息量就是:
(2)
此消息中平均每符号携带得信息量就是:
3、2 某一无记忆信源得符号集为{0, 1},已知信源得概率空间为
(1) 求信息符号得平均熵;
(2) 由100个符号构成得序列,求某一特定序列(例如有m个“0”与(100m)个“1”)得自信息量得表达式;
(3) 计算(2)中序列得熵。
解:
3、1 设有一离散无记忆信源,其概率空间为
该信源发出得信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。求:
(1) 此消息得自信息量就是多少？
(2) 此消息中平均每符号携带得信息量就是多少？
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
信息量单位
自信息的例子
【 例 ， 增 】 一 信 源 有 4 种 输 出 符 号 码 ， xi(i=0,1,2,3) ， 且 p(xi)=1/4。设信源向信宿发出x3，但由于传输中的干扰，接 收者收到x3后，认为其可信度为0.9。于是信源再次向信宿发 送该符号x3，信宿无误收到。问: (1) 信源在两次发送中发出的信息量各是多少? (2) 信宿在两次接收中得到的信息量又各是多少?
• 得到信源的样本空间为符号集
X=｛x1, x2, x3, x4, x5, x6｝。 各消息都是等概率出现的
X的概率分布就是各消息出现的先验概率：
p(x1)=p(x2)=p(x3)=p(x4)=p(x5)=p(x6)=1/6, 信源的数学模型为:
X P( X
)
1x/16
x2 1/ 6
x3 1/ 6
按照信源符号彼此之间的依存关系，离散信源又可分为： 离散无记忆信源和离散有记忆信源 • 离散无记忆信源：信源发出的一个个消息符号是相互 独立的。 - 前面已经出现的信源符号对后面将要出现哪个信源 符号没有影响； - 即：各符号序列中的各个符号之间是没有统计关联 的关系； - 各个符号的出现概率是它自身的先验概率。 - 离散无记忆信源包含发出单符号的无记忆离散信源 和发出符号序列的无记忆离散信源。
信源熵的例子1
【例3-5，P31】计算机中常见的信源是二元信源，二元 信源可以描述为
X 0 1 0 1
P
p
q
p
1 p
则二元信源的熵为
H(X ) p log p (1 p)log(1 p) • 如例3-3，p=1/2 H(X)=1比特/符号
说明
➢ 二元信源的信息熵H(X)是 概率p的函数，通常用H(p) 表示。
们、要、的、把、看、… 我
碗、机、水、书、框、…
• p(们)=0.01，p(碗)=0.01 • p(们|我)=0.05， p(碗|我)=0.001
有限记忆信源和无限记忆信源
离散有记忆信源分为 • 有限记忆信源 • 无限记忆信源
有限记忆信源 • 当记忆长度为m时称这种记忆信源为m阶马尔可夫信源， 即信源每次发出的符号与前m个符号有关，与更前面的 符号无关。 • 假设m阶马尔可夫信源输出的随机序列为x1 x2…xi1xi …xN。在这序列中某i时刻的随机变量xi取什么符号 只与前m个随机变量xi-1 xi-2… xi-m取什么符号有关，与 其更前面的随机变量以及后面的随机变量取什么符号 都无关。
1
1
2
说明
➢ 信源的输出序列有可能是
111011111011001110110011101110011010110010110011011100010011
（23个0，37个1） ➢ 信源的输出序列也可能是
110101100110010001111111000010001010011000011100001101001110
• 因此，二次扩展信源为
X2 P
a1 p(a1)
a2 p(a2 )
a3 p(a3 )
a4 p(a4 )
00 01
10
11
p
2
p(1 p)
p(1 p)
(1
p)2
2、三次扩展信源
• 设离散无记忆二元信源
X P
0
p
1 1 p
• 三次扩展信源（N=3），包含8个长度为3的序列 {000,001,…,110,111}，分别记为a1，a2，…，a8，每个序 列出现的概率为序列中三个符号出现的概率的乘积。
信源
消息
编码器
信号
信道 干扰
干扰器
译码器
信宿
消息
在实际通信中最常见的信源有话音、文字、图像、数据等。
离散信源的数学模型
离散信源的数学模型 • 信源可以输出多个符号，每个符号以一定的概率出现。 • 因此可以用概率来描述信源。
X P
x1 p( x1 )
x2 p(x2 )
xn p(xn )
信源熵的例子2
【例3-6，P31】有一个三元信源
X P
x1 1 2
x2 1
4
x3 1 4
则信源的熵为
H (X )
3
i 1
p(xi ) log p(xi )
1 log 2
1 2
2 1 log 4
1 4
1.5
比特/符号
3.3.2 离散无记忆信源的扩展信源及其熵
可以一个符号一个符号的来研究信源，但有时这样不能满 足实际应用的需要。 • 汉语：更多地考察的是句子，而不是汉字。 • 英语：更多地考察的是单词，而不是字母。 • 图像：更多地考察的是整幅图像，而不是单个像素。 所以，有必要研究N次扩展信源。
X P
x1 p(
x1
)
x2 p( x2 )
L L
xn p(xn )
其中
n
p(xi ) 1
i 1
p(xi ) 0
则称X为离散无记忆信源。
离散无记忆信源的例子
【例，增】掷一颗质地均匀的骰子，研究其点数，每次实验 结果必然是1，2…6点中的某一个面朝上。信源输出的消息 是“一点”，“两点”，…“六点等6个不同的消息。每次 实验只能出现一种消息，出现哪一种消息是随机的，但必 是六6种情况中的一种。用xi,(i=1,…,6)来表示这些消息，则：
（31个0，29个1）
信源的例子2
【例3-2，P29】老师在讲课时不断地发出一个一个的汉 字，老师就是一个信源。该信源发出的符号包括所有的 汉字，每个汉字按照一定的概率出现，所有的已经发出 的汉字构成了信源序列。
3.2 信源的分类
信源的分类 3.2.1 无记忆信源 3.2.2 有记忆信源
信源的分类
离散有记忆信源
• 离散有记忆信源：信源先后发出的消息符号之间彼此 依存、互不独立的。 - 这类信源的数学表示比较困难； - 现实存在的信源多是离散有记忆信源； - 离散有记忆信源又可分为：有限记忆信源（马尔可 夫信源）和无限记忆信源。
信源分类小结
信源
离散信源 连续信源
单符号的无记忆离散信源 离散无记忆信源 符号序列的无记忆离散信源
3.3 离散无记忆信源
3.3.1 离散无记忆信源及其熵 3.3.2 离散无记忆信源的扩展信源及其熵
3.3.1 离散无记忆信源及其熵
【定义3-1】信源X符号集为(x1, x2 , …, xn)，n为信源发出的 消息符号的个数，每个符号发生的概率为p(xi), i=1,2,…,n， 这些消息符号彼此互不相关，且有
• 因此，三次扩展信源为
X3 P
a1 p(a1
)
a2 p(a2 )
000 001
p3
p2 (1 p)
a8 p(a8 )
11ቤተ መጻሕፍቲ ባይዱ
(1
p)3
3、N次扩展信源及其熵
根据前面例子，先归纳出N次扩展信源的数学模型，然 后再给出N次扩展信源熵的计算方法。
数学模型 • 离散无记忆N次扩展信源（也称为：离散无记忆序列 信源）输出消息由N个符号序列组成，前后符号的出 现是彼此独立的。 • 若基本离散无记忆信源的数学模型用[X，P(X)]概率空 间来描述，则离散无记忆信源X的N次扩展信源的数学 模型如下：
说明
➢ X是信源能取的符号的集合；xi是信源符号（不再称为 事件）；
➢ pi(即p(xi))是信源符号出现的概率。
信源的例子1
【例3-1，P29】在串口（图2-2）通信中，串口就是一个 信源。该信源只发出两个符号“0”和“1”，两个符号出 现的概率相等，该信源的数学模型是
X P
0 1 2
从信源发出的消息在时间上和幅度上的分布来考虑分类， 可将其分为离散信源和连续信源。
• 离散信源：指发出在时间和幅度上都是离散 分布的离散消息的信源。 如：文字、数字、数据、字母等。
• 连续信源：指发出在时间和幅度上都是连续分布 的连续消息（模拟消息）的信源。 如：语言、图像、视频等。
离散无记忆信源
第3章 离散信源
3.1 离散信源的数学模型 3.2 信源的分类 3.3 离散无记忆信源 3.4 马尔可夫信源（有限记忆信源） 3.5 离散平稳信源 3.6 信源的相关性和剩余度
本章小结
3.1 离散信源的数学模型
几点说明 • 信源是信息的来源。 • 信源发出了消息，消息载荷着信息，信息具有不确定性。 • 从数学分析上看，由于消息具有的不确定性，因此信源可 以看成是产生随机变量、随机序列（矢量）和随机过程的 源。
符号序列的有限记忆信源 离散有记忆信源
符号序列的无限记忆信源
信源的分类
3.2.1 离散无记忆信源
离散无记忆信源：信源发出的一个个消息符号是相互独立的。
如何用概率的方法定义无记忆信源？ • 已经出现的符号对将要出现的符号的概率没有影响： p(xi|x1x2…xi-1) = p(xi) • 更确切地，设X=x1x2…xM是信源发出的符号序列
【例】从一个袋子里摸球，50个红的、50个白的，每 次摸完之后放回。
则无论已经摸过的球是红的还是白的，再摸一次球 ，红白出现的概率都是1/2。
3.2.2 离散有记忆信源
离散有记忆信源：信源先后发出的消息符号之间彼此依存、 互不独立。现实存在的信源多是离散有记忆信源
有记忆信源的例子
【例3-4，P30】例3-2中，老师是一个有记忆信源。信源先后 发出的消息符号之间彼此依存、互不独立。 • 例如：
第二次无误接收，得到到的信息量为2(比特)，或I(x3/y)=0 I(x3;y)=I(x3)-I(x3/y)=2(比特)
【定义3-3】 信源X的平均自信息量（即信源熵）定义为
含义
n
n
H (X ) E(I (xi )) p(xi )I (xi ) p(xi ) log p(xi )