第4章离散信道ppt课件

1、信息论与编码理论第4章 离散信道4.1 离散信道的数学模型n由于干扰的存在，信道的输出Y与信道的输入X不完全相同，用条件概率p(y|x)描画。n而输入和输出又有各自的统计特性，分别用 和 表示。XPYP 4.2 信道的分类n根据输入输出事件的时间特性n离散信道：GSMn连续信道：有线电视、广播n半连续信道n根据输入输出个数n两端信道单路信道）：n多元接入信道：信道的复用n广播信道：广播n根据统计特性n恒参信道：信道的统计特性不随时间发生变化。n随参信道：信道的统计特性随时间发生变化。n根据记忆特性n无记忆信道：信道的输出仅与当前的输入有关，与以前的输入无关。n有记忆信道：信道的输出不仅与当前的

2、输入有关，与以前的输入也有关系。几种特殊信道n无噪无损信道：输入集和输出集之间存在一一对应的关系。n有噪无损信道：有噪无损信道的一个输入符号可能对应多个输入符号，而一个输出符号只对应一个输入符号。n无噪有损信道：无噪有损信道的一个输入符号只对应一个输入符号，而一个输出符号可能对应多个输入符号。n无用信道：输入与输出相互独立，没有任何关系。4.3 离散无记忆信道4.3.1 离散信道的数学模型n离散无记忆信道中，当前的输出yj仅与当前的输入xi有关，与过去的输入无关，即yj出现的概率仅与xi有关n信道转移矩阵或者信道矩阵1112121222|12ssY XrrrsppppppPppp例4-3n假设

3、串口通信的误码率为4%，即A发送“0而B接收到“1的概率是0.04，A发送“1而B接收到“0的概率也是0.04，可以得到该信道的信道转移矩阵|0.960.040.040.96Y XPn二进制对称信道n简称为BSCBinary Symmetric Channel）n二元：输入和输出符号集均为0,1n对称：1变成0和0变成1的概率相等。np(0|0)=p(1|1)=1-p，p(0|1)=p(1|0)=pnBSC的信道矩阵：ppPpp4.3.2 信道疑义度和噪声熵n定义定义4-1 称输入空间称输入空间X对输出空间对输出空间Y的条件的条件熵熵n 为信道疑义度。为信道疑义度。n含义：收到全部输出符号含义

4、：收到全部输出符号Y以后，对输入符以后，对输入符号号X尚存在的平均不确定性。尚存在的平均不确定性。n这种不确定性是由信道干扰引起的。这种不确定性是由信道干扰引起的。n对无噪信道：对无噪信道：H(X|Y)=0。nH(X|Y)H(X)：收到输出符号：收到输出符号Y以后，总能以后，总能消除一些对消除一些对X的不确定性，获得一些信息。的不确定性，获得一些信息。 (|)()log (|)ijijijH X Yp abp ab n【定义4-1】 称信道的输入空间X对输出空间Y的条件熵n为信道疑义度。n信道疑义度的含义是观察到信道的输出之后仍然保留的关于信道输入的平均不确定性。n这种对X尚存在的不确定性是由

5、于传输过程中的信道干扰引起的。(|)()log (|)ijijXYH X Yp x yp xy 4.3.3 平均互信息n定义定义4-3 原始信源熵与信道疑义度之差称为原始信源熵与信道疑义度之差称为平均互信息。平均互信息。nI(X;Y)=H(X)-H(X|Y)n平均互信息具有非负性。平均互信息具有非负性。n含义：接收到信道的输出符号集含义：接收到信道的输出符号集Y之后，平之后，平均每个符号获得的关于信道输入符号集均每个符号获得的关于信道输入符号集X的的信息量，即通过信道传送过去的信息量。信息量，即通过信道传送过去的信息量。( | )( | )(; )()log()log( ;)( )( )XYX

6、Yp x yp y xI X Yp xyp xyI Y Xp xp y两个定理n定理4-1 对于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函数。n固定信道：信道传递概率p(y|x)不变n定理4-2 对于固定的信源分布，平均互信息I(X;Y)是信道传递概率p(y|x)的下凸函数。n固定信源：信源概率分布p(x)不变( | )( | )(; )()log( | ) ( )log( )( | ) ( )XYXYXp y xp y xI X Yp xyp y x p xp yp y x p x信源信源信道信道平均互信息的例子n例例4-6 信源：信源： 信道：信道：n则互信息量：则互

7、信息量：(0,0)(0) (0|0)(0,1)(0) (1|0)(1,0)(1) (0|1)(1,1)(1) (1|1)p xyp xp yxpp xyp xp yxpp xyp xp yxpp xyp xp yxp011XPppPpp( | )(; )( ;)()log()( )( )XYp y xI X YI Y Xp xyHppH pp y(0)(0,0)(1,0)(1)(1)(0,1)(1,1)(1)p Yppppppp Ypppppp固定信道固定信道p p固定固定从从0 0到到1 1变化变化固定信源固定信源固定固定p p从从0 0到到1 1变化变化4.4 信道的组合n组合方式n 并行

8、：积信道 串行：级联信道n 例如：Internet 例如：GSMn重点介绍级联信道串联信道）n假设串联的两个信道为信道假设串联的两个信道为信道I和信道和信道II，信道，信道I的传的传递概率为递概率为p(y|x)，信道，信道II的传递概率为的传递概率为p(z|xy)。n定理定理4-3 若随机变量若随机变量X,Y,Z构成一个马尔可夫链构成一个马尔可夫链p(z|xy)=p(z|y)），则有），则有nI(X;Z)I(X;Y) I(X;Z)I(Y;Z)n定理定理4-3叫做数据处理定理，它的含义是通过串联叫做数据处理定理，它的含义是通过串联信道的传输，只会丢失信息，不会增加信息，至信道的传输，只会丢失信息

9、，不会增加信息，至多保持原来的消息量。这是信息不增性原理。多保持原来的消息量。这是信息不增性原理。信道Ip(y|x)信道IIp(z|xy)XYZ例4-7 两个二元对称信道串联n一个马尔可夫链，则串联信道总的信道矩阵为n那么 I(X;Y)=1-H(p)n I(X;Z)=1-H(2p(1-p)n从图中能够看出n I(X;Z)I(X;Y)011/21/2XP1211ppPPpp221222(1)2 (1)2 (1)(1)ppppPPPppppn例4-8n信道I和信道II的信道矩阵分别为nX,Y,Z构成一个马尔可夫链，那么|11110033302/31/311001/32/322Y XZ YPP|11

10、111110033333302/31/311111001/32/326322Z XY XZ YPPP 4.5 信道容量4.5.1 信息传输率n在信息传输过程中，信道每传递一个符号所能携带载荷的平均信息量称为信道的信息传输率，记作R。n若平均传输一个符号需要t秒，而每一个符号传送的信息量为I(X;Y)，则信道每秒传输的信息量为n通常将Rt称为信息传输速率，或者传输速率。(; )RI X Y1(; )tRI X Yt4.5.2 信道容量n定义4-4 信道容量定义为平均互信息的最大值：nC=maxp(x)I(X;Y)n由定理4.2.1知，I(X;Y)是p(x)的上凸函数，称使I(X;Y)取最大值的p

11、(x)为最佳输入分布。n信道容量表示信道传送信息的最大能力。n由I(X;Y)的定义式可知， I(X;Y)是由信道特性p(y|x)和信源特性p(x)共同决定的，n但是容量C已对所有n可能的p(x)取最大值，因此n容量C仅与信道特性p(y|x)有关，n也就是说，容量C是信道的固有n特性，与信源无关。( | )( | )(; )()log( | ) ( ) log( )( | ) ( )XYXYXp y xp y xI X Yp xyp y x p xp yp y x p x信道容量的例子例4-10）n 信源： 信道：n则互信息量：n从图中可以看出，当=1/2时，I(X,Y)取最大值nC=1-H(p

12、)011XPppPpp(; )()( )I X YHppH p固定信道固定信道p p固定固定从从0 0到到1 1变化变化4.5.3 三种特殊信道的信道容量n无噪无损信道n有噪无损信道n无噪有损信道无噪无损信道n输出与输入是一一对应关系，n 即信道矩阵为单位矩阵。n因此信道疑义度H(X|Y)=0，噪声熵H(Y|X)=0。n则I(X;Y) =H(X)-H(X|Y)=H(X)n =H(Y)-H(Y|X)=H(Y)n因此信道容量nC=maxp(x)I(X;Y) )=maxp(x)H(X)=logrn=maxp(x)H(Y)=logs有噪无损信道n一个输入对应多个互不n 相交的输出，即信道矩n 阵的每一

13、列只有一个非n 零元素。n由于知道输出之后，必然能够确定其对应的输入是什么，因此信道疑义度H(X|Y)=0。n则I(X;Y)=H(X)-H(X|Y)=H(X)n因此信道容量nC=maxp(x)I(X;Y)=maxp(x)H(X)=logr1/31/61/200000010000001/43/4P无噪有损信道n一个输出对应多个互不相交n 的输入，即信道矩阵的每一行n 只有一个“1”，其余元素均为0。n由于知道输出之后，必然能够确定其对应的输入是什么，因此噪声熵H(Y|X)=0。n则I(X;Y)=H(Y)-H(Y|X)=H(Y)n因此信道容量nC=maxp(x)I(X;Y)=maxp(x)H(Y)

14、=logs100100100010001001P4.5.4 对称信道的信道容量n定义4-5 信道矩阵的每一行都是其他行的不同排列，则称此类信道为输入对称信道。n定义4-6 信道矩阵的每一列都是其他列的不同排列，则称此类信道为输出对称信道。n定义4-7 若一个离散无记忆信道，既是输入对称信道，又是输出对称信道，这类信道称为对称信道。0.40.60.60.40.50.5P0.70.20.10.10.70.2P1111336611116633P 1/21/31/61/61/21/31/31/61/2P对称信道的容量n定理4-4 若一个离散对称信道有r个输入符号，s个输出符号，则当输入为等概分布时，达

15、到信道容量C，且nC=logs-H(p1p2 ps )n 式中，p1 p2 ps 为信道矩阵中的任一行。n“当输入为等概分布时，达到信道容量C的含义是最佳输入为等概分布。对称信道容量的例子n例 n这是一个对称信道n最佳输入为：n信道容量为：nC=logs-H(p1 p2 ps )=log3-H(1/2,1/3,1/6)1/21/31/61/61/21/31/31/61/2P111333XP111111log3logloglog0.1262233664.5.5 一般信道的容量n对于一般的离散无记忆信道而言，信道容量的计算比较复杂，可以用迭代算法实现。n迭代步骤如下：n取初始分布p(0)(x)。n

16、根据公式4-21计算P(k)(xi|yj)。n根据公式4-22计算p(k+1)(xi)。n根据公式4-23计算C(k+1)。n假设| C(k+1) C(k) | ，则转向步骤7。n令k = k+1，转向步骤2。n输出p(k+1)(xi)和C(k+1)。4.5.6 信源和信道的匹配n信源与信道达到匹配的含义：信源处于最佳输入分布，使得信息传输率R达到了信道容量C。n但通常情况下，让信源处于最佳输入分布并不容易，此时信道有剩余：n信道剩余度=C-I(X;Y)n信源编码的目的就是通过编码，改变原始信源的统计特性，使得信道剩余度尽可能小。原始信源信道不匹配原始信源信道信源编码基本匹配本章小结n信道可以从不同的角度分类。从输入和输出符号的时间特性分，可以分为离散信道、连续信道和半连续信道。从输入和输出端的