信息论与编码全部课件.ppt

1,1 绪论,1.1 信息的概念1.1.1 信息的定义与性质1.1.2 信息的分类1.2 信息传输系统的组成及功能1.2.1 模拟信息传输系统1.2.2 数字信息传输系统1.3 信息论研究对象和内容1.4 信息论发展简史,2,1.1.1 信息的定义与性质,古时的通信：烽火台信息传播五阶段：手势和语言文字印刷术电磁波计算机和通信微电子技术、通信技术和计算机技术促进了信息技术发展。信息产业的发展促进了社会产业结构的变化与发展。,3,1.1.1 信息的定义与性质,信息：认识主体所感受的或所表达的事物的运动状态和运动状态的变化方式。（1）信息是普遍存在的。（2）信息与物质。（3）信息与能量。（4）人类认识事物，变革事物必须要有信息。信息载体：运载信息的物质。,4,1.1.1 信息的定义与性质,消息：以文字、语音、图像等这些能够为人们的感觉器官所感知的物理现象，把客观物质运动和主观思维活动的状态表达出来就成为消息。,信号：消息的表现形式和载体。同一信息可用不同的信号来表示，同一信号也可表达不同的信息。,5,1.1.1 信息的定义与性质,信息十分抽象而又复杂的概念，是人们对客观事物感触到的新认识。消息信息的载荷者，是描述信息的一种表现形式，是对某个事物的描述和反应。信号运载或携带消息的任何物理量，达到迅速有效地传递和交换信息的目的。,6,1.1.1 信息的定义与性质,性质：（1）普遍性：信息是普遍存在的。（2）无限性：信息是无限的。（3）相对性：对同一事物不同的观察者所获得的信息量可能不同。,（4）转换性：信息可以在时间上或空间中从一点转移到另一点。（5）变换性：信息是可变的，它可以由不同的载体或不同的方法来载荷。,7,1.1.1 信息的定义与性质,（6）有序性：信息可以用来消除系统的不定性，增加系统的有序性。（7）动态性：信息具有动态性质，一切活的信息都随时间变化，具有时效性。（8）转化性：在一定条件下，信息可以转化为物质、能量、时间等。,（9）共享性：同一信息可以被无限的人所获得，可以交流而不会减少。（10）可量度性：信息的数量与质量是可量度的即信息量。,8,1.1.2 信息的分类,（1）从性质分：语法信息、语义信息、语用信息。,9,1.1.2 信息的分类,举例说明，两个布袋中装有对人手感觉完全一样的球，但颜色和数量不同，（1）50个红球和50个白球（2）红球、白球、黑球、黄球各25个随意拿出一个球，被告知是红球所获得的信息量。,10,1.1.2 信息的分类,（2）按观察的过程分：实在信息、先验信息、实得信息。（3）按信息的地位分：客观信息、主观信息。（4）按作用分：有用信息、无用信息、干扰信息。,（5）按逻辑意义分：真实信息、虚假信息、不定信息。（6）按传递方向分：前馈信息、反馈信息。,11,1.1.2 信息的分类,（7）按生成领域分：宇宙信息、自然信息、社会信息、思维信息等。（8）按应用部门分：工业信息、农业信息、军事信息、政治信息、科技信息、文化信息等。,（9）按信息源的性质分：语声信息、图像信息、文字信息、数据信息、计算信息等。（10）按载体性质分：电子信息、光学信息、生物信息等。（11）按携带信息的信号形式分：连续信息、离散信息、半连续信息等。,12,1.2.1 模拟信息传输系统,该系统传递的是模拟信号，它在任意时刻的取值是任意的，是时间的连续函数。基本模型如图1.1 所示：,13,1.2.1 模拟信息传输系统,信息源：产生含有信息的消息，是被传输的对象。信息宿：信息传送的目的地，即原消息的归宿或接受者。,14,1.2.1 模拟信息传输系统,变换器：将非电量变换成宜于远距离传输的电信号。反变换器：将信息信号恢复成原消息。,15,1.2.1 模拟信息传输系统,调制器：将频率较低的信号调制到频率更高的载波信号上。(调制方式有调幅AM、调频FM、调相、单边带调制SSB等)。,解调器：从已调的高频载波信号中解调出被传输的低频信息信号。,16,1.2.1 模拟信息传输系统,发射机：变频器和功率放大器，使已调载波信号的频率和功率达到实际应用所要求的数值。,接收机：低噪声高频放大器、混频器、中频放大器，将微弱信号放大到解调器所需强度的信号，并最大限度地降低信道噪声的影响。,17,1.2.1 模拟信息传输系统,信道：消息的信号从发射端传到接受端的媒质或通道。（有线信道：架空明线、同轴电缆、波导、光纤等；无线信道：无线电波、激光自由空间传播等）,噪声源：实际传输系统中客观存在的干扰源，有内部噪声和外部干扰两方面。,18,1.2.2 数字信息传输系统,该系统中传输的是数字信号，它只能取有限个离散值，且出现的时间也是离散的。基本模型如图1.2 所示：,19,1.2.2 数字信息传输系统,调制方式有幅度键控ASK、频移键控FSK、相移键控PSK等。,信源编码器：模/数（A/D）变换器，将模拟信号变换成数字信号。信源译码器：数/模（D/A）变换器，将数字信号变换成模拟信号。信道编译码器：提高传输系统的抗干扰能力。,20,1.2.2 数字信息传输系统,优点：（1）抗干扰能力强，特别在中继传输中尤为明显。（2）可以进行差错控制，提高了信息传输的灵活性。,（3）便于使用现代计算机技术对信号进行处理、存储和变换。（4）便于加密，实现保密信息传输。,21,1.2.2 数字信息传输系统,（5）易于与其他系统配合使用，构成综合业务信息传输网。（6）易于集成化和大规模生产，性能一致性好且成本低。,缺点：（1）占用信道频带较宽。（2）要有一个复杂的同步系统。,22,1.3 信息论研究对象和内容,研究对象：消息传输系统即信息传输系统，通信系统。,研究目的：提高通信系统的可靠性和有效性。（1）可靠性高：使信源发出的消息经过传输后尽可能准确地不失真地再现在接收端。（2）有效性高：经济效果好，用尽可能短的时间和尽可能少的设备传送一定数量的信息。,23,1.3 信息论研究对象和内容,研究内容：（1）通信的统计理论的研究。（2）信源的统计特性的研究。（3）收信者接受器官的研究。,（4）编码理论与技术。（5）如何提高信息传输效率。（6）抗干扰理论与技术。（7）噪声中信号检测理论与技术。,24,1.3 信息论研究对象和内容,信息论的三个层次：（1）信息论基础（狭义信息论）：主要研究信息的测度、信道容量、信源和信道编码理论等问题。,（2）一般信息论：主要研究信息传输和处理问题，除香农理论外，还包括噪声理论、信号滤波和预测、统计检测与估计理论、调制理论以及信息处理理论等。,（3）广义信息论：不仅包括上述两方面内容，还包括与信息有关的领域，如心理学、遗传学、神经生理学、语言学、语义学等。,25,1.4 信息论发展简史,电信系统的发展：电磁理论和电子学理论的发展促进了电信系统的创造发明或改进。1823年-1835年，莫尔斯建立了电报系统。1876年，贝尔发明了电话系统。,1895年，马可尼和波波夫发明了无线电通信。1925年-1927年，建立起电视系统。二次大战初期，微波通信系统和微波雷达系统迅速发展起来。20世纪60年代，人类进入光纤通信时代。,26,1.4 信息论发展简史,信息理论的发展：1924年，奈奎斯特首先将信息率与信号带宽联系起来。1928年，哈特莱引入了非统计（等概率事件）信息量概念。,20世纪40年代初期，维纳把随机过程和数理统计的观点引入通信和控制系统中。1948、1949年，香农用概率测度和数理统计的方法，系统地讨论了通信的基本问题。,27,1.4 信息论发展简史,无失真信源编码的发展：（香农编码理论）惟一可译码费诺码哈夫曼码（最佳码）算术编码LZ码（通用信源编码）。,信道编码的发展：纠错码汉明码（代数编码）卷积码（概率编码）并行极点卷积码。,28,2 信息的量度,2.1 自信息量和条件自信息量2.2 互信息量和条件互信息量2.3 离散集的平均自信息量2.4 离散集的平均互信息量2.5 例题,29,2.1 自信息量和条件自信息量,2.1.1 自信息量2.1.2 条件自信息量,30,2.1.1 自信息量,信源发出的消息常常是随机的，其状态存在某种程度的不确定性，经过通信将信息传给了收信者，收信者得到消息后，才消除了不确定性并获得了信息。,获得信息量的多少与信源的不确定性的消除有关。不确定度惊讶度信息量,31,2.1.1 自信息量,（1）直观定义信息量为：收到某消息获得的信息量=不确定性减少的量=收到此消息前关于某事件发生的不确定性-收到此消息后关于某事件发生的不确定性,（2）无噪声时信息量为：收到消息前获得的信息量=收到此消息前关于某事件发生的不确定性=信源输出的某消息中所含有的信息量,32,2.1.1 自信息量,举例说明，一个布袋中装有对人手感觉完全一样的球，但颜色和数量不同，问下面三种情况下随意拿出一个球的不确定程度的大小。（1）99个红球和1个白球（2）50个红球和50个白球（3）红球、白球、黑球、黄球各25个,33,2.1.1 自信息量,事件发生的不确定性与事件发生的概率有关，一般情况下，一个信源可以用一个概率空间来描述，信源的不确定程度可以用这个概率空间的可能状态数目及其概率来描述。,34,2.1.1 自信息量,设信源X的概率空间为其中：X是信源的状态空间，即随机事件的状态数；是随机事件可能状态的概率分布，且，各状态是相互独立的。通常记为,35,2.1.1 自信息量,应用概率空间的概念分析上例，设取红球的状态为x1，白球为x2，黑球为x3，黄球为x4，则概率空间为：（1）（2）（3）,36,2.1.1 自信息量,结论：（1）不确定度与信源概率空间的状态数及其概率分布有关。,（2）信源概率空间的概率分布为等概率时不确定度最大。,（3）等概率时，不确定度与信源概率空间的状态数或相应的概率有关。,37,2.1.1 自信息量,任意随机事件的自信息量定义为该事件发生概率的对数的负值。若随机事件 出现的概率为，那么它的自信息量为通常取对数的底为2，单位为比特（bit）。,38,2.1.1 自信息量,三个单位间的转换关系为：1奈特=log2e 1.433比特1哈特莱=log210 3.332比特自信息量非负且单调递减。,39,2.1.1 自信息量,例：某地的天气情况分布是：晴天占1/2，阴天占1/4，雨天占1/8，雪天占1/8。求各种天气的自信息量。解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4,40,2.1.1 自信息量,在二维联合集 上的元素 的联合自信息量定义为其中，为元素 的二维联合概率。当二者相互独立时，则有。元素 的不确定度在数值上也等于他们的自信息量。,41,2.1.1 自信息量,例2.1.1 在盒子中放入n个不同阻值的电阻，随机取出一个并猜测阻值，概率空间为其中xi代表阻值为 表示取出电阻值为i 的电阻的概率。假定取出电阻是等概率的，即 那么被告知取出阻值为i的电阻，所获得的信息量为,42,2.1.1 自信息量,若盒中放入 个不同阻值的电阻，其中阻值为1欧姆的1个，2欧姆的2个，n欧姆的n个。概率空间为其中xi代表阻值为 表示取出电阻值为i 的电阻的概率。那么被告知取出阻值为i的电阻，所获得的信息量为,43,2.1.2 条件自信息量,在联合集 对事件，设在条件 下，随机事件 的条件概率为，那么其条件自信息量定义为三种自信息量的关系：,44,2.1.2 条件自信息量,例2.1.2 设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随机地放在棋盘中某方格内让乙猜。（1）将方格按顺序编号，猜测顺序号；（2）将方格按行和列编号并告知行或列编号，猜测位置。,45,2.1.2 条件自信息量,解：由于棋子位置是二维等概率分布，故（1）在二维联合集 上的元素 的自信息量为（2）在二维联合集 上，元素 相对 的条件自信息量为,46,2.2 互信息量和条件互信息量,2.2.1 互信息量2.2.2 互信息量的性质2.2.3 条件互信息量,47,2.2.1 互信息量,（1）通常预先知道信源集合X的概率空间，即其中 为集合X中各个消息的取值，概率 称为先验概率。,48,2.2.1 互信息量,（2）信宿收到的消息符号集合Y的概率空间为其中 为集合Y中各个消息的取值。当信宿收到集合Y中的一个符号消息后，接收者重新估计关于信源各个消息Xi发生的概率就成为条件概率 也称为后验概率。,49,2.2.1 互信息量,对两个离散随机事件X和Y，事件 的出现给出关于事件 的信息量定义为互信息量，即,互信息量定义为后验概率与先验概率比值的对数，也等于自信息量减去条件自信息量。当对数底分别为2、e、10时，互信息量的单位分别为比特、奈特、哈特莱。,50,2.2.1 互信息量,例2.2.1：当告知不是晴天时，某地的天气情况分布是阴天占1/2，雨天占1/4，雪天占1/4。求不是晴天时，获得的各种天气的互信息量。解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4。不是晴天的状态为y1,51,2.2.1 互信息量,此时，各种天气的条件自信息量：,52,2.2.2 互信息量的性质,（1）互信息量的互易性对称性证：,53,2.2.2 互信息量的性质,（2）当事件xi和yj相互独立时，互信息量为零。证：由 得,54,2.2.2 互信息量的性质,（3）互信息量可正可负,当后验概率 大于先验概率 时，互信息量为正值，反之为负值。互信息量为正意味着事件 的出现有助于肯定事件 的出现，反之是不利的。,55,2.2.2 互信息量的性质,（4）任何两个事件的互信息量不可能大于其中任一事件的自信息量。证：由于故,56,2.2.2 互信息量的性质,例2.2.2 某人A预先知道他的三个朋友B、C、D中有一人晚上到他家，且这三人来的可能性相同，先验概率 P(B)=P(C)=P(D)=1/3。,但上午A接到D的电话说不能来了，将这次电话作为事件E，那么有后验概率P(D|E)=0,P(B|E)=P(C|E)=1/2。,下午又接到C的电话说不能来，将此作为事件F，则有P(C|EF)=P(D|EF)=0,P(B|EF)=1。,57,2.2.2 互信息量的性质,在接到上午电话后，A获得关于B、C、D的互信息量为因为P(D|E)=0,故无需考虑事件D与事件E间的互信息量。在接到两次电话后，A获得关于B、C、D的互信息量为因为P(C|EF)=P(D|EF)=0,故无需考虑事件D与事件E间的互信息量。,58,2.2.3 条件互信息量,在联合集,在给定 的条件下，之间的互信息量。在联合集,还存在 与 之间的互信息量。,59,2.3 离散集的平均信息量,2.3.1 平均自信息量（熵）2.3.2 熵函数的数学特性2.3.3 条件熵2.3.4 联合熵（共熵）2.3.5 各种熵的性质2.3.6 加权熵,60,2.3.1 平均自信息量（熵）,自信息量是一个随机变量，不能作为整个信源的信息测度，故引入平均自信息量，即信息熵。,信息熵H(X)是从整个信源的统计特性来考虑的，是从平均意义上表征信源的总体特性。对某特定的信源，其信息熵只有一个。,定义集X上，随机变量自信息I(xi)的数学期望为平均自信息量H(X)即信息熵，简称熵。,61,2.3.1 平均自信息量（熵）,例2.3.1 有一个布袋内放100个球，其中80个红球，20个白球。随便摸一个球猜测是什么颜色，求平均摸取一次获得的信息量。解：设事件x1表示摸到红球，事件x2表示摸到白球，则概率空间为,62,2.3.1 平均自信息量（熵）,当告知摸出的是红球时，获得的信息量当告知摸出的是白球时，获得的信息量,若每次摸出一个球后又放回去，进行第二次摸取，那么摸取n次中，红球出现的次数为nP(x1)，白球出现的次数为nP(x2)。则摸取n次后获得的信息量为,63,2.3.1 平均自信息量（熵）,平均随机摸取一次所能获得的信息量为,64,2.3.1 平均自信息量（熵）,信息熵分别为可见 H(Y)H(X),例2.3.2 比较两个信源,65,2.3.1 平均自信息量（熵）,信息熵的三种物理含义：（1）表示信源输出后每个消息所提供的平均信息量。（2）表示信源输出前信源的平均不确定性。（3）表征变量的随机性。,66,2.3.2 熵函数的数学特性,因为随机变量集的熵H(X)只是其概率分布的函数，所以熵函数H(X)又可记为,由于概率的完备性，H(P)实际上是(q-1)元函数。如二元熵 H(P)=Hp,(1-p)=H(p)。,67,2.3.2 熵函数的数学特性,设 为一多元函数，若对于任意小于1的正数 以及函数定义域内的任意两个矢量X1和X2有则称f(X)为定义域上的上凸函数。,68,2.3.2 熵函数的数学特性,（1）对称性当概率矢量中的各个分量的次序任意互换时，熵函数的值不变，即例如两个信源信息熵为,69,2.3.2 熵函数的数学特性,（2）非负性（离散信源）等号成立的充要条件是当且仅当某Pi=1,其余的 Pk=0。这表明确定信源的熵最小。证：,当每一项为零时等号成立，由于，故只能有某一个Pi=1,其余的Pk=0,70,2.3.2 熵函数的数学特性,（3）扩展性证：因为,说明信源的取值数增多时，若这些取值对应的概率很小（接近于零），则信源的熵不变。,71,2.3.2 熵函数的数学特性,（4）可加性如果有两个随机变量X和Y，他们不是相互独立的，则二维随机变量的熵H(XY)等于X的无条件熵H(X)加上当X已给定时Y的条件概率定义的熵的统计平均值H(Y|X)。H(XY)=H(X)+H(Y|X)H(XY)=H(Y)+H(X|Y),72,2.3.2 熵函数的数学特性,（5）极值性式中，n是集合X的元素数目。上式表明，在离散情况下，集合X中的各事件依等概率发生时，熵达到极大值，即最大熵定理。,73,2.3.2 熵函数的数学特性,（6）确定性从总体看，信源虽然有不同的输出符号，但当它只有一个符号几乎必然出现，而其他符号都是几乎不可能出现时，那么这个信源是一个确知信源，其熵等于零。（7）上凸性,74,2.3.3 条件熵,条件熵是在联合符号集XY上的条件自信息量的联合概率加权统计平均值。,条件熵H(X|Y)表示收到全部输出符号后，对信道输出符号集还存在的平均不确定性，称为信道疑义度。,条件熵H(Y|X)可以衡量信号通过信道后损失信息量的多少。,75,2.3.4 联合熵（共熵）,联合熵是在符号集XY上的每个元素对xiyj的自信息量的概率加权统计平均值，其定义式为,76,2.3.5 各种熵的性质,（1）联合熵与信源熵、条件熵的关系若集X和集Y相互独立则有表示熵的可加性。称为熵的强可加性。,77,2.3.5 各种熵的性质,推广到多个随机变量构成的概率空间之间的关系。设有N个变量，其联合熵可表示为若N个变量相互独立，则有,78,2.3.5 各种熵的性质,（2）联合熵与信源熵的关系当且仅当两个集合相互独立时，上式取等号，此时可得联合熵的最大值，即,此性质同样可推广到N个变量构成的概率空间等号成立的充要条件是概率空间相互独立。,79,2.3.5 各种熵的性质,（3）信源熵与条件熵的关系当且仅当两个集合相互独立时，上式取等号。,80,2.3.5 各种熵的性质,例2.3.3 输入输出的联合分布如下表,81,2.3.5 各种熵的性质,例2.3.4 P(x),P(y|x),P(xy)如下表,82,2.3.5 各种熵的性质,例2.3.5,83,2.3.6 加权熵,设有随机变量X，引入事件的重量后，其概率空间为其中离散无记忆信源X P W的加权熵定义为,84,2.3.6 加权熵,重要性质：,85,2.4 离散集的平均互信息量,2.4.1 平均条件互信息量2.4.2 平均互信息量2.4.3平均互信息量的性质,86,2.4 离散集的平均互信息量,以X P表示输入概率空间,87,2.4 离散集的平均互信息量,以Y P表示输出概率空间,88,2.4 离散集的平均互信息量,X和Y的联合空间,89,2.4 离散集的平均互信息量,以XY p(xy)表示联合概率空间，一般有当事件xi和yj相互独立时有若上式对所有的i,j成立，则称集X与Y统计独立，否则称为统计相关。,90,2.4.1 平均条件互信息量,在联合集XY上，由yj提供的关于集X的平均条件互信息量等于由yj提供的互信息量在整个X中的后验概率加权的平均值，其定义式为,联合集XY上的平均条件互信息量有当且仅当集X中的各个xi都与事件yj相互独立时取等号。,91,2.4.2 平均互信息量,互信息量在整个集上的概率加权平均值，称为平均互信息量,当事件xi与yj相互独立时,92,2.4.3 平均互信息量的性质,（1）非负性：当且仅当事件xi与yj相互独立时取等号。,（2）对称性,93,2.4.3 平均互信息量的性质,（3）平均互信息与各类熵的关系用维拉图表示为,94,2.4.3 平均互信息量的性质,（4）极值性,（5）凸函数性平均互信息量是信源概率分布p(x)和信道传递概率p(x|y)的凸函数。,95,3 无失真信源与信息熵,3.1 信源的数学模型及其分类3.2 离散无记忆信源3.3 离散无记忆信源的扩展信源3.4 离散平稳信源3.5 马尔可夫信源3.6 信源的相关性和剩余度,96,3.1 信源的数学模型及其分类,3.1.1 信源的数学模型3.1.2 信源的分类,97,3.1.1 信源的数学模型,(1)离散信源信源输出的是单个符号或代码的消息，信源符号集的取值是有限的或可数的，可以用一维离散型随机变量来描述，其数学模型是,98,3.1.1 信源的数学模型,(2)连续信源信源输出的是单个符号或代码的消息，信源符号集的取值是连续的，可以用一维连续型随机变量来描述，其数学模型是其中p(x)为连续随机变量X的概率密度函数，(a,b)为X的存在域。,99,3.1.1 信源的数学模型,若N维随机矢量 中信源的N重概率空间为,这个空间共有元素qN个，取决于序列长度N和符号集的符号个数q。,100,3.1.2 信源的分类,（1）按照消息取值集合以及取值时刻集合的离散性和连续性，信源可分为数字信源和模拟信源（波形信源）。,（2）按照某取值时刻消息的取值集合的离散性和连续性，信源可分为离散信源和连续信源。,101,3.1.2 信源的分类,（3）按照信源输出消息所对应的随机序列的平稳性，信源可分为平稳信源和非平稳信源。,（4）按照信源输出的信息所对应的随机序列中随机变量前后之间有无统计依赖关系，信源可分为无记忆信源和有记忆信源。,102,3.1.2 信源的分类,在某些简单情况下，信源发出的一个个符号是彼此统计独立的，并且它们具有相同的概率分布，则N维随机矢量的概率分布满足其中，这种信源称为离散无记忆信源。,103,3.1.2 信源的分类,在通常情况下，信源发出的符号是彼此依赖的，要引入条件概率分布来说明它们间的关联，这种信源称为有记忆信源。,有记忆信源可用有限状态马尔可夫链来描述。当信源记忆长度为m+1时，称为m阶马尔可夫信源，即信源每次发出的符号只与前m个有关,与更前面的符号无关。,104,3.2 离散无记忆信源,在信源X中，事件xi发生的概率为p(xi)，则xi所含的自信息量定义为 I(xi)=-logp(xi),信源输出各消息的自信息I(xi)的数学期望为信源的平均自信息量H(X)即信源的信息熵。,105,3.3 离散无记忆信源的扩展信源,3.3.1 最简单的离散信源3.3.2 N次扩展信源3.3.3 N次扩展信源的熵,106,3.3.1 最简单的离散信源,最简单的离散信源的输出可用一维离散随机变量描述。对于二进制信源，其数学模型为,107,3.3.2 N次扩展信源,（1）离散无记忆二进制信源X的二次扩展信源每两个二进制数字组成一组，新的等效信源的输出符号为x1=00，x2=01，x3=10，x4=11。二次扩展信源的数学模型为其中,108,3.3.2 N次扩展信源,（2）离散无记忆二进制信源X的三次扩展信源每三个二进制数字组成一组，新的等效信源的输出符号为x1=000，x2=001，x3=100，x8=111。三次扩展信源的数学模型为其中,109,3.3.2 N次扩展信源,以此类推，由N个二进制数字为一组构成的新信源共有2N个符号，每个符号长度为N，称为二进制信源的N次扩展信源。,110,3.3.2 N次扩展信源,（3）离散无记忆信源的N次扩展设一个离散无记忆信源X的概率空间为,q为信源的符号个数，则信源X的N次扩展信源用XN表示，它是具有qN个符号的离散信源，其N重概率空间为,111,3.3.3 N次扩展信源的熵,根据信息熵的定义，离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵的N倍，即 H(XN)=NH(X)证明：见教材47页,112,3.3.3 N次扩展信源的熵,例3.3.1（见教材48页）,113,3.4 离散平稳信源,3.4.1 定义3.4.2 N长信源序列的熵,114,3.4.1 定义,定义：信源产生的随机序列 满足：1）所有 都取值于有限的信源符号集；2）随机序列是平稳的，即对所有的非负整数 有,115,3.4.1 定义,一维平稳信源：任意两个不同时刻信源发出符号的概率分布完全相同，即其中，i,j为任意整数,116,3.4.1 定义,二维平稳信源：除上述条件外，如果联合概率分布p(x1x2)也与时间起点无关，即其中，i,j为任意整数,117,3.4.1 定义,完全平稳信源：如果各维联合概率分布均与时间起点无关，即当t=i,t=j,(i,j为任意整数且不相等）时有,118,3.4.2 N长信源序列的熵,平稳有记忆信源发出符号序列为，假设信源符号间的依赖长度为N，则联合概率为,119,3.4.2 N长信源序列的熵,120,3.4.2 N长信源序列的熵,例：设有一信源，产生0,1序列的消息，且在任意时间，不论前面发生过什么符号，均按P(0)=0.4,P(1)=0.6的概率发出符号。（1）试问这个信源是否是平稳的。（2）计算（3）计算H(X4)并写出X4信源中可能有的所有符号。,121,3.4.2 N长信源序列的熵,解：（1）依题意，信源发出符号的概率分布与时间平移无关，且信源发出的序列之间也是彼此无依赖的，故此信源是平稳信源，而且是离散无记忆信源。,122,3.4.2 N长信源序列的熵,（2）信源概率空间为可计算得因为信源是平稳无记忆信源，所以,123,3.4.2 N长信源序列的熵,（3）X4信源中可能有的符号有16种,124,3.4.2 N长信源序列的熵,对于离散、平稳、有记忆信源，当 时，下列结论成立：（1）条件熵 随N的增加是非递增的（即N的单调非增函数）；（2）（4）,（3）HN(X)是随N的增加是非递增的（即N的单调非增函数）；,125,3.5 马尔可夫信源,3.5.1 有限状态马尔可夫链3.5.2 马尔可夫信源,126,3.5.1 有限状态马尔可夫链,设 为一随机序列，时间参数集，其状态空间，若对所有的，有则称 为马尔可夫链。,127,3.5.1 有限状态马尔可夫链,转移概率性质：,128,3.5.1 有限状态马尔可夫链,当n-m=1时，即pij(m,m+1)的情况下，将其记为pij(m)，称为基本转移概率或一步转移概率。定义k步转移概率规定零步转移概率,129,3.5.1 有限状态马尔可夫链,由于系统在任一时刻可处于状态空间中任一状态，故转移概率是一个矩阵，也是一个随机矩阵。,一般情况下，状态空间 是一个可数无穷集合，故转移矩阵是一个无穷列的随机矩阵。,130,3.5.1 有限状态马尔可夫链,如果在马尔可夫链中即从状态i转移到状态j的概率与m无关，则称这类马尔可夫链为时齐马尔可夫链或齐次马尔可夫链，也称为具有平稳转移概率的马尔可夫链。,如果状态空间 是无穷集合，则称为可数无穷状态的马尔可夫链。,如果状态空间 是有限的，则称为有限状态的马尔可夫链。,131,3.5.1 有限状态马尔可夫链,对于具有m+r步转移概率的时齐马尔可夫链，存在切-柯方程利用该式就可以用一步转移概率表达多步转移概率。但是转移概率不包含初始分布。,132,3.5.1 有限状态马尔可夫链,若齐次马尔可夫链对一切i,j存在不依赖于i的极限则称其具有遍历性，pj称为平稳分布，也是该马尔可夫链的初始分布。,133,3.5.1 有限状态马尔可夫链,成为遍历马尔可夫链的充分条件是具有不可约性和非周期性。,134,3.5.1 有限状态马尔可夫链,不可约性指对于任意一对i和j，都存在至少一个k，使pij(k)0，即从si开始总可能到达sj。,135,3.5.1 有限状态马尔可夫链,非周期性指所有pii(n)0的n中没有比1大的公因子。,136,3.5.1 有限状态马尔可夫链,对于一个有r个状态的马尔可夫链，若令,137,3.5.1 有限状态马尔可夫链,138,3.5.1 有限状态马尔可夫链,对于有限状态马尔可夫链，如果存在一个数集，且满足则称该马尔可夫链的稳态分布存在，并有如下性质：（1）完备性,（2）不变性 WP=W,若W(0)=W 则W(n)=W（3）惟一性,139,3.5.2 马尔可夫信源,马尔可夫信源:信源输出的符号序列和状态序列满足以下条件：（1）某一时刻信源符号的输出只与当时的信源状态有关，而与以前的状态无关，即,（2）信源状态只由当前输出符号和前一时刻信源的状态惟一确定，即,140,3.5.2 马尔可夫信源,例3.5.1 有一个二进制一阶马尔可夫信源X，其信源符号集为0,1，条件概率为p(0|0)=0.25,p(1|0)=0.75,p(0|1)=0.50,p(1|1)=0.50。求各状态的稳态概率分布W1,W2。解：信源有两个状态S1=0,S2=1。状态转移矩阵,141,3.5.2 马尔可夫信源,根据稳态分布的性质（1）和（2）可得：,142,3.5.2 马尔可夫信源,由于状态转移概率完全依赖于给定的条件概率，故对一般的m阶马尔可夫信源通过引入状态转移概率而转化为马尔可夫链。,其中，状态转移概率 由信源符号条件概率 确定且。,143,3.5.2 马尔可夫信源,当时间足够长后，遍历的m阶马尔可夫信源可视为平稳信源来处理。又因为信源发出的符号只与最近的m个符号有关，所以,144,3.5.2 马尔可夫信源,对于时齐、遍历的马尔可夫链，其状态Sj由 惟一确定，因此有,145,3.5.2 马尔可夫信源,146,3.5.2 马尔可夫信源,例3.5.2 有一个二进制二阶马尔可夫信源X，其信源符号集为0,1，条件概率为p(0|00)=p(1|11)=0.8,p(1|00)=p(0|11)=0.2,p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5。（1）求各状态的稳态概率分布W1,W2,W3,W4（2）求稳定后各符号的概率分布p(0)，p(1)（3）求信源熵。,147,3.5.2 马尔可夫信源,解：信源有四个状态S1=00,S2=01,S3=10,S4=11。符号条件概率矩阵为,148,3.5.2 马尔可夫信源,（1）根据稳态分布的性质（1）和（2）可得：,149,3.5.2 马尔可夫信源,（2）稳定后各符号的概率分布,150,3.5.2 马尔可夫信源,（3）信源熵,151,3.6 信源的相关性和剩余度,由于信源符号间的依赖关系使信源的熵减小，就是信源的相关性。如果信源输出符号间的相关性越长，则信源熵减小，趋于极限熵。,若相关程度减小，信源实际熵增大。只有当信源符号彼此间无依赖、等概率分布时，信源的熵最大为H0。,152,3.6 信源的相关性和剩余度,一个信源输出的符号前后有相关性时，信源输出的熵将减少，输出的总信息量也下降，这就是一种形式的剩余或多余。输出同样的信息量有剩余的信源输出的符号数要比无剩余的信源多。信源剩余度定义为,其中，为信源实际熵；H0=Hmax为信源最大熵，当信源输出符号集有q个元素且为等概分布时H0=Hmax=logq；称为相对率。,153,3.6 信源的相关性和剩余度,信源最大可能熵与实际熵的差值定义为内熵。相对率、剩余度、内熵均可用来表示信源的剩余情况。信源的剩余度表示信源的可压缩程度。,从提高信息传输效率的观点出发，总是希望减少或去掉剩余度（信源编码）。从提高抗干扰能力的角度出发，总是希望增加或保留剩余度（信道编码）。,154,3.6 信源的相关性和剩余度,例：黑白气象传真图的消息只有黑色和白色两种，黑色出现的概率为P(黑)=0.3，白色出现的概率为P(白)=0.7。（1）假设图上黑白消息出现前后没有关联，求熵H(X)。（2）假设消息前后有关联，其依赖关系为P(白|白)=0.9，P(黑|白)=0.1，P(白|黑)=0.2，P(黑|黑)=0.8，求熵H2。（3）分别求上述两种信源的剩余度，并比较H(X)和H2的大小，说明其物理意义。,155,3.6 信源的相关性和剩余度,解：设状态x1=黑，x2=白（1）假设图上黑白消息出现前后没有关联，则等效为一个离散无记忆信源，概率空间为信息熵,156,3.6 信源的相关性和剩余度,（2）假设消息前后有关联时，从其依赖关系看出其满足一阶马尔可夫信源的定义，状态空间为状态转移矩阵,157,3.6 信源的相关性和剩余度,由图可知，此马尔可夫链满足不可约性和非周期性，其稳态分布存在，分别设为P(S1)=W1，P(S2)=W2,158,3.6 信源的相关性和剩余度,信息熵,159,3.6 信源的相关性和剩余度,（3）两种信源的剩余度,结果说明，当信源的消息符号之间有依赖时，信源输出消息的不确定性减弱。信源剩余度反映了消息符号间依赖关系的强弱，剩余度越大，符号间的依赖关系越大。,160,4 信道及其容量,4.1 信道的分类与描述4.2 离散无记忆信道4.3 离散无记忆的扩展信道4.4 信道的组合4.5 信道容量4.6 信源与信道的匹配,161,4.1 信道的分类与描述,信道是所传信息的载体（消息）的具体形式（信号）所要通过的通道或媒介。信息是抽象的但信道是具体的。,在信息系统中，信道的主要作用是传输与存储信息，而在通信系统中则主要是传输信息，对其研究的主要目的是为了描述、度量、分析不同类型信道，计算其容量。,162,4.1 信道的分类与描述,（一）信道的分类（1）按传输媒介的类型划分,163,4.1 信道的分类与描述,（2）按决定信道的信号与干扰的类型与描述划分,164,4.1 信道的分类与描述,（3）按信道的物理性质（信道的统计特性）划分,165,4.1 信道的分类与描述,（4）按用户类型划分（5）按信道的记忆特性划分,166,4.1 信道的分类与描述,（二）信道描述三要素：（1）信道输入统计概率空间：X,p(X)（2）信道输出统计概率空间：Y,p(Y)（3）信道本身的统计特性，即转移概率矩阵：p(y|x)由此构成对信道整体的描述为：X,p(X),p(y|x),Y,p(Y)简记为：X,p(y|x),Y,167,4.1 信道的分类与描述,对离散序列信源可以描述为：其中：信道转移概率为,168,4.2 离散无记忆信道,（一）离散信道的数学模型,169,4.2 离散无记忆信道,170,4.2 离散无记忆信道,根据信道的统计特性不同，离散信道又可分为三种情况：（1）无干扰信道。输入与输出之间有确定的一一对应关系，即y=f(x)，（2）有干扰无记忆信道。（3）有干扰有记忆信道。,171,4.2 离散无记忆信道,（二）单符号离散信道,172,4.2 离散无记忆信道,（1）二进制对称信道（二元对称信道BSC信道）输入符号集A=0,1;输出符号集B=0,1;传递概率为,173,4.2 离散无记忆信道,且传递概率满足：传递矩阵为,174,4.2 离散无记忆信道,（2）二进制删除信道输入符号集A=0,1;输出符号集B=0,？,1传递矩阵为且有,175,4.2 离散无记忆信道,提示：在离散信道中，一般概率关系有：（1）若输入符号的概率已知，则输入和输出符号的联合概率而且,其中p(bj|ai)是信道传递概率，称为前向概率，p(ai|bj)称为后向概率，也是输入符号的后验概率，p(ai)是输入符号的先验概率。,176,4.2 离散无记忆信道,（2）根据联合概率可得出输出符号的概率或P为信道矩阵。,177,4.2 离散无记忆信道,（3）根据贝叶斯定律可得后验概率,178,4.2 离散无记忆信道,（三）