数据通信与计算机网络参考

2019/8/171思维世界的发展，在某种意义上说，就是对惊奇的不断摆脱。-爱因斯坦（美国）2019/8/1724.2.3离散信道容量的一般计算方法(1)离散信道容量的计算方法(2)用拉格朗日乘子法求信道容量(3)一般离散信道容量计算步骤(4)举例2019/8/173(1)离散信道容量的计算方法•对一般离散信道求信道容量，就是在固定信道条件下，对所有可能的输入概率分布p(xi)，求平均互信息的极大值。•由于I(X;Y)是输入概率分布p(xi)的上凸函数，所以极大值一定存在。•因为I(X;Y)是n个变量{p(x1),p(x2),…,p(xn)}的多元函数，并满足，所以可用拉格朗日乘子法计算这个条件极值。2019/8/174(2)用拉格朗日乘子法求信道容量•引进一个新函数其中λ为拉格朗日乘子，解方程组可得一般信道容量C。(4.2.21)2019/8/175•将I(X;Y)的表达式代入(4.2.21)得•整理得(4.2.23)(2)用拉格朗日乘子法求信道容量2019/8/176•式(4.2.24)左边为平均互信息的极大值，即(4.2.25)(2)用拉格朗日乘子法求信道容量2019/8/177(2)用拉格朗日乘子法求信道容量2019/8/178(3)一般离散信道容量计算步骤•一般离散信道容量对计算步骤总结如下：2019/8/179•注意：在第②步信道容量C被求出后，计算并没有结束，必须解出相应的p(xi)，并确认所有的p(xi)≥0时，所求的C才存在。在对I(X;Y)求偏导时，仅限制，并没有限制p(xi)≥0，所以求出的p(xi)有可能为负值，此时C就不存在，必须对p(xi)进行调整，再重新求解C。近年来人们一般采用计算机，运用迭代算法求解。(3)一般离散信道容量计算步骤2019/8/1710(4)举例[例4.2.2]有一信道矩阵，求信道容量C。解：2019/8/1711因为ε是条件转移概率p(y1/x2)，所以0≤ε≤1，从而有p(x1)≥0，p(x2)≥0，保证了C的存在。111112111()221(1)()2,()1()1(1)1(1)jmmCjjjCpypypypy③由，有(4)举例2019/8/17124.3多符号离散信道如果在不同时刻有多个来自于同一信源的随机变量（多符号信源）通过离散信道传输，称这种信道为多符号离散信道。4.3.1多符号离散信道的数学模型4.3.2离散无记忆信道和独立并联信道的信道容量2019/8/17134.3.1多符号离散信道的数学模型多符号离散信道定义定义：多符号离散信源X=X1X2…XN在N个不同时刻分别通过单符号离散信道{XP(Y/X)Y}，则在输出端出现相应的随机序列Y=Y1Y2…YN，这样形成一个新的信道称为多符号离散信道。由于新信道相当于单符号离散信道在N个不同时刻连续运用了N次，所以也称为单符号离散信道{XP(Y/X)Y}的N次扩展。多符号离散信道数学模型设信源矢量X的每一个随机变量Xk(k=1,2,…,N)均取自并取遍于信道的输入符号集{x1,x2,…,xn}，则信源共有nN个不同的元素ai(i=1,2,…,nN)。4.3多符号离散信道2019/8/1714该信源通过多符号离散信道{XP(Y/X)Y}后，相对于每一个ai，信道输出端输出一个相应的、由N个符号组成的输出符号序列bj。4.3.1多符号离散信道的数学模型4.3多符号离散信道多符号离散信道/单符号离散信道的N次扩展信道数学模型如图所示。它的输入输出关系可表示为信道矩阵：2019/8/1715单符号离散信道的N次扩展信道的数学模型单符号离散信道的N次扩展信道数学模型如图所示4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1716单符号离散无记忆信道与其N次扩展信道传递概率之间的关系无记忆性：离散信道在时刻k的输出随机变量Yk只与时刻k的输入随机变量Xk(k=1,2,…,N)有关，与k时刻之前的输入随机变量X1X2…Xk-1和输出随机变量Y1Y2…Yk-1无关。无预感性：k时刻之前的输出随机变量序列Y1Y2…Yk-1只与k时刻之前的输入随机变量序列X1X2…Xk-1有关，与以后的第k时刻的输入随机变量Xk无关。离散无记忆信道的N次扩展信道4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1717离散无记忆信道的N次扩展信道的传递概率等于各单位时刻相应的单符号离散无记忆信道的传递概率的连乘。离散无记忆信道的N次扩展信道既是无记忆的，又是无预感的。即输出随机变量Yk只与对应的输入随机变量Xk有关。离散无记忆信道的N次扩展信道的数学模型可以用下图表示4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1718单符号离散无记忆信道与其N次扩展信道平均互信息之间的关系离散无记忆信道N次扩展信道两端的平均互信息为I(X;Y)=H(Y)－H(Y/X)平均互信息公式4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1719第k个随机变量Xk单独通过单符号离散信道时的平均互信息N个输入、输出变量的平均互信息之和为上两式相减得4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1720当且仅当信源X=X1X2…XN无记忆，或者说信源X是离散无记忆信源X的N次扩展信源XN=X1X2…XN时，即即输出端各Yk(k=1,2,…,N)相互独立。4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道结论1：离散无记忆信道的N次扩展信道的平均互信息，不大于N个随机变量X1X2…XN单独通过信道{XP(Y/X)Y}的平均互信息之和。2019/8/1721这时有结论2：离散无记忆信道的N次扩展信道，当输入端的N个输入随机变量统计独立时，信道的总平均互信息等于这N个变量单独通过信道的平均互信息之和。4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1722单符号离散无记忆信道与其N次扩展信道信道容量之间的关系由于离散无记忆信源的N次扩展信源中的随机变量都取自同一符号集Xk∈{x1x2…xN}(k=1,2,…,N)，并具有相同的概率分布，而且都通过同一个离散无记忆信道[XP(Y/X)Y]，信道输出端随机变量序列中的随机变量Yk(k=1,2,…,N)也取自同一符号集并具有相同的概率分布，而且相互统计独立。所以I(Xk;Yk)=I(X;Y)结论：离散无记忆信道的N次扩展信道，如果信源也是离散无记忆信源的N次扩展信源，则信道总的平均互信息是单符号离散无记忆信道平均互信息的N倍。4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1723结论的说明：因为离散无记忆信道N次扩展信道可以用N个单符号离散信道来等效，这N个信道之间没有任何关联关系，若输入端的N个随机变量之间也没有任何关联关系的话，就相当于N个毫不相干的单符号离散信道在分别传送各自的信息，所以在扩展信道的输出端得到的平均信息量必然是单个信道的N倍。用C表示离散无记忆信道容量，用CN表示其扩展信道容量，CN=NC4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1724独立并联信道独立并联信道/独立并列/独立平行/积信道：输入和输出随机序列中的各随机变量取值于不同的符号集，就构成了独立并联信道。是离散无记忆信道的N次扩展信道的推广。输入随机序列X=X1X2…XN，Xk∈{x1k,x2k,…,xnk}输出随机序列Y=Y1Y2…YN，Yk∈{y1k,y2k,…,ynk}N个独立并联信道的容量CN第k个单符号离散无记忆信道的信道容量Ck当输入端各随机变量统计独立，且每个输入随机变量Xk(k=1,2,…,N)的概率分布达到各自信道容量Ck(k=1,2,…,N)的最佳分布时，CN达到其最大值：4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1725独立并联信道推广到更一般情况：输入各随机变量不但取值于不同的符号集，而且各集合的元素个数也不相同；输出随机变量也取值于不同的符号集合，各集合的元素个数也不相同；这种更一般的信道可得到与上述类似的结论。可以把N个变量的独立并联信道看成是离散无记忆信道的N次扩展信道的推广，也可以把离散信道的N次扩展看成是独立并联信道的特例。4.3.2离散无记忆信道和独立并联信道的信道容量4.3多符号离散信道2019/8/1726单路通信系统：不论是单符号的还是多符号的，都只有一个输入端和一个输出端的信道称为单用户信道，相应的通信系统称为单路通信系统。多路通信系统：为了提高通信效率，通信网中的信道往往有多个输入端和多个输出端，这种信道称为多用户信道，相应的通信系统称为多路通信系统。网络信息论/多用户信息论：研究多路通信系统信息传递的理论。实际的信道大部分是多用户信道。例如：计算机通信、卫星通信、广播通信、有线电视等。4.4.1多址接入信道4.4.2广播信道4.4.3相关信源的多用户信道问题4.4多用户信道2019/8/1727定义及信道模型多址接入信道/多元接入信道：多个用户的信息用多个编码器分别编码以后，送入同一信道传输，在接收端用一个译码器译码，然后分送给不同的用户。这是有多个输入端但只有一个输出端的多用户信道。多址接入信道模型如下图所示4.4.1多址接入信道4.4多用户信道2019/8/1728二址接入信道的信道容量最简单的多址接入信道是只有两个输入端和一个输出端的二址接入信道，如下图所示。U1至U’1的信息率R1，信道容量C1U2至U’2的信息率R2，信道容量C2总信道容量C124.4.1多址接入信道4.4多用户信道2019/8/1729二址接入信道信息率和信道容量之间满足如下条件这些条件确定了二址接入信道以R1和R2为坐标的二维空间中的某个区域（图中阴影部分），这个区域的界线就是二址接入信道的容量。4.4.1多址接入信道4.4多用户信道当X1和X2相互独立时有max(C1,C2)≤C12≤C1+C22019/8/1730多址接入信道的信道容量二址接入信道的结论很容易推广到多址接入信道；多址接入信道参数多址接入信道数N第r个编码器的信息率为Rr相应的信道容量为Cr；信道总容量为CΣ4.4.1多址接入信道4.4多用户信道2019/8/1731当输入各信源独立时有4.4.1多址接入信道4.4多用户信道这些限制条件规定了一个在N维空间的体积，这个体积的外型是一个截去角的多面体，多面体内是信道允许的信息率，多面体的上界就是多址接入信道的容量。2019/8/1732定义：具有一个输入和多个输出的信道称为广播信道。最简单的广播信道是单输入双输出广播信道，如下图所示：对于一般的广播信道，很难用系统的方法求出其信息率可达区域，只在某些特殊的情况下，能够证明信道容量的容量界线是可以达到的。4.4.2广播信道4.4多用户信道信源1信源2编码器译码器2信道译码器1U1U2XY1U’1U’2图3.4.4单输入双输出广播信道模型Y22019/8/1733定义：由多个单用户信道组成的并联信道，传送相互有关的多路信息的信道。这种信道有多个输入和多个输出，且输入端各信源之间有关联关系。两个相关信源用两个独立信道传送的多用户信道模型。随着网络技术的发展，多用户信息论在近代信息论中越来越为大家关注，不过许多问题还没有找到系统的解决方法。4.4.3相关信源的多用户信道问题4.4多用户信道2019/8/1734定义：当信源与信道连接时，若信息传输率达到了信道容量，我们称此信源与信道达到匹配。否则，认为信道有剩余。信道冗余度定义：信道冗余度＝C-I(X;Y)C表示该信道的信道容量，I(X;Y)表示信源通过该信道实