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

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

(6-7)6.2.2BCH碼的生成多項(xiàng)式為了生成一個(gè)能糾正個(gè)錯(cuò)誤的BCH碼，可以從有限域中選取一個(gè)本原元素，那么以為根的上的最低階多項(xiàng)式便是該碼的生成多項(xiàng)式。因?yàn)樯先魏我詾楦亩囗?xiàng)式均可以被的最小多項(xiàng)式整除。因此，生成多項(xiàng)式一定可以被的最小多項(xiàng)式整除，其中，又因?yàn)閼?yīng)為滿足該條件的最低階多項(xiàng)式，于是可得

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

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

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

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

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

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

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

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

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

(6-14)

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

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

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

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

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

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

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

(6-21)如果，則需要對(duì)進(jìn)行修正來(lái)獲得，如下式

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

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

的時(shí)候，有

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

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