第六章：信道编码

信道编码本章节达到的目的理解信道编码在通信系统中的作用了解信道编码的的基本分类了解信道编码性能评价的基本方法了解汉明码的编译码原理了解信道容量/容量代价函数在信道编码定理中的作用理解香农第二定理又称有噪信道编码定理的物理意义了解信道编码理论与实际应用的差距本章研究内容信道编码概述错误概率与译码准则、编码方法信道编码定理与联合典型序列信道编码的性能界限信道编码举例－汉明码关于信道编码理论的若干评注§6.1:信道编码概述问题引出什么是信道编码信道编码的作用信道编码的三种情形信道编码的实质§6.1:信道编码概述－问题引出互信息能告诉我们什么？随机变量X,Y统计意义上的依存程度可以获得的信息量不能：所得信息能否可靠地确定信道输入？无噪信道编码能告诉我们什么？无噪无损信道，只要对信源输出进行适当编码，总能以最大信息传输率，无差错的传输信息。但是：一般信道总存在噪声或干扰，信息传输会造成损失实际通信中人们对传输要求什么？传输信息量大传输可靠提出的与信道传输有关的问题：如何能使信息传输后发生的错误最少？错误概率与那些因素有关？有无办法控制？能控制到什么程度？无误传输可达的最大信息率是多少？§6.1:信道编码概述－什么是信道编码通信系统模型信道编码：从消息到信道波形或矢量的映射

希望通信系统与信道统计特性相匹配的编码§6.1:信道编码概述－什么是信道编码复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于广义的信道编码范畴注意：信道译码可以不是离散信道译码。只有当解调为硬判决输出时才是离散信道和离散信道译码§6.1:信道编码概述－信道编码的作用信道编码的作用：在资源、可靠性和传信量之间选择一个好的工作点（有时还要考虑延时）。资源指的提供信息传输所付出的代价包括频率、时间、空间、功率等等。但不包括实现复杂度一个好的编码就是要充分利用资源，传递尽可能多的信息§6.1:信道编码概述－三种情形：给定资源和可靠性要求，通过信道编码尽量提高传输速率（例：多电平编码）给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销（例：扰乱编码）给定资源和传输速率，通过编码提高可靠性（例：检、纠错编码）§6.1:信道编码概述－编码的实质

利用冗余降低差错概率将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。§6.1:信道编码概述－信道编码的基本分类

按码的结构分:线性码线性分组码（群码）卷积码（线性树码）非线性码按抗干扰模式分抗随机差错码抗突发差错码按编译码理论所用数学工具分代数码几何码组合码按对错误的处理方式分检错码纠错码§6.2:错误概率与译码准则、编码方法－1错误概率与译码规则错误概率Pe与什么有关信道的统计特性译码规则译码规则的选择依据最大后验概率准则－－理想最大似然准则－－实用编码译码§6.2:错误概率与译码准则、编码方法－2信道译码An1243w4w3w1w2xxxAn

是接收空间w1,w2,…

是发送的码子围绕每个码子有一个译码域i如果接收的码子在i中，就认为发送的是码子

wi

发生错误一般,An中存在一些不属于任何

i的区域

有时接收码子会被映射到错误的i，进而被译成错误的

wi

正确译码不知如何译码译码错误§6.2:错误概率与译码准则、编码方法－3

问题：在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分划分接收矢量空间的准则－－译码器的译码准则§6.2:错误概率与译码准则、编码方法－4

§6.2:错误概率与译码准则、编码方法－5

准则一：平均错误概率最小译码准则计算平均错误概率：YX若码字Xm经传输后在接收端所得的接收矢量不落在Ym子集中，则译码发生错误其中：§6.2:错误概率与译码准则、编码方法－6

§6.2:错误概率与译码准则、编码方法－7理想的译码器应使平均译码差错概率最小是译码正确的概率，则译码发生错误的概率为：译码器平均的译码差错概率为：§6.2:错误概率与译码准则、编码方法－8最小错误概率准则（最大后验概率准则）：特点：优点：理想缺点：1、后验概率不易得到2、后验概率依赖于输入分布§6.2:错误概率与译码准则、编码方法－9准则二：最大似然译码准则此时译码差错概率为：平均的译码差错概率为：§6.2:错误概率与译码准则、编码方法－10最大后验概率译码准则&最大似然译码准则输入等概时－－二者是一致的此时：§6.2:错误概率与译码准则、编码方法－11错误概率与编码如何在信息传输率一定的前提下使Pe0实际经验：重复发送可以使Pe减小重复次数N很大时，可以使Pe0但：信息传输率降低信道编码定理：R一定时，可以找到一种编码方法使Pe相当低引入概念：码字距离§6.2:错误概率与译码准则、编码方法－12码字距离－汉明距离长度为n的两个符号序列(码字)αi和βj之间的距离是指αi和βj之间对应位置上不同码元的个数，用符号D(αi,βj)表示。这种码字距离通常称为汉明距离。例如：两个二元序列αi=101111βj=111100则得D(αi,βj)=3又例如：两个四元序列αi=1320120βj=1220310则得D(αi，βj)＝３。§6.2:错误概率与译码准则、编码方法－13对于二元信道，即对于二元码，汉明距离可表达成下述关系式：若令αi＝（ａi1ａi２…ａin）ａik∈｛0,1｝βj＝（bj1bj2…bjn）βjk∈｛0,1｝则αi和βj的汉明距离为D(αi，βj)＝在某一码书C中，任意两个码字的汉明距离的最小值称为该码C的最小距离，即dmin＝min｛D(Ci,Cj)｝Ci≠CjCi,Cj∈C在任一码书中，码的最小距离dmin与该码的译码错误概率有关。§6.2:错误概率与译码准则、编码方法－14与码字距离有关的结论最小距离译码准则在二进制对称信道中：最小距离译码准则＝最大似然译码准则§6.3:信道编码定理与联合典型序列-1信道编码定理引出问题：在有噪信道中，使平均误码率Pe尽可能小的情况下，可达到的信息传输率是多少？答案：信道容量C信道编码定理信道编码定理的证明证明思路随机编码方法联合典型序列§6.3:信道编码定理与联合典型序列-2信道编码定理：设R是信息传输的速率，C是离散无记忆信道的信道容量，ε>0是任意小的数，则只要R<C就总存在码字长为N，码字数为M=2NR的分组码使译码的平均差错概率Pe<ε。§6.3:信道编码定理与联合典型序列-3信道编码定理的证明思路：通常思路：先构造一个理想的好码，并定义一种译码准则，计算该好码经过译码后的误码率问题：构建极其复杂且无具体方法N值很大时，误码率计算困难香农采取的方法:用随机编码方法得到所有可能码的集合在其中随机选择一个码作为信道码利用大数定理计算在集合平均意义上的该码性能利用联合典型序列译码香农采取的方法评价：不很严格，不是最优，但便于理论分析随机编码方法在后来严格的证明中一直被采用§6.3:信道编码定理与联合典型序列-4随机编码方法：对每一个消息m,(m=0,1,…M-1),编码为xm=(xm1xm2…xmn)其中：xmi(i=1,2,…n)是按照输入字母的概率随机选取，从而得到全部M=2NR个码字，组成码集C＝（x1x2….xM-1)随机编码方法产生某一特定码字的概率P(Xm)是：§6.3:信道编码定理与联合典型序列-5联合ε典型序列ε典型序列：信源输出的随机序列－奠定了信源编码的基础联合ε典型序列：两个随机变量的自然扩展，是信道编码的基础

联合ε典型序列定义：联合AEP定理定理解释：

§6.3:信道编码定理与联合典型序列-6联合ε典型序列定义：设（X,Y）是长为N的随机序列对，则在这些随机序列对中满足下列条件的序列对被称为联合典型序列式中δ是任意小的数，联合典型序列的全体构成联合典型序列集，记做G§6.3:信道编码定理与联合典型序列-7联合AEP定理：设随机序列对（X,Y)的，则对任意小的数δ>0，我们总能找到足够大的N使全体序列对的集合能被分成满足下述条件的集合G及其补集Gc：（1）（2）（3）设（X’，Y’）是相互独立的随机序列对，但它与（X,Y）有相同的边缘分布，即：则：§6.3:信道编码定理与联合典型序列-8联合AEP定理的解释：两个随机变量情况下，序列Xn,Yn及其联合序列XnYn都具有AEP特性联合典型序列对是高概率序列对联合典型序列对出现概率接近相等，且其和接近于1联合典型序列对是一些密切关联的序列对一般与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)时，，可使Pe0给出一种译码方法：译码时，取与接收矢量联合典型的码字作为输出，这种译码方法可以保证得到很低的误码率。InputsequenceOutputsequence………………ywiwi+12nH(XY)

sequencesthatcanmaptoy

M=2nR

codewords§6.3:信道编码定理与联合典型序列-9信道编码定理证明的几点说明香农只是证明了码的存在性，未给出构造方法随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现；而且即使找到，码字也是毫无结构的，只能采用查表译码方法，当N很大时，码表的存储量也很难接受§6.4:信道编码的性能界限－1理论性能极限－－存在性香农信道编码定理作用：理论极限、渐进性能工程实现上的界限－－构造性最小距离界限作用：构造新码、估计新码性能时，说明新码与最好性能的码接近的程度香农理论极限：R<C；存在编译码方法使Pe0给定Pe；存在编译码方法使RC

－1.59dB§6.4:信道编码的性能界限－2实际信道编码理论研究内容：最佳码性能有多好？如何设计好码？如何译码？最小距离限在码长和最小距离给定时，具有最大可能的码字数A(n,dmin)的码为好码。完备码A(n,dmin)的上下限近半个世纪以来，上限不断改进，并逐步向下限靠近，但下限保持不变未证明的看法：上下限会逐步会合成为一条限。§6.5:信道编码举例－汉明码－1汉明码的编码汉明码的译码§6.5:信道编码举例－汉明码－2汉明码第一个具有系统的编译码方法的信道码（7，4）汉明码码长n=7,信息元k=4，检验元r=n-k=3。长为3的二元序列共有23＝８个。我们将其中7个非全零序列按列排成如下矩阵H矩阵称为：一致监督矩阵。§6.5:信道编码举例－汉明码－3设码字C=（c6c5c4c3c2c1c0),有：H×CT=0T其中：0＝（000），0T是0矢量的转置，即满足：c3+c2+c1+c0=0c5+c4+c1+c0=0c6+c4+c2+c0=00000000010010110000111100110000111101010101001100110100100101100110011101010111100000011001011110010110101111111§6.5:信道编码举例－汉明码－4给出生成矩阵满足：§6.5:信道编码举例－汉明码－5（7，4）汉明码特点：16个码字是所有码长为7的二元序列中的一个封闭子集。码的最小距离等于非零码字的最小重量＝3能检2个错，纠一个错。d>=s+1（检错时）d>=2s+1（纠错时）§6.5:信道编码举例－汉明码－6汉明码译码：伴随式译码错误图样ER=C+E伴随式S伴随式错误图样假设接收到码矢y=(0010010)有7个可能的错误位置,如Z矩阵所示伴随式是