当前位置:首页 >> 信息与通信 >>

信息论


信息论基础
东南大学计算机学院

信息 信息科学 信息论
? 信息:某人被通知或告知的内容,情报,消息. 信息作为技术术语被广泛使用是在计算机, 特别是微处理器得到广泛应用以后的事. 信息作为一个可以用严格的数学公式定义 的科学名词首先出现在统计数学中,随后又 出现在通信技术中,是一种统计意义上的信 息.统计信息是非常明确的,其适用范围比

广 义信息狭义的多.

信息 信息科学 信息论
? 信息科学:作为一个名词,最早出现在图书馆学中, 主要研究图书文献的检索.在计算机出现以后,信息 科学被赋予新的含义.但在不同国家中它的含义不 尽相同.在日本信息科学的含义和美国的计算机科 学的含义相似,主要研究科学计算的理论和方法.而 在美国信息科学原先主要指科学计算以外,如商业, 服务业,管理统计部门等所需要的,涉及大量数据但 计算比较简单的数据处理问题.20世纪80年代以来, 信息科学的含义不断扩大,不但逐渐把计算机科学 的内容统一包含在内,而且有把信息技术涉及的所 有科学理论统统包含在内的趋势.

信息 信息科学 信息论
? 信息论:是信息科学的基本理论.从历史上看 信息论的形成是两部分人共同努力的结果, 一部分是通信工程方面的学者,另一部分是 统计数学家,这两部分人虽然研究的是同一 领域的问题,但他们感兴趣的方面和侧重点 是有差异的.这种情况从信息论产生时起一 直保持到现在,今天从事信息论研究工作的 人仍然由这两部分人组成.

(1)信息论研究的对象
? 信息论研究的核心问题是信息的传输和处 理.把各种通信系统中具有共同特点的部分 抽象出来,概括成一个统一的理论模型,通常 称这个模型为通信系统的基本模型.

通信系统的理论模型
信源 消息 编码器 信号 干扰 噪声源 信道 信号+ 干扰 译码器 消息 信宿

信息论在通信领域研究的对象正是这种基本 的通信系统模型.人们通过对系统中消息形态 的变化来研究信息的传送和处理的共同规律.

信源 编码器 信道 译码器 信宿
? 信源:信源是产生消息和消息序列的源头. 消息通常是符号序列或时间函数,消息取值 服从一定的统计规律,所以信源的数学模型 可以是一个离散的随机序列或连续的随机 过程. ? 编码器:编码是消息变换成信号的措施,编 码器输出的是适合信道传输的信号,信号携 带消息,它是消息的载荷者.(信源编码的任务 是提高信息的传输效率&信道编码的任务 是提高信息传输的可靠性)

信源 编码器 信道 译码器 信宿
? 信道:通信系统中把载荷消息的信号从甲地传输 到乙地的媒介或通道.在侠义的通信系统中,信道有 明线,电缆,波导,光纤,人造卫星,无线电传播空间等, 这些都是属于传输电磁波能量的信道.在信道中引 入噪声和干扰是一种简化的表达方式.为了分析方 便起见,把在系统其他部分产生的干扰和噪声都等 效地折合成信道干扰,看成是由一个噪声源产生的, 它将作用于所传输的信号上,这样,信道输出的已是 叠加了干扰的信号,由于干扰或噪声往往具有随机 性,所以信道的特性也可以用概率空间来描述.

信源 编码器 信道 译码器 信宿
? 译码器:译码把信道输出的编码信号(已 叠加了干扰)进行逆变换.译码器也可分成 信源译码器&信道译码器. ? 信宿:信宿是消息传送的对象,即消息的接 收者.

编码与译码
消息S={S1, S2,…,Sq}

编码器
码符X={x1, x2,…,xn}

码字W={W1,W2,…,Wq}

消息S={A,B,….,Z}

码符X={0,1}
每个英文字母用五个码符(五位二进制)编码, 经过编码器,消息S={A,B,….,Z} 就可以转换成码字W={W1,W2,…,W26}

MH码表(一)尾码表(同一符号重复出现而形成的字符串长度称为游程长度)
RL长度
0 1 2

白游程码字
00110101 000111 0111

黑游程码字
0000110111 010 11

RL长度
16 17 18

白游程码字
101010 101011 0100111

黑游程码字
0000010111 0000011000 0000001000

3
4 5 6

1000
1011 1100 1110

10
011 0011 0010

19
20 21 22

0001100
0001000 0010111 0000011

00001100111
00001101000 00001101100 00000110111

7
8 9 10

1111
10011 10100 00111

00011
000101 000100 0000100

23
24 25 26

0000100
0101000 0101011 0010011

00000101000
00000010111 00000011000 000011001010

11
12 13 14

01000
001000 000011 110100

0000101
0000111 00000100 00000111

27
28 29 30

0100100
0011000 00000010 00000011

000011001011
000011001100 000011001101 000001101000

15

110101

000011000

31

00011010

000001101001

MH码表(一)尾码表
RL长度
32 33 34

白游程码字
00011011 00010010 00010011

黑游程码字
000001101010 000001101011 000011010010

RL长度
48 49 50

白游程码字
00001011 01010010 01010011

黑游程码字
000001100100 000001100101 000001010010

35
36 37 38

00010100
00010101 00010110 00010111

000011010011
000011010100 000011010101 000011010110

51
52 53 54

01010010
01010101 00100100 00100101

000001010011
000000100100 000000110111 000000111000

39
40 41 42

00101000
00101001 00101100 00101011

000011010111
000001101100 000001101101 000011011010

55
56 57 58

01011000
01011001 01011010 01011011

000000100111
000000101000 000001011000 000001011001

43
44 45 46

00101100
00101101 00000100 00000101

000011011011
000001010100 000001010101 000001010110

59
60 61 62

01001010
01001011 00110010 00110011

000000101011
000000101100 000001011010 000001100110

47

00001010

000001010111

63

00110100

000001100111

MH码表(二)组合基干表
RL长度
64 128 192

白游程码字
1101 10010 010111

黑游程码字
0000001111 000011001000 000011001001

RL长度
960 1024 1088

白游程码字
011010100 011010101 011010110

黑游程码字
0000001110011 0000001110100 0000001110101

256
320 284 448

0110111
00110110 00110111 01100100

000001011011
000000110011 000000110100 000000110101

1152
1216 1280 1344

011010111
011011000 011011001 011011010

0000001110110
0000001110111 0000001010010 0000001010011

512
576 640 704

01100101
01101000 01100111 011001100

0000001101100
0000001101101 0000001001010 0000001001011

1408
1472 1536 1600

011011011
010011000 010011001 010011010

0000001010100
0000001010101 0000001011010 0000001011011

768
832 890

011001101
011010010 011010011

0000001001100
0000001001101 0000001110010

1664
1728 EOL

011000
010011011 000000000001

0000001100100
0000001100101 000000000001

MH码表(三)供加大纸宽用的组合基干表(1792~2560,黑、白相同)

游程长度
1729 1856 1920

组合基干码码字
00000001000 00000001100 00000001101

1984
2048 2112 2176

000000010010
000000010011 000000010100 000000010101

2240
2304 2368 2432

000000010110
000000010111 000000011100 000000011101

2496
2560

000000011110
000000011111

信息传输的高效性和可靠性
? 高效性:系统的经济效果好。即用尽可能短的时 间和尽可能少的设备传送一定数量的信息。 ? 可靠性:系统的保真效果好。即要使信源发出的 消息经过信道的传输后,尽可能准确、不失真地 再现在接收端。 ? 信源编码器:通过压缩消息的平均编码长度,提 高消息传输的效率。 ? 信道编码器:通过增加码字的编码的长度,提高 码字在信道中自我纠正因干扰产生的错误能力。

以计算机为核心的大规模信息网络通信系统的理论模型

信 源

信 源 编 码 器



加 密 编 码

信 道 编 码 器

信道

信 源 编 码 器



噪声源

解 密 编 码

信 道 编 码 器

信 宿

保密性:隐蔽和保护通信系统中传送的消息。 认证性:接收者能正确判断所接收到的消息的正确 性,验证消息的完整性。即消息的不可伪造、不可 篡改性。

(2)信息论研究的目的
? 信息论研究的目的就是要找到信息传 输过程中的共同规律,以提高信息传输 的有效性,可靠性,保密性,认证性,达到 信息传输系统最优化.

有效性研究面对的模型
信 源 信 源 编 码 器



加 密 编 码

信 道 编 码 器

信道

信 源 编 码 器



噪声源

解 密 编 码

信 道 编 码 器

信 宿

可靠性研究面对的模型
信 源 信 源 编 码 器



加 密 编 码

信 道 编 码 器

信道

信 源 编 码 器



噪声源

解 密 编 码

信 道 编 码 器

信 宿

保密性、认证性研究面对的模型
信 源 信 源 编 码 器



加 密 编 码

信 道 编 码 器

信道

信 源 编 码 器



噪声源

解 密 编 码

信 道 编 码 器

信 宿

(3)信息论研究的内容 1
? 狭义信息论(经典信息论).主要研究 信息的测度,信源编码和信道编码, 以及信道容量理论.这部分理论是 信息论的基础理论,理论的创始人 是香农,所以又称为香农理论.

(3)信息论研究的内容 2
? 一般信息论.主要也是研究信息传 输和处理问题,除了香农理论以外, 还包括噪声理论,信号滤波和预测, 统计检测和估计理论,调试理论,信 息处理理论以及保密理论.后一部 分内容的主要贡献者是维纳 (N.Wiener)和柯尔莫哥洛夫 (A.Kolomogorov)等人的.

(3)信息论研究的内容 3
? 广义信息论.不仅包括上述两方面 的内容,而且包括所有与信息有关 的自然和社会领域,如模式识别,计 算机翻译,心理学,遗传学,神经生理 学,语言学,语义学甚至包括社会学 中有关信息的问题.

综上所述
? 信息论是一门应用概率论,随机过程,数理统 计和高等代数的方法来研究信息传输,提取 和处理系统中一般规律的科学; ? 它的目的是提高信息系统的可靠性,有效性, 保密性和认证性,以便达到系统的最优化; ? 它的主要内容包括香农理论,编码理论,维纳 理论,检测和估计理论,信号设计和处理理论, 调试理论,随机噪声理论和密码学理论.

随机变量
? 如果随机试验的所有可能的结果,可以用一个变量 X来表示,在一次试验中, X 取什么数值不能事先确 定,它随着试验结果的不同而变化,也就是说X 是样 本w的一个函数,即X= X(w),如果它取各个值的可 能性可以用概率描述,则称这个定义在样本空间 ? 上的单值实函数X= X(w)为随机变量。 ? 一般用大写英文字母表示随机变量X. ? 随机变量X的某个取值称为事件,一般用小写英文 字母表示x. ? p(x) 表示事件发生的概率.

随机变量的信息度量-自信息
定义:对随即变量X,事件x的自信息定义为
1 I ? x ? ? log ? ? log p ? x ? p ? x?

自信息I(x)是事件x的不确定性即事件x发生 的可能性的一种度量(测量),表示事件X=x 发生时,事件x所含有或提供的信息量。 p(x)越小,则I(x)越大,因为一事件发生的 可能性越小,则当其出现时所带来的信息 就越多。

log2 =比特 loge ? 奈特 log10 ? 哈特

自信息的性质:
? ? ? ?

1 I ? x ? ? log ? ? log p ? x ? p ? x?

性质1. 自信息I(x)是非负的。 性质2. 当p(x) = 0 时, I(x)=∞(太阳系毁灭). 性质3. 当p(x) = 1 时, I(x)=0(白天有太阳) 性质4. 当p(x) > p(y) 时, I(x) < I(y), 即I(x)是 p(x)的单调递减函数. ? 由于x是一个随即变量,因此自信息I(x)也是 一个随即变量.小概率事件所包含的不确定 性大,其信息量就大;而出现概率大 的随机事 件所包含的不确定性小,其自信息量就小.

联合自信息
定义:对随即变量X和Y,在二维联合集XY的事件 xy的联合自信息定义为
I ? xy ? ? log 1 ? ? log p ? x, y ? p ? x, y ?

其中p(x,y)为元素xy的二维联合概率,即
0 ? p ? x, y ? ? 1,

?? p ? x, y ? ? 1

性质5. 当x和y相互独立时,即p(x,y) = p(x)p(y)时
I

? xy ? ? I ? x ? ? I ? y ?

自信息函数
? 定理: 若函数I(x)满足性质1~5,则 I ? x ? ? ?C log p ? x ? 其中C为常数。

引理
引理:如果实函数f(x),对1 ? x ? ?? 满足: (1) f(x)≥0, (2) f(x)是严格单调增函数,即x<y时,f(x)<f(y), (3) f(xy)=f(x)+f(y), 则f(x)=Clogx.

条件自信息
? 若p(x|y)表示事件y发生时发生事件x的条件概率. ? 定义:事件y发生时,发生事件x的条件自信息定义 为

I ? x | y ? ? ? log p ? x | y ?

注:条件自信息也是随即变量,其值随着x和y的变化 而变化,且条件自信息也有非负性和单调递减性。 ? 由于p(x,y)=p(x)p(y|x)=p(y)p(x|y),因此联合自信 息、自信息和条件自信息之间满足以下关系:

I ? xy ? ? I ? x ? ? I ? x | y ? ? I ? y ? ? I ? y | x ?

互信息
? 定义:对随即变量x和y,X的事件x与Y的事 件y之间的互信息定义为
I ? x ; y ? ? log p ? x | y? p ? x?

互信息的单位与自信息一样,取决于对数 的底数。

互信息性质
? ? ? ? ? ? 性质1. 性质2. 性质3. 性质4. 性质5. 性质6.
当x与y独力时, I ? x; y ? ? 0 互信息可正可负。 I ? x; y ? ? I ? x ? , I ? x; y ? ? I ? y ? I ? x; y ? ? I ? x ? ? I ? x | y ? ? I ? y ? ? I ? y | x ? I ? x; y ? ? I ? x ? ? I ? y ? ? I ? xy ? I ? x; y ? ? I ? y; x ?

条件互信息
? 定义2.1.5 对随即变量X、Y和Z,在给定事 件Z的条件下,事件x与事件y之间的条件互 信息定义为 p ? x | yz ? I ? x ; y | z ? ? log p?x | z?
? 事件x与联合事件yz之间的互信息定义为
I ? x ; yz ? ? log p ? x | yz ? p ? x?

性质
? 性质
I ? x ; yz ? ? I ? x ; z ? ? I ? x ; y | z ?

性质表明:事件x与联合事件yz之间的互信息 等于事件x与事件z之间的互信息加上在给定 事件z的条件下事件x与事件y之间的互信息 。

离散随机变量的平均自信息(熵)
? 如果随机变量X的取值只有有限个或可列举的无 穷多个,则称X为离散随机变量。 ? 设X的所有可能取值为 x1 , x2 ,?, xk ,? ,称 ?xk | k ? 1,2,?? 为离散事件的集合。 ? 如果给定随机变量X每一个取值 x k的概率 p?xk ? ? P?X ? xk ?, k ? 1,2,? 则X的取值特征就可以被 完整地描述,称序列 ?p?xk ??, k ? 1,2,? 为离散随机变 量X的概率分布,记为 x2 ? xk ? ? ? X ? ? x1 ? p? x ?? ? ? p? x ? p? x ? ? p? x ? ?? ? ? ? 1 2 k ?
p?xk ? ? 0, k ? 1,2,?, ? p?xk ? ? 1
k

离散随机变量空间
? X ? ? x1 ? p? x ?? ? ? p? x ? ? ? ? 1 p ? x2 ? ? x2 ? xk ? ? p? xk ? ?? ?
k

p?xk ? ? 0, k ? 1,2,?

? p? x ? ? 1
k


? 自信息I(x)是随机变量X中事件x所含的信息 量,事件不同,它们所含的信息量也不同。 由于I(x)也是一个随机变量,为了度量整个 随机变量X的信息,通过求数学期望,引入 平均自信息(熵)。 ? 定义2.2.1随机变量I(x)的数学期望定义为离 散随机变量X的平均自信息,也称为熵,即
H ? X ? ? E?I ?x ?? ? E?? log p?x ?? ? ?? p?xk ?log p?xk ?
k

香农理论(经典信息学)数学基础
?

熵( Entropy )经典信息学的数学基础. 熵的数学定义: H ( X ) ? ? ? p( x) log 2 p( x) 以熵为尺度度量信息量的大小。
消息的概 率空间:

?

?



X1 , X2, 。。。。。。, Xn P(X1),P(X2),。。。,P(Xn)

例.设离散随机变量X的分布规律为
? X ? ? 0 1 ? ? p ? x ?? ? ? p 1 ? p ? ? ? ? ?
H(x) 1

H ?x ? ? ? p log p ? ?1 ? p ?log?1 ? p ?
0 1/2 p

1 可以证明:当 p ? 2 时,H(x)取最大值而当p=0

或p=1时, H(x)=0.H(x)是p的函数,称为二元熵 函数。

熵:(平均自信息量):Entropy
H ( X ) ? ?? p(i) log 2 p(i)
i ?1 32

1 1 ? ?? log 2 ? log 2 32 ? 5bits 32 i ?1 32

32

一个随机变量均匀分布在32个输出上, 该随机变量的平均信息量为5bit,即5bit 可取32个不同值的标志。

Entropy例
?

掷一枚骰子,各点出现的概率相等,用随机 变量X表示为
X P(X)



1 2 …… 6 1/6 1/6 ……1/6

则该离散随机变量X的熵为

H ( X ) ? ? ? p( x) log 2 p( x) ? ? ?1 / 6 * log 2 1 / 6 ? 2.585bits

Entropy例
例.袋内有100个球,其中红球80个,白球20个.随意摸取 一个球,猜测是什么颜色,这一随机事件的概率空间为
? X ? ? a1 a2 ? ? p ? x ?? ? ?0.8 0.2? ? ? ? ?

如果被告知摸出的是红球,那么获得的自信息量是: I ?a1 ? ? ? log p?a1 ? ? ? log 2 0.8(比特) 如果被告知摸出的是白球,那么获得的自信息量是:
I ?a2 ? ? ? log p?a2 ? ? ? log 2 0.2(比特)

若每次摸出一个球以后又放回去,再进行第二次摸取, 那么摸取n次中,红球出现的次数约为 np?a1 ? 次,白球 出现的次数约为 np?a2 ? 次。则摸取n次后总共所获得的 自信息量为 np?a ?I ?a ? ? np?a ?I ?a ?
1 1 2 2

这样,平均摸取一次所能获得的信息量约为
H ? X ? ? p?a1 ?I ?a1 ? ? p?a2 ?I ?a2 ? ? ?? p?a1 ? log p?a1 ? ? p?a2 ? log p?a2 ?? ? ?? p?ai ?I ?ai ?
i ?1 2

显然,这就是信源X的信息熵H(X)。因此信息熵是从平 均意义上来表征信源的总体信息测度。信息熵具有以下 三种物理含义:

熵的物理含义
? 第一。信息熵H(X)是表示信源输出前,信 源的平均不确定性。 例如有两个信源,其概率空间分别为
? X ? ? a1 a2 ? ? p?x ?? ? ?0.99 0.01? ? ? ? ? ? Y ? ? b1 b2 ? ? p ? y ?? ? ?0.5 0.5? ? ? ? ?

H ( X ) ? ?0.99 log 2 0.99 ? 0.01 log 2 0.01 ? 0.08 (比特/ 符号) H (Y) ? ?0.5 log 2 0.5 ? 0.5 log 2 0.5 ? (比特/ 符号) 1
信息熵正好反映了信源输出消息前,接收者对信源存在的平均不确定程度的大小。 即没有输出消息之前,H(X)反映了猜测哪一个消息将出现的不确定性的大小。

可见H (Y ) ? H ? X ?。 信源Y比信源X的平均不确定性要大。

熵的物理含义
? 第一。信息熵H(X)是表示信源输出后,每 个消息(或符号)所提供的平均信息量。

熵的物理含义
? 第三。用信息熵H(X)来表征变量X的随机性
? X ? ? a1 a2 ? ? p?x ?? ? ?0.99 0.01? ? ? ? ? ? Y ? ? b1 b2 ? ? p ? y ?? ? ?0.5 0.5? ? ? ? ?

H ( X ) ? ?0.99 log 2 0.99 ? 0.01 log 2 0.01 ? 0.08 (比特/ 符号) H (Y ) ? ?0.5 log 2 0.5 ? 0.5 log 2 0.5 ?(比特/ 符号) 1
变量Y取b1和b2是等概率的,所以其随机性大。而变量X取 a1的概率比取a2的概率大很多,这时,变量X的随机性就小。 因此,H(X)反映了变量的随机性。信息熵正是描述随机变量 X所需的比特数

Entropy例
1 1 1 1 1 1 H ( X ) ? ? log 2 ? log 2 ? log 2 2 2 4 4 8 8

1 1 1 1 ? log 2 ? 4 log 2 ? 2bits 16 16 64 64
?1 1 1 1 1 1 1 1 ? p(x) ? ? , , , , , , , , ? ? 2 4 8 16 64 64 64 64 ?

8匹马参加赛马,各自取胜的概率为p(x)
0, 10, 110, 1110, 111100, 111101, 111110, 111111 即问题的不确定性为2个比特。

Entropy例
例:一条电线上串联了8个灯泡。灯泡损坏的可能性是等概率 的。通过电路的检测,在获得足够的信息量后才能确定哪个 灯泡已损坏。 分析:在测量前,8个灯泡都可能损坏,它们损坏的先验概率 是 p1 ?x ? ? 1 8 ,这时存在的不确定性是先验概率 p1 ?x ? 的函 数,用I ? p1 ?x ?? 表示。 第一次测量后,变成猜测4个灯泡中哪一个损坏,这时后验概 率变为 p2 ?x ? ? 1 4 ,因此,尚存在的不确定性是 I ? p2 ?x ??是 p2 ?x ? 的函数。所获得的信息量就是测量前后不确定性减少 的量,即第一次测量获得的信息量: 1 1 I ? p1 ?x ?? ? I ? p2 ? x ?? ? log 2 ? log 2 p1 ? x ? p2 ? x ?
log 2 8 ? log 2 4 ? 3 ? 2 ? 1(bit)

第二次测量后,变成猜测2个灯泡中哪一个损坏,这时后验概率 变为 p3 ?x ? ? 1 2 ,因此,尚存在的不确定性是 I ? p3 ? x ?? 第二次测量所获得的信息量: 1 1 I ? p2 ?x ?? ? I ? p3 ?x ?? ? log 2 ? log 2 ? 1bit p2 ? x ? p3 ?x ? 第三次测量后,不确定性完全消除,能获知哪个灯泡是坏的。 因此,尚存在的不确定性等于零。 第三次测量获得的信息量
p3 ?x ? 因此,要从8个等可能损坏的串联灯泡中确定哪个灯泡损坏,至 少要获得3bit的信息量。 信息量=不确定性减少的量=(收到此消息前关于某事件发生 的不确定性)-(收到此消息后关于某事件发生的不确定性) I ? p2 ?x ?? ? 0 ? log 2 1 ? 0 ? 1bit

小结
? ? ? ? ? I(x)有两种含义: 1。当事件x发生以前,表示事件x发生的不确定性。 2。当事件x发生以后,表示事件x所含有的信息量。 H(X)有三种含义: 1。信息熵H(X)是表示信源输出前,信源的平均不 确定性。 ? 2。信息熵H(X)是表示信源输出后,每个消息所提 供的平均信息量。 ? 3。用信息熵H(X)来表征变量X的随机性。

离散随机变量的熵
? 设果随机变量X有K个可能的取值 x1 , x2 ,?, xk ? 相应的概率为 p?x1 ? ? p1 , p?x2 ? ? p2 ,?, p?xk ? ? pk ? ? 记为 P ? ? p1 , p2 ,?, pk ? ? 则离散随机变量X的熵可记为
H ? X ? ? HK

? ?

K ? ? P ? H K ? p1 , p2 ,?, pk ? ? ?? pk log pk k ?1

? 它有以下性质

熵的性质
性质1。对称性,即 p1 , p2 ,?, pk 的顺序任意互换时,熵 的值不变,即

? ? ? H K ? pk , p1 , ? , pk ?1 ?

H K ? p1 , p2 , ? , pk ? ? H K ? p2 , p3 , ? , pk , p1 ?

该性质表明熵只与随机变量的总体结构有关

熵的性质
性质2。非负性

H K ? p1 , p2 ,?, pk ? ? 0

? ? 性质3。确定性,若 P ? ? p1 , p2 ,? , pk ? 中有一个分量为1 ? ? 其余分量均为零时 H P ? 0 (即为常量)
K

? ?

性质4。扩展性

lim ? ?0 H K ? p1 , p2 ,?, pk ? ? , ? ? ? H K ? p1 , p2 ,?, pk ?
该性质表明随机变量的取值数增多时,若这些取值对应 的概率很小,则该随机变量的熵不变,即小概率事件在 熵的计算中占比重很小。

熵的性质
X与Y的概率分布分别为? p1 , p2 ,?, pn ?, ?q1 , q2 ,?, qm ?
则: H ? XY ? ? H ? X ? ? H ?Y ?
性质5。可加性:统计独立信源X和Y的联合信源 的熵等于信源X和信源Y的熵之和。即

? H n ? p1 , p2 ,?, pn ? ? H m ?q1 , q2 ,?, qm ?
其中: pi ? 1 ?
i ?1 n

H nm ? p1q1 , p1q2 ,?, p1qm , p2 q1 , p2 q2 ,?, pn q1 ,?, pn qm ?

?q
j ?1

m

i

?1

?? p q
i ?1 j ?1 i

n

m

j

?1

可加性是熵函数的一个重要特性,正因为具有可加性, 所以可以证明熵函数的形式是唯一的。

熵的性质
性质6。强可加性:两个相互关联信源X和Y的熵等于信源 X熵加上在X已知条件下信源Y的条件熵。即
X ? ? p1 , p2 , ? , pn ? P ?Y ? y j | X ? xi ? ? pij
n

Y ? ?q1 , q2 , ? , qm ? 0 ? pij ? 1

我们用条件概率来描述它们之间的关系

H nm ? p1 p11 , p1 p12 , ?, p1 p1m , p2 p21, ?, p2 p2 m , pn pn1 , ?, pn pnm ? ? H n ? p1 , p2 , ?, pn ? ? ? pi H m ? pi1 , pi 2 , ?, pim ?
i ?1

其中: pi ? 1 ?
i ?1

n

?? p p
i ?1 j ?1 i

n

m

ij

?1

?p p
i ?1 i

n

ij

? qj

X ? ? p1 , p2 ,?, pn ? Y ? ?q1 , q2 ,?, qm ? 其中
令P?Y ? y j | X ? xi ? ? pij
n m n m i ?1 j ?1
n m



?q ?1 p?x y ? ? p?x ? p?y | x ? ? p p
i ?1 i

?p
i

n

?1
j

m

j ?1

j

i

j

i

i

ij

? ?? pi pij ? ?? p ?xi y j ? ? 1,
i ?1 j ?1
n

?p
i ?1

n

i

?1

m ? m ? 又 ? ?? pi pij ? ? pi ? ? pij ? ? 1, ? ? pij ? 1 ? ? i ?1 j ?1 i ?1 j ?1 j ?1 ? ?

p1 p? x1 y1 ? p? x1 y2 ? ? p? x1 ym ?

q1

q2

?

qm

p32
即当某一个i确定了以后, 有:? pij=1
j ?1 m

p2 p? x2 y1 ? p? x2 y2 ? ? p? x2 ym ? p3 p? x3 y1 ? p? x3 y2 ? ? p? x3 ym ? ? ? ? ? ?

pn p? xn y1 ? p? xn y2 ? ? p? xn ym ?

在已知条件:X ? ? p1 , p2 , ? , pn ? Y ? ?q1 , q2 , ? , qm ?

?p
i ?1 m j ?1 j

n

i

?1

?q

?1

P ?Y ? y j | X ? xi ? ? pij

?? p p
i ?1 j ?1 i m j ?1

n

m

ij

?1

可推出: pij ? 1。证明下列不等式 ?

H nm ? p1 p11 , p1 p12 , ?, p1 p1m , p2 p21, ?, p2 p2 m , pn pn1 , ?, pn pnm ? ? H n ? p1 , p2 , ?, pn ? ? ? pi H m ? pi1 , pi 2 , ?, pim ?
i ?1 n

小结 1:
因为 p?xi y j ? ? p?xi ? p?y j | xi ? ? pi pij。所以
H nm ? p1 p11 , p1 p12 , ? , p1 p1m , p2 p21 , ? , p2 p2 m , pn pn1 , ? , pn pnm ? ? ??? pi pij log pi pij ? ??? p ?xi y j ?log p ?xi y j ? ? H ? XY ?
n m n m i ?1 j ?1 i ?1 j ?1

熵函数H nm就是X与Y联合信源的联合熵H ? XY ?。

小结 2:
H nm ? p1 p11 , p1 p12 , ? , p1 p1m , p2 p21 , ? , p2 p2 m , pn pn1 , ? , pn pnm ? ? H n ? p1 , p2 , ? , pn ? ? ? pi H m ? pi1 , pi 2 , ? , pim ?
i ?1 n

H m ? pi1 , pi 2 , ? , pim ? ? ?? pij log pij ? H ?Y | X ? xi ?
j ?1

m

它表示当已知信源X取值为xi的条件下,信源Y选取一个 值所提供的平均信息量,这个量与xi 有关将此量对X取 统计平均值,记为H ?Y | X ?, 称为条件熵

? p H ?p
i ?1 i m

n

i1

, pi 2 , ? , pim ? ? ? pi H ?Y | X ? xi ? ? H ?Y | X ?
i ?1

n

强可加性可写成: H ? XY ? ? H ? X ? ? H ?Y | X ?

熵的性质
性质7。极值性,即当X为等概率分布时,熵的值最大。

1? ?1 1 H K ? p1 , p2 ,?, pk ? ? H K ? , ,?, ? ? log K K? ?K K

ln x ? x ? 1.( x ? 0)
log x ln x ? log e

log x ? log e ? ln x

凸集合
定义:设D是K维实空间R K中的子集,若任给

? , ? ? D,均有?? ? ?1 ? ? ?? ? D, 0 ? ? ? 1
则称D是凸集合。 若? , ? 在凸集D内,则? , ? 之间的线段整个都在 D内。 凸集的例子很多,例如实数域是凸集,但整数、 有理数域不是凸集。

?

?
凸集

?
?

非凸集

凹函数与凸函数 ?a 定义: , b ?上的函数f ?x ?被说成是凹函数,如果 对于任意x1 , x2 ? ?a, b ?, 且0 ? ? ? 1则 f ??x1 ? ?1 ? ? ?x2 ? ? ?f ?x1 ? ? ?1 ? ? ? f ?x2 ?
一个函数被说成是严格凹函数,仅当?=0或1时 等号成立。
定义:一个函数f ?x ?被说成是凸函数,如果 ? f ? x ?是凹函数。

凹性是许多信息理论量 的基本性质

凹函数与凸函数
一个函数称为凹函数,如果它总是位于其任意 一条弦的下方。 一个函数称为凸函数,如果它总是位于其任意 一条弦的上方。
凹函数有:x , | x |, e , x log x
2 x

凸函数有:log x,

x

? for

? for x ? 0?

x ? 0?

定理:如果函数f ?x ?有二阶导函数,且导函数 处处非负(正定),则函数是凹函数(严格凹函数)
函数在x0点用Taylor展开 f ??? x0 ? 2 ?? x0 ?? x ? x0 ? ? ?x ? x0 ? f ? x ? ? f ? x0 ? ? f 2 x*取x0和x之间,且假设f ?? x* ? 0

再令x0 ? ?x1 ? ?1 ? ? ?x2

? ?

取x ? x1 , 则f ? x1 ? ? f ? x0 ? ? f ?? x0 ???1 ? ? ?? x1 ? x2 ?? 取x ? x2 , 则f ? x2 ? ? f ? x0 ? ? f ?? x0 ??? ? x2 ? x1 ??

则?f ? x1 ? ? ?1 ? ? ? f ? x2 ? ? f ? x0 ? ? f ??x1 ? ?1 ? ? ?x2 ?

Jensen不等式
定理:如果f是凹函数,X是一随机变量,则 f ?EX ? ? Ef ? X ? 如果f是严格凹函数,且等号成立隐含X=EX 概率为1,即X是一常数。 即: 若ai ? 0, i ? 1,2, ? , n.且? ai ? 1, 对于凹函数f ?t ?
i

? n ? n 则Jensen不等式为:f ? ? ai ti ? ? ? ai f ?ti ? ? i ?1 ? i ?1

Jensen不等式的证明
若ai ? 0, i ? 1,2,? , n.且? ai ? 1, 对于凹函数f ?t ?
i

? n ? 则Jensen不等式为: ai f ?ti ? ? f ? ? ai ti ? ? i ?1 ? i ?1 ? 归纳法证明。
n

熵的极值性的证明
极值性的证明:即当X为等概率分布时,熵的值最大。

1? ?1 1 H K ? p1 , p2 ,?, pk ? ? H K ? , ,?, ? ? log K K? ?K K
? ? 证:设 P ? ? p1 , p2 ,..., pk ? , 且

? pi ? 1
i ?1

k

? 1 ? ,另设 Y ? ?? 即 yi ? 1 pi P

因为已知LogY在实数集(Y>0)是凸函数,所以根据

Jensen不等式,有

? ? ? ? E ?log Y ? ? log E ?Y ? ? ? ? ?

?

?

熵的性质
性质8。递增性

H n ? m ?1 ? p1 , p2 , ? , pn ?1 , q1 , q2 , ? , qm ? ? q1 q2 qm ? ? H n ? p1 , p2 , ? , pn ?1 , pn ? ? pn H m ? , , ? , ? ?p p pn ? ? n n ?
其中? pi ? 1, 令? q j ? pn
i ?1 j ?1 n m

性质表明,若原信源X(n个符号的概率分布为 p1 ,?, pn ) 中有一个元素划分(分割)成m个元素(符号),而这m个元 素的概率之和等于原元素的概率,则新信源的熵增加了 一项由于划分而产生的不确定性量。

例:运用递增性,化简熵函数的计算 H ? 1 , 1 , 1 , 1 ? ? ?
H n ? p1 , p2 , ? , pn ?1 , pn ? ? H n ?1 ? p1 , p2 , ? , pn ?1 ? pn ? ? pn ?1 ? pn ? ? pn ?1 ? pn ?H 2 ? ?p ?p ,p ?p ? ? n n ?1 n ? ? n ?1
16 ? ?1 1 1 1? ?1 1 1 1? ?1 1? ? 1 6 ? H ? , , , ? ? H ? , , ? ? ? ? ? ?H ? , 3 3 6 6? 3 3 6 6 ? ? 6 6 ? ?1 6 ?1 6 1 6 ?1 6 ? ? ? ? ? ?1 1 1? 1 ?1 1? ? H? , , ? ? H? , ? ?3 3 3? 3 ? 2 2? 1 3 ? 1 ?1 1? ?1 1 1? ?1 1? ? 1 3 ? H ? , ? ? ? ? ? ?H ? , ?1 3 ?1 3 1 3 ?1 3 ? ? 3 H ? 2 , 2 ? ? ?3 3 3? ?3 3? ? ? ? ? ?1 2? 2 ?1 1? 1 ?1 1? ?1 2? ?1 1? ? H ? , ? ? H ? , ? ? H ? , ? ? H ? , ? ? H ? , ? ? 1.918 (bit / 符号) ?3 3? 3 ?2 2? 3 ?2 2? ?3 3? ?2 2?

?3 3 6 6?

相关熵与互信息
? 一个随机变量的平均信息量是那个随机变量不确 定性的一个测度,它等于描述那个随机变量所需 信息量的一个测度。 ? 相关熵D(p||q):如果我们知道一个随机变量的真 实分布p(x),我们可以构造一个平均描述长度为 H(p)的代码,如果我们试图使用分布为q的随机变 量去描述p,那么我们就需要用长度为 H(p)+D(p||q)的代码来描述这个随机变量p(x) 。 ? 即D(p||q)可以表示随机变量q与p的距离。

相关熵
p?x ? 定义:D ? p || q ? ? ? p ? x ? log q?x ? x? X 0 p 这里: 0 log ? 0 p log ? ? q 0

且有:D ? p || q ? ? 0 当p ? q时 D ? p || q ? ? 0 D ? p || q ?不对称,且不满足三角不等式。

相关熵例题
q?0? ? 1 ? s,q?1? ? s。求D? p || q ?,D?q || p ?。 解: 显然如果r ? s,则D? p || q ? ? D?q || p ? ? 0 1 1 如果r ? ,s ? 2 4 D? p || q ? ? 0.2075 bits X ? ?0,1?上有分布p, q,令p ?0 ? ? 1 ? r,p?1? ? r

D?q || p ? ? 0.1887 bits

Log sum不等式
对于非负数a1 , a2 , ? , an 和b1 , b2 , ? , bn ai ? ? 有? ai log ? ? ? ai ? log bi ? i ?1 ? i ?1
n n

?a
i ?1 n i ?1

n

i

?b

i

ai 当且仅当 为常数时等号成立。 bi 作业:用log sum不等式证明熵函数的极值性

D(p||q)的性质
? D(p||q)是概率密度函数关于(p,q)的凹函数。

即如果 ? p1 , q1 ? 和 ? p2 , q2 ? 是密度函, D ? ? p 1 ? ?1 ? ? ? p2 || ? q 1 ? ?1 ? ? ? q2 ? ? ? D ? p 1|| q 1 ? ? ?1 ? ? ? D ? p2 || q 2 ?
证:由Log Sum不等式:

? ? 定理:熵函数H K ? p ?是p=? p1 , p2 , ? , p K ?上的凸 函数,即对任意?, ? ? ? 1和任何两个概率矢 0 ? ? 量p1,p2,有 ? ? ? ? H K ??p1 ? ?1 ? ? ? p2 ? ? ?H K ? p1 ? ? ?1 ? ? ?H K ? p2 ? 证:由于概率矢量的集合S p是凸集,因此熵函 数是从凸集S p到实数域R的一个实值函数。设 ? ? p1=? p11 , p12 , ? , p1K ?,p2=? p21 , p22 , ? , p2 K ? ? S p 对任何0 ? ? ? 1,则

熵函数的凸性

熵函数形式的唯一性
定理:设H k ? p1 , p2 , ? , pk ?是非负实函数,对于任意k, 满足pk ? 0, pk ? 1,且 ?
k

1.对任意K,函数H k ? p1 , p2 , ? , pk ?是pk , k ? 1,2, ?, K的 连续和对称函数; 2.对任意K,有H k ?1 ? p1 , p2 , ?, pk ,0 ? ? H k ? p1 , p2 , ? , pk ? 1? ?1 1 3.对任意K,有H k ?1 ? p1 , p2 , ? , pk ,0 ? ? H k ? , , ? , ? K? ?K K 4.若pk pkj ? 0, ?? pk pkj ? 1, ? pkj ? 1, k ? 1, ? , K , j ? 1, ? , m
k ?1 j ?1 j ?1 K m m

有 H Km ? p1 p11 , p1 p12 , ? , p1 p1m , ? , p K p K 1 , p K p K 2 , ? , p K p Km ? ? H K ? p1 , p2 , ? , p K ? ? ? pk H m ? pk 1 , pk 2 , ? , pkm ?
k ?1 K

则 H K ? p1 , p2 , ? , p K ? ? ?C ? pk log pk
k ?1 K

其中C为正常数。 以上的定理说明,只要函数H K ? p1 , p2 , ? , p K ?满足 以上基本性质,则它一定是熵函数的形式,这就 是熵函数的唯一性。

离散随机变量的条件熵与联合熵
如果需要用两个随机变量X , Y来描述随机试验 的所有结果,则称( X , Y )为二维随机变量。若 二维随机变量的每一对取值是可以一一列举出 率为p ?xk , y j ?, k ? 1,2, ? , j ? 1,2, ? , 则称( X , Y )为 ,其中p ?xk , y j ?满足: (1). p ?xk , y j ? ? 0, 来的: k , y j ), k ? 1,2, ? , j ? 1,2, ? , 并且相应的概 (x

二维随机变量,称?p ?xk , y j ?? ( X , Y )的联合分布 为 (2).?? p ?xk , y j ? ? 1
k j

p1 p?x1 y1 ? p?x1 y2 ? ? p?x1 ym ?

q1

q2

?

qm

p2 p?x2 y1 ? p?x2 y2 ? ? p?x2 ym ? p3 p?x3 y1 ? p?x3 y2 ? ? p?x3 ym ? ? ? ? ? ?

pn p?xn y1 ? p?xn y2 ? ? p?xn ym ?
若记 p ? xk ? ? ? p ?xk , y j ?, k ? 1,2, ? , p ? y j ? ? ? p ?xk , y j ?j ? 1,2, ? ,
j k

则?p ? xk ??为( X , Y )关于X的边际概率分布

?p?y ??为( X , Y )关于Y的边际概率分布
j

p1 p? x1 y1 ? p? x1 y2 ? ? p? x1 ym ?

q1

q2

?

qm

p2 p? x2 y1 ? p? x2 y2 ? ? p? x2 ym ? p3 p? x3 y1 ? p? x3 y2 ? ? p? x3 ym ? ? ? ? ? ?

pn p? xn y1 ? p? xn y2 ? ? p? xn ym ?

给定事件Y ? y j 发生时,事件X ? xk 发生的条件 概率为:p ?xk | y j ? ? p ?xk , y j ? p?y j ? , p?y j ? ? 0

给定事件X ? xk 发生时,事件Y ? y j 发生的条件 概率为:p ? y j | xk ? ? p ?xk , y j ? p ? xk ? , p ? xk ? ? 0

离散随机变量的条件熵
定义:事件y j发生时,随机变量X 的条件熵定义为 H ? X | y j ? ? ? p ? xk | y j ? I ? xk | y j ? ? ?? p ? xk | y j ? log p ? xk | y j ? 对随机变量H ? X | y j ? 关于Y 取数学期望,定义随机 变量Y 给定的条件下,随机变量X 的条件熵定义为 ? ?? p ? y j ? ? p ? xk | y j ? log p ? xk | y j ?
j k k k

H ? X | Y ? ? E ? H ? X | y j ?? ? ?

? ??? p ? xk , y j ? log p ? xk | y j ?
k j

同理:事件xk 发生时,随机变量X的条件熵定义为 H ?Y | xk ? ? ?? p ? y j | xk ?log p ? y j | xk ?
k

即随机变量X给定的条件下,随机变量Y的条件熵 定义为 H ?Y | X ? ? ??? p ?xk , y j ?log p ? y j | xk ?
k j

随机变量的联合熵
定义:离散随机变量X和Y的联合熵定义为 H ? XY ? ? ?? p ?xk , y j ?I ?xk y j ?
k j k j

? ??? p ?xk , y j ?log p ?xk , y j ? 条件熵和联合熵有以下性质

条件熵和联合熵的性质
性质1。当随机变量X和Y独立时 H ? X | Y ? ? H ? X ?, H ?Y | X ? ? H ?Y ?

性质2。当随机变量X和Y独立时 H ? XY ? ? H ? X ? ? H ?Y ? 性质3。对一般随机变量X和Y有

H ? XY ? ? H ? X ? ? H ?Y | X ? ? H ?Y ? ? H ? X | Y ?

条件熵和联合熵的性质
性质4。对一般随机变量X和Y有 H ? XY ? ? H ? X ? ? H ?Y ? H ?X | Y ? ? H ?X ? H ?Y | X ? ? H ?Y ?

性质5。H ? X 1 X 2 ? X N ? ? H ? X 1 ? ? H ? X 1 ? ? ? ? H ? X N ? 且当N个随机变量相互独立时,等号成立。 性质6。H ? X 1 X 2 ? X N ? ? H ? X 1 ? ? H ? X 2 | X 1 ? ? ? H ? X 3 | X 1 X 2 ?? ? H ? X N | X 1 X 2 ? X N ?1 ?

? 0 1 2 ? ? X ? 设随机变量X的概率分布为? ? ? ? 11 4 1 ? ? p? x ?? ? 36 9 4 ? ? ? 二维随机变量? X , Y ?的联合概率分布为
p ?xi , y j ?
Y X

0 1/4

1 1/18

2 0

0

1
2

1/18
0

1/3
1/18

1/18
7/36

求解H ? X ?, H ?Y | X ?和H ? XY ?.

由条件概率公式p ? y j | xi ? ?
p? y j | xi ?
Y

p?xi , y j ? p? xi ?
2 0 2/9

,的

X

0 9/11 2/11

1 1/8 3/4

0 1

2

0

1/8

7/9

显然有 H ? XY ? ? H ? X ? ? H ?Y | X ? ? 1.54 ? 0.87 ? 2.41bits

设一系统的输入符号集为X=?x1 , x2 , x3 , x4 , x5 ?,

输出符号集为Y=?y1 , y2 , y3 , y4 ?(结构如下图所示), 输入符号与输出符号的联合分布如下表所示, 求H ? X ?, H ?Y ?, H ? XY ?, H ?Y | X ?, H ? X | Y ?.
P(xi,yj) X1 X2 X X3 X4 Y y1 0.25 0 0 y2 0 y3 0 0 y4 0 0 0
x4 x5 x1 x2 x3 y1 y2 y3

0.10 0.30 0

0.05 0.10

0.05 0.10

X5

0

0

0.05

0

y4

P(xi|yj)

Y

p ?xi | y j ? ?

p ?xi , y j ? p?y j ?
X

y1
5/7 2/7 0 0

y2
0 6/7 1/7 0

y3
0 0 1/2 1/4

y4
0 0 0 1

X1 X2 X3 X4

X5

0

0 Y

1/4

0

p ? y j | xi ? ?

p ?xi , y j ? p ? xi ?

P(yj|xi)

y1

y2

y3

y4

X1
X2 X X3 X4 X5

1
1/4 0 0 0

0
3/4 1/3 0 0

0
0 2/3 1/3 1

0
0 0 2/3 0

离散随机变量的平均互信息
定义:随机变量X与随机变量Y中事件y j 之间的平均 互信息定义为: I ?X ; y j ? ? ? p?xk | y j ?I ?xk ; y j ? ? ? p?xk | y j ?log
k k

p?xk | y j ? p ? xk ?

定义:随机变量X中事件xk 与随机变量Y之间的平均 互信息定义为: I ?xk ; Y ? ? ? p? y j | xk ?I ?xk ; y j ? ? ? p? y j | xk ?log
j j

p? y j | xk ? p?y j ?

离散随机变量的平均互信息
定义:随机变量X与随机变量Y之间的平均互信息定义为: I ? X ; Y ? ? ? p ? y j ?I ?X ; y j ? ? ? p ? xk ?I ? xk ; Y ?
j k k j

? ?? p ?xk , y j ?I ?xk ; y j ? 显然也可以表示成: I ? X ; Y ? ? ?? p ?xk , y j ?log
k j

p ?xk | y j ? p ? xk ? ? ?? p ?xk , y j ?log
k j

? ?? p ?xk , y j ?log
k j

p ? y j | xk ? p?y j ?

p ? xk ? p ? y j ?

p ?xk , y j ?

离散随机变量的平均互信息的性质
性质1:对称性。I ? X ; Y ? ? I ?Y ; X ? ? H ?Y ? ? H ?Y | X ? 性质2:I ? X ; Y ? ? H ? X ? ? H ? X | Y ? ? H ? X ? ? H ?Y ? ? H ? XY ?

性质3:非负性。I ? X ; Y ? ? 0 性质4:I ? X ; Y ? ? H ? X ? I ? X ; Y ? ? H ?Y ?

性质5:当随机变量X和Y统计上独立时, I ?X ;Y ? ? 0 性质6:I ? X ; YZ ? ? I ? X ; Z ? ? I ? X ; Y | Z ? ? I ?X ;Y ? ? I ?X ; Z | Y ?

? ? 定理:熵函数H K ? p ?是p=? p1 , p2 , ? , p K ?上的凸 函数,即对任意?, ? ? ? 1和任何两个概率矢 0 ? ? 量p1,p2,有 ? ? ? ? H K ??p1 ? ?1 ? ? ? p2 ? ? ?H K ? p1 ? ? ?1 ? ? ?H K ? p2 ? 证:由于概率矢量的集合S p是凸集,因此熵函 数是从凸集S p到实数域R的一个实值函数。设 ? ? p1=? p11 , p12 , ? , p1K ?,p2=? p21 , p22 , ? , p2 K ? ? S p 对任何0 ? ? ? 1,则

熵函数的凸性

互信息的凸性
根据互信息的定义,当X,Y的取值分别为K和 J个时,I ? X ; Y ?也可以写成 I ? X ; Y ? ? ?? p ? xk ? p ? y j | xk ?log
K J k ?1 j ?1 K

p ? y j | xk ?

? p?x ? p?y
i ?1 i

j

| xi ?

因此互信息I ? X ; Y ?是随机变量X的概率矢量 ? p=? p? x1 ?, p ? x2 ?, ? , p ? xK ??和条件概率矩阵 ? Q ? p ? y j | xk ? K ? J 的函数,可以记作I ? p, Q ?。

?

?

联合分布中的边际分布

互信息的凸性
定理:当条件概率矩阵Q ? p ? y j | xk ? 给定时, ? ? 互信息I ? p, Q ?是p的凸函数,即任给 ? p1=? p1 ? x1 ?, p1 ? x2 ?, ? , p1 ? xK ?? ? S p, ? p2=? p2 ? x1 ?, p2 ? x2 ?, ? , p2 ? xK ?? ? S p 及0 ? ? ? 1,有 ? ? ? ? ?I ? p1 , Q ? ? ?1 ? ? ?I ? p2 , Q ? ? I ??p1 ? ?1 ? ? ? p2 , Q ? 证:记p ? xk ? ? ?p1 ? xk ? ? ?1 ? ? ? p2 ? xk ?, k ? 1,2, ? , K

?

?

??
l ?1

L

l

log xl ? log ? ? l xl
l ?1

L

互信息的凸性

定理:当随机变量X的概率矢量 ? p=? p?x1 ?, p?x2 ?,?, p?xK ??给定时,互信息 ? I ? p, Q ?是Q的凹函数,即任给两个条件概率 矩阵Q1,Q2及0 ? ? ? 1,有 ? ? ? ?I ? p, Q1 ? ? ?1 ? ? ?I ? p, Q2 ? ? I ? p,?Q1 ? ?1 ? ? ?Q2 ?

相关熵与互信息
? 一个随机变量的平均信息量是那个随机变 量不确定性的一个测度,它等于描述那个 随机变量所需信息量的一个测度。 ? 相关熵D(p||q):如果我们知道一个随机变 量的真实分布p(x),我们可以构造一个平均 描述长度为H(p)的代码,如果我们使用了分 布为q的代码,那么我们就需要一个长度为 H(p)+D(p||q)的代码来描述这个随机变量。

相关熵
p?x ? 定义:D ? p || q ? ? ? p ? x ? log q?x ? x? X 0 p 这里: 0 log ? 0 p log ? ? q 0

且有:D ? p || q ? ? 0 当p ? q时 D ? p || q ? ? 0 D ? p || q ?不对称,且不满足三角不等式。

互信息
为p? x, y ?,边际分布分别为p? x ?, p? y ?,则互 信息I ? X ; Y ?是联合分布p? x, y ?与乘积分布 p ? x, y ? I ? X ; Y ?=?? p? x, y ? log p?x ? p? y ? x? X y?Y
I ? X ; Y ?是一个随机变量包含另一个随机变量 信息量的测度。它是一个随机变量,由于知 道一个随机变量之后,起不确定性的减少量。

定义:两个随机变量? X , Y ?的联合概率分布

p? x ? p? y ?的相关平均信息量

? D? p? x, y ? || p? x ? p? y ??

相关熵例题
q?0? ? 1 ? s,q?1? ? s。求D? p || q ?,D?q || p ?。 解: 显然如果r ? s,则D? p || q ? ? D?q || p ? ? 0 1 1 如果r ? ,s ? 2 4 D? p || q ? ? 0.2075 bits X ? ?0,1?上有分布p, q,令p ?0 ? ? 1 ? r,p?1? ? r

D?q || p ? ? 0.1887 bits

互信息与熵
H ? XY ?
I ? X ;Y ? ? H ? X ? ? H ? X | Y ? I ? X ; Y ? ? H ?Y ? ? H ?Y | X ? I ? X ; Y ? ? H ? X ? ? H ?Y ? ? H ? XY ? I ?X; X ? ? H ?X ?

H ?X | Y ? H ?Y | X ? I ?X ;Y ? H ?X ?

H ?Y ?

连续随机变量的互信息
如果随机变量X的取值充满某个实数区间,则 称X为连续变量。记p X ? x ?为随机变量X的概率 二维连续随机变量? X , Y ?的联合概率密度函数 记为p XY ? x, y ?,则p XY ? x, y ? ? 0; ? 称p X ? x ? ? ? p XY ? x, y ?dy
?? ?? ?? ?? ?? ??

密度函数,显然有: p X ? x ? ? 0; ? p X ? x ?dx ? 1
??

??

?

p XY ? x, y ?dxdy ? 1;
?? ??

pY ? x ? ? ? p XY ? x, y ?dx

分别为二维连续随机变量关于X和Y边际概率密度

连续随机变量的互信息
连续随机变量X和Y之间的互信息定义为 I ? X ; Y ? ? ?? p XY ? x, y ? log ? ?? p XY ? x, y ? log pY ? y ? p X |Y ? x | y ? p X ?x ? dxdy dxdy

pY | X ? y | x ?

p XY ?x, y ? ? ?? p XY ? x, y ? log dxdy p X ? x ? pY ? y ?

设二维连续随机变量? X , Y ?的概率密度函数为 p XY ? x, y ? ? ? 1 ? ?? 2 1? ? 2 ? ? 1 2?? x? y 1 ? ? 2 ? ? x ? mx ?2 2 ? ? x ? mx ?? y ? m y ? ? y ? m y ?2 ? ? ? ? ? ? ?? 2 2 ? x? y ? y ?? ? ?x ? ?? ? 1 2? ? x ? mx ? ? exp ?? 2 2? ? x ? 2? x ? 1 1

?

?

p X ? x ? ? ? p XY ? x, y ?dy ?
?? ??

??

? 1 ? ? 2? ?y ? my ? ? pY ? y ? ? ? p XY ? x, y ?dx ? exp ?? 2 ?? 2? ? y ? 2? y ? ? ? p XY ? x, y ? 1 I ? X ; Y ? ? ?? p XY ? x, y ? log dxdy ? ? log 1 ? ? 2 p X ? x ? pY ? y ? 2

?

?

连续随机变量的微分熵
定义:设连续随机变量X的概率密度函数为 p X ? x ?则定义 H c ? X ? ? h? X ? ? ? ? p X ? x ? log p X ?x ?dx
?? ??

为连续随机变量X的微分熵。

例:设连续随机变量X满足均匀分布,即其 概率密度函数为 ? 1 ? x ? ?a, b? p X ?x ? ? ? b ? a ? 0 其他 ? 则X的微分熵为 H c ? X ? ? ? ? p X ? x ? log p X ? x ?dx
?? ??

1 1 ? ?? log dx ? log?b ? a ? a b?a b?a
b

设连续随机变量X的满足高斯分布,其概率 密度函数为 1 ? 1 2? ?x ? m ? ? p X ?x ? ? exp ?? 2 2? ? ? 2? ? 则X的微分熵为 H c ? X ? ? ? ? p X ? x ? log p X ? x ?dx
?? ??

1 2 ? log 2?e? 2

?

?

?补证明作业?

微分熵的极大化
定理:设连续变量X的取值限于

?? M , M ?,即?? M p X ?x ?dx ? 1,
M

这时X的微分熵 H c ? X ? ? log 2 M 等号在均匀分布时取得。

定理:设连续变量X的均值为m,方差为? ,
2

即? p X ? x ?dx ? 1, xpX ? x ?dx ? m, ?
?? ??

?

?

? ?x ? m ?
??

?

2

p X ? x ?dx ? ?

2

设q? x ?为均值为m,方差为? 2 1 ? 1 2? exp ?? 2 ? x ? m ? ? 2? ? ? 2? ? 证明时利用相关熵D? p || q ?。 q?x ? ?
2

的正态分布的密度函数,则



1 设p? x ?为均值为m,方差为? 2 H c ? X ? ? log 2?e? 的密度函数。 2 2 当X服从均值为m方差为? 的高斯分布时, 上式取等号。

?

?

定理:设X为连续变量,其概率密度函数为 加且可导的函数,此时Y ? g ? x ?也是随机变 量,则Y ? g ? x ?的微分熵为
?? ??

p X ? x ?,微分熵为H c ? X ?,y ? g ? x ?是单调增

H c ?Y ? ? H c ? X ? ? ? p X ? x ? logg ?? x ?dx

例:设X是?-1,上满足均匀分布的随机变量, 1? 求H c ? X ?,H c X 3 ?1 ? p X ?x ? ? ? 2 ?0 ?

? ?

x ? ?? 1,1? 其他
?? ??

则:H c ? X ? ? ? p X ? x ? log p X ? x ?dx 1 1 ? ? log dx ?1 2 2
1

Hc X

? ? ? H ?X ? ? ?
3 c 1

??

??

p X ? x ? log 3 x 2 dx

? ?

1 1 2 ? 1 ? ? log 3 x dx ? 1 ? ? log 3 x 2 dx ?1 2 0 ? 1 ? log 3 ? 2 log e

? ?

? ?

概率计算公式

?条件概率与乘积公式?在事件B发生的条件下,
事件A发生的概率称为事件A在事件B已发生的 条件下的条件概率。记作P? A | B ?, 当P?B ? ? 0时 P? A ? B ? 规定P? A | B ? ? ,当P?B ? ? 0时, 规定 P ?B ? P? A | B ? ? 0。由此得出乘法公式: P? A ? B ? ? P?B ?P? A | B ? ? P ? A?P?B | A? ? P? An | A1 A2 ? An ?1 ?

P? A1 A2 ? An ? ? P? A1 ?P? A2 | A1 ?P? A3 | A2 A1 ??

概率计算公式

?独立性公式?如果事件A与B满足P? A | B ? ? P? A?
那么称事件A关于事件B是独立的。 独立性是相互的性质,及A关于B独立,B一定 关于A也独立,或称A与B相互独立。 P? A ? B ? ? P?B ?P? A? A与B相互独立的充分必要条件是:

概率计算公式

?全概率公式?如果事件组B , B ,?满足
1 2

?? ? Bi ? B j ? ? ?i ? j ?, P? ? Bi ? ? 1, ? i ?1 ? 则对任一事件A有 P? A? ? ? P? A | Bi ?P?Bi ?
i ?1 ?

P?Bi ? ? 0

如果Bi只有n个, 公式也成立。

概率计算公式

?贝叶斯公式?如果事件组B , B ,?满足
1 2

? ? Bi ? B j ? ? ?i ? j ?, P? ? Bi ? ? 1, ? i ?1 ? 则对任一事件A ?P? A? ? 0 ?,有
?

P?Bi ? ? 0

P?Bi | A? ?

? P?B ?P? A | B ?
i ?1 i i

?

P?Bi ?P? A | Bi ?

如果Bi只有n个, 公式也成立。

?伯努利公式?设一次试验中某事件A出现的
概率为p,则n次重复试验中事件A出现k次 的概率pn ,k 为 ?n? k n?k ?k ? 0,1,? , n ? pn ,k ? ? ? p ?1 ? p ? ?k ? ? ? ?n? 式中? ?为二项式系数, 当n和k都很大时, ?k ? ? ? 有近似公式:pn ,k 1 ? e ? 2?
x2 ? 2

概率计算公式

概率计算公式

?泊松公式?
?n? k n?k ?k ? 0,1,?, n ? pn ,k ? ? ? p ?1 ? p ? ?k ? ? ? 当n充分大,且p很小时, 有近似公式:pn ,k ? 式中? ? np

?k
k!

e ??

随机变量的数字特征(离散)
1.随机变量?的数学期望(均值)记作E?,它 描述了随机变量的取值中心。 2.随机变量?? ? E? ? 的数学期望称为?的方差,
2

记作D?。D?的平方根称为?的均方差(标准 方差),记作? ? D?,它描述了随机变量 的可能取值与均值的偏差的疏密程度。

随机变量的数字特征(连续)
若?是连续型的随机变量,其分布密度为p?x ?, E? ? ? xp?x ?dx ? ? xdF?x ?
?? ? ?? ? ?

?当积分绝对收敛时?,则 分布密度函数为F ?x ?。
D? ? ?

?x ? E? ? p?x ?dx ? ??? ?x ? E? ? dF ?x ? ??
2 2

?

随机变量的数字特征(连续)
若?是离散型的随机变量,其可能取值为xk k ? 1,2, ?,且p?? ? xk ? ? pk E? ? ? xk pk
k ?1 ? ?

?当级数绝对收敛时?,则
D? ? ? ? xk ? E? ? pk
2 k ?1

均值与方差的几个公式 2 2 1。D? ? E? ? ?E? ? 2。Ea ? a, Da ? a ?a为常数 ? 3。E ?c? ? ? cE? , D ?c? ? ? c 2 D? ?c为常数 ? 4。E ??? ? ? E?E? ? E ??? ? E? ??? ? E? ??
5。若?1 , ? 2 , ? , ? n 互为独立的n个随机变量,则 E ??1 ? ? 2 ? ? ? ? n ? ? E?1 ? E? 2 ? ? ? E? n D ??1 ? ? 2 ? ? ? ? n ? ?
i , j ?1

? E ???
n

i

? E? i ??? j ? E? j ?

?

均值与方差的几个公式
6。若?1 , ? 2 , ? , ? n 互为独立的n个随机变量,则 E ??1? 2 ?? n ? ? ?E?1 ??E? 2 ?? ?E? n ? D??1 ? ? 2 ? ? ? ? n ? ? D??1 ? ? D?? 2 ? ? ? ? D?? n ? 7。若?1 , ? 2 , ? , ? n互为独立的n个随机变量,且 E? k ? 0, D? k ? ? ?k ? 1,2, ? , n ?。则随机变量
2 n

1 ?= ? ? k的均值与方差分别为 n k ?1 E? ? 0 D? ?

?

2

n

契贝谢夫不等式
对任一给定的正整数?,有 P?? ? E? ? ? ? ? D?

?

2

随机向量的联合分布函数
如果?1 , ? 2 , ? , ? n是联系于同一组条件下的n个 ? 随机变量,则称? ??1 , ? 2 , ? , ? n ?为n维随机变量 或随机向量。 若x1 , x2 , ? , xn是n维实空间R 上的一点,则事件
n

?1 ? x1 , ? 2 ? x2 , ? , ? n ? xn的概率 F ? x1 , x2 , ? , xn ? ? p ??1 ? x1 , ? 2 ? x2 , ? , ? n ? xn ?
作为x1 , x2 , ? , xn的函数,称为随机向量 ? ? ??1 , ? 2 , ? , ? n ?的联合分布函数。

随机向量联合分布函数的边缘分布函数

设? k1 , ? k 2 , ? , ? k m 是??1 , ? 2 , ? , ? n ?中任意取出的m

?m ? n ?个分量构成的m维随机变量, 则称 ?? k , ? k ,?, ? k ?的联合分布函数为??1 , ? 2 ,?, ? n ?
1 2 m

的m维边缘分布函数,此时 Fk1k 2 ?k m xk1 , xk 2 , ? , xk m ? F ?, ? , xk1 , ? , ?, ? , xk 2 , ? , xk m , ? , ?

?

?

?

?

二维离散随机的边缘分布函数
设二维离散随机变量?? ,? ?,?和?的可能取值 的联合分布为P ?? ? x k ? ? y j ? ? pkj,则 两个一维边缘分布维 P ?? ? xk ? ? pk ? ? pkj P ?? ? y j ? ? p j ? ? pkj
k j

分别为xk ?k ? 1,2, ??和y j ? j ? 1,2, ??,又记?? ,? ?

?k ? 1,2,?? ? j ? 1,2,??

二维离散随机的边缘分布函数
则称P ?? ? xk | ? ? y j ? ? pkj p? j pkj pk ?

?p

j

? 0, j ? 1,2, ??

为? ? y j 条件下离散型随机变量?的条件分布 类似地P ?? ? y j | ? ? xk ? ?

? pk ? 0, k ? 1,2,??

如果??1 , ? 2 , ? , ? n ?的联合分布函数等于所有一维 的。即F ? x1 , x2 , ? , xn ? ? F1 ? x1 ?F2 ? x2 ?? Fn ? xn ? 边缘分布函数的乘积,称?1 , ? 2 , ? , ? n是相互独立

随机过程
对每个t ? T(T是某个固定的实数集),? ?t ? 是个随机变量,就把这样的随机变量族

?? ?t ?, t ? T ?称为随机过程。随机过程一次实验
的结果是定义在T上的函数,称为随机过程的 一次实现。 当参数t的变化范围T是个整数集合,则称

? ?t ?, t ? 0,?1,?2, ?为随机序列。 ?? 当T只包含一个或有限个元素, ?t ?, t ? T ?就是
概率论中研究过的随机变量或随机向量。

马尔可夫过程
若对于任意的n ? 1,2,? , 和任意t0 , t1 , ?, t n ? T (其中t0 ? t1 ? ? ? t n)以及任意的实数x,y, 等式 ? P?? ?t n ? ? y | ? ?t n ?1 ? ? x? P?? ?t n ? ? y | ? ?t n ?1 ? ? x, ? ?t n ? 2 ? ? xn ? 2 , ?, ? ?t0 ? ? x0 ?

?? ?t ?, t ? T ?是马尔可夫过程。

对所有的? ?t n ?1 ?, ? ?t n ? 2 ?, ?, ? ?t0 ?成立,则称

时齐马尔可夫过程 设?? ?t ?, t ? T ?是马尔可夫过程,若对于任意
的t1 ? T,t 2 ? T(t1 ? t 2),条件分布 ? F ?t 2 ? t1 , x, y ? F ?t1 , x ; t 2 , y ? ? P?? ?t 2 ? ? y | ? ?t1 ? ? x?

即条件分布F ?t1 , x; t 2 , y ?只依赖于t 2 ? t1 , x, y, 的马尔可夫过程。

则称?? ?t ?, t ? T ?是一个时齐(对时间齐次地)

平稳增量的随机过程
若对任意t1 , t 2 ? T和任意的h(t1 ? h, t 2 ? h ? T) 随机变量

? ?t 2 ? h ? ? ? ?t1 ? h ?与? ?t 2 ? ? ? ?t1 ?
具有平稳增量的随机过程。

遵从相同的概率分布,则称?? ?t ?,t ? T ?是

平稳过程
若对于n ? 1,2, ? , 任意t m ? T(m ? 1,2, ? , n) 及任意的?(t m ? ? ? T,m ? 1,2, ? , n)等式 ? P?? ?t1 ? ? ? ? x1 , ? , ? ?t n ? ? ? ? xn ? ? Ft1 ?? ,?,tn ?? ? x1 , ? , xn ? Ft1 ,?,tn ? x1 , ? , xn ? ? P?? ?t1 ? ? x1 , ? , ? ?t n ? ? xn ?

成立,则?? ?t ?,t ? T ?称是平稳过程(侠义的)

马尔可夫过程(转移概率)

?状态与状态转移概率?考虑一系列随机试验,其中
每次试验的结果如果出现可列个两两互斥事件E1 , E2 , ?中的一个而且仅出现一个,则称这些事件 状态Ei。用pi j ?t ,? ?表示“已知在时刻 t 系统处在状 的条件概率,称为pi j ?t ,? ?转移概率。 Ei i ? 1,2, ?)为状态。如果Ei出现,就称系统处在 (

态Ei的条件下,在时刻?(? ? t)系统处在状态E j ”

马尔可夫过程(转移概率) ?过程的无后效性与时齐性?
无后效性:若已知在时刻t0系统所处状态的条 件下,在时刻t0以后系统将到达状态的情况与 时刻t0以前系统所处的状态无关,则称过程为 无后效的。 时齐性:若转移概率pi j ?t ,? ?只与i, j ,? ? t有关, 则称过程为时齐的。记为 pi j ?? ? ? pi j ?t , t ? ? ?.

马尔可夫过程(马尔可夫链) ?马尔可夫链?马尔可夫链是时间与状态都是
离散的马尔可夫过程。 1 设在一系列随机试验下,系统的可能离散状 态为E0 , E1 , ?,如果对于任意两个正整数k , m, 任意整数0 ? j1 ? j2 ? ? ? jt ? m,等式
' ' ' ' P Em ? k | Em E 'jt ? E 'j2 E 'j1 ? P Em ? k | Em 。

?

? ?

?

' 都成立(Em 表示“第m次试验出现Em”的事件)

那么称这一随机试验列为马尔可夫链。

随机变量序列为马尔可夫链的定义
2。 ?? ?t ???n ? 0,1, ? ?为一随机变量序列,它 设 们中间的每一个都可能取值(相当于所处状 态Ei)xi i ? 1,2, ?)如果对于任意正整数k , m, ( , 任意整数0 ? j1 ? j2 ? ? ? jt ? m, 等式 ? P ?? m ? k ? xm ? k | ? m ? xm ? P ? m ? k ? xm ? k | ? m ? xm , ? jt ? x jt , ? , ? j1 ? x j1

?

?

成立,则称?? ?t ??为马尔可夫链。

随机变量序列为马尔可夫链的定义
马尔可夫链所刻画的随机试验序列,可以 直观地理解为要检测“将来”所处的状态 只要用“现在”已知的状态,而“过去” 的状态不起任何作用,这就是无后效性。 马尔可夫链,以至马尔可夫过程都是具有 无后效性的随机过程。

马尔可夫链的转移概率矩阵
如果在时刻m系统由状态Ei 经过一次转移 到达状态E j的概率和时刻m无关,那么就 可用pij 表示这个一次转移概率。显然

?p
j

ij

?1

?p

ij

? 0, i, j ? 0,1,2,??

转移概率pij 可排成一个转移概率矩阵

马尔可夫链的转移概率矩阵
转移概率pij 可排成一个转移概率矩阵 ? p00 p01 p02 ?? ?p ? P ? ? pij ? ? ? 10 p11 p12 ? ? ? ? ? ? ? ? ? ? 这是一个每一行元素之和为1的非负元素 的矩阵,称为马尔可夫链的一步转移矩阵。

马尔可夫链的转移概率矩阵
同样用pij 表示系统由状态Ei 经过n次转移而 到达E j的转移概率。同样定义马尔可夫链的
? n步转移矩阵:P ?n ? ? pijn ? 。由无后效性,得 ? ? ? pijn ? ? ? pirm ? prjn ? m ?。
r

?n ?

? ?

称为切普曼 ? 柯尔莫哥洛夫方程。 切普曼 ? 柯尔莫哥洛夫方程可以推出 P
?n ?

?P

n

信源综述
连续信源 随机序 列描述 的信源 离散平稳信源 离散信源 离散无记忆信 源的扩展信源 离散平稳有记 忆信源

离散非平稳信源:马尔可夫信源

信源
? 信源即信息的来源,它是信息论研究中的 主要组成部分。信源的输出在未接收到之 前是随机的,所以可以用随机变量,随机 序列或随机过程来描述。 ? 按照信源输出消息的方式不同,可用不同 的数学模型进行分类。

信源的数学模型及分类
? 信源作为一般信息系统中信息的来源,其内容非 常广泛,如通讯系统中传输的对象、信号处理系 统中信号的来源、测量系统中被测物理量的来源、 数据统计中原始数据的来源等。 ? 信源的输出被称作消息,消息一般是不能直接送 给信道传输的,消息需经过发送器的变换才能转 换成适合于信道传输的信号。例如播音员播送的 一段新闻,记者拍摄的一段录像,歌手演唱的一 首歌曲,都应该说是消息,而当信源的输出只被 看作是随时间变化的某一物理量 f ?t ? 或随时间、空 间位置变化的某一物理量 f ?x, y, t ? 时称为信号。

信源的分类
? 不同的信源输出的消息不同,可根据 消息的不同随机性质来对信源进行分 类: ? 有随机变量型 ? 随机序列型(基于某整数集合) ? 随机过程型(基于某实数集合)

随机变量-离散型
? 如果信源输出的是单个符号(或代码)的 消息,它们的符号集的取值是有限的或可 数的,则可用一维离散随机变量X来描述这 样的信源输出。称这样的信源为离散信源, 它的数学模型是离散概率空间:
x2 ? xK ? ? ? X ? ? x1 ? p?x ?? ? ? p?x ? p?x ? ? p?x ? ?? ? ? ? 1 2 K ? 其中p?xk ? ? 0是概率分布, ? p?xk ? ? 1
k

随机变量-连续型
? 如果信源输出的是单个符号(或代码)的消息, 但其可能出现的消息数是不可数的无限值,即输 出消息的符号集的取值是连续的,则可用一维连 续随机变量X来描述这样的信源输出。称这样的 信源为连续信源,它的数学模型是连续概率空间:
? X ? ? ?a, b ? ? ? p ?x ?? ? ? p ?x ?? ? X ? ? X ? 其中p X ?x ? ? 0是概率密度函数, ? p X ?x ? ? 1
b a

信源输出的消息由随机序列描述
? 很多实际信源输出的消息往往是由一系列符号序 列组成的,例如: ? 中文自然语言文字作为信源:从时间上看,中文 信源输出的消息是时间上离散的符号序列,其中 每个符号的出现是不确定的、随机的,并由此构 成了不同的中文消息。 ? 离散化的平面灰度图像信源:从XY平面上来看每 一幅画面是一系列离散的灰度值符号,而每一点 的符号(灰度值)又都是随机的,由此形成了不 同的图像消息。

随机序列描述的信源
? 上述这类信源输出的消息是按一定的概率 选取的符号序列,所以可以把这种信源输 出的消息看做时间上或空间上离散的一系 列随机变量,即为随机序列。这样,信源 的输出可用随机序列 X 1 , X 2 ,?, X N ,? 来描述, 随机序列实际上就是一种参数集为离散的 随机过程。

随机序列描述的信源
? 如果信源输出的随机序列 X 1 , X 2 ,?, X N ,? 中, 每个随机变量 X k 都是取值离散的离散型随 机变量,即每个随机变量 X k 的可能取值是 有限的或可数的,这样的信源称为离散信 源

随机序列描述的信源
? 如果信源输出的随机序列X 1 , X 2 ,?, X N ,?中,每个 随机变量 X k都是取值为连续的连续型随机变量, 即每个随机变量 X k 的可能取值是不可数的无限多 个值,这样的信源称为连续信源。 ? 语音信号?X ?t ??、热噪声信号 ?n?t ?? ,它们在时间上 取样离散化后的信源成为 X 1 , X 2 ,?, X N ,? 或 n1 , n2 ,?, nN ,? ,虽然在时间上是离散的,但每 个随机变量的取值都是连续的,所以它们是连续 信源。由于连续信源可以进一步离散化为离散信 源,因此我们着重讨论离散信源。

离散平稳信源
? 如果离散信源中描述信源输出消息的随机 序列是平稳的,即随机序列的各维概率分 布都与时间起点无关,也就是说任意两个 不同时刻随机序列的各维概率分布都相同, 这样的离散信源称为离散平稳信源。如果 离散信源中描述信源输出消息的随机序列 是非平稳的,这样的离散信源称为离散非 平稳信源。

离散无记忆信源(1)
? 在某些简单的离散平稳信源情况下,信源 先后发出的一个个符号彼此是统计独立的, ? X ? X1 X 2 ? X N 也就是说信源输出的随机序列 中,各 X k (k ? 1,2,?, N ) 随机变量 之间是无依赖的、统 计独立的,则随机序列的联合概率分布满 ? P?X ? ? P? X 1 X 2 ? X N ? ? P ? X 1 ?P2 ? X 2 ?? PN ? X N ? 足: 1 ? 因为信源是平稳的,根据平稳随机序列的 统计特性可知,各变量 X k 的一维概率分布都 相同,即 P1 ? X1 ? ? P2 ? X 2 ? ? ? ? PN ? X N ? ,则有 N ? P?X ? ? P? X 1 X 2 ? X N ? ? ? P? X k ?
k ?1

离散无记忆信源(2)
? 若不同时刻的随机变量又取值于同一符号 N 集 ?x1 , x2 ,?, xK ? ,则有 ? ?
? xi ? xi1 xi2 ? xiN

其中 i 是符号集的一维概率分布。 ? 由符号集 ?x1 , x2 ,?, xK ? 与概率分布 P?xk ??k ? 1,2,?, K ? 构成一个概率空间:
? X ? ? x1 ? p? x ?? ? ? p ? x ? ? ? ? 1 p ? x2 ? ? x2 ?

? ? 是随机序列的一个取值,而 P?x ?
P X ? xi ? P xi1 xi2 ? xiN ? ? P xik
k ?1
k

?

? ?

?

xK ? p? xK ?? ?

? 称由概率空间 ?X , p?x ?? 描述的信源 X 为离散无记忆 信源。离散无记忆信源在不同时刻发出的符号之 间是无依赖的、统计独立,即是独立随机序列。

离散无记忆信源X的N次扩展信源
? 离散无记忆信源 X 输出的随机序列所描述 的信源称为离散无记忆信源 X 的 N 次扩展信 源,它的数学模型是离散无记忆信源空间 的重空间,即
? x1 ?X ? ? ? ? ? ? ? ? p?x ? ? p? x ?? ? 1
N

? x2 ? ? p ? x2 ? ?

? xK N ? ? ? p ?xK N ??

? 其中

? xi ? xi1 xi2 ? xiN ?i1 , i2 ,?, iN ? 1,2,?, K ?

离散平稳有记忆信源与马尔可夫信源
? 表示有记忆信源要比表示无记忆信源困难的多, 对离散非平稳序列,需在随机序列的联合概率分 布中引入统计概率分布来说明它们之间的关系。 实际上信源发出的符号往往只与前若干符号的依 赖关系强,而与更前面的符号的依赖关系弱,为 此,可以限制随机序列的记忆长度。当记忆长度 为m+1时,称这种有记忆信源为m阶马尔可夫信 源。也就是信源每次发出的符号只与前m个符号 有关,与更前面的符号无关。

m阶马尔可夫信源
? 假设m阶马尔可夫信源输出的随机序列为 X 1 , X 2 ,?, X i , X i ?1 ,?, X N ? 在这序列的某 i 时刻的随机变量 X i 取什么符号只 与前m个随机变量 X i ?1 , X i ?2 ,?, X i ?m 取什么符号 有关,与其更前面的随机变量取什么符号都无关。 这样就可以用马尔可夫链来描述。设各时刻随机 变量的取值为 uk , uk ? X k , k ? 1,2,?, i ? 1, i, i ? 1,?, N ? 则描述随机序列中各随机变量之间的依赖关系的 条件概率为

p?ui | ui ?1ui ?2 ?ui ?m ?u1 ? ? p?ui | ui ?1ui ?2 ?ui ?m ?

时齐马尔可夫信源
? 已知m阶马尔可夫信源输出的随机序列中各 随机变量之间的依赖关系的条件概率为
p?ui | ui ?1ui ?2 ?ui ?m ?u1 ? ? p?ui | ui ?1ui ?2 ?ui ?m ?

? 如果上述条件概率与时间起点 i 无关,即信 源输出的符号序列可看成时齐马尔可夫链, 则此信源称为时齐马尔可夫信源。
? p?um | u1u2 ?um ?1 ? p?ui | ui ?1ui ?2 ?ui ?m ?u1 ? ? p?ui | ui ?1ui ?2 ?ui ? m ?

信源综述小结
连续信源 随机序 列描述 的信源 离散平稳信源 离散信源 离散无记忆信 源的扩展信源 离散平稳有记 忆信源

离散非平稳信源:马尔可夫信源

离散无记忆信源的扩展信源
? 离散无记忆信源是最简单,也是最基本的 一类信源,它可以用完备的离散型概率空 间来描述,即由符号集 ?x1 , x2 ,?, xK ? 与概率分 布 P?xk ??k ? 1,2,?, K ? 构成一个概率空间:
? X ? ? x1 ? p? x ?? ? ? p ? x ? ? ? ? 1 p ? x2 ? ? x2 ? xK ? p? xK ?? ?

? 因此这样的信源的信息可以用离散随机变 量X的熵来度量。

? 离散无记忆信源虽然简单,但实际信源输 出往往是时间或空间上一系列消息符号。 电报系统可以看成二进制信源,其信源输 出是一串0、1序列。因此该信源的数学模 型可以用 ? X ? ? ? 0 1 ? 其中 p ? 1 ? p
? p ? x ?? ? ? ?p ? p? ?

? 如果把信源输出的序列看成一组一组发出, 每两个二元数字组成一组,则此时信源的 数学模型如下,这是原信源的一个二次扩 展信源。 ? X ? ? 00 01 10 11 ?
? p? x ?? ? ? p 2 ? ? ? pp pp p2 ? ?

? 如果把每三个二元数字组成一组,可得三 次扩展信源。
? X ? ? 000 001 010 011 100 101 110 111 ? ? p? x ?? ? ? p 3 p 2 p p 2 p pp 2 p 2 p pp 2 pp 2 p 3 ? ? ? ? ?

? 定义。设离散无记忆信源为
? X ? ? x1 ? p? x ?? ? ? p? x ? ? ? ? 1 p ? x2 ? ? x2 ? xK ? K ? , ? p ? xk ? ? 1 p?xK ?? k ?1

? 定义信源X的N次扩展信源XN为具有KN个符 号的离散信源,其N重概率空间为
? x1 ?X ? ? ? ? ? ? ? ? p?x ? ? p? x ?? ? 1
N

? x2 ? ? p ? x2 ? ?

? xK N ? ? ? p ?xK N ??

? ? ? x2 ? xK N ? ? X ? ? x1 ? ? ? ? ? ? ? ? p ? x ? p ? x ? ? p ?x ?? 2 ? p ? x ?? ? 1 KN ? ? xi ? xi1 xi2 ? xiN , i1 , i2 , ? , iN ? 1,2, ? , K ,
N

则由X的无记忆性,有 ? p ? xi ? ? p xi1 xi2 ? xiN ? ? p xik
N k ?1 KN KN N

?

?

? ?
KN

? ? p?xi ? ? ?? p xik ? ?? p xik ? 1
N i ?1 i ?1 i ?1 i ?1 i ?1

? ?

? ?

定理:离散无记忆信源X的N次扩展信源 X 的熵等于信源X的熵的N倍,即
N

H X N ? NH ? X ?

? ?

设有一离散无记忆信源X , 其概率空间为 x x2 x3 ? ? X ? ? 1 ? p? x ?? ? ? 3 1 3 ? ? ? ? 8 4 8 ? ? ? 11 3 H ? X ? ? log 2 ? log 3 4 4 ? X 2 ? ? x1 x1 x1 x2 x1 x3 3 9 ? ? ??? 9 ? p? x ?? ? 64 32 64 ? 11 3 2 H X ? log 2 ? log 3 2 2

x2 x1 3 32

x2 x2 1 16

x2 x3 3 32

x3 x1 9 64

x3 x2 3 32

x3 x3 ? 9 ? ? 64 ?

? ?

离散平稳有记忆信源
? 离散空间的信源的输出是空间或时间的离 散符号序列,而且在序列中符号之间有依 赖关系,此时可用随机序列来描述信源发 出的消息,即 X 1 , X 2 ,?, X N ,? ,其中任一变 量 X k 都是离散随机变量,它表示 t ? k 时刻 所发出的符号。信源在 t ? k 时刻将要发出 什么样的符号决定于两个方面:

一般随机序列的描述
的概率分布p ?u k ?有关。一般情况下t不同时, 概率分布也不同,即p ?u k ? ? p ?u j ?. (2).与 t ? k 时刻以前信源发出的符号有关,即 与条件概率p ?u k | u k ?1u k ? 2 ??有关。同样在一般 情况下,它也是时间t ? k时间的函数,所以 p ?u k | u k ?1u k ? 2 ?? ? p ?u j | u j ?1u j ? 2 ?? (1).与信源在 t ? k 时刻随机变量 X k 的取值u k

一般随机序列不稳定,处理困难

离散平稳有记忆信源的数学定义(1)
? 平稳随机序列的概率分布与时间起点无关
定义:如果各维联合概率分布均与时间起点无关, 即当t ? k , t ? j(k , j为任意整数,且k ? j)时,满 足下列条件的离散信源称为N维离散平稳信源。 p?uk ? ? p ?u j ? p?uk , uk ?1 ? ? p ?u j , u j ?1 ? ? p?uk , uk ?1 , ? , uk ? N ? ? p ?u j , u j ?1 , ? , u j ? N ?

离散平稳有记忆信源的数学定义(2)
? 如果在N维离散平稳信源中,任一时刻发出 的符号与以前时刻发出的符号有关,则称 这样的信源为N维离散平稳有记忆信源。
因为联合概率与条件概率有以下关系: p?uk , uk ?1 ? ? p?uk ? p?uk+1 | uk ? ? p?uk , uk ?1 , uk ? 2 ? ? p?uk ? p?uk+1 | uk ? p?uk+2 | uk ?1uk ? p?uk , uk ?1 , ?, uk ? N ? ? p?uk ? p?uk+1 | uk ??

p?uk+N | uk ? N ?1 ?uk ?1uk ?

离散平稳有记忆信源的数学定义(3)
则对离散平稳有记忆信源来说: p?uk+1 | uk ? ? p ?u j+1 | u j ? p?uk+2 | uk ?1uk ? ? p ?u j+2 | u j ?1u j ??

p?uk+N | v k ? N ?1 ? uk ?1uk ? ? p ?u j+N | u j ? N ?1 ? u j ?1u j ? 即条件概率均与时间起点无关,只与关联长度N 有关,它表示平稳信源发出的平稳随机序列前后 的依赖关系与时间起点无关。

离散平稳有记忆信源的数学定义(4)
如果某时刻发出的符号与以前发出的N个符号 有关,那么任何时刻它们的依赖关系都是一样 的,即 p?uk+N | uk ? N ?1 ?uk ?1uk ? ? p?u j+N | u j ? N ?1 ?u j ?1u j ? ? p?u N | u N ?1 ?u1u0 ?

离散平稳有记忆信源的熵
? 离散平稳有记忆信源发出的各符号之间具 有统计关联关系,这种统计关联性可用信 源发出的一个符号序列的整体概率,即N个 符号的联合概率来反映有记忆信源的特征。 最简单的有记忆平稳信源是N=2的情况,即 二维平稳有记忆信源。 ? 设有一个单符号离散信源的概率空间为
? X ? ? x1 ? p ? x ?? ? ? p ? x ? ? ? ? 1 p ? x2 ? ? x2 ? xK ? ? , p ? xK ??

? p?x ? ? 1
k ?1 k

K

K xK ? ? p ? xk ? ? 1 ? , p? x2 ? ? p ? xK ?? k ?1 ? 则二维离散平稳有记忆信源X ? X 1 X 2的概率空间为 ? ? X ? ? x1 x1 x1 x2 ? xK xK ? ? ? ??? p? x1 x1 ? p ? x1 x2 ? ? p ? xK xK ?? ? ? p ? x ?? ?

? X ? ? x1 ? p ? x ?? ? ? p ? x ? ? ? ? 1

x2 ?

根据熵的定义,可得 K K ? H X ? H ? X 1 X 2 ? ? ??? p ?xk , x j ?log p ?xk , x j ?

? ?
K

其中p ?xk , x j ? ? p ? xk ? p ?x j | xk ? , k , j ? 1,2, ? , k

k ?1 j ?1

?? p?x , x ? ? 1
K k ?1 j ?1 k j

二维离散平稳有记忆信源熵的结论
H ? X 1 X 2 ?是X 1与X 2的联合熵,表示原先信源X 输出任意一对消息的熵,即描述信源X输出长 ? H ?X1 X 2 ? ? H ?X1 ? ? H ?X 2 | X1 ? ? H ?X1 X 2 ? ? H ?X1 ? ? H ?X 2 ? 若X 1和X 2都取值同一个概率空间X,则有 H ? X 1 ? ? H ? X 2 ? ? H ? X ?,所以H ? X 1 X 2 ? ? 2 H ? X ? 又? H ?X 2 | X1 ? ? H ?X 2 ? 度为2的序列平均不确定性或所含有的信息量。

x x2 x3 ? ? X ? ? 1 设单符号离散信源为表? ? ? ? 11 4 1 ? ? p? x ?? ? 36 9 4 ? ? ? 则二维联合分布为表 ,条件分布为表2所示: 1 y1 表1: y2 y3 x1 1 4 1 18 0 x2 1 18 1 3 1 18 x3 0 y1 1 ,表2: y2 18 1 y3 36 x1 9 11 2 11 0 x2 1 8 3 4 1 8 x3 0 2 9 7 9

p ?xk y j ?

p ?y j | xk ?

H ? X ? ? ?? p ? xk ? log p ? xk ? ? 1.542 (比特 / 符号) H ?X 2 | X1 ?
3 3 k ?1 j ?1 k ?1

3

? ??? p ? xk ? p ?x j | xk ?log p ?x j | xk ? ? 0.870 显然H ? X 2 | X 1 ? ? H ? X ?,这正是由于前后符号 之间的依赖关系造成的,又 ? H X ? H ?X1 X 2 ? ? H ?X1 ? ? H ?X 2 | X1 ?

? H ? X ? ? H ? X 2 | X 1 ? ? 2.412 (比特 / 符号) ? 所以H X ? 2 H ? X ?

? ?

? ?

N维离散平稳有记忆信源
设单符号离散信源的概率空间为: p ? x2 ? ? k ?1 ? 发出的符号序列为X ? X 1 X 2 ? X N , 假设信源符号之
k

? X ? ? x1 ? p ? x ?? ? ? p ? x ? ? ? ? 1

x2 ?

xK ? ? , p ? xK ??

? p?x ? ? 1

K

间的依赖长度为N,并已知各维概率分布满足完备性 则N维离散平稳信源的联合熵为 ? H X ? H ?X1 X 2 ? X N ?

? ?
K

? ?? ? ? p X k1 X k 2 ? X k N log p X k1 X k 2 ? X k N
k1 ?1 k N ?1

K

?

?

?

?

N维离散平稳有记忆信源
定义:称长为N的信源符号序列中平均每个信源 符号所携带的信息量 ? 1 H N X ? H ? X 1 X 2 ? X N ?为平均符号熵。 N 因为信源符号之间的依赖关系长度为N,所以

? ?

可以求出已知前面N ? 1的符号时,后面出现一 个符号的平均不确定性,即用条件熵 H ? X N | X 1 X 2 ? X N-1 ? ? ?? ? ? p X k1 X k2 ? X k N log p X k N | X k1 X k 2 ? X k N ?1
k1 ?1 k N ?1 K K

?

?

?

?

离散平稳有记忆信源的极限熵
? 对于离散平稳有记忆信源,当H(X)<∞时, 有以下性质:
性质1。条件熵H ? X N | X 1 X 2 ? X N ?1 ?随N的增加而 单调不增。即 ? H ? X N ? 2 | X 1 X 2 ? X N ?3 ? ? ? H ? X N | X 1 X 2 ? X N ?1 ? ? H ? X N ?1 | X 1 X 2 ? X N ? 2 ?

证明时使用熵性质:H ? X | Y ? ? H ? X ?

? H ?X 3 | X1 X 2 ? ? H ?X 2 | X1 ? ? H ?X1 ?

离散平稳有记忆信源的极限熵
性质2。N给定时平均符号熵大于等于条件熵, ? 即:H N X ? H ? X N | X 1 X 2 ? X N ?1 ? ? 证明时由NH N X ? H ? X 1 X 2 ? X N ?展开后利用

? ?

? ?

性质1即可得。 性质3。平均符号熵H N ? ? 即:H N X ? H N-1 X

? ?

? ?

? ?

? X 随N增加单调不增。

离散平稳有记忆信源的极限熵
性质4。 H N lim N ?? ? lim H N X = lim H ? X N | X 1 X 2 ? X N ?1 ?
N ??

? ?

? ?

? X 存在,并且

N ??

证明:因为 ? ? ? 0 ? H N X ? H N-1 X ? H N-2 X ? ? ? ? H1 X ? H ? X ? ? ? ? 故 lim H N X 存在,且为零和H ? X ?之间的某
N ??

? ? ? ? ? ?

? ?

? ?

一值。

离散平稳有记忆信源的极限熵
定义:称H ? ? lim H N
N ??

? ?

? X = lim H ? X N | X 1 X 2 ? X N ?1 ?
N ??

为离散平稳有记忆信源的极限熵或极限信息量或熵 速率。 定理:当离散平稳信源的记忆长度为m ? 1时,即信 源在某时刻发出什么符号只与前m个符号有关,则 ? H ? ? lim H N X = lim H ? X N | X 1 X 2 ? X N ?1 ? ? H ? X m ?1 | X 1 X 2 ? X m ? 特别对离散无记忆信源,由以上定理显然有 H ? ? H ?X ?
N ??

? ?

N ??

马尔可夫信源
? 若信源输出的符号序列和信源所处的状态满足下 列两个条件: 1.某一时刻信源符号的输出只与此刻信源所处状态 有关,而与以前的状态及以前的输出符号都无关: 即 时间 t
p X t ? ak | St ? Ei , X t ?1 ? ak1 , St ?1 ? E j , ? ? p? X t ? ak | St ? Ei ? 符号 状态

?

?

当具有时齐性时,有
p? X t ? ak | St ? Ei ? ? p?ak | Ei ?, 与时间无关

? p?a
k ?1

K

k

| Ei ? ? 1

马尔可夫信源
2.信源在某 t 时刻所处的状态由当前的输出符号和 前一时刻 t-1 信源的状态唯一决定:即 ? 0 p?St ? Ei | X t ? ak , St ?1 ? Ei ? ? ? ? 1 则此信源称为马尔可夫信源。

举例说明这些概率及状态转移图
设信源符号X ? A?a1 , a2 , a3 ? ,信源所处的状态 况由图表示
a3 :
E2

S ? E?E1 , E2 , E3 , E4 , E5 ? ,各状态之间的转移情
1 a2 : 2 1 a2 : 4
E1

1 2
E3

1 a3 : 4

a2 :

3 4 1 a1 : 4
E5

1 a1 : 2

满足? p?ak | Ei ? ? 1
k ?1

3

a3 :

1 4

a1 : 1
E4

1 a2 : 4

1 a3 : 2

1.各状态下发符号的概率分别为 2. 且有

p ?a1 | E1 ? ? 0.5, p ?a2 | E2 ? ? 0.5, ? , p ?a1 | E5 ? ? 0.25 p ?S t ? E2 | X t ? a1 , S t ?1 ? E1 ? ? 0 p ?S t ? E1 | X t ? a1 , S t ?1 ? E1 ? ? 1 p ?S t ? E2 | X t ? a2 , S t ?1 ? E1 ? ? 1

p ?S t ? E2 | X t ? a3 , S t ?1 ? E1 ? ? 0 ? 3. 各状态的一步转移概率分别为 p ?E1 | E1 ? ? 0.5, p ?E2 | E2 ? ? 0.5, p ?E3 | E3 ? ? 0.25, p ?E2 | E1 ? ? 0.25, 其余p ?E j | Ei ? ? 0 由此可见此信源满足(1), (2)和(**),所以此信源 是马尔可夫信源,并且是时齐的马尔可夫信源

定义:m阶有记忆离散信源的数学模型可由一组 信源符号集?x1 , x2 , ? , xK ?和一组条件概率 p xk m?1 | xk1 xk 2 ? xk m , k1 , k 2 , ? k m , k m ?1 ? 1,2, ? , K 确定,并满足
k m?1 ?1

?

?

? p?x
K

k m?1

| xk1 xk 2 ? xk m ? 1

?

则称此信源为m阶马尔可夫信源。当m ? 1时,即 任何时刻信源符号发生的概率只与前面一个符号 有关,则称为一阶马尔可夫信源。

例:设有一个二进制一阶马尔可夫信源,其信源 符号集为?0,,条件概率为 1? p?0 | 0? ? 0.25, p?0 | 1? ? 0.5, p?1 | 0? ? 0.75, p?1 | 1? ? 0.5
1: 0.75 0 : 0.25
E1 E2

若记忆信源的状态E1 ? 0, E2 ? 1, 则信源的状态转移图

1 : 0.5

0 : 0.5

1.各状态下发符号的概率分别为

p ?0 | E1 ? ? 0.25, p ?1 | E1 ? ? 0.75, p ?0 | E2 ? ? 0.5, p?1 | E2 ? ? 0.5 p ?E1 | E1 ? ? 0.25, p ?E2 | E1 ? ? 0.75, p ?E1 | E2 ? ? 0.5, p ?E2 | E2 ? ? 0.5

2. 各状态的一步转移概率分别为

设有一个二元二阶马尔可夫信源,其信源符号集为

?0,,条件概率为 1? p?0 | 00 ? ? p?1 | 11? ? 0.8, p?1 | 00 ? ? p?0 | 11? ? 0.2, p?0 | 01? ? p?0 | 10 ? ? p?1 | 01? ? p?1 | 10 ? ? 0.5
这个信源有2 =4个可能状态
2

E1 ? 00, E2 ? 01, E3 ? 10, E4 ? 11。
E2

0 : 0.8
E1

1 : 0.2

0 : 0.5
E3

0 : 0.5 1 : 0.5

1 : 0.5
E4

0 : 0.2 1 : 0.8

如果信源原来的状态为E1 ? 00,则下一个状态 只可能转移到00或01状态,而不会转移到 或 10 11状态。同理可分析初始状态为其他状态时的 状态转移过程。 各状态下发符号 的概率分别为: p ?0 | E1 ? ? 0.8 p ?1 | E1 ? ? 0.2 ? 状态的一步转移概率为 p ?E1 | E1 ? ? 0.8, ?
E2

0 : 0.8
E1

1 : 0.2

0 : 0.5
E3

0 : 0.5 1 : 0.5

1 : 0.5
E4

0 : 0.2 1 : 0.8

E1 ? 00, E2 ? 01, E3 ? 10, E4 ? 11。

马尔可夫信源熵的计算
? 一般的马尔可夫信源输出的消息是非平稳的随机 序列,它们的各维概率分布随时间的推移可能会 改变,但马尔可夫信源输出的符号序列中符号之 间是有依赖的,而且依赖关系也是无限的。若信 源的起始状态不同,信源发出的符号序列亦不相 同,某时刻信源输出什么符号,不但与前一时刻 信源所处的状态和所发出的符号有关,而且一直 延续到与信源初始所处的状态和所发的符号有关。 因此,一般马尔可夫信源的熵应该是其平均符号 1 熵的极限值,即 H ? ? lim H ? X 1 X 2 ? X N ? N ?? N ? 这一极限很难计算,但可通过以下定理计算

定理:设马尔可夫信源所处的状态为S ? E?E1 , E2 , ? , E J ?, 的随机序列为X 1 , X 2 , ? , X N , ? , 信源所处的状态序列为 S1 , S 2 , ? , S N , ? , 则该马尔可夫信源的熵
J 1 H ? ? lim H ? X 1 X 2 ? X N ? ? ? q? ?E j ?H ?X | S ? E j ? N ?? N j ?1

在每一状态下可能输出的符号X ? ?x1 , x2 , ? , xK ?, 信源输出

1 其中q? ?E j ? ? lim N ?? N
K k ?1

? p?S
N l ?1

l

? Ej ?

? H ?X | S ? E j ? ? ?? p ?xk | E j ?log p ?xk | E j 【证明推导】

? 0 ? H ?S | X 1 X 2 ? X N ? ? H ?S ? ? log J ? 0 ? H ?S ? ? H ?S | X 1 X 2 ? X N ? ? log J 则H ? ? lim 1 H ?X1 X 2 ? X N ? N ?? N

? H ?S ? ? H ? X 1 X 2 ? X N | S ? ? H ?S | X 1 X 2 ? X N ?

H ? X 1 X 2 ? X N ? ? H ? X 1 X 2 ? X N S ? ? H ?S | X 1 X 2 ? X N ?
? H ? XY ? ? H ? X ? ? H ?Y | X ?

有界

1 1 ? lim ?H ?S ? ? H ?S | X 1 X 2 ? X N ?? ? lim H ? X 1 X 2 ? X N | S ? N ?? N N ?? N 1 ? lim H ? X 1 X 2 ? X N | S ? 当N ? ?时趋向于零 N ?? N 1 ? lim ?H ? X 1 | S ? ? H ? X 2 | X 1S ? ? ? ? H ? X N | X 1 X 2 ? X N ?1S ?? N ?? N 1 N ? lim ? H ? X l | X 1 X 2 ? X l ?1S ? 熵的链规则 N ?? N l ?1

设初始时刻状态为S1 ? Ei , 则H ? X l | X 1 X 2 ? X l ?1 , S1 ? Ei ? ? ? ? ? ? ? p xk1 xk 2 ? xkl | S1 ? Ei
k1 ?1 k 2 ?1 K K K

?

?

? log p xkl | xk1 xk 2 ? xkl ?1 , S1 ? Ei

?

k l ?1

?

由马尔可夫信源的性质可知: 1 , xk1 ) ? S 2 , ( S1 , xk1 xk 2 ) ? S 3 (S ( S1 , xk1 xk 2 ? xkl ?1 ) ? S l:表示初始状态S1 ? Ei时,输出 xk1 xk 2 ? xkl ?1 xkl 序列后,状态变为S l , 于是有 p xk1 xk 2 ? xkl | S1 ? Ei ? p xk1 xk 2 ? xkl , S l | S1 ? Ei xk 2 ? xkl ?1 , S l | S1

? ? p ?x

?

? ?

? p xk1 xk 2 ? xkl ?1 , S l | S1 ? Ei p xkl | xk1 xk 2 ? xkl ?1 , S l S1 ? Ei
k1

又 ? p xkl | xk1 xk 2 ? xkl ?1

?

?? ? E ? p ?x | S ? , S ? E ? ? p ?x
i kl l 1 i

?

?

kl

| Sl

?

因此 H ? X l | X 1 X 2 ? X l ?1 , S1 ? Ei ? ??
J

? ? ? ? p?x
K K K k1 ?1 k 2 ?1 k l ?1

k1

xk 2 ? xkl | S1 ? Ei p xkl | S l log p xkl | S l j ? kl

??

?

?

?

? ? p ?S l ? E j | S1 ? Ei ?H ?X l | S l ? E j ?
j ?1

对任意给定的S1的概率分布都可得到相应的S l的概率分布, 所以对上式中的S1取平均即可得 H ? X l | X 1 X 2 ? X l ?1S ? ? ? p ?S l ? E j ?H ?X l | S l ? E j ?
J j ?1

? ? p ?S ? E j ?H ?X | S ? E j ?
J j ?1

因此 1 H ? ? lim N ?? N 1 ? lim N ?? N
J N

? H ?X
l ?1 J l

N

l

| X 1 X 2 ? X l ?1S ?

?? p?S
l ?1 j ?1 N

? E j ?H ?X | S ? E j ?

1 ? ? ? ? lim N ?? N j ?1 ?
J j ?1

? ? p?Sl ? E j ?? H ?X | S ? E j ? l ?1 ?
表示当N ? ?时,每一个状态E j出现的概率
对一般的马尔可夫信源,q∞与 初始状态概率分布有关,但仍 然很难计算,在实际应用中, 许多马尔可夫信源的状态序列 往往是遍历的马尔可夫链,因 此定理可以简化

? ? q? ?E j ?H ?X | S ? E j ? 1 其中q? ?E j ? ? lim N ?? N
N

? p?S
l ?1

l

? Ej ?

定义:设随机序列S1 , S 2 , ? , S N , ?是齐次马尔可夫 链,状态集S ? E?E1 , E2 , ? , E J ?, 在时刻m从状态Ei p?S m ? n ? E j | S m ? Ei ? 经过n步转移后处于状态E j的概率 称为n步转移概率。由于马尔可夫链是齐次的,这个
? 概率与m无关,记为pijn ? ? n ? 1, 就是一步转移概率:pij1? ? pij ? p ?E j | Ei ?

? 由所有n步转移概率pijn ?为元素组成的矩阵 ? P ?n ? ? pijn ? 称为n步转移矩阵

? ?

对n步转移矩阵规定 P
?0 ?

? pij ,其中pij

? ?
?0 ?

?0 ?

? P ?1? ? pij1? ? pij

? ? ? ?
J k ?1

?1 当i ? j ?? ?0 当i ? j

n步转移概率满足下面的切普曼 ? 柯尔莫哥洛夫方程
? ? ? pijm ? n ? ? ? pikn ? pkjm ?

由此可用一步转移概率计算多步概率,如果用转移 矩阵表示P
?n ? m ?

? P P 特别P

?n ? ?m ?

?n ?

? P

? ?
?1?

n

定义:设随机序列S1 , S 2 , ? , S N , ?是齐次马尔可夫 链,状态集S ? E?E1 , E2 , ? , E J ?, 若对一切Ei , E j ? E 存在不依赖于Ei的常数p?Ei ?, 使得
n ??

? lim pijn ? ? p ?E j ?, 称此马尔可夫链具有遍历性。

由随机过程理论可知,当马尔可夫链具有遍历性 上式中的p ?E j ?满足
J j ?1 J j i j

? p?E ?p?E | E ? ? p?E ?, i ? 1,2,?, J
i

? p?Ei ? ? 1
j ?1

稳定的

初始状态可以任意,但转 移步骤n足够大以后,转 移概率与初始状态无关, 状态出现的概率已达到一 种稳定分布

定理:设马尔可夫信源所处的状态为S ? E?E1 , E2 , ? , E J ?, 在每一状态下可能输出的符号X ? ?x1 , x2 , ? , xK ?, 如果该 马尔可夫信源所处的状态序列是遍历的, 则这样的马尔可 夫信源的熵 H ? ? ? p ?E j ?H ?X | S ? E j ?
J j ?1

其中H ?X | S ? E j ? ? ?? p ?xk | E j ?log p ?xk | E j ?
K k ?1

p ?E j ?满足? p ?E j ? p ?Ei | E j ? ? p ?Ei ?, i ? 1,2, ? , J
J j ?1

与? p ?Ei ? ? 1
j ?1

J

回到上一个结论,即
J 1 H ? ? lim H ? X 1 X 2 ? X N ? ? ? q? ?E j ?H ?X | S ? E j ? N ?? N j ?1

1 其中q? ?E j ? ? lim N ?? N 1 ? lim N ?? N 1 ? lim N ?? N 因此 1 lim N ?? N
N

? p?S
N l ?1

l

? Ej ?

?? p?S
l ?1 j ?1 N J

N

J

1

? Ei ? p ?S l ? E j | S1 ? Ei ? ? Ei ? pij
?l ?1?

?? p?S
l ?1 j ?1 J

1

? p ?S1 ? Ei ? pijl ?1? ? ? p ?S1 ? Ei ? p ?E j ? ? p ?E j ? ??
J l ?1 j ?1 j ?1

定理:设状态序列S1 , S 2 ,?, S N 是齐次马尔可 夫链,若存在正整数n0 , 使一切Ei , E j ? E , 都 有pij
?n0 ?

? 0, 则此马尔可夫链是遍历的。

考虑两个状态的Mark ov 链,具有概率转移矩阵

? ? ?1 ? ? P? ?, p?E1 | E1 ? ? 1 ? ? , p?E2 | E1 ? ? ? , 1? ? ? ? ? p?E1 | E2 ? ? ? , p?E2 | E2 ? ? 1 ? ?。
我们用一个向量?表示平稳分布,?由状态0和 状态1的平稳概率组成:? ? ? ??1 , ? 2 ?,求解

? ? ?1 ? ? ? ? ?P ? ? , 可得到??1 , ? 2 ?? ? ??1 , ? 2 ? ?1 ? 。 , ?2 ? ? 1? ? ? ? ?? ? ?? ? ? 如果mark ov链满足平稳分布,则随机过程将是平稳的,因此,
? ? ? 在时间n,状态X n的熵为H ? X n ? ? H ? ?? ? ? ,? ? ? ? ?
1??
E1 E2

? ? ? ?
1? ?

?

考虑两个状态的Mark ov 链,具有概率转移矩阵 ?2 ?? p ?E j ? p ?Ei | E j ? ? p ?Ei ? ?0.25 0.75 ? ? j ?1 2 3 P? ,? : 解得p ?E1 ? ? , p ?E2 ? ? 0 .5 0 .5 ? ? 2 5 5 ? ? p ?Ei ? ? 1 ?? ? i ?1 H ? X | S ? E1 ? ? ?? p ? xk | E1 ? log p ? xk | E1 ? ? 0.811
k ?1 2 2

H ? X | S ? E2 ? ? ?? p ? xk | E2 ? log p ? xk | E2 ? ? 1
k ?1

所以 H?

?E ?H ?X | S ? E ? ? 2 ? 0.811 ? 3 ?1 ? 0.9244 ??p
2 j ?1 j j

5

5

0? ? 0 .8 0 .2 0 ?0.64 0.16 0.1 0.1 ? ?0 ?0.25 0.25 0.1 0.4 ? 0 0 .5 0 .5 ? ? 2 ? ?, P ? P ?1? 2 ? ? ? P ?1? ? ? ? 0 .5 0 . 5 0 ? 0.4 0.1 0.25 0.25 ? 0? ? ? ? ? 0 0 0 . 2 0 .8 ? 0.1 0.1 0.16 0.64 ? ? ?

? ?

?2 ?? p ?E j ? p ?Ei | E j ? ? p ?Ei ? ? j ?1 : ?2 ? p ?E ? ? 1 0 : 0.8 i ?? ? i ?1 5 1 1 : 0.2 解得p ?E1 ? ? , p ?E2 ? ? , 14 7 E2 1 5 p ? E3 ? ? , p ? E 4 ? ? 7 14 1 : 0.5

E1

0 : 0.5
E3

0 : 0.5 1 : 0.5 0 : 0.2
E4

1 : 0.8

H ? X | S ? E1 ? ? ?? p? xk | E1 ? log p? xk | E1 ? ? 0.722
k ?1 4

4

H ? X | S ? E2 ? ? ?? p ? xk | E2 ? log p? xk | E2 ? ? 1
k ?1 4

H ? X | S ? E3 ? ? ?? p ? xk | E3 ? log p ? xk | E3 ? ? 1
k ?1 4

H ? X | S ? E4 ? ? ?? p ? xk | E4 ? log p? xk | E4 ? ? 0.722
k ?1

所以 H ? ? ? p ?E j ?H ?X | S ? E j ? ? 0.801
4 j ?1

例:一个二元二阶Mark ov 信源: p ? xn ?1 | xn xn ?1 ? ?

x ? A?0,1? 。信源开始时以概率p? x1 ? : p?0? ? p ?1? ? 0.5

发出随机变量x1后,下一个单位时间输出的随机变 表示。再下一个单位时间输出的随机变量x3与x1 x2

量x2与x1有依赖关系,依赖关系由条件概率p? x2 | x1 ? 有依赖关系,依赖关系由条件概率p? x3 | x2 x1 ?表示

p?x2 | x1 ?

x2
0 1

x1
0 1 0.3 0.4 0.7 0.6

p?x3 | x2 x1 ?

x3
0

x2 x1
00 01 10 11 0.4 0.2 0.3 0.4

1

0.6 0.8 0.7 0.6

从第四个单位时间开始,任一时刻信源发出 的随机变量xi只与前面两个单位时间的随机 变量xi ? 2 xi ?1有依赖关系,即 p ? xi | xi ?1 xi ? 2 ? x1 ? ? p ? xi | xi ?1 xi ? 2 ?

而且p ? xi | xi ?1 xi ? 2 ?=p ? x3 | x2 x1 ?。 符号0和1的概率分布。

求该Mark ov 信源的熵及当信源达到稳定后, 解:根据题意,该信源有7个状态: S ? E?E0 , E1 , E2 , E3 , E4 , E5 , E6 ?

图A

0 : 0.4 E3 ? 00 0 : 0.3 1 : 0.6 E1 ? 0 0 : 0.2 1 : 0.7 E4 ? 01 0 : 0.5 1 : 0.8 E0 0 : 0.3 1 : 0.5 0 : 0.4 E5 ? 10 1 : 0.7 E2 ? 1 1 : 0.6 0 : 0.4 E6 ? 11 1 : 0.6

E3 ? 00

当信源发完第三个 符号以后,根据表 达式p ? x3 | x2 x1 ?以及 ? p ? x3 | x2 x1 ? p ? xi | xi ?1 xi ? 2 ?

E4 ? 01
E5 ? 10

E6 ? 11
E3 ? 00

可知从第三个单位 时间以后,信源必 处在E3 , E4 , E5 , E6四 种状态之一,即在 i ? 3以后信源的状 态转移可用图

E4 ? 01
E5 ? 10

E6 ? 11

图A
0 : 0.3
E1 ? 0 1 : 0.7

0 : 0.4
E3 ? 00

E0 , E1 , E2
为过渡状态

1 : 0.6
E4 ? 01

0 : 0.5
E0

0 : 0.3

E3 , E4 , E5 , E6
为稳定状态

0 : 0.2 0 : 0.4 E2 ? 1 1 : 0.6

1 : 0.7
E5 ? 10

1 : 0.5

0 : 0.4
E6 ? 11

1 : 0.8

1 : 0.6

图B

E5
10

0 : 0.3 0 : 0.2

E3
00

0 : 0.4

前后 E3 E4 E5 E6
E3 0.4 0.6 0 0 0.3 0.7 0 0 0 0 E4 E5 0.2 0.8

0 : 0.4

1 : 0.6 1 : 0.7
01

11

E6

0

0

0.4 0.6

1 : 0.6

E6

1 : 0.8

E4
? 2?

由于 P

? 2?

? P

则该信源是遍历的

? ?
?1?

E3

E4

E5

E6

2

,且 Pij

?0

E3 E4 E5 E6

0.16 0.24 0.12 0.48 0.06 0.14 0.32 0.48 0.12 0.18 0.14 0.56 0.12 0.28 0.24 0.36

解2:设平稳分布? ? ??3 , ? 4 , ?5 , ? 6 ?,则由平稳 分布条件得到: ?0.4 ?0 ??3 , ? 4 , ?5 , ?6 ?? ?0.3 ? ?0 1 则?3 ? , ?4 9 0? ? 0 0.2 0.8? ? ??3 , ? 4 , ?5 , ? 6 ? 0.7 0 0? ? 0 0.4 0.6? 2 4 ? ?5 ? , ?6 ? 9 9 0.6 0

?

解3:H ? ? ??? ?i pij log pij ? ?3 H ?0.4,0.6 ? ? ? 4 H ?0.2,0.8? ? ?5 H ?0.3,0.7 ? ? ? 6 H ?0.4,0.6 ? ? 0.8956 ?比特 / 符号? 解4:当Mark ov 信源达到稳定后,符号0和1的概率 分布可根据以下方式计算p?ak ? ? ? ?i p?ak | Ei ?
i ?1 J i ?3 j ?1

6

2

1 p?0 ? ? 0.4 ?3 ? 0.2 ? 4 ? 0.3?5 ? 0.4 ? 6 ? 3 2 p?1? ? 0.6 ?3 ? 0.8? 4 ? 0.7 ?5 ? 0.6 ? 6 ? 3

可见,信源达到稳定状态后,信源符号的概 率分布与初始时刻的符号概率分布是不同 的,平稳信源必须知道信源的各维概率分 布,而m阶Markov信源只要知道与前m个符 号有关的条件概率,就可以计算出信源的 信息熵,所以一般信源可以用m阶Markov 信源来近似。

我们在前面讨论了各类离散信源及其信息熵 1.我们给出了一个随机过程?xi ? 的熵率的定义: 1 H ? X ? ? lim H ? X 1 X 2 ? X n ?,当极限存在。 n ?? n 2.我们又定义了一个熵率的相关量: H ?? X ? ? lim H ? X n | X n ?1 X n ? 2 ? X 1 ?,当极限存在。 3.对于平稳的随机过程,我们证明了:H ? X ? ? H ?? X ? 5.已知不等式成立:H ? X 2 | X 1 ? ? H ? X 2 ?
n ??

4.一个平稳Mark ov 的熵率为H ? X ? ? H ?? X ? ? H ? X 2 | X 1 ?

6.由熵的极值性,在离散信源情况下,信源各符号等 概率分布时,其熵值最大,即H ? X ? ? H ? p1 , p2 , ?, p N ? ? log N

于是我们往往这样考虑和处理问题: 1.非平稳信源H ? X ?不一定存在,于是考虑用平稳 信源H ? X ?来逼近非平稳信源。 2.H ? X ?求解困难,于是考虑用m阶Mark ov 信源的 H ?? X ?来近似平稳信源的H ? X ?,特别在m ? 1时, H m ?1 ? H 2 ? H ? X 2 | X 1 ?。

3.可假设信源为无记忆信源,而信源符号有一定 的概率分布,这时可用信源的平均信息量 H1 ? H ? X ?来近似。 4.最后,则可以假定是等概率分布的离散无记忆 信源,用最大熵H 0 ? log X 来近似。

因此,对于一般信源都可以近似地用不同记忆长度的 Mark ov 信源来逼近,我们以证明了条件熵随N的增加 是非递增的结论: 即:H ? X N | X 1 X 2 ? X N ?1 ? ? H ? X N ?1 | X 1 X 2 ? X N ? 2 ? ? H ? X N ? 2 | X 1 X 2 ? X N ?3 ? ? ? ? H ? X 3 | X 1 X 2 ? ? H ?X 2 | X1 ? ? H ?X1 ? 我们又有: log X ? H 0 ? H1 ? H 2 ? ? ? H m ? H m ?1 ? ? ? H ? X ? 由此可见:由于信源符号间的依赖关系使信源的熵 减小。如果它们的前后依赖关系越长,则信源的熵 越小,并且仅当信源符号间彼此无依赖且等概率分 布时,信源熵才最大。

也就是说:信源符号之间的依赖关系越强,每个符 号提供的平均信息量就越小。每个符号提供的平均 信息量随着符号间的依赖关系长度的增加而减少。 为此我们引进信源的剩余度来衡量信源的相关性程 度(多余度)。

信息剩余度与自然语言的熵
H ( X ) H? 熵的相对率:?= ? log | X | H 0 H? 熵的剩余率:? =1-?=1- H0 1 H ? ( X ) ? lim H ( x1 x2 ...xn ) n ?? n ????? lim H ( xn | xn ?1 xn ? 2 ...x1 ) ? H ?( X ) ? 相对平稳过程
n ??

log | X |? H 0 ? H1 ? H 2 ... ? H ?

信源剩余度 ? 的大小能很好的反映离散信源输出 的符号序列中符号之间的依赖关系的强弱:

? H ? 信源符号间依赖关系 符号间记忆长度
大小 小大 0 H0 强 弱 无 长 短 0

人类自然语言等都是由一组符号的集合构成的 信源。在自然语言的序列中,符号之间是有关 联的,它们都可以用Mark ov 信源来逼近。

英文信息相关的例子: 1.以英文组成的信源为例,信源的输出是由英文字母组

?A 成的序列: , B, ? , Z ? ,所以由英文组成的信源的最大熵
H 0 ? log 27 ? 4.76 (比特 / 符号) 2.但实际上,用英文组成单词,再由单词组成文章时, 英文字母并非等概率出现,而且英文字母之间有严格 的依赖关系,如果我们先做第一级近似,只考虑英文 书写中各字母出现的概率,不考虑字母之间的依赖关 系,由此可得到第一级近似为无记忆信源熵 H1 ? ?? pi log pi ? 4.03 (比特 / 符号)
i ?1 27

由此我们随机的选择英文字母排列起来,可得到 第一级近似信源输出的一个典型的字母序列: AI , NGAE, NNR, ASAEV , ? 它们有一点象英文,但并非是英文的排列,因为 字母之间并没有组成有意义的单词,更谈不上单 词之间组成有意义的句子。考察英文的结构得知 要组成有意义的单词,英文字母的前后是有依赖 的,当前面某个字母出现以后,后面将出现什么 字母,并不是完全不确定的,而是有一定的概率 分布,例如:

字母T后面出现H、R的可能性较大,出现J、K、 L、M、N的可能性极小,而且根本不会出现字母 Q、F、X。 考虑到字母之间的依赖关系,可以把英文信源作 进一步的近似,看作一阶或二阶Mark ov 信源,这 样可求得: H 2 ? 3.32 (比特 / 符号)H 3 ? 3.(比特 / 符号) , 1

维条件概率p ?a j | ai ?和二维条件概率p ?ak | ai a j ?,

根据这种近似,我们需要计算得到字母之间的一 然后按照这种概率发布随机地选择英文字母排列 起来,就可以得到二级近似(一阶Mark ov 信源) 和三级近似(二阶Mark ov 信源) 但其计算量相当大,如果近似为二阶Mark ov 信源

,就要计算27 3=196832 项二维条件概率。 为了精确地计算这些条件概率,就必须处理上百 万的字母。为此,香农提出了一种构成近似英语 信源的典型字母序列的最简洁的方法:

一阶Mark ov 近似:p ?a j | ai ? : 在确定了ai以后,确认紧随其后的字母a j , 在确定了a j以后, 确认紧随其后的字母ak , 反复操作就构成一阶Mark ov 英语 信源所输出的一个典型序列: URTESHETHING AD E AT FOULE ITHALIORT ? 二阶Mark ov 近似:p ?ak | ai a j ? : 在确定了ai a j以后,确认紧随其后的字母ak , 在确定了a j ak 以后,确认紧随其后的字母am , 反复操作就构成二阶 Mark ov 英语信源所输出的一个典型序列: IANKS CAN OU ANG RLER THTTED OF TO SHOR OF TO HAVEMEN A I MAND BUT WHISSITABLY THERVERER?

可以看出,在此序列中由两个字母和三个字母 组成的单词大都是有意义的英文单词,而四个 以上字母组成的单词却很难在英文字典中查到, 这是因为各字母之间的相互依赖关系往往要延 伸到更多的符号,所以只有很少量的字母序列 才能组成有意义的单词。 另外,要构成具有意义的英文句子,文章时, 还要考虑各个单词之间的依赖关系,只有很少 量适当的单词才能组成一句有意义的句子。

下面我们应用相同的近似方法来研究英语信源输出 的符号是单词的情况: 1.首先考虑单词独立出现的情况,研究英语单词出 现的概率,就可以得到英语信源的第一级单词近似 的信源。此时,只考虑单词出现的概率,不考虑单 词的相互依赖关系,仍按查表方法: REPRESENTINE AND SPEEDILY IS AN GOOD ART OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES LINE

2.进一步考虑单词之间的依赖关系,这里只考虑 单词间一步转移概率,但不包括句子的结构,就 得到英语信源的第二级单词近似(单词的一阶 Mark ov 信源),仍按香农方法: THE # HEAD # AND# IN # PRONTAL# ATTACK # ON AN # ENGLISH # WRITER # THAT # THE # CHARACTER OF # THIS # POINT # IS # THERE # FORE # ANOTHER # METHOD # FOR # THE # LETTERS # THAT # THE # TIME OF # WHO # EVER# TOLD # THE # PROBLEM # FOR # AN UNEXPECTER?

3.在序列中两个、三个或较多的单词联在一起的 序列并非称为完全不合理的句子,也不会造成异 常或别扭的句法,显而易见,近似的随机序列模 型复杂程度越高就越逼近实际英语的文章。 所以一个足够复杂的随机序列模型能够满意地表 示自然语言的信源,这也说明,一般离散信源都 可以用不同记忆长度的Mark ov 信源来逼近。

英语信源的这种统计特性在对加密的英语文章进行 解密时很有用处,例如,在一种简单的替换密码方 法中,只要用经常发出的字母来猜测,就能够破译 在一些字母丢失的破译文章中,我们可用根据英语 的统计特性将丢失的字母填写上。 由前所知,在信源所输出的序列中依赖关系越复杂, 其信息熵就越低,因此实际英文信源的熵还要低的 多。

对英文字母组成的信源,一般认为: H ? X ? ? H ? ? 1.(比特 / 符号) 4 H? 则相对率:? ? ? 0.29 H0 剩余度:? ? 1 ? ? ? 0.71 这说明,用英文字母写文章时,有百分之71 是由词法、语法和语义等信息确定,而剩下 只有百分之29是写文章的人可以自由选择。

这也意味着在传递或存储英语信息时,只需 传送和存储那些必要的字母,而那些有关联 的字母则可以进行大幅度的压缩。例如, 页 100 英文的书籍,大约只要存储29页就可以了,其 他71页可以压缩掉,而这压缩掉的文字完全可 以根据英文的特性来恢复,从而大大提高了传 输或存储英文消息的效率。 信源的剩余度正是表示这种信源可压缩的程度。

意义信息与加权熵
? 香农定义的信息量是撇开了人的主观因素 的,它只是概率的函数。但在实际场合中, 各种随机事件虽以一定的概率发生,而各 种事件的发生对人们有着不同的价值和效 用,即重要性程度不同。因此,通常很难 忽略与个人目的有关的主观因素。 ? 为了把主观价值和主观意义引入信息度量 中,有人提出了加权熵和意义信息的概念

引入加权熵的概念,它即依赖于事件出现的概率, 又依赖于事件的主观的权重系数。可以用权熵表示 事件发生后和事件主观意义所提供的平均信息量。 现有两个概率空间: ? x ? ? a1 ? p ? x ?? ? ? p ? ? ? 1 a2 ? an ? ? a1 a2 ? an ? ? 及 ?? ? ? ? ? p2 ? pn ? ? 1 2 n?
n i ?1

定义加权熵:H ? ? ?? ?i pi log pi 性质:非负性,等重性,无重性,确定性 非容性,扩展性,线性叠加,递增性。

无失真信源编码
1。理论模型:信源?信源编码器?信道编码器?信道?…… 干扰 噪声 2。编码器:是将信源字符表中的符号si 变换成由x j ( x j ? X )组成的

长度为li的另一序列w i,

S : ( s1 , s2 ,..., sq ) ? 编码器 ? W : ( w1 , w2 ,..., wq )

信源字符表 码字符表

X : ( x1 , x2 ,..., xr )
编码字符表 码元(码符号)

码类的定义
1.编码就是从信源符号到码符号的一种映射,若要实现无失 真编码,必须这种映射是一一对应的。 2.码类的定义: 二元码:码符号集X={0,1}。 等长码:一组码中所有码字的码长都相等。 变长码:一组码中所有码字的码长各不相同。 si ? s j 但wi=w j 奇异码: 非奇异码: si ? s j ? wi ? w j 同价码: X : ( x1 , x2 ,..., xr ) 中每个码元所占的传输时间都相同 码的N次扩展码:

码的N次扩展码
码C的N次扩展码是所有N个码字组成的码字序列集合

若码C : ( w1 , w2 ,..., wq ),其中si ? wi ( xi1 xi2 ...xil )
则N次扩 B ? B ? w w ...w , i , i ,..., i ? 1, 2,..., q , i ? 1, 2,..., q N i i1 i2 iN 1 2 N 展码

? ?

i

?

?

惟一可译码:若码的任意一串有限长的码符号序列只 能被惟一地翻译成所对应的信源符号序列,则称为 惟一可译码。否则就称为非惟一可译码。


信源符号 si 出现概率 s1 s2 P(s1) P(s2) 码1 码2 00 01 11 0 01 111 (X2) w1w1=a1 w1w2=a2 码字 00 001

s3
s4

P(s3)
P(s4)

10 001

w1w3=a3
w1w4=a4 w2w1=a5

0001
0111 010

码1是惟一可译码,码2是非惟一可 译码。因为对于吗2,其有限长的 码符号序列能够译成不同的信源符 号序列。例:0010 可译成s1s2s1 或s3s1。


w4w4=a16


111111

码2二次扩展码

? 下面我们分别讨论等长码和变长码的最佳编码问题,也就 是讨论是否存在一种惟一可译码方法,使得平均每个信源 符号所需要的码符号最短,也就是寻找无失真信源压缩的 极限值。 ? 等长码:①一般说来,若要实现无失真的编码,这不但要 求信源符号 si与码字wi (i ? 1, 2,..., q) 是一一对应,而且要求码 符号序列的反变换也是惟一的,也就是说,所编的码必须 是惟一可译的。②对于等长码来说,若等长码是非奇异码, 则它的任意有限长N次扩展码一定也是非奇异的,因此等 长非奇异码一定是惟一可译码。
信源符号 si s1 s2 s3 s4 码1 00 01 10 11 码2 00 11 10 11

码1是等长非奇异码?惟一 可译码。 码2是奇异码,不是惟一可 译码。

等长码
(码长) 若对信源S进行等长编码,则必须满足: ? r l ? q (信源符号数)(码元个数) ?

信源符号 si s1

码1 00

码2 00

S ? q ? 4, X ? r ? 2, 由 ? r l可知 ? 2 q l
如果对信源S的N次扩展信源进行等长编码, 如果要求编得的等长码是惟一可译码,则 必须满足: N l n

s2
s3 s4

01
10 11

11
10 11

X

q ?r

此式表明:只有当L长的码符号序列数(rL)大于等于N次扩展信源的符号数(qN)时, 才可能存在等长非奇异码。

N log q ? l log r ? l N ? log q log r 若N ? 1则l ? log q log r
l N :表示平均每个信源符号所需要的码符号个数,所以

q N ? r l 表示:对于等长惟一可译码,每个信源符号至少需要用 log q log r
个码符号来变换。

等长码

S : ( s1 , s2 ,..., sq ) ? 编码器 ? W : (w1 , w2 ,..., wq )
码 信源字符表 码字符表

X : ( x1 , x2 ,..., xr )
编码字符表 码元(码符号)

l?N

log q q = 10, r = 2, N = 1, L ≥ log10 / log2 > 3,即用4位或更多位的二进制来 log r 表示每个信源符号。
q = 10, r = 2, N = 2, L ≥ 2×log10/log2 > 6,这时两位信源符号总共有 100种,用二进制来表示只要7位就足够了,平均每个信源符号只要 3.5个二进制就可以了。 更一般L ≥ N×log10/log2 ? 即平均每个信源符号只需 L/N ≥ log10/log2 ≈ 3.222个二进制数即可。

( AEP) The Asymptotic Equipartit ion P roperty 渐进等分割性:相互独立的且满足等 同分布的随机变量X 1 , X 2 , ? , X n,只要 n足够大,每一个样本? x1 , x2 , ? , xn ?发 生的概率几乎趋于相同,即 Pr ? x1 , x2 , ? , xn ? : p ? x1 , x2 , ? , xn ? ? 2 ? n ? H ? x ??? ? ?1

?

?

AEP是弱大数定律的直接推论。 大数定律指出,对于独立的且满足等 同分布的随机变量X 1 , X 2 ,?, X n,只要 1 n n足够大, ? xi 是接近其数学期望值 n i ?1
n 1 n E ?X ? ? ? pi xi , 即 ? xi ? ? pi xi n i ?1 i ?1 i ?1 n

AEP解释:随机变量X 1 , X 2 , ? , X n中的 每一个X k 有发生与不发生的两种可能
n

性,那么? X 1 , X 2 , ? , X n ?的样本空间就 次试验时出现哪种结果的不确定性可

有2 个样本? x1 , x2 , ? , xn ? ,每个X k 每一 用H ? X k ?来描述。因为X k 有相同的p ? x ?

? X 1 , X 2 ,?, X n ?每个X k 有发生与不发生
的联合概率几乎接近2 ? nH ? X ?。

所以H ? X 1 ? ? H ? X 2 ? ? ? ? H ? X n ? ,则

例:设随机变量S ? ?0,1?, 其概率分布为 p?0 ? ? p, ?1? ? q p 若S1 , S 2 , ? , S N 是独立等同分布,则随机序列的联合概率 ? si q N ?? si 其中 分布p ?s1 , s2 , ? , s N ? ? ? p ?sk ? ? p
k ?1 N

s1 , s2 , ? , s N ? S1 , S 2 , ? , S N,sk 取1或0。当N ? 6时,序列 ? si q N ?? si ? p 4 q 2。当N足够大时,可以认为 ?011011 ?,p

?s1 , s2 ,?, s N ?有相同的概率,这些序列的概率为 ?等式两边取以2为底对数? p Np q N ? Np ? 2 ? NH ? S ?。 ? Np log p ? ? N ? Np ? log q ? N ? p log p ? ?1 ? p ? log q ? ? N ? p log p ? q log q ? ? ? NH ?S ?

在2 N 个序列中,那些序列中 1 的个数趋向于Np的序列

TH : ? AEP ?如果随机变量X 1 , X 2 , ? , X n 是i.i.d且 1 ~p ? x ? ,则 ? log p ? x1 , x2 , ? , xn ? ?概率 ? H ? X ?。 ? ? n 因为随机变量X 1 , X 2 , ? , X n 是i.i.d且~p? x ? , 1 1 n 所以 ? log p ? x1 , x2 , ? , xn ? ? ? ? log p? xk ? n n k ?1 ? ?? p ? xk ? log p ? xk ? ?概率收敛 ? H ? X ? ?? ?
k ?1 n

即对任意? ? 0, ?1 ? lim ? log p ? x1 , x2 , ? , xn ? ? H ? X ? ? ? ? ? 1 n ?? n ? ?

渐近等同分割性
( AEP )如果x1 x2 ...xn是i.i.d 且 ? p(x),则 1 - log p ( x1 x2 ...xn ) ? H ( X )概率收敛,即对任意? ? 0 n ?1 ? lim ? n log p( x1 x2 ...xn ) ? H ( X ) ? ? ? ? 1 n ?? ? ? A ? ?( x1 x2 ...xn ) | ( x1 x2 ...xn ) ? X n ? A?( n ) ? ?( x1 x2 ...xn ) | p ( x1 x2 ...xn ) ? 2 ? nH ? A?( n ) ? ?( x1 x2 ...xn ) | p ( x1 x2 ...xn ) ?? 2 ? nH ? A?( n ) ? A?( n ) ? ?且A?( n ) ? A?( n )=A

? ?典型序列集

?x1 x2 ? xn ?? X
特性: 2
? n ? H ? x ??? ?

定义:?典型序列A? ~ p?x ?是序列
?n ?
n

的集合,具有以下
? n ? H ? x ??? ?

? p?x1 x2 ? xn ? ? 2

A? 的性质
(n)

A?( n )具有以下性质: 1 1.如果( x1 x2 ...xn ) ? A? , H ( X ) ? ? ? ? log p( x1 x2 ...xn ) ? H ( X ) ? ? n 2.对于充分大的n, Pr ? A?( n ) ? ? 1 ? ? n
(n)

3. A?( n ) ? 2n ( H ( X ) ?? ) 4. A?( n ) ? (1 ? ? )2n ( H ( X ) ?? ) 2? n ( H ( X ) ?? ) ? p( x1 x2 ...xn ) ? 2? n ( H ( X ) ?? )

X

A?( n )

A?

(n)

性质1 :如果?x1 , x2 ,?, xn ? ? A? ,则
?n ?

1 H ? X ? ? ? ? ? log?x1 , x2 ,?, xn ? ? H ? X ? ? ? n ?n ? 由定义 : 若? x1 , x2 ,?, xn ? ? A? ,则 2
? n ? H ? x ??? ?

? p?x1 x2 ? xn ? ? 2

? n ? H ? x ??? ?

两边去对数即得到。

性质2:对于充分大的n, A??n ? ? 1 ? ? Pr 由AEP定理:当n ? ?时, 1 概率 ? log p? x1 , x2 , ? , xn ? ?? ? H ? X ? ? n 即事件? x1 , x2 , ? , xn ? ? A??n ?发生的概率接近1 , 因此,对于任意的? ? 0,存在一个n0,对于 所有n ? n0 都有 ?1 ? lim ? log p? x1 , x2 , ? , xn ? ? H ? X ? ? ? ? ? 1 ? ? n ?? n ? ? ?n ? 设?=?,则有 Pr A? ? 1 ? ?

? ?

? ?

性质3: ? 2

? n ? H ? x ??? ?

? 又 ?1 ? ? P X
? X ?X n ? X ?X n ? ? n H X ??

?1 ?

? ? ? ? ? P ?X ? ? ? P ?X ? ? ? 2
? ?n ? X ? A? ? ?n ? X ?A?

? p? x1 x2 ? xn ? ? 2

? n ? H ? x ??? ?

? ? n H X ??

? ? ? ?

? ? ? ? A? n ? ?2 ?

? A?

?n ?

? ? ? ? ?2
? n H X ??

性质4: ? 2 ? n ? H ? x ??? ? ? p ? x1 x2 ? xn ? ? 2 ? n ? H ? x ??? ? 又 ? 对于充分大的 n 有 Pr A??n ? ? 1 ? ? ? ?1 ? ? ? Pr A?n ? ? 2 ? n ?H ? X ??? ?

? ? ?
?

? ?

? 2 ? ? ? ? A??n ?
? ? n H X ??

? ? X ? A? n ?

? A?

?n ?

? ? ? ? ? ?1 ? ? ?2
? n H X ??

AEP定理告诉我们:? 典型序列集合 A??n ? 的 元素虽然很少,但在样本空间中A??n ?的元素 出现的概率 Pr A??n ? ? 1 ? ? 几乎接近 1。

? ?

如果 X 1 , X 2 , ? , X n 是 i.i.d 随机变量~p ? x ?, 我们希望找到对这样随机变量序列的尽可 能短的描述。我们可以把 X n 中的所有序 列划分成两个集合,一类是 ? 典型序列集 时, ??n ? 中的序列? x1 , x2 , ? , xn ?出现的概率趋 A 合 A??n ?,另一类是 A??n ? 的补集 A??n ?,当n ? ?

AEP定理在数据压缩上的应用:

向于 1,A??n ? 中的序列出现的概率趋向于 0 。

再看A? 中序列的总数占信源序列的比值:

?n ?

??

A??n ? X
n

?

2 n ? H ? X ??? ? X
n

?2

? n ?log X ? H ? X ??? ?

一般情况下H ? X ? ? log X , 所以 log X ? H ? X ? ? ? ? 0 则随 n 增大 ? 趋于 0,这就是说 A? 虽然是 高概率集,但它含有的序列数常常比非典 型序列 A??n ? 要少很多。
?n ?

现在我们可以只对少数的高概率 A? 中序列进行一一对应的等长 编码,这样码字的总数减少了, 所需的码长自然可以减少。
?n ?

编码的长度:我们令每个集合中的所有元素 按照一个顺序排列起来,然后将 A? 中的每 一个序列用它在序列中的序号表示,因为 A?
?n ? ?n ?

?2

n ? H ? X ?? ? ?

,所以可用不超过

n?H ? X ? ? ? ? ? 1 bits位表示序号,在这些序号 前加上一个0标记,那么表示 A??n ? 中的每个 序列的长度 ? n?H ? X ? ? ? ? ? 2 bits。

同理我们能够用不多于 n log X ? 1 bits 索引不在 A??n ? 中的每个序列,在这些 序号前加上一个标记1,于是我们就 可以给出 X n 中所有序列的编码,码 长为 n log X ? 2 bits

在以上的编码体系中我们应该注意到以下性质 1.编码是一一对应的且容易译码,编码的第一 位bit是一个标记位,用来确定该编码的后续长 度。 0 : n? H ? X ? ? ? ? ? 2 ; 1 : n log X ? 2 2.我们已经利用了一个强有力的、有关不规则 集合 A??n ? 的穷举法,该方法将不考虑 A??n ? 中的 元素个数远少于 X n 的事实,这对产生一个有 效的编码描述是非常有效的。 3.典型序列有一个长度为 ? nH ? X ? 的短描述。

我们用 x 表示序列 x1 , x2 , ? , xn ,令 l x 为 x
n n

? ?

n

? ? E ?l ?x ?? ? ? p ?x ? l ?x ? ? ? p ?x ? l ?x ? ? ? p ?x ? l ?x ?
n n n x n ?X n n n n n
? x n ? A? n ?

的码字长度,如果 n 充分大以致

Pr A??n ? ? 1 ? ?,则码字长度的期望值为

?

? x n ? A? n ?

p x n ?n?H ? X ? ? ? ? ? 2? ? ?
?n ?

? ?

x n ? A?? n ?

? Pr A?

? ??n?H ? X ? ? ? ? ? 2? ? Pr?A ??n log X ? 2?
?

x n ? A?? n ?

p x n ?n log X ? 2? ?
?n ?

? ?

??n?H ? X ? ? ? ? ? 2? ? Pr?A ??n log X ? 2? ? Pr ?A? ? ? ? 1 ? ?, ? Pr ?A? ? ?最多为 1 ,且取 Pr ?A ? ? ? ? ? ? ?n?H ? X ? ? ? ? ? 2? ? ? ?n log X ? 2?
?n ?
n

? Pr ?A?

?

?n ?

?

?

n

?

n

2 ? n?H ? X ? ? ? ??。注? ? ? ? ? ? log X ? n 只要根据n选择适当的?,我们就能够使? ? 任意地小。由此引入定理

定理:设 X 是 i.i.d . ~ p ? x ? , 令 ? ? 0 ,则
n

一定存在一个编码,它将长度为 n 的序 列 x n 映射成二进制串,且这个映射是 一一对应的(可逆的),且当 n 充分大 时,有 E l x n ? nH ? X ? ? ? 因此从平均的角度,我们能够使用 nH ? X ? bits 来表示序列 X n

? ? ??

前面的讨论已知:若对信源 S 进行等长编码, 则必须满足不等式

?信源符号数? ? ?码元个数?

?编码长度 ?

?q?r

l

若对信源 S 的 N 次扩展进行等长编码,则 q N ? r l。此式表明,只有当l长的码符号序列 数 r l 大于等于 N 次扩展信源的符号数 q N 时 ,才可能存在等长的非奇异码

l N 表示平均每个信源符号所需要的码符号个数 所以q N ? r l 表示:对于等长唯一可译码,每一个 信源符号至少需要用log q log r 个码符号来变换。 当r ? 2时, N ? log q表明:等于二元等长唯一可 l 译码,每个信源至少需要用 log q个二元符号来变 换,这也表明:对于二元等长唯一可译码,每个 信源符号所需码长的极限值为 log q。

例:英文电报系统有32 个符号(q ? 32, r ? 2, N ? 1 ) log q l? ? log 32 ? 5bits log r 因此每个英文电报至少需要用5位二元符号编码。 但实际英文电报符号信源,在考虑符号出现的 概率以及符号之间的依赖性之后,平均每个英 文电报符号所提供的信息量约等于1.4bit,大大 小于5bits。

因此等长编码后,每个码字载荷约1.4bit信息 量,也就是说编码后5个二元符号只携带约 1.4bit信息量。由前面讨论已知对于无噪声无 损二元信道,每5个二元码符号最大能载荷 5bit的信息量,因此等长编码的信息传输效率 是极低的。

是否可以使每个信源所需的码符号个数减少, 也就是说是否可以提高传输效率呢?可以! 现举例说明若考虑符号出现的概率,以及符号 之间的依赖关系,就可以减少每个信源符号平 均所需的码符号个数。设信源 ? X ? ? a1 a2 ? p? x ?? ? ? p p ? ? ? 1 2 而依赖关系: 其余p ?a j | ak ? ? 0 a3 p3 a4 ? ? , p4 ?

?p
k ?1

4

k

?1

p ?a2 | a1 ? ? p ?a1 | a2 ? ? p ?a3 | a4 ? ? p ?a4 | a3 ? ? 1

1.若不考虑符号之间的依赖关系,信源符号 q ? 4,进行等长二元编码,可知l ? 2。 2.若考虑符号之间的依赖关系,此信源的二次 扩展信源为 ? X 2 ? ? a1a2 a2 a1 a3 a4 a4 a3 ? ? ??? ? ? p ?x j xk ?? ? p ?a1a2 ? p ?a2 a1 ? p?a3 a4 ? p?a4 a3 ?? ? ? ? p?a j ak ? ? 1,又p?a j ak ? ? p?a j ?p?ak | a j ? 由假设可知,除p?a1a2 ?, p ?a2 a1 ?, p?a3 a4 ?, p ?a4 a3 ? ? 0 其余a j ak出现的概率趋于另。
j ,k

因此二次扩展信源 X 由 4 ? 16 个符号缩减
2 2

到只有4个符号,此时,对二次扩展信源 X 进行等长编码,所需码长仍为 l ? ? 2 ,但平均
2

每个信源符号所需码符号为 l ? N ? 1 ? l ,由此 可见当考虑符号之间的依赖关系后,有些信源 符号序列就不会出现,这样信源符号序列的个 数就会减少,再进行编码时,所需要的平均码 长就可以缩短。

等长编码定理
一个熵为H ? X ?的离散无记忆信源, 若对信源长度为N的 N ?H ? X ? ? ? ? 当码长l满足l ? , N足够大时, 可以实现几乎 log r N ?H ? X ? ? 2? ? 反之, 若l ? , 则不可能实现几乎无失真编码 log r 且当N足够大时, 译码错误率近似等于 . 1 无失真编码, 即译码错误概率可以任意小. 符号序列进行等长编码, 设码元有r个, 则对任意? ? 0,

说明: A? ?

?N ?

?2

N ? H ? X ??? ?

, ? 我们只对少数的高

概率序列进行一对一的等长编码,这就要求码 字的总数不少于 A?
?N ?

,即

r l ? 2 N ? H ? X ??? ? ? A?? N ? ,取对数 l log r ? N ?H ? X ? ? ? ? ? l N ? ?H ? X ? ? ? ? log r 即当选取等长编码的码字长度 l 满足上式,就 能使集合 A?
?N ?

中所有的? ? 典型序列? k 都有不

同的码字与其对应。

? 在这种编码下,集合A? 中的非典型序列? k 被 舍弃,虽然A? 中序列出现总概率很小,但仍 然可能出现,即造成出错,出错的概率与A? 出现的概率相同,因此 ? Pr A?? N ? ? 1 ? ? ,? Pr A?? N ? ? ?, ? PE ? Pr A?? N ? ? ? ? N , ? ? ? D?I ?ak ?? N? 2 显然,当N ? ?时,译码的错误概率PE ? 0 又 ? ? ? ? ? N , ? ? ? D?I ?ak ?? N? 2
?N ? ?N ?

?N ?

? ?

? ?

? ?

契贝谢夫不等式
对任一给定的正整数?,有 P?? ? E? ? ? ? ? D?

?

2

PE ? Pr A?? N ? ? ? ? N , ? ? ? D?I ?ak ?? N? 2 显然,当N ? ?时,译码的错误概率PE ? 0 其中方差:D? ? E? ? ?E? ? ,均方差? ? D?
2 2

?

?

定理是在平稳无记忆离散信源的条件下论证的, 但它同样适合平稳有记忆信源,此时,只要求
2 有记忆信源的极限熵H ? ?S ?和极限方差? ? ?S ?存

在即可

当二元编码时:

l ?H ?S ? ? ? ? r ? 2, ? ? ?H ?S ? ? ? ? N log r

可见,定理给出了等长编码时平均每个信源 符号所需要的二元码符号的理论极限,这个 极限由信源熵H ?S ?决定。

l 当信源符号具有等概率分布时: ? log q N 当信源符号具有非等概率分布时,而且符号 之间有很强的关联性时,信源熵H ? ?S ? ?? log q 由定理可知,这时等长码中每个信源符号平均 所需的二元码符号大大减少,从而使编码效率 提高。 PE ? Pr A?

?

?N ?

?? ? ?N , ? ? ? D?I ?a ?? N?
k

2

容许错误概率越小,编码效率要越高,则信源 序列长度N必须越长。

l H ?X ? ? ? l ? ? log r ? H ? X ? ? ? . N log r N l 令R ? log r为编码信息率 : N 即编码后平均每个信源符号能够载荷 的最大信息量.及编码信息率大于信源 熵, 才能实现几乎无失真编码.

H ?X ? l 令? ? ? H ?X ? log r 为编码效率. N R 由定理可知等长编码的效率为 : H ?X ? 1 ?? ?? ?? ? H ?X ? H ?X ? ? ? ? D?I ?ak ?? ? 2 ?N? 2 2 H ? X ? ?1 ? ? ? ? N ,? , ?的关系

? ? ? D?I ?ak ?? N? 2 ? N ? D?I ?ak ?? ?? 2

在方差和熵已知的条件下, 上式给出了

s2 ? ? s ? ? s1 设离散无记忆信源? ? ? ?3 4 1 4? ? p ?s ?? ? ? 1 3 4 熵:H ?S ? ? log 4 ? log ? 0.811?bit / 信源符号? 4 4 3 自信息量方差:D?I ?si ?? ? ? p ?si ??log p ?si ?? ? H ?S ?
2 i ?1 2 2

3? 3? 1? 1? ? ? log ? ? ? log ? ? 0.8112 ? 0.4715 4? 4? 4? 4? 若对信源S取等长编码,要求编码效率? ? 0.96 允许错误概率? ? 10 , 则 D?I ?ak ??
?5

2

2

? N? ? ? , ? ? 2 ?1 ? ? ? ?
2 2

0.4715 0.96 2 N? ? 4.13 ? 10 7 0.8112 0.04 2 ? 10 ?5

变长码
? 变长码往往在N不是很大时就可以编出效率 很高的,且无失真的码。 ? 变长码也必须是唯一可译码,才能实现无 失真编码,对于变长码,要满足唯一性, 不但码本身必须是非奇异的,而且其任意 有限长N次扩展也都必须是非奇异的。

不等长编码的平均码字长度
信源字符表为X ? {x1 , x2 ,...xK } 相应的概率为p ( x1 ), p ( x2 ),..., p( xK ) 码字符表为W ? {w1 , w2 ,...wK } 其码长分别为:n1 , n2 ,..., nK 则评价码字长度为: ? ? p ( xk )nk n
k ?1 K

变长码
信源符号 si 符号出现概率P(si) 码1 码2 码3 码4

s1
s2 s3 s4

1/2
1/4 1/8 1/8

0
11 00 11

0
10 00 01

1
10 100 1000

1
01 001 0001

码1:奇异码。

码2:非奇异码,但不是唯一可译码。 ‘01000’?S4S3S1,S4S1S3,S1S2S1S1
码3,码4都是唯一可译码,但有区别: 码4:码中每个码字都以1为终点,起到码字之间的分隔作用, 称为逗点码 码3:没有逗点码的功能,例收到‘10’时不能立即翻译

即时码
? 定义:在唯一可译码中,有一类码,它在译码时 无需参考后继的码符号就能立即作出判断,译成 对应的信源符号,则这类码称为即时码。
信源符号 si
s1 s2 s3 s4

符号出现概率P(si)
1/2 1/4 1/8 1/8 0 11 00 11

码1
0 10 00 01

码2
1

码3
1 10 100 1000

码4
01 001 0001

两个码字W2=10,W3=100间的前缀与延长的关系: W2=10是W3=100的前缀; W3=100是W2=10的延续

前缀码、即时码
? 定义:若码C中没有任何完整的码字是其他 码字的前缀,则称此码为即时码,也称为 前缀码或非延长码。
即时码

各种码 字之间 的包含 关系

唯一可译码 非奇异码 所有码

? 即时码的一种简单构造法是树图法:即给定码字 全体集合{w1,w2,…,wn},用码树来描述。 ? 按树图法构造码,若树的中间节点不安排码字, 那么该码一定满足即时码的定义。 ? 因为从根到每一个终端节点所走的 A 0 1 路径不同,且中间节点不安排 B 1 码字,所以该码一定满足前缀 0 1 C 01 码的定义。 0 1
D

1

001 0001=W4 E

信源符号 si

符号出现概率P(si)

码1

码2

码3

码4

s1
s2 s3 s4

1/2
1/4 1/8 1/8

0
11 00 11

0
10 00 01

1
10 100 1000

1
01 001 0001

码4
0 C 0 D 1

A 0 B 1 1 001 0001=W4 E 01 1 1

码3
B 0 C 0 D 100

1 A 0 10 1

1000=W4 E

码3 从树根 到终端节点 所经过的路 径上的每一 个中间节点 都为码字, 因此码3不 满足前缀码 的定义。

前缀码 即时码
如果没有一个码字是任意其他码字的 前缀, 即当ak1 ak2 ? akn 是码字时, ak1 ak2 ? ak j ;1 ? j ? n不是码字, 这样的 编码称为前缀码. 定理 : 编码C是即时码的充分必要条件 是C是前缀码

Kraft不等式
其码字为W ? ?w1 , ? , wK ?, 所对应的码长为 l1 , ? , l K时, 则必须满足以下Kraft不等式 r ?l k ? 1 ?
k ?1 K

对于码符号为X ? ?x1 ,? , xr ? 的任意即时码,

反之,若码长满足不的满足不等式,则一 定存在具有这样码长的即时码。

码符号X

Kraft不等式 ? ?x1 , x2 , ? , xr ? ,码字W ? ?w1 , w2 , ? , wq ?
q ?lk

码长为l1 , l2 , ? , lq , 则? r
k ?1

? 1。

A 0 1

因为任意即时码都可以用r元树图 来描述,那么,即时码C一定也可 以用r元树图表示,从树图来看
一阶结点

w1
0 0 1 1

0

1
二阶结点 1 0 1 三阶结点

w2
1

0

0

w3

第N阶所有可能伸出的树枝为r N 枝,当某第k(k ? N )阶节点为 码字,即码长lk ? k , 它将影响到第N阶所伸出的树枝数目,它 使得第N阶不能伸出的树枝数目等于r N ? k ? r N ?lk 。 因为码字共有q个,每个码字作为数的终端节点后,都会影响 第N阶,那么,q个码字影响第N阶总共不能伸出的树枝数目 为? r
k ?1 q N ?lk

? r N , 则: r ?lk ? 1 ?
k ?1

q

A 0 1

证明前半部分很容易:

w1
0 0 1 1 0 1

一阶结点 0 1 二阶结点 1 0

w2
0

1
三阶结点

w3

即时码、唯一可译码
? 1949年Kraft提出不等式,1956年麦克米伦 证得:唯一可译码也满足此不等式。 ? 这说明唯一可译码在码长的选择上并不比 即时码更宽松,即在码长的选择上,即时 码与唯一可译码是一致的。

即时码、唯一可译码
? 定理:若存在一个码长为 l1 , l2 , ?, lq 的唯 一可译码,则一定存在相同码长的即时码。 ? 定理:在所有唯一可译码中最小平均码字 长度等于所有即时码中的最小平均码字长 度。 ? 因此,在所有唯一可译码中寻找最小平均 码字长度,只需在即时码中寻找即可。

编码的速率与效率
n 编码速率:R ? log r N H (X ) H (X ) 编码效率:?= ? n R log r N
编码速率是编码后平均每个信源符号能够载荷的最大信息量。 只有编码速率大于信源符号熵,才能实现几乎无失真的编码,而编码效率小 于1,它衡量了编码的效果。

H ?S ?的单位为:比特 / 信源符号。 对唯一可译码来说,信源符号与码字是一一对应的, 所以由p ?wk ? ? p ?sk ? ,则这个码的平均码长为: L ? ? p ?sk ?lk (码符号 / 信源符号) H ?S ? 编码后信道的信息传输率为:R ? (比特 / 码符号) L 若传输一个码符号平均需要t秒钟,则编码后信道每秒 H ?S ? 传输的信息量为:Rt ? (比特 / 秒) tL 可见:L 越短,Rt 越大,信息传输效率越高,为
k ?1 q

此,我们感兴趣的是使平均码长L 为最短的码。

紧致码
? 紧致码(最佳码):对于某一信源和某一 码符号集来说,若有一个唯一可译码,其 平均长度小于所有其它唯一可译码的平均 长度,则该码称为紧致码,或最佳码。无 失真信源编码的基本问题就是要寻找紧致 码。 ? 现在我们来寻找紧致码的平均码长可能达 到的理论极限值。

变长信源编码定理
设有一离散无记忆信源 x1 x2 ... xK ? ? X ? ? ? p ( x) ? ? ? p ( x ) p ( x ) ... p ( x ) ? ? ? ? 1 2 K ? H ( X )为该信源的熵,则 ()任何一个r元的惟一可译码的平均码长必须满足 1 H (X ) n? (下限) log r H (X ) n? +1(上限) log r
证明,说明怎样去找。

(2)一定存在一个r元的惟一可译码,其平均码长满足
证明(作业)

扩展信源编码
平均每个消息符号的编码长度为 ? ? n( X N ) n? , 其中n( X N )=? p (u )n(u ) N ? ? n(u )是消息序列u对应的码组的长度。 H (X ) H (X ) N ? n( X ) ? ?1 log r log r
N N

H ?S ? 1 L N H ?S ? 1 LN ? ? ? ? H r ?S ? ? ? ? H r ?S ? log r N N log r N N LN 当N ? ?时,则 lim ? H r ?S ? N ?? N LN ? ? p ?sk ??k,?k 是? k 所对应的码字长度。因此
k ?1 qN

LN 是S N ? ?1 , ? 2 , ? , ? q N 中每个符号? k 的平均码长 LN N 是信源S中每一单个信源符号所需的平均码长 L 是S N ? ?s1 , s2 , ? , sq ? 中每个符号sk 的平均码长

?

?

假设信源确切的概率分布为P?S ?, 而我们用其 概率分布的估计Q?S ?来编码,则 ? 1 ? 定理:若按照l ?s ? ? ?log ? 来编码,则码长 q?s ?? ? l ?s ?对确切的概率分布P?S ?的均值满足 H ?P ? ? D?P || Q ? ? EP ?l ?s ?? ? H ?P ? ? D?P || Q ? ? 1

LN 不等长信源编码的编码信息率:R? ? log r N 即等长和不等长编码的编码信息率的理论极限 是一致的。 香农的第一定理也可以陈述为: 若R? ? H ?S ? ,就存在唯一可译变长编码; 不能实现无失真的信源编码。

若R? ? H ?S ? ,唯一可译变长编码不存在,即

不等长编码

信源符号 si s1 s2 s3

符号出现概率P(si) 1/2 1/4 1/8 0

码1 0 10 00 11 00

码2 1

码3 1 10 100

码4 01 001

s4

1/8

11

01

1000

0001

码2的二次扩展码
信源符号 s 1s 1 s 1s 2 s 1s 3 s 1s 4 s 2s 1 s 2s 2 s 2s 3 s 2s 4 码字 00 010 000 001 100 1010 1000 1001 信源符号 s 3s 1 s 3s 2 s 3s 3 s 3s 4 s 4s 1 s 4s 2 s 4s 3 s 4s 4 码字 000 0010 0000 0001 010 0110 0100 0101

即时码的树图构造法(码4)
A 0 B 0 C 0 D 1 1 001 0001=W4 E 1 01 1 1

二元码树
A 0 1 一阶结点 0 0 1 1 0 1 0 0 1 1 二阶结点 0 1 三阶结点

三元码树
A

一阶结点 0 1 2 0 1 2 0 1 2 二阶结点 0

1

2

0

1

2
三阶结点

即时码的树图构造法(码4)
A 1 1 1 0 1110 码4的另一种形式
信源符号 si s1 s2 符号出现概率P(si) 1/2 1/4 0 11 码1 0 10

A 0 1 0 10 0 0 100 1 0 10

0 0 110

1000 码3的码树
码2 1 10 码3 1 01 码4

s3
s4

1/8
1/8

00
11

00
01

100
1000

001
0001

表a

霍夫曼(Huffman)码
码字长 度 li 码字 Wi 概率 P(si) S1 压缩信源 S2 0.4 0.2 0 1 1 01 0.4 0.4 S3 0

信源 编码 si

0.6
s1 s2 s3 s4 s5 1 2 3 4 4 1 01 0.4 0.2 1 01 0 1 0 1 1 00 0.4

1

000
0010 0011

0.2
0.1 0.1

000
0010 0011

0.2
0.2

000
001

0.2

01

离散无记忆信源S=[s1,s2,s3,s4,s5],它的一种霍夫曼码如表a,它的平均码长为:
L ? ? P( si )li ? 0.4 ?1 ? 0.2 ? 2 ? 0.2 ? 3 ? 0.1? 4 ? 0.1? 4 ? 2.2(二元码元/信源符号)
i ?1 5

编码效率:? ? 0.965

表a中霍夫曼码的码树
信源 编码 si 码字 Wi 0 s1 s2 s3 s4 s5 1 01 0 000 0 0010 1 1 0011 A 0 1 01 1 1

000
0010 0011

表b

另一种霍夫曼码
码字长 度 li 码字 Wi 概率 P(si) S1 压缩信源 S2 0.4 S3 0

信源 编码 si

0.6
s1 s2 s3 s4 s5 2 2 3 3 3 00 0.4 0 1 1 00 0.4 00 0.4 00 0 1 0.4

1

10
11 010 011

0.2
0.2 0.1 0.1 0 1

10
11 010 011

0.2
0.2 0.2

01
10 11

0.2

01

? S ? ? s1 s2 ? P ( s ) ? ? ? 0.4 0.2 ? i ? ?

s3 0.2

s4 0.1

s5

? 0.1? ?

表b中霍夫曼码的码树
信源 编码 si 码字 Wi B 0 1 0 1 011 10 1 11

0 s1 s2 s3 s4 s5 00 00

1 0 010

10
11 010 011

选择那种编码更好
? ? 1.36
2 1

A 0 1 1 1 01 0 1 0 0

B 1 0 1 011 10

2 ? 2 ? 0.36

0 0 000 0 1

1 11

1

00

0010

0011

010

2 ? n ?n ? ? ? ?E i ? p( xi )(ni ? n) ? ? i ?1 ? ? 2 2
由此得出,在霍夫曼编码过程中,当缩减信源的概率分布重新排列时,应使合 并得来的概率尽量出于最高的位置,这样可使合并的元素重复编码次数减少, 使短码得到充分利用。

?

?

K

表c
信源 编码 si s1 s2 s3 s4 s5 码字 Wi 1 2 3 00 01 02 030 031

四元霍夫曼码
概率 P(si) 0.22 0.20 0.18 0.15 压缩信源

S1
1 2 3 00 01 02 0.22 0.20 0.18 0.15 0.10 0.08 1 2 0

S2
1 2 3 00 01 02 0.40 0.22 0.20

0 1 2

S3
0 1 2 3

0.18 3

0.10
0.08 0.05 0.02 0 1 2 3

s6
s7 s8 s9

03
03

0.07 3

03

s10

为使短码得到充分利用,使平均码长为最短,必须使最后一步的缩减信源有r个信 源符号,因此对于r元编码,信源S的符号数q必须满足:

q ? (r ? 1)? ? r

表c中四元霍夫曼码的码树
信源 编码 si s1 s2 s3 s4 s5 码字 Wi 1 2 3 00 0 00 1 01 2 02 3 1 2 3 0 1 A 3

2

01
02 030 031

s6
s7 s8 s9 s10

030

031

最佳即时码
定理:对于给定分布的任何信源,存在一个最佳即时 码(其平均码长最短),此码满足以下性质: 1. 若p j ? pk,则l j ? lk。(码长和概率成反比) 2.两个最小概率的信源符号所对应的码字具有相同 的码长。 3.两个最小概率的信源符号所对应的码字,其除最 后一位不同外,前面各位码元都相同。

霍夫曼码的最佳性 条件:p1 ? p2 ? p3 ? p4 ? p5
0 0 0 0 A (a) 1 1 P2 1 P4 0 P5 0 0 0 P3 A (b) 1 0 0 P5

某一即时码
1 P1 0

1
P2 0 1 P4 P3

交换p1和p2,使 平均码长缩短

1
P1

0 0 0 1 P1 1 P4 1

P5 修剪p5树枝 0 0 1 P1 1

0 1

P2 重新排序,使 P3 平均码长最短

P2 0
P3

A
(c)

1

A
(d)

0
P4 P5

1

费诺(Fano)码
s1 1/4 0 0 1 00 01 0 1 1 1 0 0 1 0 1 1 100 101 1100 1101 2 2 3 3 4 4 4 4

s2
s3 s4 s5

1/4
1/8 1/8 1/16

0

概率递减排序,划分成概率 和近于相同的两组,并各赋 予二元码符号“0”和“1”。 反复进行,直至每小组只剩 一个信源符号为止。

p ( si ) ? r ? li
H ?S ? ?? n log r N

s6
s7 s8

1/16
1/16 1/16

1110
1111

此信源的熵H(S)=11/4(比特/信源符号),而码的平均长度也等于11/4(二元码符号/ 信源符号)。这是紧致码,码的效率等于1。它之所以能够达到最佳,是因为信源 符号的概率分布正好满足以上等式,否则不会达到1的编码效率。

费诺(Fano)码
s1 0.32 0 0 1 00 01 10 0 1 1 1 0 1 110 1110 1111 2 2 2 3 4 4

s2
s3 s4 s5

0.22
0.18 0.16 0.08

0

s6

0.04

H ( S ) ? 2.35...n ? 2.32...? ? 0.987 一般非诺码的平均码长n ? H r ( S ) ? 2 所以非诺码不一定是最佳码。

信源符号集合的累积分布函数分配码字
F (ak )

信源符集合A ? ?a1 , a2 ,?, aq ?
1.0

F (ak ) ? ? P (ai )
i ?1

k

F ( S ) ? F (ak ) ? ? P (ai ) ?
i ?1

k ?1

1 P (ai ) 2

P(a3 )

F (ak ) ? ? F (ak ) ? ? ?

l ( ak )

?

1 2l ( ak )

F (a2 )

1

2

3

4

5

6

2 - 2 ? 2 -l ? ? x ? ? ?l ?1 ? l ?x ? ? ? ?log p?x ? ? ? 1 ? log p?x ? ? 1

?F ?x ??l ? x ? ?

F ?x ? ? 0 . x1 2-1

x2 ? xl ?

? 1 ? l (ak ) ? ?log ? ?1 P (ak ) ? i ? P (ak ) 1 ? ? F (ak ) ? F (ak ) l ( ak ) 2 2 F ?ak ?1 ?
表示取L位使小于等于x的数

F (ak )

累积分布函数
F ?ak ? ? ?F ?ak ?? l ?ak ? ?
P(a3 )

1.0

F (a2 )

2 l ? ak ?
i 4 5 6

1

p?ak ? ? ? F ?ak ? ? F ?ak ?1 ? 2

2l ? ak ?

1

所以?F ? x ??l ? x ? 也位于对应于x的台阶中,显然如果用长度为l的二进 1? ? 码字Z1Z 2 ? Z l 来表示一个区间? 0.Z1Z 2 ? Z l ,0.Z1Z 2 ? Z l ? l ?,则一个 2 ? ? 码是即时码就等价于这些码字相应的区间不相交。于是用?F ? x ??l ? x ? 来作为x的码字的编码是一个即时码。因为对应于任何消息x的码字 区间长度2 ?l ? x ? 小于相应于x点的台阶的一半?香农 ? 非诺 ? 埃利斯编码?

1

2

3

香农-非诺-诶利斯码
信源符号 概率函数 累积分布函数

S
s1 s2 s3 s4

P(s)
0.25 0.5 0.125

F (s)
0.25 0.75 0.875

F (s)
0.125 0.5 0.8125

F (s)
的二进制
0.001 0.10 0.1101

? l ( s) ? ? log ?

码长 3 2 4

1 ? ? 1 P(s) ? ?

码字

W
001 10 1101

0.125

1.0

0.9375

0.1111

4

1111

1.0 0.875 0.75

0.9375 0.8125

0.5
0.25 0.125

香农-非诺-诶利斯码
信源符号 概率函数 累积分布函数

S
s1 s2 s3 s4 s5

P(s)
0.25 0.25 0.2 0.15 0.15

F (s)
0.25 0.5 0.7 0.875 1.0

F (s)
0.125 0.375 0.6 0.775 0.925

F (s)
的二进制 0.001 0.011 0.10011 0.1100011 0.1110110

码长
? 1 ? l ( s ) ? ? log ?1 P(s) ? ? ?

码字

W
001 011 1001 1100 1110

3 3 4 4 4

MH码表(一)尾码表(同一符号重复出现而形成的字符串长度称为游程长度)
RL长度
0 1 2

白游程码字
00110101 000111 0111

黑游程码字
0000110111 010 11

RL长度
16 17 18

白游程码字
101010 101011 0100111

黑游程码字
0000010111 0000011000 0000001000

3
4 5 6

1000
1011 1100 1110

10
011 0011 0010

19
20 21 22

0001100
0001000 0010111 0000011

00001100111
00001101000 00001101100 00000110111

7
8 9 10

1111
10011 10100 00111

00011
000101 000100 0000100

23
24 25 26

0000100
0101000 0101011 0010011

00000101000
00000010111 00000011000 000011001010

11
12 13 14

01000
001000 000011 110100

0000101
0000111 00000100 00000111

27
28 29 30

0100100
0011000 00000010 00000011

000011001011
000011001100 000011001101 000001101000

15

110101

000011000

31

00011010

000001101001

MH码表(一)尾码表
RL长度
32 33 34

白游程码字
00011011 00010010 00010011

黑游程码字
000001101010 000001101011 000011010010

RL长度
48 49 50

白游程码字
00001011 01010010 01010011

黑游程码字
000001100100 000001100101 000001010010

35
36 37 38

00010100
00010101 00010110 00010111

000011010011
000011010100 000011010101 000011010110

51
52 53 54

01010010
01010101 00100100 00100101

000001010011
000000100100 000000110111 000000111000

39
40 41 42

00101000
00101001 00101100 00101011

000011010111
000001101100 000001101101 000011011010

55
56 57 58

01011000
01011001 01011010 01011011

000000100111
000000101000 000001011000 000001011001

43
44 45 46

00101100
00101101 00000100 00000101

000011011011
000001010100 000001010101 000001010110

59
60 61 62

01001010
01001011 00110010 00110011

000000101011
000000101100 000001011010 000001100110

47

00001010

000001010111

63

00110100

000001100111

MH码表(二)组合基干表
RL长度
64 128 192

白游程码字
11011 10010 010111

黑游程码字
0000001111 000011001000 000011001001

RL长度
960 1024 1088

白游程码字
011010100 011010101 011010110

黑游程码字
0000001110011 0000001110100 0000001110101

256
320 284 448

0110111
00110110 00110111 01100100

000001011011
000000110011 000000110100 000000110101

1152
1216 1280 1344

011010111
011011000 011011001 011011010

0000001110110
0000001110111 0000001010010 0000001010011

512
576 640 704

01100101
01101000 01100111 011001100

0000001101100
0000001101101 0000001001010 0000001001011

1408
1472 1536 1600

011011011
010011000 010011001 010011010

0000001010100
0000001010101 0000001011010 0000001011011

768
832 890

011001101
011010010 011010011

0000001001100
0000001001101 0000001110010

1664
1728 EOL

011000
010011011 000000000001

0000001100100
0000001100101 000000000001

MH码表(三)供加大纸宽用的组合基干表(1792~2560,黑、白相同)

游程长度
1792 1856 1920

组合基干码码字
00000001000 00000001100 00000001101

1984
2048 2112 2176

000000010010
000000010011 000000010100 000000010101

2240
2304 2368 2432

000000010110
000000010111 000000011100 000000011101

2496
2560

000000011110
000000011111

MH码
? 其编码规则如下: 1.游程长度在0~63时,码字直接用相应的终端码表示,例如,一行中连续19个白, 接着连续30个黑,既白游程长度为19,接着黑游程长度为30,查表得码字为: 0001100 | 000001101000; 2.游程长度在64~1728时,用一个组合码加上一个终端码为相应码字,例如,白 游程长度为65(=64+1),用白游程长度为64的组合码字加上白游程长度 为1的终端码字组成相应的码字,查表得码字为: 11001 | 000111; 若黑游程长度为856=832+24=64×13+24,故查表得码字为: 0000001001101 | 00000010111; 3.规定每行都从白游程开始。若实际出现黑游程开始的话,则在行首加上零长度 白游程码字。每行结束用一个结束码(EOL); 4.每页文件开始第一个数据前加一个结束码。每页尾连续使用6个结束码表示结 尾。 5.每行恢复成1728个像素,否则有错。因为霍夫曼码是即时码,所以可以将接收 到的二元序列查表译得原二元序列。 6.为了传输是实现同步操作,规定T为每编码行的最小传输时间。一般规定T最小 为20ms,最大为5s。若编码行传输时间小于T,则在结束之前填以足够的“0” 码元(填充码)。

传真信息传输格式
页首 EOL 数据 EOL 数据 <T ≥T 设某页传真文件中某一扫描行的像素点为: |←17个(白)→|←5黑→|←55白→|←10黑→|←1641白→| 该扫描行MH码为: 填充 EOL 数据 数据 EOL 数据 页尾 6个EOL RTC

≥T

??

17白

5黑

55白

10黑

1600白 +

41白

EOL

101011 | 0011 | 01011000 | 0000100 | 010011010 | 00101010 | 000000000001 | 原一行为1728个像素,用“0”表示白,用“1”表示黑,需要1728位二元码。现MH 码这行只需用54位二元码元。可见,这一行数据压缩比为1728:54=32,压缩效 率很高。

F(0)
0 P(0) F(0) 0 P(00)

F(1)

算术编码
P(1) 1 F(1) P(01)

F(01)

F(01) P(010)

F(011) P(011) F(011) F(0111) P(0111) F(0111) P(01110) F(01111) P(01111)

F(1)

F(1)

信源符号序列的累积分 布函数F(s)及对应的区间
k ?1 i ?1

P(0110)

F(1)

F (ak ) ? ? P(ai ), F (0) ? 0, F (1) ? P(0)

香农提出信源序列的累积概率的概念。 P.Elias将累计概率分布函数用于信源符号, 得到信源序列的累积概率分布函数的递推 算法。 J .Rissanan改进递推算法,得以实用。

函数的区间?0,分成许多互不重叠的小区间,每个 1?

从香农 ? 非诺 ? 埃利斯编码方法中,是将累积分布

信源符号对应于各个小区间,每一小区间的长度等 于这个信源符号的概率分布,在此小区间内取一点, 取该点的二进位小数点后l位作为这个信源符号的码 字。 把这基本思想运用到信源符号序列中来,能计算出 信源符号序列的累积分布函数,使每个符号序列对 应于累积分布函数上不同区间,再在区间内取一点, 将其二进位小数后l位作为这个符号序列的码字,只 要这些区间不重复,就可以编得即时码。

算术码主要的编码方法正是计算输入信源符号序列所 设信源符号集A ? ?a1 , a2 , ? , aq ? ,其相应的概率分布为 p ?ai ?, p ?ai ? ? 0。可知信源符号的累积分布函数
k ?1 i ?1

对应的区间。如何找出信源符号序列所对应的区间。

F ?ak ? ? ? p ?ai ? 。该累积分布函数为每台阶的下届值, 则其区间为?0, 1? 显然由上式可知:F ?a1 ? ? 0, F ?a2 ? ? p ?a1 ?, 当A ? ?0,1?二元信源时,则F ?0 ? ? 0,F ?1? ? p ?0 ? F ?a3 ? ? p ?a1 ? ? p ?a2 ?, ?

算术编码计算
F ?ak ? ? ? p?ai ?, F ?0 ? ? 0, F ?1? ? p ?0 ?;
i ?1 k ?1

?0,1? ? ?0, F ?1?? ? ?F ?1?,1? ?0, F ?1??的宽度为A?0? ? p?0? 对应信源符号0 ?F ?1?,1?的宽度为A?1? ? p?1? 对应信源符号1 F ? s 0 ? ? F ?s ? A?s 0 ? ? A?s ?? p?0 ? 计算的递推公式 F ?s1? ? F ?s ? ? A?s ?? p?0? A?s1? ? A?s ?? p?1? ? A?s ? ? A?s 0 ?

初始条件

算术编码计算
由此可得二元信源符号序列的累积分布函数的递推公式 F ?sr ? ? F ?s ? ? p ?s ?? F ?r ?? r ? ?0,1? 区间宽度的递推公式 A?sr ? ? p ?sr ? ? p ?s ?? p ?r ? 例:序列为"0111",则s ?"011" F ?s1? ? F ?s ?"011"? ? p ?011?? F ?1? ? F ?"011"? ? p ?011?? p ?0 ?

? F ?s ?"01"? ? p ?01?? p ?0 ? ? p ?011?? p ?0 ? ? 0 ? p ?00 ? ? p ?010 ? ? p ?0110 ? 其对应区间宽度

? F ?s ?"0"? ? p ?0 ?? p ?0 ? ? p ?01?? p ?0 ? ? p ?011?? p ?0 ?

A?s1? ? A?s ?"011"?? p ?1? ? p ?011?? p ?1? ? p ?0111 ?

F(0)
0 P(0) F(0) 0 P(00)

F(1)

算术编码
P(1) 1 F(1) P(01)

F(01)

F(01) P(010)

F(011) P(011) F(011) F(0111) P(0111) F(0111) P(01110) F(01111) P(01111)

F(1)

F(1)

信源符号序列的累积分 布函数F(s)及对应的区间
k ?1 i ?1

P(0110)

F(1)

F (ak ) ? ? P(ai ), F (0) ? 0, F (1) ? P(0)

算术码

F的计算方法:F ?s ? ? ? p? y ? ?
y?s

s左侧的所有节点 T

? p?T ?

0

1

0

1

0

1 0 1 s 0 1

T1

T2

T3

T4

F ? 0111? ? p ?T1 ? ? p ?T2 ? ? p ?T3 ? ? p ? 00? ? p ? 010? ? p ? 0110?

根据累积分布函数我们的编码任务
? 1 ? l ? ?log ? p ? x? ? ? F ? s ? ? 0.10110001 1 p?s? ? 7 l ?3 C ? 0.110 ? 有位 ?
1 C ? F ?s? ? l 2 C ? F ? s ? ( 尾 0) ? p?s? ? 1 2l

1 F ? s ?+p ? s ? ? F ? s ?+ l ? C 2 ? C ? ? F ? s ? , F ? s ?+p ? s ? ? ?

序列11111100的编码过程
输入 符号 空 1 1 1 1 1 1 0 0 P(s)=A(s) 1:初始长度值 0.11:右移两位 0.1001 0.011011 0.01010001 0.0011110011 0.001011011001 0.00001011011001 0.0000001011011001 0.01 0.0011 0.001001 0.00011011 0.0001010001 A(s)?p(0) F(s) 0:累积函数值 L(s) 0 1 1 2 2 3 3 5 7 0.1 0.1 0.11 0.11 0.111 0.111 0.11011 0.1101010 C

+ + = = + = + = +

0.01 0.0111 0.100101 0.10101111 0.1100001101 0.110100100111 0.110100100111 0.110100100111

= + 0.000011110011 =
0.00001011011001 0.0000001011011001

S={0,1}, P(0)=1/4, P(1)=3/4,对于二元序列s=11111100做算术编码。 P(s=11111100)=P2(0)P6(1)=(3/4)6(1/4)2 F(s)=P(0)+P(10)+P(110)+P(1110)+P(11110)+P(111110) =1-P(11111111)-P(11111110)-P(11111101)-P(11111100) =1-P(111111)=1-(3/4)6=0.82202=>0.110100100111 得C=0.1101010 得s的码字为 1101010

LZ码
设q=4,信源序列为: a0 a0 a2 a3a1a1a0 a0 a0 a3a2 根据前面分段规则,可以分段为
a0 , a0 a2 , a3 , a1 , a1a0 , a0 a0 , a3a2
段号 1 2 3 4 5 6 7 短语(符号串) a0 a0a2 a3 a1 a1a0 a0a0 a3a2

共7段。其编码字典表。因为字典表中共有7段, 所以段号需用3位二元码符号,而符号集q=4, 所以每个符号需用2位二元码符号,即 a0??00 a1 ?? 01 a2 ?? 10 a3 ?? 11 可得次序列的码符号序列为: 00000001100001100001100000010001110

LZ码
1。LZ码是一种基于字典的编码方法。其基本算法是,将长度不同的 符号串编成一个个新的短语(单词),形成短语字典的索引表。 2。编码就是将输入序列分成不同的段,分段的规则是尽可能取最少 个连着的信源符号,并保证各段都不相同。开始时,先取一个符号作 为第一段,然后再继续分段,若出现与前面相同符号时,就再取紧跟 后面的一个符号一起组成一个段,以使与前面的段不同。有了许多段 后,再分段时就应查看有否与前面段的短语相同,若有重复就添加符 号后使与前面的段不同,直至信源符号序列结束。 3。这样,不同的段内的信源符号可看成一短语,可得不同段所对应 的短语字典。 4。码字由段号加后面一个符号组成。

5。若组成二元码,段号所需码长 ? log C (n) ? , ? ? 每个符号所需码长为 ? log q ? ? ?

有噪信道编码
? 在有噪信道中传输消息是会发生错误的, 为了减少错误,提高可靠性,首先就要分 析错误概率与哪些因素有关,有没有办法 加以控制,能控制到什么程度等。 ? 显然错误概率与信道统计特性有关,但通 信过程一般并不是在信道输出端就结束, 还要经过译码过程才到达消息的终端(信 宿),因此译码过程和译码规则对系统的 错误概率影响很大。

有噪信道编码

? 错误概率与译码规则 ? 错误概率与编码方法

译码规则对错误概率影响的例题
0 0.1 0 二元对称信道,其输入符号位等概率分布。 译码规则1:接收到符号“0”,译成发送的符号为“0” 接收到符号“1”,译成发送的符号为“1” 1
(0) 因此当发送符号“0”时,译对的概率为0.1,译错的概率为pe ? 0.9

0.9
0.9 1 0.1

当发送符号“1”时,译对的概率为0.1,译错的概率为pe(1) ? 0.9 1 (0) 1 (1) 则根据条件(等概率),平均错误概率为 pe ? ? pe ? pe ? ? ? 0.9 ? 0.9 ? ? 0.9 2 2

p (0) 译码规则2:接收到符号“1”,译成发送的符号为“0” e ? 0.1
接收到符号“0”,译成发送的符号为“1”pe ? 0.1
(1)
(0) 因此当发送符号“0”时,译对的概率为0.9,译错的概率为pe ? 0.1
(1) 当发送符号“1”时,译对的概率为0.9,译错的概率为pe ? 0.1

则根据条件(等概率),平均错误概率为

1 (0) 1 (1) pe ? ? pe ? pe ? ? ? 0.1 ? 0.1? ? 0.1 2 2

由此可见,错误概率既与信道的统计特性有关,也与译码规则有关

译码规则的定义
设离散单符号信道的输入符号集为:A ? ?a1 , a2 ,..., ar ?, 输出符号集为:B ? ?b1 , b2 ,..., bs ?, 转移概率为:p ? b j | ak ? , k ? 1, 2,..., r , j ? 1, 2,..., s 确定一个惟一的输入符号ak 与其对应,即 F (b j ) ? ak , k ? 1, 2,..., r , j ? 1, 2,..., s。 由于s个输出中每一个都可以译成r个输入符号中的任何 一个,所以共有rs种译码规则可供选择,选择译码规则 的准则就是使平均错误概率为最小。

?

?

制定译码规则就是设计一个函数F (?)它的每一个输出符号b j

译码规则的定义
在确定了译码规则F (b j ) ? ak , k ? 1, 2,..., r , j ? 1, 2,..., s后 收到符号b j 条件下译码的条件正确概率为p ? ak | b j ? , 令p ? e | b j ? 为条件错误概率,其中e表示除了F (b j ) ? ak以外 的所有输入符号的集合,则

p ? e | b j ?=1-p ? F (b j ) | b j ? =1-p ? ak | b j ? ? ? ? ?

定义1
定义:经过译码后的平均错误概率pE 定义为 pE ? ? p ? b j ? p ? e | b j ?。
s j ?1

它表示经过译码后平均接收到一个符号产生的错误大小。 如何设计译码规则F ? b j ? ? ak , 使pE 最小呢?由pE的定义 可以看出,只要使条件错误概率p ? e | b j ? 最小即可,这 等价于p ? F ? b j ? | b j ? 为最大。 ? ?

p ? e | b j ?=1-p ? F (b j ) | b j ? =1-p ? ak | b j ? ? ? ? ?

定义2
定义:选择译码函数F ? b j ? ? a* , a* ? A, b j ? B使之满足条件 p ? a* | b j ? ? p ? ak | b j ? , ak ? A, ak ? a*。......(1) 也就是说,如果采用这样一种译码规则函数,它对于每一个 输出符号均译成具有最大后验概率的那个输入符号,则信道 的错误概率就能最小,这种译码规则称为最大后验概率准则 或最小错误概率准则。

p ? a | b j ? ? p ? ak | b j ? , ak ? A, ak ? a 。
* *

由于我们一般是已知信道的转移概率p ? b j | ak ? 与输入符号的 先验概率,所以根据贝叶斯定律,(1)式可以写成 p ? b j | a* ? p ? a* ? p ?bj ? ? p ? b j | ak ? p ? ak ? p ?bj ? , ak ? A, ak ? a* , b j ? B

一般p ? b j ? ? 0,b j ? B,这样,最大后验概率准则就可以表示 为:选择译码函数 F ? b j ? ? a* , a* ? A, b j ? B 使其满足 p ? b j | a* ? p ? a* ? ? p ? b j | ak ? p ? ak ? , ak ? A, ak ? a* , b j ? B

定义3
定义:选择译码函数 F ? b j ? ? a , a ? A, b j ? B
* *

使满足 p ? b j | a* ? ? p ? b j | ak ? , ak ? A, ak ? a *。 这样的译码规则称为最大拟然译码准则。


有一离散单符号信道,信道矩阵为P,根据这样一个信道矩阵我们可以设计译码 规则A和B。

b1 b2 P? a1 a2 a3

b3

?0.5 0.3 0.2 ? ?0.2 0.3 0.5? ? ? ? 0.3 0.3 0.4 ? ? ?

A : F ? b2 ? ? a2 F ? b3 ? ? a3

F ? b1 ? ? a1

B : F ? b2 ? ? a3 F ? b3 ? ? a2

F ? b1 ? ? a1

最大拟然译码准则
s s j ?1 j ?1

p ? b j | a * ? ? p ? b j | ak ?

pE ? ? p ? b j ? p ? e | b j ? ? ? p ? b j ? 1 ? p ? F ? b j ? | b j ? ? ? ? ? p ?b j ? ? ? p ? F ?b j ? | b j ? p ?b j ? ? ?
s s j ?1 j ?1

?

?

? 1 ? ? p ? F ? b j ? , b j ? ? 1 ? ? p ? a* , b j ? ? ?
s s j ?1 s j ?1

? ?? p ? b j | ak ? p ? ak ? ? ? p ? b j | a* ? p ? a* ?
r s k ?1 j ?1 r j ?1

根据最大拟然译码准则,从信道 矩阵的转移概率中去选择译码函 数,就是说收到bj后,译成矩阵的 第j列中最大那个数值所对应的信 源符号,当输入符号的先验概率 p(ak)为等概率分布时,最大后验 概率准则与最大拟然译码准则等 价。

??

k ?1 j ?1 F b j ? a*

?

s

p ? b j | ak ? p ? ak ?

? ?

最大拟然译码准则本身,不再依赖先验概率p(ak), 当先验概率为等概率分布时,它会使平均错误概率 pE最小,如果先验概率不相等或不知道时,仍可以 采用这个准则,但不一定能使pE最小。

我们可以把平均错误概率pE写成信道转移概率和输入概率的函数。

b1 b2 P? a1 a2 a3

b3

?0.5 0.3 0.2 ? ?0.2 0.3 0.5? ? ? ? 0.3 0.3 0.4 ? ? ?

可见pE? ? pE

A : F ? b2 ? ? a2 F ? b3 ? ? a3
pe(1) ? 1 ? p ? b1 | a1 ? ? 1 ? 0.5 ? 0.5 pe(2) ? 1 ? p ? b2 | a2 ? ? 1 ? 0.3 ? 0.7 pe(3) ? 1 ? p ? b3 | a3 ? ? 1 ? 0.4 ? 0.6 则平均错误概率 1 3 (k ) 1 pE? ? ? pe ? ? 0.5 ? 0.7 ? 0.6 ? ? 0.6 3 k ?1 3

F ? b1 ? ? a1

B : F ? b2 ? ? a3 F ? b3 ? ? a2

F ? b1 ? ? a1

pe(1) ? 1 ? p ? b1 | a1 ? ? 1 ? 0.5 ? 0.5 pe(2) ? 1 ? p ? b3 | a2 ? ? 1 ? 0.5 ? 0.5 pe(3) ? 1 ? p ? b2 | a3 ? ? 1 ? 0.3 ? 0.7 则平均错误概率 1 3 (k ) 1 pE ? ? pe ? ? 0.5 ? 0.5 ? 0.7 ? ? 0.567 3 k ?1 3

b1 b2 P? a1 a2 a3

b3

如果输入不是等概率分布,其概率分布为:

?0.5 0.3 0.2 ? p a ? 1 , p a ? 1 , p a ? 1 ?0.2 0.3 0.5? ? 1 ? 4 ? 2 ? 4 ? 3 ? 2 ? ? 根据最大拟然译码准则仍可选择译码函数B, ? 0.3 0.3 0.4 ? ? ? 计算其平均错误概率。
平均错误概率 1 1 1 ( pE?? ? ? p ? ak ? pe k ) ? ? 0.5 ? ? 0.5 ? ? 0.7 ? 0.6 4 4 2 k ?1
3

pE?? ? pE???

B : F ? b2 ? ? a3 F ? b3 ? ? a2

F ? b1 ? ? a1

? 0.125 0.075 0.05 ? 根据p ? ai ? p ? b j | ai ? 我们可以写出联合 ? P ? ai b j ? ? ? ? 0.05 0.075 0.125 ? 概率矩阵p a b 采用最小错误概率译 ? i j? ? ? ? ? ? 0.15 0.15 0.2 ? ? ? 码准则,可得译码函数为C

C : F ? b2 ? ? a3 F ? b3 ? ? a3
3

F ? b1 ? ? a3

(1) pe ? p ? b1 | a1 ? ? p ? b2 | a1 ? ? p ? b3 | a1 ? ? 1 (2) pe ? p ? b1 | a2 ? ? p ? b2 | a2 ? ? p ? b3 | a2 ? ? 1 (3) pe ? 1 ? p ? b1 | a3 ? ? p ? b2 | a3 ? ? p ? b3 | a3 ? ? 1 ? 1 ? 0

( pE??? ? ? p ? ak ? pe k ) ? 0.5 k ?1

所以输入不是等概率分布时最大拟然译码准则的 平均错误概率不是最小

非诺不等式
? 平均错误概率PE与译码规则(译码函数)有关,而译码规则又由信道 特性来决定,由于信道中存在噪声,导致输出端发生错误,并使接收 到输出符号后,对发送的是什么符号还存在不确定性。可见PE与信道 疑义度H(X|Y)是有一定关系的,因此可得以下的非诺不等式(重要)

H ? X | Y ? ? H ? PE ? ? PE log ? r ? 1?
虽然PE与译码规则有关,但是不管采用 什么译码规则该不等式都是成立的。 H(PE)是错误概率的熵,表示产生错误的 不确定性。非诺不等式告诉我们:接收 到Y后关于X的平均不确定性可分为两部 分,第一部分是指接收到Y后是否产生 PE错误的不确定性H(PE),第二部分表示 当错误PE发生后,到底是哪个输入符号 发送而造成错误的最大不确定性为:
PE log ? r ? 1?
当信源、信道给定,信道疑义度就给定了译 码错误概率的下界。
H ? X |Y ?

H ? PE ? ? PE log ? r ? 1?

Log r Log(r-1)

PE 和H ? X | Y ?的作用区域
PE

r ?1 r

1

非诺不等式曲线图

错误概率与编码方法
? 消息通过有噪信道传输时会发生错误,而 错误概率与译码规则有关,但当信道给定 时,无论采用什么译码规则,PE总不会等 于或趋于零,要想进一步减少错误概率PE, 必须考虑信道的编码方法。

0

p

p p

0

译码规则:F(0)=0, F(1)=1 则在输入等概率条件下平均错误概率为

pe ?
p

1

1

1 (0) 1 (1) pe ? pe ? ? ? 0.01 ? 0.01? ? 0.01 ? 10?2 ? 2 2

10?6 ~ 10?9

p ? 0.99

p ? 0.01

为了降低错误概率,在发送端把消息重复发几遍,就可使 接受端接受消息时错误减小,从而提高通信的可靠性。
0 ? 000,1 ? 111 信道输入端有两个码字: , 。 000 111 输出端,由于信道干扰可能发生错误,则有8种可能输出

?1=000,? 2=001,?3=010,? 4=011, ?5=100,? 6=101,? 7=110,?8=111, ?1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7
P ? ?1

?8
pp 2 p p
2

?8

? p3 ? ? p3 ?

p p pp 2

2

p p pp 2

2

pp 2 p p
2

p p pp 2

2

pp 2 p p
2

p3 ? ? 3 p ? ?

根据最大拟然译码规则,得重复码的译码函数为: F ? ?1 ?=?1,F ? ? 2 ?=?1,F ? ? 3 ?=?1,F ? ? 4 ?=? 8 F ? ? 5 ?=?1,F ? ? 6 ?=? 8,F ? ? 7 ?=? 8,F ? ? 8 ?=? 8 则
(1) pe ? 1 ? p ? ?1 | ?1 ? ? p ? ? 2 | ?1 ? ? p ? ? 3 | ?1 ? ? p ? ? 5 | ?1 ?

? 1? p ? p p ? p p ? p p ? 1? p ? 3 p p
(8) pe ? 1 ? p ? ? 4 | ? 8 ? ? p ? ? 6 | ? 8 ? ? p ? ? 7 | ? 8 ? ? p ? ? 8 | ? 8 ?

3

2

2

2

3

2

? 1? p p ? p p ? p p ? p ? 1? p ? 3 p p 因此在输入等概率分布时
3 2 1 (1) (8) pE ? ? pe ? pe ? ? 1 ? p ? 3 p p ? 2.98 ? 10 ?4 2 显然,若重复更多次,一定可以进一步降低错误概率。

2

2

2

3

3

2

n=5时pE ? 10 ?5;n=7时pE ? 4 ? 10 ?7 ; n=9时pE ? 10 ?8;n=11时pE ? 5 ? 10 ?10

码率的定义
log M 定义:把编码后的消息传输率表示为:R ? n 若传输每一码符号平均需t秒钟,则定义编码后每一秒 log M 传输的信息量为:Rt ? 。 nt 其中M 是输入符号的个数, M 表示符号集在等概率条 log 件下每个符号携带的平均信息量,n是编码后码字长度。
1 1 1 当n ? 1, M ? 2时,R ? 1, Rt ? ;当n ? 3, M ? 2时,R ? , Rt ? t 3 3t 1 1 1 1 当n ? 5, M ? 2时,R ? , Rt ? ;...当n ? 11, M ? 2时,R ? , Rt ? 5 5t 11 11t

PE与R的关系
pE
1
10?2

pE是关于R单调减少的
简单重复编码

10

?4

10?6 10?8 10?10 10?12 10?14

香农定理给出的极限

?
1
C 1/ 3 1/ 5 1/ 7 1/ 9 1/11

R

输入符号个数对错误概率的影响
在一个二元信道要重复发送n遍后再编码实际上可以看成 是输入端信源的n次扩展信源的编码问题,此时输入端共 有2n 个符号序列可能作为消息符号,现仅选择其中的M 个 作为消息符号传递,显然M 对平均错误概率pE 和消息传输 率R会产生影响。下面来分析:
前例中:

n ? 3, M ? 2时,等概率分布,采用最大拟然译码规则 1 pE ? 2.98 ?10 , 而消息传输率为:R ? 3
?4

如果当n ? 3时,取M ? 4,共有C84 ? 70种不同的选择方法,不同的选择方法 导致不同的编码方法,其平均错误概率也不同。

?1=000,? 2=001,? 3=010,? 4=011,? 5=100,? 6=101,? 7=110,? 8=111 ?1=000,? 2=001,?3=010,? 4=011,?5=100,? 6=101,? 7=110,?8=111
假定选择M ? 4时的一种选法:

?1=000,? 4=011,? 6=101,? 7=110; pE ? 2 ?10?2 , R ?
?1 ? 2 ?1 P ? ?4 ?6 ?7 ?3 ? 4 ?5
p p
2

?6

?7

?8
pp 2

log 4 2 ? 3 3

? p 3 p 2 p p 2 p pp 2 ? ? pp 2 p 2 p p 2 p p 3 ? ? pp 2 p 2 p p 3 pp 2 ? ? pp 2 p 3 p 2 p pp 2 ?

p3 ? ? 2 3 2 2 p pp pp p p? ? 2 3 2 2 p p p pp p p? ? 2 2 3 2 p p pp p p p ? ? pp 2
log 4 2 ? 3 3

?1=000,? 2=001,?3=010,?5=100; pE ? 2.28 ?10?2 , R ?
当M ? 8时; pE ? 3 ?10?2 , R ? log8 ?1 3

纠错码的基本思想
? 纠错编码的目的就是引入乘余度。编码就 是在传输的信息码元之后增加一些多余的 码元(通称为效验码元),以使信息损失 或错误发生后仍能在接受端回复。根据信 息码元和效验码元之间不同的关系,纠错 码按结构分类达致如图:

纠错码的分类
纠错码 非线形码 卷积码 循环码 线形码 分组码 非循环码

纠随机 错误码

纠突发 错误码

纠随机和突 发错误码

纠同步 错误码

纠错码按结构的分类图

纠错码的分类简介
1.线形码:信息码元与效验码元之间呈线形关系 2.非线形码:信息码元与效验码元之间不存在线形关系 3.分组码:信息序列以每k个码元分组,然后把每组k个信息 元按一定规律产生r个多余的效验元,输出序列每组长n= k+r,则每一码字的r个效验元只与本码字的k个信息位有 关,与别的码字的信息位无关,记为分组码(n,k) 4.卷积码:信息序列以每k0个码元分段,编码器输出该段的 效验元r=n- k0 不但与本段的k0个信息位有关,而且还与 其前面m段的信息位有关,故记为卷积码(n, k0,m) 5.分组码又可以分为循环码和非循环码: 5.1.循环码:该码的特点是,若将其全部码字分成若干组, 则每组中任一码字的码元循环移位后仍是这组的码字 5.2.非循环码:任一码字中码元的循环移位不一定再是该码 的码字

线性分组码的基本概念

编码是在信道输入端2n 个n长的二元序列中找一组2k 个码字 使码字的r ? n ? k 个效验元与其k 个信息元之间满足一定的 线性关系,并使码中码字间最小距离最大,而译码则采用 最大拟然译码准则,即最小汉明距离译码准则。

汉明距离
定义:设? i 和? j是由编码字符表 ?0,1?中元素 组成的长度为n的码字符号列:

? i=? i1? i 2 ...? in;? j=? j1? j 2 ...? jn。其中? ik 和? jk ? ?0,1?
则? i 和? j 之间的汉明距离定义为 D ?? i , ? j ? ? ? ? ik ? ? jk
n k ?1

?表示模二和运算,即 1 ? 1=0 1 ? 0=1 0 ? 1=1 0 ? 0=0

汉明权重与最小距离
定义:码字的汉明权重是指码字中含非零码元的个数 令? i=? i1? i 2 ...? in,其中? ik ? ?0,1? 则? i 汉明权重定义为: W ?? i ? ? ? ? ik
k ?1 n

因此得码字? i与? j 之间的距离 D ? ? i , ? j ? ? W ?? i ? ? j ? 在二元码C中,任意两个码字的汉明距离最小值称为 码C的最小距离 Dmin ? min D ? Ci , C j ? | Ci ? C j , Ci , C j ? C

?

?

错误图样
在二元无记忆n次扩展信道中,差错的形式也可以用二元序列 来描述。这样差错的描述称之为错误图样。 E ? ?en ?1en ? 2 ...e1e0 ? , ei ? 0或1。 当ei ? 0时表示该码元没发生错误, 当ei ? 1时表示该码元发生了错误。 二元信道的错误总是“0” “1”或“1” “0” ? ? 令R表示输出端接收到的二元序列,则 R ? E ?C ? E ? C ? R C ? 0110000 ? 0100000 R ? E ? C ? 0000000 ? 0100000 ? 0100000 E ? C ? R ? 0110000 ? 0100000 ? 0010000

设二元对称信道中,p为错误概率( p ? 1/ 2), p ? 1 ? p为正确 传输概率,则n次无记忆扩展信道中,错误图样 E出现的概率 P?E? ? p
n ?W ? E ?

p

W ?E?

发生一位错误:。。。W ? E1 ? ? 1;。。。P ? E1 ? ? p n ?1 p 发生二位错误:。。。W ? E2 ? ? 2;。。。P ? E2 ? ? p n ? 2 p 2 ... 发生k位错误:。。。W ? Ek ? ? k ;。。。P ? Ek ? ? p n ? k p k ... 全错。。。。。。。W ? En ? ? n;。。。P ? En ? ? p n 因为p ? 1/ 2,所以发生一位错误、二位错误的概率大于 发生多位错误的概率

分组码纠正随机错误能力与码的最小距离的关系

重复码(3,1)中码的最小距离 d min ? 3,即000与111的距离。 两个码字在传输后发生一位码 元错误的接受序列形成两个互 不相交的子集,因此根据最小 距离译码准则就能纠正发生一 位码元的随机错误。若传输中 发生二位或三位错误,则就进入 另一个码字对应的正四面体中, 就无法纠正。
(000) (010)
(100)

(110)

(111)

(101)

(011)

(001)

由以上分析得出: 1.要发现(检测)e个随机错误,则要求码的最小距离d min ? e ? 1 2.要纠正e个随机错误,则要求d min ? 2e ? 1 3.要纠正e个随机错误同时检测( ? e)个错误,则要求d min ? e ? f ? 1 f

1 c1 e

1
e c2

c1
e

e

e e 1 1

c2

ck …… c3 c c1 c2 e c3 e

?000,111?的最小距离dmin=3 ? e ? 1

(7,4)汉明码
? (7,4)汉明码其码长n=7,信息元k=4,效验元r=n-k=3. 长为3的二元序列共有8个,我们将其中7个非零 序列按列排成如下矩阵
称H ? 7, 4 ? 为效验矩阵, 设码字C ? ? c6 c5c4 c3c2c1c0 ? HC T ? 0T 其中0=(000), ? c3 ? c2 ? c1 ? c0 ? 0 ? ? c5 ? c4 ? c1 ? c0 ? 0 ?c ? c ? c ? c ? 0 ? 6 4 2 0

H ? 7,4?

? 0 0 0 1 1 1 1? ? ? 0 1 1 0 0 1 1? ? ? ?1 0 1 0 1 0 1? ? ?

方程组表示了码元之间的线性关系。 信息元k ? 4, 所以不同码字有M ? 2k ? 16 令码字C中前4个码元为信息元,即得 16个码字

0000000 0100101 1000011 1100110 0001111 0101010 1001100 1101001 0010110 0110011 1010101 1110000 0011001 0111100 1011010 1111111

? c3 ? c2 ? c1 ? c0 ? 0 ? ? c5 ? c4 ? c1 ? c0 ? 0 ?c ? c ? c ? c ? 0 ? 6 4 2 0

特点:16个码字是所有码长为7的二元序列中的一个封闭子集 它的封闭性表现为:ci , c j ? C ; ci ? c j ? ck ? C 码的最小距离等于非零码字的最小权重,即 d min ? min W (Ci )
? 0 0 0 1 1 1 1? ? 0 1 1 0 0 1 1? ? ? ?1 0 1 0 1 0 1? ? ?

因为 min W (Ci )=3,效验矩阵中各列都不相同,

任意二列之和不等于000,但任意二列之和一定 等于矩阵中某一列,所有码字的最小权重为3。

0000000 0100101 1000011 1100110 0001111 0101010 1001100 1101001 0010110 0110011 1010101 1110000 0011001 0111100 1011010 1111111

?1 0 ?0 1 G?? ?0 0 ? ?0 0 生成矩阵

0 0 0 1 1? 0 0 1 0 1? ? 0 1 1 1 1? ? 1 0 1 1 0?

在16个码字中只有k ? 4个码字是独立的,其他码字可由这4个 码字线性组合而来,将这4个码字按行排列成右上矩阵 满足 ? c6 c5c4c3 ? G ? ? c6c5c4c3c2c1c0 ? 可得HGT ? 0T ......或GH T ? 0。其中0k ?( n ?k )是4 ? 3矩阵
?1 ?0 ? 0 0 0 1 1 1 1? ?0 ? ? T H ? ? ?0 1 1 0 0 1 1? ?0 G ? ? ?1 0 1 0 1 0 1? ? 0 ? ? ? ?1 ?1 ? 0 0 0? 1 0 0? ? 0 0 1? ? 0 1 0? 1 1 1? ? 0 1 1? 1 1 0? ?

我们可以由下式生成全体编码。

? c6c5c4c3 ? G ? ? c6c5c4c3c2c1c0 ?

若信道中发生随机错误,错误图样为E , 接收序列R ? E ? C。 得HRT ? HC T ? HE T ? HE T ? OT ...(*) 设E ? ? e6e5e4e3e2e1e0 ? ? ? 0010000 ?即e4=1 表示码字中第五位码元发生错误,代入(*)有
?0 ? ?0 ? ? ? ?0 0 0 1 1 1 1? ?0 ? ?1 ? ? ? HE T ? ?0 1 1 0 0 1 1? ?0 ? = ?0 ? ? ? ? ? ?1 0 1 0 1 0 1? ?1 ? ?1 ? ? ? ? ? ? ? ?0 ? ?0 ? ? ?

? s2 ? 由此可见:HE T ? S T ? S T ? ? s1 ? , ? ? ? s0 ? ? ? S 称为伴随式由矩阵H 进行译码, 根据所得的伴随式就可判断码字 中哪一位码元发生错误,就可以 纠正一位随机错误。

汉明码有r 位效验元,就有2r ? 1个不同的非全零向量,将其按列 排成矩阵就得到效验矩阵H,有了矩阵H 就可以生成码字和进行 译码了。汉明码的信息传输率 k 2r ? 1 ? r r R? ? ? 1? r r n 2 ?1 2 ?1 r 当r很大时, r 很小,所以信息传输率R ?(比特/二元码) 1 2 ?1 汉明码是一种高效的纠正一位随机错误的分组码。汉明码可以 方便的用移位寄存器等硬件或计算机软件来实现。 以上只是以汉明码为例说明线性分组码的基本思想。线性分组 码可以用群、环、域和线性空间等数学工具进行讨论。

信道及信道容量
? 信道是信息传输的通道,是信息论中与信 源并列的另一个主要研究对象,研究信道 的一个重要问题是信道的容量,它表示信 道可以传输的最大信息量。

信道的数学模型及分类
? 在信息论中,信道是信息传输的通道,在实际通信中所利 用的各种物理通道是信道的最典型的例子,如光缆,光纤, 电波传布的空间,载波线路等。 ? 由于信道是传输信息的媒介或通道,它有输入和输出,所 以也可把信道看成是一种变换。由于干扰和噪声的存在, 这种变换不是由确定的函数关系来表示,而是由统计依赖 关系来表示,因此可以抽象地将信道用下图所示的模型来 描述。
输入/输出统计关系 输入是X (随机过程) 信道 输出是Y (随机过程)

信道可以按其输入/输出信号的数学特点及输入/输出信号之间关系 的数学特点进行分类 1.信道按其输入/输出信号在幅度和时间上的取值是离散或连续来 划分 (1)离散信道:I/O的随机序列的取值都是离散的信道, (2)连续信道:I/O的随机序列的取值都是连续的信道,

(3)半离散或半连续信道:

(4)波形信道:I/O都是一些时间上连续的随机信号x(t)和y(t),且随 时间连续变化,一般可用随机过程来描述其I/O.无论何种随机过程, 只要有某种限制(如限频或限时),就可以分成时间(空间)离散随机 序列,由于实际信道的带宽总是有限的,所以输入信号和输出信 号总可以分解成时间离散的随机序列来研究。

2.信道按其输入/输出之间关系的记忆性来划分 (1)无记忆信道:信道的输出只与信道该时刻的输入有关与其他时刻 的输入无关 (2)有记忆信道:信道的输出不但与信道现时刻的输入有关,而且还 与前时刻的输入有关

实际信道一般都是有记忆的,信道中的记忆现象来源于物理信道 中的惯性,如电缆信道中的电感电容、无线信道中电波传布的衰 落现象等。 3.信道按其输入/输出之间的关系是否是确定关系来划分 (1)有噪声信道:信道中存在某种程度噪声,因此信道输入/输出之 间的关系是一种统计依赖关系,而不是确定关系 (2)无噪声信道:信噪比很小,可以忽略。此时输入/输出之间的关 系理想化为确定关系。

离散无记忆信道及其容量
设离散信道的输入空间A ? ?a1 , a2 ,..., ar ? , 输出空间B ? ?b1 , b2 ,..., bs ? , 信道输入序列为X=X 1 X 2 ... X N , 其取值为X=x1 x2 ...xN , xn ? A, n ? 1, 2,..., N ; 相应的输出序列为Y =Y1Y2 ...YN , 其取值为Y=y1 y2 ... y N , yn ? B, n ? 1, 2,..., N , 信道的特性可用转移概率 p ? y1 y2 ... y N | x1 x2 ...xN ? 来描述,信道的数学模型可表示为 X ,p ? y1 y2 ... y N | x1 x2 ...xN ?,Y

当信道输入序列为X 1 X 2 ... X N时, 信道输出序列为Y1Y2 ...YN ,

则信道的输入输出之间的互信息为I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? 这一互信息是从信道输出端可以得到的关于输入端输入 序列的信息量,因此也就是通过信道可以传输的信息量, 显然,作为信息传输的通道,希望此信息量尽可能大, 所以有以下定义: 定义:称 C ? lim 1 N ?? N

maxI ? X X
1 p( x)

2

... X N ; Y1Y2 ...YN ?

为离散信道的容量,其中p ( x)是输入序列 X 1 X 2 ... X N的取值X=x1 x2 ...xN , xn ? A, n ? 1, 2,..., N的概率, 最大值是在输入序列的全部可能的概率分布下取得。

定义:若离散信道对于任意长为N的输入、输出序列 都有 p ? y1 y2 ... y N | x1 x2 ...xN ?=? p ? yn | xn ?
n ?1 N

则称该信道为离散无记忆信道,进一步若对任意 ak ? A, b j ? B及正整数m, n, 有 p ? yn ? b j | xn ? ak ? ? p ? ym ? b j | xm ? ak ? ? p ? b j | ak ? 则称此信道是平稳的。

对离散无记忆信道,在任何时刻信道的输出只与此时信道的 输入有关,而与以前的输入无关,平稳信道的转移概率不随 时间变化,因而平稳的离散无记忆信道可用输入输出空间的 转移概率p ? b j | ak ? 描述,其数学模型为
j

? A, p ? b

| ak ? , B

?

对于平稳的离散无记忆信道,由转移概率p ? b j | ak ? 所组成的矩阵 ? p ? b1 | a1 ? ? ? p ? b1 | a2 ? Q ? ? p ? b j | ak ? ? ? r?s ? ? ? ? ? ? p ? b1 | ar ? ? 称为转移概率矩阵。 p ? b2 | a2 ? ? ? p ? b2 | ar ? ? p ? b2 | a1 ? ? p ? bs | a1 ? ? ? p ? bs | a2 ? ? ? ? ? p ? bs | ar ? ? ?

例:下图给出了离散无记忆信道的两个最简单的例子,其中 信道的输入空间、输出空间以及转移概率均标识在图中
a1
1-?

?

b1

a1

1-?

?

b1

a2

?
1-?

b2

a2

?
1-?

b3 b2

(a)二元对称信道

(b)二元删除信道

? ? ?1 ? ? Qa ? ? ? 1? ? ? ? ?

?1 ? ? 0 ? ? Qb ? ? ? ?0 1 ? ? ? ?

定理
定理1:设离散信道的输入序列为X 1 X 2 ... X N , 输出序列为 Y1Y2 ...YN , 若信道是离散无记忆的,则 I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? ? ? I ? X n ; Yn ?
n ?1 N

定理2:设离散信道的输入序列为X 1 X 2 ... X N , 通过信道传输 输出的序列为Y1Y2 ...YN , 假设输入序列为独立的随机序列, 即信源是离散无记忆的,则 I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? ? ? I ? X n ; Yn ?
n ?1 N

定理1证:对离散无记忆信道,有 p ?Y | X ?=p ? y1 y2 ... y N | x1 x2 ...xN ?=? p ? yn | xn ? I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? ? H ?Y1Y2 ...YN ? ? H ?Y1Y2 ...YN | X 1 X 2 ... X N ?
N n ?1 n ?1 N

H ?Y1Y2 ...YN ? ? H ?Y1 ? ? H ?Y2 | Y1 ? ? H ?Y3 | Y1Y2 ? ? ... ? H ?YN | Y1Y2 ...YN ?1 ? ? ? H ?Yn ? H ?Y1Y2 ...YN | X 1 X 2 ... X N ? ? ??
N

x1 ?y1 x2 ?y2

? ... ?

xN ?y N

? N ? p ? y1 y2 ... y N | x1 x2 ...xN ??log ?? p ? yn | xn ? ? ? n ?1 ?
1 2 N

? ?? ? ? ??
N

n ?1 x1 ?y1 x2 ?y2

? ... ? p ? y y ... y
xN ?y N n

| x1 x2 ...xN ??log p ? yn | xn ?
N

n ?1 xn ?yn

? p? y

| xn ??log p ? yn | xn ?=? H ? yn | xn ?
n ?1 N N N

I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? ? ? H ?Yn ? ? ? H ? yn | xn ? ? ? I ? xn ; yn ?
n ?1 n ?1 n ?1

定理2证:因为信源是离散无记忆的,则 p ? x1 x2 ...xN ?=p ? x1 ? p ? x2 ? ... p ? xN ? ,因此 I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? ?

x1 ?y1 x2 ?y2 N

? ? ... ? p ? x , x ,..., x
1 2 xN ?y N N n ?1 n ?1 xn ?yn

N

, y1 , y2 ,..., y N ??log

p ? x1 x2 ...xN | y1 y2 ... y N ? p ? x1 ? p ? x2 ? ... p ? xN ?

又? I ? xn ; yn ?=? ?

? p? y
2

n

| xn ??log p ? yn | xn ? , y1 , y2 ,..., y N ??log p ? x1 | y1 ? p ? x2 | y2 ? ... p ? xn | yn ? p ? x1 ? p ? x2 ? ... p ? xN ?

x1 ?y1 x2 ?y2

? ? ... ? p ? x , x ,..., x
1 xN ?y N

N

从而有

? I ? x ; y ?-I ? X X
n ?1 n n 1

N

2

... X N ; Y1Y2 ...YN ? p ? x1 | y1 ? p ? x2 | y2 ? ... p ? xn | yn ? p ? x1 x2 ...xN | y1 y2 ... y N ?

?

x1 ?y1 x2 ?y2

?

? ... ? p ? x1 , x2 ,..., xN , y1 , y2 ,..., yN ??log
xN ?y N

? p ? x1 | y1 ? p ? x2 | y2 ? ... p ? xn | yn ? ? ? log ? ? ? ... ? p ? x1 , x2 ,..., xN , y1 , y2 ,..., y N ?? ? p ? x1 x2 ...xN | y1 y2 ... y N ? ? x1 ?y1 x2 ?y2 xN ?yN ? ? ? ? log ? ? ? ... ? p ? y1 , y2 ,..., y N ? p ? x1 | y1 ? p ? x2 | y2 ? ... p ? xn | yn ? ? ? x1 ?y1 x2 ?y2 xN ?yN ? ? ? ? log ? ?? ...? p ? y1 , y2 ,..., y N ? ? ? y1 y2 yN ? ? log1 ? 0

结论
由定理1,2可知:若信源和信道都是离散无记忆的,则

? I ? x ; y ?=I ? X X
n ?1 n n 1

N

2

... X N ; Y1Y2 ...YN ?。

对离散无记忆信道,当输入的信源是平稳时,对任意n有 I ? xn ; yn ?=I ? X ; Y ? 如果信道的输入空间为A ? ?a1 , a2 ,..., ar ? , 相应的输入字母 概率为P(a)= ? p ( a1 ), p( a2 ),..., p( ar ) ? , 输出空间B ? ?b1 , b2 ,..., bs ? , 相应的输出字母概率为P(b)= ? p (b1 ), p (b2 ),..., p (bs ) ? , 转移概率矩阵为 Q ? ? p ? b j | ak ? ? ? ? ? p ? b1 | a1 ? ? ? p ? b1 | a2 ? ? ? ? ? ? p ? b1 | ar ? ? p ? b2 | a2 ? ? ? p ? b2 | ar ? ? p ? b2 | a1 ? ? p ? bs | a1 ? ? ? p ? bs | a2 ? ? ? ? ? p ? bs | ar ? ? ?

r?s

由于 p ? ak , b j ?=p ? ak ? p ? b j | ak ? , k ? 1, 2,..., r , j ? 1, 2,..., s p ? b j ?=? p ? ai ? p ? b j | ai ?, j ? 1, 2,..., s
r i ?1

因此I ? X n ; Yn ?=I ? X ; Y ? ? ?? p ? ak , b j ? log
r s k ?1 j ?1

p ? b j | ak ? p ?bj ?

? ?? p ? ak ? p ? b j | ak ? log
r s k ?1 j ?1

p ? b j | ak ?

? p ? a ? p ?b
r i ?1 i

j

| ai ?

即I ? X ; Y ? 是输入字母概率P(a)= ? p (a1 ), p (a2 ),..., p (ar ) ? 和转移概率矩阵 Q ? ? p ? b j | ak ? ? ? ?
r?s

的函数,因此可表示为I ? P (a ), Q ? , 这样离散无记忆信

道的输入输出的互信息在一般情况下满足 I ? X 1 X 2 ... X N ; Y1Y2 ...YN ? ? NI ? P (a ), Q ?

定义:设离散无记忆信道的输入字母表概率为P(a)= ? p (a1 ), p (a2 ),..., p (ar ) ?, 转移概率矩阵为Q ? ? p ? b j | ak ? ? ? ? C ? max I ? P (a ), Q ?
p(a) r ?s

,则该信道的容量定义为

根据定义,求信道容量C,只须求I ? P (a ), Q ?的最大值即可,因为I ? P (a ), Q ? 是P (a )的上凸函数,故I ? P (a ), Q ? 相对于P (a )必有一个惟一的极大值存在, 该极大值就是最大值,这一最大值只有在下面两个条件下才能达到: (1)信源输入的字母序列是一个独立的随机序列,即要求信源是离散无记忆 (2)信源输入字母的概率分布是所有可能分布中使互信息I ? P (a ), Q ? 达到最 大值的分布。 这并不是首信道容量是由输入字母的概率分布决定的,信道容量只取决于 信道的转移概率,它代表了信道作为信息传输通道的一个最重要的性能度 量,信源发出的字母序列只有在满足一定条件时才能充分利用信道传输信

息,因此,计算各种信道的信道容量是一件有理论意义和实用价值的工作。

0

0

X
1

Y
1

无噪二元信道概率转移图

1 ? ? X ? ? 0 解:设输入空间A为 ? ?? , ? p(a1 ) p(a2 ) ? ? p(a) ? ? ? 1 ? ? Y ? ? 0 p(a1 ) ? p(a1 ) ? 1, 输出空间B为 ? ? p(b) ? ? p(b1 ) p(b2 ) ? ? ? ? ?

p ? b1 | a1 ? ? 1, p ? b2 | a1 ? ? 0, p ? b1 | a2 ? ? 0, p ? b2 | a2 ? ? 1 则 p ? b1 ?=? p ? ak ? p ? b1 | ak ? ? p ? a1 ?, p ? b2 ?=? p ? ak ? p ? b2 | ak ? ? p ? a2 ?
k=1 k=1 2 2

因此 I ? P ? a ? , Q ? ? ?? p ? ak ? p ? b j | ak ? log
2 2 k ?1 j ?1

p ? b j | ak ? p ?bj ?

? p ? a1 ? log 所以

1 1 ? p ? a2 ? log ? H ?X ? p ? a1 ? p ? a2 ?

?1 1? C ? max I ? P (a ), Q ? ? max H ? X ? ? H ? , ? ? 1 比特 / 符号 p(a) p(a) 2 2? ? 1 且在p ? a1 ?=p ? a2 ?= 达到信道容量。

英文26个字母中每一个以0.5概率复制自己以0.5概率变成下一个字母,求该信道的容量
H ?Y | X ? ? ??? p ? ak ? p ? b j | ak ? log p ? b j | ak ?
26 26 k ?1 j ?1

A
B

0.5
0.5

0.5
0.5

A
B C

1 1 1 ?1 ? ? ? p ? a1 ? ? log ? log ? 0 ? ... ? 0 ? ? 2 2 2 ?2 ? 1 1 1 1 ? ? p ? a2 ? ? 0 ? log ? log ? 0 ? ... ? 0 ? ? ... ? 2 2 2 2 ? ? 1 1 1 1? ? p ? a26 ? ? 0 ? 0 ? ... ? log ? log ? ? p( a1 ) ? p( a2 ) ? ... ? p( a26 ) ? 1 2 2 2 2? ? 则 I ? P ? a ? , Q ? ? I ? X ; Y ? ? H ? Y ? ? H ?Y | X ? ? H ?Y ? ? 1 由于

C 0.5 … 0.5 Z


0.5 Z

1 1 1 1 p ? b1 ?= p ? a26 ? ? p ? a1 ? , p ? b2 ?= p ? a1 ? ? p ? a2 ? ,..., 2 2 2 2 1 1 p ? b26 ?= p ? a25 ? ? p ? a26 ? .因此当输入p (a1 ), p (a2 ),..., p (a26 )为等概率分布时 2 2 输出P(b)= ? p (b1 ), p (b2 ),..., p (b26 ) ? C ? max I ? P (a ), Q ? ? max H ?Y ? ? 1 ? log 26 ? 1 ? log13比特 / 符号
p(a) p(a)

H ?Y | X ? ? ??? p ? ak ? p ? b j | ak ? log p ? b j | ak ?
2 2 k ?1 j ?1

? ? p log p ? ?1 ? p ? log ?1 ? p ? , 其中用到条件 p ? a1 ?+p ? a2 ?=1,则 I ? P ? a ? , Q ? ? I ? X ; Y ? ? H ?Y ? ? H ?Y | X ? ? H ?Y ?+p log p+?1 ? p ? log ?1 ? p ? 由于 p ? b1 ?=? p ? ak ? p ? b1 | ak ? ? ?1 ? p ? p ? a1 ? ? pp ? a2 ?
k =1 2 2

0

1? p

p

0

p
1
1? p

1

(a)二元对称信道

p ? b2 ?=? p ? ak ? p ? b2 | ak ? ? pp ? a1 ? ? ?1 ? p ? p ? a2 ?
k =1

?1 1? 因此当输入P(a)= ? p (a1 ), p (a2 ) ? ? ? , ? 为等概率分布时输出 ?2 2? ?1 1? P(b)= ? p (b1 ), p (b2 ) ? ? ? , ? 也为等概率分布,所以 ?2 2? C ? max I ? P (a ), Q ? ? max H ?Y ?+p log p+?1 ? p ? log ?1 ? p ?
p(a) p(a)

? 1+p log p+?1 ? p ? log ?1 ? p ?比特 / 符号

0
H ?Y | X ? ? ??? p ? ak ? p ? b j | ak ? log p ? b j | ak ?
2 3 k ?1 j ?1

1-?

?

0

? ?? log ? ? ?1 ? ? ? log ?1 ? ? ? ? 1,因为p ? a1 ?+p ? a2 ?=1 记输入a1 ? 0时的概率为p ? a1 ? , 则输入a2=1时的概率为 1-p ? a1 ?,因此输出b1 ? 0, b2 ? ? , b3 ? 1时的概率分别为,
2 k =1 2

1

?
1-?

1

(b)二元删除信道

p ? b1 ?=? p ? ak ? p ? b1 | ak ? ? p ? a1 ??1 ? ? ? ? ?1-p ? a1 ? ? 0=p ? a1 ??1 ? ? ? p ? b2 ?=? p ? ak ? p

相关文章:
信息论重点 (新)
信息论重点 (新)_工学_高等教育_教育专区。哈工大威海 信息论复习重点1.消息定义 信息的通俗概念:消息就是信息,用文字、符号、数据、语言、音符、图片、图像等能...
信息论自学报告
信息论与编码》课程自学报告 题学姓 目: 号: 名: 信息率失真函数 11124636 于鹏伟 黄素娟 18817394459 任课教师: 联系方式: 二零一四 年 2 月 18 日 ...
信息论与编码概念总结
第一章 1.通信系统的基本模型: 2.信息论研究内容:信源熵,信道容量,信息率失真函数,信源编码,信道编 码,密码体制的安全性测度等等 第二章 1.自信息量:一个...
信息论思考题
信息论思考题_理学_高等教育_教育专区。信息论思考题1、信息论的基本思想 信息论是一门研究信息传输和信息处理一般规律的学科。 信息论起源于通讯理论,是美国科学家...
第三版信息论答案
解:从信息论的角度看, “ 12 枚硬币中,某一枚为假币” 该事件发生的概率为 P “ 假币的重量比真的轻,或重” 该事件发生的概率为 P 1 ; 12 1 ; 2 ...
浅谈信息论及其应用
浅谈信息论及其应用摘要本文主要研究了信息论的起源、信息论的分类、 信息论研究的主要内容以及 信息论在现实生活中的运用, 信息论是运用概率论与数理统计的方法研究...
信息论应用
香农认为,信息论的基本内容,就是研究信源、信宿、信道和编码问题,他对信 息论的贡献很多,主要有五点:一是他第一次从理论上阐明了通讯的基本问题,提出了通讯 ...
论信息论与编码的发展与前景
信息论与编码的发展与前景摘要:信息论理论的建立,提出了信息、信息熵的概念,接着人们提出了编码定理。编码方 法有较大发展,各种界限也不断有人提出,使多用户信息...
信息论习题解答
信​息​论​习​题​解​答第二章 信息量和熵 2.2 八元编码系统,码长为 3,第一个符号用于同步,每秒 1000 个码字,求它的信息速率。 解:同步...
信息论
信息论_工学_高等教育_教育专区。齐鲁工业大学 2013-2014 学年第二学期《信息理论与编码》期末小论文 Page 1 of 4 从信息论看生活问题——论自信息、熵和生活...
更多相关标签:
信息论基础 | 信息论与编码 | 信息论基础 pdf | 系统论 | 信息熵 | 信息 | 控制论 | |