对称信道容量的求解1
课程设计任务书
2011—2012学年第一学期
专业: 通信工程 学号: 姓名:
课程设计名称: 信息论与编码课程设计
设计题目: 对称信道容量的求解
完成期限:自 2011 年 12 月 19 日至 2011年 12 月 25 日共 1 周
一.设计目的
1、深刻理解信道容量的概念;
2、理解对称信道的概念与容量公式;
3、使用MATLAB 或其他语言进行编程。
二.设计内容
给定信道的概率矩阵,编程判断其是否为对称信道,并求解其信道容量。
三.设计要求
1、任意给定矩阵;
2、如矩阵不满足信道矩阵的要求,要能提示错误。
四.设计条件
计算机、MATLAB 或其他语言环境
五.参考资料
[1]曹雪虹,张宗橙. 信息论与编码. 北京:清华大学出版社,2007.
[2]王慧琴,数字图像处理. 北京:北京邮电大学出版社,2007.
[3]张德丰,MATLAB 通信工程仿真 北京:机械工程出版社,2010
[4]陈鲁生,信息论与编码 北京:科学出版社,2010
指导教师(签字): 教研室主任(签字): 批准日期: 年 月 日
摘 要
本课程设计主要以给定信道的概率矩阵1/2 1/2 0 0;0 1/2 1/2 0;0 0 1/2 1/2;1/2 0 0 1/2通过计算机利用MATLAB 软件编辑判断其是否为对称信道,如不是对称信道,则提示错误。并利用互信息量二等函数来求平均互信息量,并最终得到信道容量的结果。
关键字:信道;信道容量;信道容量计算
目录
1绪论..................................................................................................1
2信道容量概念...................................................................................1
3单用户信道.......................................................................................2
4多用户信道.......................................................................................3
5信道容量计算...................................................................................4
5.1离散单符号信道及其信道容量................................................4
5.2信道容量计算思路...................................................................5
5.3信道容量定理...........................................................................5
5.4离散多符号信道及其信道容量................................................5
6组合信道及其信道容量....................................................................6
7程序设计...........................................................................................7
8程序运行与分析................................................................................9
总结....................................................................................................11
致谢....................................................................................................12
参考文献.............................................................................................13
1. 绪论
通信系统一般由信源、信道和信宿三部分组成, 信道是信息传递的通道, 承担信息的传输和储存的任务, 是构成通信系统的重要组成部分。信道容量是指信道能够传输信息量的大小,我们经常需要考虑如何去计算信道容量,这也是香农信息论一个很重要的方面。信道的种类有多种,信道容量也是一个非常复杂的问题。
2. 信道容量概念
信息论不研究信号在信道中传输的物理过程,它假定信道的传输特性是已知的,这样信道就可以用抽象的数学模型来描述。在信息论中,信道通常表示成:{X, P(Y|X), Y},即信道输入随机变量X 、输出随机变量Y 以及在输入已知的情况下,输出的条件概率分布 P(Y|X)。
图1信道容量
根据信道的统计特性是否随时间变化分为:
①恒参信道(平稳信道):信道的统计特性不随时间变化。卫星通信信道在某种意义下可以近似为恒参信道。
②随参信道(非平稳信道):信道的统计特性随时间变化。如短波通信中,其信道可看成随参信道 。
信道容量是信道的一个参数,反映了信道所能传输的最大信息量,其大小与信源无关。对不同的输入概率分布,互信息一定存在最大值。我们将这个最大值定义为信道的容量。一但转移概率矩阵确定以后,信道容量也完全确定了。尽管信道容量的定义涉及到输入概率分布,但信道容量的数值与输入概率分布无关。我们将不同的输入概率分布称为试验信源,对
不同的试验信源,互信息也不同。其中必有一个试验信源使互信息达到最大。这个最大值就是信道容量。
信道容量有时也表示为单位时间内可传输的二进制位的位数(称信道的数据传输速率,位速率),以位/秒(b/s)形式予以表示,简记为bps 。
通信的目的是为了获得信息,为度量信息的多少(信息量),我们用到了熵这个概念。在信号通过信道传输的过程中,我们涉及到了两个熵,
发射端处信源熵——即发端信源的不确定度,接收端处在接收信号条件下的发端信源熵——即在接收信号条件下发端信源的不确定度。接收到了信号,不确定度小了,我们也就在一定程度上消除了发端信源的不确定性,也就是在一定程度上获得了发端信源的信息,这部分信息的获取是通过信道传输信号带来的。如果在通信的过程中熵不能够减小(不确定度减小)的话,也就没有通信的必要了。最理想的情况就是在接收信号条件下信源熵变为0(不确定度完全消失),这时,发端信息完全得到。
通信信道,发端 X ,收端 Y 。从信息传输的角度看,通过信道传输了 I(X;Y)=H(X)-H(X|Y) ,( 接收Y 前后对于X 的不确定度的变化) 。 I 该值与两个概率有关, p(x),p(y|x),特定信道转移概率一定,那么在所有 p(x) 分布中,max I(X;Y)就是该信道的信道容量C(互信息的上凸性)。
3. 单用户信道容量
信道是由输入集A 、输出集B 和条件概率P(y│x),y ∈B,x ∈A 所规定的。当B 是离散集时,归一性要求就是:
当B 是连续集时,P (y │x ) 应理解为条件概率密度,上式就成为积分形式。如A 和B 都是离散集,信道所传送的信息率(每符号)就是输出符号和输入符号之间的互信息:
错误!未找到引用源。
互信息与P (y │x ) 有关,也与输入符号的概率P (x ) 有关,后者可由改变编码器来变动。若能改变P (x ) 使I (X ; Y ) 最大,就能充分利用信道传输信息的能力,这个最大值就称为单用户信道容量C ,即:
式中∑为所有允许的输入符号概率分布的集。
当A 或B 是连续集时,相应的概率应理解为概率密度,求和号应改为积分,其他都相仿。
4. 多用户信道容量
多用户信道容量问题要复杂一些。以二址接入信道为例, 这种信道有两个输入 X 2∈A 1和X 2∈A 2,分别与两个信源联结, 发送信息率分别为R 1和R 2;有一个输出Y , 用它去提取这两个信源的信息。若信道的条件概率为P (y │x 1, x 2) ,则
式中I (X 1; Y │X 2) 为条件互信息,就是当X 2已确知时从Y 中获得的关于X 1的信息; I (X 2; Y │X 1)的意义相仿;I (X 1, X 2; Y ) 为无条件互信息,就是从Y 中获得的关于X 1和X 2的信息。E 1和 E 2分别为所有允许的输入符号的概率分布P 1(x 1) 和P 2(x 2) 的集。
当X 1和X 2相互独立时, 这些条件互信息要比相应的无条件互信息大, 因此两个信息率R 1和R 2的上界必为上面三个式子所限制。若调整P 1(x 1) 和P 2(x 2) 能使这些互信息都达到最大,就得到式中的C 1,C 2,C 0。
因此R 1和R 2的范围将是一个截角四边形区域, 其外围封闭线就是二址接入信道的容量上界。更一般的多用户的情况还要复杂。
要使信道容量有确切的含义,尚须证明相应的编码定理,就是说当信息率低于信道容量时必存在一种编码方法,使之在信道中传输而不发生错
误或错误可任意逼近于零。已经过严格证明的只有无记忆单用户信道和多用户信道中的某些多址接入信道和退化型广播信道。对某些有记忆信道,只能得到容量的上界和下界,确切容量尚不易规定。
5. 信道的容量计算
5.1离散单符号信道及其信道容量
信道的输入、输出都取值于离散符号集,且都用一个随机变量来表示的信道就是离散单符号信道。 由于信道中存在干扰,因此输入符号在传输中将会产生错误,这种信道干扰对传输的影响可用传递概率来描述。 信道传递概率通常称为前向概率。它是由于信道噪声引起的,所以通常用它描述信道噪声的特性。 有时把p(x)称为输入符号的先验概率。而对应的把p(x|y)称为输入符号的后验(后向)概率。
平均互信息 I(X;Y) 是接收到输出符号集Y 后所获得的关于输入符号集X 的信息量。信源的不确定性为H(X),由于干扰的存在,接收端收到 Y 后对信源仍然存在的不确定性为H(X|Y),又称为信道疑义度。信宿所消除的关于信源的不确定性,也就是获得的关于信源的信息为 I(X;Y),它是平均意义上每传送一个符号流经信道的信息量,从这个意义上来说,平均互信息又称为信道的信息传输率,通常用 R 表示。有时我们所关心的是信道在单位时间内平均传输的信息量。如果平均传输一个符号为t 秒,则信道平均每秒钟传输的信息量为Rt 一般称为信息传输速率。
对于固定的信道,总存在一种信源(某种输入概率分布),使信道平均传输一个符号接收端获得的信息量最大,也就是说对于每个固定信道都有一个最大的信息传输率,这个最大的信息传输率即为信道容量,而相应的输入概率分布称为最佳输入分布。
信道容量是信道传送信息的最大能力的度量,信道实际传送的信息量必然不大于信道容量。
要使信道容量有确切的含义,尚须证明相应的编码定理,就是说当信息率低于信道容量时必存在一种编码方法,使之在信道中传输而不发生错误或错误可任意逼近于零。已经过严格证明的只有无记忆单用户信道和多用户信道中的某些多址接入信道和退化型广播信道。对某些有记忆信道,
只能得到容量的上界和下界,确切容量尚不易规定。
5.2信道容量计算思路
为了评价实际信道的利用率,应具体计算已给信道的容量。这是一个求最大值的问题。由于互信息对输入符号概率而言是凸函数,其极值将为最大值,因此这也就是求极值的问题。对于离散信道,P(x)是一组数,满足非负性和归一性等条件,可用拉格朗日乘子法求得条件极值。对于连续信道,P(x)是一函数,须用变分法求条件极值。但是对于大部分信道,这些方法常常不能得到显式的解,有时还会得到不允许的解,如求得的P(x)为负值等。为了工程目的,常把信道近似表示成某些易于解出容量的模式,如二元对称信道和高斯信道。对于其他信道的容量计算曾提出过一些方法,但都有较多的限制。比较通用的解法是迭代计算,可借助计算机得到较精确的结果。
对于连续信道,只需把输入集和输出集离散化,就仍可用迭代公式来计算。当然如此形成的离散集,包含的元的数目越多,精度越高,计算将越繁。对于信息论中的其他量,如信息率失真函数,可靠性函数等,都可以用类似的方法得到的各种迭代公式来计算。
5.3信道容量定理
从求信道容量的问题实际上是在约束条件下求多元函数极值的问题,在通常情况下,计算量是非常大的。下面我们介绍一般离散信道的平均互信息达到信道容量的充要条件,在某些情况下它可以帮助我们较快地找到极值点。
信道容量定理只给出了达到信道容量时,最佳输入概率分布应满足的条件,并没有给出最佳输入概率分布值,也没有给出信道容量的数值。另外,定理本身也隐含着达到信道容量的最佳分布不一定是唯一的,只要输入概率分布满足充要条件式,就是信道的最佳输入分布。在一些特殊情况下,我们常常利用这一定理寻求输入分布和信道容量值。
5.4离散多符号信道及其信道容量
实际离散信道的输入和输出常常是随机变量序列,用随机矢量来表示,
称为离散多符号信道。
若在任意时刻信道的输出只与此时刻信道的输入有关,而与其他时刻的输入和输出无关,则称之为离散无记忆信道,简称为DMC(discrete memoryless channel)。
输入、输出随机序列的长度为N 的离散无记忆平稳信道通常称为离散无记忆信道的N 次扩展信道。
对于离散无记忆N 次扩展信道,当信源是平稳无记忆信源时,其平均互信息等于单符号信道的平均互信息的N 倍。
当信源也是无记忆信源并且每一时刻的输入分布各自达到最佳输入分布时,才能达到这个信道容量NC 。
6. 组合信道及其信道容量
前面我们分析了单符号离散信道和离散无记忆信道的扩展信道。实际应用中常常会遇到两个或更多个信道组合在一起使用的情况。例如,待发送的消息比较多时,可能要用两个或更多个信道并行发送,这种组合信道称为并联信道;有时消息会依次地通过几个信道串联发送,例如无线电中继信道,数据处理系统,这种组合信道称为级联信道。在研究较复杂信道时,为使问题简化,往往可以将它们分解成几个简单的信道的组合。这一节我们将讨论这两种组合信道的信道容量与其组成信道的信道容量之间的关系。
独立并联信道的信道容量才等于各信道容量之和。
级联信道是信道最基本的组合形式,许多实际信道都可以看成是其组成信道的级联。两个单符号信道组成的最简单的级联信道X →Y →Z 组成一个马尔可夫链。根据马尔可夫链的性质,级联信道的总的信道矩阵等于这两个串接信道的信道矩阵的乘积。求得级联信道的总的信道矩阵后,级联信道的信道容量就可以用求离散单符号信道的信道容量的方法计算。信道和高斯信道 。对于其他信道的容量计算曾提出过一些方法,但都有较多的限制。比较通用的解法是迭代计算,可借助计算机得到较精确的结果。
对于连续信道,只需把输入集和输出集离散化,就仍可用迭代公式来计算。当然如此形成的离散集,包含的元的数目越多,精度越高,计算将
越繁。对于信息论中的其他量,如信息率失真函数,可靠性函数等,都可以用类似的方法得到的各种迭代公式来计算。
7. 程序设计
信道输入为等概率分布,即 p=1/4,I=1,2,3,4有如下信道转移矩阵
⎡1/2 1/2 0 0⎤⎢0 1/2 1/20⎥⎥p =⎢⎢0 0 1/2 1/2⎥⎢⎥1/2 0 0 1/2⎣⎦,求其信道容量。
求互信息量二等函数文件hmessage.m ,其源代码如下:
function r=hmessage(x,f,nx,my)
% x为输出的概率分布,f 为转移概率矩阵,nx 为输出德符号的可选个数,即x 的元素%个数,nx 同时也是矩阵f 的行数,my 是矩阵的列数,也即输出概率空间中的元素个数
sum=0;
for i=1:nx
for j=1:my
t=f(i,j)*x(i)
%求平均互信息量
sum=sum-t*log(f(i,j))/log(2);
end
end
r=sum;
disp('平均互信息量');
double(r) %返回结果
用于计算离散信源平均信息量的函数为message.m 文件,其源代码如下:
function r=message(x,n)
r=0;
for i=1:n
r=r-x(i)*log(x(i))/log(2);
end disp r
下面利用函数 message 来求信源的熵。利用函数message 来求平均互信息量,并最终得到信道容量。其实现的MATLAB 程序代码如下:
>>clear all;
x=[0.25 0.25 0.25 0.25];
f1=[1/2 1/2 0 0;0 1/2 1/2 0;0 0 1/2 1/2;1/2 0 0 1/2];%定义信道概率的转移矩阵
Hf1=hmessage(x,f1,4,4) hx=message(x,4)
disp('信道1的信道容量') c1=hx-hf1 平均互信息量为 hf1=0.1250
此离散信源的平均信息量为 hx=0
信道1的信道容量 c1=0.1250
8. 程序运行与分析
图2程序输入
图3信源的平均信息量
图4信源符号输入概率与信道容量关系
由运行图可以看出给定任意矩阵
⎡1/2 1/2 0 0⎤⎢0 1/2 1/20⎥
⎥p =⎢
⎢0 0 1/2 1/2⎥⎢⎥1/2 0 0 1/2⎣⎦输入本程序,经过MATLAB 软件运行判断其为对称信道,利用函数message 来求平均互信息量,得出信道1的平均互信息量为hf1=0.1250,此时离散信源的平均信息量为:hx=0,最终得出信道1的信道容量:c1=0.125
总 结
本次课程设计我的课题是对称信道容量求解的设计,开始的一个星期我针对这个课题的任务要求从图书馆、上网等渠道获取相关信息,查找相关的参考资料,然后设定了本课题的设计方案。经过近多日的努力,终于将本次课程设计做完了,但由于水平有限,文中肯定有很多不恰当的地方,请老师指出其中的错误和不当之处,使我能做出改正,我会虚心接受。在本次课程设计过程中,我增强了自己的动手能力和分析能力。通过跟同学的交流,也通过自己的努力,我按时完成了这次课程设计。在此过程中,我学会了很多,也看到了很多自己的不足之处。在以后的学习生活中,我会努力学习专业知识,完善自我,为将来的发展做好充分的准备。
总之,在这次课程设计中,我受益匪浅,学到了很多书本上所没有的东西,懂得了理论和实际联系的重要性。在以后的学习中,我不仅要把理论知识掌握牢固,更要提高自己的动手能力和分析能力。
致 谢
通过两周的努力,终于将信息论与编码课程设计完成了。本次课程设计目的是让我们对所学的专业知识有更进一步的了解和巩固,让我们能灵活运用所学的专业知识。在这次设计里我学到了很多,这对我来说是一种进步,每个人只要自己和自己比,每一次小的进步就是大的突破。在这次设计中我还看的了同学的友爱,当遇到困难时只要他们知道的就会耐心地指导和帮助,在论文完成之际,我要特别感谢指导老师的热情关怀和悉心指导。每次当我有问题的时候去问老师,她都能耐心的帮我指导,和我一起解决困难。通过这次的课程设计,不仅使我学到了很多专业方面的知识,也让我明白了不畏困难、勇于攀登艰难的重要性,这对我未来的学习和生活产生很大的影响。所以我觉得这次课程设计既能增强我们的动手能力、思维能力、实践能力、还能增进友情。这次课程设计对我来说真可畏受益匪浅啊!
在此,再次感谢我的学校和指导老师。
参考文献
[1]曹雪虹,张宗橙. 信息论与编码. 北京:清华大学出版社,2007; [2]王慧琴,数字图像处理. 北京:北京邮电大学出版社,2007; [3]张德丰,MATLAB 通信工程仿真 北京:机械工程出版社,2010; [4]陈鲁生,信息论与编码 北京:科学出版社,2010;