第六章信道编码.

信道编码本章节达到的目的•理解信道编码在通信系统中的作用•了解信道编码的的基本分类•了解信道编码性能评价的基本方法•了解汉明码的编译码原理•了解信道容量/容量代价函数在信道编码定理中的作用•理解香农第二定理又称有噪信道编码定理的物理意义•了解信道编码理论与实际应用的差距本章研究内容•信道编码概述•错误概率与译码准则、编码方法•信道编码定理与联合典型序列•信道编码的性能界限•信道编码举例－汉明码•关于信道编码理论的若干评注§6.1:信道编码概述•问题引出•什么是信道编码•信道编码的作用•信道编码的三种情形•信道编码的实质§6.1:信道编码概述－问题引出•互信息能告诉我们什么？–随机变量X,Y统计意义上的依存程度–可以获得的信息量–不能：所得信息能否可靠地确定信道输入？•无噪信道编码能告诉我们什么？–无噪无损信道，只要对信源输出进行适当编码，总能以最大信息传输率，无差错的传输信息。–但是：一般信道总存在噪声或干扰，信息传输会造成损失•实际通信中人们对传输要求什么？–传输信息量大–传输可靠•提出的与信道传输有关的问题：–如何能使信息传输后发生的错误最少？•错误概率与那些因素有关？•有无办法控制？•能控制到什么程度？–无误传输可达的最大信息率是多少？§6.1:信道编码概述－什么是信道编码•通信系统模型•信道编码：从消息到信道波形或矢量的映射希望通信系统与信道统计特性相匹配的编码信源编码信道编码信道信道译码信源译码消息集中一个元素信道波形空间中的一个点失真后的波形恢复的消息引入失真消息到波形的映射判断是消息集中的哪个元素§6.1:信道编码概述－什么是信道编码•复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于广义的信道编码范畴•注意：信道译码可以不是离散信道译码。只有当解调为硬判决输出时才是离散信道和离散信道译码信源编码离散信道编码信道调制信道译码解调信源译码广义信道或离散信道§6.1:信道编码概述－信道编码的作用•信道编码的作用：在资源、可靠性和传信量之间选择一个好的工作点（有时还要考虑延时）。•资源指的提供信息传输所付出的代价–包括频率、时间、空间、功率等等。但不包括实现复杂度–一个好的编码就是要充分利用资源，传递尽可能多的信息§6.1:信道编码概述－三种情形：–给定资源和可靠性要求，通过信道编码尽量提高传输速率（例：多电平编码）–给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销（例：扰乱编码）–给定资源和传输速率，通过编码提高可靠性（例：检、纠错编码）§6.1:信道编码概述－编码的实质•利用冗余降低差错概率•将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。§6.1:信道编码概述－信道编码的基本分类•按码的结构分:–线性码•线性分组码（群码）•卷积码（线性树码）–非线性码•按抗干扰模式分–抗随机差错码–抗突发差错码•按编译码理论所用数学工具分–代数码–几何码–组合码•按对错误的处理方式分–检错码–纠错码§6.2:错误概率与译码准则、编码方法－1•错误概率与译码规则–错误概率Pe与什么有关•信道的统计特性•译码规则–译码规则的选择依据•最大后验概率准则－－理想•最大似然准则－－实用编码CAB21435发送波形集合接收波形集合PA2PA1PA3PA4PA5CAB213消息集合编码集合译码§6.2:错误概率与译码准则、编码方法－2信道译码An1243w4w3w1w2xxx•An是接收空间•w1,w2,…是发送的码子•围绕每个码子有一个译码域i•如果接收的码子在i中，就认为发送的是码子wi发生错误•一般,An中存在一些不属于任何i的区域•有时接收码子会被映射到错误的i，进而被译成错误的wi正确译码不知如何译码译码错误§6.2:错误概率与译码准则、编码方法－3•问题：–在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分•划分接收矢量空间的准则－－译码器的译码准则§6.2:错误概率与译码准则、编码方法－4§6.2:错误概率与译码准则、编码方法－5•准则一：平均错误概率最小译码准则•计算平均错误概率：mmYymyggMmYMY当表示成译码函数个不相交的子集,)((.)1,...2,1,0,}{CAB21435发送波形集合接收波形集合PA2PA1PA3PA4PA5YX)()|()()|(),()|(ypyxpxpxypxypyxxypmmmmmm则按全概率公式有：的概率，条件下接收矢量取是发送码字设若码字Xm经传输后在接收端所得的接收矢量不落在Ym子集中，则译码发生错误10)()()|()|()()()|(Mmmmypxpxypmxypxpypyxpmm其中：§6.2:错误概率与译码准则、编码方法－6§6.2:错误概率与译码准则、编码方法－7理想的译码器应使平均译码差错概率最小)|(yxpm是译码正确的概率，则译码发生错误的概率为：)|(1|yxppmye译码器平均的译码差错概率为：)|()(1))|(1()()(|yxpypyxpyppypPymmyyyeemax)|(yxpm§6.2:错误概率与译码准则、编码方法－8•最小错误概率准则（最大后验概率准则）：•特点：–优点：理想–缺点：1、后验概率不易得到2、后验概率依赖于输入分布)|(max)|)((yxpyygpmm§6.2:错误概率与译码准则、编码方法－9•准则二：最大似然译码准则•此时译码差错概率为：•平均的译码差错概率为：)|(max))(|(mmxypygypmYymmexypp)|(|mmememmepmppxpP||)()(§6.2:错误概率与译码准则、编码方法－10•最大后验概率译码准则&最大似然译码准则–输入等概时－－二者是一致的此时：)|()|()(1myMpmxypyxp)|(max)|(max)(1myMpmmmxypyxp)|(max)(1mmyMpxyp§6.2:错误概率与译码准则、编码方法－11•错误概率与编码–如何在信息传输率一定的前提下使Pe0–实际经验：重复发送可以使Pe减小•重复次数N很大时，可以使Pe0•但：信息传输率降低–信道编码定理：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与该码的译码错误概率有关。jknkikba1§6.2:错误概率与译码准则、编码方法－14•与码字距离有关的结论–最小距离译码准则–在二进制对称信道中：最小距离译码准则＝最大似然译码准则),(min))(,(mmxydygyd§6.3:信道编码定理与联合典型序列-1•信道编码定理引出–问题：在有噪信道中，使平均误码率Pe尽可能小的情况下，可达到的信息传输率是多少？–答案：信道容量C•信道编码定理•信道编码定理的证明–证明思路–随机编码方法–联合典型序列§6.3:信道编码定理与联合典型序列-2•信道编码定理：–设R是信息传输的速率，C是离散无记忆信道的信道容量，ε0是任意小的数，则只要RC就总存在码字长为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)是：101)()(MmNiimmXpXP§6.3:信道编码定理与联合典型序列-5•联合ε典型序列–ε典型序列：信源输出的随机序列－奠定了信源编码的基础–联合ε典型序列：两个随机变量的自然扩展，是信道编码的基础–联合ε典型序列定义：–联合AEP定理–定理解释：§6.3:信道编码定理与联合典型序列-6•联合ε典型序列定义：–设（X,Y）是长为N的随机序列对，则在这些随机序列对中满足下列条件的序列对被称为联合典型序列式中δ是任意小的数，联合典型序列的全体构成联合典型序列集，记做G),(),(1nNnnyxppyx|)()(log|1XHxpN|)()(log|1YHypN|)()(log|1XYHxypN§6.3:信道编码定理与联合典型序列-7•联合AEP定理：–设随机序列对（X,Y)的，则对任意小的数δ0，我们总能找到足够大的N使全体序列对的集合能被分成满足下述条件的集合G及其补集Gc：（1）（2）（3）设（X’，Y’）是相互独立的随机序列对，但它与（X,Y）有相同的边缘分布，即：则：),(),(1nNnnyxppyx1}),{(}),{(GYXPGYXPc))(())((2)1(||2||XYHNXYHNGG)()()},(),{(ypxpyxYXP]3);([]3);([2)1(}),{(2}),{(YXINYXINGYXPGYXP§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)时，，可使Pe0–给出一种译码方法：译码时，取与接收矢量联合典型的码字作为输出，这种译码方法可以保证得到很低的误码率。InputsequenceOutputsequence………………ywiwi+12nH(XY)sequencesthatcanmaptoyM=2nRcodewordsthen0enPRCneP2§6.3:信道编码定理与联合典型序列-9•信道编码定理证明的几点说明–香农只是证明了码的存在性，未给出构造方法–随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现；而且即使找到，码字也是毫无结构的，只能采用查表译码方法，当N很大时，码表的存储量也很难接受§6.4:信道编码的性能界限－1•理论性能极限－－存在性–香农信道编码定理–作用：理论极限、渐进