TWI253011B - Galois field multiplier and multiplication method thereof - Google Patents

Description

I253QU 6twf.doc/m 九、發明說明： 【發明所屬之技術領域】 本發明是有關於一種乘法器及 且特別是有關於-種於加羅瓦域之乘法的/法， 方法。 〈不去為及其計算乘法的 【先前技術】 ，著=工業在半導體技術上的不斷地演進 產/:已朝向提升處理速度以及多雜化等方向邁進。在電 1統中，邏輯處理元件（例如巾域理器）以及記憶體 之處理速度亦在此一趨勢之下不斷地提升。 〜 然而，在電腦系統中除了邏輯處理元件以及 之處理速度影響著電腦系統之運作效率外，存取裳置^ 如硬碟）的存取速度亦是影響電腦系統之運作效率的重要 因素之一。由於存取裝置無法突破自身的技術障礙來提升 其存取速度，使得其存取速度仍無法與中央處理器以及記 憶體之處理速度配合，因而造成電腦系統的整體效能無法 有效地提升。 為了提升電腦系統中存取裝置的存取速度，習知技 術提出一種磁碟陣列（Redundant Array of Independent Disks，RAID)的方法。磁碟陣列係將多個次存取裝置組 合為一個存取裝置。當存取裝置進行資料的存取時，資料 會被分割成多個部分，之後同時且平行地存取於多個次存 取裝置内。因此磁碟陣列能提供較快速的存取速度。除此

I253QU 之外’為了避免存取之資料發生錯誤，磁 ^^^(parity 壞㈣之f料往往會因為磁執的損 因素而發生錯誤，因此當資料儲存於 置都需要經過—種編碼的程序。如此 於存取裝置内部之㈣發生錯誤時，錯誤 设的可能。為了能夠在一串資料中 —細峨峰^ΓΓ電 ))之數车特性的乘法器將資料進行編碼與解碼。 以利用三階原始多項式（primitive polynimiai): 一 1 + J； + /，所建立之加羅瓦域GF (23)為例，若“為 ς階多項式之一個根，則在此一加羅瓦域GF (23) Ϊ所 進仃的0^與的運算將為： “4 + 5 ·α5 一 ~ a w w 二 a 由此運异式可知習知利用加羅瓦域gf (2m)之數學特性 2行的編碼過程需要闕_的運算，目此其乘法器之 ’、路通常都十分地娜並且其運算_亦十分地耗時。 【發明内容】 谨管^明的目的就是在提供—種簡化運算電路並縮短 #日$程之於加羅瓦域之乘法器。 ^發明的再—目的是提供—種簡化運算電路並縮短 V寺私之於加羅瓦域計算乘法的方法。 6twf.doc/m 本發明提出一種於加羅瓦域之乘法器，此結構係包 括一查表裝置以及一運算電路。其中，查表裝置係根據一 乘數S ’自一乘數係數表查表而得一係數矩陣W，而乘數 S係屬於一加羅瓦域GF(2m)，s表示為L〜―2…〜]， W表示為：

W w-1,0

m-2,Q V0,0 V〇,/77-l 運"^"'電路係耦接至查表裝置，用以接受一被乘數A以及 係數矩陣W，並加以運算而得一積R，被乘數a與積r 係同屬於一加羅瓦域GF ( 2m )，其中A表示為 k'，—2 ··· a°]’R表示為k…〜]，且 + wm^m_2a^2 +... + w A 〜〜+MWV2 +. ·· + '〇% =中之付嬈+為做一邏輯互斥或運算（1〇gicalx〇R)，WA 糸為對^與aj做一邏輯及運算（logicalAND)。 哭，^肤本^明的較佳實施例所述之於加羅瓦域之乘法 二，、中運异電路例如包括一供給電路以及m個互斥或 二：%路係耦接至查表裝置，用以接受被乘數A，並 c數矩陣w而輸出以下之矩陣： Ά 冰w-i，〇a〇 %,0^0 冰一―rt -1

W V η /、中為根據Wi決定是否提供引來輸出。m個互斥或 12530从twf— 路之輪出而輸出積 閘係轉接至供給魏，肖祕據供給電 ⑺-丨—1-丨，A,—丨+ w r 丨’”7'2〜〜2+，..+ %一丨，〇% 〜卜2 — '卜2 A卜】+冰 : ^2,m,2a^^+...+ 厂〇 V〇,〇«o V-U'，八―2 +.. · + υ，υΐ

式中之符號+為做-邏輯互斥或運算Q 器 器 表 器 依照本發明的較佳實施例所述之於加 ，其中供給電路例如包括m2個及閘。 乘 ”明的較佳實施例所述之於加羅瓦域之乘法 1，、中一表裴置例如包括一記憶體用以儲存乘數係數 依照本發明的較佳實施例所述之於加羅瓦域之乘法 ，其中查表裝置例如包括一電腦系統以及一組暫存器。 電腦系統用以執行多數個指令而輸出係數矩陣w。暫存 器則用以暫存係數矩陣W。 本發明提出一種於加羅瓦域計算乘法的方法，其步 驟包括輸入一被乘數A以及一乘數s，被乘數A與乘數 S係同屬於一加羅瓦域GF ( 2m )，其中A表示為 〜_2…％]’s表示為L…〜]。接著依據乘數s， 自一乘數係數表查表而得一係數矩陣w，其中w表示為： ^m-l,/w-l ^τη-\,ηΊ-2 ^m-\,0 ^m-2,w-l ^m-2,m-2 '** ^j-2,0 • * * * ： ： ： ： 〇 * W〇,m-2 *·* W〇,〇 ^ 之後運算係數矩陣w及被乘數A而得一積R，而且積r 係同屬於加羅瓦域01"1^]01)，其中R表示為 6/6twf.doc/m k-i〜-2…小且 厂w —丨 Wm-\,m-\am-\ ^m-\^ni~iam~2 +----h Vl^ { 〇a〇 rm-2 ~ Wm-2,m-\Xm-\ + H-----l· W^_2 〇X〇 r0 ~ W0,m-\am-\ ^ W0,m~2am-2 ~·-----^ W〇 0¾ 式中之符號+為做-邏輯互斥或運算， 為對— a

做一邏輯及運算。 、J 依照本發_健實闕所述之於加羅瓦域計算乘 法的方法，其中對MW邏輯及運算之運算步驟係為 根據Wi決定是否提供a』給後序運算使用。 依照本發明的較佳實施例所述之於加羅瓦域計算乘 法的方法，其中更可包括由—m_始多項式形成一加 羅瓦域GF(2m)，並於加羅瓦域GF(2m)之下將一輸入 X以及乘數s作乘法運算，最後得—輸出τ，其中乂表 ，為^丨〜d]，T表示為[n2 ···,。]且 + + ... + ww_l5〇x〇 卜 - Ης_2，Λ_2 + · · · + '—2，。 0 V W〇，m~2Xm-2 + . ·. + Ά 式中之符號+為做一邏輯互斥或運算，〜巧係為對％與力 做邏輯及運算。因此，輸出τ可表示為係數矩陣~與 輪入X運算所得之積； 最後計算並且儲存係數矩陣W2 2m-1個可能，而得 到乘數係數表。 . 本發明根據一乘數S自一含有一乘數係數表之查表 ，置查表而得一係數矩陣W。之後，藉由一耦接至查表 发置之供給電路，接受此係數矩陣W以及一被乘數A， i253qy 6twf.doc/m 並依據係數矩陣w來決定是否將被乘數A輸出至互 閘。最後經由m個互斥或閘的計算後而得—積R。因或 於加羅瓦域GF (2m)下進行乘法運算時，本發明可二^ 由查表的方式簡化複雜之運鼻電路’並縮短運算時程。 為讓本發明之上述和其他目的、特徵和優點能更 顯易懂，下文特舉較佳實施例，並配合所附圖式，二、， 〜、 八’作㊁羊細 祝明如下。 【貫施方式】 圖1繪示為依照本發明實施例於加羅瓦域之乘法哭 的不意圖。請參照圖1，本實施例之於加羅瓦域之乘法器 100係建立在一個由三階原始多項式（例如所形 成之加羅瓦域GF (23)下，其包括一查表裝置11〇以及 一運算電路120。查表裝置100係根據一乘數s，自一乘 數係數表112查表而得一係數矩陣w，其中乘數s屬於 -加羅瓦域GFU3)，S表示為h , y，w表示為：、 〜，丨W20] '2 '丨，〇 〇 ，〇,2 〜W〇〇， 另外，運算電路120係耦接至查表裝置11〇,用以接受一 被乘數A以及自查表裝置11〇輸出之係數矩陣％，將兩 者運算後可得一積R。其中，被乘數A與積R係同屬於 加羅瓦域>GF (2 ) ，A表示為h q a。]，r表示為 h π ^]。運异電路12〇更包括一供給電路13〇以及爪個 互斥或閘140，其中供給電路13〇 (例如為以個及閘）係 6twf.doc/m 耦接至查表裝置110，而互斥或閘140則耦接至供給電路 130。 請繼續參考圖1，當於加羅瓦域之乘法器100接受一 被乘數A時，查表裝置110根據乘數S自乘數係數表112 查表而得一係數矩陣W。之後，供給電路130接受來自 查表裝置110的係數矩陣W以及被乘數A，並且根據係 數矩陣W而輸出一矩陣 W2,2a2 W2,\ai ^2,0^0 wua2 ά w10a0 ’ _wQ2a2 w0la, wQ0a0_ 其中wa為根據Wi是否提供a」輸出至互斥或閘140。互 斥或閘140根據供給電路130的輸出而計算出積R，其中 r2 = w22a2 + w2la} + w20a0 η = w12 α2+Ά + w10% r〇 = W0,2a2 + + W〇,〇a〇 1 式中之符號+為做一邏輯互斥或運算，WA係為對力與aj 做一邏輯及運算。 圖2與圖3繪示為依照本發明實施例於加羅瓦域之 乘法器的查表裝置示意圖。請共同參照圖1、圖2以及圖 3，查表裝置110之結構可以包括一記憶體114用以儲存 乘數係數表112。如此一來，查表裝置110可以根據乘數 S自記憶體114輸出係數矩陣W。此外，查表裝置110更 可以包括一電腦系統116以及一組暫存器118。如此一來’ 電腦系統116可以根據乘數S執行一連串的指令後，輸 出一係數矩陣W，並且暫存於暫存器118内。 請再次參照圖1，建立乘數係數表112之步驟包括利 11 6twf.doc/m 用^一個二1¾原始多項式（例如1 + ^ + )形成一加羅瓦域 GF (23) ’並且對一輸入X以及乘數S做乘法運算，最 後得到一輸出T。其中，X表示為卜2々xQ]，T表示為 [/2 A d而且 G 二 W2 2x2 + Ά + W2 0x0 Λ 二 W1，2X2 + W1,1X1 + Ά ,0 = W0,2X2 + Ά + %，〇X〇 式中之符號+為做一邏輯互斥或運算，WiXj係為對％與χ 做一邏輯及運算。之後，將輸出Τ表示成係數矩陣W與 輸入X作乘法運算所得之積，T = wx。以輸入X為 h A X。]且乘數s為α2為例，將輸入X與乘數s於上述 之加羅瓦域GF (23)作乘法運算時，輸入X可表示為 χ2 α 2+χ! α +χ0，貝丨j X* a -(χ2 α 2+χ1 α +χ0)* a 2=χ2 a 4+χ! a 3+χ〇 a2 又因為 α J 4= (2 2+ q 所以 X* α 2ζ=χ2( α 2+ α )+χ!( α + l)+x。α2 "C^+Xo) a 2+(χ2+Χι) a +χ! 由上可知，Χ*α2=[(χ2+χ()) (χ2+χι) \]=1 ι y 0 0 1」

=WX=T 式中付號+為做一邏輯互斥或運算，*為作一於加羅瓦域 GF (23)之乘法運算， 依，居上述之计箅方式，計算並且儲存係數矩陣W之2m-l 個可能’即可得到乘數係數表112。 基於上述，凡熟習此項技術者應知本發明並非僅偈 12530^6 twf.doc/m 限於本實施例所述，即利用二 域gf(23)，在依此加羅瓦;卩^始多項式建構—加羅瓦 瓦域之乘法器。此外mm製作出一於如羅 矛用m階原始多項式所形成之加羅瓦域 、出- 此加羅瓦域GF 建構出另一於加羅瓦域之亚依 綜上所述，本發明根據—乘數s，自 -° f表之查表裝置查表而得—係數矩陣W。之後，藉^

ιίίϊ查表裝£之供給電路，接受—被絲並依據係數矩 ^疋是否將被乘數輸出至互斥或閘。經由m個互H m便而得一積R。因此於加羅瓦域下進二 =’本發明相藉由絲财賴倾狀運算運 並縮短運算時程。 ，本發明已以較佳實施例揭露如上，然其並非用 P艮疋本發明’任何熟習此技藝者，在不脫離本發 lit範圍内，當可作些許之更動與潤飾，因此本發明之^ 遷乾圍當視後附之申請專利範圍所界定者為準。 ”

【圖式簡單說明】 圖1繪示為依照本發明實施例於加羅瓦域之乘法哭 的示意圖。 口口 圖2〜圖3繪示為依照本發明實施例於加羅瓦域之乘 决器的查表裝置示意圖。 【主要元件符號說明】 13 6twf.doc/m 100 ··於加羅瓦域之乘法器 110 :查表裝置 112 :乘數係數表 114 :記憶體 116 :電腦系統 118 :暫存器 120 :運算電路 130 :供給電路 140 :互斥或閘 14

Claims (1)

1253 Q J6}6twf.doc/m 十、申請專利範圍： ι·一種於加羅瓦域之乘法器，包括： 矣二查置’用以根據—乘數8，自—乘數係數表查 矩陣W，其中該乘數s係屬於一加羅瓦域， ^表不為k-i ^ ···〜]，W表示為 Wm-\,m-\ Wm-\,m-2 ''' Wm-\,〇 '卜2，讲-丨 \卜2，爪-2 ·.· Ww_2〇 ·、 一運算電路’減至該絲裝置，㈣接受一被乘 數A以及該係數矩陣w，運算而得—積R，該被乘數a 與該積R係同屬於該加羅瓦域，其中A表示為 k^—…’ r表示為2…μ，而 Γ/η_1 + Wm-\}m-2am~2 + * * * + 〇a〇 Γηί~2 ~ ^ ^-2,^-2^-2 + * * * + Wm_2 〇a〇 r〇 = + w。，凡-2 + · ·. + 式中之符號+為做一邏輯互斥或運算，Wia』係為對％與气 做一邏輯及運算。 J 2·如申請專利範圍第1項所述之於加羅瓦域之乘法 器，其中該運算電路包括： 一供給電路，耗接至該查表裝置，用以接受該被乘 數A，並根據該係數矩陣w而輸出 • · Wm-\^aQ Wm-2tm-2am-2 · Wm~2,0a0 W0,m-\am-\ ·· ^0,0¾ 其中wa為根據該Wi決定是否提供aj來輸出；以及 15 1253 〇il^6twf.doc/m或:=::供:電路、概據 W 卜iU %卜 1”卜2a +.，. + 1 A -f Wm-2,m~2Xm-2 + * * * + -i，〇ao ^-2,0¾ 式。‘‘〜—A-〆..· +'A 中之符號+為做一邏輯互斥或運管。哭，，申請專利範圍第2項所述:於 其中該供給電路係包括m2個及閘、、' 瓦域之乘法 器，專利範圍第1項所述之於加 表。、中《表裝置係包括—記㈣肋儲存該乘數係數 器，复+1 °】專彻11圍第1項所述之於加羅瓦域之乘法 其中该查表裝置包括·· 陣w.屯細系統’用以執行多數個指令而輸出該係數矩 ，以及 ，暫存器’用崎存該餘矩陣W。 於—種於加羅瓦域計算乘法的方法，包括下列步驟： 數Sr: 破乘數A以及—乘數S，該被乘數A與該乘 係，屬於—加羅瓦域，其中a表示為k_m]， 羅瓦域之乘法 S 表示為k…小 依據该乘數S ’「自—乘數係數表查表而得一係數矩陣 其中W表示為 ym-2,0 ;以及 利用該係數矩陣 W0 ，m~i 〇，w-2 K0,0 W及該被乘數A，運算而得一積R 16 1253 ^76twf.doc/m 該積R係同屬於該加羅瓦域，其中尺表 k_丨v 而 r〇] 示為 厂m-1 — MVu卜if w”卜I w_2a”卜〆...+ w"卜!，A '-2 二 MV2，lU '''w_2xw_2 + …+ Ι Α Γ0 - W0,m-\am~\ + Η-----h W〇 〇a〇 式中之符號+為做—邏輯互斥或運算，w 做一邏輯及運算。 1 J乐馮封Wi與a」· W-1 xm^2 丨：一八-1 切，人2 +... + W…X〇 2 = + ·. · + 夂_2，。 7.如申請專利範圍第6項所述之加羅 方法，其中對％與心該邏輯及運算之；;^乘法的 據該％決定是否提供^給後序運算使用。〜糸為根 8·如申請專利範圍第6項所述之 方法，其步驟更可包括由階原始多項乘法的 瓦域证⑺，並於該加羅瓦域证⑺之^成2^羅 =以及該乘數s作乘法運算，最後得—輸出τ，=入 表不為k k…％]，τ表示為·.. d且" ’m 丨切0，w_u · ·. + 5虎+為做一邏輯互斥或運算，WiXj係為對w，x. 則輸出T可表示為係數矩陣〜與輪入」 乘數ίίί财轉紐轉w^1個可能，而得到一 17