淺析BCH碼的編碼方法

1、根據(jù)生-表示一個(gè)二進(jìn)制移位寄存器，符號(hào)表示模根據(jù)生-表示一個(gè)二進(jìn)制移位寄存器，符號(hào)表示模2加法器，符號(hào)淺析BCH碼的編碼方法0引言數(shù)字信號(hào)在傳輸系統(tǒng)中傳輸時(shí)，不免會(huì)受到各種因素的干擾，使到達(dá)接收端的數(shù)字信 號(hào)中混有噪聲，從而引發(fā)錯(cuò)誤判決。為了抗擊傳輸過程中的干擾，必然要利用糾錯(cuò)碼的差錯(cuò) 控制技術(shù)。BCH碼是糾錯(cuò)碼中最重要的子類，其具有糾錯(cuò)能力強(qiáng)，構(gòu)造方便，編碼簡(jiǎn)單， 譯碼也較易實(shí)現(xiàn)一系列優(yōu)點(diǎn)，在實(shí)際應(yīng)用中被工程人員廣泛應(yīng)用。BCH 碼BCH碼是1959年由霍昆格姆（Hocquenghem）, 1960年由博斯（Bose）和查德胡里 （Chandhari ）各自提出的糾多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，這是

2、迄今為止發(fā)現(xiàn)的最好的線性分組碼之 一，它有嚴(yán)格的代數(shù)結(jié)構(gòu)，它的糾錯(cuò)能力很強(qiáng)，特別是在短和中等碼長下，其性能接近理論 值，并且構(gòu)造方便編碼簡(jiǎn)單，特別是它具有嚴(yán)格的代數(shù)結(jié)構(gòu)，因此它在編碼理論中起著重要 的作用。BCH碼是迄今為止研究的最為詳盡，分析得最為透徹，取得成果也最多的碼類之 一。該碼的生成多項(xiàng)式與最小距離d之間有密切關(guān)系，根據(jù)d的要求可以很容易地構(gòu)造出碼， 利用該碼的代數(shù)結(jié)構(gòu)產(chǎn)生了多種譯碼方法。BCH碼可以采用查表編碼方法，這是一種利用BCH碼作為線性分組碼和循環(huán)碼的性 質(zhì)和結(jié)構(gòu)特點(diǎn)來編寫編碼表，然后通過查表來編碼的一種方法，也可以采用編碼器進(jìn)行編碼， 還可以應(yīng)用代數(shù)算法，在本文將分別介紹

3、這些算法。BCH碼的n - k級(jí)編碼器J,k） BCH碼是一類循環(huán)碼，它的編碼方法和傳統(tǒng)的循環(huán)碼完全相同，根據(jù)循環(huán)碼的 生成多項(xiàng)式gG）或校驗(yàn)多項(xiàng)式h（x），可推出BCH碼的編碼電路是一個(gè)n - k級(jí)或k級(jí)移存 器電路，在kn-k時(shí)，一般采用n - k級(jí)編碼電路。用于產(chǎn)生系統(tǒng)碼n-k級(jí)編碼器的原理這樣的：將信息多項(xiàng)式 mG）乘以xz成為 xn-km（x），然后用g（x）除xn-km（x）得到余式r（x）, r（x）的系數(shù)就是校驗(yàn)位，因此這可以反饋連接的移位寄存器構(gòu)成的除法電，路完成。見圖1。符號(hào)g, =1，表示連線，若g, =0，表示斷開（對(duì)二進(jìn)制而言）。從圖1可以看出，該n-k級(jí)移位寄存器編

4、碼電路的硬件主要包括:1、n - k級(jí)移位寄存 器（譬如n - k個(gè)觸發(fā)器），2、大約（n - k2個(gè)模2加法器，3、反饋連接中的門電路，4、一個(gè)控制輸出開關(guān)和反饋連接門的時(shí)鐘計(jì)數(shù)電路，可由m級(jí)移位寄存器構(gòu)成（m是使nV2m 的最小整數(shù)）。圖1移位寄存器編碼電路羊3 BCH碼的代數(shù)編碼（1）圖1移位寄存器編碼電路羊3 BCH碼的代數(shù)編碼（1）共軛和最小多項(xiàng)式如果將GFG刀）看成是GF（2）的一個(gè)m階擴(kuò)展，則映射a a 2稱為共軛。共軛是線性的，即整數(shù)，則a的共軛類是包括G k），而不能屬于其他任何一個(gè)更小的域。因子，并且a e GFa的共軛類是序列a,a2,a孵，中取值不同的元素。因此，如果k

5、是滿足a2 = a的最小 ,a2,a211整數(shù)，則a的共軛類是包括G k），而不能屬于其他任何一個(gè)更小的域。因子，并且a e GFa的最小多項(xiàng)式為系數(shù)屬于GF（2）、階數(shù)最低、首項(xiàng)系數(shù)為1且滿足f （a ）= 0的多項(xiàng)式f 1）。f G）在GFG）上是不可約的，但在更大的域GF（m ）中，f G）可以進(jìn)行線性因式分解:f G)= Ga)C-a 式分解:f G)= Ga)C-a 2).(-a 2陣】)(2)如果a是GFGm）中的一個(gè)本原根，則a的最小多項(xiàng)式稱為GF（如果a是GF利用本原多項(xiàng)式可以來構(gòu)造域，通過查表可以發(fā)現(xiàn)f。）= x4 + x +1是GF（2）上的一個(gè)本 原多項(xiàng)式。即f G ）是

6、GF （16）中一個(gè)本原根的最小多項(xiàng)式。通過反復(fù)利用等式a 4 =a+1，可以將每個(gè)冪a i表示為a的一個(gè)次數(shù) 3的多項(xiàng)式。例如:a 11 =a3 +a2 +a，可以得出表（1）：表（1）將GF （16）表示為a的冪，其中a 4 =a+1ia i00001100102010031000400115011061100710118010191010100111111110121111131101141001同理：fG）= x 3 + x +1 是 GF（8） 上一個(gè)本原根的最小多項(xiàng)式。反復(fù)應(yīng)用等式a 3 =a+1，可以將每個(gè)冪a /表示為a的一個(gè)次數(shù) 2的多項(xiàng)式。例如：a 5 =a 3+a 2,

7、可以得出表（2）：表（2） GF（8）中a的冪，其中a3 =a+1ia i0001101021003011411051116101（2）BCH碼生成多項(xiàng)式&）的求法每個(gè)BCH碼都以它的生成多項(xiàng)式gG）為特征。根據(jù)生成多項(xiàng)式的定義知道gG）是碼 中次數(shù)最低的碼多項(xiàng)式，即滿足g（a）= gC3）= = gC如-1 ）= 0的最低次多項(xiàng)式。gG）的系數(shù)在GF(2)中，但是a不同次數(shù)的冪在更大的域GFGm )中。根據(jù)BCH碼的定義，gG) 若以GF(2m)中的元素a,a2,a3,.,a力(為2m 1級(jí)元素)為根，且g(g(x)= m (xm (x).m(x)其中 m G)m(),m (x)分別為 a,

8、a3, ,a2t1 在 GF(2) 上的最小多項(xiàng)式。m (x)在GF(2)上是不可約多項(xiàng)式，但是在更大的域GFGm )中可以分解為：m (x)=(x-a)x a2).( a2.一) i因此，gG)是GFGm)的子集A = a,a3,a5,a2t)在GF(2)上的最小多項(xiàng)式的 乘積。所以，如果定義A中元素的共軛為A* = 12, : p G A,i 0I那么gG)可以表示為：g(x)= n (x p)pe A *即上述文字可以用如下結(jié)論總結(jié)：，其中 a * 是 GF Gm)中 A = 0, a 3, a 5, , a 2，其中 a * 是 GF Gm)中 A = 0, a 3, a 5, , a

9、 2t-1 的 GF (2)-共軛的集合。(3)利用歸納法驗(yàn)證結(jié)論一所描述的求生成多項(xiàng)式方法的正確性可以通過查表的方法來驗(yàn)證所求的生成多項(xiàng)式是否正確。表一給出了n 31的二進(jìn)制 本原BCH碼表，可以根據(jù)此表查出碼長為n，糾正t個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式gG)。nW31的二進(jìn)制本原BCH碼表g (p)nW31的二進(jìn)制本原BCH碼表g (p)(八進(jìn)制表示)%151531313131313131712621166262113 23 721 246745 3551 107657 5423325 313365047 75 2303表中各多項(xiàng)式是以八進(jìn)制形式給出的。比如：3）8 =001011=x3 +

10、 x +1。意指將十進(jìn)制 數(shù)“ 13”轉(zhuǎn)換為八進(jìn)制數(shù)“001011”，即生成多項(xiàng)式g（x）二 X 3 + x + 1。下面通過舉例的方法對(duì)結(jié)論一的正確性進(jìn)行驗(yàn)證：a）考慮當(dāng)m = 3時(shí)，碼長n = 2m -1 = 7，糾正1個(gè)錯(cuò)誤的BCH碼。（m為 3的任意正 整數(shù)）令偵是GF（8）的一個(gè)本原元；則根據(jù)結(jié)論一，生成多項(xiàng)式是集合 A = L, a 3, a 5, .,a如-1 的最小多項(xiàng)式的乘積。/ t = 1:. A = x ）a的共軛類為：a 2i = 0時(shí)，為ai = 1時(shí)，為a 2i = 2時(shí)，為a 4i = 3 時(shí)，為a8 =a8-7 =ai只能取到2因此，A* = ,a2,a4根據(jù)結(jié)

11、論一，維數(shù)是7-4=3。式gG）是a的最小多項(xiàng)式。a的最小多項(xiàng)式：要實(shí)際計(jì)算出gG）,需要式gG）是a的最小多項(xiàng)式。a的最小多項(xiàng)式：g(x)=n (x-&)Pe A*=(x a )x a 2)( a 4)而一致校驗(yàn)多項(xiàng)式為h（x ）= X7 +1 g 1）= X4 + X2 + x +1查表一得碼長為7,糾正一個(gè)錯(cuò)誤的BCH碼的gG）為:g G）=G3）8 =001011 =X 3 + X + 1 可以看出由結(jié)論一的方法計(jì)算出的g G）是正確的。b）考慮碼長為15、糾正2個(gè)錯(cuò)誤的BCH碼。令偵是 GF （16） 的一個(gè)本原元；則根據(jù)結(jié)論一，生成多項(xiàng)式是集合A = 4,a3,a5, ,a21）的

12、最小多項(xiàng)式。因?yàn)閠 = 2，故 A = 4,a3a的共軛類為：a的共軛類為：a 2,i = 0時(shí)，為ai = 1時(shí)，為a 2i = 2時(shí)，為a 4i = 3時(shí)，為a 8i = 4 時(shí)，為 a 16 =ai只能取到3 所以a的共軛類為：,a2,a4,ada 3a 3的共軛類為：a 3x2,i = 0時(shí)，為a 3i = 1時(shí)，為a 6i = 2 時(shí)，為 a 12i = 3 時(shí)，為 a 24 = a 24-15 = a 9所以a3的共軛類為：a3,a6,a12,a9 因此，A* = ,a2,a3,a4,a6,a8,a9,a 12根據(jù)結(jié)論一，維數(shù)是15-8=7。根據(jù)結(jié)論一，生成多項(xiàng)式g G）是a和a

13、3的最小多項(xiàng)式的乘積。利用a 4 =a+1的本原元a的冪來表示GF(16)并利用表(1 )進(jìn)行化簡(jiǎn)，求得a的最小多項(xiàng)式為:g(x)=n (x-p)(a )(a 4)(-a 8)a 3的最小多項(xiàng)式記為一g (x)= g + g x + g x2 + g x3 + g x4 必須滿足 TOC o 1-5 h z 33031323334g ( 3 )= 0。由表(2)，這等價(jià)于 g t)001+ g 11000+ g 1100+ g 11010+330313233g G111M000。 這個(gè)方程組由包含5個(gè)未知數(shù)的4個(gè)齊次方程組成，它的唯一非全零 34解為 t , g , g , g , g =11111,因此 g (x) =x4 + x3 + x2 + x + 1。因此，碼長為3031323334315、糾正2個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式為：g (x )= (4 + x + 1)(4 + x 3 + x 2 + x + 1)。而一致校驗(yàn)多項(xiàng)式為 h(x )= x15 +1 g (x )= x7 + x6 + x4 +1。查表得n = 15,t = 2的生成多項(xiàng)式gG)為:g (x )=(721)8 = 111010001 =x 8 + x 7 + x 6 + x 4 +1 ?？梢姲凑战Y(jié)論一求得的g (x)是正確的。綜上所見，按照結(jié)論