第六章____信道编码.ppt

第6章信道编码目的：提高通信系统传输的可靠性；目标：寻找具体构造编码的理论与方法；l在理论上，Shannon第二编码定理已指出，只要当实际传信率R检错码（发现错误）2纠错码（不仅发现而且能自动纠正）3纠删码（兼检错、纠错）,-根据信息码元和监督码元的约束关系分为：分组码(将信息序列按照独立分组进行处理和编码）和非线性码。,-根据信息位和校验位的关系（规则）分为,线性码和非线性码,非线性码：也将k个信息比特编成n个比特，但前后N个码字之间是相互关联,分组码：将k个信息比特编成n个比特的码字，共有个码字。所有个码字组成一个分组码。传输时前后码字之间毫无关系。,编码速率=平均每个码字所携带的信息比特率。,6-1-5差错控制原理,构造出以最小多余度的代价换取最大抗干扰性的“好“码；,从直观概念出发，寻求“好“码性能的两个极端情况：1高可靠性，低有效性的重复码；2高有效性，低可靠性的奇偶校验码。,(1)重复码(n,1)：,不重复时:,结论：不重复，方法简单，但没有任何抗干扰能力，既不能发现，更不能纠正错误。,信道编码的任务：,重复一次：,结论：重发一次，效率降低一倍.可以换取在传输过程中允许产生一个错误（收端能发现它），但不能纠正。,重复二次：,结论：重发二次，效率降低二倍，但换取了可纠正一个差错或发现两个差错的性能改善。,编码效率:=1/n,(2)奇偶检验码(n.n-1)：,其编码规则为：,其中,结论：这类码效率高，但可靠性较差，仅具有部分（奇或偶）检错功能。,（n，1）重复码，随着n的增大，可靠性不断提高，但有效性却在下降：；,（n，n-1）奇偶监督码，随着n的增大，其效率，很高，但是可靠性差，仅能发现奇（偶）数个独立差错；,要寻找的是高可靠性即差错率，且编码效率的理想信道编码,目前信道编码的主要目标-是以可靠性为主，即在寻求抗干扰强的码的基础上，寻求适当的有效性，寻求和构造最小码距离比较大的码。,能否找到既可靠性高又效率不低的信道编码？讨论的核心问题。,（3）线性分组码,1构造：每k位信息为一组进行编码，按一定线性规律加入多余码元，构成n位一组的输出（即编成n位码长的信道编码），它可记为（n，k）码，其中监督（校验）位为n-k位,2编码效率为,3码重：是指码组中所含“1”的数目,如在上述（3，1）重复码中：,4码距:线性分组码中的码距是指两个码组与中相应码元不相同的数目。,比如在上述重复码（1，1）中：,（1，1）重复码：,（3，1）重复码：,（2，1）重复码：,6推广：纠正随机独立差错能力与最小码距之间的关系：,；,若要发现e个独立差错，则要求最小码距；,若要纠正t个独立差错，则要求最小码距；,若要求发现e个又纠正t个独立差错，则,5最小码距：是码的一种属性，如（n，k）码中任何两个码字C1、C2之间距离的最小值，用表示。,码的最小码距决定了码的纠错、检错性能,6-4线性分组码（n，k）,线性-是指编码规律即码元之间的约束关系是线性的.分组-是对编码方法而言，即编码是将每k个信息为分为一组进行独立处理编码，编成长度为n位（nk）的二进制码组。,6-6-1基本概念：,定义：1线性分组码的加法为模2加，乘法为二进制乘法。,即1+1=0、1+0=1、0+1=1、0+0=01x1=1,1x0=0,0 x0=0,0 x1=0,2且码字与码字的运算是各个相应比特位上符合上述二进制加法运算规则。,3线性分组码的性质：,封闭性。任意两个码组的和还是许用的码组。码的最小距离等于非零码的最小码重。,6-5-2码的校验矩阵和生成矩阵,所谓的线性分组码就是信息位和校验位之间的监督关系是线性的。所谓线性就是监督位能表示成信息的线性和形式。,一)码的校验矩阵（监督矩阵）,1)先回顾一下偶校验码的构成：,对于偶校验码的监督关系：,如果S=1，则认为传输时出错；S=0，则认为无误传输。上式称为监督关系，S-称为校验子。,2)问题：为了能纠一位错，k位信息至少需要多少位的监督信息，如何设计？,3)分析：如果校验子有两位，则可以有四种组合，可以表示4种不同的信息，如果用其中的一种表示无错，则其它3种可以表示错误的种类（或位置），为了能纠一个错，要求监督位数至少应满足：,如果取k=4，则可以确定n=7。,因此，可以用3个校验子来确定传输的7个位置是否出错。,假设传输时的码字为，如果与错码的位置对应如下：,根据上述的真值表，我们可以得到如下的关系：,在发送端编码时，信息位的取值取决于输入的信息比特，因此它们是随机变化的。,监督位应根据信息位的取值按监督关系来确定，即监督位应该使上三式的取值为0。因此，我们可以得到：,因此，给出信息位后，根据上式可以算出监督位,得到（7，4）的所有码组。,上述关系可以写成如下矩阵的形式：,即,其中,H就称为（7，4）码的校验矩阵（或监督矩阵）。只要监督矩阵确定，则编码时信息位与监督位的关系就确定了。,因此，线性分组码的设计实际上是如何设计监督矩阵的问题。,二）码的生成矩阵,将写成另一种矩阵形式,再经变换得到,其中，G称为码的生成矩阵。,因此，如果知道生成矩阵同样可以确定编码的码组。这对所有的线性码都是一样的。,三）生成矩阵G与监督矩阵H的关系,且,所以,对于任何线性分组码而言，上述关系总是存在的，即,我们再来看，在上述的例子中，,其中,其中,四、系统码与非系统码,假设信息位为，如果编码后的码组为如下形式：,其中是监督位，则称这种码为系统码。,即系统码经过编码后的码组中前k个就是信息位，后n-k是监督位。,如果不存在上述关系，则称为非系统码。,由以上定义可以看到，我们刚才讨论的（7，4）码是系统码。只有系统码才有关系。,系统码和非系统码都有性质：,或者说：若H=(PI)，即能分解为单位方阵为子阵，且I的位置可任意，则称A为系统码。,任何一个线性分组（n,k）码，均可找到一个等价的系统码，而且还可以进一步证明只要在码率R和码长n相同的条件下，最优的系统码与最优的线性分组码具有相同的错误概率。,由线性代数理论，任何一个非系统的生成矩阵G均可以通过矩阵的初等变换得到相应的系统码的生成矩阵G。因此，我们可以得到如下结论：,五校验子S,如果我们能在接收端确定E，那么我们就能够通过接收到的B来译码得到A，即A=B+E。,假设我们发送的码组为A，接收到的码组为B，则B=A+E,如何得到E呢？,E称为错误图样。S称为校验子,结论：1)校验子S是错误的判别式：若S=0,判无错；若S0，则判有错2不同的错误图样具有不同的校验子，他们一一对应，二元码校验子是H阵中与错误码元对应列。,若无错，则E=0,则B=AHET=0若有错，则E0,则HET0,下面以（7,4)为例：,其监督矩阵及生成矩阵如下：,信道产生的差错图样：,6-7循环码,6.7.1.循环码的概念及性质,一循环码简介,循环码是线性分组码中最重要的一种子类，是目前研究得比较成熟的一类码。循环码具有许多特殊的代数性质，这些性质有助于按照要求的纠错能力系统地构造这类码，并且简化译码算法,目前发现的大部分线性码与循环码有密切关系。循环码还有易于实现的特点，很容易用带反馈的移位寄存器实现其硬件。,(二)循环码的性质：,1、封闭性：-任何许用码组的线性和还是许用码组。结论：线性码都包含全零码。最小码重就是最小码距。,2.循环性-任何许用的码组循环移位后的码组还是许用码组。,三、主要特点：。理论成熟：可利用成熟的代数结构深入探讨其性质；。实现简单；可利用循环移位特性在工程上进行编，译码；。循环码的描述方式有很多，但在工程上最有用的采用多项式的描述方法,二概念及性质,（一）定义：一个（n,k）线性分组码，经任意循环移位之后，仍然是线性分组码，则称它为循环码,循环码循环码原理循环性：循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。在下表中给出一种(7,3)循环码的全部码组。例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第7码组。,一般说来，若(an-1an-2a0)是循环码的一个码组，则循环移位后的码组(an-2an-3a0an-1)(an-3an-4an-1an-2)(a0an-1a2a1)也是该编码中的码组。,码多项式码组的多项式表示法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成例如，上表中的任意一个码组可以表示为其中第7个码组可以表示为这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。,1.码多项式的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1+1=20(模2)，1+2=31(模2)，23=60(模2)等等。一般说来，若一个整数m可以表示为式中，Q整数，则在模n运算下，有mp(模n)即，在模n运算下，一个整数m等于它被n除得的余数。,在码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为这时，码多项式系数仍按模2运算，即系数只取0和1。例如，x3被(x3+1)除，得到余项1。所以有同理因为,应当注意，由于在模2运算中，用加法代替了减法，故余项不是x2x+1，而是x2+x+1。,循环码的码多项式在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若则T(x)也是该编码中的一个许用码组。【证】因为若则（模(xn+1)）所以，这时有,上式中T(x)正是T(x)代表的码组向左循环移位i次的结果。因为原已假定T(x)是循环码的一个码组，所以T(x)也必为该码中一个码组。例如，循环码组其码长n=7。现给定i=3，则其对应的码组为0101110，它正是表中第3码组。由上述分析可见，一个长为n的循环码必定为按模(xn+1)运算的一个余式。,2.循环码的生成矩阵G由上节中公式可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。例如，在此式中，若a6a5a4a3=1000，则码组A就等于G的第一行；若a6a5a4a3=0100，则码组A就等于G的第二行；等等。由于G是k行n列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，xg(x)，x2g(x)，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能有(k-1)位。否则，在经过若干次循环移位后将得到一个k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(nk)的唯一多项式。我们称这唯一的(nk)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。,因此，循环码的生成矩阵G可以写成例：在上表所给出的(7,3)循环码中，n=7,k=3,nk=4。由此表可见，唯一的一个(nk)=4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式）g(x)=x4+x2+x+1。将此g(x)代入上式，得到或,由于上式不符合G=IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。我们可以写出此循环码组，即上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k1)的多项式乘g(x)都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是T(x)。为了简洁，式中直接将乘积写为此元素。,3.如何寻找任一(n,k)循环码的生成多项式由上式可知，任一循环码多项式T(x)都是g(x)的倍式，故它可以写成T(x)=h(x)g(x)而生成多项式g(x)本身也是一个码组，即有T(x)=g(x)由于码组T(x)是一个(nk)次多项式，故xkT(x)是一个n次多项式。由下式可知，xkT(x)在模(xn+1)运算下也是一个码组，故可以写成,上式左端分子和分母都是n次多项式，故商式Q(x)=1。因此，上式可以化成将T(x)和T(x)表示式代入上式，经过化简后得到上式表明，生成多项式g(x)应该是(xn+1)的一个因子。这一结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是(xn+1)的一个(nk)次因式。例如，(x7+1)可以分解为为了求(7,3)循环码的生成多项式g(x)，需要从上式中找到一个(nk)=4次的因子。不难看出，这样的因子有两个，即,以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。,循环码的编解码方法循环码的编码方法编码原则在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即从(xn+1)的因子中选一个(n-k)次多项式作为g(x)。由于所有码多项式T(x)都可以被g(x)整除。根据这条原则，就可以对给定的信息位进行编码：设m(x)为信息码多项式，其次数小于k。用xn-k乘m(x)，得到的xn-km(x)的次数必定小于n。用g(x)除xn-km(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(nk)。将此余式r(x)加于信息位之后作为监督位，即将r(x)和xn-km(x)相加，得到的多项式必定是一个码多项式。因为它必须能被g(x)整除，且商的次数不大于(k1)。,编码步骤：用xn-k乘m(x)。这一运算实际上是在信息码后附加上(nk)个“0”。例如，信息码为110，它相当于m(x)=x2+x。当nk=73=4时，xn-km(x)=x4(x2+x)=x6+x5，它相当于1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即例如，若选定g