淺析BCH碼的編碼方法

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

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

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

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

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

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

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

8、a3, ,a2t1 在 GF(2) 上的最小多項式。m (x)在GF(2)上是不可約多項式，但是在更大的域GFGm )中可以分解為：m (x)=(x-a)x a2).( a2.一) i因此，gG)是GFGm)的子集A = a,a3,a5,a2t)在GF(2)上的最小多項式的 乘積。所以，如果定義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)利用歸納法驗證結(jié)論一所描述的求生成多項式方法的正確性可以通過查表的方法來驗證所求的生成多項式是否正確。表一給出了n 31的二進制 本原BCH碼表，可以根據(jù)此表查出碼長為n，糾正t個錯誤的BCH碼的生成多項式gG)。nW31的二進制本原BCH碼表g (p)nW31的二進制本原BCH碼表g (p)(八進制表示)%151531313131313131712621166262113 23 721 246745 3551 107657 5423325 313365047 75 2303表中各多項式是以八進制形式給出的。比如：3）8 =001011=x3 +

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

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

12、最小多項式。因為t = 2，故 A = 4,a3a的共軛類為：a的共軛類為：a 2,i = 0時，為ai = 1時，為a 2i = 2時，為a 4i = 3時，為a 8i = 4 時，為 a 16 =ai只能取到3 所以a的共軛類為：,a2,a4,ada 3a 3的共軛類為：a 3x2,i = 0時，為a 3i = 1時，為a 6i = 2 時，為 a 12i = 3 時，為 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é)論一，生成多項式g G）是a和a

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