信息論與編碼第四講

信息論與編碼第四講第1頁，共63頁，2023年，2月20日，星期日主要內(nèi)容1、循環(huán)碼代數(shù)基礎(chǔ)2、BCH碼3、BCH譯碼第2頁，共63頁，2023年，2月20日，星期日1.1幾個名詞元素：近代代數(shù)的運(yùn)算對象。集合：一組元素或若干個元素的全體。代數(shù)系統(tǒng)：包含集合和一種或幾種代數(shù)運(yùn)算（用符號“*”表示）的系統(tǒng)。一、循環(huán)碼代數(shù)基礎(chǔ)第3頁，共63頁，2023年，2月20日，星期日1.2群群，是包含集合G和一種代數(shù)運(yùn)算‘*’，且滿足下列條件的代數(shù)系統(tǒng)：（a）運(yùn)算封閉；（b）有單位元；（c）有逆元；（d）滿足結(jié)合律。加法群：滿足加法和逆運(yùn)算的群。乘法群：滿足乘法和逆運(yùn)算的群。交換群：滿足交換律的群。子群：一個非空集合SG，S滿足群G的全部條件，則S稱為子群。第4頁，共63頁，2023年，2月20日，星期日

無限群：包含無數(shù)個元素的群。

有限群：包含有限個元素的群。有限群元素的個數(shù)稱為該群的階。

循環(huán)群：某一元素a（生成元a）的一切乘冪a0,a1,a2,…的全體組成一個群，稱為循環(huán)群，寫作G={a0,a1,a2,…},其中a0=e是單位元。若序列a0=e，a1,a2,…中沒有兩個元素是相等的，稱之為無限循環(huán)群。第5頁，共63頁，2023年，2月20日，星期日

若上述序列中有兩個相等的元素ai=aj,(ij)，可推出G的元素必以n為周期重復(fù)，即an=a0=e,這樣的循環(huán)群稱為有限循環(huán)群。循環(huán)群也叫冪群，具有以下性質(zhì)：（a）循環(huán)群是交換群；（b）循環(huán)群的子群仍是循環(huán)群；（c）n階循環(huán)群子群的階數(shù)一定是n的因子。第6頁，共63頁，2023年，2月20日，星期日例例1：令R、I、E分別是有理數(shù)、整數(shù)、偶數(shù)集合，則(E,+)是(I,+)的子群，則(I,+)是(R,+)的子群，單位元均是0。奇數(shù)集合O在加法運(yùn)算下構(gòu)不成群，因不滿足封閉性條件。例3集合G={0,1,2…m-1}在模m加（用符號表示）運(yùn)算下構(gòu)成一個群（G，）。該加群是m階有限群，單位元是0。元素0的逆元是0，1的逆元是m-1,2的逆元是m-2,…。例4：集合G={1,2…q-1}在模q乘（q是素?cái)?shù)）運(yùn)算下構(gòu)成一個乘群（G，）。第7頁，共63頁，2023年，2月20日，星期日1.3環(huán)

環(huán)，包含集合R和兩種代數(shù)運(yùn)算，且滿足下列條件的代數(shù)系統(tǒng)：（a）按第一種運(yùn)算（不妨稱為加法）構(gòu)成交換群；（b）第二種運(yùn)算（不妨稱為乘法）滿足以下條件：封閉性；結(jié)合律；單位元；（c）與加法間滿足分配律：對于a,b,cR，a(b+c)=ab+ac,(a+b)c=ac+bc。交換環(huán)：對于a,bR，ab=ba(交換律)，則稱R為交換環(huán)。第8頁，共63頁，2023年，2月20日，星期日1.4域域，具有交換環(huán)的性質(zhì)，且在乘法運(yùn)算時具有逆元的代數(shù)系統(tǒng)。域具有加和乘兩種運(yùn)算及它們的逆運(yùn)算。無限域有理數(shù)、實(shí)數(shù)和復(fù)數(shù)都是無限域。有限域：包含有限個（q）元素的域，或稱伽羅華域。q稱為域的階。在信道編碼中用到的是有限域，GF(q)。(0,1)二元域GF(2)，或稱基本域。由GF(2)GF(2m)，稱擴(kuò)域。第9頁，共63頁，2023年，2月20日，星期日

可以證明：伽邏華域GF(q)的(q-1)個非零元素在模q乘運(yùn)算下構(gòu)成一個循環(huán)群（冪群），即所有非零元素可由一個元素（稱作本原元）的各次冪0、1、2、…q-2生成。

第10頁，共63頁，2023年，2月20日，星期日1.5既約多項(xiàng)式

對于某數(shù)域上的多項(xiàng)式PI（x），若除了常數(shù)C以及CPI（x）外不能被該數(shù)域上的任何其它多項(xiàng)式整除，則稱為是該數(shù)域上的既約多項(xiàng)式。如：x4+x+1第11頁，共63頁，2023年，2月20日，星期日1.6本原多項(xiàng)式

對于有限域GF(q)上的m次既約多項(xiàng)式P(x)，若能被它整除的最簡單多項(xiàng)式(xn-1)的次數(shù)nqm–1,則稱該多項(xiàng)式為本原多項(xiàng)式。

本原多項(xiàng)式一定既約；既約多項(xiàng)式未必本原。如：m本原多項(xiàng)式

31+x+x3

41+x+x4

51+x2+x5

61+x+x6

第12頁，共63頁，2023年，2月20日，星期日比如：在GF(2)域上，x4+x+1(q=2,m=4,2m-1=15)

不能被x5+1整除；不能被x6+1整除；

……

不能被x14+1整除；能被x15+1整除；所以x4+x+1是本原多項(xiàng)式。而x4+x3+x2+x+1

能被x5+1整除；能被x15+1整除；所以，x4+x3+x2+x+1是既約的，但不是本原的。第13頁，共63頁，2023年，2月20日，星期日本原元

對于m次本原多項(xiàng)式p(x)，如果p(a)=0,那么a是GF(2m)的一個本原元。利用本原多項(xiàng)式可求擴(kuò)域GF(2m)的全部元素為：第14頁，共63頁，2023年，2月20日，星期日舉例p(x)=x2+x+1，求GF(22)的全部元素及加法乘法表。分析：令p(a)=0，得a2+a+1=0，a2＝a+1。那么全部元素為：冪表示矢量表示多項(xiàng)式表示0a0a1a2=a+10001101101xx+1第15頁，共63頁，2023年，2月20日，星期日1.6GF(q)的加、乘、減和除在GF(q)中，對元0,1,2,…,q-1使用modq的計(jì)算方法：進(jìn)行加法和乘法。如GF(3)的加法和乘法如下表：+012012012120201.012012000012021第16頁，共63頁，2023年，2月20日，星期日減法：a-b=a-b+qmodq如:1-2=1-2+3=2mod3除法：b/a=b.a-1modq如：因?yàn)?×2=1mod3，2的乘法逆元2-1為2，所以：2/2=2×2-1=2×2=1第17頁，共63頁，2023年，2月20日，星期日二、BCH碼第18頁，共63頁，2023年，2月20日，星期日2.1GF(2m)域上構(gòu)造循環(huán)碼的方法第19頁，共63頁，2023年，2月20日，星期日xn-1因式分解

(4-17)這里，既約因式mj(x)（j=0,…,l-1）分成兩部分，它們的乘積分別是g(x)和

h(x)。循環(huán)碼并不強(qiáng)調(diào)g(x)的既約性，它可以是既約的，也可以是非既約的。若某既約因式mj(x)是非既約g(x)的一個因式，必有：

mj(x)|g(x)|(xn-1) (4-18)

換一個角度，如果將(xn-1)看成是一個n次多項(xiàng)式，那么它在復(fù)數(shù)域應(yīng)該有n個根，記作ai，i=0,…,n-1，此時(xn-1)可表示成

xn-1=(x-a0)(x-a1)…(x-an-1) (4-19)第20頁，共63頁，2023年，2月20日，星期日例4-7（x4-1）在不同域上的因式分解在實(shí)數(shù)域的分解：x4-1=

(x2+1)(x+1)(x-1)在復(fù)數(shù)域的分解：x4-1=

(x+i)(x-i)(x+1)(x-1)在二元域的分解：x4-1=x4+1=(x+1)(x+1)(x+1)(x+1)上例說明：域不同則分解亦不同，在一個域的既約不等于在另一個域的既約。

既約多項(xiàng)式mj(x)在GF(2)上不能再分解，其系數(shù)在數(shù)域取值于{0,1}；但它在二元擴(kuò)域GF(2m)未必就不能再分解，因GF(2m)是多項(xiàng)式域，系數(shù)取值于{0、1、2、…、}。第21頁，共63頁，2023年，2月20日，星期日根據(jù)定理4.1：只要找到與循環(huán)碼對應(yīng)的一個n階元素，就可以將(xn-1)在GF(2m)上完全分解為：

xn-1=證：若

a是循環(huán)群n

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

將ai,i=0…n-1代入(xn-1)驗(yàn)根，得(ai)n-1=(an)i-1=(1)i-1=0∴ai,i=0…n-1是(xn-1)的n個根，以根為一次項(xiàng)可將(xn-1)完全分解為：

xn-1=(x-a0)(x-a1)…(x-an-1) 第22頁，共63頁，2023年，2月20日，星期日

二元擴(kuò)域GF(2m)是由一m次本原多項(xiàng)式生成的。當(dāng)n=2m-1時，這個n階域元素a就是(2m-1)階本原元，通常用表示本原元；當(dāng)n<(2m-1)且n|(2m-1)時，這個n階域元素a為非本原元，通常用表示非本原元。這里不強(qiáng)調(diào)域元素是否本原，所以用中性字母a來表示。

=xn-1= GF(2m)擴(kuò)域|GF(2)域

系數(shù)1既是擴(kuò)域又是二元域元素

或改變順序?yàn)?/p>

==xn-1

第23頁，共63頁，2023年，2月20日，星期日若(xn-1)的某一個根ai,i{0,1…n-1}又是某個既約因式mj(x),j{0,1…l-1}的根，也是(n-k)次生成多項(xiàng)式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)以上兩式說明：生成多項(xiàng)式g(x)的（n-k）個根也是(xn-1)的根，只要能夠以適當(dāng)?shù)姆椒ㄕ页鲞@些根，就可以從這些根得到生成多項(xiàng)式g(x)。第24頁，共63頁，2023年，2月20日，星期日研究表明：有重根的g(x)不能產(chǎn)生好碼。而如果(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頁，2023年，2月20日，星期日

用(xn-1)在GF(2m)域上的根來構(gòu)造循環(huán)碼的方法：①在(xn-1)的n個根中選取若干個r1、r2…rj，

其中rj{ai},i=0,1…n-1。②找出各根對應(yīng)的既約多項(xiàng)式r1→m1(x)、

r2→m2(x)…rj→mj(x)。③求出這些既約多項(xiàng)式的最小公倍式：

g(x)=LCM[m1(x),m2(x)…mj(x)]LCM(LeastCommonMultiple)-最小公倍式若選取的根是連續(xù)冪次的根，則所得的g(x)可以產(chǎn)生一個BCH碼。第26頁，共63頁，2023年，2月20日，星期日2.2BCH碼的定義

GF(q)域循環(huán)碼生成多項(xiàng)式g(x)，若含有2t個連續(xù)冪次的根 ，則由g(x)生成的(n,k)循環(huán)碼稱為q進(jìn)制BCH碼。連續(xù)冪次起始值m0的選取并無多大實(shí)際意義，通常固定取m0=1。若q=2，稱為二進(jìn)制（二元）BCH碼。若根a是本原元，稱該碼為本原BCH碼，其碼長n=qm-1。若根a是非本原元，稱該碼為非本原BCH碼，其碼長n是qm-1的因子，滿足n|(qm-1)。

第27頁，共63頁，2023年，2月20日，星期日BCH碼限定理：若BCH碼生成多項(xiàng)式g(x)中含有2t個連續(xù)冪次的根，則該碼的最小距離dmim2t+1證明：∵BCH碼多項(xiàng)式C(x)=m(x)g(x)∴g(x)的2t個連續(xù)冪次根、…、2t也是C(x)的根設(shè)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第28頁，共63頁，2023年，2月20日，星期日將上面2t個方程寫作矩陣形式，得：CAT=0 (4-24)其中：

A== 可見，A是范得蒙矩陣。數(shù)學(xué)證明：范得蒙矩陣一定是滿秩矩陣，即矩陣A的秩是2t或者說有2t列線性無關(guān)。碼的最小距離dmin等于校驗(yàn)矩陣中線性無關(guān)的列數(shù)加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第29頁，共63頁，2023年，2月20日，星期日 2.3本原BCH碼構(gòu)造法①由關(guān)系式n=2m-1算出m，查表4-5，找到一個m次本原多項(xiàng)式P(x)，產(chǎn)生一個GF(2m)擴(kuò)域。②在GF(2m)上找一個本原元，分別計(jì)算2t個連續(xù)冪次根、2、…、2t所對應(yīng)的GF(2)域上的最小多項(xiàng)式m1(x)、m2(x)…m2t(x)。m8時連續(xù)冪次根i所對應(yīng)的最小多項(xiàng)式見表4-6。③計(jì)算這些最小多項(xiàng)式的最小公倍式，得到生成多項(xiàng)式g(x)g(x)=LCM[m1(x)m2(x)…m2t(x)] (4-27)④由關(guān)系式C(x)=m(x)g(x)求BCH碼字。第30頁，共63頁，2023年，2月20日，星期日對于二元BCH碼，無需列出全部2t個連續(xù)冪次的根，而只要列出其中一半（奇數(shù)冪次的根）就可以了。這是因?yàn)槿魏我粋€偶數(shù)ie可寫成一個小于它的奇數(shù)io與2的l次冪的乘積：

ie

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

因此任何一個偶次冪根都是奇次冪根的共軛元

它們對應(yīng)同一個最小多項(xiàng)式。第31頁，共63頁，2023年，2月20日，星期日

i最小多項(xiàng)式i最小多項(xiàng)式i最小多項(xiàng)式i最小多項(xiàng)式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二元擴(kuò)域GF(2m)中連續(xù)冪次根所對應(yīng)的最小多項(xiàng)式

第32頁，共63頁，2023年，2月20日，星期日比如t=4時8個連續(xù)冪次根

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)]因此對于二進(jìn)制碼，構(gòu)造本原BCH碼的步驟改為:②分別計(jì)算t個連續(xù)奇次冪之根、3…2t-1所對應(yīng)的最小多項(xiàng)式m1(x)、m3(x)…m2t-1(x)。第33頁，共63頁，2023年，2月20日，星期日當(dāng)碼長n確定后，BCH碼糾錯能力t的選擇并不是任意的，而要受到一定限制。對于q元BCH碼，2t個根對應(yīng)2t個最小多項(xiàng)式，每個最小多項(xiàng)式的次數(shù)不會超過m，于是2t個最小多項(xiàng)式的最小公倍式g(x)的次數(shù)：

deg[g(x)]=(n-k)≤2t(4-29)對于二元BCH碼，t個根對應(yīng)t個最小多項(xiàng)式，因此

deg[g(x)]=(n-k)≤tm (4-30)(xn-1)一共有n個根，連續(xù)冪次根不能超過根的總數(shù)

2t

n (4-31)式(4-29)(4-30)給出了t的下限，式(4-31)給出了t的上限。第34頁，共63頁，2023年，2月20日，星期日例4.8設(shè)計(jì)一個碼長n=15的二元本原BCH碼，在不同糾錯能力下的生成多項(xiàng)式應(yīng)是怎樣的？解：∵15=24-1 ∴本題m=4①第一步：查表，找到一個m=4的本原多項(xiàng)式：P(x)=x4+x+1。令是該本原多項(xiàng)式P(x)的根，滿足4+

+1=0。由式(4-31)，本碼糾錯能力t7。②第二步：對于二元碼，分別計(jì)算t=7個連續(xù)奇次冪之根

3

57

911

13所對應(yīng)的最小多項(xiàng)式。本例可參考例2.2.3的表2-3，我們看到3、9是共軛元，7、11和13是共軛元（利用教材p124“共軛根系”定義分析）。第35頁，共63頁，2023年，2月20日，星期日根和根所對應(yīng)的最小多項(xiàng)式（例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頁，2023年，2月20日，星期日③第三步：求最小公倍式得到生成多項(xiàng)式g(x)。●若t=1，g1(x)=LCM[m1(x)]=x4+x+1g1(x)是4次多項(xiàng)式，即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碼。第37頁，共63頁，2023年，2月20日，星期日●若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碼?！袢魌=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碼。第38頁，共63頁，2023年，2月20日，星期日●若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)可見，當(dāng)t=4、5、6、7時的BCH碼均是(15,1)碼，生成多項(xiàng)式g4(x)擁有x的所有各次冪，意味著編碼時將一位信息“0”或“1”重復(fù)發(fā)送15次。因此，實(shí)際上只有t=1,2,3的(15,11)、(15,7)、(15,5)BCH碼才有實(shí)用價值。第39頁，共63頁，2023年，2月20日，星期日

非本原BCH碼與本原BCH碼的主要區(qū)別在于所用的根是否本原元。當(dāng)碼長n和糾錯能力t給定后，本原BCH碼的根一定是n=2m-1階,n已知就是m已知，因而GF(qm)好找。非本原BCH碼的根是n階元素,滿足n|(qm-1)，

n已知不等于m已知，需要多一道計(jì)算。

第40頁，共63頁，2023年，2月20日，星期日已知n和t后二元非本原BCH碼的設(shè)計(jì)步驟：①求出滿足

n|(2m-1)關(guān)系的m的最小值。n是(2m-1)的因子，可以借助2m-1的素因子分解表（如表4-7）來尋找m值。②查表4-5，找出一個m階的本原多項(xiàng)式P(x)，產(chǎn)生一個二元擴(kuò)域GF(2m)。③以P(x)的根為中介找出一個n階的非本原元。④計(jì)算與、3、5…2t-1對應(yīng)的最小多項(xiàng)式m1(x)、m3(x)…m2t-1(x)。⑤求生成多項(xiàng)式g(x)=LCM[m1(x)m3(x)…m2t-1(x)]。第41頁，共63頁，2023年，2月20日，星期日表4-72m-1的素因子分解（m<34）

m素因子分解m素因子分解m素因子分解123456789101113735313371273517773311312389121314151617181920212233571381913431277311513517257131071333719735242873551l3141771273373238968323242526272829303132334717848133571317241316011801327318191773262657352943113127233110320893371131151331214748364735172576553772389599479第42頁，共63頁，2023年，2月20日，星期日例4.9試設(shè)計(jì)一個碼長n=23，糾兩個隨機(jī)差錯(t=2)的二元BCH碼。

解：①由于碼長n2m-1比如15、31、…255…等值，可知要求設(shè)計(jì)的是二元非本原BCH碼。檢查能被n=23整除的2m-1(表4-7)，m的最小值是11(211-1=2047=89×23,能夠整除23)，所以取m=11。②查表4-5,得11階的本原多項(xiàng)式是P(x)=x11+x2+1。令是本原多項(xiàng)式P(x)的根，滿足11+2+1=0。由于是本原元，它的階數(shù)是211-1=2047，滿足2047=1。③為了得到23階域元素，將2047=1改寫為2047=89×23=(89)23=()23=1,式中=89。事實(shí)上，0,1,2,3,…2047本身都是域元素，只是將域元素89定義為域元素而已。由于(89)23=()23=1，因此可斷言是一個23階的非本原元。第43頁，共63頁，2023年，2月20日，星期日④求連續(xù)奇冪次的根所對應(yīng)的最小多項(xiàng)式。首先找出的所有共軛元，然后再來計(jì)算最小多項(xiàng)式。的共軛元有：,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碼的生成多項(xiàng)式g(x)至少是11次多項(xiàng)式，有11個根。同理可得另一組共軛元5,10,20,17,11,22,21,19,15,7,14，也是11個。第44頁，共63頁，2023年，2月20日，星期日第一組所對應(yīng)的最小多項(xiàng)式為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在上式運(yùn)算過程中用到23=1,=89,11+2+1=0等關(guān)系式。⑤本題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)可以產(chǎn)生一個(23,12)二元非本原BCH碼，它就是著名的戈萊碼（Golay），該碼是完備碼，復(fù)雜度適中而糾錯能力強(qiáng)，實(shí)踐中應(yīng)用廣泛。第45頁，共63頁，2023年，2月20日，星期日表4-8BCH碼主要參數(shù)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校驗(yàn)元(n-k)糾錯能力t最小距離dmg(x)的根m0,m0+1…m0+2t-1,2…2t,2…2t第46頁，共63頁，2023年，2月20日，星期日三、BCH碼譯碼第47頁，共63頁，2023年，2月20日，星期日1960年，彼得森（Peterson）首先從理論上解決了二進(jìn)制BCH碼的時域譯碼問題，稍后就有人把它推廣到多進(jìn)制BCH碼。

1966年，伯利坎普（Berlekamp）提出了迭代譯碼算法，該算法后來被公認(rèn)是經(jīng)典的BCH實(shí)用譯碼算法。第48頁，共63頁，2023年，2月20日，星期日3.1從碼多項(xiàng)式R(x)計(jì)算伴隨式S(x)

BCH碼的生成多項(xiàng)式含有2t個連續(xù)冪次的根，又由根與校驗(yàn)矩陣的關(guān)系(式4-25)，BCH碼的校驗(yàn)矩陣可寫成：

1

2…n-1

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

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

(2t)2…(2t)n-1第49頁，共63頁，2023年，2月20日，星期日伴隨式S=(s1,s2…si…s2t)=(r0,r1,…,rn-1

)HT(4-59)其中，

(4-60)或?qū)懗桑?/p>

(4-61)第50頁，共63頁，2023年，2月20日，星期日若與i對應(yīng)的最小多項(xiàng)式是i(x),接收碼多項(xiàng)式R(x)除以i(x)的余式為pi(x)，則有：R(x)=qi(x)i(x)+pi(x)以x=i代入，∵i是i(x)的根，∴i(i)=0。由關(guān)系式(4-61)得：R(i)=qi(i)i(i)+pi(i)=pi(i)=Si (4-62)可見，Si等于R(x)除以i所對應(yīng)的最小多項(xiàng)式i(x)后的余式。由于最小多項(xiàng)式i(x)的次數(shù)低于生成多項(xiàng)式g(x),一般可減小計(jì)算量。

第51頁，共63頁，2023年，2月20日，星期日例4.19(15,5,7)二元BCH碼的t=3，根所在域由本原多項(xiàng)式P(x)=x4+x+1生成。若收碼R(x)已知，計(jì)算其伴隨式Si。解：據(jù)例2.9表2.2，,2,4,8是共軛元，對應(yīng)同一最小多項(xiàng)式1(x)=x4+x+1。3,6,9,12也是共軛元，對應(yīng)同一最小多項(xiàng)式2(x)=x4+x3+x2+x+1，而共軛元5、10對應(yīng)的最小多項(xiàng)式是3(x)=x2+x+1。對于t=3的BCH碼，應(yīng)有2t=6個連續(xù)冪次的根，它們各自對應(yīng)的最小多項(xiàng)式如表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第52頁，共63頁，2023年，2月20日，星期日

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連續(xù)冪次根的最小多項(xiàng)式和伴隨式

根伴隨式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)最小多項(xiàng)式i(x)第53頁，共63頁，2023年，2月20日，星期日3.2從伴隨式S(x)到差錯位置的迭代算法假設(shè)差錯圖樣E(x)有個差錯分別在j1、j2、…、j位上：

(4-63)這里0

j1<j2…<j

n-1,ji表示第i個差錯的位置。由式(4-61)及(4-63)可導(dǎo)出下面一組方程：

(4-64)┇第54頁，共63頁，2023年，2月20日，星期日為書寫方便，令由于指示了錯誤所在的位置，稱之為錯誤位置數(shù)。將其代入式(4-64)，可得：

(4-65)式(4-65)稱為冪和對數(shù)函數(shù)，其中S1、S2、…S2t是2t個已知數(shù)，可列出2t個方程，這些方程中包含了1、2、…、

共

個未知數(shù)。下一步任務(wù)是解這個非線性方程組，求出差錯誤位置數(shù)1、2、…、。第55頁，共63頁，2023年，2月20日，星期日解方程組，一般用

個方程解

個未知數(shù)。然而這里差錯數(shù)本身也是未知數(shù)，既不知道是多少，也不知道它比2t大還是小。任何一種求解該非線性方程的算法就是一種譯碼方法，以下介紹伯利坎普迭代算法。首先引入一個中間變量(x)，稱為差錯位置多項(xiàng)式：

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

x

(4-66)顯然，差錯位置多項(xiàng)式(x)的個根是差錯位置數(shù)的倒數(shù)1-1、2-1、…、-1。(x)各次項(xiàng)的系數(shù)0

12…與1、2、…、一樣是未知數(shù)。第56頁，共63頁，2023年，2月20日，星期日將式(4-66)的乘積展開并比較等式兩邊同次冪的系數(shù)，可得：

0=1

1=1+2+…+

2=12+23+…+－1

(4-67)

┇

=12…

式中，i稱為初等對稱函數(shù)。

第57頁，共63頁，2023年，2月20日，星期日式(4-65)給出Si和l

的關(guān)系，式(4-67)給出l和l的關(guān)系。結(jié)合兩式，可得到Si和l的關(guān)系如下: S1+1=0 S2+1S1

+22=0 S3+1S2

+2S1

+33=0 (4-68