资源描述
网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding第三章信道容量赵永斌石家庄铁道大学信息科学与技术学院 2024年8月2日网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道及其容量3.1 信道容量的数学模型和分类3.2 单符号离散信源3.3 多符号离散信源3.4 连续信道3.5 信道编码定理网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding回顾信道信道是传输信息的媒质或通道。(输入信道输出)说明说明(1)信道输入是随机过程。(2)信道响应特性是条件概率P(输出值为y|输入值为x),又称为转移概率。(3)信道输出是随机过程,输出的概率分布可以由输入的概率分布和信道的响应特性得到。(全概率公式)(4)根据信道输入、信道响应特性、信道输出的情况,可将信道分类:离散信道(又称为数字信道);连续信道(又称为模拟信道);特殊的连续信道波形信道;恒参信道和随参信道;无记忆信道和有记忆信道等网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding回顾“离散离散”的含义是时间离散,事件离散。即:信道的输入、输出时刻是离散的,且输入随机变量和输出随机变量都是离散型的随机变量。l“无记忆无记忆”的含义是信道响应没有时间延迟,当时的输出只依赖于当时的输入。l“平稳平稳”的含义是信道在不同时刻的响应特性是相同的。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding无干扰无干扰信道信道有干扰有干扰信道信道3.1 信道容量的数学模型和分类信道的分类信道的分类有记忆信道有记忆信道无记忆信道无记忆信道单符号单符号 信道信道多符号多符号信道信道单用户信道单用户信道多用户信道多用户信道连续信道连续信道半离散信道半离散信道离散信道离散信道网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding62024/8/2信道分类定义定义:如果(1)信道的输入为随机变量序列X1,X2,X3,,其中每个随机变量Xu的事件集合都是0,1,K-1,(2)信道的输出为随机变量序列Y1,Y2,Y3,,其中每个随机变量Yu的事件集合都是0,1,J-1,则称该信道为离散信道离散信道。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding72024/8/2信道分类如果更有(3)P(Y1Y2YN)=(y1y2yN)|(X1X2XN)=(x1x2xN)=P(Y1=y1|X1=x1)P(Y2=y2|X2=x2)P(YN=yN|XN=xN),则称该信道为离散无记忆信道离散无记忆信道(DMC)。如果更有(4)对任意x0,1,K-1,y0,1,J-1,任意两个时刻u和v,还有P(Yu=y|Xu=x)=P(Yv=y|Xv=x),则称该信道为离散无记忆平稳信道离散无记忆平稳信道或恒参信道。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding 信道容量的数学模型噪声噪声介质缺陷介质缺陷XY信源信源编码编码信道信道编码器编码器调制器调制器(写入头)(写入头)信信 道道(存储介质)(存储介质)解调器解调器(写入头)(写入头)信道信道译码器译码器信源信源译码译码转移转移概率概率矩阵矩阵p(Y|X)XY网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道容量的数学模型P(Y/X)xY信道的数学模型:信道的数学模型:X P(Y/X)Y信道在某一时刻u的响应特性P(Yu=y|Xu=x);x0,1,K-1,y0,1,J-1,网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道容量的数学模型l二元对称信道BSC当N1时p(0/0)=p(1/1)=0.9,p(1/0)=p(0/1)=0.1 当N=2时,p(00/00)=p(11/11)=p(0/0)p(0/0)=0.9*0.9=0.81P(10/00)=p(01/00)=p(01/11)=p(10/11)=0.1*0.9=0.09P(11/00)=p(00/11)=0.1*0.1=0.010.90.900110.10.1网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding112024/8/2信道容量的数学模型(1)转移概率矩阵的每一行都是一个概率向量。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding12信道容量的数学模型(2)对任意y0,1,J-1,由全概率公式有网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.2 单单符号离散信符号离散信道的信道容量道的信道容量1 1 信道容量的定义信道容量的定义2 2 几种特殊离散信道的容量几种特殊离散信道的容量3 3 离散信道容量的一般计算方法离散信道容量的一般计算方法网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道容量的定义信道容量的定义I(X;Y)是概率向量q(x),x0,1,K-1和转移概率矩阵p(y|x),x0,1,K-1,y0,1,J-1的函数。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道容量的定义信道容量的定义设转移概率矩阵p(y|x),x0,1,K-1,y0,1,J-1(是信道的响应特性)确定,希望选择概率向量q(x),x0,1,K-1使I(X;Y)达到最大。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道容量信道容量信道单位时间传信道单位时间传输的最大信息量输的最大信息量网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding定义定义离散无记忆信道的信道容量信道容量定义为如下的C。达到信道容量的输入概率分布x,p(x),x0,1,K-1称为最佳输入分布最佳输入分布。其中信道容量信道容量表示了信道传送信息的最大能力,这个量在信息论表示了信道传送信息的最大能力,这个量在信息论研究中有重要意义。传送的信息量必须小于信道容量研究中有重要意义。传送的信息量必须小于信道容量C信道容量的定义信道容量的定义网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量定义:DMC的转移概率矩阵为 若P的任一行是第一行的置换,则称信道是关于输入为对称的关于输入为对称的。若P的任一列是第一列的置换,则称信道是关于输出为对称的关于输出为对称的。若信道是关于输入为对称的,又是关于输出为对称的,则称信道为对称信道。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量一、离散无噪信道一、离散无噪信道1、一一对应的无噪信道、一一对应的无噪信道an bna1 b1a2 b2网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Codinga1 b1a2 b2an-1 bn-1an bnX、Y一一对应一一对应 Cmax I(X;Y)log np(ai)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Codinga1 b1 b2 b32、具有扩展功能的无噪信道、具有扩展功能的无噪信道a2 b4 b5 b6a3 b7 b8 网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding此时,此时,H(X/Y)=0,H(Y/X)0,且且 H(X)H(Y)。此时,此时,C=max H(X)=log n p(ai)一个输入对应多个输出一个输入对应多个输出网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3、具有归并性的无噪信道、具有归并性的无噪信道x1 y1x2 x3 y2x4x5 y3C=max H(Y)=log mp(ai)H(X/Y)0,H(Y/X)=0多个输入变成一个输出多个输入变成一个输出网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding二、强对称二、强对称(均匀均匀)离散信道的信道容量离散信道的信道容量 p:总体错误概率:总体错误概率n n网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding相应的相应的网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding二进制均匀信道容量二进制均匀信道容量 C1H(p),其中 H(p)=-(1-p)log(1-p)+plogp)二进制均匀信道容量曲线二进制均匀信道容量曲线网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding三、三、对称对称离散信道的信道容量离散信道的信道容量矩阵中的每行都矩阵中的每行都 是集合是集合P=p1,p2,pn中的诸元素的不同排列,称中的诸元素的不同排列,称矩阵的矩阵的行是可排列行是可排列的。的。矩阵中的每列都是集合矩阵中的每列都是集合Q=q1,q2,qm中的诸元素的不同排列,称矩中的诸元素的不同排列,称矩阵的阵的列是可排列列是可排列的。的。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding如果矩阵的行和列都是可排列的,如果矩阵的行和列都是可排列的,称矩阵是可排列的。称矩阵是可排列的。如果一个信道矩阵具有可排列性,如果一个信道矩阵具有可排列性,则它所表示的信道称为则它所表示的信道称为对称信道中,当对称信道中,当nm,Q是是P的子集;当的子集;当n=m时,时,P=Q。对称信道对称信道网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding练习:判断下列矩阵表示的信道是否是对称信道练习:判断下列矩阵表示的信道是否是对称信道网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding相应的相应的对称离散信道的信道容量网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信道的转移概率矩阵为:例网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding强对称信道与对称信道比较:强对称信道与对称信道比较:强对称强对称 对称对称 n=m n与与m未必相等未必相等 矩阵对称矩阵对称 矩阵未必对称矩阵未必对称 P=Q P与与Q未必相等未必相等行之和,列之和均为行之和,列之和均为1行之和为行之和为1网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding四、四、准对称信道离散信道准对称信道离散信道的信道容量的信道容量若信道矩阵的行是可排列的,但列不可若信道矩阵的行是可排列的,但列不可排列,如果把列分成若干个不相交的子集,排列,如果把列分成若干个不相交的子集,且由且由n n行和各子集的诸列构成的各个子矩阵行和各子集的诸列构成的各个子矩阵都是可排列的,则称相应的信道为都是可排列的,则称相应的信道为准对称准对称信道信道。例如下面的矩阵:。例如下面的矩阵:网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding假设此时将矩阵的列分为假设此时将矩阵的列分为S个子集,每个个子集,每个子集的元素个数分别是子集的元素个数分别是m1,m2,ms。准对称信道离散信道准对称信道离散信道的信道容量的信道容量网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding准对称信道离散信道准对称信道离散信道的信道容量的信道容量网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.2.3 离散信道容量的一般计算方法离散信道容量的一般计算方法 对一般离散信道而言,求信道容量,就是在固定信对一般离散信道而言,求信道容量,就是在固定信道的条件下,对所有可能的输入概率分布道的条件下,对所有可能的输入概率分布p(xi),求平均求平均互信息的极大值。采用互信息的极大值。采用拉各朗日乘子法拉各朗日乘子法来计算。来计算。原因?原因?网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding(1)两边乘两边乘p(ai),并求和,则有:,并求和,则有:网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding(2)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding将(将(2 2)代入()代入(1 1),则有:),则有:(3)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding(4)则(则(3)变为:)变为:网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding(5)(6)(7)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding(8)(9)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding离散信道容量的一般计算方法离散信道容量的一般计算方法l总结总结C的求法,过程如下:的求法,过程如下:1.求求j2.求求C3.求求p(bj)4.求求p(ai)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding例例:信道矩阵如下,求:信道矩阵如下,求C C。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding1网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding23网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding4网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding结果结果网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.3 多多符号离散信符号离散信道道3.3.1 多符号离散信道的数学模型3.3.2 离散无记忆信道的N次扩展信道和独立并联信道的信道容量网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding多符号离散信道多符号离散信道 多符号信源通过离散信道传输形多符号信源通过离散信道传输形成多符号离散信道。成多符号离散信道。3.3.1 多符号离散信道的数学模型网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.3.1 多符号离散信道的数学模型多符号离散信道的数学模型输入输入输出输出网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.3.2 离散无记忆信道的N次扩展信道 独立并联信道的信道容量无记忆:无记忆:YK仅与仅与XK有关有关网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding1YNY网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding(a)=-NKKKNKKXYHYHYXI11)/()();(=NKKNYHYYYH121)().(=-=NKKKNXYHYYYH121)/().(rr=-=NKKKXYHYHYXI1)/()();(rrr网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding652024/8/2(积信道积信道)定义定义信道的输入事件为全体(x,u),共有KN个输入事件;信道的输出事件为全体(y,v),共有JM个输出事件;转移概率矩阵为p(y,v)|(x,u)(KN)(JM),其中p(y,v)|(x,u)=p1(y|x)p2(v|u)。则称该信道为信道1与信道2的积信道积信道。(又称该信道为信道1与信道2的独立并行信道)(在物理上,积信道是两个信道的并行使用)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding662024/8/2积信道积信道积信道积信道的信道容量为C=C1+C2,最佳输入分布为(x,u),q(x,u),其中q(x,u)=q1(x)q2(u)。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding和信道定义定义信道的输入事件为全体xu,其中x与u不相交;共有K+N个输入事件;信道的输出事件为全体yv,其中y与v不相交;共有J+M个输出事件;信道的转移概率矩阵为网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding和信道则称该信道为信道1与信道2的和信道和信道(或称并信道)。任一单位时间可随机地选用一个信道,而不能同时选用两个信道。若选用信道1的概率为P1,选用信道2的概率为P2,则P1+P2=1。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding和信道容量网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.4 连续信道连续信道P(Y/X)连续信道的数学模型网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding加性连续信道加性连续信道l可加噪声信道:设平稳的(恒参的)时间离可加噪声信道:设平稳的(恒参的)时间离散的无记忆连续信道为:输入随机变量为散的无记忆连续信道为:输入随机变量为X;噪声随机变量为;噪声随机变量为N;X与与N相互独立;输相互独立;输出随机变量为出随机变量为Y=X+N。则称该信道为。则称该信道为可加可加噪声信道噪声信道。NY=X+Np(y/x)=p(n)X网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding 利用坐标变换原理,可证p(y/x)=p(n)X,N相互独立。网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding假定N是均值为0,方差为的高斯变量噪噪声声功功率率网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding输入平输入平均功率均功率输出平输出平均功率均功率对于高斯加性信道网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding信噪功率比网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding香农公式香农公式(bit/s)网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding3.5 信道编码定理信道编码定理 若一离散平稳无记忆信道,其容量为C,输入序列长度为L,只要待传送的信息率RC,RC,任何编码的必大于0,当网络网络网络网络工程系工程系工程系工程系-Information Theory and CodingInformation Theory and Coding总结1 信道的数学模型2 信道的分类3 离散信道中强对称、对称、准对称和一般信道的信道容量计算4 连续信道的信道容量计算 5 信道编码定理
展开阅读全文