1、第六章：信道编码定理第六章：信道编码定理信息论研究编码的主要内容信息论研究编码的主要内容 回答如下问题回答如下问题:为什么要编码为什么要编码?什么样的码是好码什么样的码是好码?不能回答的问题不能回答的问题:怎样进行编码怎样进行编码?怎样进行译码怎样进行译码?信息论研究编码的方法信息论研究编码的方法 将问题分而治之将问题分而治之 有效性：认为可靠性已满足有效性：认为可靠性已满足 可靠性：认为有效性已满足可靠性：认为有效性已满足 将信源与信道编码分别研究将信源与信道编码分别研究 信源编码：解决有效性问题信源编码：解决有效性问题 信道编码：解决可靠性问题信道编码：解决可靠性问题编码编码信源信源信源信
2、源编码编码信道信道编码编码信道信道信宿信宿译码译码信道信道译码译码信源信源译码译码有效性、可靠性问题分别解决有效性、可靠性问题分别解决信息流通信信道通信信道H(X)I(X;Y)可以获得的信可以获得的信息量息量所得信息能否可靠所得信息能否可靠地确定信道输入？地确定信道输入？信息传输的有效性指标信息传输的有效性指标给定特性的信道最大可达给定特性的信道最大可达的信息传输率的信息传输率信道传输信息的信道传输信息的能力度量能力度量C信道噪声信道噪声实际通信中人们对传输要求什么？实际通信中人们对传输要求什么？传输信息无差错传输要可靠传输信息无差错传输要可靠 传输信息量大传输要有效传输信息量大传输要有效传输
3、的信息是否无误？传输的信息是否无误？可靠性？可靠性？6.1:6.1:问题引出与定理描述问题引出与定理描述 提出的与信道传输提出的与信道传输可靠性可靠性有关的问题：有关的问题：如何能使信息传输后发生的错误最少？如何能使信息传输后发生的错误最少？错误概率与那些因素有关错误概率与那些因素有关？有无办法控制？有无办法控制？能控制到什么程度？能控制到什么程度？无误传输可达的最大信息率是多少？无误传输可达的最大信息率是多少？信道编码定理信道编码定理具体信道编码技术具体信道编码技术错误概率与译码准则、编码方法错误概率与译码准则、编码方法1 错误概率与错误概率与译码规则译码规则 错误概率错误概率Pe与什么有关
4、？与什么有关？信道的统计特性信道的统计特性 译码规则译码规则 译码规则的选择依据译码规则的选择依据 最大后验概率准则理想最大后验概率准则理想 最大似然准则实用最大似然准则实用 最小距离准则实用最小距离准则实用编码编码信道传输信道传输错误概率与译码准则、编码方法错误概率与译码准则、编码方法2调制调制广义的信道编码广义的信道编码已解决有效已解决有效性表示问题性表示问题CAB213消息集合消息集合 编码集合编码集合 CAB21435PA2PA1PA3PA4PA5发送波形集合发送波形集合 接收波形集合接收波形集合 错误概率与译码准则、编码方法错误概率与译码准则、编码方法3信道译码An1243w4w3w
5、1w2xxx An 是接收空间 w1,w2 是发送的码字 围绕每个码字有一个译码域i 如果接收的码字在 i中，就认为发送的是码字 wi 发发生生错误错误正确正确译码译码不知如何不知如何译码译码译码错误译码错误 有时接收码字会被映射到错误的i，进而被译成错误的 wi 一般,An中 存在一些不属于任何 i的区域 错误概率与译码准则、编码方法错误概率与译码准则、编码方法4 问题：问题：在输入和信道特性给定的条件下，差错概率将取决在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分于接收矢量空间按什么样的划分准则进行划分 划分接收矢量空间的划分接收矢量空间的准则准则 译
6、码器的译码准则译码器的译码准则 译码准则一：最小错误概率准则（最大后验概率准译码准则一：最小错误概率准则（最大后验概率准则）则）特点：特点：优点：理想优点：理想 缺点：缺点：1、后验概率不易得到、后验概率不易得到 2、后验概率依赖于输入分布、后验概率依赖于输入分布错误概率与译码准则、编码方法错误概率与译码准则、编码方法5)|(max)|)(yxpyygpmm错误概率与译码准则、编码方法错误概率与译码准则、编码方法6 译码准则二：最大似然译码准则译码准则二：最大似然译码准则 最大后验概率译码准则最大后验概率译码准则&最大似然译码准则最大似然译码准则 输入等概时二者是一致的输入等概时二者是一致的)
7、|(max)(|(mmxypygyp错误概率与译码准则、编码方法错误概率与译码准则、编码方法7 译码准则三：最小距离译码准则译码准则三：最小距离译码准则 最小距离译码准则最小距离译码准则&最大似然译码准则最大似然译码准则 在二进制对称信道中二者是一致的在二进制对称信道中二者是一致的),(min)(,(mmxydygyd 选择好的译码规则可以降低错误概率选择好的译码规则可以降低错误概率 FANO不等式说明不等式说明,无论什么译码规则无论什么译码规则,对减少误码对减少误码率的作用有限率的作用有限,误码率误码率受信道特性的影响严重受信道特性的影响严重。增加码空间增加码空间M，并选择适当的编码方法，并
8、选择适当的编码方法,可以既使可以既使错误概率降低错误概率降低,又使码率保持较大。又使码率保持较大。适当的编码方法就是适应信道特性的方法即适当的编码方法就是适应信道特性的方法即:信道信道编码编码错误概率与译码准则、编码方法错误概率与译码准则、编码方法86.1:问题引出与定理描述问题引出与定理描述 问题：问题：在有噪信道中，使平均误码率在有噪信道中，使平均误码率Pe尽可能小的尽可能小的 情况下，可达到的信息传输率是多少？情况下，可达到的信息传输率是多少？几乎无误几乎无误 答案：答案：信道容量信道容量C6.1:6.1:问题引出与定理描述问题引出与定理描述 信道编码定理：信道编码定理：设设R是信息传输
9、的速率，是信息传输的速率，C是离散无记忆信道的是离散无记忆信道的信道容量，信道容量，00是任意小的数，则只要是任意小的数，则只要RC就总存就总存在码字长为在码字长为N N，码字数为，码字数为M=2NR的分组码使译码的分组码使译码的平均差错概率的平均差错概率Pe00是任意小的数，则只要是任意小的数，则只要RCRC就总存在就总存在码字长为码字长为N N，码字数为，码字数为M=2M=2NRNR的分组码使译码的平均的分组码使译码的平均差错概率差错概率P Pe e 0，我们总能找到足够大的，我们总能找到足够大的N使全体序列对的集合能被分成满足下使全体序列对的集合能被分成满足下述条件的集合述条件的集合G及
10、其补集及其补集Gc：（1）（2）（3）设）设 是相互独立的随机序列对，但它与是相互独立的随机序列对，但它与 有相同的有相同的边缘分布，即：边缘分布，即：则：则：1(,)(,)Nnnnpp xyx y(,)(,)1cPX YGPX YG ()()|()|2|()|(1)2N H XYN H XYG XYG XY(,)(,)()()PX Yx yp x p y (;)3 (;)3(,)()2(,)()(1)2N I X YN I X YPX YG XYPX YG XY 6.3:信道编码定理的证明及其物理意义信道编码定理的证明及其物理意义(,)X Y(,)X Y(,)X Y 1x2xxy3x4x1y
11、3y4y2yjyy2y1ysxx()2NH Y个典型序列y1x2x()2NH Xx个典型序列x非典型序列非典型序列y5y()2NH XY个联合典型序列(x,y)联合联合AEP定理的解释：定理的解释：两个随机变量情况下，序列两个随机变量情况下，序列Xn,Yn及其联合序列及其联合序列XnYn都具都具有有AEP特性特性 联合典型序列对是高概率序列对联合典型序列对是高概率序列对 联合典型序列对是一些密切关联的序列对联合典型序列对是一些密切关联的序列对 一般与一般与X对应的对应的Y可能是可能是Y空间的任一个，该定理说明：随空间的任一个，该定理说明：随N的增大，对应的增大，对应X的的Y只能是（只能是（X,
12、Y)典型序列对的典型序列对的Y，取其，取其他他Y的概率的概率0 联合典型序列数目为联合典型序列数目为2NH(XY)，典型典型X,典型典型Y随机组合的空间为随机组合的空间为2NH(X)+H(Y)，联合典型序列占其中约联合典型序列占其中约1/2NI(X;Y)，只是很小的一部分，只是很小的一部分 故：当故：当X的数目的数目 2NI(X;Y)时，可使时，可使Pe0 给出一种译码方法：译码时，取与接收矢量联合典型的码给出一种译码方法：译码时，取与接收矢量联合典型的码字作为输出，这种译码方法可以保证得到很低的误码率。字作为输出，这种译码方法可以保证得到很低的误码率。6.3:信道编码定理的证明及其物理意义信
13、道编码定理的证明及其物理意义Input sequenceOutput sequenceywiwi+12NH(XY)sequencesthat canmap to y M=2NR code words th e n 0eNP2N CReP可证明6.3:信道编码定理的证明及其物理意义信道编码定理的证明及其物理意义 物理意义：物理意义：通过编码可以实现有噪信道上可靠的信息传输通过编码可以实现有噪信道上可靠的信息传输有噪信道可靠传输的信息率的上界是信道容量有噪信道可靠传输的信息率的上界是信道容量C C在码长及发送信息速率一定时，可以通过增大在码长及发送信息速率一定时，可以通过增大信道容量，使错误概率减
14、小信道容量，使错误概率减小 在信道容量及发送信息速率一定时，可以通过在信道容量及发送信息速率一定时，可以通过增加码长，使错误概率下降增加码长，使错误概率下降 随机编码方法：随机编码方法：对每一个消息对每一个消息 m,(m=0,1,M-1),编码为编码为xm=(xm1xm2xmN)其中：其中：xmi (i=1,2,N)是按照输入字母的概率随是按照输入字母的概率随 机选取，从而得到全部机选取，从而得到全部M=2NR个码字，组个码字，组 成码矢量成码矢量C（x0 x2.xM-1)随机编码方法产生某一特定码矢量的概率随机编码方法产生某一特定码矢量的概率P(C)是：是：101()()MNmimiPp x
15、C6.3:信道编码定理的证明及其物理信道编码定理的证明及其物理意义意义6.3:信道编码定理的证明及其物理信道编码定理的证明及其物理意义意义 所有码的总数所有码的总数 有了这样的码集以后，香农不是去计算某一特定好有了这样的码集以后，香农不是去计算某一特定好码的性能，而是设法计算这些码的平均性能。码的性能，而是设法计算这些码的平均性能。码字数码字数 只占全部可能序列只占全部可能序列 的一小部分。的一小部分。2N2NR8212332,16,2,10NRNrNMr2NRNrl 设码元数为设码元数为r，则所有可能产生的码的总数为：，则所有可能产生的码的总数为：例，例，证明证明 设信道容量所对应的信道输入
16、符号的最佳分布为p(x)，以此概率分布为基准，按照随机编码方法编码得到码矢量C。假设输入消息是等概率分布的，第i个码字出错的概率为pe|i，则码矢量C的译码平均错误概率为ee|e|111()()()2MMiiiNRiippppCCC其中，pi为码矢量中第i个码字对应的概率。则在码矢量集合C上对pe(C)求数学期望，得到平均错误概率为Ee()()pppCCCe|11()()2MiNRippCCC对于随机编码方法，不同的输入消息符号所产生对应码字的方法是相同的，所以在码矢量集合上进行平均后得到的码错误数学期望e|()()ippCCC与i的取值无关，为表示方便起见，令e|e()()ipppCCC将其
17、代入平均错误概率表示式，并考虑到M=2NR，于是得到Ee|ee1111()()22MMiNRNRiiPppppCCC为了计算，设y表示发送码字ci时信道输出端接收的序列，令事件Ei表示ci与接收序列y构成的联合典型序列，于是有e1p(,)1,2,iiEGiMc y同时令事件E1c表示发送第一个码字与接收序列不构成联合典型序列，即c11(,)cEGc y根据联合典型序列的译码方法，当y不与码字c1构成联合典型序列，或者是与c1以外的其他码字构成联合典型序列时，错误译码就出现了，因此cE123e()MPpp EEEE其中，表示事件和。根据概率论可知ccE12312()()()MMiiPp EEEE
18、p Ep E由于接收序列y对应于输入码字c1，与其他码字之间相互独立，因此根据联合渐近等同分割定理的性质(1)、(3)，即p(E1c)和p(Ei)2nI(X；Y)3，得到(;)3 E2(;)3 2(21)2MN I X YiNRN I X YP由于随机编码是按照信道输入的最佳分布p(x)进行的，因此有C=I(X；Y)，在上述证明最后一步用到该公式。32N CREP如果RC3，则当n足够大时，有32N CR于是得到PE2所以，在码字足够长时，随机编码码集合中的平均错误译码概率PE2，在这些码中，至少有一个码的平均错误译码概率不大于2。令=2，即证明了该定理。信道编码定理证明的几点说明信道编码定理
19、证明的几点说明特点：特点：香农只是证明了码的香农只是证明了码的存在性存在性，未给出，未给出构造方法构造方法实现困难实现困难 随机编码所得的码集很大，通过搜索得到好码的方法实际上随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现；很难实现；即使找到，码字也是毫无结构的，只能采用查表译码方法，即使找到，码字也是毫无结构的，只能采用查表译码方法，当当N N很大时，码表的存储量也很难接受很大时，码表的存储量也很难接受香农采取的证明方法评价：香农采取的证明方法评价：不很严格，不是最优，但便于理论分析不很严格，不是最优，但便于理论分析 随机编码方法在后来严格的证明中一直被采用随机编码方法在后来严
20、格的证明中一直被采用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；存在编译码方法使
21、；存在编译码方法使RC 2N CReP1.59dB01.59bENdB 6.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但是，令人惊奇地，反馈不能增加信道的容量反馈信道容量定理 定理:反馈不增加信道的容量，即()max(,)FBp xCCI X Y
