信息论与编码第四讲

信息论与编码第四讲第一页，共六十三页，2022年，8月28日主要内容1、循环码代数基础2、BCH码3、BCH译码第二页，共六十三页，2022年，8月28日1.1几个名词元素：近代代数的运算对象。集合：一组元素或若干个元素的全体。代数系统：包含集合和一种或几种代数运算（用符号“*”表示）的系统。一、循环码代数基础第三页，共六十三页，2022年，8月28日1.2群群，是包含集合G和一种代数运算‘*’，且满足下列条件的代数系统：（a）运算封闭；（b）有单位元；（c）有逆元；（d）满足结合律。加法群：满足加法和逆运算的群。乘法群：满足乘法和逆运算的群。交换群：满足交换律的群。子群：一个非空集合SG，S满足群G的全部条件，则S称为子群。第四页，共六十三页，2022年，8月28日

无限群：包含无数个元素的群。

有限群：包含有限个元素的群。有限群元素的个数称为该群的阶。

循环群：某一元素a（生成元a）的一切乘幂a0,a1,a2,…的全体组成一个群，称为循环群，写作G={a0,a1,a2,…},其中a0=e是单位元。若序列a0=e，a1,a2,…中没有两个元素是相等的，称之为无限循环群。第五页，共六十三页，2022年，8月28日

若上述序列中有两个相等的元素ai=aj,(ij)，可推出G的元素必以n为周期重复，即an=a0=e,这样的循环群称为有限循环群。循环群也叫幂群，具有以下性质：（a）循环群是交换群；（b）循环群的子群仍是循环群；（c）n阶循环群子群的阶数一定是n的因子。第六页，共六十三页，2022年，8月28日例例1：令R、I、E分别是有理数、整数、偶数集合，则(E,+)是(I,+)的子群，则(I,+)是(R,+)的子群，单位元均是0。奇数集合O在加法运算下构不成群，因不满足封闭性条件。例3集合G={0,1,2…m-1}在模m加（用符号表示）运算下构成一个群（G，）。该加群是m阶有限群，单位元是0。元素0的逆元是0，1的逆元是m-1,2的逆元是m-2,…。例4：集合G={1,2…q-1}在模q乘（q是素数）运算下构成一个乘群（G，）。第七页，共六十三页，2022年，8月28日1.3环

环，包含集合R和两种代数运算，且满足下列条件的代数系统：（a）按第一种运算（不妨称为加法）构成交换群；（b）第二种运算（不妨称为乘法）满足以下条件：封闭性；结合律；单位元；（c）与加法间满足分配律：对于a,b,cR，a(b+c)=ab+ac,(a+b)c=ac+bc。交换环：对于a,bR，ab=ba(交换律)，则称R为交换环。第八页，共六十三页，2022年，8月28日1.4域域，具有交换环的性质，且在乘法运算时具有逆元的代数系统。域具有加和乘两种运算及它们的逆运算。无限域有理数、实数和复数都是无限域。有限域：包含有限个（q）元素的域，或称伽罗华域。q称为域的阶。在信道编码中用到的是有限域，GF(q)。(0,1)二元域GF(2)，或称基本域。由GF(2)GF(2m)，称扩域。第九页，共六十三页，2022年，8月28日

可以证明：伽逻华域GF(q)的(q-1)个非零元素在模q乘运算下构成一个循环群（幂群），即所有非零元素可由一个元素（称作本原元）的各次幂0、1、2、…q-2生成。

第十页，共六十三页，2022年，8月28日1.5既约多项式

对于某数域上的多项式PI（x），若除了常数C以及CPI（x）外不能被该数域上的任何其它多项式整除，则称为是该数域上的既约多项式。如：x4+x+1第十一页，共六十三页，2022年，8月28日1.6本原多项式

对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简单多项式(xn-1)的次数nqm–1,则称该多项式为本原多项式。

本原多项式一定既约；既约多项式未必本原。如：m本原多项式

31+x+x3

41+x+x4

51+x2+x5

61+x+x6

第十二页，共六十三页，2022年，8月28日比如：在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是既约的，但不是本原的。第十三页，共六十三页，2022年，8月28日本原元

对于m次本原多项式p(x)，如果p(a)=0,那么a是GF(2m)的一个本原元。利用本原多项式可求扩域GF(2m)的全部元素为：第十四页，共六十三页，2022年，8月28日举例p(x)=x2+x+1，求GF(22)的全部元素及加法乘法表。分析：令p(a)=0，得a2+a+1=0，a2＝a+1。那么全部元素为：幂表示矢量表示多项式表示0a0a1a2=a+10001101101xx+1第十五页，共六十三页，2022年，8月28日1.6GF(q)的加、乘、减和除在GF(q)中，对元0,1,2,…,q-1使用modq的计算方法：进行加法和乘法。如GF(3)的加法和乘法如下表：+012012012120201.012012000012021第十六页，共六十三页，2022年，8月28日减法：a-b=a-b+qmodq如:1-2=1-2+3=2mod3除法：b/a=b.a-1modq如：因为2×2=1mod3，2的乘法逆元2-1为2，所以：2/2=2×2-1=2×2=1第十七页，共六十三页，2022年，8月28日二、BCH码第十八页，共六十三页，2022年，8月28日2.1GF(2m)域上构造循环码的方法第十九页，共六十三页，2022年，8月28日xn-1因式分解

(4-17)这里，既约因式mj(x)（j=0,…,l-1）分成两部分，它们的乘积分别是g(x)和

h(x)。循环码并不强调g(x)的既约性，它可以是既约的，也可以是非既约的。若某既约因式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)第二十页，共六十三页，2022年，8月28日例4-7（x4-1）在不同域上的因式分解在实数域的分解：x4-1=

(x2+1)(x+1)(x-1)在复数域的分解：x4-1=

(x+i)(x-i)(x+1)(x-1)在二元域的分解：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、…、}。第二十一页，共六十三页，2022年，8月28日根据定理4.1：只要找到与循环码对应的一个n阶元素，就可以将(xn-1)在GF(2m)上完全分解为：

xn-1=证：若

a是循环群n

阶元素，必有an=1即(an-1)=0

将ai,i=0…n-1代入(xn-1)验根，得(ai)n-1=(an)i-1=(1)i-1=0∴ai,i=0…n-1是(xn-1)的n个根，以根为一次项可将(xn-1)完全分解为：

xn-1=(x-a0)(x-a1)…(x-an-1) 第二十二页，共六十三页，2022年，8月28日

二元扩域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既是扩域又是二元域元素

或改变顺序为

==xn-1

第二十三页，共六十三页，2022年，8月28日若(xn-1)的某一个根ai,i{0,1…n-1}又是某个既约因式mj(x),j{0,1…l-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)。第二十四页，共六十三页，2022年，8月28日研究表明：有重根的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)肯定也无重根。第二十五页，共六十三页，2022年，8月28日

用(xn-1)在GF(2m)域上的根来构造循环码的方法：①在(xn-1)的n个根中选取若干个r1、r2…rj，

其中rj{ai},i=0,1…n-1。②找出各根对应的既约多项式r1→m1(x)、

r2→m2(x)…rj→mj(x)。③求出这些既约多项式的最小公倍式：

g(x)=LCM[m1(x),m2(x)…mj(x)]LCM(LeastCommonMultiple)-最小公倍式若选取的根是连续幂次的根，则所得的g(x)可以产生一个BCH码。第二十六页，共六十三页，2022年，8月28日2.2BCH码的定义

GF(q)域循环码生成多项式g(x)，若含有2t个连续幂次的根 ，则由g(x)生成的(n,k)循环码称为q进制BCH码。连续幂次起始值m0的选取并无多大实际意义，通常固定取m0=1。若q=2，称为二进制（二元）BCH码。若根a是本原元，称该码为本原BCH码，其码长n=qm-1。若根a是非本原元，称该码为非本原BCH码，其码长n是qm-1的因子，满足n|(qm-1)。

第二十七页，共六十三页，2022年，8月28日BCH码限定理：若BCH码生成多项式g(x)中含有2t个连续幂次的根，则该码的最小距离dmim2t+1证明：∵BCH码多项式C(x)=m(x)g(x)∴g(x)的2t个连续幂次根、…、2t也是C(x)的根设C(x)=c0+c1x+c2x2+…+cn-1xn-1以根x=代入，得c0+c1+c2

2+…+cn-1

n-1=0以x=2代入，得c0+c12+c2(2)2+…+cn-1(2)n-1=0

┇以x=2t代入，得c0+c12t+c2(2t)2+…+cn-1(2t)n-1=0第二十八页，共六十三页，2022年，8月28日将上面2t个方程写作矩阵形式，得：CAT=0 (4-24)其中：

A== 可见，A是范得蒙矩阵。数学证明：范得蒙矩阵一定是满秩矩阵，即矩阵A的秩是2t或者说有2t列线性无关。码的最小距离dmin等于校验矩阵中线性无关的列数加1，因此BCH码最小距离为：

dmin=2t+1

(4-26)

1

2…n-1

12(2)2…(2)n-1

┇12t

(2t)2…(2t)n-11

2…n-1

12(2)2…(n-1)2

┇12t

(2)2t…(n-1)2t第二十九页，共六十三页，2022年，8月28日 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)=LCM[m1(x)m2(x)…m2t(x)] (4-27)④由关系式C(x)=m(x)g(x)求BCH码字。第三十页，共六十三页，2022年，8月28日对于二元BCH码，无需列出全部2t个连续幂次的根，而只要列出其中一半（奇数幂次的根）就可以了。这是因为任何一个偶数ie可写成一个小于它的奇数io与2的l次幂的乘积：

ie

=io2l,io<ie (4-28)比如2=1×21，4=1×22，10=5×21，12=3×22…

因此任何一个偶次幂根都是奇次幂根的共轭元

它们对应同一个最小多项式。第三十一页，共六十三页，2022年，8月28日

i最小多项式i最小多项式i最小多项式i最小多项式m=21(0,1,2)

m=31(0,1,3)3(0,2,3)

m=41(0,1,4)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)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(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)中连续幂次根所对应的最小多项式

第三十二页，共六十三页，2022年，8月28日比如t=4时8个连续幂次根

2345678中，

248是共轭元，36是共轭元，于是g(x)=LCM[m1(x)m2(x)m3(x)m4(x)m5(x)m6(x)m7(x)m8(x)]=LCM{[m1(x)m2(x)m4(x)m8(x)][m3(x)m6(x)]

m5(x)m7(x)}=LCM[m1(x)m3(x)m5(x)m7(x)]因此对于二进制码，构造本原BCH码的步骤改为:②分别计算t个连续奇次幂之根、3…2t-1所对应的最小多项式m1(x)、m3(x)…m2t-1(x)。第三十三页，共六十三页，2022年，8月28日当码长n确定后，BCH码纠错能力t的选择并不是任意的，而要受到一定限制。对于q元BCH码，2t个根对应2t个最小多项式，每个最小多项式的次数不会超过m，于是2t个最小多项式的最小公倍式g(x)的次数：

deg[g(x)]=(n-k)≤2t(4-29)对于二元BCH码，t个根对应t个最小多项式，因此

deg[g(x)]=(n-k)≤tm (4-30)(xn-1)一共有n个根，连续幂次根不能超过根的总数

2t

n (4-31)式(4-29)(4-30)给出了t的下限，式(4-31)给出了t的上限。第三十四页，共六十三页，2022年，8月28日例4.8设计一个码长n=15的二元本原BCH码，在不同纠错能力下的生成多项式应是怎样的？解：∵15=24-1 ∴本题m=4①第一步：查表，找到一个m=4的本原多项式：P(x)=x4+x+1。令是该本原多项式P(x)的根，满足4+

+1=0。由式(4-31)，本码纠错能力t7。②第二步：对于二元码，分别计算t=7个连续奇次幂之根

3

57

911

13所对应的最小多项式。本例可参考例的表2-3，我们看到3、9是共轭元，7、11和13是共轭元（利用教材p124“共轭根系”定义分析）。第三十五页，共六十三页，2022年，8月28日根和根所对应的最小多项式（例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的序列。第三十六页，共六十三页，2022年，8月28日③第三步：求最小公倍式得到生成多项式g(x)。●若t=1，g1(x)=LCM[m1(x)]=x4+x+1g1(x)是4次多项式，即n-k=4，∴k=15-4=11,

这就是(15,11)BCH码，也是汉明码。●若t=2，g2(x)=LCM[m1(x),m3(x)]=m1(x)m3(x)=x8+x7+x6+x4+1，deg[g2(x)]=n-k=8，∴k=15-8=7，这是(15,7)BCH码。第三十七页，共六十三页，2022年，8月28日●若t=3，

g3(x)=LCM[m1(x),m3(x),m5(x)]=m1(x)m3(x)m5(x)=x10+x8+x5+x4+x2+x+1，

deg[g3(x)]=n-k=10，∴k=15-10=5，这是(15,5)BCH码。●若t=4，

g4(x)=LCM[m1(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+1deg[g4(x)]=n-k=14，∴k=15-14=1，这是(15,1)BCH码。第三十八页，共六十三页，2022年，8月28日●若t=5，g5(x)=LCM[m1(x),m3(x),m5(x),m7(x),m9(x)]=m1(x)m3(x)m5(x)m7(x)=g4(x)●若t=6，g6(x)=LCM[m1(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)=LCM[m1(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的所有各次幂，意味着编码时将一位信息“0”或“1”重复发送15次。因此，实际上只有t=1,2,3的(15,11)、(15,7)、(15,5)BCH码才有实用价值。第三十九页，共六十三页，2022年，8月28日

非本原BCH码与本原BCH码的主要区别在于所用的根是否本原元。当码长n和纠错能力t给定后，本原BCH码的根一定是n=2m-1阶,n已知就是m已知，因而GF(qm)好找。非本原BCH码的根是n阶元素,满足n|(qm-1)，

n已知不等于m已知，需要多一道计算。

第四十页，共六十三页，2022年，8月28日已知n和t后二元非本原BCH码的设计步骤：①求出满足

n|(2m-1)关系的m的最小值。n是(2m-1)的因子，可以借助2m-1的素因子分解表（如表4-7）来寻找m值。②查表4-5，找出一个m阶的本原多项式P(x)，产生一个二元扩域GF(2m)。③以P(x)的根为中介找出一个n阶的非本原元。④计算与、3、5…2t-1对应的最小多项式m1(x)、m3(x)…m2t-1(x)。⑤求生成多项式g(x)=LCM[m1(x)m3(x)…m2t-1(x)]。第四十一页，共六十三页，2022年，8月28日表4-72m-1的素因子分解（m<34）

m素因子分解m素因子分解m素因子分解123456789101113735313371273517773311312389121314151617181920212233571381913431277311513517257131071333719735242873551l3141771273373238968323242526272829303132334717848133571317241316011801327318191773262657352943113127233110320893371131151331214748364735172576553772389599479第四十二页，共六十三页，2022年，8月28日例4.9试设计一个码长n=23，纠两个随机差错(t=2)的二元BCH码。

解：①由于码长n2m-1比如15、31、…255…等值，可知要求设计的是二元非本原BCH码。检查能被n=23整除的2m-1(表4-7)，m的最小值是11(211-1=2047=89×23,能够整除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=89×23=(89)23=()23=1,式中=89。事实上，0,1,2,3,…2047本身都是域元素，只是将域元素89定义为域元素而已。由于(89)23=()23=1，因此可断言是一个23阶的非本原元。第四十三页，共六十三页，2022年，8月28日④求连续奇幂次的根所对应的最小多项式。首先找出的所有共轭元，然后再来计算最小多项式。的共轭元有：,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)至少是11次多项式，有11个根。同理可得另一组共轭元5,10,20,17,11,22,21,19,15,7,14，也是11个。第四十四页，共六十三页，2022年，8月28日第一组所对应的最小多项式为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)=LCM[m1(x)m3(x)]

=m1(x)=x11+x9+x7+x6+x5+x+1∵deg[g(x)]=n-k=11,k=23-11=12∴由g(x)可以产生一个(23,12)二元非本原BCH码，它就是著名的戈莱码（Golay），该码是完备码，复杂度适中而纠错能力强，实践中应用广泛。第四十五页，共六十三页，2022年，8月28日表4-8BCH码主要参数GF(q)本原BCH码GF(2)本原BCH码GF(2)非本原BCH码qm-12m-12m-1的因子2mt

mt

mt<qm/2<

2m/2<n/22t+12t+12t+1

码长n校验元(n-k)纠错能力t最小距离dmg(x)的根m0,m0+1…m0+2t-1,2…2t,2…2t第四十六页，共六十三页，2022年，8月28日三、BCH码译码第四十七页，共六十三页，2022年，8月28日1960年，彼得森（Peterson）首先从理论上解决了二进制BCH码的时域译码问题，稍后就有人把它推广到多进制BCH码。

1966年，伯利坎普（Berlekamp）提出了迭代译码算法，该算法后来被公认是经典的BCH实用译码算法。第四十八页，共六十三页，2022年，8月28日3.1从码多项式R(x)计算伴随式S(x)

BCH码的生成多项式含有2t个连续幂次的根，又由根与校验矩阵的关系(式4-25)，BCH码的校验矩阵可写成：

1

2…n-1

H= 12(2)2…(2)n-1

(2t×n)矩阵 (4-58) ┇ 12t

(2t)2…(2t)n-1第四十九页，共六十三页，2022年，8月28日伴随式S=(s1,s2…si…s2t)=(r0,r1,…,rn-1

)HT(4-59)其中，

(4-60)或写成：

(4-61)第五十页，共六十三页，2022年，8月28日若与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。由关系式(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),一般可减小计算量。

第五十一页，共六十三页，2022年，8月28日例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+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+a0R(x)[模2(x)]=b3x3+b2x2+b1x+b0R(x)[模3(x)]=c1x+c0由式(4-62)，伴随式

S1=p1()=a33+a22+a1+a0第五十二页，共六十三页，2022年，8月28日

S2=p2(2)=a3(2)3+a2(2)2+a12+a0

=a36+a24+a12+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+b22+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)S3=(b3+b2+b1)3+b22+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)第五十三页，共六十三页，2022年，8月28日3.2从伴随式S(x)到差错位置的迭代算法假设差错图样E(x)有个差错分别在j1、j2、…、j位上：

(4-63)这里0

j1<j2…<j

n-1,ji表示第i个差错的位置。由式(4-61)及(4-63)可导出下面一组方程：

(4-64)┇第五十四页，共六十三页，2022年，8月28日为书写方便，令由于指示了错误所在的位置，称之为错误位置数。将其代入式(4-64)，可得：

(4-65)式(4-65)称为幂和对数函数，其中S1、S2、…S2t是2t个已知数，可列出2t个方程，这些方程中包含了1、2、…、

共

个未知数。下一步任务是解这个非线性方程组，求出差错误位置数1、2、…、。第五十五页，共六十三页，2022年，8月28日解方程组，一般用

个方程解

个未知数。然而这里差错数本身也是未知数，既不知道是多少，也不知道它比2t大还是小。任何一种求解该非线性方程的算法就是一种译码方法，以下介绍伯利坎普迭代算法。首先引入一个中间变量(x)，称为差错位置多项式：

(x)=(1-1x)(1-2x)…(1-x)=0+1x+2x2+…+

x

(4-66)显然，差错位置多项式(x)的个根是差错位置数的倒数1-1、2-1、…、-1。(x)各次项的系数0

12…与1、2、…、一样是未知数。第五十六页，共六十三页，2022年，8月28日将式(4-66)的乘积展开并比较等式两边同次幂的系数，可得：

0=1

1=1+2+…+

2=12+23+…+－1

(4-67)

┇

=12…

式中，i称为初等对称函数。

第五十七页，共六十三页，2022年，8月28日式(4-65)给出Si和l

的关系，式(4-67)给出l和l的关系。结合两式，可得到Si和l的关系如下: S1+1=0 S2+1S1

+22=0 S3+1S2

+2S1

+33=0 (4-68)