线性分组码的编码原理

《通信原理课件》第九章信道编码9.1引言9.2信道编码的基本原理9.3线性分组码9.4循环码9.5卷积码《通信原理课件》9.1引言《通信原理课件》在无记忆信道中，噪声独立随机地影响着每个传输码元，因此接收的码元序列中的错误是独立随机出现的，以高斯白噪声为主体的信道属于这类信道。在有记忆信道中，噪声和干扰的影响往往前后相关，错误成串出现。还有些信道既有独立随机差错也有突发性成串差错，称为混合信道。对不同类型的信道，需要设计不同类型的信道编码，才能收到良好效果。按照信道特性和设计的码字类型进行划分，信道编码可以分为纠独立随机差错码、纠突发差错码和纠混合差错码。本章将只讨论纠独立随机差错码。《通信原理课件》《通信原理课件》本章我们将讨论常见的信道编码和译码的方法。信道编码的数字通信模型如图9-1所示。进入信道编码器的是二进制信息码元序列M。信道编码根据一定的规律在信息码元中加入监督码元，输出码字序列C。由于信道中存在噪声和干扰，接收码字序列R与发送码字序列C之间存在差错。信道译码根据某种译码规则，从接收到的码字R给出与发送的信息序列M最接近的估值序列Mˆ。《通信原理课件》9.2信道编码的基本原理香农的信道编码定理指出：对于一个给定的有扰信道，如果信道容量为C，只要发送端以低于C的信息速率R发送信息，则一定存在一种编码方法，使译码差错概率随着码长的增加，按指数规律下降到任意小的值。这就是说，通过信道编码可以使通信过程不发生差错，或者使差错控制在允许的数值之下。《通信原理课件》9.2.1信道编码的检错和纠错能力信道编码的检错和纠错能力是通过信息量的冗余度来换取的。为了便于理解，先通过一个简单的例子来说明。例如，要传送A和B两个消息，可以用一个二进制码元来表示一个消息，比如“0”码代表A，“1”码表示B。在这种情况下，若传输中产生错码，即“0”错成“1”，或“1”错成“0”，接收端将无法检测到差错，因此，这种编码没有检错和纠错能力。《通信原理课件》如果用两个二进制码元来表示一个消息，有4种可能的码字，即“00”、“01”、“10”和“11”。比如规定“00”表示消息A，“11”表示消息B。码字“01”或“10”不允许使用，称为禁用码字，对应地，用来表示消息的码字称为许用码字。如果在传输消息的过程中发生一位错码，则变成禁用码字“01”或“10”，译码器就可判决为有错。这表明在信息码元后面附加一位监督码元以后，当只发生一位错码时，码字具有检错能力。但由于不能判决是哪一位发生了错码，所以没有纠错能力。《通信原理课件》《通信原理课件》编码中的几个定义在信道编码中，n长码字中非零码元的数目定义为码字的汉明（Hamming）重量，简称码重。例如“10101”码字的码重为3，“01111”码字的码重为4。两个n长码字x，y对应码元取值不同的个数定义为码字的汉明距离，简称码距，用d(x，y)表示。在一种编码中，码字集合中任意两码字间的最小距离，称为该编码的最小汉明距离，简称为最小码距，用mind表示。例如码长n=3的重复码，只有2个许用码字，即000和111，显然mind＝3。《通信原理课件》《通信原理课件》信道编码的效用《通信原理课件》[例9.2.1]《通信原理课件》《通信原理课件》9.2.2信道编码的译码方法《通信原理课件》一、最大后验概率（MAP）译码《通信原理课件》二、最大似然（ML）译码《通信原理课件》三、最小汉明距离译码《通信原理课件》9.3线性分组码线性分组码既是分组码，又是线性码。分组码的编码包括两个基本步骤：首先将信源输出的信息序列以k个信息码元划分为一组；然后根据一定的编码规则由这k个信息码元产生r个监督码元，构成nrk个码元组成的码字。线性码是指监督码元与信息码元之间的关系是线性关系，它们的关系可用一组线性代数方程联系起来。线性分组码一般用符号kn,表示，其中k是每个码字中二进制信息码元的数目；n是码字的长度。《通信原理课件》图9-3(n，k）线性分组码为系统码的结构一个n长的码字C可以用矢量0121,c,c,,ccnnC表示。线性分组码kn,为系统码的结构如图9-3所示，码字的前k位为信息码元，与编码前原样不变，后r位为监督码元。《通信原理课件》9.3.1线性分组码的编码在介绍线性分组码的原理之前，首先我们来看一种简单而又常用的线性分组码——奇偶监督码（也称为奇偶校验码），分为奇数监督码和偶数监督码。无论信息码元有多少，监督码元只有一位。在偶数监督码中，监督码元的加入使得每个码字中“1”的数目为偶数；在奇数监督码中，监督码元的加入使得每个码字中“1”的数目为奇数。《通信原理课件》《通信原理课件》如果0S，则认为无错，反之有错。式（9.3-2）称为监督关系式或校验关系式，S称为监督子或校验子。由于只有一个监督码元，则只有一个监督关系式，S的取值只有两种，只能代表有错和无错这两种信息，不能进一步指明错码的位置。可以推测，如果将监督码元增加一位，则有两个监督关系式，监督子21SS的可能值就有4种组合，故能表示4种不同的信息，如果用其中一种表示无错，则其余3种就可以用来指示一位错码的3种不同位置。同理，监督子rSSS21的可能值就有r2种组合，可以用其中一种表示无错，其余12r种用来指示一个错码的12r个可能的位置。《通信原理课件》线性分组码的编码原理《通信原理课件》《通信原理课件》《通信原理课件》《通信原理课件》《通信原理课件》《通信原理课件》一般地，在kn,线性分组码中，设M是编码器的输入信息码元序列，如果编码器的输出码字C表示为C＝MG（9.3-14）则G为该线性分组码kn,码的生成矩阵。生成矩阵G为nk矩阵。容易看出，任何一个码字都可以表示为生成矩阵的行向量的线性组合。《通信原理课件》《通信原理课件》生成矩阵和监督矩阵的联系《通信原理课件》9.3.2线性分组码的译码《通信原理课件》《通信原理课件》[例9.3.1]《通信原理课件》解：《通信原理课件》9.3.3汉明码汉明码是1950年由Hamming提出的一种能纠正单个错误而且编码效率较高的一种线性分组码。它不仅性能好而且编译码电路非常简单，易于工程实现，因此是工程中常用的一种纠错码。汉明码属于线性分组码，前面关于线性分组码的分析方法全部适用于汉明码。同时汉明码又是一种特殊的kn,线性分组码，它的最小码距3mind，能够纠正一个错码。前面已经指出，如果希望用r个监督码元构造的kn,线性分组码能够纠正一位错码，要求nr12。设n,k线性分组码中4k，为了纠正一位错码，要求监督位数3r。如果取3r，则码字长度7rkn。《通信原理课件》9.4循环码在线性分组码中，有一种重要的码称为循环码。它除了具有线性分组码的一般特点，还具有循环性：若循环码中任一码字的码元循环移位（左移或右移）后仍是该码的一个码字。由于循环码是在严密的现代代数理论的基础上发展起来的，其编码和译码的电路较简单，且它的检、纠错能力较强，目前它已成为研究最深入、理论最成熟、应用最广泛的一类线性分组码。《通信原理课件》《通信原理课件》9.4.1循环码的码多项式循环码可用多种方式进行描述。在代数编码理论中，通常用多项式去描述循环码，它把码字中各码元当作是一个多项式的系数，即把一个n长的码字C＝01321,c,c,,c,ccnnn用一个次数不超过（n-1）的多项式表示为012211cxcxcxcxCnnnn(9.4-1)称xC为码字C的码多项式，显然C与xC是一一对应的。《通信原理课件》多项式的按模运算《通信原理课件》《通信原理课件》9.4.2循环码的生成多项式和生成矩阵《通信原理课件》《通信原理课件》《通信原理课件》[例9.4.1]《通信原理课件》9.4.3循环码的检错和纠错《通信原理课件》9.4.4循环码的编码和译码电路循环码最引人注目的特点有两个：一是由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法；二是用反馈线性移位寄存器可以很容易地实现其编码和监督子的计算。《通信原理课件》一、循环码的编码电路《通信原理课件》图9-4（7，4）循环码的编码电路《通信原理课件》二、循环码的译码电路《通信原理课件》图9-5（7，4）循环码的译码电路示意图《通信原理课件》9.5卷积码线性码可以分为分组码和卷积码。卷积码，又称连环码，由埃里亚斯(Elias)于1955年最早提出，它是一种非分组码。不同于分组码之处在于：在分组码中，监督码元仅与本组的信息码元有关；而在卷积码中，监督码元不仅与本组的信息码元有关，而且也与其前m组的信息码元也有关,卷积码一般用,mkn,00表示。称m为编码存贮，它表示输入信息组在编码器中需存贮的单位时间。称Nm1为编码约束度，说明编码过程中互相约束的码段个数。称10mnnc为编码约束长度，说明编码过程中互相约束的码元个数。《通信原理课件》9.5.1图9-6所示的（3，1，2）卷积码编码器。每一个单位时间，输入一个信息码元im，且移位寄存器内的数据往右移一位。编码器有3个输出，一个输出是输入信息码元im的直接输出；另两个输出为监督码元1i,p、2i,p，是输入im与前两个单位时间送入的信息元1i-m、2i-m按照一定规则通过运算得到的。卷积码码字中的每一个子码21i,i,ii,p,pmC最左边0k（这里0k=1）个码元是输入的信息码元，其余的是监督码元，这是系统码的形式。《通信原理课件》图9-6(3，1，2)卷积码编码器《通信原理课件》一、生成矩阵和监督矩阵《通信原理课件》《通信原理课件》《通信原理课件》监督矩阵《通信原理课件》《通信原理课件》《通信原理课件》二、多项式表示《通信原理课件》用时延算子多项式来表示编码器中移位寄存器与模2加的连接关系时，称为生成多项式。如果某级寄存器与某个模2加法器相连接，则生成多项式对应项的系数取1，无连接时取0。图9-6中的生成多项式为2321111DxgDxgxg利用生成多项式与输入序列多项式相乘，可以产生输出序列多项式，从而得到输出序列。而且生成多项式和生成矩阵一一对应。《通信原理课件》9.5.2卷积码的图形描述以图9-6所示的（3，1，2）卷积码编码器为例来说明其工作过程。假设移位寄存器的起始状态全为零。当第一个输入比特为“0”时，输出的子码为000；若当第一个输入比特为“1”时，输出的子码为111。当输入第二比特时，第一比特右移一位，此时的输出比特显然与当前输入比特和前一输入比特有关。当输入第三比特时，第一比特和第二比特都右移一位，此时的输出比特显然与当前输入比特和前二位输入比特有关。当输入第四比特时，第二比特和第三比特都右移一位，此时的输出比特与当前输入比特和前二个输入比特有关，而这时第一比特已经不再影响当前的输入比特了。编码器在移位过程中可能产生的各种序列，可用树状图来描述。《通信原理课件》图9-7给出了卷积码的树状图。由树状图，已知输入信息序列就可以得到输出序列，当输入码元是0时，则由节点出发走上支路；当输入码元是1时，则由节点出发走下支路。例如当输入编码器的信息序列为0110…时，输出的序列为000111101011…。《通信原理课件》图9-7卷积码的树状图《通信原理课件》9.5.3卷积码的几种译码方法卷积码有三种主要的译码方法：序列译码、门限译码和最大似然译码。1957年伍成克拉夫(Wozencraft)提出了一种有效的译码方法，即序列译码。1963年梅西(Massey)提出了一种性能稍差，但比较实用的门限译码方法。1967年维特比(Viterbi)提出了最大似然译码法，它又称为维特比译码。门限译码是一种代数译码法，序列译码和维特比最大似然译码都是概率译码。代数译码利用编码本身得代数结构进行解码，并不考虑信道的统计特性。比如门限译码，它以分组码理论为基础，其主要特点是算法简单，易于实现，但是它的误码性能要比概率译码差。它的译码方法是从线性码的监督子出发，找到