《信道编码定理》PPT课件.ppt

第六章 信道编码定理 信息论研究编码的主要内容 回答如下问题 为什么要编码 什么样的码是好码 不能回答的问题 怎样进行编码 怎样进行译码 信息论研究编码的方法 将问题分而治之有效性 认为可靠性已满足可靠性 认为有效性已满足将信源与信道编码分别研究信源编码 解决有效性问题信道编码 解决可靠性问题 编码 信源 信源编码 信道编码 信道 信宿 有效性 可靠性问题分别解决 信息流 H X I X Y 可以获得的信息量 所得信息能否可靠地确定信道输入 信息传输的有效性指标 给定特性的信道最大可达的信息传输率 信道传输信息的能力度量 信道噪声 实际通信中人们对传输要求什么 传输信息无差错 传输要可靠 传输信息量大 传输要有效 传输的信息是否无误 可靠性 6 1 问题引出与定理描述 提出的与信道传输可靠性有关的问题 如何能使信息传输后发生的错误最少 错误概率与那些因素有关 有无办法控制 能控制到什么程度 无误传输可达的最大信息率是多少 信道编码定理 具体信道编码技术 错误概率与译码准则 编码方法 1 错误概率与译码规则错误概率Pe与什么有关 信道的统计特性译码规则译码规则的选择依据最大后验概率准则 理想最大似然准则 实用最小距离准则 实用 编码 信道传输 错误概率与译码准则 编码方法 2 调制 广义的信道编码 已解决有效性表示问题 C A B 2 1 3 消息集合 编码集合 C A B 2 1 4 3 5 P A2 P A1 P A3 P A4 P A5 发送波形集合 接收波形集合 错误概率与译码准则 编码方法 3信道译码 An 1 2 4 3 w4 w3 w1 w2 x x x An是接收空间w1 w2 是发送的码字围绕每个码字有一个译码域 i如果接收的码字在 i中 就认为发送的是码字wi发生错误 正确译码 不知如何译码 译码错误 有时接收码字会被映射到错误的 i 进而被译成错误的wi 一般 An中存在一些不属于任何 i的区域 错误概率与译码准则 编码方法 4 问题 在输入和信道特性给定的条件下 差错概率将取决于接收矢量空间按什么样的划分准则进行划分划分接收矢量空间的准则 译码器的译码准则 译码准则一 最小错误概率准则 最大后验概率准则 特点 优点 理想缺点 1 后验概率不易得到2 后验概率依赖于输入分布 错误概率与译码准则 编码方法 5 错误概率与译码准则 编码方法 6 译码准则二 最大似然译码准则最大后验概率译码准则 最大似然译码准则输入等概时 二者是一致的 错误概率与译码准则 编码方法 7 译码准则三 最小距离译码准则最小距离译码准则 最大似然译码准则在二进制对称信道中 二者是一致的 选择好的译码规则可以降低错误概率FANO不等式说明 无论什么译码规则 对减少误码率的作用有限 误码率受信道特性的影响严重 增加码空间M 并选择适当的编码方法 可以既使错误概率降低 又使码率保持较大 适当的编码方法就是适应信道特性的方法即 信道编码 错误概率与译码准则 编码方法 8 6 1 问题引出与定理描述 问题 在有噪信道中 使平均误码率Pe尽可能小的情况下 可达到的信息传输率是多少 几乎无误 答案 信道容量C 6 1 问题引出与定理描述 信道编码定理 设R是信息传输的速率 C是离散无记忆信道的信道容量 0是任意小的数 则只要R C就总存在码字长为N 码字数为M 2NR的分组码使译码的平均差错概率Pe 信源 信道 信宿 通过不可靠的信道可以实现可靠的信息传输 只要系统设计的信息传输率在信道的信息传输能力之内 就可以实现可靠传输 实现有效且可靠传输的途径是信道编码 6 1 问题引出与定理描述 编码器 解码器 6 2 信道编码的作用及实质 什么是信道编码 通信系统模型信道编码 从消息到信道波形或矢量的映射希望通信系统与信道统计特性相匹配的编码 复接 代数编码 调制 成形滤波 扩频 上下变频等等都属于广义的信道编码范畴注意 信道译码可以不是离散信道译码 只有当解调为硬判决输出时才是离散信道和离散信道译码 6 2 信道编码的作用及实质 什么是信道编码 信道编码的作用 在资源 可靠性和传信量之间选择一个好的工作点 有时还要考虑延时 资源指的提供信息传输所付出的代价包括频率 时间 空间 功率等等 但不包括实现复杂度一个好的编码就是要充分利用资源 传递尽可能多的信息 6 2 信道编码的作用及实质 信道编码的作用 给定资源和可靠性要求 通过信道编码尽量提高传输速率 例 多电平编码 给定对信息传输的速率和可靠性要求 通过信道编码尽量减少资源开销 例 扰乱编码 给定资源和传输速率 通过编码提高可靠性 例 检 纠错编码 6 2 信道编码的作用及实质 信道编码的三种情形 利用冗余降低差错概率 在信息码中增加一定数量的监督码元 使它们满足一定的约束关系 在信道传输中如果码字受干扰而在接收端出现一些偏差 破坏了其约束关系 收方通过检验这种约束关系来把错误识别或校正出来 从而保证通信的可靠性 差控码将所有可能的输入信息 消息 映射到信道符号 波形 空间的点 而这个点的集合要小于 包含于 全信道空间中点的集合 通过增加冗余度 即将信息空间映射到更大的信道波形空间 以提高不同码字波形间的差异程度 从而获得增益 6 2 信道编码的作用及实质 信道编码的实质 6 2 信道编码的作用及实质 信道编码的实质 匹配信道特性 抗白噪声 优秀的调制 信道编码方案 扩频方式等 抗衰落和多径干扰 功控抗慢衰落 空间分集抗平滑瑞利 空间选择 衰落 Rake接收机及自适应均衡抗频率选择性 交织编码抗时间选择性衰落等 抗多址干扰与远近效应 正交码型设计 功率控制 多用户检测 扰乱编码进行能量分集 智能天线等 6 2 信道编码的作用及实质 差错控制编码的基本原理 如用三位二进制编码来代表八个字母000A001B010C011D100E101F110G111H R log8 3 1bit 二进制符号 不管哪一位发生错误 都会使传输字母错误 6 2 信道编码的作用及实质 差错控制编码的基本原理 如用三位二进制编码传四个字母000A011B101C110D R log4 3 0 67bit 二进制符号 发生一位错误 准用码字将变成禁用码字 接收端就能知道出错 但是不能纠错 禁用码字 001010100111 6 2 信道编码的作用及实质 差错控制编码的基本原理 如用三位二进制编码传二个字母000A111B R log2 3 0 33bit 二进制符号 可以检查出2位错误 可以纠正一位错误 可以同时检查一位错误 并纠正一位错误 禁用码字 001010011100101110 6 2 信道编码的作用及实质信道编码的基本分类 按码的结构分 线性码线性分组码 群码 卷积码 线性树码 非线性码按抗干扰模式分抗随机差错码抗突发差错码按对错误的处理方式分检错码 应用于ARQ 反馈重发 方式 纠错码 应用于FEC 前向纠错 方式 检纠错码 应用于HEC 混合纠错 方式 6 3 信道编码定理的证明及其物理意义 信道编码定理问题 在有噪信道中 使平均误码率Pe尽可能小的情况下 可达到的信息传输率是多少 答案 信道容量C信道编码定理的证明证明思路随机编码方法联合典型序列 信道编码定理 设R是信息传输的速率 C是离散无记忆信道的信道容量 0是任意小的数 则只要R C就总存在码字长为N 码字数为M 2NR的分组码使译码的平均差错概率Pe 6 3 信道编码定理的证明及其物理意义 信道编码定理的证明思路 通常思路 构造一个理想的好码 定义一种译码准则 计算该好码经过译码后的误码率问题 构建极其复杂且无具体方法 N值很大时 误码率计算困难香农采取的方法 用随机编码方法得到所有可能码的集合在其中随机选择一个码作为信道码利用联合典型序列译码利用大数定理计算在集合平均意义上的该码性能 6 3 信道编码定理的证明及其物理意义 联合 典型序列 典型序列 信源输出的随机序列 奠定了信源编码的基础联合 典型序列 两个随机序列的自然扩展 是信道编码的基础联合 典型序列定义 联合AEP定理定理解释 6 3 信道编码定理的证明及其物理意义 联合 典型序列定义 设是长为N的随机序列对 则在这些随机序列对中满足下列条件的序列对被称为联合典型序列 同理可得 式中 是任意小的数 联合典型序列的全体构成联合典型序列集 记做G 按此定义不难得到随机序列对取某联合典型序列的概率满足 6 3 信道编码定理的证明及其物理意义 联合AEP定理 设随机序列对的 则对任意小的数 0 我们总能找到足够大的N使全体序列对的集合能被分成满足下述条件的集合G及其补集Gc 1 2 3 设是相互独立的随机序列对 但它与有相同的边缘分布 即 则 6 3 信道编码定理的证明及其物理意义 联合AEP定理的解释 两个随机变量情况下 序列Xn Yn及其联合序列XnYn都具有AEP特性联合典型序列对是高概率序列对联合典型序列对是一些密切关联的序列对一般与X对应的Y可能是Y空间的任一个 该定理说明 随N的增大 对应X的Y只能是 X Y 典型序列对的Y 取其他Y的概率 0联合典型序列数目为2NH XY 典型X 典型Y随机组合的空间为2N H X H Y 联合典型序列占其中约1 2NI X Y 只是很小的一部分故 当X的数目 2NI X Y 时 可使Pe 0给出一种译码方法 译码时 取与接收矢量联合典型的码字作为输出 这种译码方法可以保证得到很低的误码率 6 3 信道编码定理的证明及其物理意义 6 3 信道编码定理的证明及其物理意义 物理意义 通过编码可以实现有噪信道上可靠的信息传输有噪信道可靠传输的信息率的上界是信道容量C在码长及发送信息速率一定时 可以通过增大信道容量 使错误概率减小在信道容量及发送信息速率一定时 可以通过增加码长 使错误概率下降 随机编码方法 对每一个消息m m 0 1 M 1 编码为xm xm1xm2 xmN 其中 xmi i 1 2 N 是按照输入字母的概率随机选取 从而得到全部M 2NR个码字 组成码矢量C x0 x2 xM 1 随机编码方法产生某一特定码矢量的概率P C 是 6 3 信道编码定理的证明及其物理意义 6 3 信道编码定理的证明及其物理意义 所有码的总数 有了这样的码集以后 香农不是去计算某一特定好码的性能 而是设法计算这些码的平均性能 码字数只占全部可能序列的一小部分 设码元数为r 则所有可能产生的码的总数为 例 证明设信道容量所对应的信道输入符号的最佳分布为p x 以此概率分布为基准 按照随机编码方法编码得到码矢量C 假设输入消息是等概率分布的 第i个码字出错的概率为pe i 则码矢量C的译码平均错误概率为 其中 pi为码矢量中第i个码字对应的概率 则在码矢量集合 C 上对pe C 求数学期望 得到平均错误概率为 对于随机编码方法 不同的输入消息符号所产生对应码字的方法是相同的 所以在码矢量集合上进行平均后得到的码错误数学期望 与i的取值无关 为表示方便起见 令 将其代入平均错误概率表示式 并考虑到M 2NR 于是得到 为了计算 设y表示发送码字ci时信道输出端接收的序列 令事件Ei表示ci与接收序列y构成的联合典型序列 于是有 同时令事件E1c表示发送第一个码字与接收序列不构成联合典型序列 即 根据联合典型序列的译码方法 当y不与码字c1构成联合典型序列 或者是与c1以外的其他码字构成联合典型序列时 错误译码就出现了 因此 其中 表示事件和 根据概率论可知 由于接收序列y对应于输入码字c1 与其他码字之间相互独立 因此根据联合渐近等同分割定理的性质 1 3 即p E1c 和p Ei 2 n I X Y 3 得到 由于随机编码是按照信道输入的最佳分布p x 进行的 因此有C I X Y 在上述证明最后一步用到该公式 如果R C 3 则当n足够大时 有 于是得到 PE 2 所以 在码字足够长时 随机编码码集合中的平均错误译码概率PE 2 在这些码中 至少有一个码的平均错误译码概率不大于2 令 2 即证明了该定理 信道编码定理证明的几点说明特点 香农只是证明了码的存在性 未给出构造方法实现困难随机编码所得的码集很大 通过搜索得到好码的方法实际上很难实现 即使找到 码字也是毫无结构的 只能采用查表译码方法 当N很大时 码表的存储量也很难接受香农采取的证明方法评价 不很严格 不是最优 但便于理论分析随机编码方法在后来严格的证明中一直被采用 6 3 信道编码定理的证明及其物理意义 无失真信源编码定理的物理意义 2 无失真信源编码定理 香农第一定理 又称为无噪信道编码定理无噪时 I X Y H X C maxI X Y 信道输入为最佳分布时达到 以对称信道为例 此时C logMK为平均码长 R H X K第一定理 K H X logMR logM R C将无失真编码过程看成经过一个信道 只有满足K H X logM 才能满足第二定理的无误传输条件R C 即编码过程是无失真的 香农理论极限 R C