信息与编码课程论文
本科生课程论文
题 目: 香农信息论的基本理论探究 姓 名: 学 院: 专 业: 班 级: 学 号: 指导教师: 完成时间:
课 程 论 文 任 务 书
学生姓名 指导教师 论文题目 香农信息论的基本理论探究
论文内容(需明确列出研究的问题):信息的价值在于它为人们能动的改造外部世界提供了可能,信息所揭示的事物运动规律为人们应用这些规律提供了可能,而信息所描述的事物状态也为人们推动事物向有利的方向发展提供了可能。掌握的资源和能量越多,面对同样的信息时人们能用以改造世界的可能性也越大。信息是信息论中最基本、最重要的概念。信息论的主要基本理论包括:信息的定义和度量;各类离散信源和连续信源的信息熵;有记忆、无记忆离散和连续信道的信道容量;无失真信源编码定理。香农三大定理是信息论的基础理论。香农信息论在解决了信息的测度问题之后,主要致力于研究如何提高通信系统中信息传输的可靠性和有效性,因而香农编码理论是进行信源编码和信道编码理论研究的重要的指导理论。
资料、数据、技术水平等方面的要求:论文要符合一般学术论文的写作规范,具备学术性、科学性和一定的创造性。文字要流畅、语言要准确、论点要清楚、论据要准确、论证要完整、严密,有独立的观点和见解。内容要理论联系实际,计算数据要求准确,涉及到他人的观点、统计数据或计算公式等要标明出处,结论要写的概括简短。参考文献的书写按论文中引用的先后顺序连续编码。 发出任务书日期 完成论文(设计)日期 学科组或教研室意见(签字) 院、系(系)主任意见(签字)
香农信息论的基本理论探究
【摘要】:信息的价值在于它为人们能动的改造外部世界提供了可能,信息所揭示的事物运动规律为人们应用这些规律提供了可能。而信息所描述的事物状态也为人们推动事物向有利的方向发展提供了可能。掌握的资源和能量越多,面对同样的信息时人们能用以改造世界的可能性也越大。信息是信息论中最基本、最重要的概念。信息论的主要基本理论包括:信息的定义和度量;各类离散信源和连续信源的信息熵;有记忆、无记忆离散和连续信道的信道容量;无失真信源编码定理。香农三大定理是信息论的基础理论。香农信息论在解决了信息的测度问题之后,主要致力于研究如何提高通信系统中信息传输的可靠性和有效性,因而香农编码理论是进行信源编码和信道编码理论研究的重要的指导理论。 【关键词】: 等长编码 信源编码 香农三大定理 通信系统
Shannon, the basic theory of information theory study
Abstract :The value of information is for people to move it of reform of the external world possible, information reveal the movement rule things for people using these rules to provide the possibility. While the information described the state of things as well as people push things to favorable direction may be provided. Mastery of the resources and the more energy, face the same information to people can transform the world are also more likely. Information is the most basic information theory, the most important concept 。The basic theory of information theory mainly include: the definition of information and measure; All kinds of discrete source and continuous source of information entropy;A memory, no memory discrete and continuous channel capacity; No distortion source coding theorem. Shannon three theorems is the basic theory of information theory. The main basic theory of information includes: the definition and measurement of information; all kinds of discrete and continuous source of information entropy source; a memory, memory of discrete and continuous channel capacity; lossless source coding theorem. The value of information is for people to move it of reform of the external world possible, information reveal the movement rule things for people using these rules to provide the possibility.
Key words:Corolla coding Source coding Shannon three theorems Communication system
引言
信息理论与编码理论是在长期的通信工程实践和理论研究的基础上发展起来的。信息论理论基础的建立,一般来说开始于香农(Shannon)在研究通信系统时所发表的论文《通信的数学理论》。他从研究通信系统传输的实质出发,对信息作了科学的定义,并进行了定性和定量的描述。他在1941 年至1944年对通信和密码进行深入研究,并用概率论和数理统计的方法系统地讨论了通信的基本问题,得出了无失真信源编码定理和有噪环境下的信道编码定理,由此奠定了现代信息论的基础。在香农编码定理的指导下,信道编码理论和技术逐步发展成熟。香农信息论是从通信系统的最优化角度来研究信息的传递和处理问题的。其最大特点是将概率统计的观点和方法引入到通信理论研究中,揭示了通信系统传递的对象就是信息,并对信息给以科学的定量描述,提出了信息熵的概念,还指出通信系统的中心问题是在噪声下如何有效而可靠地传送信息,而实现这一目标的主要方法是编码,而且从理论上证明了编码方法可以达到的最佳性能极限。因此,学习香农信息论对于正确理解以及进一步发展信息理论和编码技术是非常必要和有益的。香农三大定理是信息论的基础理论。香农三大定理是存在性定理,虽然并没有提供具体的编码实现方法,但为通信信息的研究指明了方向。
一. 信息的定义及度量
信息仅仅与随机事件的发生有关,不确定性的大小可以直观地看作事先猜测某随机事件是否发生的难易程度。某一事物状态的不确定性的大小,与该事物可能出现的不同状态数目和各状态出现的概率大小有关。香农信息反映的是事物的不确定性,是对事物的运动方式或形式的不确定性描述。 在样本空间中,每个可能选择的消息是这个样本空间的一个元素。对于离散消息的集合,概率预测就是对每一个可能选择的消息指定一个概率(非负,且总和为1)。一个样本空间和它的概率预测一起构成一个概率空间。一般概率空间用[X,P]来表示。在离散情况下,概率空间表示成:
x a 1⎡⎤⎡=⎣P (X ) ⎦⎣p (a 1)
a 2... aq
p (a 2) ... p (aq )
⎤⎦。
其中p (a i ) 为符号a i 作为消息的概率,称为先验概率。
在各种通信系统的信源当中,离散无记忆信源是一类最基本的信源,信源输出是单个的符号的消息,并且消息之间是两两互不相容的。离散无记忆信源,它的概率分布函数决定了它所携带的信息。若信源空间中共有q 个符号,每个符号发生的概率是p i , 那么发出某个符号所携带的信息量是-log p i ,由于概率是在0和1之间的,使得每一事件的信息量是非负的。如果该事件发生的概率是0,或者是1,则表明该事件一定不会发生或者一定会发生,那么他所携带的信息量是0。从理论上讲,该事件发生的概率越小,那么它的不确定性也就越大,它所携带的信息量也就越大。该事件发生的概率越大,它所携带的信息量也就越大。
对于通信系统的信源来说,它不会仅仅只发出一个消息,必然会有别的可能的情况发生。那么对于一个信源来讲,我们可以用平均自信息量来度量,即可以得到信源的平均自信息量。
信息熵的定义如下: q
H (x ) =E [log1/P (a 1) ]=-∑P (a i )log P (a i )
i =1
平均自信息量也称为信息熵。信息熵是从平均意义上来表征信源的总体信息测度的。对于某特定的信源,它的信息熵是一个确定的数值。不同的信源因为其概率分布不同,它的熵也不同。
信息熵具有一些基本的性质,比如,对称性,确定性,非负性,扩展性,可加性,极值性等等。
二、等长信源编码定理
信源编码:以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。
信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理:无失真信源编码定理:是离散信源/数字信号编码的基础;限失真信源编码定理:是连续信源/模拟信号编码的基础。信源编码可以分为以下几类:
离散信源编码:独立信源编码,可做到无失真编码;
连续信源编码:独立信源编码,只能做到限失真信源编码; 相关信源编码:非独立信源编码。
l
q ≤r 若对信源进行等长编码,则必须满足其中,l 是码长,r 是码符号集中的码
元数,q 信源符号个数。
例:如果有四个信源符号{s 1,s 2,s 3,s 4},采用二元编码,l =2,则可以编成s 1=00,s 2=01,s3=10,s4=11。
N l q ≤r 如果我们要对信源的N 次扩展信源进行编码,也必须满足, 两边取对数
l log q l ≥
得:N log r 。N 表示平均每个信源符号所需的码符号个数。
l ≥
例:对英文电报得32个符号进行二元编码,根据上述关系:
log32
=5log 2。我们
继续讨论上面得例子,我们已经知道英文的极限熵是1.4bit, 远小于5bit ,也就
是说,5个二元码符号只携带1.4bit 的信息量,实际上,5个二元符号最多可以携带5bit 信息量。我们可以做到让平均码长缩短,提高信息传输率
s 3s 2s 4⎤4⎡S ⎤⎡s 1
⎢P (s ) ⎥=⎢P (s ) P (s ) P (s ) P (s ) ⎥∑P (s i ) =1
⎦⎣1234⎦ i =1我们举例说明:设信源⎣而其依赖关系为:
P (s 2/s 1) =P (s 1/s 2) =P (s 4/s 3) =P (s 3/s 4) =1, P (s j /s i ) =0
若不考虑
符号间的依赖关系,可得码长l =2
若考虑符号间的依赖关系,则对此信源作二次扩展
⎡S 2⎤⎡s 1s 2s 3s 4s 4s 3s 2s 1⎤
=⎢P (s i s j ) =1⎢P (s s ) P (s s ) P (s s ) P (s s ) ⎥∑2⎥P (s ) 213443⎦⎣⎦⎣12
,ij 。可见,由于符号
间依赖关系的存在,扩展后许多符号出现的概率为0,此信源只有4个字符,可
l '
=1'
得码长l =2,但平均每个信源符号所需码符号为N 。
我们仍以英文电报为例,在考虑了英文字母间的相关性之后,我们对信源作N 次扩展,在扩展后形成的信源(也就是句子)中,有些句子是有意义的,而有些句子是没有意义的,我们可以只对有意义的句子编码,而对那些没有意义的句子不进行编码,这样就可以缩短每个信源符号所需的码长。等长信源编码定理给出了进行等长信源编码所需码长的极限值。
定理(等长信源编码定理) 一个熵为H (S ) 的离散无记忆信源,若对其N 次扩展
l H (S ) +ε≥
log r 当信源进行等长r 元编码,码长为l ,对于任意ε大于0,只要满足N
l H (S ) -2ε
≤
log r 则不可能N 无穷大时,则可以实现几乎无失真编码,反之,若:N
实现无失真编码,当N 趋向于无穷大时,译码错误率接近于1。为了衡量编码效
η=
H (S ) H (S )
='
R log r N
果,引进称为编码效率
η=
最佳编码效率为:
H (S ) H (S ) 1-η
=ε=H (S ) R ' H (S ) +ε, η
⎡s ⎡S ⎤⎢1⎢P (s ) ⎥=⎢3⎣⎦
⎣4例:设离散无记忆信源
2
s 2⎤
1⎥⎥H (S ) =1log 4+3log 4=0.8114⎦ 443
134
D [I (s i )]=∑p i (logp i ) 2-[H (S )]2=(log4) 2+(log) 2-0.8112=0.4715
443i =1若采用
-57
等长二元编码,要求编码效率η=0.96,允许错误率δ≤10, 则N ≥4.13⨯10也
就是长度要达到4130万以上。因此以下我们引入变长码的概念。离散信源的无失真编码是要讲信源输出的离散消息符号变换成适合于信道传输的信道基本符号,在这一变换过程中同时还要考虑在信源消息不失真的前提下如何用较短的码字来代表每一条消息。使用无失真变长信源编码定理即香农第一定理,可以帮助实现这一目标。
三、香农第一定理(无失真变长信源编码定理)
编码器可以看作这样一个系统,它的输入端为原始信源S ,其符号集为
S ={S 1, S 2,..., S q
;而信道所能传输的符号集为X ={x 1, x 2,..., x r }。编码器的功能是
用符号集X 中的元素,将原始信源的符号S i 变换为相应的码字符号w i ,所以编
码器输出端的符号集为
C :{W 1, W 2,..., W q }
S :s ∈W q }
信源
码字单符号信源无失真编码器
N N 次扩展信源无失真编码器
指标:
1) 平均码长
q
q N
=∑P (s i ) l i
=i =1,
∑P (
N s i ) λi
i =1
2) 编码后的信息传输率
R =H (S ) /R H (S ) N =
,N /N
3) 编码效率
η=
H (S ) N
N log r
例:二元DMS 进行无失真编码
⎡S ⎤⎡⎢s
1s 2⎤
⎢1⎥⎣P (s ) ⎥⎦
=⎢3⎣4
4⎥⎦
H(S) = H(3/4,1/4) = 0.811(bit/sign)
当N=1时, 1=1,
R 1=
H (S ) H (S )
=0.811η1==0.81111⋅log 2(bit/code),
H (S ) H (S )
=0.961η2==0.9612/2/2⋅log 22(bit/code),
H(S) = H(3/4,1/4) = 0.811(bit/sign) {0,10,110,111}
当N=2时,
2=1.688
R 2=
R 3=
H (S ) H (S )
=0.985η3==0.9853/33/3⋅log 2 (bit/code)
当N=3时,
当N=4时,R 4=0.991 (bit/code) η4=0.991
随着N 的增加,平均码长减小,有效性逐步提高;当N 趋于无穷时,平均码长可
以无限制地减小吗? 由此引出以下定理: 定理
设 S N ={α1, α2,..., αN }为q 元离散无记忆信源S 的N 次扩展
q
信源,若对 S N 进行编码,码符号集
{x 1, x 2,..., x r }=X ,则总可以找
到一种编码方法构成惟一可译码,使信源S 中每个符号所需的平均
H (S ) 1N H (S ) 编码长度满足:+>≥log r N N log r 且当
N →∞
时有:
lim
N →∞
N H (S )
==H r (S ) N log r
以上定理是香农第一定理,又称为无失真信源编码定理或变长码信源编码定理。
这个定理是香农信息论中非常重要的一个定理,它指出,要做到无失真的信源编码,信源每个符号所需要的平均码元数就是信源的熵值,如果小于这个值,则唯一可译码不存在。可见,熵是无失真信源编码的极限值。定理还指出,通过对扩展信源进行编码,当N 趋向于无穷时,平均码长可以趋进该极限值。还可以证明,如果我们不确切知道信源的概率分布,我们用估计的概率分布去进行编码时,平均码长会加长,但是如果估计的偏差不大的话,平均码长也不会增加太多。
香农第一定理的意义:将原始信源符号转化为新的码符号,使码符号尽量服从等概分布,从而每个码符号所携带的信息量达到最大,进而可以用尽量少的码符号传输信源信息。
关于香农第一定理有以下结论:
1)通过对扩展信源进行可变长编码,可以使平均码长无限趋近于极限熵值,但这是以编码复杂性为代价的。
2)无失真信源编码的实质:对离散信源进行适当的变换,使变换后新的符号序列信源尽可能为等概率分布,从而使新信源的每个码符号平均所含的信息量达到最大。
3)香农第一定理仅是一个存在性定理,没有给出更有效的信源编码的实现方法。
⎤⎡S ⎤⎡s 1s 2
=⎢P (S ) ⎥⎢3/41/4⎥⎦⎣⎦其熵为:H (S )=0.811我们令s 1=0,s 2=1,这时平例:⎣
均码长=1,编码的效率η=0.811,二次扩展信源进行编码如下所示:
2=9/16*1+3/16*2 3/16*3 1/16*3=27/16
=
2
=27/322 η=0.961
四、香农第二定理(有噪信道编码定理)
1、错误概率率包括误码和误字率。P E = P(a1)P(b2|a1)+P(a2)P(b1|a2)= = ωp + (1-ω)p = 0.01。
a 1=0 p (a 1) = ω
a 2=1 p (a 2) = 1-ω
2、常用判决准则
a 、MAP 准则(Maximum a Posteriori) 对于所有的
C ',P (C *|R ) ≥P (C '|R ) ,C '≠C *
P (R |C *) P (C ') P (C *) P (R |C *) P (C ') P (R |C ')
,似然比Λ= ≥≥
P (R ) P (R ) P (R |C ') P (C *) b 、ML 准则(Maximum Likelihood)
1
若输入符号等概率时P (C ) =,P (R |C *) ≥P (R |C ')
r
a i 3=a i 1⊕a i 2
例2、(5,2)线性码αi =(a i 1, a i 2, a i 3, a i 4, a i 5) ,a i 4=a i 1
PE = 7.8*10-4 , R
a i 5=a i 1⊕a i 2
= 0.4
00000
00010 01000 10001 01101 01111 00101 11100
00001 00100 10000 00011 01100 01001 11101 01110 10110 10011 00111 10100 11011 11001 01010 11001
00000
01101
00000 01101 10111 11010
10111 10101 11111 00110 11010 11000 10010 01011
10111
11010
3. 香农第二定理(有噪信道编码定理)
定理 设某离散无记忆信道有r 个输入符号,s 个输出符号信道容量为C 。只要码长n 足够长,总可以在输入的r n 个符号集中找到M 个码字(代表M 个等可能的消息,且M ≤2n (C -ε) , ε为任意小的正数)组成一个码,并存在相应的译码规则,使信道输出的错误概率任意小。
当信道的信息传输率不超过信道容量时,采用合适的信道编码方法可以实现任意高的传输可靠性,但若信息传输率超过了信道容量,就不可能实现可靠的传输。
设某信道有r 个输入符号,s 个输出符号,信道容量为C ,当信道的信息传输率R
1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点,为信道编码理论和技术的研究指明了方向。
2、定理仅指出编码的存在性,未给出编码的具体方法。
3、定理指出:R
4、香农进一步证明:R=C时,任意小的差错概率也是可以达到的。
五、香农第三定理(保失真度准则下的有失真信源编码定理)
1、失真度与信息率失真函数 a 、系统模型
U 符号集A ={u 1,..., u r },V 符号集B ={v 1,..., v s } b 、失真测度
1)单符号失真测度d (u , v ) ,设u ∈U , v ∈V 。
⎡d (u 1, v 1) ⎢d (u , v )
21
定义失真矩阵d =⎢
⎢. ⎢
⎣d (u r , v 1)
... d (u 1, v s ) ⎤... d (u 2, v s ) ⎥⎥ d (u , v ) ≥0。
i j
⎥... . ⎥
... d (u r , v s ) ⎦
⎡01... 1⎤⎢10... 1⎥⎧⎪0, u i =v j
⎥,N=3时,如果规定d (u i , v j ) =⎨,那么失真矩阵为d =⎢
⎢. . . . ⎥⎪⎩1, u i ≠v j
⎢⎥⎣11... 0⎦
失真度如图所示:
U
2) 序列失真测度
V
设序列(x 1,..., x N ), x i ∈U , (y 1,..., y N ), y j ∈V ,定义序列失真测度为
1N
d N (x , y ) =∑d (x i , y i ) 。
N i =1
3) 平均失真
单符号平均失真
1
E [d ]=
N
E [d ]=∑P (u i , v j ) d (u i , v j )
i , j
,序列平均失真
∑E [d (x , y )]
i
i
i =1
N
。
c 、信息率失真函数
定义:信息率失真函数R (D ) =min {I (U ; V )}
P (v j |u i ) ∈P D
例 设信源X ,符号集为{a 1, a 2,..., a 2n },,等概分布P ,..., 2n 给定失真测i =1/2n , i =1度为d i , j
⎧1, i ≠j
,设计一种单符号压缩算法使得平均失真D=1/2,并求压缩后=⎨0, i =j ⎩
的信息传输率R
信息率失真函数性质
1)当D
2)存在一个Dmax ,使D> Dmax时,R(D)=0 3)R(0)=H(X)
4)在0
定理 设R (D ) 为一离散无记忆信源的信息率失真函数,并且有有限的失真测度D, 则对于任意D ≥0, ε>0,以及任意长的码长k 一定存在一种码字个数为
M ≥2k [R (D ) +ε]的信源编码,使编码后码的平均失真度≤D 。
关于香农第三定理的几点讨论:
1)R(D)确定是保真度准则条件下,信源信息率压缩的下限。0
保真度准则下的信源编码定理,或称有损信源编码定理。只要码长足够长,总可以找到一种信源编码,使编码后的信息传输率略大于率失真函数,而码的平均失真度不大于给定的允许失真度,即D'
设R(D)为一离散无记忆信源的信息率失真函数,并且选定有限的失真函数,对于任意允许平均失真度D>=0,和任意小的a>0,以及任意足够长的码长N ,则一定存在一种信源编码W ,其码字个数为M
六、香农三大定律的内在联系
香农三大定理是信息论的基础理论,是存在性定理,虽然并没有提供具体的
编码实现方法,但为通信信息的研究指明了方向。可变长无失真信源编码定理,采用无失真最佳信源编码可使得用于每个信源符号的编码位数尽可能地小,但它的极限是原始信源的熵值,但是超过了这一极限就不可能实现无失真的译码。有噪信道编码定理,是当信道的信息传输率不超过信道容量时,采用合适的信道编码方法,可以实现任意高的传输可靠性,但是若信息传输率超过了信道容量,就不可能实现可靠的传输。而保真度准则下的信源编码定理,或称有损信源编码定理,只要码长足够长,总可以找到一种信源编码,使编码后的信息传输率略大于率失真函数,而码的平均失真度不大于给定的允许失真度。香农三大定律结合起来就构成了现代信息论的基础理论,三大理论之间相辅相成,相互联系,为现代通信数字理论的发展做出了巨大的贡献。
随着多媒体技术的发展,通信系统给人们带来了巨大的挑战,将信道编码与信源编码相结合的思想受到了人们的日益重视,这都是以香农三大定律为基础的,这也就是香农定律在通信系统中的作用,并且,这种作用会一直沿用下去。 【参考文献】:
【1】 陈运﹒信息论与编码(第二版)﹒北京:电子工业出版社,2007 【2】 傅祖芸﹒信息论——基础理论与应用(第二版)﹒北京:电子工业出版社,
2008
【3】 周炯磐,丁晓明﹒信源编码原理﹒北京:人民邮电出版社,1996 【4】 张宗橙﹒纠错编码原理和应用﹒北京:电子工业出版社,2003 【5】 周炯磐. 信息理论基础[M].人民邮电出版社,1983 【6】 钟义信. 信息科学原理[M].北京邮电大学出版社,1996
【7】 姜丹. 钱玉美. 信息理论与编码[M].中国科学技术大学出版社,1992 【8】 朱雪龙. 应用信息论基础[M].清华大学出版社,2001
课程论文成绩评定表