信息论与编码第四讲PPT讲稿.ppt

信息论与编码第四讲第1页，共63页，编辑于2022年，星期四主要内容主要内容1、循环码代数基础、循环码代数基础2、BCH码码3、BCH译码译码第2页，共63页，编辑于2022年，星期四1.1 1.1 几个名词几个名词元素：近代代数的运算对象。元素：近代代数的运算对象。集合：一组元素或若干个元素的全体。集合：一组元素或若干个元素的全体。代数系统：包含集合和一种或几种代数运算（用符号代数系统：包含集合和一种或几种代数运算（用符号“*”表示）的系统。表示）的系统。一、循环码代数基础一、循环码代数基础第3页，共63页，编辑于2022年，星期四1.2群群u群，是包含集合群，是包含集合G和一种代数运算和一种代数运算*，且满足下列条件，且满足下列条件的代数系统：的代数系统：（a）运算封闭；）运算封闭；（b）有单位元；）有单位元；（c）有逆元；）有逆元；（d）满足结合律。）满足结合律。u加法群：满足加法和逆运算的群。加法群：满足加法和逆运算的群。u乘法群：满足乘法和逆运算的群。乘法群：满足乘法和逆运算的群。u交换群：满足交换律的群。交换群：满足交换律的群。u子群：一个非空集合子群：一个非空集合SG，S满足群满足群G的全部条件，则的全部条件，则S称为子群。称为子群。第4页，共63页，编辑于2022年，星期四无限群无限群：包含无数个元素的群。：包含无数个元素的群。有有限限群群：包包含含有有限限个个元元素素的的群群。有有限限群群元元素素的的个个数数称称为为该群的阶。该群的阶。循环群循环群：某某一一元元素素a（生生成成元元a）的的一一切切乘乘幂幂a0,a1,a2,的的全全体体组组成成一一个个群群，称称为为循循环环群群，写写作作G=a0,a1,a2,其其中中a0=e是是单单位元。位元。若序列若序列a0=e，a1,a2,中没有两个元素是相等的，称之中没有两个元素是相等的，称之为无限循环群。为无限循环群。第5页，共63页，编辑于2022年，星期四 若若上上述述序序列列中中有有两两个个相相等等的的元元素素a i=a j,(i j)，可可推推出出G 的的元元素素必必以以n为为周周期期重重复复，即即an=a0=e,这这样样的的循循环环群群称称为有限循环群。为有限循环群。循环群也叫幂群，具有以下性质：循环群也叫幂群，具有以下性质：（a）循环群是交换群；）循环群是交换群；（b）循环群的子群仍是循环群；）循环群的子群仍是循环群；（c）n阶循环群子群的阶数一定是阶循环群子群的阶数一定是n的因子。的因子。第6页，共63页，编辑于2022年，星期四例例例例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，）。）。第7页，共63页，编辑于2022年，星期四1.3环环环，包含集合环，包含集合R和两种代数运算，且满足下列条件的代数系和两种代数运算，且满足下列条件的代数系统：统：（a）按第一种运算（不妨称为加法）构成交换群；）按第一种运算（不妨称为加法）构成交换群；（b）第二种运算（不妨称为乘法）满足以下条件：）第二种运算（不妨称为乘法）满足以下条件：封闭性；封闭性；结合律；结合律；单位元；单位元；（c）与加法间满足分配律：）与加法间满足分配律：对于对于a,b,cR，a(b+c)=ab+ac,(a+b)c=ac+bc。交换环交换环：对于对于a,bR，ab=ba(交换律交换律)，则称，则称R为交换环。为交换环。第8页，共63页，编辑于2022年，星期四1.4域域u域，具有交换环的性质，且在乘法运算时具有逆元的代数系统。域，具有交换环的性质，且在乘法运算时具有逆元的代数系统。u域具有加和乘两种运算及它们的逆运算。域具有加和乘两种运算及它们的逆运算。u无限域无限域u 有理数、实数和复数都是无限域。有理数、实数和复数都是无限域。u有限域：包含有限个（有限域：包含有限个（q）元素的域，或称伽罗华域。）元素的域，或称伽罗华域。q称为称为域的阶。域的阶。u在信道编码中用到的是有限域，在信道编码中用到的是有限域，GF(q)。u(0,1)二元域二元域GF(2)，或称基本域。，或称基本域。u由由GF(2)GF(2m)，称扩域。，称扩域。第9页，共63页，编辑于2022年，星期四可以证明：可以证明：伽逻华域伽逻华域GF(q)的的(q-1)个非零元素在模个非零元素在模q乘运算下构成乘运算下构成一个循环群（幂群），即一个循环群（幂群），即所有非零元素可由一个元素所有非零元素可由一个元素（称作本原元）的各次幂（称作本原元）的各次幂 0、1、2、q-2生成。生成。第10页，共63页，编辑于2022年，星期四1.5既约多项式既约多项式 对于某数域上的多项式对于某数域上的多项式PI（x），若除了常数），若除了常数C以及以及CPI（x）外不能被该数域上的任何其它多项式整除，则）外不能被该数域上的任何其它多项式整除，则称为是该数域上的称为是该数域上的既约多项式既约多项式。如：如：x x4 4+x+1+x+1 第11页，共63页，编辑于2022年，星期四1.6本原多项式本原多项式对对于于有有限限域域GF(q)上上的的m次次既既约约多多项项式式P(x)，若若能能被被它它整整除除的的最最简简单单多多项项式式(xn-1)的的次次数数n qm1,则则称称该该多多项项式式为本原多项式。为本原多项式。本原多项式一定既约；既约多项式未必本原。本原多项式一定既约；既约多项式未必本原。如：如：m本原多项式本原多项式31+x+x341+x+x451+x2+x561+x+x6第12页，共63页，编辑于2022年，星期四比如：比如：在在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年，星期四本原元本原元对于对于m次本原多项式次本原多项式p(x)，如果，如果p(a)=0,那么那么a是是GF(2m)的一个本原元。的一个本原元。利用本原多项式可求扩域利用本原多项式可求扩域GF(2m)的全部元素为：的全部元素为：第14页，共63页，编辑于2022年，星期四举例p(x)=x2+x+1，求，求GF(22)的全部元素及加法乘法表。的全部元素及加法乘法表。分析：分析：令令p(a)=0，得，得a2+a+1=0，a2a+1。那么全部元素为：那么全部元素为：幂表示矢量表示多项式表示0a0a1a2=a+10001101101xx+1第15页，共63页，编辑于2022年，星期四1.6 GF(q)的加、乘、减和除的加、乘、减和除在在GF(q)中，对元中，对元0,1,2,q-1使用使用modq的计算方法：进的计算方法：进行加法和乘法。行加法和乘法。如如GF(3)的加法和乘法如下表：的加法和乘法如下表：+012012012120201.012012000012021第16页，共63页，编辑于2022年，星期四减法：减法：a-b=a-b+qmodq如如:1-2=1-2+3=2mod3除法：除法：b/a=b.a-1modq如：因为如：因为22=1mod3，2的乘法逆元的乘法逆元2-1为为2，所以：，所以：2/2=22-1=22=1第17页，共63页，编辑于2022年，星期四二、二、BCH码码第18页，共63页，编辑于2022年，星期四2.1GF(2m)域上构造循环码的方法域上构造循环码的方法第19页，共63页，编辑于2022年，星期四 xn-1因式分解因式分解(4-17)这里，既约因式这里，既约因式m mj j(x x)（j=0,j=0,l l-1-1）分成两部分，它们的乘积分别是）分成两部分，它们的乘积分别是g g(x x)和和 h h(x x)。循环码并不强调。循环码并不强调g g(x x)的既约性，它可以是既约的，也可以的既约性，它可以是既约的，也可以是非既约的。若某既约因式是非既约的。若某既约因式m mj j(x x)是非既约是非既约g g(x x)的一个因式，必有：的一个因式，必有：m mj j(x x)|)|g g(x x)|()|(x xn n-1)-1)(4-18)(4-18)换一个角度，如果将换一个角度，如果将(x xn n-1)-1)看成是一个看成是一个n n次多项式，那么它在复数次多项式，那么它在复数域应该有域应该有n n个根，记作个根，记作a ai i，i i=0,=0,n n-1-1，此时，此时(x xn n-1)-1)可表示成可表示成x xn n-1=(-1=(x x-a a0 0)()(x x-a a1 1)()(x x-a an n-1-1)(4-19)(4-19)第20页，共63页，编辑于2022年，星期四例例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、。第21页，共63页，编辑于2022年，星期四根根据据定定理理4.1：只只要要找找到到与与循循环环码码对对应应的的一一个个n 阶阶元元素素，就可以将就可以将(xn-1)在在GF(2m)上完全分解为：上完全分解为：xn-1=证：若证：若a是循环群是循环群n阶元素，必有阶元素，必有an=1即即(an-1)=0将将ai,i=0n-1代入代入(xn-1)验根，验根，得得(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年，星期四二二元元扩扩域域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第23页，共63页，编辑于2022年，星期四若若(xn-1)的某一个根的某一个根ai,i 0,1n-1又是某个既约因式又是某个既约因式mj(x),j 0,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)。第24页，共63页，编辑于2022年，星期四研究表明：研究表明：有重根的有重根的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年，星期四用用(xn-1)在在GF(2m)域上的根来构造循环码的方法：域上的根来构造循环码的方法：在在(xn-1)的的n个根中选取若干个个根中选取若干个r1、r2rj，其中其中rj ai,i=0,1n-1。找出各根对应的既约多项式找出各根对应的既约多项式r1m1(x)、r2m2(x)rjmj(x)。求出这些既约多项式的最小公倍式：求出这些既约多项式的最小公倍式：g(x)=LCMm1(x),m2(x)mj(x)LCM(LeastCommonMultiple)-最小公倍式最小公倍式若选取的根是连续幂次的根，则所得的若选取的根是连续幂次的根，则所得的g(x)可以产生一个可以产生一个BCH码。码。第26页，共63页，编辑于2022年，星期四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)。第27页，共63页，编辑于2022年，星期四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+c1 2+c2(2)2+cn-1(2)n-1=0以以x=2t代入，得代入，得c0+c1 2t+c2(2t)2+cn-1(2t)n-1=0第28页，共63页，编辑于2022年，星期四将上面将上面2t个方程写作矩阵形式，得：个方程写作矩阵形式，得：CAT=0(4-24)其中：其中：A=可见，可见，A是范得蒙矩阵。数学证明：范得蒙矩阵一定是满秩矩是范得蒙矩阵。数学证明：范得蒙矩阵一定是满秩矩阵，即阵，即矩阵矩阵A的秩是的秩是2t或者说有或者说有2t列线性无关。码的最小距列线性无关。码的最小距离离dmin等于校验矩阵中线性无关的列数加等于校验矩阵中线性无关的列数加1，因此，因此BCH码最小码最小距离为：距离为：dmin=2t+1(4-26)12n-112(2)2(2)n-112t(2t)2(2t)n-112n-112(2)2(n-1)2 12t(2)2t(n-1)2t第29页，共63页，编辑于2022年，星期四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)。m 8时连续幂次根时连续幂次根 i所对应的最小多项式见所对应的最小多项式见表表4-6。计算这些最小多项式的最小公倍式，得到生成多项式计算这些最小多项式的最小公倍式，得到生成多项式g(x)g(x)=LCMm1(x)m2(x)m2t(x)(4-27)由关系式由关系式C(x)=m(x)g(x)求求BCH码字。码字。第30页，共63页，编辑于2022年，星期四对于二元对于二元BCH码，无需列出全部码，无需列出全部2t个连续幂次的根，而只个连续幂次的根，而只要列出其中一半（奇数幂次的根）就可以了。这是因为要列出其中一半（奇数幂次的根）就可以了。这是因为任何一个偶数任何一个偶数ie 可写成一个小于它的奇数可写成一个小于它的奇数io 与与2的的l次幂的次幂的乘积：乘积：ie=io 2l,ioie(4-28)比如比如2=121，4=122，10=521，12=322因此任何一个偶次幂根都是奇次幂根的共轭元因此任何一个偶次幂根都是奇次幂根的共轭元它们对应同一个最小多项式。它们对应同一个最小多项式。第31页，共63页，编辑于2022年，星期四 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)中连续幂次根所对应的最小多项式中连续幂次根所对应的最小多项式第32页，共63页，编辑于2022年，星期四比如比如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)m7(x)=LCMm1(x)m3(x)m5(x)m7(x)因此因此对于二进制码，构造本原对于二进制码，构造本原BCH码的步骤改为码的步骤改为:分别计算分别计算t个连续奇次幂之根个连续奇次幂之根、3 2t-1所对应的最所对应的最小多项式小多项式m1(x)、m3(x)m2t-1(x)。第33页，共63页，编辑于2022年，星期四当码长当码长n确定后，确定后，BCH码纠错能力码纠错能力t的选择并不是任意的，的选择并不是任意的，而要受到一定限制。而要受到一定限制。对于对于q元元BCH码，码，2t个根对应个根对应2t个最小多项式，每个最小个最小多项式，每个最小多项式的次数不会超过多项式的次数不会超过m，于是，于是2t个最小多项式的最小公倍个最小多项式的最小公倍式式g(x)的次数：的次数：degg(x)=(n-k)2t(4-29)对于二元对于二元BCH码，码，t个根对应个根对应t个最小多项式，因此个最小多项式，因此degg(x)=(n-k)tm(4-30)(xn-1)一共有一共有n个根，连续幂次根不能超过根的总数个根，连续幂次根不能超过根的总数2t n (4-31)式式(4-29)(4-30)给出了给出了t的下限，式的下限，式(4-31)给出了给出了t的上限。的上限。第34页，共63页，编辑于2022年，星期四例例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 5 7 9 11 13所对应的最小多项式。本例可参考例所对应的最小多项式。本例可参考例2.2.3的的表表2-3，我们看到，我们看到 3、9是共轭元，是共轭元，7、11和和 13是共轭元是共轭元（利用教材（利用教材p124“共轭根系共轭根系”定义分析）。定义分析）。第35页，共63页，编辑于2022年，星期四根和根所对应的最小多项式（例根和根所对应的最小多项式（例2.10）如下：）如下：根根 m1(x)=p(x)=x4+x+1根根 3m3(x)=(x+a3)(x+a(x+a6 6)(x+a)(x+a9 9)(x+a(x+a1212)=x4+x3+x2+x+1根根 5m5(x)=(x+a5)(x+a10)=x2+x+1根根 7m7(x)=x4+x3+1根根 9同同 3，根根 11、13同同 7。这里，这里，m(x)的全部根为下列系列：的全部根为下列系列：并把并把w序列换成序列换成a的序列。的序列。第36页，共63页，编辑于2022年，星期四 第三步：求最小公倍式得到生成多项式第三步：求最小公倍式得到生成多项式g g(x x)。若若t t=1=1，g g1(1(x x)=LCM)=LCMm m1(1(x x)=)=x x4+4+x x+1+1g g1(1(x x)是是4 4次多项式，即次多项式，即n-kn-k=4=4，k k=15-4=11,=15-4=11,这就是这就是(15,11)BCH(15,11)BCH码，也是汉明码。码，也是汉明码。若若t t=2=2，g g2(2(x x)=LCM)=LCMm m1(1(x x),),m m3(3(x x)=)=m m1(1(x x)m m3(3(x x)=)=x x8+8+x x7+7+x x6+6+x x4+14+1，degdegg g2(2(x x)=)=n-k n-k=8=8，k k=15-8=7=15-8=7，这是，这是(15,7)BCH(15,7)BCH码。码。第37页，共63页，编辑于2022年，星期四若若t=3，g3(x)=LCMm1(x),m3(x),m5(x)=m1(x)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+1degg4(x)=n-k=14，k=15-14=1，这是，这是(15,1)BCH码。码。第38页，共63页，编辑于2022年，星期四若若t=5，g5(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的所有各次幂，意味着编码时将一位信息的所有各次幂，意味着编码时将一位信息“0”或或“1”重复发送重复发送15次。因此，实际上只有次。因此，实际上只有t=1,2,3的的(15,11)、(15,7)、(15,5)BCH码才有实用价值。码才有实用价值。第39页，共63页，编辑于2022年，星期四 非本原非本原BCH码与本原码与本原BCH码的主要区别在于所用的根码的主要区别在于所用的根是否本原元是否本原元。当码长当码长n和纠错能力和纠错能力t给定后，本原给定后，本原BCH码的根码的根 一定一定是是n=2m-1阶阶,n已知就是已知就是m已知，因而已知，因而GF(qm)好找。好找。非本原非本原BCH码的根码的根 是是n阶元素阶元素,满足满足n|(qm-1)，n已知不等于已知不等于m已知，需要多一道计算。已知，需要多一道计算。第40页，共63页，编辑于2022年，星期四已知已知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)=LCMm1(x)m3(x)m2t-1(x)。第41页，共63页，编辑于2022年，星期四表表4-72m-1的素因子分解（的素因子分解（m34）m素因子分解素因子分解m素因子分解素因子分解m素因子分解素因子分解12345678910111373 5313 3 71273 5 177 733 11 3123 8912131415161718192021223 3 5 7 1381913 43 1277 31 1513 5 17 2571310713 3 3 7 19 735242873 5 5 1l 31 417 7 127 3373 23 89 683232425262728293031323347 1784813 3 5 7 13 17 24131 601 18013 2731 81917 73 2626573 5 29 43 113 127233 1103 20893 3 7 11 31 151 33121474836473 5 17 257 655377 23 89 599479第42页，共63页，编辑于2022年，星期四例例4.9试设计一个码长试设计一个码长n=23，纠两个随机差错，纠两个随机差错(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本身都是域元素，本身都是域元素，只是将域元素只是将域元素 89定义为定义为域元素域元素 而已。由于而已。由于(89)23=()23=1，因此可断言，因此可断言 是一个是一个23阶的非阶的非本原元。本原元。第43页，共63页，编辑于2022年，星期四求求 连续奇幂次的根所对应的最小多项式。连续奇幂次的根所对应的最小多项式。首先找出首先找出 的所有共轭元，然后再来计算最小多项式。的所有共轭元，然后再来计算最小多项式。的共轭元有：的共轭元有：,2,4,8,16,32=23 9=9,18,36=23 13=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个。个。第44页，共63页，编辑于2022年，星期四第一组第一组 所对应的最小多项式为所对应的最小多项式为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+x9+x7+x6+x5+x+1degg(x)=n-k=11,k=23-11=12由由g(x)可可以以产产生生一一个个(23,12)二二元元非非本本原原BCH码码，它它就就是是著著名名的的戈戈莱莱码码（Golay），该该码码是是完完备备码码，复复杂杂度度适适中中而而纠纠错错能能力力强强，实实践践中中应应用广泛。用广泛。第45页，共63页，编辑于2022年，星期四表表4-8BCH码主要参数码主要参数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+2t-1,2 2t,2 2t第46页，共63页，编辑于2022年，星期四三、三、BCH码译码码译码第47页，共63页，编辑于2022年，星期四1960年，彼得森（年，彼得森（Peterson）首先从理论上解决了）首先从理论上解决了二进制二进制BCH码的时域译码问题，稍后就有人把它推广码的时域译码问题，稍后就有人把它推广到多进制到多进制BCH码。码。1966年，伯利坎普（年，伯利坎普（Berlekamp）提出了迭代译码算）提出了迭代译码算法，该算法后来被公认是经典的法，该算法后来被公认是经典的BCH实用译码算法。实用译码算法。第48页，共63页，编辑于2022年，星期四3.1从码多项式从码多项式R(x)计算伴随式计算伴随式S(x)BCH码码的的生生成成多多项项式式含含有有2t个个连连续续幂幂次次的的根根，又又由由根根与与校校验验矩阵的关系矩阵的关系(式式4-25)，BCH码的校验矩阵可写成：码的校验矩阵可写成：1 2 n-1H=1 2(2)2(2)n-1 (2tn)矩阵矩阵(4-58)1 2t(2t)2(2t)n-1第49页，共63页，编辑于2022年，星期四伴随式伴随式S=(s1,s2sis2t)=(r0,r1,rn-1)HT(4-59)其中，其中，(4-60)或写成：或写成：(4-61)第50页，共63页，编辑于2022年，星期四若若与与 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),一一般般可可减减小计算量。小计算量。第51页，共63页，编辑于2022年，星期四例例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+a0 R(x)模模 2(x)=b3x3+b2x2+b1x+b0 R(x)模模 3(x)=c1x+c0由式由式(4-62)，伴随式，伴随式S1=p1()=a3 3+a2 2+a1+a0第52页，共63页，编辑于2022年，星期四 S2=p2(2)=a3(2)3+a2(2)2+a1 2+a0 =a3 6+a2 4+a1 2+a0=a3(3+2)+a2(+1)+a1 2+a0=a3 3+(a1+a3)2+a2+(a0+a2)同理同理S3=p2(3)=b3(3)3+b2(3)2+b1(3)+b0=(b3+b2+b1)3+