第4章 离散信道

信息论与编码理论第4章离散信道4.1离散信道的数学模型由于干扰的存在，信道的输出Y与信道的输入X不完全相同，用条件概率p(y|x)描述。而输入和输出又有各自的统计特性，分别用和表示。XPYP4.2信道的分类根据输入输出事件的时间特性离散信道：GSM连续信道：有线电视、广播半连续信道根据输入输出个数两端信道（单路信道）：电话多元接入信道：信道的复用广播信道：广播根据统计特性恒参信道：信道的统计特性不随时间发生变化。随参信道：信道的统计特性随时间发生变化。根据记忆特性无记忆信道：信道的输出仅与当前的输入有关，与以前的输入无关。有记忆信道：信道的输出不仅与当前的输入有关，与以前的输入也有关系。几种特殊信道无噪无损信道：输入集和输出集之间存在一一对应的关系。有噪无损信道：有噪无损信道的一个输入符号可能对应多个输入符号，而一个输出符号只对应一个输入符号。无噪有损信道：无噪有损信道的一个输入符号只对应一个输入符号，而一个输出符号可能对应多个输入符号。无用信道：输入与输出相互独立，没有任何关系。x1x2x3y1y2y3y4y5y6有噪无损信道y1y2y3x1x2x3x4x5x6无噪有损信道y1y2y3x1x2x3x4无噪无损信道y44.3离散无记忆信道4.3.1离散信道的数学模型离散无记忆信道中，当前的输出yj仅与当前的输入xi有关，与过去的输入无关，即yj出现的概率仅与xi有关信道转移矩阵或者信道矩阵1112121222|12ssYXrrrsppppppPppp例4-3假设串口通信的误码率为4%，即A发送“0”而B接收到“1”的概率是0.04，A发送“1”而B接收到“0”的概率也是0.04，可以得到该信道的信道转移矩阵|0.960.040.040.96YXP二进制对称信道简称为BSC（BinarySymmetricChannel）二元：输入和输出符号集均为{0,1}对称：1变成0和0变成1的概率相等。p(0|0)=p(1|1)=1-p，p(0|1)=p(1|0)=pBSC的信道矩阵：a1=0a2=1b1=0b2=1pp1-p1-pppPpp4.3.2信道疑义度和噪声熵定义4-1称输入空间X对输出空间Y的条件熵为信道疑义度。含义：收到全部输出符号Y以后，对输入符号X尚存在的平均不确定性。这种不确定性是由信道干扰引起的。对无噪信道：H(X|Y)=0。H(X|Y)≤H(X)：收到输出符号Y以后，总能消除一些对X的不确定性，获得一些信息。(|)()log(|)ijijijHXYpabpab【定义4-1】称信道的输入空间X对输出空间Y的条件熵为信道疑义度。信道疑义度的含义是观察到信道的输出之后仍然保留的关于信道输入的平均不确定性。这种对X尚存在的不确定性是由于传输过程中的信道干扰引起的。(|)()log(|)ijijXYHXYpxypxy4.3.3平均互信息定义4-3原始信源熵与信道疑义度之差称为平均互信息。I(X;Y)=H(X)-H(X|Y)平均互信息具有非负性。含义：接收到信道的输出符号集Y之后，平均每个符号获得的关于信道输入符号集X的信息量，即通过信道传送过去的信息量。(|)(|)(;)()log()log(;)()()XYXYpxypyxIXYpxypxyIYXpxpy两个定理定理4-1对于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函数。固定信道：信道传递概率p(y|x)不变定理4-2对于固定的信源分布，平均互信息I(X;Y)是信道传递概率p(y|x)的下凸函数。固定信源：信源概率分布p(x)不变p(y|x)I(X;Y)p(x)I(X;Y)(|)(|)(;)()log(|)()log()(|)()XYXYXpyxpyxIXYpxypyxpxpypyxpx信源信道平均互信息的例子例4-6信源：信道：则互信息量：(0,0)(0)(0|0)(0,1)(0)(1|0)(1,0)(1)(0|1)(1,1)(1)(1|1)pxypxpyxppxypxpyxppxypxpyxppxypxpyxp011XPppPpp(|)(;)(;)()log()()()XYpyxIXYIYXpxyHppHppy(0)(0,0)(1,0)(1)(1)(0,1)(1,1)(1)pYpppppppYpppppp固定信道p固定从0到1变化固定信源固定p从0到1变化4.4信道的组合组合方式并行：积信道串行：级联信道例如：Internet例如：GSM重点介绍级联信道（串联信道）级联信道积信道假设串联的两个信道为信道I和信道II，信道I的传递概率为p(y|x)，信道II的传递概率为p(z|xy)。定理4-3若随机变量X,Y,Z构成一个马尔可夫链（p(z|xy)=p(z|y)），则有I(X;Z)≤I(X;Y)I(X;Z)≤I(Y;Z)定理4-3叫做数据处理定理，它的含义是通过串联信道的传输，只会丢失信息，不会增加信息，至多保持原来的消息量。这是信息不增性原理。信道Ip(y|x)信道IIp(z|xy)XYZ例4-7两个二元对称信道串联一个马尔可夫链，则串联信道总的信道矩阵为则I(X;Y)=1-H(p)I(X;Z)=1-H(2p(1-p))从图中能够看出I(X;Z)≤I(X;Y)011/21/2XP1211ppPPpp221222(1)2(1)2(1)(1)ppppPPPpppp例4-8信道I和信道II的信道矩阵分别为X,Y,Z构成一个马尔可夫链，则1/31/31/31/21/22/31/31/32/31XYZ1/31/31/21/6XZ1/31/3||11110033302/31/311001/32/322YXZYPP|||11111110033333302/31/311111001/32/326322ZXYXZYPPP4.5信道容量4.5.1信息传输率在信息传输过程中，信道每传递一个符号所能携带（载荷）的平均信息量称为信道的信息传输率，记作R。若平均传输一个符号需要t秒，而每一个符号传送的信息量为I(X;Y)，则信道每秒传输的信息量为通常将Rt称为信息传输速率，或者传输速率。(;)RIXY1(;)tRIXYt4.5.2信道容量定义4-4信道容量定义为平均互信息的最大值：C=maxp(x){I(X;Y)}由定理4.2.1知，I(X;Y)是p(x)的上凸函数，称使I(X;Y)取最大值的p(x)为最佳输入分布。信道容量表示信道传送信息的最大能力。由I(X;Y)的定义式可知，I(X;Y)是由信道特性p(y|x)和信源特性p(x)共同决定的，但是容量C已对所有可能的p(x)取最大值，因此容量C仅与信道特性p(y|x)有关，也就是说，容量C是信道的固有特性，与信源无关。信道1的最佳输入分布I(X;Y)p(x)信道1的容量信道2的最佳输入分布信道2的容量(|)(|)(;)()log(|)()log()(|)()XYXYXpyxpyxIXYpxypyxpxpypyxpx信道容量的例子（例4-10）信源：信道：则互信息量：从图中可以看出，当=1/2时，I(X,Y)取最大值C=1-H(p)011XPppPpp(;)()()IXYHppHp固定信道p固定从0到1变化4.5.3三种特殊信道的信道容量无噪无损信道有噪无损信道无噪有损信道无噪无损信道输出与输入是一一对应关系，即信道矩阵为单位矩阵。因此信道疑义度H(X|Y)=0，噪声熵H(Y|X)=0。则I(X;Y)=H(X)-H(X|Y)=H(X)=H(Y)-H(Y|X)=H(Y)因此信道容量C=maxp(x){I(X;Y)})}=maxp(x){H(X)}=logr=maxp(x){H(Y)}=logs有噪无损信道一个输入对应多个互不相交的输出，即信道矩阵的每一列只有一个非零元素。由于知道输出之后，必然能够确定其对应的输入是什么，因此信道疑义度H(X|Y)=0。则I(X;Y)=H(X)-H(X|Y)=H(X)因此信道容量C=maxp(x){I(X;Y)}=maxp(x){H(X)}=logr1/31/61/200000010000001/43/4P无噪有损信道一个输出对应多个互不相交的输入，即信道矩阵的每一行只有一个“1”，其余元素均为0。由于知道输出之后，必然能够确定其对应的输入是什么，因此噪声熵H(Y|X)=0。则I(X;Y)=H(Y)-H(Y|X)=H(Y)因此信道容量C=maxp(x){I(X;Y)}=maxp(x){H(Y)}=logs100100100010001001P4.5.4对称信道的信道容量定义4-5信道矩阵的每一行都是其他行的不同排列，则称此类信道为输入对称信道。定义4-6信道矩阵的每一列都是其他列的不同排列，则称此类信道为输出对称信道。定义4-7若一个离散无记忆信道，既是输入对称信道，又是输出对称信道，这类信道称为对称信道。0.40.60.60.40.50.5P0.70.20.10.10.70.2P1111336611116633P1/21/31/61/61/21/31/31/61/2P对称信道的容量定理4-4若一个离散对称信道有r个输入符号，s个输出符号，则当输入为等概分布时，达到信道容量C，且C=logs-H(p1p2…ps)式中，p1p2…ps为信道矩阵中的任一行。“当输入为等概分布时，达到信道容量C”的含义是最佳输入为等概分布。对称信道容量的例子例这是一个对称信道最佳输入为：信道容量为：C=logs-H(p1p2…ps)=log3-H(1/2,1/3,1/6)1/21/31/61/61/21/31/31/61/2P111333XP111111log3logloglog0.1262233664.5.5一般信道的容量对于一般的离散无记忆信道而言，信道容量的计算比较复杂，可以用迭代算法实现。迭代步骤如下：取初始分布p(0)(x)。根据公式（4-21）计算P(k)(xi|yj)。根据公式（4-22）计算p(k+1)(xi)。根据公式（4-23）计算C(k+1)。若|C(k+1)−C(k)|δ，则转向步骤7。令k=k+1，转向步骤2。输出p(k+1)(xi)和C(k+1)。4.5.6信源和信道的匹配信源与信道达到匹配的含义：信源处于最佳输入分布，使得信息传输率R达到了信道容量C。但通常情况下，让信源处于最佳输入分布并不容易，此时信道有剩余：信道剩余度=C-I(X;Y)信源编码的目的就是通过编码，改变原始信源的统计特性，使得信道剩余度尽可能小。原始信源信道不匹配原始信源信道信源编码基本匹配本章小结信道可以从不同的角度分类。从输入和输出符号的时间特性分，可以分为离散信道、连续信道和半连续信道。从输入和输出端的个数分，可以分为两端信道、多元接入信道和广播信道。从信道的统计特性分，信道可以分为恒参信道和随参信道。从信道的记忆特性分，信道可以分为无记忆信道和有记忆信道。还给出了三种特殊信道：无噪无损信道、有噪无损信道、无噪有损信道