【正文】 析。并且循環(huán)碼具有循環(huán)特性，其編譯碼電路，特別是編碼電路易于實(shí)現(xiàn)。 循環(huán)碼的定義 ： 設(shè)有一個(gè) n 重的 k 維子空間 ,VVnk n? ,若對(duì)其中任意一個(gè)? ?, , ,1 2 0 ,V a a a Vn n n k???? ，恒有 ? ?, , , ,1 2 3 0 1 ,V a a a a Vn n n n k??? ? ?，則稱 ,Vnk 為循環(huán)子空間或循環(huán)碼。將碼矢表示成多項(xiàng)式的形式，即碼元多項(xiàng)式 ??Cx為： ? ? 121 2 0nnnnC x C x C x C????? ? ? ? （ ） 其 i次循環(huán)移位所得的碼矢也用多項(xiàng)式表示為： ? ? ? ? 121 2 0i n n in i n i n iC x C x C x C x C??? ? ? ? ?? ? ? ? ? （ ） 由式（ ）乘以 ix 再除以 1nx? 得： ? ?? ? ? ?112 1012111212 1i nix C x C x C x Cii n i n iC x C x Cn n n innxxiCxiiC x C x Cn n n i nx? ? ? ??? ? ? ?? ? ? ? ?? ? ?????? ? ? ? ?? ? ? ? () 由此 可知： ??Cx的 i次循環(huán)移位是 ??Cx乘以 ix 后再除以 1nx? 的余式。在 [, ]nk循環(huán)碼的 2k 個(gè)碼字，取其前 k1位皆為 0的碼字 g(x)(其次數(shù)為 r=nk)，在經(jīng)過 k1次循環(huán)移位后，總共得到 k個(gè)相互獨(dú)立的碼字： ? ? ? ? ? ?1, kg x xg x x g x?可作為碼生成矩陣的 k行，于是得到 ? ?,nk 循環(huán)碼的生成矩陣 ??Gx： ? ?? ?? ?? ?? ?12kkx g xx g xGxxg xgx????????????? () 碼的生成矩陣一旦確定，碼就可以確定。每一個(gè)碼多項(xiàng)式都是 ??gx的倍式，每一個(gè)是 ??gx倍式且次 數(shù)≤ n1的多項(xiàng)式都是碼多項(xiàng)式。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 6 BCH 碼 自 1950年漢明發(fā)表了糾正單個(gè)錯(cuò)誤的碼以來，幾乎過了 10年的時(shí)間，才于 1959年由霍昆格姆（ Hocquenghem）， 1960年由博斯 (Bose)和雷一查得胡里（ RayChaudhuri）分別提出了糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼 — BCH碼的構(gòu)造方法。特別是它具有嚴(yán)格的代數(shù)結(jié)構(gòu)，因此它在編碼理論中起著重要的作用。 1960年彼得遜伊（ Peterson）從理論上解決了二進(jìn)制 BCH碼的譯碼算法，奠定了 BCH碼譯碼的理論基礎(chǔ)。 1966年伯利坎譜（ Berlekamp）利用迭代法譯碼 BCH碼，從而大大地提高了譯碼速度，從實(shí)際上解決了 BCH碼的譯碼問題。若碼元取自 ? ?GFq 上的一個(gè)循環(huán)碼，它的生成多項(xiàng)式 ??gx的根集合 R中含有以 1?? 個(gè)連續(xù)根，則由 ??gx生成的循環(huán)碼稱為 q進(jìn)制 BCH碼。因?yàn)榇a元符號(hào)取自二元域 ? ?2GF 、糾 t個(gè)錯(cuò)誤的二元 BCH碼的生成多項(xiàng)式是以 ? ?2GF 的擴(kuò)域 ? ?2mGF 上 2t個(gè)相鄰元素為根的多項(xiàng)式。由 ? ?gx確定的 BCH碼是 q元本原 BCH碼。下面將討論 RS碼。在同樣編碼冗余度下 ,RS 碼具有最強(qiáng)的糾錯(cuò)能力。RS碼是非二進(jìn)制循環(huán)碼 ,每一個(gè)碼元由 m個(gè)比特構(gòu)成 ,m是大于 2的任意正整數(shù) .只有所有的 n和 k都滿足 以下條件時(shí)， m比特碼元的 ? ?,RS nk 碼才存在。 對(duì)于大多數(shù)? ?,RS nk 碼 ? ? ? ?, 2 1,2 1 2mmn k t? ? ? ? () 其中 ,t是 RS碼能夠糾正的錯(cuò)誤碼元個(gè)數(shù) , 2n k t?? 是監(jiān)督碼元個(gè)數(shù)。對(duì)任何相同輸入輸出分組長(zhǎng)度的線性編碼 , 里德索羅蒙碼可以達(dá)到最大可能的碼元最小距離。里德 索羅蒙碼最小碼本距離為 min 1d n k? ? ? () 這種編碼可以糾正少于 t的任意多個(gè)錯(cuò)誤組合。上式表明 ,對(duì)于 RS碼 ,糾正 t個(gè)錯(cuò)誤需要不超過 2t個(gè)的監(jiān)督碼元。對(duì)于每個(gè)錯(cuò)誤，一個(gè)冗余碼元用于定位此錯(cuò)誤，另一個(gè)用于找到其正確的取值。 RS碼的編碼原理分為時(shí)域編碼和頻域編碼 2種，本文中僅討論時(shí)域編碼。域 :非空元素集合 Q，若在 Q 中定義了加和乘兩種運(yùn)算且滿足下述公理： 1） Q 關(guān)于加法構(gòu)成阿貝爾群，其加法恒等元（單位元）記為 0。其乘法恒等元 (單位元 )記為 1。域中元素的個(gè)數(shù)為域的階。有限域也稱為伽羅華域，在編碼理論中起著非常重要的作用?？梢詫?GF(q)延伸為一個(gè)含有 mq 個(gè)元素的域，這稱為 GF(q)的擴(kuò)展域，表示為 GF( mq ),m 是一個(gè)非零正整數(shù)。擴(kuò)展域 GF( mq )中的碼元用于構(gòu)造 RS 碼。除了數(shù)字 0和 1，在擴(kuò)展域中還有特殊的元素，用一個(gè)新的符號(hào) a表示。元素的無限集 G， 就是根據(jù)元素 {0,1,a}而形成的，后一個(gè)元素通過前一項(xiàng)乘以 a而得 : ? ? ? ?2 3 0 1 2 30 , 1 , , , , 0 , , , , ,nnG a a a a a a a a a?? （ ） 為了從 G中得到有限元素的集合 GF(2n )，必須對(duì) G域施加一個(gè)條件，使它只能含有 2n 個(gè)元素，并且對(duì)乘法封閉。 有限域的本原多項(xiàng)式 ： 有限域 GF(2m )可用一組本原多項(xiàng)式來定義，有 限域是定義 RS碼所必需的，所以研究RS 碼須研究本原多項(xiàng)式。如果 f(x)能整除 1nx? 的最小整數(shù) n，其中 21mn??，則該多項(xiàng)式是本原多項(xiàng)式。 表 31中列舉了一些常用的本原多項(xiàng)式。 (2)在 [n,k]循環(huán)碼中，每個(gè)碼字多項(xiàng)式 C(x)都是 g(x)的倍式，而每個(gè)為 g(x)倍式 且次數(shù) (n1)的多項(xiàng)式必為一個(gè)碼字多項(xiàng)式。 (4)若 g(x)是一個(gè) (nk)次多項(xiàng)式，且為 1nx? 的因式，則由 g(x)可以生成一個(gè) [nk]循環(huán)碼。 例如， 電路產(chǎn)生了域中的 ? ?2 1 3m m??個(gè)非 0 的域元素 ,注意在 圖 31中線路反饋連接是與 本源 多項(xiàng)式 ? ? 31f x x x? ? ? 的系數(shù)相對(duì)應(yīng)的，類似于二進(jìn)制循環(huán)碼的情況。兩種算術(shù)運(yùn)算即加法和乘法可以用來定義這個(gè) GF( 32 )有限域。 表 32 GF( 32 )域中的元素映射表 指數(shù)形式 二進(jìn)制形式 十進(jìn)制形式 0? 001 1 1? 010 2 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 10 2? 100 4 3? 011 3 4? 110 6 5? 111 7 6? 101 5 7? 001 1 根據(jù) 圖 31可以 通過 c 語言 求出在域 GF(32 )中的所有元素。 int i。i=6。 else GF[i+1]=((GF[i]1)amp。 } for(i=0。i++) printf(%d\n,GF[i])。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 11 圖 32 GF( 32 )域十進(jìn)制元素生成 圖 32中所示的 7 位十進(jìn)制數(shù)字就是 GF(32 )域中的十進(jìn)制形式的元素。這里以? ?32GF 為準(zhǔn)。 ． 有限 域 GF(2m )中的加法 有限域中兩個(gè)元素的加 法定義為兩個(gè)多項(xiàng)式中同冪次項(xiàng)系數(shù)進(jìn)行模 2 加，即 ? ? ? ? ? ? 1. 0 . 0 . 1 . 1 . 1 . 1i j mi j i j i m j ma a a a a a x a a x ???? ? ? ? ? ? ? ? （ ） 已知 GF(2m )上的 兩個(gè)多項(xiàng)式 ? ? 1 2 11 2 1 0nnnnA x a x a x a x a????? ? ? ? ? ? ? 1 2 11 2 1 0nnnnB x b x b x b x b????? ? ? ? ? 由 有限域中兩個(gè)元素的加法定義 得兩多項(xiàng)式相加 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 12 11 1 1 1 0 0( ) ( ) ( ) ( ) ( ) ( )nnnC x A x B x a b x a b x a b???? ? ? ? ? ? ? ? ? （ ） 121 2 1 0nnnnc x c x c x c????? ? ? ? ? 其中 。 有限 域 GF(2m )中的乘法 為 了找到一種遵守有限域內(nèi)全部乘法性質(zhì)的多項(xiàng)式乘法，將構(gòu) 成一個(gè)元素 為 mq 的有限域。只要該乘積是一個(gè)次數(shù)等于或低于 m1 的多項(xiàng)式，就可以滿足這一要求。這里所需要的 m次固定多項(xiàng)式就是本原多項(xiàng)式 q(x)。一般地說，系數(shù)取自 GF(q)的不可約多項(xiàng)式在 GF(q)中無根，但在擴(kuò)張域 GF( mq )內(nèi)有根。在有限域GF(2m )中， 2m 個(gè)元素中的任意一個(gè)都可由階數(shù)小于或等于 m1 的不同多項(xiàng)式來表示。當(dāng) m=3 時(shí)，有限域表示為 GF(32 )。 GF(32 )是 GF(2)的擴(kuò)展域， GF(32 )中 8個(gè)元素都可以用 GF(2)中的兩個(gè)元素 0， 1組合來表示，例如 100， 110， 011等等。 有限域中的乘法運(yùn)算規(guī)則是把兩個(gè)元素表示 成指數(shù)形式，將指數(shù)直接相加取模 21m? ，如下式所示： ? ? ? ?m od 2 1mijija a a ???? （ ） RS 碼定義在有限域上 ,其編碼譯碼運(yùn)算都是有限域上的算術(shù)運(yùn)算。乘法器按實(shí)現(xiàn)方法分為比特串行乘法器和比特并行乘法器 兩種，比特串行乘法器的硬件實(shí)現(xiàn)比較簡(jiǎn)單 ,但是由于運(yùn)算逐比特進(jìn)行 ,實(shí)現(xiàn)高速的難度較大 ,不易達(dá)到較高的吞吐率。所謂比特并行乘法器 是指通過連接 ,直接實(shí)現(xiàn)輸出結(jié)果的多位運(yùn)算 , 最后結(jié)果并行輸出 ,這樣可以顯著提高處理速度。 現(xiàn)以乘 2? 為例， 說明八進(jìn)制常乘器的組成， GF(32 )中每個(gè)元素都可表示成它 的自然基底 21 ??， ， 的線性組合 ： 22 1 0a1aa????， 再乘以 2? 后，則 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 13 ? ? ? ? ? ?? ? ? ?2 2 4 3 2 2 22 1 0 2 1 0 2 1 0222 0 2 1 1 2 1 0a 1 1a a a a a a a aa a a a a a a a? ? ? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ? 式中 2 2 01 2 101a a aa a aaa???????? 所以，乘 2? 電路如下圖 33 所示 0a? 1a? 2a? 1a 2a 0a 圖 33 乘 2? 電路 用 c 語言實(shí)現(xiàn) 有限域 GF( 32 )中乘法器源程序代碼如下 include int MUL(a， b) {int i,j,k,n,m。 for(i=0。i++)//生成 GF[2]域 // {if(GF[i]=3) GF[i+1]=GF[i]1。7)^3。n=6。} for(m=0。m++) {if(GF[m]==b) 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 14 j=m。kj。 else a=((a1)amp。 } return a。 scanf(%d %d,amp。y)。 printf(%d\n,z)。 圖 34 有限域 GF( 32 )中 4*6的運(yùn)算結(jié)果 通過圖 34可以看出，當(dāng)輸入十進(jìn)制數(shù) 4 和 6 時(shí)，表示在 GF(32 )域中作 4*6 的運(yùn)算，結(jié)果輸出為 5，運(yùn)算結(jié)果正確 。每個(gè)符號(hào)表示 m比特 ,可糾 t=(d1) 2個(gè)錯(cuò)誤。所以編碼的關(guān)鍵是首先得出生成矩陣 G, 而且為了得到某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 16 G, 必須首先找到生成多項(xiàng)式 g(x)。它由兩個(gè)步驟構(gòu)成 , 首先完成每次移位時(shí)校驗(yàn)元的求解 , 然后完成碼元的移位。設(shè)系統(tǒng)碼的多項(xiàng)式 ? ? 11 1 0nC x c x c x ?? ? ? ?? （ ） 其前 k 1c nk? ? 位系數(shù)是已知的信息位 ,后 nk位系數(shù) 0ck? 是需求的校驗(yàn)元 ,C(x)為 g (x)倍式 , 即 ? ? ? ? ? ?C x q x g x? , 而 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1nnh x C x q