1、主要内容主要内容 信道编码的概念信道编码的概念 香农第二定理香农第二定理 差错控制差错控制 信道编码方法信道编码方法l第5章结论：在无噪无损信道上，只要对信源的输出进行恰当的编码，总能以信道容量C无差错地传输信息。l实际信道都有噪声干扰，本章研究香农第二香农第二定理，即通信的可靠性问题定理，即通信的可靠性问题。包括：1.怎么使有噪信道中消息传输错误达到最少怎么使有噪信道中消息传输错误达到最少?2.在有噪信道中无错误传输的可达的最大信息在有噪信道中无错误传输的可达的最大信息传输率是什么传输率是什么?6.1 信道编码的概念信道编码的概念信道编码概述信道编码概述 问题引出问题引出 什么是信道编码什么
2、是信道编码 信道编码的作用信道编码的作用 信道编码的三种情形信道编码的三种情形 信道编码的实质信道编码的实质 信道编码概述问题引出 互信息能告诉我们什么？互信息能告诉我们什么？随机变量随机变量X,Y统计意义上的依存程度统计意义上的依存程度 可以获得的信息量可以获得的信息量 不能：所得信息能否可靠地确定信道输入？不能：所得信息能否可靠地确定信道输入？无噪信道编码能告诉我们什么？无噪信道编码能告诉我们什么？无噪无损信道，只要对信源输出进行适当编码，无噪无损信道，只要对信源输出进行适当编码，总能以最大信息传输率，无差错的传输信息。总能以最大信息传输率，无差错的传输信息。但是：一般信道总存在噪声或干扰
3、，信息传输但是：一般信道总存在噪声或干扰，信息传输会造成损失会造成损失信道编码概述问题引出 实际通信中人们对传输要求什么？实际通信中人们对传输要求什么？传输信息量大传输信息量大 传输可靠传输可靠 提出的与信道传输有关的问题：提出的与信道传输有关的问题：如何能使信息传输后发生的错误最少？如何能使信息传输后发生的错误最少？错误概率与那些因素有关？错误概率与那些因素有关？有无办法控制？有无办法控制？能控制到什么程度？能控制到什么程度？无误传输可达的最大信息率是多少？无误传输可达的最大信息率是多少？信道编码概述信道编码概述什么是信道编码什么是信道编码 通信系统模型通信系统模型 信道编码：信道编码：从消
4、息到信道波形或矢量的映射从消息到信道波形或矢量的映射 希望通信系统与信道统计特性相匹配的编码希望通信系统与信道统计特性相匹配的编码信源编码信道编码信道信道译码信源译码消息集中一个元素信道波形空间中的一个点失真后的波形恢复的消息引入失真消息到波形的映射判断是消息集中的哪个元素信道编码概述信道编码概述信道编码的作用信道编码的作用 信道编码的作用：信道编码的作用：在资源、可靠性和传信在资源、可靠性和传信量量之间选择一个好的工作点（有时还要考之间选择一个好的工作点（有时还要考虑延时）。虑延时）。资源资源指的是提供信息传输所付出的代价指的是提供信息传输所付出的代价 包括频率、时间、空间、功率等。但不包括
5、实包括频率、时间、空间、功率等。但不包括实现复杂度现复杂度 一个好的编码就是要充分利用资源，传递尽可一个好的编码就是要充分利用资源，传递尽可能多的信息能多的信息信道编码概述信道编码概述三种情形三种情形 给定资源和可靠性要求，通过信道编码尽量提给定资源和可靠性要求，通过信道编码尽量提高传输速率高传输速率 给定对信息传输的速率和可靠性要求，通过信给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销道编码尽量减少资源开销 给定资源和传输速率，通过编码提高可靠性给定资源和传输速率，通过编码提高可靠性信道编码概述信道编码概述编码的实质编码的实质 利用冗余降低差错概率利用冗余降低差错概率 将所有
6、可能的输入信息（消息）映射到信将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。合要小于（包含于）全信道空间中。信道编码概述信道编码概述信道编码的基本分类信道编码的基本分类 按码的结构分按码的结构分:线性码线性码 线性分组码（群码）线性分组码（群码）卷积码（线性树码）卷积码（线性树码）非线性码非线性码 按抗干扰模式分按抗干扰模式分 抗随机差错码抗随机差错码 抗突发差错码抗突发差错码 按编译码理论所用数学工按编译码理论所用数学工具分具分 代数码代数码 几何码几何码 组合码组合码 按对错误的处理方式分按对错误
7、的处理方式分 检错码检错码 纠错码纠错码 错误：译码输出 信源输出 产生原因：噪声干扰 研究目的：减少错误，提高可靠性 研究途径：信道的传递矩阵信道统计 特性错误概率1 1 译码规则译码规则 错误概率与译码规则错误概率与译码规则 错误概率错误概率PE与什么有关与什么有关 信道的统计特性：当确定了输入和输出对应关系后，信道的统计特性：当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确传递概率，哪些是也就确定了信道矩阵中哪些是正确传递概率，哪些是错误传递概率。错误传递概率。译码规则：译码规则：通信过程一般并不是在信道输出端就结束通信过程一般并不是在信道输出端就结束了，还要经过译码了，还要
8、经过译码(或判决或判决)过程才到达消息的终端过程才到达消息的终端(收收信者信者)。因此译码过程和译码规则对系统的错误概率。因此译码过程和译码规则对系统的错误概率影响很大。影响很大。译码规则的选择依据译码规则的选择依据 最大后验概率准则理想最大后验概率准则理想 最大似然准则实用最大似然准则实用（一）译码规则XYa1a2arb1b2bsp(bj/ai)ijabF)(译码函数sjri,.,2,1,.,2,1译码规则：raaabF211)(rsaaabF21)(rs种译码规则pppp01010)1(0)0(FF1)1(0)0(FF0)1(1)0(FF1)1(1)0(FF422sr译码规则编码编码CAB
9、21435发送波形集合接收波形集合PA2PA1PA3PA4PA5CAB213消息集合编码集合译码译码信道译码An1243w4w3w1w2xxxAn 是接收空间w w1,w w2,是发送的码字 围绕每个码字有一个译码域i 如果接收的码字在 i中，就认为发送的是码字 w wi 发生错误发生错误 一般,An中 存在一些不属于任何 i的区域 有时接收码字会被映射到错误的i，进而被译成错误的 w wi 正确译码不知如何译码译码错误 问题：在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分 划分接收矢量空间的准则译码器的译码准则（二）准则一：最大后验概率译码准则(最小平均
10、错误概率准则)ijabF)(输入ai正确译码输入为除ai以外的(r-1)种任何符号错误译码正确译码的概率：rjp/)(jijbabFp错误译码的概率：ejp/jbeprjp1/)(1jijbabFp平均正确译码概率：sjrjjrpbpP1)(sjjijjbabFpbp1/)()(平均错误译码概率：sjejjEpbpP1)(/)(1)(1sjjijjbabFpbpsjjijjbabFpbp1/)()(1最大后验概率译码准则(最小错误概率准则)riijijabpapbp1)/()()(riijiijijiabpapabpapbap1)/()()/()()/(rjrjjbapbapbap)/()/(
11、)/(21ribapbapjij,.,2,1)/()/(*)(abFjmineEPP sjjijEbapbpP1min)/(1)(sjjjsjjbapbpbp11)/()()(sjjsisjjibapbap1*11)()(即把每个输出符号均译成具有最大后验概率的那个输入符号的译码函数使信道错误概率最小。sjijiEbapP1*min)(sjiijiabpap1*)/()(ribapbapjij,.,2,1)/()/(*)(abFj)/()()/()(ijijabpapabpap等概信源)/()/(ijjabpabp*)(abFj译码规则最大似然准则)()/()()()/()(jijijjbpa
12、bpapbpabpap)/()/()/()/()/()/()/()/()/(21222211121121rsrrssrabpabpabpabpabpabpabpabpabpaaaP1b2bsb)1()1(srsjiijiEabpapP1*min)/()(sjiijabpr1*)/(1平均错误概率的计算sjijiEbapP1*min)(sjiijiabpap1*)/()(1.求平均错误概率步骤（按列计算）：求联合概率矩阵 P(ai)P(bj|ai)中每列除去 F(bj)=a*所对应的 P(a*bj)以外所有元素之和；再对上述结果求和。2.采用逐行计算方法：求矩阵 P(ai)P(bj|ai)各行中
13、 F(bj)=a*所对应的 P(a*bj)以外所有元素之和；再对上述结果求和。1*1*(i)()*11()()(/)()(/)()jjsrEijijijY aiY abrrijiF baieijiPp abp a p bap ap bap a p对应的若先验概率P(ai)=1/r，有：即在等先验概率分布情况下，译码错误概率可用信道矩阵中的元素P(bj|ai)和（除去每列对应于F(bj)=a*的那一项）来表示。(i),*11(/)EjieY XaXPp baprr 关于最大似然比译码准则的说明 l 若输入符号等概率，等同最小平均错误概率准则。l 直接从信道矩阵的传递概率中去选定译码函数：收到bj
14、后，译成信道矩阵P的第j列中最大那个元素所对应的信源符号。l 本身不再依赖于先验概率 P(ai)。但当先验概率为等概率分布时，它使错误概率PE最小。最大后验概率译码准则&最大似然译码准则 输入等概时二者是一致的 此时：)|()|(*)(1*abpbapbSp)|(max)|(max*)(1*abpbapbsprr)|(max*)(1abprbsp例：5.03.02.04.03.03.02.03.05.0P31)()()(321apapap求译码规则和平均错误译码概率。解：5.03.02.04.03.03.02.03.05.0P11)(abF33)(abF22)(abF译码规则)4.02.0()
15、3.03.0()2.03.0(31minEP57.02 2 编码方法编码方法 上一节结论：上一节结论：l 消息通过有噪信道传输时会发生错误消息通过有噪信道传输时会发生错误l 错误概率与译码规则有关错误概率与译码规则有关 噪声干扰：噪声干扰：破坏了信号的内部结构产生畸变破坏了信号的内部结构产生畸变而造成信息的损失。而造成信息的损失。提高信号抗噪声干扰能力：提高信号抗噪声干扰能力：改造信号使其内部结改造信号使其内部结构具有更强的规律性或相关性，当信号的部分结构具有更强的规律性或相关性，当信号的部分结构被破坏时，仍能根据信号原有的内在规律和相构被破坏时，仍能根据信号原有的内在规律和相关性来发现甚至纠
16、正错误，恢复原来的信息。关性来发现甚至纠正错误，恢复原来的信息。错误概率与编码错误概率与编码 如何在信息传输率一定的前提下使如何在信息传输率一定的前提下使PE0 实际经验：重复发送可以使实际经验：重复发送可以使PE减小减小 重复次数重复次数N很大时，可以使很大时，可以使PE0 但是：信息传输率降低但是：信息传输率降低 信道编码定理：信道编码定理：R一定时，可以找到一种编码一定时，可以找到一种编码方法使方法使PE相当低相当低 引入概念：码字距离引入概念：码字距离编码方法010199.0p01.0pppp 1 ppppppP10101)1(0)0(FFEPsjiijEabprP1*min)/(1)
17、(21pp210 重复码010199.0p01.0ppBSC无记忆321XXXXn321YYYYn11100021823nrM=2823nS11111010101110001000100087654321vcm正确译码正确译码正确译码错误译码错误译码正确译码正确译码正确译码0001011100000000011100011111111100000101001110010111011100000000000011111111111100001111译码状态译码消息 译码码字 接收分组 发送码字信息 mc”)/()/()/()/()/()/(28222118121121ppppppP1283222
18、22233222222321ppppppppppppppppppppppppppppP12834567pp 21111)111()110()101()011(000)100()010()001()000(FFFFFFFFsjiijEabprP1*min)/(1233 ppp 4103自动纠正一位错nMRlog比特/码符M是输入消息(符号)的个数logM表示消息集在等概率条件下每个消息(符号)携带的平均信息量(比特)n是编码后码字的长度(码元的个数)若传输每个码符号平均需要 t 秒钟，则编码后每秒钟传输的信息量:l对上述重复编码方法可计算得，当n1(无重复)，M2，设t1秒时 l当n3(重复三次
19、)，M2，设t1秒时 log(/tMRnt比特 秒)log1(/1(/tMRnR比特 码符号)比特 秒)log1(/31(/3tMRnR比特码符号)比特秒)ln5，M2时 ln11，M2时log1(/51(/5tMRnR比特码符号)比特秒)log1(/111(/11tMRnR比特 码符号)比特 秒)由此得PE和R的关系，如图所示。它表明：尽管可使PE降低很多，但同时也使信息传输率降得很低。问题：能否找到一种更好的编码方法，使PE相当低，而R却保持在一定水平？即有噪信道编码定理。简单重复编码方法使信息传输率降低的原因 l在未重复编码以前，输入端是二个消息的集合。假设为等概率分布则每个消息携带的信
20、息量是 logM=1(比特符号)。l简单重复(n=3)后，可以把信道看成是三次无记忆扩展信道。这时输入端有8个二元序列可以作为消息(a 1,a 8)，但我们只选择了二个二元序列作为消息，M2。这样每个消息携带的平均信息量仍是1比特。而传送一个消息需要付出的代价却是三个二元码符号，所以R就降低到 1/3(比特码符号)。如果在扩展信道的输入端把8个可能作为消息的二元序列都作为消息，M8，则每个消息携带的平均信息量就是3比特，而传递一个消息所得的符号数仍为三个二元码符号，则R就提高到 1（比特码符号）。这时的信道如下图所示。用做消息 输出端 的码字 接收序列 1=000 000=1 2=001 00
21、1=2 3=010 010=3 4=011 011=4 5=100 100=5 6=101 101=6 7=110 110=7 8=111 111=8 二元对称信道的 三次扩展信道 这时只能规定接收端8个输出符号序列 j与 i 一一对应。这样，只要符号序列中有一个码元符号发生错误就会变成其他所用的码字，造成译码错误。只有符号序列中每个符号都不发生错误才能正确传输。错误概率:)01.0(103123ppPE 还存在另外一个问题，M=4时，有70种选取方法，而选取方法不同，错误率也不同。我们比较下面两种选取方法：第一种：000 011 101 110 第二种：000 001 010 100 可以计
22、算得第一种方法的错误率为 第二种方法的错误率为22*1022.28*10 比较可知，第一种方法好，仔细观察发现，在第一种方法中，如果000有一位出错，我们就可以判定出错了；而在第二种方法中，如果000中任何一位出错，就变成了其他的合法的码字，我们无法判断是否出错。再仔细观察，发现第二种方法中，码字之间太“象”了，或者说太“近”了。我们再讨论一个例子，取M4，n5，这4个码字按如下规则选取：设输入序列为:12345()iiiiiiaaaaaa满足方程：31241512iiiiiiiiaaaaaaaa若译码采取最大似然准则：25R 000000000100010001000000001000100
23、001000100011011010110001111010010110100101111011110001110101111011010101100111011111111001110011010100110101101111000111101101010010010100101111001 此码能纠正所有码字中一位码元错误，也能纠正其中两个两位码元的错误。543252EPpp pp p5432411(52)7.8 10EEPPpp pp p 我们引进这样一个概念：汉明距离。在二元码中：1(,)nijikjkkD 如：101111i111100j则(,)3ijD 在某一码书中，任意两个码字的
24、汉明距离的最小值称为该码C的最小距离。minmin(,)ijijdD C CCC我们来讨论前边的5种码的距离：码A码B码C码D码E码字01000111000011101110000001010100000 001010 011100 101100 111消息数M22448最小距离dmin13211信息传输率R11/32/32/31错误概率43*1022*1022.28*1023*10210 很明显，越大，越小，在M相同的情况下也是一样。mindEP 在二元对称信道的情况下，译码规则可以如下：*()jF ba选择 使之满足*(,)(,)jijiDD 它称为最小距离译码准则，它等价与最大似然译码准
25、则，也就是收到一个码字后，把它译成与它最近的输入码字，这样可以使平均错误率最小。另外，我们应该选择这样的编码方法：应尽量设法使选取的M个码字中任意两两不同码字的距离尽量大。Nkikjkijabpp1)/()/(),(),(.jijiDNDpppppp),(),(jijiDNDpp),(),(*)/(jjDNDjppp),(),()/(jijiDNDijppp*)(jF),(),(*jijDDnjjnsjDNDsjjEppMpMP1),(),(1*min11)/(11*njijinsjiDNDsjiijEppMpMP1*),(),(1*min1)/(1l结论结论 在有噪信道中，传输的平均错误概率
26、在有噪信道中，传输的平均错误概率PE与各与各种编、译码方法有关。种编、译码方法有关。l编码选用编码选用M个消息所对应的码字间最小距离个消息所对应的码字间最小距离dmin尽可能大的编码方法；尽可能大的编码方法；l译码采用将接收序列译码采用将接收序列bj译成与之距离最近的译成与之距离最近的那个码字那个码字a*的译码规则；的译码规则；则只要码长则只要码长n足够长时，合适地选择足够长时，合适地选择M个消个消息所对应的码字，就可以使错误概率很小，息所对应的码字，就可以使错误概率很小，而信息传输率保持一定。而信息传输率保持一定。对两种译码准则的评述 l最大后验概率准则具有很好的直观合理性。收到y的条件下，
27、最可能发送的是哪个码字，就认为发送的是哪个码字。最大似然概率准则（最小距离准则）所具有的直观合理性弱一些。发送哪个码字的条件下，最可能收到y，就认为发送的是哪个码字。l最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：前者只需要看哪个码字与y的Hamming距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。两种准则都可以用在没有编码（直接发送）情况下的纠错译码。6.2 6.2 信道编码定理信道编码定理 信道编码定理引出 问题：在有噪信道中，使平均误码率PE尽可能小的情况下，可达到的信息传输率是多少？答案：信道容量C 信道编码定理 信道编码定理的证明
28、 证明思路 随机编码方法 联合典型序列 信道编码定理（香农第二定理）：设R是信息传输的速率，C是离散无记忆信道的信道容量，00是任意小的数，则只要RCRC就总存在码字长为n n，码字数为M=2M=2nRnR的分组码使译码的平均差错概率P PE E。信道编码定理的证明l 思路：通常思路：先构造一个理想的好码，并定义一种译码准则，计算该好码经过译码后的误码率 问题：构建极其复杂且无具体方法 N值很大时，误码率计算困难 香农采取的方法:用随机编码方法得到所有可能码的集合 在其中随机选择一个码作为信道码 利用大数定理计算在集合平均意义上的该码性能 利用联合典型序列译码 香农采取的方法评价：不很严格，不
29、是最优，但便于理论分析 随机编码方法在后来严格的证明中一直被采用l随机编码方法：对每一个消息 m(m=0,1,M-1),编码为xm=(xm1xm2xmn)其中：xmi (i=1,2,n)是按照输入字母的概率随 机选取，从而得到全部M=2nR个码字，组 成码集C（x1x2.xM-1)l随机编码方法产生某一特定码字的概率P(Xm)是：101)()(MmNiimmXpXPl 联合联合典型序列典型序列典型序列：典型序列：信源输出的随机序列奠定了信源输出的随机序列奠定了信源编码的基础信源编码的基础联合联合典型序列：典型序列：两个随机变量的自然扩展，两个随机变量的自然扩展，是信道编码的基础是信道编码的基础
30、 联合联合典型序列定义：典型序列定义：联合联合AEPAEP定理定理定理解释：定理解释：联合 典型序列的定义 l若若x为为典型序列典型序列,则则:|-logP(x)/n-H(X)|,Xn空间中的空间中的典典型序列集型序列集 记记 为为G n(X)l若若y为为典型序列典型序列,则则:|-logP(y)/n-H(Y)|,Yn空间中的空间中的典型典型序列集序列集 记记 为为G n(Y)l若若(x,y)满足满足:|-logP(xy)/n-H(XY)|,则称则称(x,y)为联合为联合典典型序列型序列,XnYn联合空间中的联合空间中的典型序列集典型序列集 记为记为G n(XY)。lG n(XY)=(x,y)
31、Xnx Yn；|-logP(x)/n-H(X)|l|-logP(y)/n-H(Y)|；|-logP(xy)/n-H(XY)|0，我们总能找到足够大的，我们总能找到足够大的N使全体序列对的集合使全体序列对的集合能被分成满足下述条件的集合能被分成满足下述条件的集合G及其补集及其补集Gc：（1）（2）（3）设（）设（X，Y）是相互独立的随机序列对，但它与）是相互独立的随机序列对，但它与（X,Y）有相同的边缘分布，即：）有相同的边缘分布，即：则：则：),(),(1nNnnyxppyx1),(),(GYXPGYXPc)()(2)1(|2|XYHNXYHNGG)()(),(),(ypxpyxYXP3);(
32、3);(2)1(),(2),(YXINYXINGYXPGYXPl联合联合AEP定理的解释定理的解释 两个随机变量情况下，序列两个随机变量情况下，序列Xn,Yn及其联合序列及其联合序列XnYn都具都具有有AEP特性特性 联合典型序列对是高概率序列对联合典型序列对是高概率序列对 联合典型序列对出现概率接近相等，且其和接近于联合典型序列对出现概率接近相等，且其和接近于1 联合典型序列对是一些密切关联的序列对联合典型序列对是一些密切关联的序列对 一般与一般与X对应的对应的Y可能是可能是Y空间的任一个，该定理说明：随空间的任一个，该定理说明：随N的增大，对应的增大，对应X的的Y只能是（只能是（X,Y)典
33、型序列对的典型序列对的Y，取其，取其他他Y的概率的概率0 联合典型序列数目为联合典型序列数目为2NH(XY)，典型典型x,典型典型Y随机组合的空间为随机组合的空间为2NH(X)+H(Y)，联合典型序列占其中约联合典型序列占其中约1/2NI(X;Y)，只是很小的一部分，只是很小的一部分 故：当故：当X的数目的数目0是任意小的数，则只要RC就总存在码字长为n，码字数为M=2nR的分组码使译码的平均差错概率PE。定理证明：设有M2nR个消息，则 1,2nR为消息的标号集。对M中任一码字w，当等概分布时，有 P(w)=2-nR 如果发送w，收端序列为y，根据译码函数：g(y)=w1,2nR 为正确译码
34、；g(y)=w1,2nR w不等于w，则为错误译码。所以 nRnRwewnRwewEPPwPP212121)(对于XN扩展信道，其平均错误概率 因为w的选取是随机的，可设w1，则 Pr(E)=PE1=Pg(y)1/x=x(1)现在的问题是使PE1能否尽可能地最小？nRwewnRCCErPCPPCPEP2121)()()(PE1=Pg(y)1/x=x(1)P(E1C U E2 U E3 U U E2nR)P(E1C)+P(E1)1 ，P(E1C)1P(E1)P(Ei)2-nI(X;Y)-3 所以 PE1 2-nI(X;Y)-3 2-nI(X;Y)-R-3 )(22nRiiEPnRi22 即对于任
35、意小 的 和，当RI(X;Y)时，PE1任意小，所以当RC时，至少存在一种码书（M,n），其错误概率小于或等于平均值。l信道编码定理证明的几点说明 香农只是证明了码的存在性，未给出构造方法 随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现；而且即使找到，码字也是毫无结构的，只能采用查表译码方法，当N很大时，码表的存储量也很难接受l理论性能极限存在性 香农信道编码定理 作用：理论极限、渐进性能l工程实现上的界限构造性 最小距离界限 作用：构造新码、估计新码性能时，说明新码与最好性能的码接近的程度l信道编码的性能界限l 香农理论极限：RC则无论码长n多长，总也找不到一种编码（M=2nR
36、,n）使译码错误概率任意小。根据平均互信息的定义，数据处理定理以及无记忆扩展信道的性质，得出：PE1当RC时，增大n，错误概率远离零值；当 RC时，增大n，错误概率趋于零。nRRC1 这个定理是信道编码的理论依据，可以看出：信道容量是一个明确的分界点，当取分界点以下的信息传输率时，以指数趋进于0；当取分界点以下的信息传输率时，以指数趋进于1；因此在任何信道中，信道容量都是可达的、最大的可靠信息传输率。这个定理是一个存在定理，它没有给出一个具体可构造的编码方法，在它的证明过程中，码书是随机的选取的，它有助于指导各种通信系统的设计，有助于评价各种系统及编码的效率。EPEPl联合信源信道编码定理联合
37、信源信道编码定理 在任意信道中进行数据传输，必须信息传输率在任意信道中进行数据传输，必须信息传输率小于信道容量小于信道容量RH。联合这两个定理，就会有这样地问题：若信源联合这两个定理，就会有这样地问题：若信源通过信道传输，要做到有效和可靠地传输，是否通过信道传输，要做到有效和可靠地传输，是否HC是充分和必要条件。是充分和必要条件。定理 信源信道编码定理 若Sn=(S1S2Sn)是有限符号集的随机序列并满足AEP，又信源S极限熵 C，则错误概率远离零，即不可能在信道中以任意小的错误概率发送这随机序列。HH 从香农第一、第二定理可以看出，要做到有效和可靠的传输信息，我们可以将通信系统设计成两部分的
38、组合，即信源编码和信道编码两部分，首先通过信源编码，用尽可能少的信道符号来表达信源，尽可能减少编码后信源的数据的剩余率，然后针对信道，对信源编码后的数据独立的进行信道编码，适当增加一些剩余度，使能纠正和克服信道中引起的错误和干扰。可以证明，只要满足香农第一定理和第二定理，用两步编码的方法传输信息和一步编码的方法传输信息其效果是一样的。6.3 差错控制概述差错控制概述l错误格式错误格式 将发生错误看成是因为加入了某种将发生错误看成是因为加入了某种“错误格式错误格式”E的的结果。由于随机差错可能发生在结果。由于随机差错可能发生在n长码字的某长码字的某1位、位、某几位，甚至全错，因此其错误格式种类为
39、某几位，甚至全错，因此其错误格式种类为 （只有（只有1个全个全0时的时的E，没有差错），在这，没有差错），在这 个可个可能的错误中，能的错误中，n长码总错误概率为长码总错误概率为21n1(1)nin ibbinPPPi21n错误图样错误图样 在二元无记忆n次扩展信道中，差错的形式也可以用二元序列来描述。设发送C=c1,c2,cn，接收Y=y1,y2,yn，两者的差别:E=CR=e1,e2,en称为错误图样。6.3 差错控制概述差错控制概述l差错控制分类差错控制分类前向纠错前向纠错反馈重发反馈重发混合纠错方式混合纠错方式信息反馈信息反馈l常用的差错控制码常用的差错控制码6.4 信道编码方法信道编
40、码方法 通过在传输的信息码元后增加一些多余通过在传输的信息码元后增加一些多余的码元的码元(称为校验元称为校验元)，纠错编码可以在信息，纠错编码可以在信息损失或错误后还能在接收端恢复原代码。损失或错误后还能在接收端恢复原代码。6.4.1 6.4.1 线性分组码线性分组码 线性码线性码信息码元与校验码元之间呈线性关系。信息码元与校验码元之间呈线性关系。非线性码非线性码信息码元与校验码元之间不存在线性信息码元与校验码元之间不存在线性关系。关系。分组码分组码把信息序列以每把信息序列以每k个码元分组，然后把个码元分组，然后把每组每组k个信息元按一定规律产生个信息元按一定规律产生r个多余的校验元，个多余的
41、校验元，输出序列每组长为输出序列每组长为nk+r，则每一码字的，则每一码字的r个校验个校验元只与本码字的元只与本码字的k个信息冗有关，与别的码字的信个信息冗有关，与别的码字的信息位无关，记为分组码息位无关，记为分组码(n,k)。卷积码卷积码把信息序列以每把信息序列以每ko(通常较小通常较小)个码元分个码元分段，编码器输出该段的校验元段，编码器输出该段的校验元rn-ko不但与本段不但与本段的的ko个信息元有关，而且还与其前面个信息元有关，而且还与其前面m段的信息元段的信息元有关，故记为卷积码有关，故记为卷积码(n，ko，m)。1 基本概念基本概念 线性分组码编码框图如下图所示。编码是在信道输入端
42、2n个n 长的二元序列中找一组2k 个码字，使码字的rn-k个校验元与其k个信息元之间满足一定的线性关系，并使码书中码字间最小距离最大。而译码则采用最大似然译码准则即最小汉明距离译码准则。2 一致一致监督方程和一致监督矩阵监督方程和一致监督矩阵 一致监督方程：确定信息元得到监督元规则的一一致监督方程：确定信息元得到监督元规则的一组方程。组方程。（7,3）线性分组码）线性分组码 码长码长n=7,信息元信息元k=3，检验元，检验元r=n-k=4。C6c5c4为信息元，为信息元，c3c2c1c0为监督码元，监督为监督码元，监督码元由以下方程得出：码元由以下方程得出：一致监督方程。一致监督方程。364
43、2654165054CCCCCCCCCCCCC 信息码组(101)，即C6=1,C5=0,C4=1；由线性方程组得：C3=0,C2=0,C1=1,C0=1；即信息码组(101)编出的码字为 (1010011)。00000000000000000000451562456346CCCCCCCCCCCCC 设码字C=（c6c5c4c3c2c1c0),有：HCT=0T0（0 0 0），0T是0矢量的转置，即满足：为一致监督矩阵。其中：1000110010001100101110001101H1000010000100001I110011111101P4343 线性分组码的生成矩阵线性分组码的生成矩阵
44、是待编码的信息组，是待编码的信息组，G是一个是一个 的矩阵。的矩阵。对每一个信息组对每一个信息组m，由矩阵，由矩阵G都可以求得都可以求得(n,k)线线性码对应的码字。性码对应的码字。由于矩阵由于矩阵 G 生成了生成了(n,k)线性码，称矩阵线性码，称矩阵 G 为为(n,k)线性码的线性码的生成矩阵生成矩阵。例例6.6.nkkkkknmmmGmgggC1210211021mmmmkknk 3 线性分组码的生成矩阵线性分组码的生成矩阵 线性系统码的监督矩阵线性系统码的监督矩阵 H 和生成矩阵和生成矩阵 G 之间可之间可以直接互换以直接互换。例例6.7.rkrSrkkSIPHQIGTkrrk)P(Q
45、4 线性分组码的编码线性分组码的编码(n,k)线性码的编码就是根据线性码的监督矩阵或线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为生成矩阵将长为k的信息组变换成长为的信息组变换成长为n(nk)的的码字。码字。利用监督矩阵构造(7,3)线性分组码的编码电路：设码字矢量为C=(C6C5C4C3C2C1C0)，码的监督矩阵为1000110010001100101110001101H)3,7(4 线性分组码的编码线性分组码的编码 由HCT=0T得4505614562463CCCCCCCCCCCCC 用几何图形来解释，用几何图形来解释，可将码字看成可将码字看成n维空维空间上的一点，则重复间上的一点
46、，则重复码码(3，1)的码字为三的码字为三维空间上的点，如图维空间上的点，如图正方体上八个顶角为正方体上八个顶角为所有八个可能的接收所有八个可能的接收序列，而对角序列，而对角(000)和和(111)正好为发送的两正好为发送的两个码字。个码字。5 线性分组码的最小距离、检错线性分组码的最小距离、检错和纠错能力和纠错能力最小距离最小距离 以码字以码字C为中心，为中心，半径为半径为 t 的汉明的汉明球是与球是与 C 的汉明的汉明距离距离 t 的向量全的向量全体集合体集合 SC(t)。任意两个汉明球任意两个汉明球不相交最大程度不相交最大程度取决于任意两个取决于任意两个码字之间的最小码字之间的最小汉明距
47、离汉明距离dmin。5 线性分组码的最小距离、检错线性分组码的最小距离、检错和纠错能力和纠错能力汉明球 汉明重量 码字重量（汉明重量）(Hamming weight)在二元编码的码字集合中，码字中“1”码元的个数称为这个码字的重量。记为：W()。分组码最小码距与纠检错能力的关系：分组码最小码距与纠检错能力的关系：一个分组码的最小码距为一个分组码的最小码距为dmin，则其纠检错能力为：则其纠检错能力为：l若检测若检测l l个错误，则要求个错误，则要求dminl+1;l若纠正若纠正t个错误，则要求个错误，则要求dmin2t+1;l若 纠 正若 纠 正 t 个 错 误，同 时 检 测个 错 误，同
48、时 检 测 l l 个 错 误，则 要 求个 错 误，则 要 求dmint+l+1;tl;伴随式伴随式/监督子监督子/校验子校验子：6 线性分组码的伴随式线性分组码的伴随式TSR H0TTTSH R()TTTTTSH RHCEH CH E0TTH CTTSH E 伴随式仅与错误图样有关，而与发送的具体码字无关。定义：汉明码是一类能纠正一位错的线性码。汉明码参数 码长：n=2r-1 信息位数：k=2r-r-1 监督位数：r=n-k 最小码距：d=3 汉明码是具有纠一位错能力的完备码6.4.2 6.4.2 汉明码汉明码 汉明码有r 位校验元，就有2r-1个不同的非全零矢量，将其按列排成矩阵，则得一致监督矩阵H。有了矩阵H就可生成码字和进行译码了。汉明码的信息传输率汉明码的信息传输率:当r很大时，信息传输率R 1(比特二元码)。可见汉明码是一种高效率的纠正一位随机错误的分组码。汉明码可以方便地用移位寄存器等硬件或计算机软件来实现。
