信息论与编码(姜丹)2章

信息论与编码张祖平/ZhangZuping电子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,[e-mail]&Coding2014秋季信息12InfTheory&Coding-张祖平本章主要内容(MainContent)信道的数学模型信道的交互信息量条件交互信息量平均交互信息量及其特性信道容量及其一般算法特征信道容量的计算2014秋季信息12InfTheory&Coding-张祖平信道的数学模型2014秋季信息12InfTheory&Coding-张祖平•什么是信道–通信的过程：信源发出消息，以适合信道传输的信号的形式，通过信道的传输，被信宿接收，从而获取信息。–什么是信道：信道是信息传输的通道，承担信息的传输与存储的任务，是通信系统的重要组成部分。•信息是抽象的，信道则是具体的。•比如：二人对话，二人间的空气就是信道；打电话，电话线就是信道；看电视，听收音机，收、发间的空间就是信道。–信道的作用：信道是信息传输的通道，承担信息的传输与存储的任务，是通信系统的重要组成部分。信道的数学模型信源信道信宿42014秋季信息12InfTheory&Coding-张祖平•信道的分类信道的数学模型51明线对称平衡电缆（市内）固体介质电缆小同轴（长途）中同轴（长途）长波中波短波超短波移动传输媒介类型空气介质视距接力微波对流层散射电离层卫星光波波导混合介质光缆2离散连续无记忆信号类型半离散有记忆半连续波形无干扰：干扰少到可忽略；〉信号与干扰类型无源热噪声线性叠加干扰有源散弹噪声脉冲噪声干扰类型有干扰交调乘性干扰衰落码间干扰2014秋季信息12InfTheory&Coding-张祖平•信道的分类信道的数学模型6变参信道（时变信道））恒参信道（时不变信道〉信道参量类型3多用户信道（通信网）信）二用户信道（点对点通〉用户类型4离散信道：输入、输出信号在时间和幅度上均离散；连续信道：信号的幅度是连续的，时间是离散的；半离散半连续信道：输入和输出中有一个是离散的，另一个是连续的；波形信道：输入和输出信号在时间上和幅度上均连续，一般可用随机过程来描述。而且一般经过抽样处理，分解为前三种情况。2014秋季信息12InfTheory&Coding-张祖平•单符号离散信道的数学模型–输入随机变量X，可以输入r种不同的离散符号，取值于{a1,a2,…,ar}–输出随机变量Y，相应输出s种不同的离散符号，取值于{b1,b2,…,bs}–由于信道中的噪声干扰，符号集X和Y可以完全相同，部分相同，完全不同，r和s可以相等也可以不相等–输入a1可能在输出端得到b1~bs的任意一种结果，那么设输入a1在输出端得到b1的概率，用条件概率：P（b1/a1）来表示。信道的数学模型712,,,rxXaaa输入符号集：12{,,,}syYbbb输出符号集：2014秋季信息12InfTheory&Coding-张祖平•单符号离散信道的数学模型–定义：假设信道输入随机变量为X，其取值为x；输出随机变量为Y，取值为y。可以用条件概率来表示输入与输出的关系，这组条件概率称为信道的传递概率或转移概率，可以用来描述信道干扰影响的大小或者说表示信道的传输特性。一般简单的单符号离散信道的数学模型用[X,P(y/x),Y]三者描述。信道的数学模型8(|)(|)(|)jijipyxPYbXaPba1,2,,1,2,,irjs；a1b1a2b2X..Y..arbsP(bj/ai)2014秋季信息12InfTheory&Coding-张祖平•单符号离散信道的数学模型–通常信道传递概率可以用传递概率矩阵表示，称为信道矩阵[P]，是一个(r×s)阶的矩阵。–信道矩阵可作为离散单符号信道的另一种数学模型的形式。信道的数学模型9sjijijpp110rsrrsspppppppppP...::::......212222111211b1b2…bsa1P(b1|a1)P(b2|a1)…P(bs|a1)a2P(b1|a2)P(b2|a2)…P(bs|a2)…….……arP(b1|ar)P(b2|ar)…P(bs|ar)2014秋季信息12InfTheory&Coding-张祖平练习10二元对称信道（BSC：BinarySymmetricChannel），给定一个单符号离散信道，如下图，输入符号集和输出符号集分别为A={0，1}和B={0，1}，用概率p表示单个符号传输中发生错误的概率，1-p表示单个符号无错误传递的概率。写出它的信道矩阵？pppppppp11P1-p1-pppXa1=00a2=11=b2Y0=b1p)|p()|ap(bp)|p()|ap(bpp)|p()|ap(bpp)|p()|ap(b0110111100122122112014秋季信息12InfTheory&Coding-张祖平练习11二元删除信道（BEC－BinaryEliminateChannel），给定一个单符号离散信道，如下图，输入符号X取值于｛0，1｝；输出符号取值于｛0，？，1｝,用概率p表示单个符号传输中发生错误的概率，1-p表示单个符号无错误传递的概率。写出它的信道矩阵？01011-p1-ppp？0)1/0()0/0(pppppppp)1(?/1)0(?/pppp1)1/1(0)0/1(ppppP001?010][2014秋季信息12InfTheory&Coding-张祖平信道的交互信息量2014秋季信息12InfTheory&Coding-张祖平•输入符号ai，输出符号bj的联合概率的表示信道的交互信息量13(,)()1,2,,1,2,,ijijPXaYbpabirjs()()()ijijipabpapb|a也就是说当知道信源空间[X·P]和信道的信道矩阵[P],就可以计算出输入和输出符号的（r*s）个联合概率，得到分布矩阵根据条件概率公式得到：2014秋季信息12InfTheory&Coding-张祖平•输出符号bj的概率的表示–输出某个符号bj的概率，被分解成了许多部分之和–请参考概率论中的全概率公式信道的交互信息量141,2,,1,2,,irjs11()()(|)()rrjijjiiiipbpabpbapa2014秋季信息12InfTheory&Coding-张祖平•输出符号bj后，推测输入是ai的后验概率的表示–对任意输出bj，r个后验概率构成一个完备的概率空间–参考概率论中的贝叶斯公式。信道的交互信息量151,2,,1,2,,irjs1()()(|)()()(|)()ijijiijrjjiiipabpapbapa|bpbpbapa1()11,2...rijipa|bjs当信道输出符号bj，接受者接收到了bj，信源空间是已知的，那么收到了bj的情况下，先验概率p(ai)就转变为了后验概率p(ai/bj)，这种概率转换，正表达了人们对ai原有的不确定性p(ai)，在收到bj后，人们对ai的不确定性变化了，那变化了多少呢？？2014秋季信息12InfTheory&Coding-张祖平•交互信息量的表达形式一信道的交互信息量16的不确定性的消除前后对收到仍存在的不确定性后对收到的不确定性前对收到接收方获得的信息量ijjiijiijjiabbaIabaIabbaI)/()();()/()();(jiijibaIaIbaI)/(1log)(1logjiibapap)()/(logijiapbap交互信息量，简称互信息物理意义：互信息量是一种消除的不确定性的度量。互信息量=先验的不确定性-尚存在(后验)的不确定性互信函数2014秋季信息12InfTheory&Coding-张祖平•交互信息量的表达形式一–互信函数告诉我们：只要给定信源空间[X·P]，也就是X的先验概率分布，再给定信道的信道矩阵[P]，也就是传输概率，就可以计算出任何一种信源符号通过信道传递后，输出任何一种输出符号，信道所传递的（r*s）个交互信息量I（ai;bj）–互信函数为定量描述信息传输问题，奠定了基础。–TIP：“传输概率矩阵，交互信息量矩阵，联合概率矩阵”的区别。信道的交互信息量17(;)ijIab)()/(logijiapbap1()()(|)()()(|)()ijijiijrjjiiipabpapbapa|bpbpbapa2014秋季信息12InfTheory&Coding-张祖平练习18已知信源空间和信道矩阵，求：(1)“输入a3，输出b2的概率”；(2)“输出b4的概率”；(3)“收到b3条件下推测输入a2”的概率。4.02.03.01.0:)(::][4321XPaaaaXPX136.022.01.03.0)()()()(22.04.04.01.02.01.03.01.01.0)()()()()3(19.02.04.02.02.01.03.04.01.0)()()()()2(04.02.02.0)()();()1(3232324134133414414432323bpabpapbapabpapbapbpabpapbapbpabpapbapiiiiiiiiii2014秋季信息12InfTheory&Coding-张祖平•互信函数分析，当p(ai/bj)=1–表明收信者收到输出符号bj后，推测信源以概率1发出符号ai，也就是收到bj可准确无误的认为收到了ai–表明ai的自信量只是交互信息量在后验概率=1时的特例–表明完全消除了对ai的不确定性，即唯一确定ai必须获得的最大信息•互信函数分析，当p(ai)p(ai/bj)1，I（ai；bj）0–表明收信者收到输出符号bj后，推测信源发出符号ai的后验概率，大于收到bj前对ai的先验概率–表明收信者收到bj后，判断信源发ai的可能性比先验概率增大–表明收信者收到bj后，对信源发ai的不确定性比收到bj前变小，因此收信者从收到bj中就可以获取关于ai的一定的信息量信道的交互信息量19(/)1(;)loglog()()()ijijiiipabIabIapapa2014秋季信息12InfTheory&Coding-张祖平•互信函数分析，当p(ai/bj)=p(ai)–表明收信者收到输出符号bj后，推测信源发出符号ai的后验概率，与收到bj前推测信源发ai的先验概率相等–表明收信者收到bj后，从中得不到任何关于ai的信息量•互信函数分析，当0p(ai/bj)p(ai)，I（ai；bj）0–表明收信者收到输出符号bj后，推测信源发出符号ai的后验概率，小于收到bj前对ai的先验概率–表明收信者收到bj后，对信源发ai的不确定性比收到bj前变大，因此收信者从收到bj中不但没有获取关于ai的信息量，而且还产生了负面效应。信道的交互信息量20(/)(;)loglog10()ijijipabIabpa2014秋季信息12InfTheory&Coding-张祖平•交互信息量的表达形式二--站在通信系统的立场上思考–通信前，输入输出可看作相互独立，同时出现的概率为p(ai)p(bj)，也就是说通信前在输入和输出端同时出现ai和bj的先验不确定性为：–通信后，输入符号ai和输出符号bi有了一定的联系，这个联系是信道的传递概率p(bj/ai)，因此通信后