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