信息论与编码第一讲.pptx

主要内容主要内容v课程介绍课程介绍v信息概念、信息论信息概念、信息论v信息的度量信息的度量v信道及其容量信道及其容量一、课程介绍一、课程介绍信息论与信道编码信息论与信道编码教学目标教学目标香农信息论的基本理论香农信息论的基本理论信息的统计度量，信源，信道和信道容量。信息的统计度量，信源，信道和信道容量。编码的理论和实现原理编码的理论和实现原理近世代数基础近世代数基础；信道编码定理；线性分组码；信道编码定理；线性分组码、循环码、循环码、卷积码卷积码、Turbo码的码的编、译码方法编、译码方法。教学重点教学重点 信息度量、信源描述、信道容量信息度量、信源描述、信道容量近世代数基础近世代数基础、线性分组码、线性分组码、循环码、循环码、卷积码、卷积码、Turbo码的码的编、译码方法编、译码方法。教学计划教学计划第一讲：第一讲：信息论信息论（复习）（复习）第二讲：第二讲：有噪信道编码理论、有噪信道编码理论、线性分组码线性分组码（讲述和讨论）（讲述和讨论）第三讲：第三讲：近世代数基础、循环码近世代数基础、循环码（讲述和（讲述和讨论）讨论）第四讲：第四讲：BCH码、码、RS码码（讲述和讨论）（讲述和讨论）第五讲：第五讲：卷积码编码卷积码编码（讲述和讨论）（讲述和讨论）第六讲：第六讲：卷积码卷积码译译码码（讲述和讨论）（讲述和讨论）第七讲：第七讲：Turbo码码（讲述和讨论）（讲述和讨论）（1）纠错码纠错码原理与方法原理与方法（2001），西安电子科，西安电子科 技大学出版社技大学出版社；（2）傅祖芸编著，信息论基础理论与应用傅祖芸编著，信息论基础理论与应用（2001），北京：电子工业出版社；，北京：电子工业出版社；（3）姜丹，信息论与编码姜丹，信息论与编码（2001），合肥，中，合肥，中国科学技术大学出版社；国科学技术大学出版社；（4）曹雪虹，张宗橙，信息论与编码曹雪虹，张宗橙，信息论与编码（2004），北，北京，清华大学出版社京，清华大学出版社。参考书参考书计分方式计分方式u 期终考试占期终考试占60u 专题报告占专题报告占20；个人报告占；个人报告占20u 小论文占小论文占20%二、信息概念、信息论二、信息概念、信息论2.1 信息信息u信息、消息、信号信息、消息、信号u信息信息是抽象、复杂的概念，它包含在消息之中，是是抽象、复杂的概念，它包含在消息之中，是通信系统中传递的对象通信系统中传递的对象。2.2 信息定义信息定义 信息就是事物运动的状态和方式，就是关于事信息就是事物运动的状态和方式，就是关于事物运动的千差万别的状态和方式的知识。物运动的千差万别的状态和方式的知识。2.3 研究信息的目的研究信息的目的：为了准确地把握信息本质和特：为了准确地把握信息本质和特点，以便有效地利用信息。点，以便有效地利用信息。2.4 香农信息论香农信息论 1948年年，美美国国数数学学家家克克劳劳特特香香农农（C.E.Shannon）发发表表了了一一篇篇著著名名论论文文“通通信信的数学理论的数学理论”。该该论论文文给给出出了了信信息息传传输输问问题题的的一一系系列列重重要要结结果果，建建立立了了比比较较系系统统的的信信息息理理论论香农信息论香农信息论。信息论奠基人信息论奠基人香农香农“通信的基本问题就是在一通信的基本问题就是在一点重新准确地或近似地再点重新准确地或近似地再现另一点所选择的消息现另一点所选择的消息”。这是香农在他的惊世之著这是香农在他的惊世之著通信的数学理论通信的数学理论中的中的一句铭言。正是沿着这一一句铭言。正是沿着这一思路思路,他应用数理统计的方他应用数理统计的方法来研究通信系统，从而法来研究通信系统，从而创立了影响深远的信息论。创立了影响深远的信息论。他的成就轰动了世界，他的成就轰动了世界，激起了人们对信息理论的巨激起了人们对信息理论的巨大热情。信息论向各门学科大热情。信息论向各门学科冲击，研究规模像滚雪球一冲击，研究规模像滚雪球一样越来越大。不仅在电子学样越来越大。不仅在电子学的其他领域，如计算机、自的其他领域，如计算机、自动控制等方面大显身手，而动控制等方面大显身手，而且遍及物理学、化学、生物且遍及物理学、化学、生物学、心理学、医学、经济学、学、心理学、医学、经济学、人类学、语音学、统计学、人类学、语音学、统计学、管理学管理学等学科。它已远等学科。它已远远地突破了香农本人所研究远地突破了香农本人所研究和意料的范畴，即从香农的和意料的范畴，即从香农的所谓所谓“狭义信息论狭义信息论”发展到发展到了了“广义信息论广义信息论”。三、信息的度量三、信息的度量3.1 自信息量自信息量随机事件随机事件出现概率出现概率自信息量定义自信息量定义v随机事件的不确定性随机事件的不确定性出现概率小的随机事件所包含的不确定性大，出现概率小的随机事件所包含的不确定性大，它的自信息量大。它的自信息量大。出现概率大的随机事件所包含的不确定性小，出现概率大的随机事件所包含的不确定性小，它的自信息量小。它的自信息量小。在极限情况下，出现概率为在极限情况下，出现概率为1的确定性事件，的确定性事件，其自信息量为零。其自信息量为零。条件自信息量条件自信息量v条件自信息量用其条件概率的负对数来量度条件自信息量用其条件概率的负对数来量度 随机事件随机事件条件概率条件概率条件自信息量条件自信息量条件自信息量：能在规定条件下唯一地确定该事件条件自信息量：能在规定条件下唯一地确定该事件必须提供的信息量。必须提供的信息量。3.2 互信息量互信息量v先验概率先验概率对于预先知道信源对于预先知道信源X集合的概率空间集合的概率空间P(xi)的情况，各个的情况，各个符号符号xi(i=1,2,)的概率的概率P(xi)。v后验概率后验概率当信宿当信宿Y收到集合中的一个符号收到集合中的一个符号yj后，接收者重新估计后，接收者重新估计的关于信源各个符号的概率分布就变成条件概率。对的关于信源各个符号的概率分布就变成条件概率。对消息消息xi而言，其条件概率定义为而言，其条件概率定义为P(xi|yj)。v互信息量互信息量 互信息量定义为后验概率与先验概率比值的对数：互信息量定义为后验概率与先验概率比值的对数：3.3 通信熵通信熵v无记忆信源无记忆信源信源往往包含着多个符号，且各个符号的出现信源往往包含着多个符号，且各个符号的出现概率按信源的概率空间分布。概率按信源的概率空间分布。当各个符号的出现相互独立时，这种信源称为当各个符号的出现相互独立时，这种信源称为无记忆信源。无记忆信源。无记忆信源的平均自信息量是各消息自信息量无记忆信源的平均自信息量是各消息自信息量的概率加权平均值（统计平均值）。的概率加权平均值（统计平均值）。v通信熵通信熵平均自信息量平均自信息量自信息量自信息量代入代入信息论的一个基本的重要公式。信息论的一个基本的重要公式。此式与统计热力学中此式与统计热力学中“熵熵”的表示形式相同，因此往的表示形式相同，因此往往把平均自信息量往把平均自信息量H(X)H(X)称为熵。称为熵。H(X)H(X)是是P(x)P(x)的函数。的函数。v定理定理:熵满足不等式熵满足不等式v当且仅当信源中各符号的出现概率当且仅当信源中各符号的出现概率P(x)都等于时都等于时1/M，上式取等号，可得最大熵：，上式取等号，可得最大熵：二元信源的信源熵二元信源的信源熵二元信源的信源熵二元信源的信源熵v信源信源X有两个消息，有两个消息，M=2一个符号出现概率一个符号出现概率P另一个符号出现概率另一个符号出现概率1P该信源的熵该信源的熵H(P)H(P)1 10 01 10.50.5P P最大熵最大熵条件熵条件熵v条件熵是联合空间条件熵是联合空间XY上上的的条件自信息量条件自信息量的概率加权的概率加权平均值。平均值。v若给定若给定x条件下条件下y的条件自信息量为的条件自信息量为I(y|x)，则它，则它在在XY集合上的概率加权平均值集合上的概率加权平均值H(Y|X)定义为：定义为：vH(Y|X)为条件熵，也可直接定义为：为条件熵，也可直接定义为：共熵共熵v共熵（又称联合熵）是联合空间共熵（又称联合熵）是联合空间XY上的每个元素上的每个元素对对xy的自信息量的概率加权平均值，定义为：的自信息量的概率加权平均值，定义为：与信源熵和条件熵的关系与信源熵和条件熵的关系21联合熵与条件熵的关系联合熵与条件熵的关系 全概率公式全概率公式所以所以 H(X Y)=H(X)H(Y|X)同理同理 H(X Y)=H(Y)H(X|Y)而当而当X、Y 是统计独立的两个信源：是统计独立的两个信源：H(X Y)=H(X)H(Y)3.4 平均互信息量平均互信息量XYXY联合集上的平均条件互信息量联合集上的平均条件互信息量定理定理2.52.5XYXY联合集上的条件互信息量满足联合集上的条件互信息量满足当且仅当当且仅当X X集合中的各集合中的各x x都与都与y yi i独立时，等号成立独立时，等号成立通过有扰信道的接收符号通过有扰信道的接收符号任意一个可能被传输的消息任意一个可能被传输的消息结论：有扰信道中接收到的符号所提供的结论：有扰信道中接收到的符号所提供的关于传输消息的平均信息量总是非负量。关于传输消息的平均信息量总是非负量。v平均互信息量平均互信息量：平均条件互信息量平均条件互信息量在整个在整个Y集合上的概率加权平均值集合上的概率加权平均值。特性特性互易性互易性与熵和条件熵的关系与熵和条件熵的关系与熵和共熵的关系与熵和共熵的关系条件熵可看作由于信道噪声而损失的信息量（损失熵）条件熵可看作由于信道噪声而损失的信息量（损失熵）也可以看作由于信道噪声所造成的对信源消息的平均不确定性也可以看作由于信道噪声所造成的对信源消息的平均不确定性 疑义度疑义度条件熵可看作唯一地确定信道噪声所需要的平均信息量（散布度）条件熵可看作唯一地确定信道噪声所需要的平均信息量（散布度）噪声熵噪声熵无扰信道无扰信道噪声很大的信道噪声很大的信道四、信道及其四、信道及其容量容量4.14.2 4.3 4.3 信道容量计算信道容量计算 离散信道离散信道可分成：可分成：特殊信道特殊信道无噪无损信道无噪无损信道有噪无损信道有噪无损信道 无噪有损信道无噪有损信道 有干扰无记忆有干扰无记忆信道信道有干扰有记忆有干扰有记忆信道信道特殊信道特殊信道信道名称信道名称信道特征信道特征信息传输情况信息传输情况全损信道全损信道 P(xy)=P(x)P(y)H(X/Y)=H(X)I(X;Y)=0无损无噪无损无噪信道信道P(x/y)=0 or 1且且P(y/x)=0 or 1H(X/Y)=H(Y/X)=0I(X;Y)=H(X)=H(Y)无损信道无损信道 P(x/y)=0 or 1H(X/Y)=0I(X;Y)=H(X)无噪信道无噪信道 P(y/x)=0 or 1H(Y/X)=0I(X;Y)=H(Y)对称对称DMC信道信道对称性:每一行都是由同一集p1,p2,pm 的诸元素不同排列组成输入对称每一列都是由集q1,q2,qn的诸元素不同排列组成输出对称满足对称性,所对应的信道是对称离散信道。信道矩阵 不具有对称性,因而所对应的信通不是对称离散信道。若输入符号和输出符号个数相同,都等于n,且信道矩阵为此信道称为强对称信道(均匀信道)信道矩阵中各列之和也等于1 对称离散信道的平均互信息为对称对称DMCDMC信道的容量信道的容量 上式是对称离散信道能够传输的最大的平均信息量,它只与对称信道矩阵中行矢量p1,p2,pm 和输出符号集的个数m有关。强对称信道的信道容量：设二进制对称信道的输入概率空间信道矩阵：4.4 BSC信道容量信道容量当p固定时,I(X,Y)是的 型上凸函数。BSC信道容量信道容量I(XY)1-H(p)I(X,Y)对存在一个极大值。pC当固定信源的概率分布时,I(X,Y)是p的 型 下凸函数。信道无噪声当p=0,C=10=1bit=H(X)当p=1/2,信道强噪声BSC信道容量信道容量当信源输入符号的速率为rs(符/秒),信道容量实际信息传输速率Rt为 进入信道输入端的信息速率 4.5 4.5 一般一般DMCDMC信道信道定理：一般离散信道的平均互信息I(X;Y)达到极大值的充分和必要条件是输入概率p(ai)必须满足:I(ai;Y)=C 对于所有ai其p(ai)0 I(ai;Y)C 对于所有ai其pai)=0上式说明：当信道的平均互信息I(X;Y)达到信道容量时,输入符号概率集p(ai)中每一个符号ai对输出端Y提供相同的互信息，只是概率为0的除外。5 连续信道及其容量连续信道及其容量当信道为加性连续信道时，情况较简单。当信道为加性连续信道时，情况较简单。设信道的输入和输出信号是随机过程设信道的输入和输出信号是随机过程x(t)和和y(t)y(t)=x(t)+n(t)n(t)：信道的加性高斯白噪声：信道的加性高斯白噪声 一个受加性高斯白噪声干扰的带限波形信道的容一个受加性高斯白噪声干扰的带限波形信道的容量，由香农量，由香农(1948)正式定义：正式定义：信 道n(t)x(t)y(t)高斯白噪声加性信道单位时间的信道容量高斯白噪声加性信道单位时间的信道容量这就是著名的香农公式 5.1 连续信源的熵和互信息连续信源的熵和互信息 连续信源的输出是取值连续的单个随机变量，可用连续信源的输出是取值连续的单个随机变量，可用变量的概率密度变量的概率密度p(x)来描述。此时，连续信源的数来描述。此时，连续信源的数学模型为：学模型为：其中，其中，R是全实数集，是变量是全实数集，是变量X的取值范围。的取值范围。对连续变量，可用离散变量来逼近，即连续变量可对连续变量，可用离散变量来逼近，即连续变量可以认为是离散变量的极限情况。量化单位越小，则以认为是离散变量的极限情况。量化单位越小，则所得的离散变量和连续变量越接近。所得的离散变量和连续变量越接近。把连续信源概率密度的取值区间把连续信源概率密度的取值区间a,b分割成分割成n个小个小区间，各小区间设有等宽区间，各小区间设有等宽=(b-a)/n，那么，那么，x处于第处于第i 区间的概率区间的概率Pi是：是：其中，其中，xi是是a+(i-1)到到a+i之间的某一值。当之间的某一值。当p(x)是是x的的连续函数时，由积分中值定理可知，必存在一个连续函数时，由积分中值定理可知，必存在一个xi 值值使上式成立。使上式成立。此时，连续变量此时，连续变量X就可以用取值为就可以用取值为xi(i=1,2,n)的离散变量的离散变量 xn 来近似。连续信源来近似。连续信源X被量化为离散信源：被量化为离散信源：且且 这时离散信源这时离散信源xn 的熵：的熵：当当 时，离散随机变量时，离散随机变量xn 趋于连续随机变趋于连续随机变量量X，而离散信源，而离散信源xn 的熵的熵 H(xn)的极限值就是连续信的极限值就是连续信源的信息熵。源的信息熵。一般情况下，上式的第一项是定值，而当一般情况下，上式的第一项是定值，而当时，第二项是趋于无限大的常数。所以避开第二项，时，第二项是趋于无限大的常数。所以避开第二项，定义定义连续信源的熵连续信源的熵为：为：由上式可知，所定义的连续信源的熵并不是由上式可知，所定义的连续信源的熵并不是实际信源输出的绝对熵，连续信源的绝对熵应该还实际信源输出的绝对熵，连续信源的绝对熵应该还要加上一项无限大的常数项。这一点可以这样理解：要加上一项无限大的常数项。这一点可以这样理解：因为连续信源的可能取值数是无限多个，若设取值因为连续信源的可能取值数是无限多个，若设取值是等概分布，那么信源的不确定性为无限大。当确是等概分布，那么信源的不确定性为无限大。当确知信源输出为某值后，所获得的信息量也将为无限知信源输出为某值后，所获得的信息量也将为无限大。大。既然如此，那么为什么还要那样来定义连续信既然如此，那么为什么还要那样来定义连续信源的熵呢？一方面，因为这样定义可与离散信源的源的熵呢？一方面，因为这样定义可与离散信源的熵在形式上统一起来（这里用积分代替了求和）；熵在形式上统一起来（这里用积分代替了求和）；另一方面，因为在实际问题中，常常讨论的是熵之另一方面，因为在实际问题中，常常讨论的是熵之间的差值，如平均互信息等。在讨论熵差时，只要间的差值，如平均互信息等。在讨论熵差时，只要两者离散逼近时所取的间隔两者离散逼近时所取的间隔一致，无限大项常数一致，无限大项常数将互相抵消掉。由此可见，连续信源的熵将互相抵消掉。由此可见，连续信源的熵h(X)称为称为差熵，以区别于原来的绝对熵。差熵，以区别于原来的绝对熵。同理，可以定义两个连续变量同理，可以定义两个连续变量X、Y的联合熵的联合熵和条件熵，即和条件熵，即 它们之间也有与离散信源一样的相互关系，并且可它们之间也有与离散信源一样的相互关系，并且可以得到有信息特征的互信息：以得到有信息特征的互信息：这样定义的熵虽然形式上和离散信源的熵相似，但这样定义的熵虽然形式上和离散信源的熵相似，但在概念上不能把它作为信息熵来理解。连续信源的在概念上不能把它作为信息熵来理解。连续信源的差熵值具有熵的部分含义和性质，而丧失了某些重差熵值具有熵的部分含义和性质，而丧失了某些重要的特性。要的特性。5.2 最大熵定理最大熵定理 在离散信源中，当信源符号等概率分布时信源的在离散信源中，当信源符号等概率分布时信源的熵取最大值。在连续信源中，差熵也具有极大值，但熵取最大值。在连续信源中，差熵也具有极大值，但其情况有所不同。除存在完备集条件其情况有所不同。除存在完备集条件 以外，还有其它约束条件。当各约束条件不同时，以外，还有其它约束条件。当各约束条件不同时，信源的最大熵值不同。一般情况，在不同约束条件下，信源的最大熵值不同。一般情况，在不同约束条件下，求连续信源的差熵的最大值，就是在下述若干约束条求连续信源的差熵的最大值，就是在下述若干约束条件。件。求泛函求泛函 的极值。的极值。通常感兴趣的是两种情况：一种是信源的输出通常感兴趣的是两种情况：一种是信源的输出值受限；另一种是信源的输出平均功率受限。下面值受限；另一种是信源的输出平均功率受限。下面分别加以讨论。分别加以讨论。（1）峰值功率受限条件下信源的最大熵）峰值功率受限条件下信源的最大熵 定理：定理：若信源输出的幅度被限定在若信源输出的幅度被限定在a,b区域内，则当区域内，则当输出信号的概率密度是均匀分布时，信源具有最大输出信号的概率密度是均匀分布时，信源具有最大熵。其值等于熵。其值等于log(b-a)。此时，此时，（2）平均功率受限条件下信源的最大熵）平均功率受限条件下信源的最大熵 定理：定理：若一个连续信源输出符号的平均功率被限定为若一个连续信源输出符号的平均功率被限定为P（这里是指的交流功率，即方差（这里是指的交流功率，即方差 ），则其），则其输出信号幅度的概率密度分布是高斯分布时，信源输出信号幅度的概率密度分布是高斯分布时，信源有最大的熵，其值为有最大的熵，其值为 。高斯分布（正态分布）：（其中，高斯分布（正态分布）：（其中，m为数学期为数学期望，方差为望，方差为 ）在限制信号平均功率的条件下，正态分布的信源有在限制信号平均功率的条件下，正态分布的信源有最大差熵，其值随平均功率的增加而增加。最大差熵，其值随平均功率的增加而增加。上述定理说明，连续信源在不同的限制条件下有不上述定理说明，连续信源在不同的限制条件下有不同的最大熵，在无限制条件时，最大熵不存在。同的最大熵，在无限制条件时，最大熵不存在。根据最大熵定理可知，如果噪声是正态分布时，则根据最大熵定理可知，如果噪声是正态分布时，则噪声熵最大，因此高斯白噪声获得最大噪声熵。也噪声熵最大，因此高斯白噪声获得最大噪声熵。也就是说，高斯白噪声是最有害的干扰，在一定平均就是说，高斯白噪声是最有害的干扰，在一定平均功率下，造成最大数量的有害信息。在通信系统中，功率下，造成最大数量的有害信息。在通信系统中，往往各种设计都将高斯白噪声作为标准，并不完全往往各种设计都将高斯白噪声作为标准，并不完全是为了简化分析，而是根据最坏的条件进行设计获是为了简化分析，而是根据最坏的条件进行设计获得可靠性。得可靠性。