中南大学信息论与编码课件Inf-T-C-74N

信息论与编码张祖平/ZhangZuping电子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,zpzhang@InformationTheory&Coding第七章抗干扰信道编码2013秋季信息111InfTheory&Coding-张祖平本章主要内容

(MainContent)7.1译码规则7.2译码规则的选择准则7.3信道编码的编码原则7.4抗干扰信道编码定理7.5分组码及其检纠能力7.6线性分组码的代数结构7.7简单重复编码7.8香农第二定理7.9标准阵列与译码表7.10检纠能力与一致校验矩阵的关系7.11完备码7.12汉明码与扩展汉明码2013秋季信息112InfTheory&Coding-张祖平抗干扰信道编码

实际的通信信道总是存在噪声的干扰，为了兼顾有效性和可靠性，我们往往对无失真信源编码的码字，用有噪信道的输入符号集作为码符号集，再进行一次编码，利用和挖掘信道的统计特性，在保持一定有效性的基础上，提高其抗干扰能力。

2013秋季信息113InfTheory&Coding-张祖平7.1译码规则

在完整的通信过程中，译码规则对通信的可靠性有重大影响。设有噪离散信道的输入符号集，输出符号集，信道的传递概率。由于噪声的随机干扰，信道输入某符号，输出的一般是的某一种变型。根据一定的判决准则，设计一个单值函数是使每一种可能的输出符号与一个唯一的输入符号一一对应。共构成种不同的译码规则。2013秋季信息114InfTheory&Coding-张祖平

在信道输出端收到某符号后正确译码的概率，就应该是信道输出端出现的前提下，推测信道输入符号的后验概率，即同理，错误译码的概率就是其中“”表示除了以外的所有其它可能的输入符号的集合。上式也可改写为

7.1译码规则2013秋季信息115InfTheory&Coding-张祖平

后验概率在信道输出随机变量的概率空间中的统计平均值，即同样，后验概率在信道输出随机变量的概率空间中的统计平均值，即平均错误译码概率是衡量通信的可靠性的标准。7.1译码规则2013秋季信息116InfTheory&Coding-张祖平

由上式可知，平均错误译码概率就唯一地由选择的译码规则所决定，不同的译码规则就有不同的平均错误概率。所以，选择合适的译码规则，就成为降低平均错误译码概率，提高通信有效性的一种可控制的手段。

7.1译码规则2013秋季信息117InfTheory&Coding-张祖平错误概率错误原因：噪声干扰错误概率与信道的统计特性有关，信道的统计特性由信道的传递矩阵来描述。当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确传递概率，哪些是错误传递概率。译码规则错误表现：译码输出≠信源输出通信过程一般并不是在信道输出端就结束了，还要经过译码(或判决)过程才到达消息的终端(收信者)。因此译码过程和译码规则对系统的错误概率影响很大。为了减少错误，提高通信的可靠性，就必须分析错误概率与译码规则，有没有办法控制，能控制到什么程度。87.1译码规则2013秋季信息118InfTheory&Coding-张祖平译码规则的定义设离散单符号信道：输入符号集为输出符号集为制定译码规则就是定义一个单值函数它对于每一个输出符号bj

确定一个惟一的输入符号ai

与其对应。97.1译码规则2013秋季信息119InfTheory&Coding-张祖平译码规则的定义由于s个输出符号中的每一个都可以译成r个输入符号中的任何一个，所以共有

rs

种译码规则可供选择。(见书上例子)若信道输出端接收到的符号为bj

，则译为ai

若发送端发送的是ai则为正确译码；否则为错误译码。定义收到bj条件下译码的条件正确概率（后验概率）为：定义收到bj

条件下译码的条件错误概率（后验概率）为：（e代表任何除ai外可能的输入符号）：107.1译码规则2013秋季信息1110InfTheory&Coding-张祖平译码规则的定义每收到一个符号的平均正确译码概率，是输出随机变量Y的概率空间的统计平均值。每收到一个符号的平均错误译码概率，是输出随机变量Y的概率空间的统计平均值。11在信道传输概率确定情况下，显然，不同的译码规则会出现不同的平均错误译码概率如何选择译码规则，让Perror简写成Pe更小呢？Pright简写成Pr更大呢??7.1译码规则2013秋季信息1111InfTheory&Coding-张祖平7.2译码规则选择准则信源和信道概率复习12

b1b2…bsa1P(b1|a1)P(b2|a1)…P(bs|a1)a2P(b1|a2)P(b2|a2)…P(bs|a2)…….……arP(b1|ar)P(b2|ar)…P(bs|ar)2013秋季信息1112InfTheory&Coding-张祖平最大后验概率准则(最小错误概率准则)要使平均错误译码概率Pe最小，就要平均正确译码概率Pr最大。通过信源先验概率和信道矩阵中条件概率，计算出每个输出符号概率，和每个输出符号判断输入符号的后验概率。后验概率是我们的依据，似乎信源先验概率，信道矩阵中条件概率都与译码规则无直接关系。针对某个bj，选择r个后验概率p(ai/bj)中最大的值时对应的a*，就可以使信道错误概率最小，这种译码规则称“最大后验概率准则”13即选择译码函数：并满足:7.2译码规则选择准则2013秋季信息1113InfTheory&Coding-张祖平平均错误译码概率与平均正确译码概率的计算14因此，使用最大后验概率准则可以让平均错误译码概率最小，而且只取决于给定信源空间和给定信道矩阵，也就是说，信源和信道给定时，通信的可靠性最高程度就已经确定。表示对输入符号集中除F（bj）=a*以外的所有元素求和。7.2译码规则选择准则2013秋季信息1114InfTheory&Coding-张祖平举例：设有一离散信道，其信道矩阵为，当信源X的概率分布为р(a1)＝2/3，р(a2)＝р(a3)＝1/6时，按最大后验概率准则选择译码函数，并计算其平均错误译码概率Pemin．157.2译码规则选择准则a1a2a3b1b2b32013秋季信息1115InfTheory&Coding-张祖平最大似然概率准则16当信源等概分布时，可选择译码函数：并满足：这样定义的译码规则称为最大似然概率准则最大似然译码准则的方法是收到一个bj

后，在信道矩阵的第j列，选择最大的传输概率值所对应的输入符号作为译码输出。最大似然译码准则本身不再依赖于先验概率P(ai)，只依赖于信道传递特性

。但当先验概率为等概率分布时，它使错误概率PE最小。7.2译码规则选择准则2013秋季信息1116InfTheory&Coding-张祖平最大似然概率准则最大后验概率需要求解输出概率和后验概率，计算较为复杂。当信源个符号是等概率输入时可以进一步简化计算过程。已知信道的传递概率P(bj|ai)与输入符号的先验概率P(ai)。17后验概率的比较可以转化为先验概率和传输概率乘积的比较：当输入为等概率时，可以转化为传输概率的比较：7.2译码规则选择准则2013秋季信息1117InfTheory&Coding-张祖平输入等概率情况下：平均错误译码概率的计算18上式表明在等先验概率分布情况下，译码错误概率可用信道矩阵中的元素P(bj|ai)求和（不包括每列对应于F(bj)=a*的那一项）来表示。7.2译码规则选择准则2013秋季信息1118InfTheory&Coding-张祖平举例：输入为a1，a2，a3，输出为b1，b2，b3，输入等概率1/3，使用最大似然概率准则设计译码规则，求其平均错误译码概率。19第一列0.5最大，所以b1对应a1第三列0.5最大，所以b3对应a2第二列值一样，所以b2可以对应任意一个，由于b1和b3有确定对应，所以b2对应a3计算技巧：去掉信道矩阵中每列最大的值，然后余下的元素相加，并乘上1/r7.2译码规则选择准则2013秋季信息1119InfTheory&Coding-张祖平练习接前面例题，还是输入等概率分布，如果译码规则如下，求平均错误译码概率。20计算技巧：去掉信道矩阵中每列被译码的值，然后余下的元素相加，并乘上1/r7.2译码规则选择准则2013秋季信息1120InfTheory&Coding-张祖平练习接前面例题，输入概率分布如下，如果译码规则按照最大似然概率规则得到如下，求平均错误译码概率。21计算技巧：去掉信道矩阵中每行被译码的值，每行乘以p(ai)，各行结果相加7.2译码规则选择准则2013秋季信息1121InfTheory&Coding-张祖平练习接前面例题，输入概率分布如下，如果译码规则按照最大后验概率规则，求译码规则，求平均错误译码概率。227.2译码规则选择准则2013秋季信息1122InfTheory&Coding-张祖平练习23所以，输入不是等概分布时最大似然译码准则的平均错误概率不是最小。7.2译码规则选择准则2013秋季信息1123InfTheory&Coding-张祖平7.3信道编码的编码原则

对于给定的信源来说，要使其最小平均错误译码概率继续下降，就必须进行信道编码，以改变信道的统计特性，挖掘和利用信道统计特性对提高通信可靠性的潜力。在消息数和码字长度保持不变的条件下，引入“汉明距离”的概念，并以此来挑选码字。2013秋季信息1124InfTheory&Coding-张祖平若有则选择译码函数这就是用汉明距离来表述的最大似然译码准则。同理可得或7.3信道编码的编码原则2013秋季信息1125InfTheory&Coding-张祖平经过分析可得：1.要尽量缩短与之间的汉明距离；2.要尽量扩大与之间的汉明距离。7.3信道编码的编码原则2013秋季信息1126InfTheory&Coding-张祖平7.4抗干扰信道编码定理

设某信道有个输入符号，个输出符号，信道容量为。当信道的信息传输率时，只要码长足够长，总可以在输入集合中（含有个长度为的码符号序列），找到（，为任意小的正数）个码字，分别代表个等可能性的消息，组成一个信道编码，选择相应的译码规则，使信道输出端的译码过程的最小平均错误译码概率达到任意小。这就是抗干扰信道编码定理，又称之为香农第二定理。2013秋季信息1127InfTheory&Coding-张祖平

抗干扰信道编码定理的逆定理，从相反的角度进一步揭示了抗干扰信道编码定理的内涵。在叙述和证明抗干扰编码定理的逆定理之前，有必要从一般的角度阐明平均错误译码概率与信道疑义度的内在联系。著名的费诺（Fano）不等式

7.4抗干扰信道编码定理2013秋季信息1128InfTheory&Coding-张祖平

抗干扰信道编码定理的逆定理表明，若某信道有个输入符号、个输出符号、信道容量为。如选用码字个数(消息数)，即时，则无论码长有多长，也不可能找到一种编码，使其平均错误译码概率任意小。实际上，当选用码字数（消息数），即有时，信道的信息传输率（码率）这表明，信道信息传输率已超过了信道容量，这是不可能的。逆定理告诉我们，要使信道的信息传输率超过信息容量，而有又要求无错误地传输消息，这是不可能的。同时也给我们指明，信道容量是在信道中可靠地传输信息的最大信息传输率。7.4抗干扰信道编码定理2013秋季信息1129InfTheory&Coding-张祖平7.5分组码及其检纠能力一、分组码的基本概念

由个长度为的符号序列组成的集合，构成一个分组码，代表个长度为的信息序列（信息）。分组码的编码问题，实质上就是如何从总数为个长度为的序列中挑选个长度为的序列作为码字的问题。

2013秋季信息1130InfTheory&Coding-张祖平二、分组码的检错、纠错能力由码符号集组成的码字间汉明距离具有的一般特性（1）具有自主性（2）具有对称性（3）满足三角不等式

7.5分组码及其检纠能力2013秋季信息1131InfTheory&Coding-张祖平

运用以上三大特性剖析由组成的分组码的检纠能力与码字间汉明距离之间的内在联系：1.分组码能发现个错误的充分必要条件是分组码的个码字中任意两个码字个之间的汉明距离2.分组码能自动纠正个错误的充分必要条件是分组码中任意两个码字和之间的汉明距离

7.5分组码及其检纠能力2013秋季信息1132InfTheory&Coding-张祖平3.分组码能自动纠正个错误，同时又能发现个错误的充分必要条件是分组码中任意两个码字和之间的汉明距离把由组成的分组码的个长度为的码字间的个汉明距离的最小值称之为这个分组码的最小汉明距离。

7.5分组码及其检纠能力2013秋季信息1133InfTheory&Coding-张祖平由以上讨论，可得一下结论：1.若，则分组码具有发现个错误的检错能力；2.若，则分组码具有自动纠正个错误的纠错能力；3.若，则分组码具有自动纠正个错误，同时发现个错误的检、纠错误能力。

7.5分组码及其检纠能力2013秋季信息1134InfTheory&Coding-张祖平7.6线性分组码的代数结构

1.群

2.子群

3.域

4.线性空间及子空间

2013秋季信息1135InfTheory&Coding-张祖平7.7简单重复编码一般信道传输时都会产生错误，而错误概率与译码规则有关。但当信道给定即信道矩阵给定，不论选择什么译码规PE总不会趋于零从而消除错误，那么如何减少错误概率呢？下边讨论通过编码方法来降低错误概率，以最简单的简单重复编码（随机编码）为例，针对最简单等概率二元对称信道。36例：对于二元对称信道译码规则：平均错误概率(假设输入等概时)：01010.990.990.010.012013秋季信息1136InfTheory&Coding-张祖平最简单的思路：冗余，重复待发送的内容，出错了重发37没有使用的码字001010011100101110用作消息的码字000111输出端接收序列000001010011100101110111二元对称信道的三次扩展信道01011-P=0.990.990.01P=0.017.7简单重复编码2013秋季信息1137InfTheory&Coding-张祖平这时信道矩阵为：假设输入等概率，根据最大似然译码准则，可得译码函数为：F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=11138平均错误概率，大大减小，降低了两个数量级7.7简单重复编码2013秋季信息1138InfTheory&Coding-张祖平利用重复发送信源消息进行信道编码，从而降低译码错误概率，这种信道编码方式称为“简单重复编码”也叫“随机编码”进一步分析信道随机编码如果我们不选择000和111呢？，假设我们选择000代表0，001代表1译码规则通过最大似然译码准则可以得到：F(000)=000F(010)=000F(100)=000F(110)=000F(001)=000F(011)=001F(101)=001F(111)=001为什么第二种译码规则的错误率会提升呢？这表明扩展后8个符号中选择2个也是有技巧的。000和111任何一位变化，都非常明显，而第二次选择的000和001太“像”了。再思考一下，如果我们选001和110作为输入，平均错误译码概率会如何？为什么呢？397.7简单重复编码2013秋季信息1139InfTheory&Coding-张祖平汉明Hamming距离。长度为n的两个符号序列(码字)ai和bj之间的距离是指ai和bj之间对应位置上不同码元的个数，用符号D(ai，bj)表示。这种码字距离通常称为汉明距离。在某一码书C中，任意两个码字Ci和Cj的汉明距离的最小值称为该码的最小汉明距离。在任一码书中，码的最小距离dmin与该码的译码错误概率有关。407.7简单重复编码2013秋季信息1140InfTheory&Coding-张祖平41码A码B码C码D码字00011100001110111000000101010000000011011011111010消息数M2444最小汉明距dmin3213错误概率(最大似然译码规则)dmin越大，Pe越小，在M相同的情况下，dmin越大，Pe也越小。码书中最小距离大，受到干扰后不容易把一个码字错为另一个码字，因而错误概率小。所以在选择编码规则时，要尽量使码字之间距离越大越好。7.7简单重复编码2013秋季信息1141InfTheory&Coding-张祖平最小汉明距离译码准则从码书中选择输入时用dmin最大为准则，那么得到输出时呢？

若ai和bj

之间的距离为D(ai,bj)记为Dij，它表示传输过程中ai传输到bj

，有Dij

个位置发生了错误，(n-Dij)个位置没有错误。通常（p＜1/2时），Dij越大，P(bj/ai)越小，Dij越小P(bj/ai)越大将最大似然译码准则与汉明距离连系起来了42当信源等概分布时，可选择译码函数：并满足：这样定义的译码规则称为最大似然概率准则7.7简单重复编码2013秋季信息1142InfTheory&Coding-张祖平最小汉明距离译码准则最大似然译码准则可用汉明距离表示为选择译码函数使之满足即满足它称为最小距离译码准则。在二元对称信道中它等价与最大似然译码准则，也就是收到一个码字后，把它译成与它最近的输入码字，这样可以使平均错误概率最小。437.7简单重复编码2013秋季信息1143InfTheory&Coding-张祖平练习设某二元码为C={11100,01001,10010,00111}，计算此码的最小距离

dmin；采用最小距离译码准则，试问接收序列10000，01100和00100应译成什么码字？44（1）此码字的最小距离dmin=3；（2）采用最小距离译码，

10000应译成10010；

01100应译成11100；

00100译成11100、00111均可；7.7简单重复编码2013秋季信息1144InfTheory&Coding-张祖平7.8香农第二定理信息传速率很显然有效性和可靠性是一对矛盾。以简单重复编码为例，重复次数多，N变大，错误译码概率就会变小，可是R也会变小。以简单重复编码为例，M的大小也会影响R。M大，R会变大，但是错误译码概率也会变大。如何选择合适的M和N，也就是信道编码和译码方法，让R保持在一定水平，同时由能让Pe尽量小？从理论上这是可能的，这就是香农第二基本定理。452013秋季信息1145InfTheory&Coding-张祖平香农第二定理（抗干扰信道编码定理）当信道的信息传输率R小于信道容量C时，只要信道编码的码长N足够长，总可以在输入集合RN个码字中找到M个码字，组成一个信道编码，选择相应的译码规则，使𝑷𝒆达到任意小。也就是说：总可以找到一种抗干扰信道编码，只要码长N够长，他的最小平均错误译码概率𝑷𝒆可以达到任意小，信道的信息传输率R可以无限接近于C。香农第二定理（抗干扰信道编码定理）逆定理当信息传输率R>C信道容量时，则无论码长N多长，总找不到一种编码使信道输出端的平均错误译码概率达到任意小。467.8香农第二定理2013秋季信息1146InfTheory&Coding-张祖平香农第二定理（抗干扰信道编码定理）这个定理是一个存在定理，它没有给出一个具体可构造的编码方法，它有助于指导各种通信系统的设计有助于评价各种系统及编码的效率。在它的指导下，人们设计出了很多有效又可靠的信道编码方法。常用的信道编码有线性分组码汉明码循环码卷积码477.8香农第二定理2013秋季信息1147InfTheory&Coding-张祖平7.9标准阵列与译码表

上表构成的阵列，称为线性分组码的“标准阵列”。2013秋季信息1148InfTheory&Coding-张祖平

把标准阵列中个陪集首和由所得相对应的伴随式按相对应的位置排成下表所示的“译码表”。

陪集首

伴随式7.9标准阵列与译码表2013秋季信息1149InfTheory&Coding-张祖平“译码表”译码的方法只须存储个陪集首和相应的个伴随式。而“标准阵列”译码方法必须存储个重矢量，特别当足够大时，这种译码方法就会显得很繁琐，所需译码设备就可能十分庞大。显然，“译码表”译码方法比“标准阵列”译码方法简单得多，而且易于具体操作。7.9标准阵列与译码表2013秋季信息1150InfTheory&Coding-张祖平

一般以“译码表”中各陪集首的总重量作为衡量一个线性分组码的可靠性高低的标准。总重量越小，最小平均错误译码概率越小；总重量越大，最小平均错误译码概率就越大。我们把结构相同的各种线性分组码中陪集首总重量最小的线性分组码，称为这种结构的线性分组码中的“最优码”。7.9标准阵列与译码表2013秋季信息1151InfTheory&Coding-张祖平7.10检纠能力与一致校验矩阵的关系

以为一致校验矩阵的线性分组码能纠正个错误的充分必要条件是，中任意列线性独立。结论表明，线性分组码的一致检验矩阵的结构，与线性分组码的最小汉明重量存在内在的联系。由一致校验矩阵的结构特点，可直接判断相应的线性分组码具有的检纠能力。

2013秋季信息1152InfTheory&Coding-张祖平7.11完备码

由于线性分组码用“译码表”译码时，能纠正的错误就是各种陪集首，所以，如果小于或等于个错误的全部错误图样数正好等于陪集首的总数，即那么，陪集首就是小于或等于个错误的全部错误图样。我们把满足上式的线性分组码称为“完备码”。

2013秋季信息1153InfTheory&Coding-张祖平