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

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

2、加的信息组，以一定的规则增加r r个监督位，组成长度为个监督位，组成长度为n=k+rn=k+r的二进制序列的二进制序列 。这个长为这个长为n n的序列叫做的序列叫做码字、码组或码矢码字、码组或码矢，并称此，并称此2 2k k个个码字的集合为码字的集合为(n,k)(n,k)分组码分组码，其中，其中n n表示码长，表示码长，k k表示信息表示信息位长，位长，r=n-kr=n-k为监督位长。为监督位长。0121,.,CCCCnn第二节第二节 抗干扰编码的基本原理抗干扰编码的基本原理二、码距和最大似然译码二、码距和最大似然译码在分组码中，码字中在分组码中，码字中“1”1”的数目叫做码字的重量，简称的数

3、目叫做码字的重量，简称码码重重；任意两个码字对应位上的数字符号不同的位数叫做码字距任意两个码字对应位上的数字符号不同的位数叫做码字距离，简称离，简称码距码距。所有码字间的最小距离叫做。所有码字间的最小距离叫做最小码距最小码距，记，记作作d d0 0 。最大似然译码最大似然译码：收到的数字序列和哪一个许用码字的距离：收到的数字序列和哪一个许用码字的距离最小，就把它译成这个码字。最小，就把它译成这个码字。理解理解P111P111举例说明。举例说明。第二节第二节 抗干扰编码的基本原理抗干扰编码的基本原理三、分组码的检错、纠错能力三、分组码的检错、纠错能力要发现（检查）要发现（检查）e e个错误，要求

4、最小码距：个错误，要求最小码距： d d0 0 e + 1 e + 1要纠正要纠正t t个错误，要求最小码距：个错误，要求最小码距： d d0 0 2t + 1 2t + 1要纠正要纠正t t个错误，同时要发现个错误，同时要发现e e个错误，则要求最小码个错误，则要求最小码距：距： d d0 0 t + e + 1 (e t) t + e + 1 (e t) 第二节第二节 抗干扰编码的基本原理抗干扰编码的基本原理例如：例如： 某一（某一（n, kn, k）码的最小码距）码的最小码距d d0 01010， 则：则：e 9e 9 t 4.5 t 4.5 e et 9 t 9 即：该码最多只能发现即

5、：该码最多只能发现9 9个错误；或者：个错误；或者： 最多只能纠正最多只能纠正4 4个错误，但同时可查个错误，但同时可查5 5个错误；或者：个错误；或者： 纠正纠正3 3个错误，但同时可查个错误，但同时可查6 6个错误；或者：个错误；或者： 纠正纠正2 2个错误，但同时可查个错误，但同时可查7 7个错误等。个错误等。第三节第三节 线性分组码线性分组码一、代数运算知识简介一、代数运算知识简介v模模2运算运算v向量和矩阵向量和矩阵加法加法乘法乘法加法加法乘法乘法0+0=000=01+0=110=00+1=101=01+1=011=1向量：向量：在数学上的定义是一组有序的数，这里的在数学上的定义是一

6、组有序的数，这里的数是数是0或或1；矩阵：矩阵：是是n维向量排列成维向量排列成m行的表，矩阵中的每行的表，矩阵中的每个元素都是个元素都是0或或1。第三节第三节 线性分组码线性分组码二、生成矩阵二、生成矩阵设设(7,3)(7,3)码的码的3 3个信息位是个信息位是C C6 6C C5 5C C4 4,4,4个监督位是个监督位是C C3 3C C2 2C C1 1C C0 0。信息组信息组码字码字000000001001010010011011100100101101110110111111000 000 00000000001 001 11011101010 010 01110111011 01

7、1 10101010100 100 11101110101 101 00110011110 110 10011001111 111 010001004560456145624563110011111101CCCCCCCCCCCCCCCC求监督位方程为求监督位方程为第三节第三节 线性分组码线性分组码二、生成矩阵二、生成矩阵G：生成矩阵（kn）Ik：为k阶单位矩阵Q：为（kr）阶矩阵 编码：将待编信息组M乘以生成矩阵G就直接得到线性码字C。MGC 1101001011101011101004560123456CCCCCCCCCCQIGk110100101110101110100456CCCM 写成

8、矩阵形式第三节第三节 线性分组码线性分组码三、监督矩阵及线性码的性质三、监督矩阵及线性码的性质将监督方程改写为：010001100010001100010111000011010123456012345601234560123456CCCCCCCCCCCCCCCCCCCCCCCCCCCC写成矩阵形式000000010110010110010011110001010123456CCCCCCCPIrH00010110010110010011110001010TCH0THC监督矩阵监督矩阵说明线性码中信息说明线性码中信息位和监督位之间的位和监督位之间的线性关系。线性关系。第三节第三节 线性分组码线性

9、分组码三、监督矩阵及线性码的性质三、监督矩阵及线性码的性质线性码性质：（1）封闭性，即任意两个线性码字之和仍为一个线性码字。设C1、C2是任意两个线性码字，有0)(2121TTTHCHCHCC所以，C1+C2是一个线性码字。（2）线性码字的最小码距等于码字的最小重量。因为任意两个线性码字之间的距离等于这两个码字的（模2）和的非零个数，由性质1知任意两个线性码字之和仍为一个线性码字，所以最小码距等于码字的最小重量。第三节第三节 线性分组码线性分组码四、伴随式四、伴随式E为错码样式接收端收到的码字：E为（为（1n）矩阵，其元素为）矩阵，其元素为“0”（正确）或（正确）或“1”（错误）（错误）如如：

10、C(0011101) ，E（1000011） R（1011110）为）为禁用码字，检测错误禁用码字，检测错误检错检错判断判断R是否为许用码字是否为许用码字 定义伴随式S为：ECR),.,(0111eeeeEnnTTTEHHECRHS)(第三节第三节 线性分组码线性分组码四、伴随式四、伴随式0110001110001011101001011000H0123456012345610000100001000011011111001110110001110001011101001011000eeeeeeeeeeeeeeEHSTT监督矩阵：第四节第四节 循环码循环码一、代数知识一、代数知识 循环码是线性

11、分组码的重要子类，有严格的代数结构，用代数方法可找出许多编码效率高、检纠错能力强的循环码。 循环码的编码、检纠错方法简单、易实现，并且已找到许多有效的纠错方法。 得到广泛应用 循环码可用多项式分析，其系数为“0”或“1”。多项式的系数是一组按幂次的有序数组，而码字也是一组的有序数组，因此码字：C=(Cn-1,Cn-2, C0)不但可用向量表示，也可用一个多项式表示称为码多项式。注意：多项式系数的加、乘为模2加、乘。012111.)(CxCxCxCxCnnnn第四节第四节 循环码循环码一、代数知识一、代数知识v模模f(x)加法，记作加法，记作 定义：两个多项式f1(x)、f2(x)的模f(x)加

12、法是f1(x)加 f2(x)后，除以f(x)所得的余式。)(2121)()()()(xfxfxfxfxf如果f1(x)、f2(x)的次数都小于f(x)，则)()()()(2121xfxfxfxfv模模f(x)乘法，记作乘法，记作 定义：两个多项式f1(x)、f2(x)的模f(x)乘法是f1(x)乘 f2(x)后，除以f(x)所得的余式。)(2121)()()()(xfxfxfxfxf第四节第四节 循环码循环码二、循环码原理二、循环码原理v循环码的定义循环码的定义定义：(n,k)循环码是线性分组码，并且任意码字的每一次循环移位，得到的仍是一个码字。第四节第四节 循环码循环码二、循环码原理二、循环

13、码原理v循环码的生成多项式循环码的生成多项式定义(n,k)循环码的生成多项式是码字中n-k次的码多项式，记作g(x)。从2k个码字中，取出一个前面k-1位均为0的码字，其构成的多项式即是该码字的生成多项式，其次数：n-1-(k-1)=n-k。如：(7,3)循环码：前2位为0的码字：0011101，其生成多项式： ，次数为6-2=41)(234xxxxg第四节第四节 循环码循环码二、循环码原理二、循环码原理因为g(x)是一个循环码字，所以 都是码字。循环码是线性码，由线性码字的性质的：这k个码字的线性组合也是一个码字)().()(012111xgmxmxmxmxCkkkk把信息组 写成多项式01

14、2111.)(mxmxmxmxmkkkk),.,(021mmmkk可以得到)()()(xgxmxC循环码的码字是待编码的信息多项式乘生成多项式得到，m(x)共有2k种形式，可以生成2k个循环码码字，(n,k)循环码只有2k个码字，因此：所有循环码字均可以由g(x)生成。)(),.,(),(12xgxxgxxxgk注意：直接由式生成的循环码不是系统码格式。第四节第四节 循环码循环码二、循环码原理二、循环码原理生成多项式的性质：生成多项式是次数最低的码多项式。生成多项式可由 进行因式分解，然后取其n-k次因式就是g(x)，所以其次数就是n-k次。1nx将 进行因式分解：又因(7,3)码的n-k=4

15、，g(x)应为4次多项式。前表中的(7,3)码的g(x)为： 17x) 1)(1)(1(13237xxxxxx1)1)(1()(2343xxxxxxxg例：求(7,3)循环码的生成多项式。第四节第四节 循环码循环码二、循环码原理二、循环码原理v系统码格式的循环码的编码系统码格式的循环码的编码(1)将待编信息多项式 乘以 ，得)()()()(xrxgxQxxmkn1)(234xxxxg111000000000012234343455234xxxxxxxxxxxxxxxxx(2)求余式：(3)码多项式：例：求的(7,3)码。解：knxknxxm)()()()()()(xrxxmxgxQxCknxx

16、m)() 1()(2xxxrC=0100111) 1() 1)(1()(22345xxxxxxxxxmkn1)()()(25xxxxrxxmxCkn)(xm第四节第四节 循环码循环码三、循环码的伴随式三、循环码的伴随式在发送端把信息序列编成循环码字，发送给接收端，在传输中因干扰产生错码，接收端收到的不一定是循环码字，而是一个数字序列R。设错码样式为012111.)(exexexexEnnnn在接收端收到的数字序列多项式为)()(.)(012111xExCrxrxrxrxRnnnn循环码的伴随式记作 ，它是数字序列 除以生成多项式g(x)所得的余式。当 时， ； 时， 。所以，循环码的检错方法是

17、：在接收端把接收到的数字序列 除以生成多项式g(x)所得的余式 ，如果 ，认为无错码；如果 ，则有错码。)(xS)(xR0)(xE0)(xS0)(xE0)(xS)(xS0)(xS0)(xS第四节第四节 循环码循环码四、缩短循环码四、缩短循环码v只取原系统中部分码字，并删去前面的只取原系统中部分码字，并删去前面的0，不再具，不再具有循环的特性。有循环的特性。v 只删去只删去0，不影响由信息生成码字时的运算过程和，不影响由信息生成码字时的运算过程和运算结果，实现的电路（程序）不变，监督位数不运算结果，实现的电路（程序）不变，监督位数不变、纠检错的能力不变。变、纠检错的能力不变。定义：任何一个给定的

18、(n,k)系统循环码的2k个码字中，一定存在2k-i(ik)个前i位为零的码字。如果删去2k-i个码字中前面i位零，可以得到2k-i个长为(n-i)的码字，由它们构成的(n-i,k-i)线性系统码，称为原(n,k)系统循环码的缩短循环码。第四节第四节 循环码循环码四、缩短循环码四、缩短循环码考察(7,4)系统循环码。0120123rrrmmmmC 1111011110110011110101011001000111100110101000101100010010000000 在16个码字中，1/2的码字信息最高位为0。编码时0不起作用，去掉不影响余式。删去得到8个码长为6的码字，构成(6,3)

19、码，校验元同原来(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)如生成多项式 的项数是偶数，则能检出所有奇数个差错。因为当差错个数为奇数时，错误图样 的项数也是奇数。 的项数是偶数， 的项数是奇数

20、， 不可能被 除尽，从而检出了所有奇数个错误。(2)用 与任一 相乘所得的生成多项式 ，其项数必为偶数。)(xg)(xE)(xg)(xE)(xE)(xg)() 1()(12xgxxg)(1xg1x1.)() 1()(11112xgxgxxgxxgknknkn令01.1) 1 (0) 1 () 11 () 1 (11112gggggkn代入 有1x从循环码的的检错译码的原理可知，要看收到的码组从循环码的的检错译码的原理可知，要看收到的码组 是否能被生成多项式是否能被生成多项式 除尽，也就是错误图样除尽，也就是错误图样 是否能被生成是否能被生成多项式多项式 除尽，除不尽时伴随式除尽，除不尽时伴随式

21、 ，就能检出错误。，就能检出错误。)(xg)(xg)(xE)()()(xExCxR0)(xS第五节第五节 循环码的抗干扰能力循环码的抗干扰能力二、循环码的突发检错能力二、循环码的突发检错能力由突发干扰产生的错误是成串的差错。第一个错码与最后一个错码之间的位数叫做突发长度，记作b。例如突发干扰使111111111错成1010001011，其突发长度b=7。一个突发长度为b的突发错误，其首位和末位必定有错，中间的码元可能有错，也可能无错。若一个线性码能发现（或纠正）码组中所有长度小于等于b的突发错误，则该码的突发检错（或纠错）能力为b。设(n,k)循环码的突发检错能力为b。突发长度为b的错误图样

22、可写成1.)(1221xexexxEbbbb任意一个突发长度为b的错误多项式都可写成)()(xExxEbi)(xEb第五节第五节 循环码的抗干扰能力循环码的抗干扰能力二、循环码的突发检错能力二、循环码的突发检错能力(1)由n-k次生成多项式生成的循环码，能检出所有突发长度 的突发错误。(2)若 ，则不能检出的突发错误部分占同样长度的突发错误总数的 。(3)若 ，则不能检出的突发错误部分占同样长度的突发错误总数的 。knb1knb)1(2kn1knb)(2knv(n,k)循环码的监督位数越大时，不能被发现的突循环码的监督位数越大时，不能被发现的突发错误占的比例就越小。发错误占的比例就越小。 第六

23、节第六节 BCH码码一、代数知识简介一、代数知识简介BCH码是循环码的一个子类，其生成多项式与最小码距之码是循环码的一个子类，其生成多项式与最小码距之间有直接关系。间有直接关系。(1)多项式的根。多项式 的根以符号表示， 。(2)既约多项式：指不能在二元域内再分解因式的多项式。0)(f例：例： 是可约多项式，是可约多项式， 是既约多项式。是既约多项式。17x13 xx如果如果 是是 的根，则的根，则 。01313 xx001) 1() 1(101) 1() 1(111) 1() 1(110) 1(0111327223262232543三位元素的域记作 ，共有 个元素，其中001-111叫做非零

24、元素。称 是本原多项式，其根叫做本原元。)2(3GF82313 xx)(xf第六节第六节 BCH码码一般情况，一个m次既约多项式，如果其根 生成 中的所有非零元素，且两两不同，则此多项式称本原多项式，其根叫做本原元。1,.,1221m)2(mGF)2(mGF(1)m次既约多项式必为 的因式，其中 。(2)定义：设是 中的某一元素，若m(x)是以为根的既约多项式，则称m(x)是的最小多项式(称为一阶最小多项式)。(3)设是 中的本原元， 的最小多项式记作 ，称为i阶最小多项式。1nx12 mn)2(mGFi)2(mGF)(xmi(1)(n,k)BCH码是循环码，规定码长 ，其中m为本原多项式的次

25、数。由于规定BCH码的码长 ，所以BCH码是循环码的子类，且BCH码的生成多项式 必为 的因式。(2)本原BCH码的生成多项式 定义为第六节第六节 BCH码码i二、二、BCH码简述码简述BCH码分为两类：一类称本原BCH码，另一类是非本原BCH码。v本原本原BCH码的定义码的定义12mn12mn)(xg112mx)(xg)(),.,(),(),()(12531xmxmxmxmLCMxgtLCM-最小公倍式 - 的最小多项式)(xmi第六节第六节 BCH码码二、二、BCH码简述码简述如果已知码长n和最小码距d0，要求找到一个生成多项式 以编成BCH码，具体步骤为：(1)确定BCH码的码长n， 。

26、(2)将 因式分解，且分解后各因式都是既约多项式；(3)求本原多项式，它的根是本原元；(4)确定各因式是几阶最小多项式；(5)求出BCH码的生成多项式，确定BCH码的形式。12mn1nxv非本原非本原BCH码码非本原BCH码的定义和本原BCH码定义相同，只是把本原元用非本原元代替即可。非本原BCH码的码长n只要满足 条件，n就是 的因子。 1n12m要生成一个(n,k)循环码，只需要将 分解，找出一个次数等于n-k次的因式，就可以作为(n,k)循环码的生成多项式生成该码组。如果在 的分解式中有多个n-k次的因式，则把其中任意一个作为生成多项式，都可以生成一个(n,k)循环码。如果被选用的生成多项式的重量不同，它生成的循环码最小距离也不相同。即使对次数相同又具有相同重量的生成多项式，只要它们的重量分布不同，所生成的循环码码字的重量分布也不相同。第七节第七节 远动信息的远动信息的CRC校验校验一、生成多项式一、生成多项式1nx1nx第七节第七节 远动信息的远动信息的CRC校验校验一、生成多项式一、生成多项式我国部颁循环式远动规约规定，每帧远动信息中的控制字和信息字都采用CRC校验，并选用生成多项式 生成(48,40)循环码，其陪集为FFH。规约中的(48,40)循环码实际是(127,120)循环码进行增余删信(保证