信息與編碼理論 第2版 課件 6.2 BCH碼

§6.2BCH碼6.2.1BCH碼的結(jié)構(gòu)BCH碼是一種循環(huán)碼，因此也可以用生成多項式來描述。接下來介紹一種被稱作本原二進制BCH碼（PrimitiveBinaryBCHCode）的編碼和譯碼方法。碼長為，其中整數(shù)。對于任意的，這種碼可以糾正不少于個錯誤。實際上，對于任意兩個正整數(shù)和，均可以設(shè)計一個參數(shù)滿足下列關(guān)系的BCH碼：

(6-7)6.2.2BCH碼的生成多項式為了生成一個能糾正個錯誤的BCH碼，可以從有限域中選取一個本原元素，那么以為根的上的最低階多項式便是該碼的生成多項式。因為上任何以為根的多項式均可以被的最小多項式整除。因此，生成多項式一定可以被的最小多項式整除，其中，又因為應(yīng)為滿足該條件的最低階多項式，于是可得

(6-8)另外，考慮到共軛類中元素的最小多項式相同，故在確定生成多項式時僅考慮奇數(shù)值的就夠了，于是

(6-9)因為最小多項式的階不會超過，于是的階最多為，所以假設(shè)是BCH碼的任一碼字多項式，那么根據(jù)循環(huán)碼的性質(zhì)可知該碼的生成多項式將是一個因式，故對應(yīng)于的所有都將是的根，

(6-10)這是判斷一個階小于的多項式是否為一個合法BCH碼字多項式的充要條件。【例6-6】設(shè)計一個能夠糾正單個錯誤的BCH碼，要求碼長?！窘狻坑深}意可知，。選取上的一個本原元素，則由例6-5的結(jié)果可知的最小多項式為，顯然該式是一個階為4的本原多項式。于是，該BCH碼的生成多項式為

由上式可知，。因為對于BCH碼有，而觀察上式后可知對應(yīng)碼字向量的重量為3，所以可確定。綜上，該BCH碼是一個可以糾正1個錯誤的碼，其最小碼距為3，實際上該碼是一個循環(huán)漢明碼（CyclicHammingCode）。一般而言，循環(huán)漢明碼是可以糾正單個錯誤的BCH碼?！纠?-7】設(shè)計一個能夠糾正四個錯誤的BCH碼，要求碼長?！窘狻坑深}意可知，。仍然假設(shè)是上的一個本原元素，那么由例6-5的結(jié)果可知，，，的最小多項式分別為因此生成多項式為

由上式可知，，該碼的最小碼距。因此該BCH碼是一個重復(fù)碼（RepetitionCode）。該BCH碼是按照糾正4個錯誤來設(shè)計的，但實際上該碼可以糾正最多7個錯誤?！纠?-8】設(shè)計一個能夠糾正兩個錯誤的BCH碼，要求碼長?！窘狻坑深}意可知，。仍設(shè)表示上的一個本原元素，且由例6-5的結(jié)果可知和的最小多項式分別為因此，該BCH碼的生成多項式為

由上式可知，。因為對于BCH碼有，而觀察上式可知對應(yīng)的碼字向量的重量為5，所以可確定。6.2.3BCH碼的譯碼設(shè)碼字向量對應(yīng)的碼字多項式為，則對于均有。如果傳輸過程中的錯誤多項式為，那么接收多項式為

(6-11)于是，可以將與上式對應(yīng)的伴隨式定義為

(6-12)該伴隨式可以通過對接收向量使用域運算來計算得到。如果傳輸過程中沒有發(fā)生錯誤，那么，則伴隨式為零。假設(shè)在碼字向量的傳輸過程中共有個錯誤發(fā)生，且，其中是該碼的糾錯能力，將這些錯誤的具體位置分別記作。不失一般性，假設(shè)，于是

(6-13)將式(6-13)帶入式(6-12)，可得

(6-14)

(6-14)式(6-14)給出的方程組中共有個方程，以及個未知數(shù)：或者是等效的通過解該方程組便可以求得個未知數(shù)，進而可得錯誤位置。一旦得到錯誤位置，便可以對應(yīng)修改這些位置的接收比特從而得到發(fā)射碼字的估計值。定義為錯誤位置數(shù)（ErrorLocationNumber），其中，則式(6-14)可以改寫為

(6-15)通過解該方程組可以求得個未知數(shù)，于是可以進一步確定個錯誤位置。由于是中的元素，故在解上面方程組時應(yīng)使用內(nèi)的運算規(guī)則。為了解方程組，定義錯誤定位多項式（ErrorLocatorPolynomial）為

(6-16)顯然，上式的根為，，求解該多項式的根即可確定錯誤的位置。將式(6-16)展開之后可得

(6-17)利用式(6-15)和式(6-17)，可得的系數(shù)與伴隨式之間的關(guān)系如下

(6-18)接下來，需要求得系數(shù)滿足上面這些方程的最低階多項式。在確定之后，便可以求得其根，再由這些根的逆即可得到錯誤的位置。求根時，可以將中所有個元素分別代入進行驗證。6.2.4BCH碼的Berlekamp-Massey譯碼算法BM迭代譯碼算法首先找到滿足式(6-18)中第一個等式的最低階多項式，然后驗證其是否也滿足第二個等式，并根據(jù)驗證結(jié)果分別做如下處理：如果滿足第二個等式，則記；如果不滿足第二個等式，則引入一個修正項從而得到，使其為滿足前兩個等式的最低階多項式；重復(fù)該過程，直到獲得一個同時滿足式(6-18)中所有等式的最低階多項式。假設(shè)下式表示滿足式(6-18)中前個等式的最低階多項式

(6-19)為了確定，可以計算求得第個偏差（Discrepancy），如下式

(6-20)如果，表明滿足前個等式，于是有

(6-21)如果，則需要對進行修正來獲得，如下式

(6-22)式中，且其選擇原則為滿足的所有中使得值最大的那個，其中表示的階。這樣得到的是滿足式(6-18)中前個等式的最低階多項式。重復(fù)該過程直到獲得，該多項式的階就是錯誤比特的個數(shù)，其根可以用來確定錯誤的位置。如果的階大于，則表明接收向量中錯誤個數(shù)多于，此時不能進行糾正。綜上，Berlekamp-Massey譯碼算法的初始條件如表6-7所示，然后可以按照上述方法來迭代進行。表6-7Berlekamp-Massey算法【例6-9】考慮例6-8中可以糾正2個錯誤的BCH碼，并利用Berlekamp-Massey算法對下列接收向量進行譯碼【解】該接收向量對應(yīng)的接收多項式為，于是可得伴隨式為

在上面4個伴隨式的計算過程中用到了表6-6中的結(jié)論。接下來，便可以按照表6-7中給出的Berlekamp-Massey算法來進行譯碼。當(dāng)?shù)臅r候，由表6-7可得當(dāng)?shù)臅r候，有當(dāng)

的時候，有

當(dāng)?shù)臅r候，有綜上，可知

觀察上式，可知錯誤定位多項式的階為2，表示接收向量中有2位錯誤，所以對應(yīng)了一個可以糾正的錯誤圖樣，因此只需要求得該多項式的根便可以得到