用於雙基底有限域的心縮式乘加器結構的製作方法

2023-05-03 04:18:21 1

專利名稱：用於雙基底有限域的心縮式乘加器結構的製作方法
技術領域：
本案是一種運用於雙基底(dual-basis)有限域GF(2m)及GF(2n)(GFGalois Field)的A*B+C運算的心縮式乘加器(Systolic product-sumcalculator over dual-basis in GF(2m)and GF(2n))結構，尤指一種可在有限域GF(2m)的最大mxm元素單元數組(elementary cell array)中在不變mxm單元數組架構下可各自獨立執行雙基底有限域GF(2m)或GF(2n)的A*B+C運算，而其中A，B和C是指有限域GF(2m)及GF(2n)中的任意元素，其中該雙基底有限域的各個A*B+C的並行輸入(parallel in)及並行輸出(parallelout)運算結果亦仍各自涵蓋於該各自基底的有限域內的一種雙基底有限域(finite field)結構，同時以該基本A*B+C元素單元數組電路為基礎，可組合用來作為有限域GF(2m)中的乘法電路、加法電路、指數電路、乘法反元素及除法電路等的運算。
背景技術：
有關於Galois field GF(2m)運用在A*B+C的乘加運算可追朔到1984年C.S.Yea.et.al所公開的並行輸入、並行輸出的心縮式架構，其在VLSI的設計中GF(2m)是一相當簡便及有效的計算工具，因此本案發明即據此將此一技術改良升級成在不變該並行輸入及並行輸出的心縮式有限域的架構下提出一種雙基底GF(2m)或GF(2n)來運算A*B+C(0＜n＜m)，而此種前所未有改良型雙基底心縮式架構可被用將GF(2)有限域的延伸域來作數位訊號的處理及錯誤控制更正碼(error control coding)，這方面的應用如利用RS codes或BCH codes等。

發明內容
目前在數位訊號處理、計算器(computers)及通訊等領域的實際運用上，該有限域GF(2m)的運算已受到相當的重視，例如RS codes、BCH codes等的錯誤句柄(error control codes)運用。
由於要設計一個同時具有高解碼速率及低電路複雜度的錯誤更正碼的解碼器，除了有效的解碼法外，一個功能強大的運算電路也是必需的，因此，如何致力於低電路複雜度、較短的計算延遲、較高運算速率、節省空間及降低製造成本的有限域運算電路設計是目前該有限域GF(2m)運算廣被討論的議題；我們知道乘加法運算是在有限域運算中最被頻繁使用到的運算之一，以如具有4個錯誤控制更正能力的二元基本(binary primitive)BCH codes為例，就需要數個乘加法運算才能完成，因此如何有效運用有限域邏輯運算即為一重要的課題，再者，有限域運算單元電路目前已有很多不同基底(basis)的架構被發展出來，如使用雙基底(dual-basis)，正規基底(normal basis)，以及標準基底(standard basis)等，各種型式基底的有限域運算皆有其特色，也因此各適合於不同的特殊應用，而本案的設計則是採用用於雙基底有限域GF(2m)及GF(2n)的心縮式乘加器結構的有限域運算，這個乘加器的電路是由m2個相同元素單元(elementary cell)所構成，每一個元素單元中含有二個二輸入邏輯「與」(2-input AND)門及二個二輸入邏輯「異或」(2-input XOR)門。
總而言之，本案是一種用於並行輸入及並行輸出的雙基底有限域GF(2m)或GF(2n)的心縮式乘加器結構，包括一有限域GF(2m)的m2單元數組，於該有限域GF(2m)中執行一A*B+C運算，該A，B，C是該有限域GF(2m)中的任意元素，其中m≥3的整數；以及一有限域GF(2n)的n2單元數組，於該有限域GF(2n)中執行一A*B+C運算，該A，B，C是該有限域GF(2n)中的任意元素，其中0＜n＜m。其特徵在於該有限域GF(2n)的n2單元數組為該有限域GF(2m)的m2單元數組內的一部份，藉由於該m2單元數組中加入多個以選擇控制線sel控制輸入的多路復用器(MUX)，該雙基底有限域GF(2m)或GF(2n)即可各自獨立處理外界並行輸入的不可約本原多項式(Irreducible Primitivepolynomial)作該A*B+C運算並並行輸出，達到只要具備一套m2單元數組架構即能各自獨立處理作該雙基底有限域GF(2m)或GF(2n)的兩套A*B+C運算。
最好，其中該A*B+C的運算為一基本運算單元，以此基本運算單元為基礎電路可用來執行乘法電路、指數電路、乘法反元素電路及除法電路等的電路運算。
最好，其中該A*B+C單元數組架構是由m2個相同元素單元(elementarycell)以數組方式所組成，而該每個元素單元中有二個二輸入邏輯「與」(2-input AND)門及二個二輸入邏輯「異或」(2-input XOR)門。


本案得藉由下列圖式簡單說明，俾得一更深入的了解圖1熟知單基底GF(24)心縮式乘加器；圖2是本案發明元素單元電路圖；圖3本案發明雙基底GF(24)及GF(23)心縮式乘加器；圖4本案發明雙基底GF(2m)及GF(2n)心縮式乘加器。
具體實施例方式
請參考圖1，該圖1是本案熟知單基底並行輸入(parallel in)、並行輸出(parallel out)心縮式結構有限域GF(2m)(m＝4)的單元間接線圖，其是由4×4元素單元(elementary cell)的單元間接線圖，即當m＝4，而任意元素A，B，及C是下形式輸入{a0，a1，a2，a3}、{b0，b1，b2，b3}及{c0，c1，c2，c3}，其中ai，bi，ci是含屬於GF(2)。
請參考圖2，該圖2則是本案有限域GF(2m)的元素單元電路圖M(u，v)，該圖2的圖中明白標示出了輸入端/輸出端元素及單元中的接線，該圖2所示的元素單元電路是由二個二輸入邏輯「與」(2-input AND)門及二個二輸入邏輯「異或」(2-input XOR)門所組成，而該元素單元邏輯運算輸出端P＝A*B+C，如當m＝4，則該邏輯運算輸出端P的輸出型式為{P0，P1，P2，P3}。
其中h_out＝h_in；d_out＝d_in；v_out＝g_in；u_out＝u_in；e_out＝(g_in*d_in)e_in；g_out＝(h_in*u_in)v_in.
而該元素單元電路在並行輸入端的形式如下
h_in＝fj；g_in＝aj；e_in＝cj；d_in＝bi；u_in＝v_out.
該圖1及圖2可以藉由於該元素單元數組間加入以「sel」控制線控制輸入的多個MUX多路復用器而延伸到其它如圖3(雙基底GF(23)及GF(24)，當m＝4，n＝m-1)及圖4(雙基底GF(2n)及GF(2m)，0＜n＜m)有限域。
綜合以上的說明，可知本案發明的一種用於並行輸入及並行輸出的雙基底有限域GF(2m)或GF(2n)的心縮式乘加器結構，不但具有其優越功效，熟悉此技藝的人士亦不易思及，且亦已達可具體實施的程度，從未先見於國內外刊物或已公開使用，而有大幅節省使用空間(只需一套元素單元數組即可處理兩組有限域基底的乘加運算)、降低製造成本(節省門數的製造成本)及增進元素單元數組運用效率的優點，本案發明結構實允符新穎性、進步性及產業可利用性的專利三要件，依法提出申請，懇請賜準。
本案發明得任由熟悉本技術的人士任施匠思而為諸般修飾，然皆不脫如附申請專利範圍所欲保護者。
權利要求
1.一種用於雙基底有限域GF(2m)或GF(2n)的心縮式乘加器結構，包括一有限域GF(2m)的m2單元數組，於該有限域GF(2m)中執行一A*B+C運算，該A，B，C是該有限域GF(2m)中的任意元素，其中m≥3的整數；以及一有限域GF(2n)的n2單元數組，於該有限域GF(2n)中執行一A*B+C運算，該A，B，C是該有限域GF(2n)中的任意元素，其中0＜n＜m。其特徵在於該有限域GF(2n)的n2單元數組為該有限域GF(2m)的m2單元數組內的一部份，藉由於該m2單元數組中加入多個以選擇控制線控制輸入的多路復用器，使該雙基底有限域GF(2m)或GF(2n)即可依各自獨立的兩組不可約本原多項式處理並行輸入、並行輸出的A*B+C運算，達到只要具備一套m2單元數組架構即能各自獨立處理該雙基底有限域GF(2m)或GF(2n)的兩組不可約本原多項式的A*B+C運算。
2.如權利要求1所述的用於雙基底有限域GF(2m)或GF(2n)的心縮式乘加器結構，其中該A*B+C的運算為一基本運算單元，以此基本運算單元為基礎電路可用來執行乘法電路、指數電路、乘法反元素電路及除法電路等的電路運算。
3.如權利要求1所述的用於雙基底有限域GF(2m)或GF(2n)的心縮式乘加器結構，其中該A*B+C單元數組架構是由m2個相同元素單元以數組方式所組成，而該每個元素單元中有二個二輸入邏輯「與」門及二個二輸入邏輯「異或」門。
全文摘要
本案是一種運用於雙基底有限域GF(文檔編號G06F7/48GK1459710SQ0211986
公開日2003年12月3日 申請日期2002年5月17日 優先權日2002年5月17日
發明者邱榮樑 申請人:矽統科技股份有限公司