第3章-离散信道与其容量-2005-9

第3章_离散信道与其容量-2005-9第一页，共126页。3.1信道的数学模型及分类3.1信道的数学模型及分类

通常信源发送包含信息的消息，消息转换成适合信道传输的信号，然后通过信道传递给接收者。信道中的干扰或者噪声，使信道传输的信号错误或者失真，因此信道的输入和输出之间一般是不确定的函数关系，而是统计依赖关系。因此，只要知道输入输出信号以及它们的统计依赖关系，那么信道的全部特性就确定了。了解第二页，共126页。3.1信道的数学模型及分类3.1.1信道的分类了解第三页，共126页。3.1信道的数学模型及分类离散信道连续信道半离散或半连续信道时间离散的连续信道波形信道根据输入和输出信号的特点：了解第四页，共126页。3.1信道的数学模型及分类按信道的转移概率特点来分:有噪信道无噪信道无损信道(每个输入对应多个输出);确定信道(多个输入对应单个输出);无扰信道(一个输入对应一个输出).无记忆信道有记忆信道了解第五页，共126页。3.1信道的数学模型及分类根据信道输入端和输出端的关联无反馈信道反馈信道了解第六页，共126页。3.1信道的数学模型及分类根据载荷消息的媒体不同邮递信道电信道光信道声信道根据信道的参数与时间的关系：固定参数信道时变参数信道根据信道的记忆特性无记忆信道有记忆信道了解第七页，共126页。3.1信道的数学模型及分类根据信道的用户多少多元接入信道广播信道两端(单用户)信道多端(多用户)信道了解第八页，共126页。3.1信道的数学模型及分类3.1.2信道的数学模型

条件概率P(y|x)描述了输入信号和输出信号之间统计依赖关系,反映了信道的统计特性.

信道的数学模型有几种描述方法：(1)如上图用框图描述；(2)数学语言描述；(3)信道传递图描述；(4)信道传递矩阵描述。理解第九页，共126页。3.1信道的数学模型及分类1无扰(无噪声)信道

信道中没有随机性的干扰或干扰很小，输出信号y与输入信号x之间有确定的对应的关系，其信道传递图的特点：一一对应或多对一，但不交叉。即：y＝f(x)理解第十页，共126页。3.1信道的数学模型及分类2有干扰无记忆信道输入和输出间因噪声干扰而没有确定的对应关系，但任一时刻的输出只依赖于对应时刻的输入。其信道传递图特点是：一对多但不交叉。或者:理解第十一页，共126页。满足离散无记忆信道的充要条件：无记忆信道：若信道的任一时刻的输出符号只依赖于对应时刻的输入符号。理解第十二页，共126页。3.1信道的数学模型及分类充要条件：[证明]

充分性：若信道传递概率满足上式，则离散信道为无记忆信道。理解第十三页，共126页。3.1信道的数学模型及分类必要性：若离散信道无记忆，则必须满足上式。证明：根据离散无记忆信道的定义可知：理解第十四页，共126页。3.1信道的数学模型及分类3有干扰(噪声)有记忆信道实际信道往往是既有干扰(噪声)又有记忆的.

例如在数字信道中，由于信道滤波使频率特性不理想时造成了码字之间的干扰。这类信道中输出符号不但与对应时刻的输入符号有关，而且还与以前信道的输入符号及输出符号有关，这样的信道称为有记忆信道。理解第十五页，共126页。3.1信道的数学模型及分类3.1.3单符号离散信道的数学模型输入符号为X，取值于{a1,a2,…,ar}。输出符号为Y，取值于{b1,b2,…,bs}。条件概率：P(y|x)＝P(y=bj|x=ai)＝P(bj|ai)称为信道的传递概率或转移概率。作用：用来描述信道干扰影响的大小。理解第十六页，共126页。3.1信道的数学模型及分类3.1.3单符号离散信道的数学模型

简单的单符号离散信道可以用概率空间

[X,P(y|x),Y]描述:理解第十七页，共126页。3.1信道的数学模型及分类

信道中存在干扰，输入符号在传递过程中会产生错误，这种信道干扰对传输的影响可以用传递概率p(bj|ai)来描述。所有的传递概率构成传递概率矩阵P，如下图所示：

b1b2…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)掌握第十八页，共126页。[例3-1]二元对称信道(BSC：BinarySymmetricalChannel)，已知其信道传递图，求转移概率矩阵。1－p

a1=00=b11－p

a2=11=b2pp解：X:{0,1}；Y:{0,1}r=s=2，a1=b1=0；a2=b2=1。传递概率：p是单个符号传输发生错误的概率。(1-p)表示是无错误传输的概率。转移矩阵如右图:3.1信道的数学模型及分类掌握第十九页，共126页。[例3-2]二元删除信道(BEC，BinaryEliminatedChannel)，其信道传递图如图，求传递概率矩阵。p001－p11q1－q2解：X：{0,1}Y：{0,1,2}此时，r＝2，s＝3。传递矩阵为：

符号“2”表示接收到了“0”、“1”以外的特殊符号。3.1信道的数学模型及分类掌握第二十页，共126页。[例3-3]二元对称消失信道，其信道传递图如下图，求其传递概率矩阵。解：X:{0,1}；Y:{0,x,1}r=2，s=3转移概率矩阵:3.1信道的数学模型及分类掌握第二十一页，共126页。假设信源符号集合X：A={a1,a2,…ar}；接收端符号集合Y：B={b1,b2,…bs}，则单符号离散无记忆信道模型为[X,P(y|x),Y]

或者：先验概率：p(ai)联合概率：p(aibj)前向(传递或转移)概率：p(bj|ai)后向(后验)概率：p(ai|bj)；输出符号概率:p(bj)3.1信道的数学模型及分类理解第二十二页，共126页。根据联合概率计算输出符号的概率3.1信道的数学模型及分类P(b1|a1)P(b2|a1)…P(bs|a1)P(b1|a2)P(b2|a2)…P(bs|a2)…….……P(b1|ar)P(b2|ar)…P(bs|ar)P=3.20掌握第二十三页，共126页。3.2平均互信息及其性质3.2.1信道疑义度

H(X)是在接收到输出Y以前，关于输入变量X的先验不确定性，称为先验熵。接收到bj后，关于X的不确定性为:

当信道接收端接收到输出符号bj后，关于输入符号的信息测度(平均不确定性)，称为后验熵。掌握第二十四页，共126页。3.2平均互信息及其性质对后验熵在符号集Y中求数学期望,得条件熵：

称为信道疑义度，它表示在输出端接收到输出变量Y之后，对输入端的变量X尚存在的平均不确定性(疑义),由信道干扰(噪声)引起的。若信道是一一对应(或者一对多不交叉)的无干扰信道，那么p(ai|bj)=1，则H(X|Y)=0。掌握第二十五页，共126页。解：信道矩阵为:[例3-4]已知二元删除信道传递图如图所示,已知信源X的概率分布为，求H(X|Y)。掌握第二十六页，共126页。3.2平均互信息及其性质掌握第二十七页，共126页。3.2平均互信息及其性质掌握第二十八页，共126页。3.2平均互信息及其性质3.2.2平均互信息互信息量I(xi;yj):收到消息yj后获得关于xi的信息量。

表示先验的不确定性减去尚存的不确定性,就是单次通信过程中收信者获得的信息量。对于无干扰信道，I(xi;yj)=I(xi)；对于全损信道，I(xi;yj)=0。掌握第二十九页，共126页。3.2平均互信息及其性质3.2.2平均互信息平均互信息I(X;Y)：I(xi;yj)的统计平均。掌握第三十页，共126页。3.2平均互信息及其性质

互信息I(x;y)代表收到某消息y后获得关于某事件x的信息量，它可取正值，也可取负值。

I(x;y)<0，在未收到信息y以前对消息x不确定性小于收到消息y后的不确定性(噪声的影响)。

I(X;Y)

表示输入与输出两个随机变量之间的统计约束程度(或相关程度)。

了解第三十一页，共126页。3.2平均互信息及其性质

通常I(X;Y)≥0，若I(X;Y)=0，表示不能获得信息量—全损信道。

I(X;Y)=H(X)表示通信时获得的信息量即为信源发送的信息量—无噪（无损）信道。了解第三十二页，共126页。3.2平均互信息及其性质互信息与信息熵之间的关系：掌握第三十三页，共126页。3.2平均互信息及其性质掌握第三十四页，共126页。3.2平均互信息及其性质掌握第三十五页，共126页。3.2平均互信息及其性质H(XY)左边的圆代表随机变量X的熵，右边的圆代表随机变量Y的熵，两个圆重叠部分是平均互信息I(X;Y)。每个圆减去I(X;Y)后剩余的部分代表两个疑义度。H(X)I[X;Y]H(Y)★H(X|Y)是信道疑义度，表示符号通过有噪信道后所引起的信息量的损失，故也称为损失熵。★H(Y|X)是由信道噪声引起的，和信道统计特性p(y|x)相关的熵,称为噪声熵。H(X|Y)=H(X)-I(X;Y)H(Y|X)=H(Y)-I(X;Y)理解第三十六页，共126页。两种极端情况的信道

输入符号集合X：A={a1,a2,…ar}；输出符号集合Y：B={b1,b2,…bs}，s=r。信道传递概率如下：情况1：符号的传递概率等于1，否则等于0.H(X|Y)=0H(Y|X)=0I(X;Y)=H(X)=H(Y)掌握第三十七页，共126页。两种极端情况的信道

输入符号集合X：A={a1,a2,…ar}；输出符号集合Y：B={b1,b2,…bs}，s=r。信道传递概率如下：情况2：信道输入端X与输出端Y完全统计独立H(X|Y)=H(X)H(Y|X)=H(Y)I(X;Y)=0掌握第三十八页，共126页。两级级联信道XP(Y/X)YP(Z/Y)Z3.2.3平均条件互信息了解第三十九页，共126页。

定义已知事件z属于Z的条件下，接收到y后获得关于某事件x的条件互信息了解第四十页，共126页。证明：

了解第四十一页，共126页。定义

了解第四十二页，共126页。证明：

了解第四十三页，共126页。平均互信息的链式法则了解第四十四页，共126页。了解第四十五页，共126页。了解第四十六页，共126页。[例3-3]4个等概率分布的消息M1，M2，M3，M4被送入一个二元无记忆对称信道进行传送。通过编码使M1=00，M2=01，M3=10，M4=11。试问。输入是M1和输出符号是0的互信息是多少？如果知道第二个符号也是0，这时带来多少附加信息量？1－p001－p11pp3.1信道的数学模型及分类掌握第四十七页，共126页。[解]P(M1)

=P(M2)=

P(M3)=

P(M4)=1/4

P(0|M1)=P(0|0)=1-pP(M10)=P(M1).P(0|M1)=(1-p)/4

1－p001－p11ppP(M100)=P(M1).P(00|M1)=(1-p)2/4P(00|M1)=P(00|00)=(1-p)2第四十八页，共126页。3.2平均互信息及其性质3.3平均互信息的特性1非负性I(X;Y)≥0

物理意义：I(X;Y)不会是负值，即从平均的角度总能消除一些不确定性。除非输入与输出统计独立才不能接收到任何信息，但也不会失去信息。了解第四十九页，共126页。3.2平均互信息及其性质2极值性I(X;Y)≤H(X)

物理意义：从某一事件(Y或X)提取关于另一事件(X或Y)的信息量，最多只有这个事件所包含的所有信息量H(X)或H(Y)。了解第五十页，共126页。3.2平均互信息及其性质3交互性I(X;Y)=I(Y;X)

物理意义：I(X;Y)表示从Y中提取的关于X的信息量，I(Y;X)表示从X当中提取的关于Y的信息量。特别的：当X、Y统计独立时，就不可能从一个随机变量中获得关于另一个随机变量的任何信息。了解第五十一页，共126页。3.2平均互信息及其性质4上凸性

I(X;Y)是关于输入信源概率分布p(x)的上凸函数，是关于信道传递概率p(y|x)的下凸函数。证明:先假设信道是固定信道，则其信道特性固定，即转移概率p(y|x)不受p(x)的变化影响。令p1(x)和p2(x)为信源的两种概率分布，相应的互信息分别记为：I[p1(x)]和I[P2(X)]设任意正数0＜θ＜1，且有p(x)=θp1(x)+(1-θ)p2(x)了解第五十二页，共126页。3.2平均互信息及其性质结论：I[X;Y]是输入信源概率分布p(x)的上凸函数。了解第五十三页，共126页。例3.3

设信源X的概率空间为：信道特征如下图，计算平均互信息1－p001－p11pp掌握第五十四页，共126页。解1－p001－p11pp由可求得

平均互信息量

掌握第五十五页，共126页。第五十六页，共126页。3.4信道容量及其计算3.4.1信道容量的定义

信道中平均每个符号所能传送的信息量，称为信道的信息传输率，记为R。

R=I(X;Y)=H(X)-H(X|Y)

（bit/symbol）掌握第五十七页，共126页。3.4信道容量及其计算3.4.1信道容量的定义

若信道每传递一个符号需要的时间为t秒，则信道单位时间传输的信息量为信息传输速率：Rt=I(X;Y)/t=[H(X)-H(X|Y)]/t(bit/symbol)

了解第五十八页，共126页。3.4信道容量及其计算

信道容量的定义有两种方式，1、定义信息传输率的最大值为信道容量。2、定义信息传输速率的最大值为信道容量。掌握第五十九页，共126页。注：(1)如无特殊说明，本书的信道容量都采用第一种定义。

(2)信道容量的单位为bit/symbol(nat/symbol)

在不引起混淆时可简写成bit或nat；

(3)当信道给定后，p(y|x)就固定,所以C仅与

p(y|x)有关，而与p(x)无关；

(4)C是信道传输最大信息速率能力的度量。3.3信道容量及其计算第六十页，共126页。[例3-5]试计算二元对称信道的信道容量。可以看出：(1)信道容量C只是信道传递概率p的函数，而与信源概率分布ω无关；(2)求解信道容量的的核心问题是找到使信道达到信道容量的信源概率分布p(x)。解:已知二元对称信道第六十一页，共126页。3.4.1离散无噪信道的信道容量1无损无噪信道信道特点：输入和输出是一一对应的，其传递矩阵为单位矩阵。H(X/Y)=H(Y/X)=0即，损失熵=噪声熵=0→I(X;Y)=H(X)=H(Y)掌握第六十二页，共126页。1无损无噪信道无损无噪信道容量掌握第六十三页，共126页。2无损(有噪)信道信道矩阵特点：一个输入符号互不交叉的对应多个输出符号。其传递矩阵中每列元素有且仅有一个不为零。掌握第六十四页，共126页。2无损(有噪)信道

损失熵H(X/Y)=0

但噪声熵H(Y/X)≠0所以：I(X;Y)=H(X)<H(Y)掌握第六十五页，共126页。【例】无损信道

如图所示，信道输入符号集X={x1,x2,x3}，输出符号集Y={y1,y2,y3,y4,y5}，其信道转移概率矩阵记为，计算该信道的信道容量。

图无损信道x1x2x3y1y2y3y5y62/61/63/61/21/21y4掌握第六十六页，共126页。2.根据定义计算信道容量C

由极大离散熵定理知道，在信源消息等概分布时，熵值达到最大，即有1.平均互信息量I（X;Y）=H（X）-H（X︱Y），在无噪信道条件下，H（X︱Y）=0，则平均互信息量I（X;Y）=H（X）掌握第六十七页，共126页。3无噪有损信道(确定信道)特点：输入和输出是多对一的对应关系，但一个输入只对应一个输出。信道矩阵掌握第六十八页，共126页。3无噪有损信道(确定信道)H(Y|X)=0，H(X|Y)>0

所以：I(X;Y)=H(Y)<H(X)掌握第六十九页，共126页。70离散无噪信道的信道容量结论无损信道的C决定于信道的输入符号数r无噪信道的C只决定于信道的输出符号数s第七十页，共126页。3.4.2对称离散信道的信道容量

对称离散信道定义：离散无记忆信道中，若信道传递矩阵P中每一行都是由同一集合{p1,p2,…,ps}中的诸元素不同排列组成，每一列也都是由{q1,q2,…,qr}中的诸元素不同排列组成。例如：正例反例掌握第七十一页，共126页。证明:

离散对称信道的信道容量

若一离散对称信道具有r个输入符号，s个输出符号，则当输入为等概率分布时,信道容量C：式中，为信道矩阵中的任一行。掌握第七十二页，共126页。？第七十三页，共126页。因为：当输入等概率分布时:

在离散对称信道中输入等概率分布可以得到输出等概率分布。第七十四页，共126页。

由于信道是离散对称的，则每一列元素都是由相同的元素的不同排列构成的，所以每一列元素的和是相等的。设为A，则有：(j=1,2,…,s)可以得出：在离散对称信道中输入等概率分布可以得到输出等概率分布。即输入等概率时，可以得到信道的信道容量：第七十五页，共126页。[例3-6]一信道的转移概率矩阵为:求信道容量和达到容量时的输出概率。解：设信道矩阵每行元素为p1’,p2’,p3’，由于信道为离散对称信道，故当输入等概率时达到容量C，此时输出也等概率。所以:=0.126比特/符号达到容量时的输出概率：信道的输入符号是等概率分布时。掌握第七十六页，共126页。定义若输入/输出符号个数相同，都等于r，且信道矩阵为:则为强对称信道或均匀信道。这类信道中总的错误概率为p，对称地平均分配给r-1个输出符号。是对称离散信道的特例。掌握第七十七页，共126页。2强对称信道(均匀信道)的信道容量证明：讨论r=2时掌握第七十八页，共126页。定义：若信道矩阵按照信道输出集Y(列)可以将信道矩阵划分成n个子矩阵，每个子矩阵都是对称矩阵，则称此信道为准对称信道。3.4.3准对称信道的信道容量掌握第七十九页，共126页。例可见，输入对称信道也属于准对称信道。掌握第八十页，共126页。3.4.3准对称离散信道的信道容量其中：r是输入符号集中符号的个数，为准对称信道矩阵中的行元素。

设传递矩阵可以划分为n个互不相交的子集。Nk是第k个子矩阵Qk中行元素之和，Mk是第k个子矩阵Qk中列元素之和。掌握第八十一页，共126页。[例3-7]

一信道的转移概率矩阵如图，求信道容量和达到容量时的输出概率。解：设输出概率为q1,q2,q3,q4，因准对称信道当输入等概率时达到信道容量。可得：信道容量的计算有两种方法。方法一：利用信道容量的定义进行计算。掌握第八十二页，共126页。方法二：利用离散准对称信道信道容量公式计算。掌握第八十三页，共126页。掌握第八十四页，共126页。例3.8：可分成：行之和：N1=1-p-q+p=1-q；N2=q；列之和：M1=1-q-p+p=1-q，M2=2q掌握第八十五页，共126页。3.4.4一般离散信道的信道容量

根据离散信道信道容量的定义：在固定信道的条件下，对所有可能的输入分布P(x)，求平均互信息的最大值即为信道容量。因为信道容量为输入概率分布P(x)的上凸函数，且为输入概率分布的多元函数，可利用拉格朗日乘数法计算这个条件极值。引入辅助函数：了解第八十六页，共126页。解得：了解第八十七页，共126页。了解第八十八页，共126页。了解第八十九页，共126页。因此信道容量：

设令若假设使平均互信息达到信道容量的输入概率分布为P={p1,p2,…,pr}，并代入上述方程得：了解第九十页，共126页。定理3.3一般离散信道的平均互信息I(X;Y)达到信道容量的充要条件是:理解第九十一页，共126页。上述充要条件可以等价为:定理的证明略！见教材。理解第九十二页，共126页。可以利用该定理对一些特殊信道求得它的信道容量例3.9输入符号集为:{0,1,2}，输出符号集：{0,1}假设P(0)=P(2)=1/2，P(1)=0，则：理解第九十三页，共126页。所以：理解第九十四页，共126页。例3.10输入符号集为:{a1,a2,a3,a4,a5}，输出符号集：{b1,b2}假设P(a1)=P(a5)=1/2，P(a2)=P(a3)=P(a4)=0，则：信道矩阵掌握第九十五页，共126页。所以：掌握第九十六页，共126页。假设P(a1)=P(a2)=P(a4)=P(a5)=1/4P(a3)=0根据公式3.94P(a1)=P(a2)=P(a4)=P(a5)=1/4；P(a3)=0也是最佳分布解法二掌握第九十七页，共126页。对于一般信道的求解方法，就是求解方程组移项得：令则:若r=s，此方程有解，可以解出s个未知数，再根据得从而i=1,2,…r掌握第九十八页，共126页。例3.11可列方程组：求信道容量与最佳输入分布掌握第九十九页，共126页。解之得：掌握第一百页，共126页。3.6离散无记忆扩展信道及其信道容量

离散无记忆信道(DMC，DiscreteMemorylessChannel)，其传递概率满足：仍用[X，P(y/x)，Y]概率空间来描述。

不同的只是当信道传输消息序列时，输入随机序列与输出随机序列之间的传递概率等于对应时刻的随机变量的传递概率的乘积。理解第一百零一页，共126页。设离散无记忆信道的输入符号集A＝{a1，…，ar}，输出符号集B＝{b1

，…，bs}，信道矩阵为:第一百零二页，共126页。

无记忆信道的N次扩展信道的数学模型如图所示:而信道矩阵：其中：理解第一百零三页，共126页。例3.12求二元无记忆对称信道（BSC）的二次扩展信道。解：BSC的输入和输出变量X和Y的取值都是0或1，因此，二次扩展信道的输入符号集为A＝{00，01，10，11}，共有22＝4个符号，输出符号集为B＝{00，01，10，11}。由于是无记忆信道，可求得二次扩展信道的传递概率：信道矩阵：掌握第一百零四页，共126页。

根据平均互信息的定义，可得无记忆信道的N次扩展信道的平均互信息：理解第一百零五页，共126页。N次扩展信道的信道容量定理3.5

若信道输入序列为X=(X1X2…XN)，通过信道传输，接收到的序列为Y=(Y1Y2…YN)。(1)若信道是无记忆的，即信道传递概率满足则有：式中Xi，Yi是对应第i位的随机变量。(2)若信源是无记忆的，即满足则有：(3)若信源信道都无记忆则理解第一百零六页，共126页。证明：(1)信道输入和输出序列为X和Y，其取值了解第一百零七页，共126页。了解第一百