通信原理 CT8差错控制编码课件.ppt
8.1 差错控制编码的基本概念8.2 线性分组码8.3 循环码,第 8 章 差错控制编码,返回主目录,概 述,差错控制编码：信道编码 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码。 数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还必须采用信道编码技术。,8.1.1 差错控制方式,图 8-1 差错控制方式,1. 前向纠错方式 前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。,2. 检错重发方式 检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效， 但实时性差，主要在计算机数据通信中得到应用。,3. 混合纠错方式 混合纠错方式记作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广泛应用。,另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道， 错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。,8.1.2 纠错码的分类 (1) 根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关， 而且还与前面若干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。,8.1.3 几种简单的检测码 (1) 奇偶监督码。 (2) 二维奇偶监督码。 (3) 重复码。 (4) 恒比码。 (5) ISBN国际统一图书编号。,1 奇偶监督码,奇偶监督码是在原信息码后面附加一个监督元， 使得码组中“1”的个数是奇数或偶数。奇偶监督码分为奇监督（校验）码和偶监督（校验）码。,设码字A=an-1,an-2,a1,a0，对偶监督码有,奇监督码情况相似， 只是码组中“1”的数目为奇数， 即满足条件,而检错能力与偶监督码相同。 奇偶监督码的编码效率R为,2 二维奇偶监督码,码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码，定 1 码。这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。 目前我国电传通信中普遍采用 32 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的不同码组数目等于从 5 中取 3 的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字，如下表所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。,3 重复码4 恒比码（定比码、等重码、范德伦码）,七三定比码（七单位码）用于国际电报系统，码长为7，其中1的个数为3。这种码的许用码字为：,32 恒比码,五三定比码（五单位码）用于国内电报系统，码长为5，其中1的个数为3。这种码的许用码字为：,代表26个英文字母和一些符号。,代表国内电报系统中的数字09。而每个汉字又是以四位十进制数来代表的。,8.1.4 检错和纠错的基本原理,1. 分组码 分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元， 组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。,在分组码中，非零码元的数目称为码字的汉明(Hamming)重量， 简称码重。例如，码字 10110，码重w=3。 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离， 简称码距。例如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用dmin表示。最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据 。,如果线性分组码(n,k)码位信息位没有变化，与信息码元排列相同，并且与监督位分开，称为系统码，否则称为非系统码。,2. 检错和纠错能力,若分组码码字中的监督元在信息元之后，而且是信息元的简单重复， 则称该分组码为重复码。它是一种简单实用的检错码， 并有一定的纠错能力。例如(2,1)重复码，两个许用码组是 00 与 11，d0=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是 000 与111, d0=3; 当收端出现两个或三个 1 时，判为 1，否则判为 0。此时，可以纠正单个错误，或者该码可以检出两个错误。,码的最小距离dmin直接关系着码的检错和纠错能力；对于任一(n,k)分组码，若要在码字内:若检测e个错误，则要求dmine+1;若纠正t个错误，则要求dmin2t+1;若纠正t个错误，同时发现e个错误，则要求dmint+e+1; te;,3. 编码效率 用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性: R=k/n其中, k是信息元的个数，n为码长。 对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。,8.2 线性分组码,现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元， 可用下列线性方程组来描述该分组码，产生监督元。,(7,4) 码的码字表,1 监督矩阵H和生成矩阵G 线性方程组为：,其中,P为rk阶矩阵，Ir为rr阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型监督矩阵。 HCT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字C是否出错的依据。,并简记为,H称为监督矩阵,若把监督方程补充为下列方程,可改写为矩阵形式,即：,C=mG系统码的生成矩阵也称为典型生成矩阵 G=Ik,Q，G为kn矩阵，Q为kr矩阵，Ik为kk单位阵。 HCT=0系统码的监督矩阵也称为基本监督矩阵H=P Ir ，H 为rn矩阵，P为rk矩阵，Ir为rr单位阵。HGT=0，同时有：GHT=0称H与G为正交矩阵，由 P Ir Ik QT=0 P+QT=0 ，即P=QT Q = PT P矩阵与Q矩阵互为转置矩阵。,2 伴随式(校正子)S,设发送码组C=an-1,an-2,a1,a0，在传输过程中可能发生误码。接收码组R=bn-1,bn-2,b1,b0，则收发码组之差定义为错误图样E， 也称为误差矢量， 即,其中E=en-1,en-2,e1,e0，且,当bi=ai,当biai,令S=RHT，称为伴随式或校正子。,(7,4)分组码S与E的对应关系,循环码定义：一个(n,k)线性分组码C，如果码组中的一个码字的循环移位也是这个码组中的一个码字，则称C为循环码。称为具有循环自闭性。C(0)=cn-1,cn-2,c1,c0 CC(1)=cn-2,cn-3,c0,cn-1 C循环码的多项式描述：循环码可以用监督矩阵和生成矩阵描述，但更多地用域上多项式来描述，一个(n,k)循环的码字矢量C(0)用一个n-1次多项式描述，可以表示为：C(x)= cn-1xn-1+cn-2xn-2+c1x+c0这个多项式称为码字多项式。码字矢量的循环移位可以用x乘上C(x)后的模(xn+1)来表示。xC(x)= x(cn-1xn-1+cn-2xn-2+c1x+c0) = cn-1xn+cn-2xn-1+c1x2+c0 x = cn-2xn-1+c1x2+c0 x+ cn-1 (模xn+1)模xn+1相当于xn+1=0；xn=1,8.3 循 环 码,(7,4)系统循环码的编码及码字多项式如下表：g(x)=x3+x+1可以看出：每个码字的循环移位仍然属于这个码组。并不是说码组是由一个码字的循环移位构成的，本例中是由四个码字的循环移位构成的。,8.3 循 环 码,8.3 循 环 码,(7,3) 循环码,在一个(n,k)循环码中，有且仅有一个次数为n-k=r的码字多项式，记为：g(x)=xr+gr-1xr-1+g1x+1同时：每个码字多项式都是g(x)的倍式；每个次数小于等于n-1的g(x)的倍式必为一个码字多项式。这时称g(x)的(n,k)码的生成多项式。生成多项式的性质：是循环码C中次数最低的非零码字多项式，并且是唯一的，其次数为r=n-k。令g(x)=xr+gr-1xr-1+g1x+g0为一个(n,k)循环码C中最低次数码字多项式，则其常数项必为g0=1。(n,k)循环码的生成多项式g(x)是xn+1的因式。,在代数理论中，为了便于计算，常用码多项式表示码字。(n,k)循环码的码字，其码多项式(以降幂顺序排列)为,系统循环码的编码方法：已知循环码的生成矩阵,可以按以下步骤产生系统循环码。首先定义以下多项式：m(x)=mk-1xk-1+mk-2xk-2+m1x+m0 为信息码字多项式；c(x)=cn-1xn-1+cn-2xn-2+c1x+c0 为循环码字多项式；g(x)=xr-1+gr-2xr-2+g1x+1 为生成多项式；系统码的编码分为三步：用xn-k乘上m(x);用g(x)除以xn-km(x)，得到模g(x)的余式r(x)c(x)=xn-km(x)+r(x)为系统循环码的码字多项式。,例: (7,4)循环码的生成多项式为g(x)=x3+x+1求m=1010的循环码。解：m(x)=x3+x, xn-k=x3;xn-km(x)=x3(x3+x)=x6+x4r(x)=x+1C(x)=xn-km(x)+r(x)=x6+x4+x+1C=1010 011,非系统循环码的编码方法：已知循环码的生成矩阵，可以方便的求出非系统循环码，C(x)=m(x)g(x)。例:m=1101 g(x)=x3+x+1C(x)=(x3+x2+1)(x3+x+1) =x6+x4+x3+x5+x3+x2+x3+x+1 =x6+x5+x4+x3+x2+x+1C=1111111m=0101; c(x)=(x2+1)(x3+x+1) =x5+x3+x2+x3+x+1=x5+x2+x+1C=0100111,循环码的生成矩阵：循环码可以用域上多项式描述，也可以用生成矩阵描述。已知g(x)为循环码C中的一个码字多项式，由循环码的循环特性可知，可以证明：在(n,k)循环码的码字多项式中，g(x),xg(x),xk-1g(x)等k个码字多项式必是线性无关（相互独立的）的。根据线性空间的特性，可知，它们是一个k维子空间的基底，即由它们的线性组合可以生成这个k维子空间的2k个码字。再根据线性分组码生成矩阵的定义，它的行向量是由k个线性无关的码字构成的，可以得到(n,k)循环码的一个多项式矩阵为：,例如(7,3)循环码，n=7, k=3, r=4, 其生成多项式及生成矩阵分别为,非系统循环码编码电路：非系统循环码的产生为：C(x)=m(x)g(x),可知其编码器为如下：,监督多项式及监督矩阵 为了便于对循环码编译码，通常还定义监督多项式， 令,其中g(x)是常数项为 1 的r次多项式，是生成多项式；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H,是h(x)的逆多项式。例如(9，3)循环码，g(x)=x4+x3+x2+1，则,其中,编码方法和电路,在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为,循环码的码多项式可表示为,图 (7,3)循环码编码电路,表 (7,3)循环码的编码过程,系统码编码器：为了构成系统码，可知C(x)=xn-km(x)+r(x)r(x)=xn-km(x)/g(x) 模g(x)以(7,4)汉明码为例：g(x)=x3+x+1编码器电路如图所示：它由r=n-k级移位寄存器构成。,系统循环码的生成矩阵与监督矩阵：,大数逻辑译码器：(门限译码器),其工作过程如下：由(7,3)循环码生成多项式g(x)=x4+x3+x2+1的除法电路，计算R(x)的校验子多项式S(x)。n=7次移位后得到校验子(s0,s1,s2,s3)，存在校验子移位寄存器中，此时，R(x)已全部进入7级缓存器中。停止译码器输入，并开始对rn-1=r6进行检查，也就是检查A1=s3，A2=s1，A3=s2+s0中1的个数。如果1的个数为3，大数门输出1。此时，缓存器移位一次，输出r6，对它进行纠错，如果1的个数小于3，大数门无输出，r6直接输出。除法电路循环移位一次，对r5进行检查，此时校验子寄存器中的内容是对r5的计算结果。如果大数门输出1，则对r5进行纠错，否则，r5直接输出。重复上述步骤，直至n=7次为止；第n=7次移位完毕后，如果校验子除法电路的状态为全0，则说明R(x)中的错误是可以纠正的，否则说明是不可纠正的。若是不可纠正的，译码器送出一个信号至用户，表示R(x)有误。然后重新清洗译码器的初始状态，准备接收第二各码字。图中的虚线是把大数门输出的1反馈到除法电路的输入端，以消除该错误码元对除法电路的影响。,捕错译码 ,译码过程如下：译码前所有移位寄存器和缓存器都为全0状态，门2，门3开，门1，门4，门5关。n=15次移位后，接收码字的R(x)的15个码元全部进入15级缓存器，信息元在前7级，监督元在后8级，同时进入除法电路，得到校验子多项式S0(x)。如果S0(x)=0，说明无错，打开门5，输出接收码字。如果S0(x)0，说明有错，进行以下各步。此时门2关，门1开，如果W(S0(x)2，检测电路输出有效，把门4打开，把门3关闭，此时除法电路移位寄存器中的内容就是接收码字的后8位的错误图样，只要接收码字只错2位或2位以下，后8位错误图样就等于全部错误图样。这时移位15次，除法电路的状态S0(x)=EP(x)通过门4与接收码字的后8位逐次相加，完成纠错。然后门1关，门5开，再移位15次，输出接收码字。如果W(S0(x)2，则15级缓存器和除法电路都循环移位一次，再次检测，若仍大于2，则继续移位，当移位I次后，检测到W(S0(x)2，则说明已经检测出错误图样已进入缓存器的后8位。这时门3关闭，门4打开，继续移位n-I次，进行纠错。最后门1关，门2，门5开，再移位15次输出正确的接收码字。从以上步骤中可以看出，译码器完成一个码字的译码，共需要3n次移位。这里介绍的是捕错译码器的基本原理，若要实现连续译码，还要进行一些改进，一方面力图使译码器电路简单化，另一方面提高译码速度，减少移位次数。,梅吉特(Meggit)译码器 ,这个译码器上面是一个g(x)除法电路，下面是一个7级移位寄存器作为缓存器，中间的反相器和一个与门组成了(101)校验子识别电路。译码过程如下：开始译码时门打开，移位寄存器内容位全0。收到的码字多项式位R(x)=r6x6+r0 由高次到低次分别输入到7级缓存器和除法电路，7次移位后，缓存器存入整个码字，除法电路S(x)=E(x)/g(x), E(x)=x6得到校验子S0=s2,s1,s0。这时门关上进行译码。如果S0(x)=x6=x2+1mod g(x)，这时101识别电路输出为1，表明r6为有错。这时译码器继续移位，通过101识别电路可以将r6位的错误纠正。在纠错的同时，101识别电路的输出又反馈到除法电路的输入端，以消除错误码元对除法电路的下一个校验子计算的影响。校验子产生电路开始在无输入的情况下移位，相当于开始产生xjS(x)。本电路中，输入R(x)第7次移位后产生了校验子S0，第8次移位时对r6进行纠正，同时将101识别电路的输出的1输入到除法电路的输入端，结果使除法电路的寄存器状态为000，消除了e6的影响。下面我们看一下，利用这个电路能否纠正其它错误图样的接收码字。如果E(x)=x5, 表明e5=1或E=0100000，这时经过前7次移位后得到的校验子多项式为S0(x)=x5mod g(x)=x2+x+1，这时除法电路的移位寄存器状态为111，101识别电路的输出为0，说明r6正确，不必纠正。第8次移位后，r5移位到缓存器的最右端。同时校验子除法电路的结果根据定理可知：（通过电路分析也可以看出）S1(x)=xS0(x)=xE(x)=x6mod g(x)=x2+1 mod g(x) 产生101状态；这时101识别电路输出1，对r5进行纠正。可以看到，利用循环码的循环特性，可以简化译码器的复杂性。从上述译码过程中可以看到，(n,k)循环码的译码器译一个码字共需要2n次移位，不能实现连续译码，为了实现连续译码，可以再加一套除法电路，,
