《信道编码定理》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是任意小的数，则只要RC就总存在码字长为N，码字数为M=2NR的分组码使译码的平均差错概率Pe。,信源,信道,信宿,通过不可靠的信道可以实现可靠的信息传输,只要系统设计的信息传输率在信道的信 息传输能力之内，就可以实现可靠传输。,实现有效且可靠传输的途径是信道编码。,6.1:问题引出与定理描述,编 码 器,解 码 器,6.2:信道编码的作用及实质什么是信道编码？,通信系统模型 信道编码：从消息到信道波形或矢量的映射 希望通信系统与信道统计特性相匹配的编码,复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于广义的信道编码范畴 注意：信道译码可以不是离散信道译码。只有当解调为 硬判决输出时才是离散信道和离散信道译码,6.2:信道编码的作用及实质 什么是信道编码？,信道编码的作用： 在资源、可靠性和传信量之间选择一个好的工作点（有时还要考虑延时）。 资源指的提供信息传输所付出的代价 包括频率、时间、空间、功率等等。但不包括实现复杂度 一个好的编码就是要充分利用资源，传递尽可能多的信息,6.2:信道编码的作用及实质 信道编码的作用,给定资源和可靠性要求，通过信道编码尽量提高传输速率（例：多电平编码） 给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销（例：扰乱编码） 给定资源和传输速率，通过编码提高可靠性（例：检、纠错编码）,6.2:信道编码的作用及实质 信道编码的三种情形,利用冗余降低差错概率 在信息码中增加一定数量的监督码元，使它们满足一定的约束关系。在信道传输中如果码字受干扰而在接收端出现一些偏差，破坏了其约束关系，收方通过检验这种约束关系来把错误识别或校正出来，从而保证通信的可靠性。 差控码 将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中点的集合。 通过增加冗余度，即将信息空间映射到更大的信道波形空间，以提高不同码字波形间的差异程度，从而获得增益。,6.2:信道编码的作用及实质 信道编码的实质,6.2:信道编码的作用及实质 信道编码的实质,匹配信道特性： 抗白噪声： 优秀的调制、信道编码方案， 扩频方式等。 抗衰落和多径干扰： 功控抗慢衰落， 空间分集抗平滑瑞利（空间选择）衰落， Rake接收机及自适应均衡抗频率选择性， 交织编码抗时间选择性衰落等。 抗多址干扰与远近效应： 正交码型设计， 功率控制， 多用户检测， 扰乱编码进行能量分集， 智能天线等。,6.2:信道编码的作用及实质 差错控制编码的基本原理,如用三位二进制编码来代表八个字母 000 A 001 B 010 C 011 D 100 E 101 F 110 G 111 H R=log8/3=1bit/二进制符号 不管哪一位发生错误，都会使传输字母错误,6.2:信道编码的作用及实质 差错控制编码的基本原理,如用三位二进制编码传四个字母 000 A 011 B 101 C 110 D R=（log4）/3=0.67bit/二进制符号 发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。 禁用码字： 001 010 100 111,6.2:信道编码的作用及实质 差错控制编码的基本原理,如用三位二进制编码传二个字母 000 A 111 B R=（log2）/3=0.33bit/二进制符号 可以检查出2位错误 可以纠正一位错误 可以同时检查一位错误，并纠正一位错误。 禁用码字： 001 010 011 100 101 110,6.2:信道编码的作用及实质 信道编码的基本分类,按码的结构分: 线性码 线性分组码（群码） 卷积码（线性树码） 非线性码 按抗干扰模式分 抗随机差错码 抗突发差错码 按对错误的处理方式分 检错码应用于ARQ（反馈重发）方式； 纠错码应用于FEC（前向纠错）方式； 检纠错码应用于HEC（混合纠错）方式。,6.3:信道编码定理的证明及其物理意义,信道编码定理 问题：在有噪信道中，使平均误码率Pe尽可能小的情 况下，可达到的信息传输率是多少？ 答案：信道容量C 信道编码定理的证明 证明思路 随机编码方法 联合典型序列,信道编码定理： 设R是信息传输的速率，C是离散无记忆信道的信道容量，0是任意小的数，则只要RC就总存在码字长为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随机组合的空间为2NH(X)+H(Y)， 联合典型序列占其中约1/ 2NI(X;Y)，只是很小的一部分 故：当X的数目 2NI(X;Y)时，可使Pe0 给出一种译码方法：译码时，取与接收矢量联合典型的码字作为输出，这种译码方法可以保证得到很低的误码率。,6.3:信道编码定理的证明及其物理意义,6.3:信道编码定理的证明及其物理意义,物理意义： 通过编码可以实现有噪信道上可靠的信息传输 有噪信道可靠传输的信息率的上界是信道容量C 在码长及发送信息速率一定时，可以通过增大信道容量，使错误概率减小 在信道容量及发送信息速率一定时，可以通过增加码长，使错误概率下降,随机编码方法： 对每一个消息 m,(m=0,1,M-1), 编码为xm=(xm1xm2xmN) 其中：xmi (i=1,2,N) 是按照输入字母的概率随 机选取，从而得到全部M=2NR个码字，组 成码矢量C（x0x2.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)2nI(X；Y)3，得到,由于随机编码是按照信道输入的最佳分布p(x)进行的，因此有C=I(X；Y)，在上述证明最后一步用到该公式。,如果RC3，则当n足够大时，有,于是得到,PE2,所以，在码字足够长时，随机编码码集合中的平均错误译码概率PE2，在这些码中，至少有一个码的平均错误译码概率不大于2。 令=2，即证明了该定理。,信道编码定理证明的几点说明 特点： 香农只是证明了码的存在性，未给出构造方法 实现困难 随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现； 即使找到，码字也是毫无结构的，只能采用查表译码方法，当N很大时，码表的存储量也很难接受 香农采取的证明方法评价： 不很严格，不是最优，但便于理论分析 随机编码方法在后来严格的证明中一直被采用,6.3:信道编码定理的证明及其物理意义,无失真信源编码定理的物理意义（2）,无失真信源编码定理（香农第一定理） 又称为无噪信道编码定理 无噪时，I(X;Y)=H(X) C=maxI(X;Y),信道输入为最佳分布时达到。以对称信道为例，此时ClogM K为平均码长，R=H(X)/K 第一定理：KH(X)/logM RlogMR C 将无失真编码过程看成经过一个信道，只有满足KH(X)/logM，才能满足第二定理的无误传输条件RC，即编码过程是无失真的。,香农理论极限：RC； 存在编译码方法使Pe0 给定Pe；存在