信息论与编码第四讲

1、信息论与编码第四讲第1页，共63页，2022年，5月20日，1点17分，星期一主要内容1、循环码代数基础2、 BCH码3、 BCH译码第2页，共63页，2022年，5月20日，1点17分，星期一1.1 几个名词元素：近代代数的运算对象。集合：一组元素或若干个元素的全体。代数系统：包含集合和一种或几种代数运算（用符号“*”表示）的系统。一、循环码代数基础第3页，共63页，2022年，5月20日，1点17分，星期一1.2 群群，是包含集合G和一种代数运算*，且满足下列条件的代数系统：（a）运算封闭；（b）有单位元；（c）有逆元；（d）满足结合律。加法群：满足加法和逆运算的群。乘法群：满足乘法和逆运

2、算的群。交换群：满足交换律的群。子群：一个非空集合S G，S满足群G的全部条件，则S称为子群。第4页，共63页，2022年，5月20日，1点17分，星期一 无限群：包含无数个元素的群。 有限群：包含有限个元素的群。有限群元素的个数称为该群的阶。 循环群： 某一元素a（生成元a）的一切乘幂a0, a1, a2,的全体组成一个群，称为循环群，写作G = a0, a1, a2, ,其中a0= e是单位元。 若序列a0= e，a1, a2, 中没有两个元素是相等的，称之为无限循环群。第5页，共63页，2022年，5月20日，1点17分，星期一 若上述序列中有两个相等的元素a i= a j, (ij)，

3、可推出G 的元素必以n为周期重复，即an = a0=e , 这样的循环群称为有限循环群。 循环群也叫幂群，具有以下性质： （a）循环群是交换群； （b）循环群的子群仍是循环群； （c）n阶循环群子群的阶数一定是n的因子。第6页，共63页，2022年，5月20日，1点17分，星期一例例1：令R、I、E分别是有理数、整数、偶数集合，则(E,+)是(I,+)的子群，则(I,+)是(R,+)的子群，单位元均是0。奇数集合O在加法运算下构不成群，因不满足封闭性条件。例3 集合G = 0,1,2 m-1在模m加（用符号表示）运算下构成一个群（G，）。 该加群是m阶有限群，单位元是0。元素0的逆元是0，1的

4、逆元是m-1, 2的逆元是m-2,。例4：集合G = 1,2 q-1在模q乘（q是素数）运算下构成一个乘群（G，）。第7页，共63页，2022年，5月20日，1点17分，星期一1.3 环 环，包含集合R和两种代数运算，且满足下列条件的代数系统： （a）按第一种运算（不妨称为加法）构成交换群； （b）第二种运算（不妨称为乘法）满足以下条件：封闭性；结合律；单位元；（c）与加法间满足分配律：对于a,b,c R，a(b+c)=ab+ac, (a+b)c=ac+bc。交换环： 对于a,b R，ab=ba(交换律)，则称R为交换环。第8页，共63页，2022年，5月20日，1点17分，星期一1.4 域域

5、，具有交换环的性质，且在乘法运算时具有逆元的代数系统。域具有加和乘两种运算及它们的逆运算。无限域 有理数、实数和复数都是无限域。有限域：包含有限个（q）元素的域，或称伽罗华域。q称为域的阶。在信道编码中用到的是有限域，GF(q)。(0,1) 二元域GF(2)，或称基本域。由GF(2) GF(2m )，称扩域。第9页，共63页，2022年，5月20日，1点17分，星期一 可以证明： 伽逻华域GF(q) 的 (q-1)个非零元素在模 q 乘运算下构成一个循环群（幂群），即所有非零元素可由一个元素（称作本原元）的各次幂 0、1、2、q-2 生成。 第10页，共63页，2022年，5月20日，1点17

6、分，星期一1.5 既约多项式 对于某数域上的多项式PI（x），若除了常数C以及CPI（x）外不能被该数域上的任何其它多项式整除，则称为是该数域上的既约多项式。 如：x4+x+1 第11页，共63页，2022年，5月20日，1点17分，星期一1.6 本原多项式 对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简单多项式(x n -1)的次数n qm 1, 则称该多项式为本原多项式。本原多项式一定既约；既约多项式未必本原。如： m 本原多项式 3 1+x+x3 4 1+x+x4 5 1+x2+x5 6 1+x+x6 第12页，共63页，2022年，5月20日，1点17分，星期一比如

7、：在GF(2)域上，x4+x+1 (q=2, m=4, 2m-1=15) 不能被 x5+1 整除； 不能被 x6+1 整除； 不能被 x14+1 整除； 能被 x15+1 整除；所以 x4+x+1 是本原多项式。 而 x4+ x3+ x2+ x+1 能被 x5+1 整除； 能被 x15+1 整除；所以，x4+x3+x2+x+1是既约的，但不是本原的。第13页，共63页，2022年，5月20日，1点17分，星期一本原元 对于m次本原多项式p(x)，如果p(a)=0, 那么a是GF(2m)的一个本原元。 利用本原多项式可求扩域GF(2m)的全部元素为：第14页，共63页，2022年，5月20日，1

8、点17分，星期一举例p(x)=x2+x+1，求GF(22)的全部元素及加法乘法表。分析：令p(a)=0，得a2+a+1=0 ，a2a+1。那么全部元素为：幂表示矢量表示多项式表示0a0a1a2=a+10001101101xx+1第15页，共63页，2022年，5月20日，1点17分，星期一1.6 GF(q)的加、乘、减和除在GF(q)中，对元0,1,2,q-1使用mod q的计算方法：进行加法和乘法。如GF(3)的加法和乘法如下表：+0 1 20120 1 21 2 02 0 1.0 1 20120 0 00 1 20 2 1第16页，共63页，2022年，5月20日，1点17分，星期一减法：

9、a-b=a-b+q mod q如: 1-2=1-2+3=2 mod 3除法：b/a=b. a-1 mod q如：因为22=1 mod 3，2的乘法逆元2-1为2，所以： 2/2=2 2-1=2 2=1 第17页，共63页，2022年，5月20日，1点17分，星期一二、BCH码第18页，共63页，2022年，5月20日，1点17分，星期一2.1 GF(2m)域上构造循环码的方法第19页，共63页，2022年，5月20日，1点17分，星期一 xn-1 因式分解 (4-17)这里，既约因式mj(x)（j=0,l-1）分成两部分，它们的乘积分别是g(x)和 h(x)。循环码并不强调g(x)的既约性，它

10、可以是既约的，也可以是非既约的。若某既约因式mj(x)是非既约g(x)的一个因式，必有： mj(x) | g(x) | (xn-1) (4-18) 换一个角度，如果将(xn-1)看成是一个n次多项式，那么它在复数域应该有n个根，记作ai，i=0,n-1，此时(xn-1)可表示成xn-1=(x-a0) (x-a1) (x-an-1) (4-19)第20页，共63页，2022年，5月20日，1点17分，星期一例4 -7 （x4-1）在不同域上的因式分解在实数域的分解：x4-1= (x2+1)(x+1)(x-1)在复数域的分解：x4-1= (x+i) (x-i) (x+1)(x-1)在二元域的分解：

11、x4-1= x4+1= (x+1)(x+1) (x+1)(x+1)上例说明：域不同则分解亦不同，在一个域的既约不等于在另一个域的既约。既约多项式mj(x)在GF(2)上不能再分解，其系数在数域取值于0,1；但它在二元扩域GF(2m)未必就不能再分解，因GF(2m) 是多项式域，系数取值于0、1、2、 。第21页，共63页，2022年，5月20日，1点17分，星期一根据定理4.1：只要找到与循环码对应的一个n 阶元素，就可以将(xn -1)在GF(2m)上完全分解为： xn-1 =证：若 a是循环群n 阶元素，必有an = 1 即(an -1)=0 将ai,i=0n-1代入(xn-1)验根， 得

12、 (ai)n-1= (a n) i -1= (1)i-1= 0 ai,i=0n-1是(xn-1)的n个根，以根为一次项可将(xn-1 )完全分解为： xn-1=(x-a0) (x-a1) (x-an-1) 第22页，共63页，2022年，5月20日，1点17分，星期一 二元扩域GF(2m)是由一m次本原多项式生成的。当n=2m-1时，这个n阶域元素a就是(2m-1)阶本原元，通常用表示本原元；当n(2m-1)且n|(2m-1)时，这个n阶域元素a为非本原元，通常用表示非本原元。这里不强调域元素是否本原，所以用中性字母a来表示。 = xn-1 = GF(2m)扩域 | GF(2)域 系数1既是扩

13、域又是二元域元素或改变顺序为 = = xn-1 第23页，共63页，2022年，5月20日，1点17分，星期一若(xn-1)的某一个根ai , i0,1n-1又是某个既约因式mj(x), j0,1l-1的根，也是(n-k)次生成多项式g(x)的根，那么必有：a为n阶本原元时： (x-ai) | mj(x) | g(x) | (xn-1)=( )(4-22)a为n阶非本原元时： (x-ai) | mj(x) | g(x) | (xn-1) | ( )(4-23)以上两式说明：生成多项式g(x)的（n-k）个根也是(xn-1)的根，只要能够以适当的方法找出这些根，就可以从这些根得到生成多项式g(x

14、)。第24页，共63页，2022年，5月20日，1点17分，星期一研究表明：有重根的g(x)不能产生好码。而如果 (xn-1)无重根，则g(x)肯定无重根。在GF(qm)上(xn-1)无重根的充要条件是n、q互素。(xn-1)的n个根中，(n-k)个根也是g(x)的根，剩下的k个根一定也是h(x)的根。 因此如果 (xn-1)无重根，h(x)肯定也无重根。第25页，共63页，2022年，5月20日，1点17分，星期一 用(xn-1)在GF(2m)域上的根来构造循环码的方法： 在(xn-1)的n个根中选取若干个r1、r2rj， 其中 rj ai, i=0,1n-1。 找出各根对应的既约多项式r1

15、m1(x)、 r2m2(x)rjmj (x)。 求出这些既约多项式的最小公倍式： g(x)=LCMm1(x), m2(x)mj (x) LCM (Least Common Multiple) - 最小公倍式若选取的根是连续幂次的根，则所得的g(x)可以产生一个BCH码。第26页，共63页，2022年，5月20日，1点17分，星期一2.2 BCH码的定义 GF(q)域循环码生成多项式g(x)，若含有2t个连续幂次的根 ，则由g(x)生成的(n,k)循环码称为q进制BCH码。连续幂次起始值m0的选取并无多大实际意义，通常固定取m0=1。 若q=2，称为二进制（二元）BCH码。 若根a是本原元，称该

16、码为本原BCH码，其码长n=qm-1。 若根a是非本原元，称该码为非本原BCH码，其码长n是qm-1的因子，满足n | (qm-1)。 第27页，共63页，2022年，5月20日，1点17分，星期一BCH码限定理：若BCH码生成多项式g(x)中含有2t个连续幂次的根，则该码的最小距离dmim 2t+1证明： BCH码多项式C(x)=m(x)g(x) g(x)的2t个连续幂次根、2t也是C(x)的根设 C(x)= c0+ c1x + c2 x2+ cn-1 xn-1以根x = 代入， 得 c0+ c1 + c2 2+ cn-1 n-1 = 0以x = 2代入，得 c0+c12 +c2(2) 2+

17、cn-1(2)n-1= 0 以x = 2t代入，得c0+c12t+c2(2t)2+cn-1(2t)n-1= 0 第28页，共63页，2022年，5月20日，1点17分，星期一将上面2t个方程写作矩阵形式，得：CAT= 0(4-24) 其中： A = =可见，A是范得蒙矩阵。数学证明：范得蒙矩阵一定是满秩矩阵，即矩阵A的秩是2t或者说有2t列线性无关。码的最小距离dmin等于校验矩阵中线性无关的列数加1，因此BCH码最小距离为： dmin = 2t +1 (4-26) 1 2 n-1 1 2 (2)2 (2) n-1 1 2t (2t)2 (2t) n-1 1 2 n-1 1 2 (2)2 (n

18、-1)2 1 2t (2)2t (n-1)2t第29页，共63页，2022年，5月20日，1点17分，星期一 2.3 本原BCH码构造法 由关系式n=2m-1算出m，查表4-5，找到一个m次本原多项式P(x)，产生一个GF(2m)扩域。 在GF(2m)上找一个本原元，分别计算2t个连续幂次根、2、2t所对应的GF(2)域上的最小多项式m1(x)、m2(x)m2t(x)。m8时连续幂次根i所对应的最小多项式见表4-6。 计算这些最小多项式的最小公倍式，得到生成多项式g (x) g(x)=LCMm1(x) m2(x) m2t(x) (4-27) 由关系式C(x)=m(x)g(x) 求BCH码字。

19、第30页，共63页，2022年，5月20日，1点17分，星期一对于二元BCH码，无需列出全部2t个连续幂次的根，而只要列出其中一半（奇数幂次的根）就可以了。这是因为任何一个偶数ie 可写成一个小于它的奇数io 与2的l次幂的乘积： ie =io2l , ioie(4-28)比如2=121，4=122，10=521，12=322 因此任何一个偶次幂根都是奇次幂根的共轭元 它们对应同一个最小多项式。第31页，共63页，2022年，5月20日，1点17分，星期一i最小多项式i最小多项式i最小多项式i最小多项式m = 21(0,1,2)m = 31(0,1,3)3(0,2,3)m = 41(0,1,4

20、)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m = 51(0,2,5)3(0,2,3,4,5)5(0,1,2,4,5)7(0,1,2,3,5)11(0,1,3,4,5)15(0,3,5)m = 61(0,1,6)3(0,l,2,4,6)5(0,l,2,5,6)7(0,3,6)9(0,2,3)11(0,2,3,5,6)13(0,1,3,4;6)15(0,2,4,5,6)21(0,1,2)23(0,1,4,5,6)27(0,1,3)31(0,5,6)m = 71(0,3,7)3(0,1,2,3,7)5(0,2,3,4,7)7(0,1,2,4,5,6,7)9(0,1,2,3,4,5,7

21、)11(0,2,4,6,7)13(0,1,7)15(0,1,2,3,5,6,7)19(0,1,6,7)21(0,2,5,6,7)23(0,6,7)27(0,1,4,6,7)29(0,1,3,5,7)31(0,4,5,6,7)43(0,l,2,5,7)47(0,3,4,5,7)55(0,2,3,4,5,6,7)63(0,4,7)m = 81(0,2,3,4,8)3(0,1,2,4,5,6,8)5(0,1,4,5,6,7,8)7(0,3,5,6,8)9(0,2,3,4,5,7,8)11(0,1,2,5,6,7,8)13(0,1,3,5,8)15(0,1,2,4,6,7,8)17(0,1,4)19(

22、0,2,5,6,8)21(0,l,3,7,8)23(0,1,5,6,8)25(0,1,3,4,8)27(0,1,2,3,4,5,8)29(0,2,3,7,8)31(0,2,3,5,8)表4-6二元扩域GF(2m)中连续幂次根所对应的最小多项式 第32页，共63页，2022年，5月20日，1点17分，星期一比如t=4时8个连续幂次根 2 3 4 5 6 7 8中， 2 4 8是共轭元，3 6是共轭元，于是g(x)=LCMm1(x) m2(x) m3(x) m4(x) m5(x)m6(x)m7(x)m8(x)= LCMm1(x) m2(x) m4(x) m8(x) m3(x) m6(x) m5(x

23、) m7(x)= LCMm1(x) m3(x) m5(x) m7(x)因此对于二进制码，构造本原BCH码的步骤改为: 分别计算t个连续奇次幂之根、32t-1所对应的最小多项式m1(x)、m3(x)m2t-1(x)。第33页，共63页，2022年，5月20日，1点17分，星期一当码长n确定后，BCH码纠错能力t的选择并不是任意的，而要受到一定限制。对于q元BCH码，2t个根对应2t个最小多项式，每个最小多项式的次数不会超过m，于是2t个最小多项式的最小公倍式g(x)的次数： degg(x) = (n-k) 2t (4-29)对于二元BCH码，t个根对应t个最小多项式，因此 degg(x) = (

24、n-k) tm(4-30)(xn-1)一共有n个根，连续幂次根不能超过根的总数 2t n (4-31)式(4-29) (4-30)给出了t的下限，式(4-31)给出了t的上限。第34页，共63页，2022年，5月20日，1点17分，星期一例4.8 设计一个码长n = 15的二元本原BCH码，在不同纠错能力下的生成多项式应是怎样的？解： 15=24-1本题m = 4第一步：查表，找到一个m=4的本原多项式：P(x)=x4+ x+1。令是该本原多项式P(x)的根，满足4+ +1=0。由式(4-31)，本码纠错能力t 7。第二步：对于二元码，分别计算t=7个连续奇次幂之根 3 57 9 11 13所

25、对应的最小多项式。本例可参考例的表2-3，我们看到3、9是共轭元，7、11和13是共轭元（利用教材p124“共轭根系”定义分析）。第35页，共63页，2022年，5月20日，1点17分，星期一根和根所对应的最小多项式（例2.10）如下：根 m1(x) =p(x)=x4+ x+1 根3 m3(x) =(x+a3) (x+a6) (x+a9) (x+a12)=x4+ x3+ x2+ x+1 根5 m5(x) =(x+a5)(x+a10)=x2+ x+1 根7 m7(x) =x4+ x3+ 1 根9同3，根11、13同7。这里，m(x)的全部根为下列系列：并把w序列换成a的序列。第36页，共63页，

26、2022年，5月20日，1点17分，星期一 第三步：求最小公倍式得到生成多项式g(x)。若t =1，g1(x)=LCMm1(x) = x4+ x+1g1(x)是4次多项式，即n-k=4， k =15-4=11, 这就是(15,11)BCH码，也是汉明码。若t=2，g2(x)=LCMm1(x), m3(x) = m1(x)m3(x) = x8+ x7+ x6+x4+1，degg2(x)= n-k = 8， k =15-8=7，这是(15,7) BCH码。第37页，共63页，2022年，5月20日，1点17分，星期一若t=3， g3(x)=LCMm1(x), m3(x), m5(x) = m1(x

27、)m3(x) m5(x) = x10+ x8+ x5+ x4+x2 + x +1， degg3(x)= n-k = 10， k =15-10=5，这是(15,5) BCH码。若t=4， g4(x)=LCMm1(x), m3(x), m5(x), m7(x) = m1(x)m3(x) m5(x) m7(x) = x14+ x13+ x12+ x11+x10+ x9+ x8+ x7+x6 + x5+ x4+ x3 +x2 + x +1 degg4(x)= n-k = 14， k =15-14=1，这是(15,1) BCH码。第38页，共63页，2022年，5月20日，1点17分，星期一若t=5，g

28、5(x)=LCMm1(x), m3(x), m5(x), m7(x), m9(x) = m1(x)m3(x) m5(x) m7(x)= g4(x)若t=6，g6(x)=LCMm1(x), m3(x), m5(x), m7(x), m9(x) , m11(x)= m1(x)m3(x) m5(x) m7(x)= g4(x) 若t=7，g7(x)=LCMm1(x),m3(x),m5(x),m7(x), m9(x), m11(x),m13(x)=m1(x)m3(x) m5(x) m7(x)=g4(x)可见，当t=4、5、6、7时的BCH码均是(15,1)码，生成多项式g4(x)拥有x的所有各次幂，意味

29、着编码时将一位信息“0”或“1”重复发送15次。因此，实际上只有t=1,2,3的(15,11)、(15,7)、(15,5) BCH码才有实用价值。第39页，共63页，2022年，5月20日，1点17分，星期一 非本原BCH码与本原BCH码的主要区别在于所用的根是否本原元。 当码长n和纠错能力t给定后，本原BCH码的根一定是n=2m-1阶, n已知就是m已知，因而GF(qm)好找。 非本原BCH码的根是n阶元素, 满足n | (qm-1)， n已知不等于m已知，需要多一道计算。 第40页，共63页，2022年，5月20日，1点17分，星期一已知n和t后二元非本原BCH码的设计步骤： 求出满足 n

30、 | (2m-1)关系的m的最小值。n是(2m-1) 的因子，可以借助2m-1的素因子分解表（如表4-7）来寻找m值。 查表4-5，找出一个m阶的本原多项式P(x)， 产生一个二元扩域GF(2m)。 以P(x)的根为中介找出一个n阶的非本原元。 计算与、3、52t-1对应的最小多项式m1(x)、m3(x)m2t-1(x)。 求生成多项式g(x)=LCMm1(x) m3(x) m2t-1(x)。第41页，共63页，2022年，5月20日，1点17分，星期一表4-7 2m-1的素因子分解（m34） m素因子分解m素因子分解m素因子分解12345678910111373531337127351777

31、3311312389121314151617181920212233571381913431277311513517257131071333719735242873551l 3141771273373238968323242526272829303132334717848133571317241316011801327318191773262657352943113127233110320893371131151331214748364735172576553772389599479第42页，共63页，2022年，5月20日，1点17分，星期一例4.9 试设计一个码长n = 23，纠两个随机差

32、错(t =2)的二元BCH码。 解： 由于码长n 2m-1比如15、31、 255等值，可知要求设计的是二元非本原BCH码。检查能被n=23整除的2m-1(表4-7)，m的最小值是11 (211-1=2047=8923,能够整除23)，所以取m=11。 查表4-5, 得11阶的本原多项式是P(x)=x11+x2+1。令是本原多项式P(x)的根，满足11+2+1= 0。由于是本原元，它的阶数是211-1=2047，满足2047=1 。 为了得到23阶域元素，将2047=1改写为 2047 = 8923 = (89)23 = ()23 = 1, 式中= 89。 事实上，0,1,2,3,2047 本

33、身都是域元素， 只是将域元素89定义为域元素而已。由于(89)23 = ()23 = 1，因此可断言是一个23阶的非本原元。第43页，共63页，2022年，5月20日，1点17分，星期一 求连续奇幂次的根所对应的最小多项式。 首先找出的所有共轭元，然后再来计算最小多项式。 的共轭元有：, 2, 4, 8, 16, 32=239=9, 18, 36=2313=13, 26=3, 6, 12, 24=。 因24=完成了一个周期，所以这个周期的11个域元素都是共轭元。将它们重新按幂次顺序排列就是：, 2, 3,4,6, 8,9,12,13,16,18。由此可断定该BCH码的生成多项式g(x)至少是1

34、1次多项式，有11个根。 同理可得另一组共轭元5, 10, 20,17,11, 22,21, 19, 15,7,14，也是11个。第44页，共63页，2022年，5月20日，1点17分，星期一第一组所对应的最小多项式为m1(x)=(x+)(x+2)(x+3)(x+4)(x+6)(x+8)(x+9) (x+12)(x+13)(x+16)(x+18) = x11+ x9+ x7+x6 + x5 + x +1在上式运算过程中用到23=1, =89, 11+2+1= 0等关系式。本题t =2， 和3是共轭元, m1(x)= m3(x) g(x)=LCMm1(x) m3(x) = m1(x) = x11

35、+ x9+ x7+x6 + x5 + x +1 degg(x) = n-k = 11, k = 23-11=12由g(x)可以产生一个(23,12)二元非本原BCH码，它就是著名的戈莱码（Golay），该码是完备码，复杂度适中而纠错能力强，实践中应用广泛。第45页，共63页，2022年，5月20日，1点17分，星期一表4-8 BCH码主要参数GF(q)本原BCH码GF(2)本原BCH码GF(2)非本原BCH码qm-12m-12m-1的因子 2mt mt mt qm/2 2m/2 n/2 2t+1 2t+1 2t+1码长n校验元(n-k)纠错能力t最小距离dmg(x)的根m0, m0+1 m0+

36、2t-1, 22t, 22t第46页，共63页，2022年，5月20日，1点17分，星期一三、BCH码译码第47页，共63页，2022年，5月20日，1点17分，星期一 1960年，彼得森（Peterson）首先从理论上解决了二进制BCH码的时域译码问题，稍后就有人把它推广到多进制BCH码。 1966年，伯利坎普（Berlekamp）提出了迭代译码算法，该算法后来被公认是经典的BCH实用译码算法。第48页，共63页，2022年，5月20日，1点17分，星期一3.1 从码多项式R(x)计算伴随式S(x) BCH码的生成多项式含有2t个连续幂次的根，又由根与校验矩阵的关系(式4-25)，BCH码的

37、校验矩阵可写成： 1 2 n-1 H = 1 2 (2)2 (2) n-1 (2tn)矩阵 (4-58) 1 2t (2t)2 (2t) n-1第49页，共63页，2022年，5月20日，1点17分，星期一伴随式S=(s1,s2sis2t )=(r0,r1, rn-1 )HT (4-59)其中， (4-60) 或写成： (4-61)第50页，共63页，2022年，5月20日，1点17分，星期一 若与i对应的最小多项式是i(x) , 接收码多项式R(x)除以i(x)的余式为pi(x)，则有： R(x) = qi(x)i(x) + pi(x) 以 x = i代入，i是i(x)的根，i(i)= 0。

38、由关系式(4-61)得：R(i) = qi(i)i(i) + pi(i) = pi(i) = Si (4-62)可见，Si等于R(x)除以i所对应的最小多项式i(x)后的余式。由于最小多项式i(x)的次数低于生成多项式g(x), 一般可减小计算量。 第51页，共63页，2022年，5月20日，1点17分，星期一例4.19 (15,5,7)二元BCH码的t=3，根所在域由本原多项式P(x)=x4+x+1生成。若收码R(x)已知，计算其伴随式Si。解：据例2.9表2.2，,2,4,8是共轭元，对应同一最小多项式1(x)= x4+x+1。3,6,9,12也是共轭元，对应同一最小多项式2(x)= x4

39、+ x3+ x2+ x +1，而共轭元5、10对应的最小多项式是3(x)= x2+ x+1。对于t=3的BCH码，应有2t=6个连续幂次的根，它们各自对应的最小多项式如表4-14。令R(x) 模1(x) = a3x3+ a2x2+ a1x+ a0 R(x) 模2(x) = b3 x3+ b2 x2+ b1 x+ b0 R(x) 模3(x) = c1 x+ c0由式(4-62)，伴随式S1= p1() = a33+ a22+ a1+ a0第52页，共63页，2022年，5月20日，1点17分，星期一 S2= p2(2) = a3(2) 3+ a2(2) 2+ a12+ a0 =a36+a24+a

40、12+a0=a3(3+2)+a2(+1)+a12+ a0 = a33+(a1+a3)2+ a2+(a0+a2)同理S3= p2(3) = b3 (3)3+ b2 (3)2+ b1(3)+ b0 = (b3+b2+b1)3+ b2 2+ b3+ b0 表4-14连续幂次根的最小多项式和伴随式根伴随式Si = pi(i) 234561(x)= x4+ x+11(x)= x4+ x+12(x)= x4+x3+x2+x+11(x)= x4+ x+13(x)= x2+ x+12(x)=x4+x3+x2+x+1S1= a33+ a22+ a1+ a0S2= a33+(a1+a3)2+ a2+(a0+a2)

41、S3=(b3+b2+b1)3+ b2 2+ b3+ b0S4=a33+(a2+a3)2+(a1+a3)+(a3+a2+a1+a0)S5= c12+ c1+ c0S6=(b3+b2+b1)3+(b2+b1)2+b2+(b2+b0)最小多项式i(x)第53页，共63页，2022年，5月20日，1点17分，星期一3.2 从伴随式S(x)到差错位置的迭代算法假设差错图样E(x)有个差错分别在j1、j2、j位上： (4-63)这里0 j1j2 j n-1, ji表示第i个差错的位置。由式(4-61)及(4-63)可导出下面一组方程： (4-64)第54页，共63页，2022年，5月20日，1点17分，星

42、期一为书写方便，令由于 指示了错误所在的位置，称之为错误位置数。将其代入式(4-64)，可得： (4-65)式(4-65)称为幂和对数函数，其中S1、S2、S2t是2t个已知数，可列出2t个方程，这些方程中包含了1、2、 共 个未知数。下一步任务是解这个非线性方程组，求出差错误位置数1、2、。第55页，共63页，2022年，5月20日，1点17分，星期一解方程组，一般用 个方程解 个未知数。然而这里差错数本身也是未知数，既不知道是多少，也不知道它比2t大还是小。任何一种求解该非线性方程的算法就是一种译码方法，以下介绍伯利坎普迭代算法。首先引入一个中间变量(x)，称为差错位置多项式： (x) = (1-1x) (1-2x) (1-x) = 0+1x+2x2+ x(4-66)显然，差错位置多项式(x)的个根是差错位置数的倒数1-1、2-1、-1。(x)各次项的系数0 1 2与1、2、一样是未知数。第56页，共63页，2022年，5月20日，1点17分，星期一 将式(4-66)的乘积展开并比较等式两边同次幂的系数，可得 ：0 = 11 = 1+2+2 =12+23+1 (4-67) =12 式中，i 称为初等对称函数。 第57页，共63页，2022年，5月20日，1点17分，星期一式(4-65)给出 Si和l 的关系，式(