第三章 信道容量

nullnull苗立刚 ligangmiao@yahoo.com.cn 实验楼417 电话8048018东北大学秦皇岛分校自动化工程系 2009年3月第三章 信道容量信息论与编码null第三章 信道容量3.1 单符号离散信道的数学模型（重点） 3.2 单符号离散信道的信道容量（重点） 3.3 多符号离散信道的信道容量（重点） 3.4 网络信息理论（自学） 3.5 连续信道（自学） 3.6 信道编码定理（重点） 本章主要讨论的问题：null3.1单符号离散信道的数学模型 单符号离散信道的数学模型及其分类 信道的数学模型 X —— 输入事件的集合, 概率空间为[X P] Y —— 输出事件的集合, 概率空间为[Y P] null 信道的分类 1、根据信道用户的多少，分为： 单用户信道---输入、输出均只有一个 多用户信道---输入、输出有多个 2、根据输入输出信号的特点，分为： 离散信道---输入、输出随机变量均离散取值 连续信道---输入、输出随机变量均连续取值 半离散(连续)信道--- 一为离散，另一为连续 3、根据输入、输出随机变量的个数 单符号信道---输入、输出均用随机变量表示 多符号信道---输入、输出用随机矢量表示3.1单符号离散信道的数学模型null4、根据信道上有无噪声(干扰) ： 有噪(扰)信道 无噪(扰)信道 5、根据信道有无记忆特性 无记忆信道---输出仅与当前输入有关，与先前输入无关 有记忆信道---输出不仅与当前输入有关，还与先前输入有关3.1单符号离散信道的数学模型null 离散信道的数学模型 信道容量的定义设离散信道的输入空间为输出空间为概率分布为概率分布为3.2单符号离散信道的信道容量并有条件概率 条件概率被称为信道的传递概率或转移概率。 X Ynull将所有转移概率以矩阵方式列出，得：其中该矩阵完全描述了信道在干扰作用下的统计特性，称为信道矩阵(n行m列)。3.2单符号离散信道的信道容量null反信道矩阵（m行n列）其中3.2单符号离散信道的信道容量null3.2单符号离散信道的信道容量（1）联合概率其中称为前向概率，描述信道的噪声特性称为后向概率，有时也把 称为先验概率 称为后验概率（2）输出符号的概率（3）后验概率表明输出端收到任一符号，必定是输入端某一符号输入所致 离散信道中的概率关系null3.2单符号离散信道的信道容量 信道容量的定义含义： ①给定信道时，对应各种信源分布，求取的最大平均互信息； ②给定信道时，理论上能传输的最大信息量，表征信道传送信息的最大能力； 信道容量定义为平均互信息的最大值： 平均互信息I(X;Y)是信源分布p(x)的上凸函数，是信道传递概率p(y|x)的下凸函数。对于一个固定的信道，总存在一种信源，使传输每个符号平均获得的信息量I(X;Y)最大。 信道容量C只与信道的统计特性p(y|x)有关，而与信源的分布p(x)无关。它是信道的特征参数，反应的是信道的最大的信息传输能力。null信息传输速率Rt: 单位时间内平均传输的信息量信息传输率R: 信道中平均每个符号所能传送的信息量。由于平均互信息I(X;Y)的含义是接收到符号Y后，平均每个符号获得的关于X的信息量，因此信道信息传输率就是平均互信息。最大信息传输速率Ct: 单位时间内平均传输的最大信息量3.2单符号离散信道的信道容量null例：对于二元对称信道如果信源分布X={p,1-p}，则 3.2单符号离散信道的信道容量信道容量为： null3.2单符号离散信道的信道容量 无损确定信道：一对一（n=m）信道矩阵：单位阵损失熵 H(X/Y) = 0 噪声熵 H(Y/X) = 0 I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X) H(X) = H(Y) 离散无噪信道：输出Y和输入X有确定关系（广义）a1 a2 a3 anb1 b2 b3 bn… … …null3.2单符号离散信道的信道容量 无损信道：一对多（n＜m）具有扩展性的无噪信道信道矩阵：每列只有一个非0元素，不全是0、1信道疑义度（损失熵） H(X/Y)=0 噪声熵 H(Y/X)>0 I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X) H(X)＜H(Y) 思考：p(x)应该怎样取值？a1 a2 a3b1 b2 b3 b4 b5null3.2单符号离散信道的信道容量 确定信道：多对一（n>m）具有归并性的无噪信道信道矩阵：每行只有一个元素“1”，其它全是0损失熵 H(X/Y) > 0 噪声熵 H(Y/X) = 0 I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(Y) H(X) ＞ H(Y)思考：p(x)应该怎样取值？null信道特点 信道输入、输出均为n元 每符号正确传输概率均为 其他符号错误传输概率为p/(n-1) 矩阵特点 (1)n×n阶对称阵 (2)每行和为1,每列和为1 强对称离散信道(均匀信道)3.2单符号离散信道的信道容量null3.2单符号离散信道的信道容量 信道容量 可以看出，当输出等概分布时，即H(Y)=log2n时达到信道容量。null3.2单符号离散信道的信道容量 那么，在什么样的信源输入情况下，信道输出能等概分布呢？可以证明，输入等概分布时，离散对称信道的输出也为等概分布[结论]对强对称信道，输入等概→输出等概，可达到Cnull3.2单符号离散信道的信道容量二进制对称信道(n=2)null3.2单符号离散信道的信道容量行可排列——矩阵每行各元素都来自同一集合Q Q∈{q1,q2,…,qm}(排列可不同) 列可排列——矩阵每列各元素都来自同一集合P P∈{p1,p2,…,pn}(排列可不同) 矩阵可排列——矩阵的行、列皆可排列 对称信道——信道矩阵可排列 离散对称信道 (1)m=n 时，Q、P为同一集合 m≠n时，Q、P中，一个必为另一个的子集 (2)输入等概→输出等概null3.2单符号离散信道的信道容量 离散输入对称信道 如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，则称此类信道为离散输入对称信道。 离散输出对称信道 如果一个离散无记忆信道的信道矩阵中，每一列都是其他列的同一组元素的不同排列，则称此类信道为离散输出对称信道。null3.2单符号离散信道的信道容量 离散对称信道 如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，并且每一列都是其他列的同一组元素的不同排列，则称此类信道为离散对称信道。null 离散对称信道的信道容量 定理：如果一个离散对称信道具有n个输入符号，m个输出符 号，则当输入为等概率分布时，达到信道容量C。可以看出，当输出等概分布时，即H(Y)=log2m时达到信道容量。 由于对称信道的特点，输入等概率分布输出等概率分布。3.2单符号离散信道的信道容量对于行可排列情况，Hmi与i 无关null准对称离散信道 信道矩阵的行可排列，列不可排列 但把该矩阵在水平方向上分割， 则各子矩阵皆具可排列性 [例] [关键]——H(Y)最大(改变p(xi)时)3.2单符号离散信道的信道容量思考：p(xi)应该怎样取值？P79null 离散信道容量的一般计算 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 (自学)—P813.2单符号离散信道的信道容量 对于固定的信道，平均互信息I(X;Y)是信源概率分布p(xi)的上凸函数,所以极大值一定存在。 I(X;Y)是n个变量p(ai)(i=1,2,…,n)的多元函数，并满足 所以可以用拉格朗日乘子法计算条件极值:其中， 为拉格朗日乘子null3.2单符号离散信道的信道容量解方程组可得一般信道容量C。 由I(X;Y) = H(Y) - H(Y|X)H(Y)H(Y|X)nullI(X;Y)最大值3.2单符号离散信道的信道容量令 则若m=n,则可求解null3.2单符号离散信道的信道容量一般离散信道容量的求解步骤：(1) (2) (3) (4)需要确认所有的 ，所求的C才存在。null3.2单符号离散信道的信道容量例：可列方程组：null解之得：3.2单符号离散信道的信道容量null3.3多符号离散信道的信道容量 多符号离散信道的数学模型 多符号离散信源X=X1X2… Xk ….XN在N个不同时刻分别通过单符号离散信道 {X P(Y/X) Y}，在输出端出现Y=Y1Y2… Yk ….YN，形成一个新的信道，此即多符号离散信道。由于新信道相当于单符号离散信道在N个不同的时刻连续运用了N次，也称为单符号离散信道的N次扩展信道 基本概念null3.3多符号离散信道的信道容量Xk取值: a1,a2,…,an, 则X共有nN种 , i=1～nN Yk取值: b1,b2,…,bm, 则Y共有mN种 , j=1～mN 多符号离散信道的数学模型null 信道矩阵3.3多符号离散信道的信道容量每行元素之和等于1null3.3多符号离散信道的信道容量 离散无记忆扩展信道的信道容量 把多符号离散信道理解成单符号离散信道在每一个单位时间 传递一个随机变量的时候，需要考虑k时刻的输出变量Yk与时刻k 之前的输入变量X1X2…Xk-1和输出变量Y1Y2…Yk-1之间有无依赖关系。单符号离散信道的N次扩展信道的数学模型null 若多符号离散信道的转移概率满足 则称之为离散无记忆信道的N次扩展信道 [解释]扩展信道的转移概率 =各时刻单符号信道转移概率的连乘 无记忆性——k时刻输出Yk只与k 时刻输入Xk有关, 与k时刻之前输入X1X2… Xk-1无关 无预感性——k时刻之前输出Y1Y2… Yk-1只与k时刻之前输 入X1X2… Xk-1有关，与Xk无关 [结论] 离散无记忆N次扩展信道——无记忆，无预感3.3多符号离散信道的信道容量null互信息和信道容量 3.3多符号离散信道的信道容量离散无记忆N次扩展信道两端的平均互信息I(X;Y)=H(Y) - H(Y|X) 由于信道无记忆 当第k个随机变量Xk单独通过单符号离散信道时，在输出端得到的关于Xk的平均互信息量null相减可得3.3多符号离散信道的信道容量 离散无记忆信道的N次扩展信道的平均互信息，不大于N个随机变量X1X2…XN单独通过信道{X P(Y|X) Y}的平均互信息之和。 当且仅当信源X=X1X2…XN无记忆,或信源X是离散无记忆信源X的N次扩展信源时，等号成立。 原因： 离散无记忆信道的N次扩展信道，当输入端的N个输入随机变量统计独立时，信道的总平均互信息等于这N个变量单独通过信道的平均互信息之和。null3.3多符号离散信道的信道容量 对于离散无记忆信源的N次扩展信源 通过同一个离散无记忆信道信道 { X P(Y|X) Y } 在信道输出端，随机变量序列Y=Y1Y2…YN中的随机变量Yk 离散无记忆信道的N次扩展信道，如果信源也是离散无记忆信源的N次扩展信源，则信道总的平均互信息量是单符号离散无记忆信道的平均互信息量的N倍。null独立并联信道 含义 信道输入序列的各随机变量取值于不同符号集 信道输出序列的各随机变量亦取值于不同符号集 也称为独立并列信道、独立平行信道或积信道 3.3多符号离散信道的信道容量信道容量当N个输入随机变量之间统计独立，并且每个输入随机变量Xk 的概率分布为达到各自信道容量Ck的最佳分布时，CN达到最大值N个独立并联信道的信道容量等于各个信道容量之和null信道编码定理 对离散平稳无记忆信道，其信道容量为C，输入序列长度为L。只要实际信息率RC，则对任何编码，Pe必大于零。 [说明] ①前者为正定理，后者为逆定理 ②给出了信息传输率的极限 只要RC，必为有失真传输 ③存在性定理3.6信道编码定理null作业： 3.1 (P99); 3.2 (P99)； 3.11 (P100); 3.14 (P101); 3.15 (p101);3.3多符号离散信道的信道容量