第七章BCH碼與Goppa碼

第7章BCH碼與Goppa碼7.1BCH碼的描述及其距離限7.2二進(jìn)制BCH碼及其擴(kuò)展7.3Reed-Solomon(RS)碼7.4BCH碼的一般譯碼方法7.5BCH碼的迭代譯碼算法§7.1BCH碼的描述及其距離限

一、BCH碼的定義BCH碼是糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，可以用生成多項(xiàng)式g(x)的根描述。定義7.1.1給定任一有限域GF(q)及其擴(kuò)域GF(qm)，其中q是素?cái)?shù)或素?cái)?shù)的冪，m為某一正整數(shù)。若碼元取自GF(q)上的一循環(huán)碼，它的生成多項(xiàng)式g(x)的根集合R中含有以下δ-1個(gè)連續(xù)根：時(shí)，則由g(x)生成的循環(huán)碼稱為q進(jìn)制BCH碼。

設(shè)mi(x)和ei分別是

(i=0，1，…，δ-2)元素的最小多項(xiàng)式和級(jí)，則由式（５.２.３）和式(5.2.4)可知，BCH碼的生成多項(xiàng)式和碼長分別是：g(x)=LCM(m0(x)，m1(x)，…，mδ-2(x))(7.1.1)n=LCM(e0，e1，…，eδ-2)(7.1.2)

如果生成多項(xiàng)式g(x)的根中，有一個(gè)GF(qm)中的本原域元素，則n=qm-1，稱這種碼長n=qm-1的BCH碼為本原BCH碼；否則，稱為非本原BCH碼。GF(qm)中元素的級(jí)一定是qm-1的因子，所以非本原BCH碼的碼長也一定是qm-1的因子。二、BCH碼的距離限定理7.1.1(BCH限)BCH碼的最小距離dBCH至少為δ。BCH碼限的證明有兩種方法，一種是從碼的校驗(yàn)矩陣H出發(fā)，另一種是從碼的ＤＦＴ或ＭＳ多項(xiàng)式出發(fā)。定理7.1.2(HT限)若BCH碼的生成多項(xiàng)式g(x)的根集R中含有s組δ-1個(gè)α的連續(xù)元素：R｛

｜i=0，1，…，s-1;j=0，1，…，δ-2｝且(n，a)=1，α∈GF(qm)是n級(jí)元素，則碼的最小距離dHT≥δ+s-1。定理7.1.3(Roos限)若BCH碼的g(x)根集R含有s組α的δ-1個(gè)連續(xù)元素R｛

｜i只取0至s+μ-1中的s個(gè)整數(shù)；j=0，1，…，δ-2｝，且(a，n)=1，αn=1，α∈GF(qm)，則碼的最小距離dR≥δ+s-1?！?.2二進(jìn)制BCH碼及其擴(kuò)展

一、二進(jìn)制BCH碼在實(shí)際中應(yīng)用得最多的是碼元取自GF(2)中的二進(jìn)制BCH碼。由BCH碼的定義可知，對(duì)任一個(gè)正整數(shù)m，一定可以構(gòu)造出以下的二進(jìn)制碼。

取m0=1，δ=2t+1，又設(shè)α是GF(2m)的本原域元素，則由BCH碼的定義可知：若碼以α，α2，…，α2t為根，則二進(jìn)制BCH碼的生成多項(xiàng)式g(x)=LCM(m1(x)m2(x)…m2t(x))(7.2.1)式中，mi(x)是αi(1≤i≤2t)的最小多項(xiàng)式，該BCH碼一定能糾正t個(gè)錯(cuò)誤。

由第四章知，在特征為２的GF(2m)域上，α2i的最小多項(xiàng)式與αi的相同，所以，式(7.2.1)也可寫成g(x)=m1(x)m3(x)…m2t-1(x)(7.2.2)因此，二進(jìn)制BCH碼以α，α3，α5，…，

α2t-1為根，碼長n=LCM(e1，e3，…，e2t-1)(7.2.3)碼的校驗(yàn)矩陣是(7.2.4)

式中，e1，e3，…，e2t-1分別是α，α3，…，

α2t-1元素的級(jí)。顯然，二進(jìn)制BCH碼的碼長或者是2m-1或者是它的一個(gè)因子。我們把上述結(jié)果歸結(jié)成如下定理。

定理7.2.1對(duì)任何正整數(shù)m和t，一定存在一個(gè)二進(jìn)制BCH碼，它以α，α3，…，α2t-1為根，其碼長n=2m-1或是2m-1的因子，能糾正t個(gè)隨機(jī)錯(cuò)誤，校驗(yàn)位數(shù)目至多為°g(x)=mt個(gè)。

例7.1m=4，α∈GF(24)是本原域元素，它是x4+x+1的根。求碼長n=24-1=15的二進(jìn)制BCH碼。(1)t=1，則碼以α，α2，α4，α8為根，α的最小多項(xiàng)式m1(x)=x4+x+1，所以碼的生成多項(xiàng)式g(x)=m1(x)=x4+x+1校驗(yàn)元數(shù)目是°g(x)=4，得到一個(gè)［15，11，3］BCH碼，這是一個(gè)糾正單個(gè)錯(cuò)誤的循環(huán)漢明碼?？芍?，糾正單個(gè)錯(cuò)誤的本原BCH碼就是循環(huán)漢明碼。

(2)t=2,則碼以α，α3為根，α3的最小多項(xiàng)式為m3(x)=x4+x3+x2+x+1，所以g(x)

=m1(x)m3(x)=(x4+x+1)(x4+x3+x2+x+1)

=x8+x7+x6+x4+1

n=LCM(15，5)=15有8個(gè)校驗(yàn)元，得到一個(gè)［15，7，5］碼，能糾正2個(gè)隨機(jī)錯(cuò)誤。

(3)t=3，則碼以α，α3，α5為根，α5的最小多項(xiàng)式m5(x)=x2+x+1，所以g(x)

=m1(x)m3(x)m5(x)

=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)

=x10+x8+x5+x4+x2+x+1得到一個(gè)［15，5，7］BCH碼。

(4)t=4。碼以α，α3，α5，α7為根，α7的最小多項(xiàng)式m7(x)=x4+x3+1，所以碼的生成多項(xiàng)式g(x)

=m1(x)m3(x)m5(x)m7(x)

=x14+x13+x12+x11+x10+x9+x8+x7

+x6+x5+x4+x3+x2+x+1

得到一個(gè)［15，1，15］碼，這是一個(gè)重復(fù)碼，最小距離d=15，能糾正7個(gè)隨機(jī)錯(cuò)誤。該碼雖以α，α3，α5，α7為根，但由于共軛根系的原因，該碼實(shí)際上以αi，1≤i＜14，14個(gè)連續(xù)元素為根，故設(shè)計(jì)距離δ=15，實(shí)際最小距離也為1５。

例7.2求碼長n=21，糾2個(gè)隨機(jī)錯(cuò)誤的BCH碼。

n=21不是2m-1的類型，故必是2m-1的一個(gè)因子。26-1=21×3，所以GF(26)是含有21級(jí)元素的最小域。設(shè)α∈GF(26)是本原域元素，它是x6+x+1的根。令β=α3，則β的級(jí)是21。要求糾正2個(gè)錯(cuò)誤，則g(x)以β，β3為根。β=α3的最小多項(xiàng)式m1(x)=x6+x4+x2+x+1β3=(α3)3=α9的最小多項(xiàng)式m3(x)=x3+x2+1，所以碼的生成多項(xiàng)式

g(x)

=m1(x)m3(x)

=(x6+x4+x2+x+1)(x3+x2+1)

=x9+x8+x7+x5+x4+x+1

n=LCM(21，7)=21得到一個(gè)［21，12，5］非本原BCH碼。二、BCH碼的擴(kuò)展由第三章可知，任何一個(gè)奇重量線性碼，增加1個(gè)全校驗(yàn)位后最小重量增加１。若我們對(duì)奇最小距離的［n，k，d］BCH碼增加1個(gè)全校驗(yàn)位，則變成一個(gè)［n+1，k，d+1］碼，稱它為擴(kuò)展BCH碼。若對(duì)［2m-1，k，d］本原BCH碼增加1個(gè)全校驗(yàn)位，則變成［2m，k，d+1］碼，稱為擴(kuò)展本原BCH碼。設(shè)［n，k，δ］BCH碼以α，α2，…，αδ-1為根。由式(7.1.3)可知，碼的校驗(yàn)矩陣由H矩陣每行每列的性質(zhì)可知，［n+1，k，δ+1］擴(kuò)展碼的校驗(yàn)矩陣為(7.2.5)顯然，這相當(dāng)于碼增加了以α0=1為根。但是必須注意，這種擴(kuò)展方法與增加以１為根，減少１個(gè)信息位的增余刪信BCH碼不一樣，它們的最小距離雖然都增加了１，但擴(kuò)展BCH碼的碼長增加了１，且每個(gè)碼字之間不一定存在循環(huán)關(guān)系，而增余刪信BCH碼的碼長與原碼相同，且仍是循環(huán)碼。如二進(jìn)制［7，4，3］本原BCH碼，它以α，α2，α4為根，g(x)=x3+x+1，校驗(yàn)矩陣H=［α6α5

α4α3α2α1

1］該碼增加一個(gè)全校驗(yàn)位后變成［8，4，4］擴(kuò)展本原BCH碼，它的校驗(yàn)矩陣因［7，4，3］碼是一個(gè)漢明碼，所以［8，4，4］碼也稱為擴(kuò)展?jié)h明碼。若［7，4，3］碼增加以α0=1為根，則碼的生成多項(xiàng)式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1，此碼的校驗(yàn)矩陣為這是一個(gè)［7，3，4］BCH碼，它其實(shí)就是一個(gè)增余刪信漢明碼。

碼長n≤255的二進(jìn)制本原BCH碼，它的k、d和生成多項(xiàng)式g(x)列于表7-4中。表5-2中列出的QR碼(除［7，4］和［31，16］碼以外)都是非本原BCH碼，此外還有一些非本原BCH碼，它們的d和g(x)列于表7-5中。表7-4和表7-5中生成多項(xiàng)式g(x)欄下面的數(shù)字，代表g(x)的二進(jìn)制系數(shù)的八進(jìn)制數(shù)表示。例如，八進(jìn)制數(shù)１３的二進(jìn)制數(shù)表示為001011，因而代表g(x)=x3+x+1。b和z分別表示該碼的糾突發(fā)錯(cuò)誤能力和最佳程度。這將在第九章中講到。表7-5中的(QR)表示該碼是平方剩余碼。由該圖可以明顯看出：(1)當(dāng)碼的糾錯(cuò)能力t／n固定時(shí)，碼長越短，碼的R越大；當(dāng)n≤31時(shí)接近漢明限；而n≤1023時(shí)，接近V-G限；但是隨著n→∞，R→0。(2)當(dāng)碼率R固定時(shí)，碼長≤31時(shí)，碼的糾錯(cuò)能力接近漢明限；n≤1023時(shí)，接近V-G限；但是隨著n→∞，碼的糾錯(cuò)能力t／n→0。由此可知，BCH碼的性能在碼長≤1023時(shí)很好，都在V-G限以上；特別在短碼時(shí)性能更好，接近漢明限；但隨著碼長的增加，性能變壞。因此BCH碼做不到香農(nóng)編碼定理所要求的能力。雖然圖7-1是根據(jù)表7-4的BCH限得到的，但由定理7.1.8可知，BCH碼的實(shí)際距離d≤qδ+q-2≈qδ=2δ(二進(jìn)制情況)因此，實(shí)際上當(dāng)R固定時(shí)，BCH碼的糾錯(cuò)能力隨著n的增加仍趨向于0。即使如此，在中、短碼長時(shí)BCH碼仍不愧是一個(gè)很好的碼。表7-5某些二進(jìn)制非本原BCH碼圖7-1某些二進(jìn)制BCH碼的糾錯(cuò)能力§7.3Reed-Solomon(RS)碼

RS碼是一類有很強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH碼，也是一類典型的代數(shù)幾何碼。它首先由里德(Reed)和索洛蒙(Solomon)應(yīng)用MS多項(xiàng)式(p178)于1960年構(gòu)造出來的。當(dāng)然，用MS多項(xiàng)式構(gòu)造的RS碼是非系統(tǒng)碼，而用BCH碼構(gòu)造方法能產(chǎn)生系統(tǒng)碼。

一、RS碼的時(shí)域編碼定義7.3.1GF(q)(q≠2)上，碼長N=q-1的本原BCH碼稱為RS碼。可知RS碼最主要特點(diǎn)之一是碼元取自GF(q)上，而它的生成多項(xiàng)式的根也在GF(q)上，所以RS碼是碼元的符號(hào)域與根域一致的BCH碼。

因?yàn)?/p>

αi的最小多項(xiàng)式mi(x)=x-αi。所以，長為N=q-1，設(shè)計(jì)距離為δ的RS碼，由BCH碼的定義可知，它的生成多項(xiàng)式

(7.3.1)

通常情況下取m0=1，此時(shí)

g(x)=(x-α)(x-α2)…(x-αδ-1)(7.3.2)

由此生成一個(gè)q進(jìn)制的［q-1，q-δ］RS碼，有最小距離為δ。由于線性碼的最大可能的最小距離是校驗(yàn)元的個(gè)數(shù)加１，而RS碼恰好做到了這一點(diǎn)。因此，稱RS碼為極大最小距離可分碼，簡稱MDS碼。顯然，RS碼的設(shè)計(jì)距離δ與實(shí)際距離D是一致的。

例7.3設(shè)碼的符號(hào)取自GF(q)=GF(23)中的元素，α∈GF(23)是本原域元素，它是x3+x+1的根，構(gòu)造D=5的RS碼。GF(23)的元素同表4-1。

要求碼的D=5，則碼必以α，α2，α3，α4為根，因此由式(7.3.2)可知，碼的生成多項(xiàng)式g(x)=(x-α)(x-α2)(x-α3)(x-α4)=x4+α3x3+x2+αx+α3由此生成一個(gè)GF(23)上的八進(jìn)制［7，3，5］本原BCH碼，也就是［7，3，5］RS碼。它的系統(tǒng)碼生成矩陣由式(5.1.7)可知為相應(yīng)的校驗(yàn)多項(xiàng)式

校驗(yàn)矩陣為：

或

一般情況下，GF(q)上系統(tǒng)碼形式［q-1，q-D］RS碼的H矩陣(7.3.3)或由式(5.1.9)可得H的標(biāo)準(zhǔn)形式為GF(2m)上的RS碼是2m進(jìn)制碼，它的編碼電路可用k或n-k級(jí)2m進(jìn)制移位寄存器實(shí)現(xiàn)。該例中［7，3，5］RS碼的編碼器，若用k=3級(jí)乘法電路實(shí)現(xiàn)，則如圖7-2所示。圖中的移存器必須是能寄存八進(jìn)制的元件組成，這可用３級(jí)觸發(fā)器組成的移存器完成。α2，α3，α4常乘器也可用模2加法器構(gòu)成。現(xiàn)以乘α2為例，說明八進(jìn)制常乘器的組成。GF(23)中每個(gè)元素均可表示成它的自然基底1，α，α2的線性組合：a2α2+a1α+a0，在乘以α2后，則α2(a2α2+a1α+a0)

=a2α4+a1α3+a0α2=a2(α2+α)+a1(α+1)+a0α2

=(a2+a0)α2+(a2+a1)α+a1=a′2α2+a′1α+a′0式中

a′2=a2+a0

a′1=a2+a1

a′0=a1所以，乘α2電路如圖7-3所示。圖7-2［7,3,5］八進(jìn)制RS碼編碼器圖7-3GF(23)中乘α2電路圖7-4［7，3，5］RS碼編碼器(1)門1、門2、門3關(guān)閉，所有移存器清洗為０。然后將３個(gè)八進(jìn)制信息符號(hào)cn-1=c6，cn-2=c5，cn-3=c4，一方面送入八進(jìn)制寄存器中，另一方面送入信道。注意每一節(jié)拍移動(dòng)１個(gè)八進(jìn)制符號(hào)。(2)3個(gè)八進(jìn)制信息元送入后，門１、門２、門３打開，移動(dòng)一個(gè)節(jié)拍后，這時(shí)移存器右移一位送出c6，同時(shí)得到第一個(gè)校驗(yàn)元c3，它一方面送至信道，另一方面存入八進(jìn)制寄存器的第一級(jí)中（最左面）。這時(shí)在八進(jìn)制寄存器中存貯的數(shù)據(jù)自左至右是c3，c4，c5。再移動(dòng)1個(gè)節(jié)拍，得到第二個(gè)校驗(yàn)元c2，這樣依次類推移完７個(gè)節(jié)拍后，得到了所有４個(gè)校驗(yàn)元，并且跟隨在信息元后送至信道，完成了一個(gè)碼字的編碼過程。(3)清洗寄存器，重新關(guān)閉門１、門２、門３，重復(fù)（１）、（２）過程，對(duì)第二組信息元進(jìn)行編碼。如果GF(q)上RS碼的生成多項(xiàng)式為g(x)

=(x-αa)(x-αa+1)…(x-αa+δ-2)

=g0+g1x+…+gδ-1

xδ-1

=g0+g1x+…+g2tx2t這里，α∈GF(q)，αq-1=1，若αaαa+2t-1=1，則生成多項(xiàng)式g(x)的系數(shù)具有如下特點(diǎn)：g0=g2t=1，g1=g2t-1，gt-1=gt+1，…。生成多項(xiàng)式的系數(shù)有對(duì)稱性，g(x)的互反多項(xiàng)式g*(x)=g(x)。對(duì)這種RS碼的編碼器，只要t個(gè)乘法器就夠了。最近，林舒等應(yīng)用域元素的對(duì)偶基表示，使RS碼的編譯碼更為簡單，有關(guān)這方面的知識(shí)可參閱［11］。§7.4BCH碼的一般譯碼方法

一、BCH碼譯碼的基本概念BCH碼的譯碼與第三章講的線性碼的譯碼步驟相同分為3步：第一步是由接收到的R(x)計(jì)算出伴隨式S；第二步由伴隨式找出錯(cuò)誤圖樣ê(x)；第三步由R(x)-ê(x)得到最可能發(fā)送的碼字(x)，完成譯碼。

設(shè)GF(q)上的［n，k，d］BCH碼以

為根，則它的生成多項(xiàng)式

α∈GF(qm)為n級(jí)域元素。發(fā)送的碼字C(x)=q(x)g(x)，接收的n重為R(x)=C(x)+E(x)。設(shè)錯(cuò)誤圖樣

E(x)=en-1

xn-1+en-2

xn-2+…+e1x+e0

若信道產(chǎn)生t個(gè)錯(cuò)誤，則錯(cuò)誤位置錯(cuò)誤值譯碼的目標(biāo)

求解錯(cuò)誤位置和錯(cuò)誤值由伴隨式定義和式(7.1.3)可知：(7.4.1)式中

j=m0，m0+1，…，m0+2t-1若令，則上式可寫成

j=m0，m0+1，…，m0+2t-1(7.4.2)

或(7.4.3)通常情況下取m0=1，則(7.4.4)稱式中的sj為x的加權(quán)冪和對(duì)稱函數(shù)。

求解上述2t個(gè)方程可求出2t個(gè)未知數(shù)(錯(cuò)誤值和錯(cuò)誤位置)，但上述方程組是非線性的，因此求解變得非常困難。皮特提出了先求解錯(cuò)誤位置，再求錯(cuò)誤值的方法：直接求解錯(cuò)誤位置無法著手，皮特提出用中間變量，構(gòu)造一個(gè)中間方程:

錯(cuò)誤位置多項(xiàng)式p270經(jīng)推導(dǎo)得到7.4.7式，仍求不出，但s1，s2，…，s2t已知，將σ1，σ2，。。。σt與s1，s2，…，s2t聯(lián)系起來：由7.4.77.4.8的推導(dǎo)得到7.4.10

求解7.4.10線性方程組可得到錯(cuò)誤位置，但一般求解起來也很麻煩，錢聞天提出了快速求解錯(cuò)誤位置的方法：錢搜索法

二、錢(Chien)搜索和伴隨式計(jì)算電路用式(7.4.10)求得σ(x)后，下一步的問題是從工程觀點(diǎn)看，如何簡單地求出它的根即錯(cuò)誤位置。１９６４年錢聞天提出了一個(gè)求σ(x)根的實(shí)用方法，解決了這個(gè)問題。思想：σ(x)的根只能在α1

α2，…，αn中出現(xiàn)，逐個(gè)帶入σ(x)，看是否是滿足方程。

解σ(x)的根，就是確定R(x)中哪幾位產(chǎn)生了錯(cuò)誤。設(shè)R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0，為了要檢驗(yàn)第一位rn-1是否錯(cuò)誤，相當(dāng)于譯碼器要確定αn-1是否是錯(cuò)誤位置數(shù)，這等于檢驗(yàn)α-(n-1)是否是σ(x)的根。若

α-(n-1)=α是σ(x)的根，則σ(α-(n-1))=σ(α)=1+σ1α+σ2α2+…+σtαt=0或σ1α+σ2α2+…+σtαt=-1

所以得到了σ(x)后，為了譯rn-1，譯碼器首先計(jì)算σ1α，σ2α2，…，σtαt，然后計(jì)算它們的和是否為-1。若是，則αn-1是錯(cuò)誤位置數(shù)，rn-1碼元是錯(cuò)誤的；否則rn-1是正確的。換言之

σ1α+σ2α2+…+σtαt=-1，rn-1有錯(cuò)σ1α+σ2α2+…+σtαt≠-1，rn-1正確(7.4.15)

同理，為了譯rn-l譯碼器必須計(jì)算σ1xl，σ2α2l，…，σtαtl，并計(jì)算它們的和，若

σ1αl+σ2α2l+…+σtαtl=-1rn-l有錯(cuò)σ1αl+σ2α2l+…+σtαtl≠-1rn-l正確(7.4.16)這樣依次對(duì)每一個(gè)rn-l

(l=1，2，…，n)進(jìn)行檢驗(yàn)，就求得了σ(x)的根，這個(gè)過程稱為錢搜索。在工程上，錢搜索過程可用圖７－５所示的電路實(shí)現(xiàn)，它的工作過程如下：(1)t個(gè)寄存器寄存σ1，σ2，…，σt，當(dāng)錯(cuò)誤個(gè)數(shù)γ＜t，則σγ+1=σγ+2=…=σt=0。(2)rn-1正要從緩沖存貯器讀出之前，t個(gè)乘法器由移位脈沖控制行乘法運(yùn)算，且σ1α，σ2α2，…，σtαt存在σ寄存器中，并送入A中進(jìn)行σ1α+σ2α2+…+σtαt運(yùn)算和檢驗(yàn)。若等于－１，則A輸出一個(gè)信號(hào)，控制門打開，把錯(cuò)誤值Yn-1與緩存器輸出的rn-1相減，得到rn-1-Yn-1=cn-1。在二進(jìn)制情況下，A輸出1與rn-1進(jìn)行模2加，即完成對(duì)rn-1的糾錯(cuò)。圖7-5錢搜索電路圖(3)rn-1譯完后，再進(jìn)行一次相乘，此時(shí)σ1α2，σ2(α2)2，…，σt(αt)2存在σ寄存器中，并在A中進(jìn)行相加運(yùn)算和檢驗(yàn)，對(duì)rn-2進(jìn)行糾錯(cuò)。(4)其余碼元同(2)一樣糾錯(cuò)。圖7-6m1(x)、m3(x)、m5(x)除法電路圖7-7計(jì)算s1至s6電路§7.5BCH碼的迭代譯碼算法

1966年,伯利坎普(Berlekamp)提出了迭代譯碼算法，1969年梅西（Massey)推導(dǎo)出迭代譯碼算法與最短線性移位寄存器序列（m序列）之間的關(guān)系，用簡化的方式解讀了伯利坎普(Berlekamp)提出的迭代譯碼算法，后來稱為BM迭代譯碼算法?！?.5BCH碼的迭代譯碼算法一、迭代譯碼算法的基本原理由式(7.4.7)可知：

(7.5.1)(7.5.2)式中，s0=1。作乘積S(x)δ(x)，并用

ω(x)=1+ω1x+ω2x2+…(7.5.3)

表示該乘積

S(x)σ(x)=ω(x)

將式(7.5.1)和式(7.5.2)代入上式并展開S(x)σ(x)=1+(s1+σ1)x+(s2+σ1s1+σ2)x2+…+(st+σ1st-1+…+σt)xt+(st+1+σ1st+…+σts1)xt+1+…=1+ω1x+ω2x2+…+ωtxt+ωt+1xt+1+…(7.5.4)由式(7.4.9)可知，若m0=1，則有：

st+1+σ1st+…+σts1=0st+2+σ1st+1+…+σts2=0…(7.5.5)s2t+σ1s2t-1+…+σtst=0所以，式(7.5.4)中大于xt的系數(shù)均為0。由于σ(x)的次數(shù)為t，而式(7.5.4)中的最高次數(shù)為t，所以°ω(x)≤t，或°ω(x)≤°σ(x)。由式(7.5.4)看出，式(7.5.2)中的S(x)及σ(x)都只要選到xt次項(xiàng)即可，因而°S(x)σ(x)≤2t。所以式(7.5.4)成為

S(x)σ(x)≡ω(x)

(modx2t+1)(7.5.6)稱它是求σ(x)的

關(guān)鍵方程

。(1)由初值

σ(-1)(x)=1，ω(-1)(x)=0，D(1)=0，d-1=1

σ(0)(x)=1，ω(0)(x)=1，D(0)=0，d0=s1開始迭代。圖7-8求σ(x)的迭代算法流程圖(2)按式(7.5.12)計(jì)算dj，若dj=0，則有：

σ(j+1)(x)=σ(j)(x)

ω(j+1)(x)=ω(j)(x)

D*(j+1)=D*(j)并計(jì)算dj+1，再進(jìn)行下一次迭代。如果dj≠0，則找出j之前的某一行i，它在所有j行之前各行中的i-D*(i)最大，且di≠0，于是按照式(7.5.13)和式(7.5.14)分別計(jì)算σ(j+1)(x)和ω(j+1)(x)，這就是第j+1步的解。(3)計(jì)算dj+1，重復(fù)(2)進(jìn)行下一次迭代。這樣2t次迭代后得到的σ(2t)(x)和ω(2t)(x)即為所求的σ(x)和ω(x)。ω(x)是在求σ(x)過程中得到的輔助多項(xiàng)式，在求解錯(cuò)誤值時(shí)將用到，故稱ω(x)為

錯(cuò)誤值多項(xiàng)式

。上述迭代過程如圖7-8所示?？闪谐杀恚?６，進(jìn)行迭代時(shí)逐步把表格填滿即可。

表7-6求σ(x)

的迭代過程表

表7-7求［15，9，7］

RS碼σ(x)

的迭代過程表表7-8求［31，11，11］

二進(jìn)制BCH碼σ(x)

的迭代過程表二、二進(jìn)制

BCH碼迭代譯碼算法的簡化由例7.7看出，迭代譯碼過程中，若j為奇數(shù)時(shí)dj=0，因而迭代次數(shù)可以減少一半，下面我們將證明這一點(diǎn)。若碼為二進(jìn)制BCH碼，則E(x)中的錯(cuò)誤值Yi均為1，因而式(7.4.3)中的sj成為(7.5.15)由加權(quán)冪和對(duì)稱函數(shù)變?yōu)橐话愕?/p>

初等冪和對(duì)稱函數(shù)

。另一方面，由二進(jìn)制BCH碼的校驗(yàn)矩陣特點(diǎn)可知s2j=s2j。由關(guān)鍵方程式(7.5.6)出發(fā)，把它展開并考慮到式(7.5.5)，可得S(x)σ(x)≡1+(s1+σ1)x+(s2+σ1s1+σ2)x2+(s3+s2σ1+s1σ2+σ3)x3+…+(st+σ1st-1+…+σt)xt

(modx2t+1)(7.5.16)由式(7.4.6)和式(7.5.15)可知，有如下的

牛頓恒等式

：

s1-σ1=0

s2-s1σ1+2σ2=0

s3-s2σ1+s1σ2-3σ3=0

…在任意域中成立。所以在GF(2)中上式成為：

s1+σ1=0

s2+σ1s1=0

s3+s2σ1+s1σ2+σ3=0

…(7.5.17)將式(7.5.17)代入式(7.5.16)得

S(x)σ(x)=1+σ2x2+σ4x4+…+σ2tx2t≡ω(x)

(mod

x2t+1)(7.5.18)這說明關(guān)鍵方程的奇數(shù)次項(xiàng)的系數(shù)均為0，僅只有偶次項(xiàng)系數(shù)。基于上式我們不難相信，在二進(jìn)制BCH碼的迭代譯碼過程中有如下特點(diǎn)：(1)ω(i)(x)等于σ(i)(x)的偶部多項(xiàng)式σ(i)e(x)；(2)i為奇數(shù)時(shí)的di=0。為了證明上述兩個(gè)特點(diǎn)，在特征為2的域中引入逆生成函數(shù)R(x)，它定義為

S(x)R(x)=1(7.5.19)

式中，R(x)=1+R1x+R2x2+…，是一個(gè)有常數(shù)項(xiàng)的冪級(jí)數(shù)。我們分別用So和Ro記為S和R的奇次冪部分，用Se和Re記為它們的偶次冪部分。

引理7.5.3

在特征為2的域中，Re=0的充要條件是Se=S2。

證明

將S、R寫成：

S=1+So+Se

R=1+Ro+Re

代入式(7.5.19)展開得(1+So+Se)(1+Ro+Re)=1+Se+Re+SoRo+SeRe+(1+Se)Ro+(1+Re)So=1比較奇偶部分可得：偶部：1+Se+Re+SoRo+SeRe=1奇部：(1+Se)Ro+(1+Re)So=0消去Ro得

Re=(Se+S2)／(1+S2)

所以，若Se=S2，則Re=0；反之若Re=0，則Se=S2。

定理7.5.2

對(duì)二進(jìn)制BCH碼的迭代譯碼算法有：

ω(i)(x)=σ(i)e(x)i=0，1，2，…，2t和

d2k+1=0k=0，1，2，…，t-1表7-9二進(jìn)制BCH碼求σ(x)

表7-10二進(jìn)制［31，11，11］BCH碼求σ(x)迭代過程三、迭代譯碼算法與序列的最短線性反饋移位寄存器綜合及線性復(fù)雜度之間的關(guān)系這里將簡單討論一下求σ(x)的迭代算法，與序列的最短線性反饋移位寄存器(LFSR)綜合及序列的線性復(fù)雜度之間的關(guān)系。由上節(jié)討論可知，要解式(7.5.5)st+1+σ1st+…+σts1=0

st+2+σ1st+1+…+σts2=0…

s2t+σ1s2t-1+…+σtst=0線性方程組可用式(7.5.6)

S(x)σ(x)≡ω(x)(modx2t+1)利用迭代方法求解σ(x)。在上述方程組中，如果已知σ1，σ2，…σt和s1，s2，…，st，則可通過計(jì)算求得st+1，依次類推就可求得st+2，st+3，…，s2t。這個(gè)遞推過程可用圖7-9的電路實(shí)現(xiàn)，與圖5-18比較可知它們完全相同。式(7.5.5)顯然是一組線性遞推關(guān)系式。因此只要在電路中放入初始值s1，s2，…，st，通過移位就可在輸出端得到一組序列s1，s2，…，s2t。現(xiàn)在的問題是已知s1，s2，…，s2t，問電路應(yīng)如何聯(lián)接，并且使用的級(jí)數(shù)最少，才能使輸出的序列為s1，s2，…，s2t。這個(gè)問題就是LFSR的綜合問題，它與BCH碼迭代譯碼求σ(x)的關(guān)系，首先由梅西于１９６９年發(fā)現(xiàn)。從BCH碼譯碼的角度考慮，上述問題就是已知伴隨式s1，s2，…，s2t，如何確定電路的聯(lián)接多項(xiàng)式σ(x)=1+