信息论 第三章

2006-11-61信息理论基础第8讲北京航空航天大学201教研室陈杰2006-11-62当前状态u l =(a l1, a l2, a l3, …, a lm )当前输出X l =a l1.信源状态S={S 1, S 2 ,…S J }, J =q m⎧⎪⎪⎨⎪⎪⎩()12|m q i j S S S p S S ⎡⎤⎢⎥⎢⎥⎣⎦()112|m mi i i i p a a a a + 状态转移概率p (S i |S j )由条件符号概率确定u lu l+1X l =a l新状态u l+1=(a l2, a l3, …, a lm ,a l )2.状态空间2006-11-633.极限熵当时间足够长时，遍历的m 阶马尔可夫信源可视为平稳信源()121lim |N N N H H X X X X ∞−→∞= ()112|m m H X X X X += 1m H +=()()|jj j s p S H X S =∑H (X|S j )是信源处于状态S j 时的条件熵()()()||log |jj i j i j S H X S p a S p a S =∑()()|log |ji j i j S p S S p S S =∑2006-11-64例3.7一阶马尔可夫信源的状态如例题图所示，信源X 的符号集为{0，1，2}。

（1）求平稳后的信源的概率分布；（2）求信源熵H ∞（3）求当p =0或p =1时信源的熵12pppppp2006-11-65解（1）状态转移矩阵令信源的平稳分布为则0 00 p p p p p p ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦P []012 W W W =W 0011120121W pW pW W pW pW W W W =+⎧⎪=+⎨⎪++=⎩2006-11-66整理得，平稳后信源的概率分布（2）求信源熵H ∞。

根据平稳分布01213W W W ===()()jj k j s H p S H a S ∞=∑1113[lo g lo g ]3p p p p =×+11log logp p p p=+2006-11-67（3）p =0时p =1时∞→→=+=−=0311lim [loglog]lim ()log 0p p H p p ppp e∞→→=+=−=0311lim [loglog]lim ()log 0P P H p p ppp e3.5.3 马尔可夫信源解释：•信源熵表示的是信源的平均不确定性。

• （1）求信源熵 • （2）求由m个“0”和（100-m）个“1”构成
的某一特定序列自信息量的表达式
• （3）计算由100个符号构成的符号序列的熵
• 3.3.2离散平稳有记忆信源 • 熵函数的链规则：
X x1，x2，，xN ,其中每个随机变量之间存在统计依赖关系。 H ( X ) H ( X1X 2 X N ) H ( X1) H ( X 2 X1) H ( X 3 X1X 2 ) H (X N X1X 2 X N1)
i
j
则称其具有遍历性，w
为平稳分布
j
• 遍历的马尔可夫信源熵率: • (1)齐次的马尔可夫信源:视作平稳的信源来处理 • 遍历的马尔可夫信源都是齐次的 • 遍历的马尔可夫信源:视作平稳的信源来处理 • (2) m阶马尔可夫信源: 只与最近的m个符号有关.
H
＝
lim
N
H
(
X
N
X1X 2 X N 1)
件不断增加，平均符号熵
及HN (条X) 件熵
• H ( X N X1X 2 X3 X N1) 均随之减少。
• 当 N 时 HN (X)=H ( X N X1X 2 X N1)
• 即为熵率，它表示信源输出的符合序列中，平均 每个符号所携带的信息熵。
• 求熵率的两种途径：
• 1.极限平均符号熵 • 2.极限条件熵
4
)
0
0.5
0
0 0.5 0
0.5 0 0.2
0.5 0
=(w 1
0.8
w2
w3
w4 )
0.2w1 0.5w 2
+0.5w3 =w2 +0.2w4 =w3
lim lim 现在令N ，则有H (X )

条件概率被称为信道的传递概率或转移概率。
一般简单的单符号离散信道的数学模型可以用概率空
间[X,p(y|x),Y]来描述。
a1
b1
X
P (b j | ai )
Y
ar
2021/6/7
bs
6
第一节 信道的数学模型及分类
表示成矩阵形式：
…
y1
y2
… x1 p(y1/x1) p(y2/x1)
[P]=
…
x2 p(y1/x2) p(y2/x2)
2021/6/7
27
第四节 信道容量及其一般计算方法
(3)无噪有损信道
x1
x2
y1
x3
x4
y2
x5
此时信道疑义度为0，而信道噪声熵不为0，从而
C=max{I(X;Y)}=max{H(Y)-H(Y/X)}=max{H(Y)}=logs
2021/6/7
28
第四节 信道容量及其一般计算方法
2、对称离散信道的信道容量
y1
y2
…
x1
p(y1/x1)
p(y2/x1)
…
[P]= x2
p(y1/x2)
p(y2/x2)
…
…
…
…
…
xn
p(y1/xn)
p(y2/xn)
…
ym p(ym/x1) p(ym/x2)
… p(ym/xn)
2021/6/7
10
第一节 信道的数学模型及分类
为了表述简便，可以写成 P(bj /ai)pij
因为H(X),表示传输前信源的不确定性，而H(X/Y)表示
收到一个符号后，对信源尚存的不确定性，所以二者之
差信道传递的信息量。

• 信道编码：是以提高信息传输的可靠性为目的的编 码。通常通过增加信源的冗余度来实现。采用的一 般方法是增大码率/带宽。与信源编码正好相反。
• 信源编码理论是信息论的一个重要分支，其理论基础 是信源编码的两个定理。 –无失真信源编码定理：是离散信源/数字信号编码 的基础； –限失真信源编码定理：是连续信源/模拟信号编码 的基础。 • 信源编码的分类：离散信源编码、连续信源编码和相 关信源编码三类 –离散信源编码：独立信源编码，可做到无失真编码； –连续信源编码：独立信源编码，只能做到限失真信 源编码； –相关信源编码：非独立信源编码。
*
3.5 通用信源编码
本节将主要介绍 • LZ算法， • 改进的LZ-Welcn 算法 • Kieffer-Yang算法， • LZ算法基于符号串匹配的算法，而LZWelcn 算法是基于字典的算法，它们都是 利用信源输出符号自身的信息来进行压缩 编码。Kieffer-Yang算法（简称YK算法）则 兼顾了字符串匹配和算术码结构的优点。
0 11 00 11
0 10 00 01
1 10 100 1000
1 01 001 0001
6 、同价码: 每个码字占相同的传输时间
7.码的N 次扩展: 若码C :{W1 , W2 ,..., Wq }，B :{Bi (Wi1Wi 2 ...WiN )}，则 码B称为码C的N 次扩展码
8、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成 所对应的信源符号序列，则称此码为唯一可译码。 9、即时码（瞬时编码）：没有一个码字是其他码字的前缀 的唯一可译码称为~。 10、码分类
信源
信源编码器
等效信源 等效信宿
信道编码器
等效干扰 信道
信 道