第六章信道编码定理课件

第六章：信道编码定理第六章：信道编码定理信息论研究编码的主要内容信息论研究编码的主要内容回答如下问题回答如下问题:为什么要编码为什么要编码?什么样的码是好码什么样的码是好码?不能回答的问题不能回答的问题:怎样进行编码怎样进行编码?怎样进行译码怎样进行译码?信息论研究编码的方法信息论研究编码的方法将问题分而治之将问题分而治之有效性：认为可靠性已满足有效性：认为可靠性已满足可靠性：认为有效性已满足可靠性：认为有效性已满足将信源与信道编码分别研究将信源与信道编码分别研究信源编码：解决有效性问题信源编码：解决有效性问题信道编码：解决可靠性问题信道编码：解决可靠性问题编码信源信源信源信源编码信道信道编码信道信道信宿信宿译码信道信道译码信源信源译码有效性、可靠性问题分别解决有效性、可靠性问题分别解决信息流通信信道通信信道H(X)I(X;Y)可以获得的信可以获得的信息量息量所得信息能否可靠所得信息能否可靠地确定信道输入？地确定信道输入？信息传输的有效性指标信息传输的有效性指标给定特性的信道最大可达给定特性的信道最大可达的信息传输率的信息传输率信道传输信息的信道传输信息的能力度量能力度量C信道噪声信道噪声实际通信中人们对传输要求什么？实际通信中人们对传输要求什么？传输信息无差错传输要可靠传输信息无差错传输要可靠 传输信息量大传输要有效传输信息量大传输要有效传输的信息是否无误？传输的信息是否无误？可靠性？可靠性？6.1:6.1:问题引出与定理描述问题引出与定理描述提出的与信道传输提出的与信道传输可靠性可靠性有关的问题：有关的问题：如何能使信息传输后发生的错误最少？如何能使信息传输后发生的错误最少？错误概率与那些因素有关错误概率与那些因素有关？有无办法控制？有无办法控制？能控制到什么程度？能控制到什么程度？无误传输可达的最大信息率是多少？无误传输可达的最大信息率是多少？信道编码定理信道编码定理具体信道编码技术具体信道编码技术错误概率与译码准则、编码方法错误概率与译码准则、编码方法1错误概率与错误概率与译码规则译码规则错误概率错误概率Pe与什么有关？与什么有关？信道的统计特性信道的统计特性译码规则译码规则译码规则的选择依据译码规则的选择依据最大后验概率准则理想最大后验概率准则理想最大似然准则实用最大似然准则实用最小距离准则实用最小距离准则实用编码编码编码编码信道传输信道传输错误概率与译码准则、编码方法错误概率与译码准则、编码方法2调制调制广义的信道编码广义的信道编码已解决有效已解决有效性表示问题性表示问题CAB213消消息息集集合合 编编码码集集合合 CAB21435PA2PA1PA3PA4PA5发发送送波波形形集集合合 接接收收波波形形集集合合 错误概率与译码准则、编码方法错误概率与译码准则、编码方法3信道译码An1243w4w3w1w2xxxAn 是接收空间w1,w2 是发送的码字围绕每个码字有一个译码域i如果接收的码字在 i中，就认为发送的是码字 wi 发生生错误正确正确译码不知如何不知如何译码译码错误有时接收码字会被映射到错误的i，进而被译成错误的 wi 一般,An中 存在一些不属于任何 i的区域 错误概率与译码准则、编码方法错误概率与译码准则、编码方法4问题：问题：在输入和信道特性给定的条件下，差错概率将取决在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分于接收矢量空间按什么样的划分准则进行划分划分接收矢量空间的划分接收矢量空间的准则准则译码器的译码准则译码器的译码准则译码准则一：最小错误概率准则（最大后验概率准译码准则一：最小错误概率准则（最大后验概率准则）则）特点：特点：优点：理想优点：理想缺点：缺点：1、后验概率不易得到、后验概率不易得到 2、后验概率依赖于输入分布、后验概率依赖于输入分布错误概率与译码准则、编码方法错误概率与译码准则、编码方法5错误概率与译码准则、编码方法错误概率与译码准则、编码方法6译码准则二：最大似然译码准则译码准则二：最大似然译码准则最大后验概率译码准则最大后验概率译码准则&最大似然译码准则最大似然译码准则输入等概时二者是一致的输入等概时二者是一致的错误概率与译码准则、编码方法错误概率与译码准则、编码方法7译码准则三：最小距离译码准则译码准则三：最小距离译码准则最小距离译码准则最小距离译码准则&最大似然译码准则最大似然译码准则在二进制对称信道中二者是一致的在二进制对称信道中二者是一致的选择好的译码规则可以降低错误概率选择好的译码规则可以降低错误概率FANO不等式说明不等式说明,无论什么译码规则无论什么译码规则,对减少误码对减少误码率的作用有限率的作用有限,误码率误码率受信道特性的影响严重受信道特性的影响严重。增加码空间增加码空间M，并选择适当的编码方法，并选择适当的编码方法,可以既使错可以既使错误概率降低误概率降低,又使码率保持较大。又使码率保持较大。适当的编码方法就是适应信道特性的方法即适当的编码方法就是适应信道特性的方法即:信道信道编码编码错误概率与译码准则、编码方法错误概率与译码准则、编码方法86.1:问题引出与定理描述问题引出与定理描述 问题：问题：在有噪信道中，使平均误码率在有噪信道中，使平均误码率Pe尽可能小的尽可能小的 情况下，可达到的信息传输率是多少？情况下，可达到的信息传输率是多少？几乎无误几乎无误 答案：答案：信道容量信道容量C6.1:6.1:问题引出与定理描述问题引出与定理描述信道编码定理：信道编码定理：设设R是信息传输的速率，是信息传输的速率，C是离散无记忆信道的信是离散无记忆信道的信道容量，道容量，00是任意小的数，则只要是任意小的数，则只要RC就总存在就总存在码字长为码字长为N N，码字数为，码字数为M=2NR的分组码使译码的平的分组码使译码的平均差错概率均差错概率Pe00是任意小的数，则只要是任意小的数，则只要RCRC就总存在码就总存在码字长为字长为N N，码字数为，码字数为M=2M=2NRNR的分组码使译码的平均差的分组码使译码的平均差错概率错概率P Pe e 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:信道编码定理的证明及其物理意义信道编码定理的证明及其物理意义Input sequenceOutput sequenceywiwi+12NH(XY)sequencesthat canmap to y M=2NR code words6.3:信道编码定理的证明及其物理意义信道编码定理的证明及其物理意义物理意义：物理意义：通过编码可以实现有噪信道上可靠的信息传输通过编码可以实现有噪信道上可靠的信息传输有噪信道可靠传输的信息率的上界是信道容量有噪信道可靠传输的信息率的上界是信道容量C C在码长及发送信息速率一定时，可以通过增大在码长及发送信息速率一定时，可以通过增大信道容量，使错误概率减小信道容量，使错误概率减小 在信道容量及发送信息速率一定时，可以通过在信道容量及发送信息速率一定时，可以通过增加码长，使错误概率下降增加码长，使错误概率下降 随机编码方法：随机编码方法：对每一个消息对每一个消息 m,(m=0,1,M-1),编码为编码为xm=(xm1xm2xmN)其中：其中：xmi (i=1,2,N)是按照输入字母的概率随是按照输入字母的概率随 机选取，从而得到全部机选取，从而得到全部M=2NR个码字，组个码字，组 成码矢量成码矢量C（x0 x2.xM-1)随机编码方法产生某一特定码矢量的概率随机编码方法产生某一特定码矢量的概率P(C)是：是：6.3:信道编码定理的证明及其物理信道编码定理的证明及其物理意义意义6.3:信道编码定理的证明及其物理信道编码定理的证明及其物理意义意义所有码的总数所有码的总数有了这样的码集以后，香农不是去计算某一特定好有了这样的码集以后，香农不是去计算某一特定好码的性能，而是设法计算这些码的平均性能。码的性能，而是设法计算这些码的平均性能。码字数码字数 只占全部可能序列只占全部可能序列 的一小部分。的一小部分。l设码元数为设码元数为r，则所有可能产生的码的总数为：，则所有可能产生的码的总数为：例，例，证明证明证明证明 设信道容量所对应的信道输入符号的最佳分布为设信道容量所对应的信道输入符号的最佳分布为p p(x x)，以此概率分布为基准，按照随机编码方法编码得到码矢，以此概率分布为基准，按照随机编码方法编码得到码矢量量C C。假设输入消息是等概率分布的，第假设输入消息是等概率分布的，第i i个码字出错的概个码字出错的概率为率为p pe|e|i i，则码矢量，则码矢量C 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 N很大时，码表的存储量也很难接受很大时，码表的存储量也很难接受香农采取的证明方法评价：香农采取的证明方法评价：不很严格，不是最优，但便于理论分析不很严格，不是最优，但便于理论分析随机编码方法在后来严格的证明中一直被采用随机编码方法在后来严格的证明中一直被采用6.3:信道编码定理的证明及其物理信道编码定理的证明及其物理意义意义无失真信源编码定理的物理意义（2）无失真信源编码定理（香农第一定理）又称为无噪信道编码定理无噪时，I(X;Y)=H(X)C=maxI(X;Y),信道输入为最佳分布时达到。以对称信道为例，此时ClogMK为平均码长，R=H(X)/K第一定理：KH(X)/logMRlogMR C将无失真编码过程看成经过一个信道，只有满足KH(X)/logM，才能满足第二定理的无误传输条件RC，即编码过程是无失真的。香农理论极限：香农理论极限：RC；存在编译码方法使存在编译码方法使Pe0 给定给定Pe；存在编译码方法使；存在编译码方法使RC 1.59dB6.4:信道编码的性能界限信道编码的性能界限-3-3-2-2-1-10 01 12 23 34 45 56 67 78 89 91010111112121010-6-61010-5-51010-4-41010-3-31010-2-21010-1-1误误码码率率p pb b信噪比信噪比E Eb b/N/N0 0(dB)(dB)s sh ha an nn no o限限仅仅内内码码（4 4，1 1，1 15 5）未未编编码码仅仅内内码码（2 2，1 1，7 7）码码级连级连级连级连反馈信道不增加容量 反馈是纠错的最直观工程方法 无反馈信道是反馈信道的特例，因此CFBC但是，令人惊奇地，反馈不能增加信道的容量反馈信道容量定理 定理:反馈不增加信道的容量，即结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings演讲人：XXXXXX 时 间：XX年XX月XX日