信息论与编码纠错第4章.ppt

信息论与编码 第4章 离散信道的信道容量 信息论与编码 内容提要 信道对于信息率的容纳并不是无限制的，它不仅与 物理信道本身的特性有关，还与信道输入信号的统计特 性有关，它有一个极限值，即信道容量，信道容量是有 关信道的一个很重要的物理量。这一章研究信道，研究 在信道中传输的每个符号所携带的信息量，并给出信道 容量的定义和计算方法。 信息论与编码 4.14.1信道容量的定义信道容量的定义 一信息传输率一信息传输率 平均互信息量 H ( X )：信道输入方关于发送符号集X中的某个消息的平均不确定性； H(X/Y)：信道输出方接收到符号集Y后对X发送消息仍存在的平均不 确定性； I(X;Y)：为通信过程中获得的信息量，也就是平均每个码元所携带的 信息量。 对于单符号传输情况，信息传输率为： 信息论与编码 二信道容量二信道容量 信息传输率是衡量通信质量的一个重要指标，由前面的定理知：对于 固定信道，总存在某种输入概率分布 p ( x ) ，使 I（X; Y）达到最大值， 定义这个最大值为信道容量信道容量，记为C。 使I（X; Y）达到信道容量的分布p(x)为最佳分布最佳分布。 信道容量C就是在保证可靠通信的前提下，信道所能容纳的最大 信息传输量。 对于固定信道，信道容量C是一个固定值；对于不同信道，C不同 ，信道容量C是信道转移概率p(y/x)的函数。 信息论与编码 4.2 4.2 离散无记忆信道容量的计算离散无记忆信道容量的计算 一离散无记忆信道的容量一离散无记忆信道的容量 如果信道输入的是N维序列XN，其概率分布为P（XN），输出的是N 维序列YN，则平均互信息量记为I（XN；YN），此时N维信道容量定义为 ： 下面一条定理给出了一维信道和N维信道的信道容量之间的关系。 定理：如果信道是离散无记忆（DMC）的，则CN NC， 其中C是同一信道传输单符号时的信道容量。 信息论与编码 证明：对于DMC信道，由定理2.4（若信道离散无记忆，则信道输入、输出 符号序列间的平均互信息量I（XN；YN）小于等于各单个符号间平均 互信息量的总和） 信息论与编码 （1）若输入的N个符号统计独立，即信源离散无记忆,根据定理2.3有： （信源无记忆，则信道输入、输出符号序列间的平均互信息量I（ XN；YN）大于等于各单个符号间平均互信息量的总和 ） （2）对每个i，输入分布p (xi) 可使I (Xi; Yi) 达到信道容量C，则： 则： 综上，在信源和信道都离散无记忆的情况下，有CNNC， 即定理中等号成立，这时N长序列的传输问题可归结为单符号传 输问题。 信息论与编码 二达到信道容量的充要条件二达到信道容量的充要条件 定理：使平均互信息量I（X; Y）达到信道容量C的充要条件是信道输入概 率分布 简记为p (X) = p (x1), p (x2), , p (xM)满足： 说明：定理只给出了使平均互信息量达到信道容量的充要条件，并没有给 出求信道容量及信道输入概率分布的显式，它只能用来求解一些特 殊情况的信道容量。 信息论与编码 下面介绍几种特殊信道信道容量的求解。 对于特殊信道，信道的输入X和输出Y之间有着确定的关系，一般有 三类：有噪无损信道、无噪确定信道和无噪无损信道。 【例】 有噪无损信道 无损信道的输入符号集元素个数小于输出符号 集的元素个数，信道的一个输入对应多个互不交叉 的输出，如图所示，信道输入符号集X =x1, x2, x3 ，输出符号集Y =y1, y2, y3, y4, y5 , y6，其信道转移 概率矩阵记为P，计算该信道的信道容量。 信息论与编码 【解】 1先考察平均互信息量I（X; Y）= H（X）- H（X/Y），在无噪信道条件 下，H（X/Y）= 0，则平均互信息量I（X; Y）= H（X）。 2根据定义计算信道容量C 从上式可看出，求信道容量C的问题转化为寻找某种分布p (x) 使信源 熵H（X）达到最大，由极大离散熵定理知道，在信源消息等概分布p(x1) = p(x2) = p(x3) = 1/3时，熵值达到最大，即有 信息论与编码 3. 根据平均互信息量I（X; Y）达到信道容量的充要条件式对C进行验证： 先根据计算出p(yj)（j =1，2，3，4，5，6） 信息论与编码 再计算出： 上面三式均满足平均互信息量达到信道容量C的充要条件，故C = log3。 信息论与编码 【例】 无噪确定信道 确定信道的输入符号集的元素个数大于输出符号集的个数，信道的 一个输出对应多某个个互不交叉的输入，这时输入符号以确定的概率1指 向某个输出符号，如图所示。信道输入符号集Xx1, x2, x3, x4, x5，输出 符号集Yy1, y2，其信道转移概率矩阵记为P，计算该信道的容量。 信息论与编码 【解】 1先考察平均互信息量I（X; Y）= H（Y）- H（Y/X），对于确定信道 ，H（Y / X）= 0，则平均互信息量I（X; Y）= H（Y） 2根据定义计算信道容量C 由于 ，由于信道转移概率是确定的，求使H ( Y ) 达到最大值的p ( x )的最佳分布就转化为求p ( y )的最佳分布。由极大离散 熵定理知，在p ( y )等概率分布时，H ( Y ) 达到最大，则 信息论与编码 3. 根据平均互信息量I（X; Y）达到信道容量的充要条件式对C进行验证： 上面的式子均满足平均互信息量达到信道容量C的充要条件，故C = log2。 信息论与编码 【例】 无噪无损信道 无损确定信道的输入符号集的元素个数等于输出符号集的个数，且信 道的输入符号以确定概率1指向某个固定的输出符号，如图所示，信道输入 符号集Xx1,x2,x3,x4,x5，输出符号集Y y1,y2,y3,y4,y5，其信道转移概率 矩阵为P，计算信道容量。 【解】 该信道的信道容量为： 信息论与编码 三几类特殊信道的信道容量三几类特殊信道的信道容量 1. 准对称信道 定义1：如果信道转移概率矩阵P中，每一行元素都是另一行相同元素的不 同排列，则称该信道关于行（输入）对称。 定义2：如果信道转移概率矩阵P中，每一列元素都是另一列相同元素的 不同排列，则称该信道关于列（输出）对称。 信息论与编码 定义3：如果信道转移概率矩阵P可按输出符号集Y分成几个子集（子矩阵 ），而每一子集关于行、列都对称，称此信道为准对称信道。 定义4：如果信道转移概率矩阵P可按输出符号集Y化分的子集（子矩 阵）只有一个，则该信道关于关于行、列都对称，称此信道为 对称信道。 信息论与编码 【定理一】 （准）对称信道的条件熵H(Y/X) 与信道输入消息的分布p(x)无关，且有H(Y/X)= H(Y/xi) 。 【定理二】 离散对称信道，若信源（信道输入 集合）等概率分布，则信宿（信道输出集合）也 是等概率分布的；反之亦然。 信息论与编码 【定理三】 实现DMC准对称信道的信道容量的信源分布为等概率分布。 证明：若信源含有K个消息，等概率分布，即p(xk)=1/K，k 1，2，.，K，则 准对称信道是关于行 对称，对任何k值， 上式中的和值相等， 与k无关，故I(xk； Y)是常数，根据前面 的定理，知平均互信 息量达到信道容量C 。 信息论与编码 【例】信道输入符号集X = x1, x2，输出符号集Y = y1, y2, y3, y4，给定信 道转移概率矩阵为P，求该信道的信道容量C。 这是一个准对称信道，根据定理，当X等概分布，p(x1)p(x2)1/2 时，信道容量 平均互信息量 信息论与编码 由 得 信息论与编码 可算得信道容量 信息论与编码 【例】BSC信道的转移概率如下，求信道容量： 该信道为一个对称信道，当输入等概率分布（此时输出也是等概率分 布），取得信道容量。 信息论与编码 时，信道的输入符号和输出符号是 一一对应的关系，在这种情况下，信道容 量Clog2，达到最大值。 时，信道的不确定性最大，在 这种情况下，信道容量C0，是一种 最差信道。 时，这是一种强噪声信道，但也是一种确定信道，在这种情况 下，可将判决取反，收到y1 判为x2 ， y2收到判为 x1 ，也能达到信道容 量的最大值Clog2。 信息论与编码 2. 信源只含两个消息 【例】信道输入符号集X = x1, x2 ，输出符号集Y = y1, y2, y3，给定信道转 移概率矩阵P，求信道容量C。 设使平均互信息量达到信道容量的信源分布为: p(x1) = ， p(x2) =1- 。 由 ，可算出 信息论与编码 平均互信息量 根据定义，求C的问题就转化为为何值时，I (X; Y ) 达到最大值。令 则信道容量 信息论与编码 3信道转移概率矩阵为非奇异方阵 非奇异方阵： 方阵行列式的值不为零，存在逆阵。 计算信道容量C按下面步骤进行： (1) 先验证信道转移概率矩阵P =p(yj/xi)是方阵，且矩阵P的行列式|P|0； (2) 计算出逆矩阵P-1= p-1 (yjxk)； (3) 计算出 (4) 根据式 ，计算出信道容量C； 信息论与编码 (5) 验证是否满足p(xi) 0， i =1, 2, , K。 u 先由式 计算出p(yk) k =1, 2, , K u 再由式 计算出p(xi) i =1, 2, , K 信息论与编码 【例】 已知信道转移概率矩阵P，求信道容量C。 （1）P矩阵的行列式： ，说明P是一个非奇异方阵。 （2）P的逆矩阵： （3）算出 信息论与编码 (4) 根据式 ，计算出信道容量C； （5）下面验证是否p (xi) 0，i =1, 2 先根据 算出 信息论与编码 再算得 信息论与编码 4.3 4.3 组合信道的容量组合信道的容量 考虑有两个信道 信道1： 信道2： 下面介绍信道三种不同组合情况下的信道容量。 信息论与编码 一独立并行信道一独立并行信道 在这种情况下，二个信道作为一个信道使用，传送符号XX，接收 符号YY，因为两个信道是独立的，故并行信道的转移概率为： 这相当于信道是离散无记忆的，根据定理2.4，对于离散无记忆信道 ，下式成立 对上面不等式两边取最大值，得 C C 1 + C2 说明在两信道并行使用的情况下，总容量小于等于两信道单独使 用时的信道容量之和。 推广到N个信道的并行组合，当N个信道并行独立使用时，记Ck (k = 1, 2, , N )为第k个信道的信道容量，C为组合信道的总容量，则有 等号成立的条件，都要求信源离散无记忆，即要求信道独立使用且输 入独立。 信息论与编码 二和信道二和信道 两个信道轮流使用，使用概率分别为p1，p2，且p1+p2 = 1，记概率分 布P =（p1，p2），和信道的平均互信息计算如下 信息论与编码 根据定义，有 求使上式取极大值的P, 令 对数以2为底，注意到p2 = 1- p1，得 记 （为待定常数） 信息论与编码 从上式中解出 （*） 代入条件p1+p2 = 1，得 式（*）中的p1，p2就是使平均互信息量I（p1，p2）达到最大的取值， 将其代入信道容量公式，得： 故信道容量为： 推广到N个信道轮流使用的情况, 当N个信道以不同概率轮流使用时， 记Ck (k = 1, 2, , N )为第k个信道的信道容量，C为组合信道的总容量，则 有 信息论与编码 三串行信道三串行信道 将两个信道级联，有X = Y，如图所示 。 串行信道的信道转移概率 用矩阵表示为： 串连信道的总信道 转移概率矩阵 第一个信道的转移 概率矩阵 第二个信道的转移 概率矩阵 信息论与编码 【例】给定两个信道，信道转移概率矩阵分别为： 串行信道的转移概率矩阵为： 串行级联信道的信道转移概率趋向于两个独立信道转移概率的均值 。这是很不利的，这种情况下出错概率增大，使信息能力减小。 求得串联信道的总转移概率矩阵，利用前面的方法可以求得信道的总容量。 若将N个转移概率相同的信道级联，当N 时，其总信道容量将趋于零。 信息论与编码 对于前面的结论，可用数据处理定理说明： 信道1：P1 = p (y/x) ；信道2：P2 = p (y/x ) ) 。 信道1和信道2是独立的，信道2的输出Z只与其输入Y及信道转移概率 P2 = p (y/x )有关，而与X无关。因此信道1和信道2串连就构成了一个马 尔可夫链，对于马尔可夫链有如下定理： 定理：若随即变量X、Y、Z组成一个马尔可夫链，如图所示，则有 I（X; Z） I（X; Y） I（X; Z） I（Y; Z） 数据处理定理：无论经过何种数据处理，都不会使信息量增加。 信息论与编码 证明： 则： I（X; Z） I（X; Y） 同理：I（X; Z） I（Y; Z） 若满足：H(X/Y) = H(X/Z)，即满足p(x/y) = p(x/z)，则等号成立 I（X; Z）= I（X; Y），说明这种情况下串行传输不会增加信息的损 失。 信息论与编码 【例】两个离散信道，将它们串行连接使用，计算总信道容量C。 【解】（1）先计算总信道的信道转移概率矩阵 信息论与编码 串联信道的总信道矩阵P等于第一级信道的信道矩阵P1，从而概率满足 对上式两边关于x求和，得 上式说明：无论信源如何分布，只要串行信道的总信