电力系统远动第4章 抗干扰编码

电力系统调度自动化电气工程学院林国松第四章抗干扰编码概述1抗干扰编码的基本原理2线性分组码3循环码4循环码的抗干扰能力5远动信息的CRC校验7BCH码6第一节概述基本概念误码率奇偶校验码抗干扰编码差错控制方法循环检错检错重发前向纠错反馈检验第二节抗干扰编码的基本原理许用码字禁用码字概念：一、分组码的概念分组码是对每个长度为k的信息组，以一定的规则增加r个监督位，组成长度为n=k+r的二进制序列

。这个长为n的序列叫做码字、码组或码矢，并称此2k个码字的集合为(n,k)分组码，其中n表示码长，k表示信息位长，r=n-k为监督位长。第二节抗干扰编码的基本原理二、码距和最大似然译码在分组码中，码字中“1”的数目叫做码字的重量，简称码重；任意两个码字对应位上的数字符号不同的位数叫做码字距离，简称码距。所有码字间的最小距离叫做最小码距，记作d0

。最大似然译码：收到的数字序列和哪一个许用码字的距离最小，就把它译成这个码字。理解P111举例说明。第二节抗干扰编码的基本原理三、分组码的检错、纠错能力要发现（检查）e个错误，要求最小码距：

d0≥e+1要纠正t个错误，要求最小码距：

d0≥2t+1要纠正t个错误，同时要发现e个错误，则要求最小码距：

d0≥t+e+1(e≥t)第二节抗干扰编码的基本原理例如：某一（n,k）码的最小码距d0＝10，则：e≤9t≤4.5e＋t≤9

即：该码最多只能发现9个错误；或者：最多只能纠正4个错误，但同时可查5个错误；或者：纠正3个错误，但同时可查6个错误；或者：纠正2个错误，但同时可查7个错误等。第三节线性分组码一、代数运算知识简介模2运算向量和矩阵加法乘法加法乘法0+0=00·0=01+0=11·0=00+1=10·1=01+1=01·1=1向量：在数学上的定义是一组有序的数，这里的数是0或1；矩阵：是n维向量排列成m行的表，矩阵中的每个元素都是0或1。第三节线性分组码二、生成矩阵设(7,3)码的3个信息位是C6C5C4,4个监督位是C3C2C1C0。信息组码字00000101001110010111011100000000011101010011101110101001110101001111010011110100求监督位方程为第三节线性分组码二、生成矩阵G：生成矩阵（k×n）Ik：为k阶单位矩阵Q：为（k×r）阶矩阵

编码：将待编信息组M乘以生成矩阵G就直接得到线性码字C。写成矩阵形式第三节线性分组码三、监督矩阵及线性码的性质将监督方程改写为：写成矩阵形式监督矩阵说明线性码中信息位和监督位之间的线性关系。第三节线性分组码三、监督矩阵及线性码的性质线性码性质：（1）封闭性，即任意两个线性码字之和仍为一个线性码字。设C1、C2是任意两个线性码字，有所以，C1+C2是一个线性码字。（2）线性码字的最小码距等于码字的最小重量。因为任意两个线性码字之间的距离等于这两个码字的（模2）和的非零个数，由性质1知任意两个线性码字之和仍为一个线性码字，所以最小码距等于码字的最小重量。第三节线性分组码四、伴随式E为错码样式接收端收到的码字：E为（1×n）矩阵，其元素为“0”（正确）或“1”（错误）如：C＝(0011101)，E＝（1000011）

——R＝（1011110）为禁用码字，检测错误检错——判断R是否为许用码字

定义伴随式S为：第三节线性分组码四、伴随式监督矩阵：第四节循环码一、代数知识

循环码是线性分组码的重要子类，有严格的代数结构，用代数方法可找出许多编码效率高、检纠错能力强的循环码。循环码的编码、检纠错方法简单、易实现，并且已找到许多有效的纠错方法。——得到广泛应用循环码可用多项式分析，其系数为“0”或“1”。多项式的系数是一组按幂次的有序数组，而码字也是一组的有序数组，因此码字：C=(Cn-1,Cn-2,∙∙∙,C0)不但可用向量表示，也可用一个多项式表示－称为码多项式。注意：多项式系数的加、乘为模2加、乘。第四节循环码一、代数知识模f(x)加法，记作⊕定义：两个多项式f1(x)、f2(x)的模f(x)加法是f1(x)加f2(x)后，除以f(x)所得的余式。如果f1(x)、f2(x)的次数都小于f(x)，则模f(x)乘法，记作⊙定义：两个多项式f1(x)、f2(x)的模f(x)乘法是f1(x)乘f2(x)后，除以f(x)所得的余式。第四节循环码二、循环码原理循环码的定义定义：(n,k)循环码是线性分组码，并且任意码字的每一次循环移位，得到的仍是一个码字。第四节循环码二、循环码原理循环码的生成多项式定义(n,k)循环码的生成多项式是码字中n-k次的码多项式，记作g(x)。从2k个码字中，取出一个前面k-1位均为0的码字，其构成的多项式即是该码字的生成多项式，其次数：n-1-(k-1)=n-k。如：(7,3)循环码：前2位为0的码字：0011101，其生成多项式：

，次数为6-2=4第四节循环码二、循环码原理因为g(x)是一个循环码字，所以

都是码字。循环码是线性码，由线性码字的性质的：这k个码字的线性组合也是一个码字把信息组写成多项式可以得到循环码的码字是待编码的信息多项式乘生成多项式得到，m(x)共有2k种形式，可以生成2k个循环码码字，(n,k)循环码只有2k个码字，因此：所有循环码字均可以由g(x)生成。注意：直接由式生成的循环码不是系统码格式。第四节循环码二、循环码原理生成多项式的性质：生成多项式是次数最低的码多项式。生成多项式可由进行因式分解，然后取其n-k次因式就是g(x)，所以其次数就是n-k次。将进行因式分解：又因(7,3)码的n-k=4，g(x)应为4次多项式。前表中的(7,3)码的g(x)为：

例：求(7,3)循环码的生成多项式。第四节循环码二、循环码原理系统码格式的循环码的编码(1)将待编信息多项式

乘以，得(2)求余式：(3)码多项式：例：求的(7,3)码。解：C=0100111第四节循环码三、循环码的伴随式在发送端把信息序列编成循环码字，发送给接收端，在传输中因干扰产生错码，接收端收到的不一定是循环码字，而是一个数字序列R。设错码样式为在接收端收到的数字序列多项式为循环码的伴随式记作

，它是数字序列

除以生成多项式g(x)所得的余式。当

时，

；

时，

。所以，循环码的检错方法是：在接收端把接收到的数字序列除以生成多项式g(x)所得的余式

，如果

，认为无错码；如果

，则有错码。第四节循环码四、缩短循环码只取原系统中部分码字，并删去前面的0，不再具有循环的特性。只删去0，不影响由信息生成码字时的运算过程和运算结果，实现的电路（程序）不变，监督位数不变、纠检错的能力不变。定义：任何一个给定的(n,k)系统循环码的2k个码字中，一定存在2k-i(i<k)个前i位为零的码字。如果删去2k-i个码字中前面i位零，可以得到2k-i个长为(n-i)的码字，由它们构成的(n-i,k-i)线性系统码，称为原(n,k)系统循环码的缩短循环码。第四节循环码四、缩短循环码考察(7,4)系统循环码。在16个码字中，1/2的码字信息最高位为0。编码时0不起作用，去掉不影响余式。删去得到8个码长为6的码字，构成(6,3)码，校验元同原来(7,4)码，相同的生成多项式和编码方法。称(6,3)码为原来(7,4)码的缩短循环码。将(7,4)码的码长和信息位同时减少1位，是(n-1,k-1)码。在16个码字中，1/4的码字信息前两位为0。删去得到4个码长为5的码字，构成(5,2)码，也称为原来(7,4)码的缩短循环码。将(7,4)码的码长和信息位同时减少2位，是(n-2,k-2)码。第五节循环码的抗干扰能力一、循环码的随机检错能力(1)如生成多项式

的项数是偶数，则能检出所有奇数个差错。因为当差错个数为奇数时，错误图样

的项数也是奇数。

的项数是偶数，

的项数是奇数，

不可能被

除尽，从而检出了所有奇数个错误。(2)用

与任一

相乘所得的生成多项式

，其项数必为偶数。令代入有从循环码的的检错译码的原理可知，要看收到的码组是否能被生成多项式除尽，也就是错误图样是否能被生成多项式除尽，除不尽时伴随式，就能检出错误。第五节循环码的抗干扰能力二、循环码的突发检错能力由突发干扰产生的错误是成串的差错。第一个错码与最后一个错码之间的位数叫做突发长度，记作b。例如突发干扰使111111111错成1010001011，其突发长度b=7。一个突发长度为b的突发错误，其首位和末位必定有错，中间的码元可能有错，也可能无错。若一个线性码能发现（或纠正）码组中所有长度小于等于b的突发错误，则该码的突发检错（或纠错）能力为b。设(n,k)循环码的突发检错能力为b。突发长度为b的错误图样

可写成任意一个突发长度为b的错误多项式都可写成第五节循环码的抗干扰能力二、循环码的突发检错能力(1)由n-k次生成多项式生成的循环码，能检出所有突发长度的突发错误。(2)若，则不能检出的突发错误部分占同样长度的突发错误总数的。(3)若，则不能检出的突发错误部分占同样长度的突发错误总数的。(n,k)循环码的监督位数越大时，不能被发现的突发错误占的比例就越小。第六节BCH码一、代数知识简介BCH码是循环码的一个子类，其生成多项式与最小码距之间有直接关系。(1)多项式的根。多项式

的根以符号α表示，。(2)既约多项式：指不能在二元域内再分解因式的多项式。例：是可约多项式，是既约多项式。如果α是的根，则。三位元素的域记作，共有个元素，其中001-111叫做非零元素。称是本原多项式，其根α叫做本原元。第六节BCH码一般情况，一个m次既约多项式，如果其根生成中的所有非零元素，且两两不同，则此多项式称本原多项式，其根叫做本原元。(1)m次既约多项式必为的因式，其中。(2)定义：设β是中的某一元素，若m(x)是以β为根的既约多项式，则称m(x)是β的最小多项式(称为一阶最小多项式)。(3)设α是中的本原元，的最小多项式记作，称为i阶最小多项式。(1)(n,k)BCH码是循环码，规定码长，其中m为本原多项式的次数。由于规定BCH码的码长，所以BCH码是循环码的子类，且BCH码的生成多项式必为的因式。(2)本原BCH码的生成多项式定义为第六节BCH码二、BCH码简述BCH码分为两类：一类称本原BCH码，另一类是非本原BCH码。本原BCH码的定义LCM----最小公倍式----的最小多项式第六节BCH码二、BCH码简述如果已知码长n和最小码距d0，要求找到一个生成多项式以编成BCH码，具体步骤为：(1)确定BCH码的码长n，。(2)将因式分解，且分解后各因式都是既约多项式；(3)求本原多项式，它的根α是本原元；(4)确定各因式是几阶最小多项式；(5)求出BCH码的生成多项式，确定BCH码的形式。非本原BCH码非本原BCH码的定义和本原BCH码定义相同，只是把本原元α用非本原元β代替即可。非本原BCH码的码长n只要满足条件，n就是的因子。要生成一个(n,k)循环码，只需要将分解，找出一个次数等于n-k次的因式，就可以作为(n,k)循环码的生成多项式生成该码组。如果在的分解式中有多个n-k次的因式，则把其中任意一个作为生成多项式，都可以生成一个(n,k)循环码。如果被选用的生成多项式的重量不同，它生成的循环码最小距离也不相同。即使对次数相同又具有相同重量的生成多项式，只要它们的重量分布不同，所生成的循环码码字的重量分布也不相同。第七节远动信息的CRC校验一、生成多项式第七节远动信息的CRC校验一、生成多项式我国部颁循环式远动规约规定，每帧远动信息中的控制字和信息字都采用CRC校验，并选用生成多项式生成(48,40)循环码，其陪集为FFH。规约中的(48,40)循环码实际是(127,120)循环码进行增余删信(保证码长n不变，增加一位校验元，删除一位信息码元)和缩短处理之后得到的缩短循环码。我国部颁问答式远动规约中的报文校验码为16位的报文采用CRC校验，生成多项式是校验码为8位的报文校验码由7位CRC校验码和1位奇偶校验码组成，CRC校验码的生成多项式是

。第七节远动信息