【文章內(nèi)容簡(jiǎn)介】 于加法構(gòu)成阿貝爾群，其加法恒等元（單位元）記為 0。 2） Q 中非零元素全體對(duì)乘法構(gòu)成阿貝爾群。其乘法恒等元 (單位元 )記為 1。 3）加法和乘法間有如下分配律 : ? ?? ? ? ?? ??? ? ? （ ） ? ?? ? ? ?? ??? ? ? （ ） 則稱 Q是一個(gè)域。域中元素的個(gè)數(shù)為域的階。 元素個(gè)數(shù)有限的域稱有限域，用 GF(q)表示 q 階有限域。有限域也稱為伽羅華域，在編碼理論中起著非常重要的作用。有限域的一個(gè)重要性質(zhì)是每個(gè)有限域 GF(q)至少要包含一個(gè)叫做 a的本原元素，它能生成該域中的每個(gè)元素?？梢詫?GF(q)延伸為一個(gè)含有 mq 個(gè)元素的域，這稱為 GF(q)的擴(kuò)展域，表示為 GF( mq ),m 是一個(gè)非零正整數(shù)。 GF(q)是 GF(mq )的子集。擴(kuò)展域 GF( mq )中的碼元用于構(gòu)造 RS 碼。二進(jìn)制域 GF(2)是 GF(2n )的一個(gè)子域，類似于實(shí)數(shù)是復(fù)數(shù)的一個(gè)子域一樣。除了數(shù)字 0和 1，在擴(kuò)展域中還有特殊的元素，用一個(gè)新的符號(hào) a表示。 GF(2n )中任何非零元素都可以由 a 的冪次表示。元素的無(wú)限集 G， 就是根據(jù)元素 {0,1,a}而形成的，后一個(gè)元素通過(guò)前一項(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ì)乘法封閉。域元素對(duì)乘法封閉的條件可由下面的不可約多項(xiàng)式表示 : ? ?2110ma ? ??即 ? ?21 01maa? ?? （ ） 根據(jù)這個(gè)多項(xiàng)式限制條件，任何冪次等于或超 21m? 的域元素都可降階為如下表示 的冪次小于 21m? 的元素。 有限域的本原多項(xiàng)式 ： 有限域 GF(2m )可用一組本原多項(xiàng)式來(lái)定義，有 限域是定義 RS碼所必需的，所以研究RS 碼須研究本原多項(xiàng)式。本原多項(xiàng)式可定義為 :一個(gè) m 階的不可約多項(xiàng)式 f(x)。如果 f(x)能整除 1nx? 的最小整數(shù) n，其中 21mn??，則該多項(xiàng)式是本原多項(xiàng)式。不可約多項(xiàng)式是指一個(gè)多項(xiàng)式不能因式分解為更低冪次的多項(xiàng)式， B整除 A 是指 A除以 B 得到非 0 商并且余數(shù)為 0。 表 31中列舉了一些常用的本原多項(xiàng)式。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 9 表 3— 1常用本原多項(xiàng)式 M 本原多項(xiàng)式 2 21 XX?? 3 31 XX?? 4 41 XX?? 5 261 XX?? 6 61 XX?? 7 371 XX?? 8 2 3 4 81 X X X X? ? ? ? 本原多項(xiàng)式 g(x)具有以下的性質(zhì) : (1)在 [n,k]循環(huán)碼中，生成多項(xiàng)式 g(x)是唯一的 (nk)次多項(xiàng)式，且次數(shù)是最低 的。 (2)在 [n,k]循環(huán)碼中，每個(gè)碼字多項(xiàng)式 C(x)都是 g(x)的倍式，而每個(gè)為 g(x)倍式 且次數(shù) (n1)的多項(xiàng)式必為一個(gè)碼字多項(xiàng)式。 (3)[n,k]循環(huán)碼的生成多項(xiàng)式 g(x)是 1nx? 的因式，即 ? ? ? ?1nx h x g x?? 。 (4)若 g(x)是一個(gè) (nk)次多項(xiàng)式，且為 1nx? 的因式，則由 g(x)可以生成一個(gè) [nk]循環(huán)碼。 本文設(shè)計(jì)的是 RS(7,3)碼編碼器，由表 31可 以查出本原多項(xiàng)式是： ? ? 31f x x x? ? ? ， 用 本源 多項(xiàng)式表示的基本元素可映射為域元素 圖 (LFSR)電路的形式。 例如， 電路產(chǎn)生了域中的 ? ?2 1 3m m??個(gè)非 0 的域元素 ,注意在 圖 31中線路反饋連接是與 本源 多項(xiàng)式 ? ? 31f x x x? ? ? 的系數(shù)相對(duì)應(yīng)的，類似于二進(jìn)制循環(huán)碼的情況。置線路初始狀態(tài)非零，例如為 100，每個(gè)時(shí)鐘實(shí)現(xiàn)一次右移，可以證明， 圖 31 中所示的每個(gè)域元素 (除了全 0元素 )將周 期性地出現(xiàn)在移位寄存器的狀態(tài)上。兩種算術(shù)運(yùn)算即加法和乘法可以用來(lái)定義這個(gè) GF( 32 )有限域。 0X 1X 2X 3X 圖 31由本源多項(xiàng)式表示的基本元素映射為域元素的電路 根據(jù)本源多項(xiàng)式可得 GF( 32 )域元素表如 表 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可以 通過(guò) c 語(yǔ)言 求出在域 GF(32 )中的所有元素。 源程序代碼如下： include void main() { int GF[7]={1}。 int i。 for(i=0。i=6。i++) {if(GF[i]=3) GF[i+1]=GF[i]1。 else GF[i+1]=((GF[i]1)amp。7)^3。 } for(i=0。i=6。i++) printf(%d\n,GF[i])。 } 程序運(yùn)行結(jié)果 圖 32。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 11 圖 32 GF( 32 )域十進(jìn)制元素生成 圖 32中所示的 7 位十進(jìn)制數(shù)字就是 GF(32 )域中的十進(jìn)制形式的元素。 有限域元素運(yùn)算 了解了有限域后，看看如何用 高級(jí)語(yǔ)言編寫 出有限域上的加法器和乘法器。這里以? ?32GF 為準(zhǔn)。可以看出，多項(xiàng)式加法器的實(shí)現(xiàn)比較簡(jiǎn)單，可以直接將 2 個(gè)多項(xiàng)式對(duì)應(yīng)的系數(shù)異或即可， 而多項(xiàng)式乘法器的實(shí)現(xiàn)比較復(fù)雜 ，這里重點(diǎn)介紹 用 高級(jí)語(yǔ)言編寫出有限域上的 乘法器 原理和方法 。 ． 有限 域 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????? ? ? ? ? 其中 。 0 , 1 , 2 , , 1i i ic a b i n? ? ? ? 若為 A(x)B(x)，則只要把 B(x)系數(shù)以 GF(2m )中的加法逆元代替得到 B(x)，再作 B(x)+ A(x)運(yùn)算即可，在二進(jìn)制情況下“ ”與“ +”運(yùn)算相同，以此相加和相減的運(yùn)算結(jié)果一樣。 有限 域 GF(2m )中的乘法 為 了找到一種遵守有限域內(nèi)全部乘法性質(zhì)的多項(xiàng)式乘法，將構(gòu) 成一個(gè)元素 為 mq 的有限域。首先，我們要求在一個(gè)集合內(nèi)的任何兩個(gè)多項(xiàng)式之積是本集合中的另一個(gè)多項(xiàng)式，以滿足封閉性。只要該乘積是一個(gè)次數(shù)等于或低于 m1 的多項(xiàng)式，就可以滿足這一要求。對(duì)于次數(shù)等于或大于 m的乘積多項(xiàng)式，可以取它相對(duì)于一個(gè) m次固定多項(xiàng)式的余項(xiàng)多項(xiàng)式。這里所需要的 m次固定多項(xiàng)式就是本原多項(xiàng)式 q(x)。它的最高次冪為 m，而系數(shù)在 GF(q)上，它是不可約多項(xiàng)式。一般地說(shuō)，系數(shù)取自 GF(q)的不可約多項(xiàng)式在 GF(q)中無(wú)根，但在擴(kuò)張域 GF( mq )內(nèi)有根。具體說(shuō)， m次 q(x)在擴(kuò)張域 GF( mq )內(nèi)必有 m個(gè)根。在有限域GF(2m )中， 2m 個(gè)元素中的任意一個(gè)都可由階數(shù)小于或等于 m1 的不同多項(xiàng)式來(lái)表示。多項(xiàng)式的階數(shù)是它的最高冪指數(shù)。當(dāng) m=3 時(shí)，有限域表示為 GF(32 )。由于 07aa? ，所以在該域中有 7個(gè)非零元素，或者說(shuō)總共 7個(gè)元素。 GF(32 )是 GF(2)的擴(kuò)展域， GF(32 )中 8個(gè)元素都可以用 GF(2)中的兩個(gè)元素 0， 1組合來(lái)表示，例如 100， 110， 011等等。 擴(kuò)展域元素代替二進(jìn)制元素的一個(gè)好處就是表達(dá)的緊密性，使得非二進(jìn)制編碼和譯碼過(guò)程的數(shù)學(xué)表示變得簡(jiǎn)單。 有限域中的乘法運(yùn)算規(guī)則是把兩個(gè)元素表示 成指數(shù)形式，將指數(shù)直接相加取模 21m? ，如下式所示： ? ? ? ?m od 2 1mijija a a ???? （ ） RS 碼定義在有限域上 ,其編碼譯碼運(yùn)算都是有限域上的算術(shù)運(yùn)算。在有限域的各種算術(shù)運(yùn)算中 ,乘法研究最多。乘法器按實(shí)現(xiàn)方法分為比特串行乘法器和比特并行乘法器 兩種，比特串行乘法器的硬件實(shí)現(xiàn)比較簡(jiǎn)單 ,但是由于運(yùn)算逐比特進(jìn)行 ,實(shí)現(xiàn)高速的難度較大 ,不易達(dá)到較高的吞吐率。在高速應(yīng)用時(shí)一般考慮用比特并行乘法器。所謂比特并行乘法器 是指通過(guò)連接 ,直接實(shí)現(xiàn)輸出結(jié)果的多位運(yùn)算 , 最后結(jié)果并行輸出 ,這樣可以顯著提高處理速度。 在 ? ?m2GF 域中 , 兩個(gè)以自然基表示的元素直接相乘時(shí) ,約需要 3mm? 個(gè)模 2 加法器 , 這樣實(shí)現(xiàn)的電路復(fù)雜度較高 , 而且缺乏規(guī)范性 , 因此一般釆用對(duì)偶基下的乘法器。 現(xiàn)以乘 2? 為例， 說(shuō)明八進(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 語(yǔ)言實(shí)現(xiàn) 有限域 GF( 32 )中乘法器源程序代碼如下 include int MUL(a， b) {int i,j,k,n,m。 int GF[7]={1}。 for(i=0。i=6。i++)//生成 GF[2]域 // {if(GF[i]=3) GF[i+1]=GF[i]1。 else GF[i+1]=((GF[i]1)amp。7)^3。 } for(n=0。n=6。n++) { if(GF[n]==a) i=n。} for(m=0。m=6。m++) {if(GF[m]==b) 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 14 j=m。} for(k=0。kj。k++) {if(a=3) a=a1。 else a=((a1)amp。7)^3。 } return a。 } main() { int x,y,z。 scanf(%d %d,amp。x,amp。y)。 z=MUL(x,y)。 printf(%d\n,z)。 } 有限域 GF( 32 )中 4*6 的 運(yùn)行結(jié)果 如圖 34 所示 。 圖 34 有限域 GF( 32 )中 4*6的運(yùn)算結(jié)果 通過(guò)圖 34可以看出，當(dāng)輸入十進(jìn)制數(shù) 4 和 6 時(shí)，表示在 GF(32 )域中作 4*6 的運(yùn)算，結(jié)果輸出為 5，運(yùn)算結(jié)果正確 。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 15 4 RS(7,3)碼的編碼 器設(shè)計(jì) RS 碼的編碼原理 生成多項(xiàng)式的求解 GF(2m )域上 RS碼一般寫成 (n,k)形式 ,其中 n為碼長(zhǎng) n=2m 1,k為信息位的長(zhǎng)度 ,碼的最小距離 d=nk+ 1。每個(gè)符號(hào)表示 m比特 ,可糾 t=(d1) 2個(gè)錯(cuò)誤。 設(shè) A為