通信原理樊昌信版第11章差错控制编码2

1、1第第1111章章 差错控制编码差错控制编码11.1 概述概述11.2 纠错编码的基本原理纠错编码的基本原理11.3 纠错编码的性能纠错编码的性能11.4 简单的实用编码简单的实用编码11.5 线性分组码线性分组码11.6 循环码循环码211.5 11.5 线性分组码线性分组码 (1) 分组码分组码： 先将信息码分组，然后给每组信码附加若干先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用符号监督码的编码称为分组码，用符号(n,k)表示，表示，k是信息码的位数，是信息码的位数，n是编码组总位数，又称为是编码组总位数，又称为码长，码长，r = n-k为监督位数。为监督位数。 (2)

2、 代数码代数码： 建立在代数学基础上的编码称为代数码。例建立在代数学基础上的编码称为代数码。例如奇偶校验码。如奇偶校验码。 1、基本概念、基本概念3 (3) 线性码线性码： 线性码中信息位和监督位是按一组线性码中信息位和监督位是按一组线性方线性方程程构成的。线性码是一种代数码。奇偶监督构成的。线性码是一种代数码。奇偶监督码是最简单的线性码。码是最简单的线性码。(4) 线性分组码线性分组码： 信息码分组后，附加的监督码和信息码由信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分一些线性代数方程联系着的编码称为线性分组码。组码。42、线性分组码的性质、线性分组码的性质任意两

3、个许用码组之和（对应位模任意两个许用码组之和（对应位模2和加）和加）仍为一许用码组，即具有仍为一许用码组，即具有封闭性封闭性。最小码距最小码距=非零码的最小码重非零码的最小码重 (1的个数的个数)。5 以汉明码为例来说明编码原理。以汉明码为例来说明编码原理。 汉明码是一种能够纠正一位错码且编码效汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。率较高的线性分组码。3、线性分组码的编码原理、线性分组码的编码原理6（1）回忆奇偶监督偶校验码）回忆奇偶监督偶校验码 发送端编码：将一位监督码元附加在信息发送端编码：将一位监督码元附加在信息码元后，使得码元中码元后，使得码元中“1”码元个数为偶数。

4、码元个数为偶数。 接收端译码：接收端译码：计数接收码组中计数接收码组中“1”码元个数是否为偶数，码元个数是否为偶数，即计算：即计算： (11.5-1)S=0认为没错，认为没错，S=1认为有错。认为有错。(11.5-1)式称为式称为监督方程监督方程/监督关系式监督关系式，S 称为称为校校正子正子/校验子校验子/伴随式伴随式。0121aaaaSnn7 监督位增加到监督位增加到2位：有两个监督方程，两个位：有两个监督方程，两个校正子；校正子； 两个校正子组合有四种（两个校正子组合有四种（00表示无错，表示无错，01、10、11表示表示1位错码的位错码的3种可能位置）种可能位置） 监督位增加到监督位增

5、加到r位：可指示位：可指示1位错码的位错码的(2r-1)个个可能位置可能位置对于对于(n,k)分组码，若用分组码，若用r=n-k个监督位构造出个监督位构造出的的r个监督关系式来指示个监督关系式来指示1位错码的位错码的n种可能位种可能位置，则要求：置，则要求： 可以这样来考虑可以这样来考虑:2r-1n 即即2r k+r+1 (11.5-2)8欲纠正一位错码，由欲纠正一位错码，由（11.5-2）式知式知r 3。取取r=3，则，则n=k+r=7设设7位码元为：位码元为：a6 a5 a4 a3 a2 a1 a0；三个伴随式：三个伴随式：S1、S2、S3；可规定可规定S1S2S3的八种组合与一位错码的对

6、应的八种组合与一位错码的对应关系（也可规定为另一种对应关系）：关系（也可规定为另一种对应关系）：构造一构造一 (n, k) 分组码，分组码，k=4并能纠正一位错码并能纠正一位错码(2) 汉明码的构造汉明码的构造2r-1n 即即2r k+r+1 （11.5-2）9S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错码无错码仅当一位错码的位置在仅当一位错码的位置在a2、a4、a5或或a6时，校时，校正子正子S1为为1；否则；否则S1为零。这就意味着为零。这就意味着a2、a4、

7、a5和和a6四个码元构成偶数监督关系：四个码元构成偶数监督关系：24561aaaaS10S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错码无错码24561aaaaS13562aaaaS03463aaaaS以及以及a0、a3、a4 和和a6构成偶数监督关系构成偶数监督关系:同理，同理， a1、a3、a5和和a6构成偶数监督关系：构成偶数监督关系：24561aaaaS13562aaaaS11（3）发端编码的原则）发端编码的原则 信息码元信息码元a6、a5、a4、a3来源于

8、待编码的来源于待编码的信息序列；信息序列； 监督码元监督码元 a2、a1、 a0的取值应的取值应根据信息码根据信息码元按监督关系式来决定，即使前面三式中元按监督关系式来决定，即使前面三式中的的S1、S2、S3均为均为0：000034613562456aaaaaaaaaaaa034631356224561aaaaSaaaaSaaaaS12000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa上式经过移项运算，解出监督位上式经过移项运算，解出监督位: 给定信息位后，可以直接按上式算出监督给定信息位后，可以直接按上式算出监督位，位， 结果见下表：结果见

9、下表：13信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111346035614562aaaaaaaaaaaa034631356224561aaaaSaaaaSaaaaS14该汉明码的编码效率较高该汉明码的编码效率较高=k/n = (n - r) /n =1 r/n，故当故当n很大和很大和r很小时，很小

10、时，码率接近码率接近1。可见，汉明码是一种高效码。可见，汉明码是一种高效码。 =k/n=4/757% 该码的该码的最小码距为最小码距为3，能纠正一个错码或检测，能纠正一个错码或检测两个错码。两个错码。设收到码组设收到码组0000011，按监督方程计算可得：，按监督方程计算可得：S1=0，S2=1，S3=1；根据校正子组合与一位错码；根据校正子组合与一位错码位置的对应关系，查表可知错码发生在位置的对应关系，查表可知错码发生在a3位，并位，并加以纠正。加以纠正。000101115（4）监督矩阵（）监督矩阵（ H 矩阵）矩阵）000034613562456aaaaaaaaaaaa上面上面(7, 4)

11、汉明码的例子有汉明码的例子有:现在将上面它改写为现在将上面它改写为:010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa上式中已经将上式中已经将“ ”简写成简写成“+”。160001001101010101100101110123456aaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa上式可以表示成如下矩阵形式：上式可以表示成如下矩阵形式：17H称为线性码监督矩阵。称为线性码监督矩阵。只要监督矩阵只要监督矩阵H 给定，给

12、定，编码时监督位和信息位的关系就完全确定了。编码时监督位和信息位的关系就完全确定了。 可化简为：可化简为：HAT=0T 或或AHT=0A = a6 a5 a4 a3 a2 a1 a0 0 = 000101100111010101110100H0001001101010101100101110123456aaaaaaa18监督矩阵监督矩阵H 特点：特点：001101101011011001110H1) H 的行数就是监督关系式的数目，它等于的行数就是监督关系式的数目，它等于监督位的数目监督位的数目r。H的每行中的每行中“1”的位置表示的位置表示相应码元之间存在的监督关系。相应码元之间存在的监督关

13、系。H矩阵可以矩阵可以分成两部分，例如分成两部分，例如P 为为r k 阶矩阵，阶矩阵，Ir为为r r 阶单位方阵。我阶单位方阵。我们将具有们将具有P Ir形式的形式的H 矩阵称为矩阵称为典型阵典型阵。rPI192) 由代数理论可知，由代数理论可知，H矩阵的各行应该是线性矩阵的各行应该是线性无关的无关的，否则将得不到，否则将得不到 r 个线性无关的监督关个线性无关的监督关系式，从而也得不到系式，从而也得不到 r 个独立的监督位。若一个独立的监督位。若一矩阵能写成典型阵形式矩阵能写成典型阵形式P Ir，则其各行一定，则其各行一定是线性无关的。因为容易验证是线性无关的。因为容易验证Ir的各行是线的各

14、行是线性无关的，故性无关的，故P Ir的各行也是线性无关的。的各行也是线性无关的。rPIH001101101011011001110203456012101111011110aaaaaaa346035614562aaaaaaaaaaaa(5) 生成矩阵生成矩阵( G 矩阵矩阵 ) 汉明码例子中的监督位公式为汉明码例子中的监督位公式为:可以改写成矩阵形式：可以改写成矩阵形式： Q34563456012011101110111aaaaaaaaaaa或者写成或者写成:21 Q34563456012011101110111aaaaaaaaaaaTaaaaP3456rPIH001101101011011

15、001110式中式中Q为一个为一个k r阶矩阵，为阶矩阵，为P的转置，的转置，Q = PT 上式表示，在信息位给定后，用信息位的行矩上式表示，在信息位给定后，用信息位的行矩阵乘矩阵阵乘矩阵Q就产生出监督位。就产生出监督位。011101110111Q22将将Q 的左边加上的左边加上1个个k k 阶单位方阵，构成矩阶单位方阵，构成矩阵阵GQGkI IG 称为称为生成矩阵生成矩阵，由它可以产生整个码组，由它可以产生整个码组:G34560123456aaaaaaaaaaaGA3456aaaa或者或者: Tkk1 0 0 0 1 1 10 1 0 0 1 1 0G IQ IP0 0 1 0 1 0 10

16、 0 0 1 0 1 1 生生 成成 矩矩 阵阵23G34560123456aaaaaaaaaaaGA3456aaaa或者或者 如果找到了码的生成矩阵如果找到了码的生成矩阵G，则编码的方法，则编码的方法就完全确定了。具有就完全确定了。具有IkQ形式的生成矩阵称为形式的生成矩阵称为典型生成矩阵典型生成矩阵。由典型生成矩阵得出的码组。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。中，信息位的位置不变，监督位附加于其后。这种形式的码称为这种形式的码称为系统码系统码。 QGkI I24(6) G 矩阵的性质矩阵的性质 G矩阵的各行是线性无关的。矩阵的各行是线性无关的。实际上，实际上

17、，G的各行本身就是一个码组。因此，的各行本身就是一个码组。因此，如果已有如果已有k个线性无关的码组，则可以用其作个线性无关的码组，则可以用其作为生成矩阵为生成矩阵G，并由它生成其余码组。，并由它生成其余码组。QGkI IG34560123456aaaaaaaaaaa Tkk1 0 0 0 1 1 10 1 0 0 1 1 0G IQ IP0 0 1 0 1 0 10 0 0 1 0 1 1 生生 成成 矩矩 阵阵250121bbbbnnB(7) 错码矩阵和错误图样错码矩阵和错误图样设发送码组为设发送码组为A，接收码组为，接收码组为B，0121aaaannA0121eeeeABnnE则错误矩阵：

18、则错误矩阵： (模模2)iiiiiiiabababe当当10260121eeeennEiiiiiiiabababe当当, 1, 0B A = E (模模2) B A = E 可以改写成可以改写成 B = A + E 例例: 若发送码组若发送码组A = 1000111， 错码矩阵错码矩阵E = 0000100， 则接收码组则接收码组B = 1000011。 错码矩阵有时也称为错码矩阵有时也称为错误图样错误图样。27当接收码组有错且未超过检错能力时，将当接收码组有错且未超过检错能力时，将B当当作作A代入上式，不成立，即其右端不等于代入上式，不成立，即其右端不等于0。假设这时该式的右端为假设这时该式

19、的右端为S，即，即B H T = S将将B = A + E代入上式，可得：代入上式，可得：校正子校正子SAHT = 0 B A = E (模模2)S = (A + E) HT = A HT + E HT= E HTS称为校正子。它能用来指示错码的位置。称为校正子。它能用来指示错码的位置。S和错码和错码E之间有确定的线性变换关系。若之间有确定的线性变换关系。若S和和E之间一一对应，则之间一一对应，则S将能代表错码的位置。将能代表错码的位置。284、线性分组码的性质、线性分组码的性质封闭性封闭性 是指一种线性码中的任意两个码组之和仍为是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。这种码

20、中的一个码组。 这就是说，若这就是说，若A1和和A2是一种线性码中的两个是一种线性码中的两个许用码组，则许用码组，则(A1+A2)仍为其中的一个码组。仍为其中的一个码组。证明：若证明：若A1和和A2是两个码组，则有：是两个码组，则有： A1 HT = 0,A2 HT = 0将上两式相加，得出：将上两式相加，得出：A1 HT + A2 HT = (A1 + A2) HT = 0所以所以(A1 + A2)也是一个码组。也是一个码组。29由于线性码具有封闭性，所以两个码组由于线性码具有封闭性，所以两个码组(A1和和A2)之间的距离（即对应位不同的数目）之间的距离（即对应位不同的数目）必定是另一个码组

21、必定是另一个码组(A1 + A2)的重量（即的重量（即“1”的数目）。因此，码的最小距离就是码的最的数目）。因此，码的最小距离就是码的最小重量（除全小重量（除全“0”码组外）。码组外）。30例例 已知（已知（6，3）汉明码的生成矩阵如下，）汉明码的生成矩阵如下，(1)列出所有许用码组列出所有许用码组; (2)最小码距最小码距d0;(3)检错纠错能力；检错纠错能力； (4)编码效率。编码效率。100101G010011001110 （1）列出所有许用码组）列出所有许用码组GA345aaa信息码信息码编码码字编码码字码重码重0 0 00 0 0 0 0 000 0 10 0 1 1 1 0 30

22、1 00 1 0 0 1 130 1 10 1 1 1 0 141 0 01 0 0 1 0 131 0 11 0 1 0 1 141 1 01 1 0 1 1 041 1 1 1 1 1 0 0 03（2）最小码距）最小码距0d3 （3）检错纠错能力）检错纠错能力（4）编码效率）编码效率000e=d -1=2d -1t=12et1det 该该码码可可以以检检2 2位位错错该该码码可可以以纠纠1 1位位错错该该码码不不能能同同时时用用于于检检错错与与纠纠错错k350%n6 3311.6 循环码循环码循环码是循环码是一种重要的一种重要的线性分组码线性分组码。这种。这种码的编码和解码设备都不太复杂

23、，且有较码的编码和解码设备都不太复杂，且有较强的检（纠）错能力。强的检（纠）错能力。共共n位。通常前位。通常前k 位为信息位，后位为信息位，后r 位位为为监督位。监督位。11.6.1 循环码编码原理循环码编码原理34循环码的循环码的特点特点： 封闭性封闭性；任意两个码组之和仍是一个码组任意两个码组之和仍是一个码组 循环性循环性；即码中任一码组循环一位；即码中任一码组循环一位(将最右将最右端的码元移到左端或反之）以后，仍为该码端的码元移到左端或反之）以后，仍为该码中的一个码组。中的一个码组。 (an-1,an-2,a1,a0)是某是某(n,k)循环码的码组，则：循环码的码组，则： (an-2 ,

24、an-3 ,a1,a0 ,an-1)(an-3 ,an-4 , , a0 , an-1 ,an-2) ( a0 ,an-1 , an-2 ,an-3 ,a2 ,a1) 也是该循环码的码组也是该循环码的码组35表表11-5 一种（一种（7，3）循环码的全部码组）循环码的全部码组码组码组编号编号信息位信息位监督位监督位码组码组编号编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010为便于计算，把码组中各码元当作多项式系数为便于计算，把码组中

25、各码元当作多项式系数若码组若码组A=(an-1,an-2,a1,a0)，则其相应的码，则其相应的码多项式为：多项式为：T(x)= an-1xn-1+ an-1xn-1+ + a1x+ a0对于（对于（7，3）循环码的任意码组可表示为：）循环码的任意码组可表示为： T(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0如码组（如码组（1100101）对应的码多项式可表示为）对应的码多项式可表示为T7(x)=1x6+1x5+ 0 x4 +0 x3 +1x2+0 x+1 = x6 + x5 + x2 +11、码多项式、码多项式T(x)37码多项式与码组的关系：码

26、多项式与码组的关系： 本质上是一回事，仅是表示方法的不同而已。本质上是一回事，仅是表示方法的不同而已。对于二进制码组，多项式的每个系数不是对于二进制码组，多项式的每个系数不是0就就是是1，x 仅是码元位置的标志。因此，这里并仅是码元位置的标志。因此，这里并不关心不关心x 的取值。的取值。如码组如码组 1100101 对应的码多项式可表示为对应的码多项式可表示为T7(x)=1x6+1x5+ 0 x4 +0 x3 +1x2+0 x+1 = x6 + x5 + x2 +138npnpQnm2、 循环码的运算循环码的运算(1) 整数的按模运算整数的按模运算在整数运算中，有模在整数运算中，有模n运算。例

27、如，在模运算。例如，在模4运运算中，有算中，有: 1 + 1 = 2 0 1 + 2 = 3 1 2 3 = 6 0 等等。等等。一般说来，若整数一般说来，若整数m可以表示为可以表示为:式中，式中，Q为整数，则在模为整数，则在模n运算下，有运算下，有:m p (模模n)在模在模n运算下，整数运算下，整数m等于它被等于它被n除得的余数。除得的余数。39)()()()(xRxQxNxF）（模)()()(xNxRxF(2) 码多项式的按模运算码多项式的按模运算 若任意一个多项式若任意一个多项式F(x)被一个被一个n次多项式次多项式N(x)除，得到商式除，得到商式Q(x)和一个次数小于和一个次数小于n

28、的余式的余式R(x)，即，即:则在按模则在按模N(x)运算下，有运算下，有 这时，码多项式系数仍按模这时，码多项式系数仍按模2运算，即系数运算，即系数只取只取 0 和和1。40）（模) 1(133xx）模) 1(113224xxxxx同理：同理：例：例：x3被被(x3 + 1)除，得到余项除，得到余项1，即，即因为因为 应当注意，由于在模应当注意，由于在模2运算中，用加法代替了运算中，用加法代替了减法，故余项不是减法，故余项不是x2 x + 1，而是，而是x2 + x + 1。在模在模2运算中加法和减法一样。运算中加法和减法一样。 xx3 + 1 x4 +x2 + 1 x4 + x x2 +x

29、 +141(3) 循环码的数学表示法循环码的数学表示法 在循环码中，设在循环码中，设T(x)是一个长度为是一个长度为n的码组，的码组，若若: 则则T (x)也是该编码中的一个码组，是码组也是该编码中的一个码组，是码组T (x)向左循环移位向左循环移位 i 次的结果。次的结果。）（模) 1()()(nixxTxTx421)(256xxxxTxxxxxxxxxTx23535893)(例：例： 一循环码为一循环码为1100101，即，即若给定若给定 i = 3，则有，则有 上式对应的码组为上式对应的码组为0101110，它正是，它正是T(x)向左向左移移3位的结果。位的结果。 结论：一个长为结论：一

30、个长为n的循环码必定为按模的循环码必定为按模(xn + 1)运算的一个余式。运算的一个余式。 ）（模) 1(7x43(4) 循环码的生成多项式与生成矩阵循环码的生成多项式与生成矩阵GA3456aaaa 可知，有了生成矩阵可知，有了生成矩阵G，就可以由，就可以由k个信息位个信息位得出整个码组，而且生成矩阵得出整个码组，而且生成矩阵G的每一行都是的每一行都是一个码组。由于一个码组。由于G是是k行行n列的矩阵，因此若能列的矩阵，因此若能找到找到k个已知码组个已知码组(必须是线性不相关的必须是线性不相关的)，就，就能构成矩阵能构成矩阵G。44在循环码中，一个在循环码中，一个(n, k)码有码有2k个不

31、同的码组。个不同的码组。若用若用g(x)表示其中前表示其中前(k-1)位皆为位皆为“0”的码组，的码组，则则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码都是码组，而且这组，而且这k个码组是线性无关的。因此它们个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵可以用来构成此循环码的生成矩阵G。在循环码中除全在循环码中除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的码组，即连的码组，即连“0”的长度最多只能的长度最多只能有有(k - 1)位。位。 45g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n - k)次次多项式，而且这个多项式，

32、而且这个g(x)还是这种还是这种(n, k)码中次码中次数为数为(n k)的的唯一唯一多项式。多项式。我们称这唯一的我们称这唯一的(n k)次多项式次多项式g(x)为码的为码的生成多项式生成多项式。一旦确定了。一旦确定了g(x)，则整个，则整个(n, k)循环码就被确定了。循环码就被确定了。 因此，循环码的生成矩阵因此，循环码的生成矩阵G可以写成可以写成)()()()()(21xgxxgxgxxgxxkkG46例：表例：表11-5所给出的所给出的(7, 3)循环码中，循环码中，n=7, k=3, nk=4。由表可见，唯一的一个。由表可见，唯一的一个(n k)= 4次码次码多项式代表的码组是第二

33、码组多项式代表的码组是第二码组0010111，与它相，与它相对应的码多项式（即生成多项式）：对应的码多项式（即生成多项式）：g(x) = x4 + x2 + x + 1。将此。将此g(x)代入上式，得到代入上式，得到)()()()(2xgxxgxgxxG0010111010111010111001)(242352346xxxxxxxxxxxxG)()()()()(2456456xgxxgxgxaaaxaaaxTG可以写出此循环码组，即可以写出此循环码组，即:47)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaa

34、axTG上式表明，所有码多项式上式表明，所有码多项式T(x)都可被都可被g(x)整除，整除，而且任意一个次数不大于而且任意一个次数不大于(k 1)的多项式乘的多项式乘g(x)都是码多项式。都是码多项式。48可以证明生成多项式可以证明生成多项式g(x)具有以下特性：具有以下特性： （1） g(x)是一个常数项为是一个常数项为1的的 次次多项式；多项式； （2） g(x)是是 的一个因式；的一个因式； （3）该循环码中其它码多项式都是）该循环码中其它码多项式都是g(x)的倍式。的倍式。 g(x)， xg(x) ， xk-1g(x)。knr1nx49由上式可知，任一循环码多项式由上式可知，任一循环码

35、多项式T(x)都是都是g(x)的倍式，故它可以写成的倍式，故它可以写成 : T(x) = h(x) g(x)而生成多项式而生成多项式g(x)本身也是一个码组，即有本身也是一个码组，即有 T (x) = g(x)由于码组由于码组T (x)是一个是一个(n k)次多项式，故次多项式，故xkT (x)是一个是一个n次多项式。由下式次多项式。由下式）（模) 1()()(nixxTxTx(5)如何寻找任一如何寻找任一(n, k)循环码的生成多项式循环码的生成多项式 50）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx 可知，可知，xk T (x)在模在模(xn + 1)运算

36、下也是一运算下也是一个码组，故可以写成：个码组，故可以写成：上式左端分子和分母都是上式左端分子和分母都是n次多项式，故商式次多项式，故商式Q(x) = 1。因此，上式可以化成：。因此，上式可以化成：)() 1()(xTxxTxnk 将将T(x) = h(x) g(x)和和T (x) = g(x)代入上式并代入上式并化简。化简。51)() 1()(xTxxTxnk)()(1xhxxgxknT(x) = h(x) g(x) T (x) = g(x) 上式表明，上式表明，生成多项式生成多项式g(x)应该是应该是(xn + 1)的的一个因子一个因子。这一结论为我们寻找循环码的生成。这一结论为我们寻找循

37、环码的生成多项式指出了一条道路，即循环码的生成多项多项式指出了一条道路，即循环码的生成多项式应该是式应该是(xn +1)的一个的一个(n k)次因式。次因式。52例：例：试求（试求（7，3）循环码的生成多项式和生）循环码的生成多项式和生成矩阵。成矩阵。解解1：对（：对（7, 3）循环码，）循环码，n=7，k=3, r=4由于由于g(x)是一个常数项为是一个常数项为1的的 n-k次多项式，次多项式，查表查表11-5知知生成多项式为：生成多项式为：g(x)= x4+x2+x+11)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG53生成多项式生成多项式g(x)是是xn+

38、1的一个因式，且的一个因式，且g(x)是一是一个个r 次因式。次因式。因此，就可以先对因此，就可以先对xn+1进行因式分解，找到它进行因式分解，找到它的的r 次次因式。因式。下面仍以（下面仍以（7，3）循环码为例进行分析。）循环码为例进行分析。 54解解2：对（：对（7, 3）循环码，）循环码，n=7，k=3, r=4第一步：第一步：对对x7+1进行因式分解进行因式分解得：得： x7+1=(x+1)(x3+x2+1)(x3+x+1) .(1)第二步：第二步：构造构造r 次生成多项式次生成多项式g(x)。从从(1)中找中找r=n-k=4次的因子次的因子,这样的因子有两个这样的因子有两个： (x+

39、1)(x3+x2+1)=x4+x2+x+1(a) (x+1)(x3+x+1)=x4+x3+x2+1(b)第三步：若按第三步：若按(a)构成生成多项式构成生成多项式:生成多项式为：生成多项式为：g(x)= x4+x2+x+1例例求求(7,3)循环码的生成多项式和生成矩阵。循环码的生成多项式和生成矩阵。1)()()()(2423523462xxxxxxxxxxxxgxxgxgxXG生成矩阵为：生成矩阵为：为典型生成为典型生成矩阵矩阵111010001110101101001G生成多项式为：生成多项式为：g(x)= x4+x2+x+1111010001110100011101G将第将第1行与第行与第

40、3行行模模2加加作为第作为第1行，则有行，则有若按若按(b)构成生成多项式构成生成多项式:生成多项式为：生成多项式为：g(x)= x4+x3+x2+11)()()()(23434524562xxxxxxxxxxxxgxxgxgxXG101110011100100111001G进行线性变换，得进行线性变换，得典型生成矩阵典型生成矩阵为：为：101110001011100010111G生成矩阵为：生成矩阵为：571111111111010011010011100010101100010100111001110100010101110100110001010110001001110011101001

41、011000010110000000例：已知（例：已知（7，4）循环码的全部码组为：）循环码的全部码组为：试写出该循环码的生成多项式试写出该循环码的生成多项式g(x)和生和生成矩阵成矩阵G，并将，并将G化成典型矩阵。化成典型矩阵。解：解：n=7，k=4，n-k=3。码组中的。码组中的(n-k)=3次码次码多项式为第多项式为第2组，它所对应的码多项式组，它所对应的码多项式g(x)即即为生成多项式：为生成多项式：g(x)=x3+x+1。58g(x)=x3+x+1。生成矩阵为：生成矩阵为：364325321423x g(x)xxxx g(x)xxxG (x)x g(x)xxxg(x)xx110110

42、001000101010110001001110010110001011000010110001011 364325321423x g(x)xxxx g(x)xxxG(x)x g(x)xxxg(x)xx110110001000101010110001001110010110001011000010110001011 364325321423x g(x)xxxx g(x)xxxG(x)x g(x)xxxg(x)xx11011000100010101011000100111001011000101100001011000101159 首先从首先从xn+1的因子中选一个（的因子中选一个（n-k）次多

43、）次多项式作为项式作为g(x)； 然后，利用循环码的编码特点，即所有循然后，利用循环码的编码特点，即所有循环码多项式环码多项式T(x)都可以被都可以被g(x)整除，来定义整除，来定义生成多项式生成多项式g(x)。 11.6.2 循环码的编码、解码方法循环码的编码、解码方法1、循环码的循环码的编码方法编码方法（1）原理）原理60设信息位对应的多项式为设信息位对应的多项式为m(x)用用xn-k乘乘m(x)，相当于把信息码后附加上，相当于把信息码后附加上(n-k)个个“0” 用用g(x)除除xn-k m(x)，得到余式为，得到余式为r(x)编出码组为：编出码组为：T(x)= xn-k m(x)+ r

44、(x) xgxrxQxgxmxkn(2)编码步骤编码步骤61例如例如:信息码为信息码为110，它相当于，它相当于m(x)x2+x。 当当n-k7-34时，时， xn-k m(x)x4(x2+x)= x6+x5，相当于，相当于1100000。而希望的到得系统循环码多项式应当是而希望的到得系统循环码多项式应当是: T(x) = xn-k m(x) + r(x)。 6211) 1(1)()(24222456xxxxxxxxxxxxgxmxkn即余式即余式r(x)=x2+1则对应码组则对应码组T(x)= xn-k m(x)+r(x)= x6+x5+ x2+1编码为编码为1100101例例 设设(7,3

45、)循环码的生成多项式为循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为，待编码信息位为110，求对应，求对应循环码码组。循环码码组。解：解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5632、循环码的解码方法、循环码的解码方法（1）解码要求：检错和纠错。）解码要求：检错和纠错。（2）检错解码原理）检错解码原理 由于任意一个码组多项式由于任意一个码组多项式T(x)都应该能被都应该能被生成多项式生成多项式g(x)整除，所以在接收端可以将整除，所以在接收端可以将接收码组接收码组R(x)用原生成多项式用原生成多项式g(x)去除。去除。传输中未发生错误：接收码组与

46、发送码组传输中未发生错误：接收码组与发送码组相同，即相同，即R(x) = T(x)，故接收码组，故接收码组R(x)必定能必定能被被g(x)整除；整除；64传输中发生错误，则传输中发生错误，则R(x) T(x)，R(x)被被g(x)除时可能除不尽而有余项，即有：除时可能除不尽而有余项，即有：)(/ )()()(/ )(xgxrxQxgxR 以余项是否为零来判别接收码组中有无错码。以余项是否为零来判别接收码组中有无错码。 有错码的接收码组也有可能被有错码的接收码组也有可能被g(x)整除，这整除，这时的错码就不能检出了。这种错误称为时的错码就不能检出了。这种错误称为不可不可检错误检错误。不可检错误中

47、的误码数必定超过了。不可检错误中的误码数必定超过了这种编码的检错能力。这种编码的检错能力。65（3）纠错解码原理）纠错解码原理为了能够纠错，要求每个可纠正的错误图样必为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。原则上纠须与一个特定余式有一一对应关系。原则上纠错可按下述步骤进行：错可按下述步骤进行：用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)，得出余，得出余式式r(x)。按余式按余式r(x)，用查表的方法或通过某种计算，用查表的方法或通过某种计算得到错误图样得到错误图样E(x)；如通过计算校正子；如通过计算校正子S和查和查表，可确定错码的位置。表，可确

48、定错码的位置。从从R(x)中减去中减去E(x)，便得到已经纠正错码的，便得到已经纠正错码的原发送码组原发送码组T(x)。6611.6.3 截短循环码截短循环码截短目的截短目的：在设计纠错编码方案时，常常：在设计纠错编码方案时，常常信息位数信息位数k、码长、码长n和纠错能力都是预先给定和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。方法，得出满足要求的编码。67截短方法截短方法：设给定一个：设给定一个(n, k)循环码，它循环码，它共有共有2k种

49、码组，现使其前种码组，现使其前i (0 i k)个信息个信息位全为位全为“0”，于是它变成仅有，于是它变成仅有2k-i种码组。种码组。然后从中删去这然后从中删去这i位全位全“0”的信息位，最终的信息位，最终得到一个得到一个(n i, k i)的线性码。将这种码称的线性码。将这种码称为为截短循环码截短循环码。截短循环码性能截短循环码性能：循环码截短前后至少具：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截有相同的纠错能力，并且编解码方法仍和截短前的方法一样。短前的方法一样。68例例：要求构造一个能够纠正：要求构造一个能够纠正1位错码的位错码的(13,9)码。这时可以由码。这时可以由(

50、15,11)循环码的循环码的11种码组中种码组中选出前两信息位均为选出前两信息位均为“0”的码组，构成一个的码组，构成一个新的码组集合。然后在发送时不发送这两位新的码组集合。然后在发送时不发送这两位“0”。于是发送码组成为。于是发送码组成为(13,9)截短循环码。截短循环码。 6911.6.4 BCH码码什么是什么是BCH码？码？ 它是一种获得广泛应用的能够纠正多个错码它是一种获得广泛应用的能够纠正多个错码的循环码，是以的循环码，是以3位发明这种码的人名位发明这种码的人名(Bose - Chaudhuri - Hocguenghem)命名的。命名的。 BCH码的重要性在于它解决了生成多项式与码

51、的重要性在于它解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。有了生成求的条件下寻找到码的生成多项式。有了生成多项式，编码的基本问题就随之解决了。多项式，编码的基本问题就随之解决了。70BCH码分类：码分类：本原本原BCH码码：其生成多项式：其生成多项式g(x)中含有最高中含有最高次数为次数为m的本原多项式，且码长为的本原多项式，且码长为n=2m1，(m 3，为正整数，为正整数)。非本原非本原BCH码码：其生成多项式中不含这种：其生成多项式中不含这种本原多项式，且码长本原多项式，且码长n是是(2m 1)的一个因子

52、，的一个因子，即码长即码长n一定除得尽一定除得尽2m 1。本原多项式：不能分解因子；可整除本原多项式：不能分解因子；可整除xm+1 (m=2n-1);除不尽除不尽xq+1 (qm)。71BCH码的性能：码的性能：码长码长n与监督位、纠错个数与监督位、纠错个数 t 之间的关系：之间的关系： 对于正整数对于正整数m (m 3)和正整数和正整数t1，且除得尽，且除得尽(2m -1)），），则为非本原则为非本原BCH码。码。72汉明码是能够纠正单个随机错误的码。可汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原单个随机错误的本原BCH码。码。例如，例如，(7, 4)汉明码就是以汉明码就是以g1(x) = x3 + x + 1或或g2(x) = x3+x2+1生成的生成的BCH码，而用码，而用g3(x) = x4 + x + 1或或g4(x) = x4 + x3 + 1都能生成都能生成(15, 11)汉明码。汉明码。73 BCH码的设计码的设计 在工程设计中，一般不需要用计算方法在工程设计中，一般不需要用计算方法去寻找生成多项式去寻找生成多项式g(x)。因为前人早已将寻。因为前人早已将寻找到的找到的g(x)列