信息论与编码纠错第1章.ppt

信息论与编码,第一章,信 息 论 基 础,内容提要,信息论是应用近代概率统计方法研究信息传输、交换、存储和处理的一门学科，也是源于通信实践发展起来的一门新兴应用科学。,本章首先引出信息的概念，简述信息传输系统模型的各个组成部分，进而讨论离散信源和离散信道的数学模型，简单介绍几种常见的离散信源和离散信道。,1.1 信息的基本概念,信息：物质和能量在空间和时间上分布的不均匀程度，或者说信息是关于事物运动的状态和规律。,一信息的基本含义,二信息、消息和信号的区别与联系,信息：指事物运动的状态及状态变化的方式，是抽象的意识或知识。,消息：一般指包含有信息的语言、文字和图像，它载荷信息，但它不是物理性的。,信号：是消息的物理体现，消息要传输，必须加载到某种特征的信号上去，它是信息的载体，是物理性的。,通信系统中形式上传输的是消息，实质上传输的是信息，实际上传输的是信号。消息中包含信息，消息是信息的载体。,三什么是信息论,四信息论的发展及范畴划分,1狭义信息论：即通信的数学理论，主要研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的编码定理。（香农信息论）,2实用信息论：研究信息传输和处理问题，也就是狭义信息论方法在调制解调、编码译码以及检测理论等领域的应用。,3广义信息论：包括信息论在自然和社会中的新的应用，如模式识别、机器翻译、自学习自组织系统、心理学、生物学、经济学、社会学等一切与信息问题有关的领域。,信息论：,研究信息的基本性质及度量方法，研究信息的获取、传输、存储和处理的一般规律的科学,。,1.2 信息传输系统,信息传输系统模型,1信 源：产生消息的源。,2编码器：将消息变成适合于信道传送的信号的设备。,（1）信源编码器：对信源输出的消息进行适当的变换和处理，以达到减少或消除信源冗余度来提高信息的传输速率。,（2）信道编码器：对信源编码器的输出进行变换和处理，通过增加冗余度来提高信息传输的可靠性。,可靠性研究把信源编码、保密编码并入信源,信道编码,信道译码,信道,广义信源,广义信宿,信道编码,信源编码,保密译码,信道译码,信源译码,保密编码,噪声,信道,信源,信宿,保密性、认证性研究把信源编码并入信源，信道编码并入信道,保密译码,保密编码,无噪广义信道,广义信源,广义信宿,信道编码,信源编码,保密译码,信道译码,信源译码,保密编码,噪声,信道,信源,信宿,1.3 离散信源及其数学模型,一信源的描述及分类,1信源的描述,信源是产生消息的源，消息是随机的，因此可以用随机变量或随机过程来描述消息，在信息论中，通常用一个样本空间及其概率测度,X,，,p,(X)来描述信源。,2信源的分类,根据,X,的不同情况,(1)离散信源：消息集X为离散集合，即时间和空间都离散的信源；,(2)连续信源：时间离散而空间连续的信源；,(3)波形信源：时间连续的信源，如语言、图像等。,根据信源的统计特性,(1),无记忆信源：X的各时刻取值相互独立；,(2)有记忆信源：X的各时刻取值相互有关联。,二离散无记忆信源,离散无记忆信源,（Discrete Memoryless Source，简记为DMS）输出的是单个符号的消息，不同时刻发出的符号之间彼此统计独立，而且符号集中的符号数目是有限的或可数的。,离散无记忆信源的,数学模型,为离散型的概率空间，即,【例】,二进制对称信源只能输出符号0或1，输出0的概率为p，输出1的概率为1-p，信源概率空间描述为：,【例】随机掷一个无偏的骰子，可能出现的点数与其概率分布为：,三离散无记忆的扩展信源,实际情况下，信源输出的消息往往不是单个符号，而是由许多不同时刻发出的符号所组成的符号序列。设序列由,N,个符号组成，若这,N,个符号取自同一符号集,a,1,a,2,a,k,，并且先后发出的符号彼此间统计独立，我们将这样的信源称作,离散无记忆的N维扩展信源,。其数学模型为N维概率空间：,为各种长为,N,的符号序列。,=,x,1,x,2,x,N,，,x,i,a,1,，,a,2,，,a,k,，1,i,N。,序列集,X,=,a,1,a,1,a,1,a,1,a,1,a,2,a,k,a,k,a,k,，共有,M,=,k,N,种序列。,由于序列是无记忆的，故序列的概率为：,【例】,将二进制对称信源进行二维无记忆扩展，则信源序列共M2,2,4种：00，01，10，11。,由 ，得各序列的概率依次为：,则将这4种序列看成4个符号，得到一个新的信源，即,四离散平稳有记忆信源,如果该条件概率分布与时间起点无关，只与关联长度有关，则该信源为,平稳信源,。,中、英文句子中前后出现的汉字、字母往往是有依赖的。这种依赖性我们称作,有记忆,。,一般用,联合概率空间,来描述离散有记忆信源的输出。由于具有关联性，信源在,i,时刻发出什么符号与,i,时刻以前信源所发出的符号有关，即由,条件概率,p,(,x,i,x,i,-1,x,i,-2,),确定。,对于,离散平稳有记忆信源,，有,【例】,某离散平稳信源 ，设信源发出的符号只与前一个符号有关，其关联程度用表所示联合概率,p,(,x,i,x,j,)表示（,x,i,为前一个符号，,x,j,为后一个符号），求条件概率：,x,j,x,i,0,1,2,0,1/3,1/9,0,1,1/9,1/18,1/6,2,0,1/6,1/18,p,(,x,i,x,j,),p,(,x,j,/,x,i,),由 可计算出,p,(,x,j,/,x,i,)，如表。,x,j,x,i,0,1,2,0,3/4,1/4,0,1,1/3,1/6,1/2,2,0,3/4,1/4,五马尔可夫信源,多数有记忆信源的记忆长度是有限的，即某一时刻信源发出的符号只与前面已发出的若干个符号有关。为了描述这种有限的记忆关系，常引入“,状态,”的概念，这样，信源发出的符号消息与信源所处的状态有关。,设信源 r 时刻发出的符号 x,r,与前m个符号x,r-1,，x,r-2,，.，x,r-m,有关（,称做m阶,），这m个时间上依次相邻的符号组成一个,状态s,。,若 ，则可能的状态s有k,m,种：。,用e,r,表示r时刻的状态:,当符号,x,r,发出后状态将改变，记为,当状态转移概率和已知状态下发符号的概率与时刻无关，即：,称为,时齐,。,马尔可夫信源的两个条件：,（1）某一时刻信源的输出只与当时的信源状态有关，而与以前的状态无关，即,且满足：,（2）某一时刻信源所处的状态只由前一时刻的输出符号和前一时刻的状态唯一确定,当时齐马尔可夫信源达到平稳分布时，满足：,【例】,某二阶平稳时齐马尔可夫信源，设信源符号集为a,1,，a,2,，状态集为s,1,=a,1,a,1,，s,2,=a,1,a,2,或a,2,a,2,，s,3,=a,2,a,1,，各状态之间的转移情况如图(,香农线图,)所示，求平稳时各状态的概率分布。,【解】由图可得在已知状态下发符号的概率分别为：,状态的一步转移概率为：,当系统达到平稳分布时，可得：,解方程组，可得平稳时各状态的概率分布：,1.4 离散信道及其数学模型,信道是信息传输的通道，如图所示，信道可看作一个变换器，它将输入消息,x,变换成输出消息,y,，通常用信道转移概率,p,(,y,x,)来描述信道的统计特性。,一信道模型及分类,1.信道模型：,（1）根据输入和输出信号的特点可分为：,2.信道分类：,离散信道：输入和输出都是时间上离散、取值离散的随机序列。离散信道有时也称为数字信道。,连续信道：输入和输出都是时间上离散、取值连续的随机序列，又称为模拟信道。,半连续信道：输入、输出序列一个是离散的，而另一个是连续的。,波形信道：输入和输出都是时间和取值均连续的随机信号。,（2）根据统计特性，即转移概率,p,(,y,x,)的不同，信道又可分类为：,无记忆信道：信道的输出y只与当前时刻输入x有关。,有记忆信道：信道的输出y不仅与当前时刻输入有关，还与以前的输入有统计关系。,离散无记忆信道（DMC，Discrete Memoryless Channel）的输入和输出消息都是离散无记忆的单个符号，设输入符号,x,i,a,1,a,2,a,k,，1,i,I,，输出符号,y,j,b,1,b,2,b,D,，1,j,J,，信道的特性可表示为转移概率矩阵：,二离散无记忆信道,1离散无记忆信道特性描述,将信道特性表示成图的形式：,p,(,y,j,x,i,)对应为已知输入符号为,x,i,，当输出符号为,y,j,时的信道转移概率，满足：,0,p,(,y,j,x,i,),1,，且 （Y完备）,2几种常见的离散无记忆信道,（1）二元对称信道,（Binary Symmetric Channel，简记为BSC）。,这是一种很重要的信道，它的输入符号,x,0,1,，输出符号,y,0,1,，转移概率,p,(,y,x,)如图所示，信道特性可表示为信道矩阵：,其中,p,称作信道错误概率。,（2）无干扰信道,这是一种最理想的信道，也称作无噪信道，信道的输入和输出符号间有确定的一一对应关系，即,如图所示三元无干扰信道中，,x,y,0,1,2,对应信道矩阵是单位矩阵,（3）二元删除信道,对接收符号不能作出肯定或否定判决时，引入删除符号，表示对该符号存有疑问，作为有误或等待得到更多信息时再作判决。,二元删除信道如图所示，输入符号,x,0,1,，输出符号,y,0,e,1，转移概率矩阵为：,（4）二元Z信道,二元,Z,信道如图所示，输入符号,x,0,1,，输出符号,y,0,1，,转移概率矩阵为：,三,离散无记忆的扩展信道,N,维离散扩展信道的输入和输出都是长为,N,的消息序列，如图所示：,若,x,i,a,1,a,2,a,k,，,y,j,b,1,b,2,b,D,，1,i,j,N,。,输入消息序列集：,X,=,a,1,a,1,a,1,a,1,a,1,a,2,a,k,a,k,a,k,。,输出消息序列集为,Y,=,b,1,b,1,b,1,b,1,b,1,b,2,b,D,b,D,b,D,。,信道的特性用序列的转移概率描述：,当信道无记忆时,且满足：,【例】求二元对称信道的二维扩展无记忆信道的转移概率矩阵。,【解】二元对称信道的输入符号,x,0,1,，输出符号,y,0,1,，转移概率,p,(0/,0)=,p,(1/,1)=1-,p,，,p,(1/,0)=,p,(0/,1)=,p,，二维扩展后输入和输出都是长为2的符号序列：,可以计算出序列的转移概率 分别为,p,(00,/,00)=,p,(0/,0),p,(0/,0)=(1-,p,),2,p,(01/,00)=,p,(0/,0),p,(1/,0)=(1-,p,),p,p,(11/,11)=,p,(1/,1),p,(1/,1)=(1-,p,),2,信道的转移概率矩阵为：,本 章 小 结,本章是信息论的基本概念，介绍的主要内容有：,(1)信息是关于事物运动的状态和规律。从通信的角度讲，信息论是应用近代概率统计方法研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的编码定理。,信息传输系统由信源、信源及信道编码器、信道、信源及信道译码器、信宿组成。信源和信宿用来产生和接收消息。信源编码将信源的剩余度剔除，信道编码增加冗余的纠错、检错码元。信道是消息传输的通道。,信源分为离散的和连续的，无记忆的和有记忆的。信源的数学模型为一个样本空间及其概率测度,X,q(X),。,信道分为离散的和连续的，无记忆的和有记忆的。信道的数学模型用转移概率描述。离散无记忆信道的输入和输出都是离散无记忆的单个符号。离散无记忆,N,维扩展信道的输入和输出都是长为,N,的符号序列。序列的信道转移概率是序列中对应,N,个符号的信道转移概率的乘积。,作业：,某时齐马尔可夫信源，状态转移情况如图所示，设信源符号集为a,1,，a,2,，a,3,，状态集为s,1,=xa,1,，s,2,=xa,2,，s,3,=xa,3,。,（1）,求平稳后各状态出现的概率。,（2）若初始时刻l=0时处于状态,s,1,，求l=2时刻x,2,=a,1,的概率。,（3）求稳态下字母a,3,a,1,a,2,a,1,a,2,的概率。,