吳海霞， 李凌宇， 王天， 王興華， 李瀟然

(北京理工大學 信息與電子學院，北京 100081)

相對于布爾邏輯計算模式而言，多值邏輯計算模式在理論上具有更為強大的計算能力. 多值電流模(multiple-valued current-mode，MVCM)電路在降低硬件復雜性方面具有更大的潛能，因為在該類電路中，不僅一根線可以承載多于1位的數(shù)據(jù)，而且算術運算中頻繁使用的線性和運算可以簡單地通過線的直接連接而實現(xiàn)，不需要任何器件[1-5]. 伽羅華域運算在通信領域包括糾錯編碼、加密運算及數(shù)字信號處理等方面起著重要的作用. 越來越多的應用都需要VLSI實現(xiàn)以滿足面積、速度及安全性的要求，而且這些應用的有效性很大程度上取決于伽羅華域算術運算的有效性. 目前伽羅華域運算的實現(xiàn)主要是基于布爾邏輯，存在的主要問題是延遲太長和硬件太大. 因此，迫切需要針對這些運算操作的有效算法和簡化的硬件結構[6-10]. 針對上述問題，本文主要討論了GF(24) 上基于四值邏輯的AB+C算法及其基于多值電流模的并進并出脈動電路的實現(xiàn).

1 建立四值邏輯與伽羅華域的關系

GF(2k)域元素有很多種表示形式和方法. 若k為兩個整數(shù)的積,k=nm， 那么通過GF(2n)來描述GF(2k),可以得到該域的不同表示方法. 這樣，域GF(2n)，通過它來描述合成域， 被稱為基域. 因此，對于四進制的有限域，基域為GF(22) =GF(4). 合成域是指在GF(2k)的某個子域GF(2n)上而不是素域GF(2)上定義的擴展域. 用GF((22)m)表示四進制合成域，GF(2k)表示通過素域GF(2)定義的二進制擴展域. 一個域GF(2k)，若其具有確定的k值、確定的不可約多項式及確定的初始元素，那么它就具有確定的2k個域元素，無論是用二進制擴展域GF(2k)或是合成域GF((22)m)表示，代表的是同一個域. 這些完全不同的表示方法之間可以相互轉換[3].

利用初始元素β和最佳不可約多項式f(x)=x2+x+1構成域GF(22)，其對應的4種表示方法，β表示、多項式表示、2-位二進制表示及1-位四進制表示，如表1所示.

用1-位四進制0、1、2、3和2-位二進制表示GF(4)中的元素后，圖1給出了其模乘和模加的定義，其中符號?和⊕分別表示這兩種算術運算. 這些運算在運算過程中不涉及任何進位，可以簡化硬件實現(xiàn).

圖1 GF(4)的模乘和模加運算

利用初始元素0100和初始不可約多項式f(x)=x4+x+1構造域GF(24)，其對應的合成域GF((22)2)的最佳不可約多項式可以推導得出為f(x)=x2+x+3. 進而得出其相應的5種表示法：α表示，GF(24)的多項式表示和4-位二進制表示，及GF((22)2)的4-位二進制表示和2-位四進制表示[3,9-10,12]. 表2給出了這5種不同的表示，并顯示了合成域GF((22)2)如何與四進制及二進制域GF(24)建立聯(lián)系. 通過這樣的轉換和表述，可以看出基2的合成域運算比較適合利用多值邏輯來實現(xiàn)，例如，GF((22)m)運算適于利用四值邏輯來實現(xiàn). 多值邏輯表示的每一個數(shù)據(jù)位承載多于1-bit的信息，在二值邏輯系統(tǒng)每次處理1-bit信息，而在多值邏輯系統(tǒng)每次處理多于1-bit信息，因此有希望獲得處理速度的改善及硬件連線的減少.

表2 同一域的不同表示法：GF(24)和GF((22)2)

2 MVCM電路的基本原理

MVCM電路的基本結構如圖2所示，通常包括3個基本組件，線性和、閾值比較器和輸出生成器. 本文采用基于動態(tài)源極耦合邏輯的MVCM電路架構，其上述3個基本元件的電路原理圖如圖3所示. 在閾值比較器中，首先將四值電流模輸入信號I(X) 轉換為電壓信號V(X)，然后V(X)與閾值V(T)進行比較并產(chǎn)生二值差分輸出信號(G,G′)；信號(G,G′)作為輸出生成器的輸入信號控制輸出信號的生成；線性和是通過將信號線直接連接在一起來實現(xiàn)；這樣，最終輸出的是電流模信號[1-2]. 因此，可以看出輸出生成器是設計的關鍵. 本文采用文獻[12]中GF(4)的四進制模乘和模加器，分別用圖4所示的兩個符號表示這兩個模塊.

圖2 MVCM電路的基本結構

圖3 MVCM基本組件的電路原理圖

圖4 模乘和模加符號

3 基于四值邏輯的脈動積-和AB+C運算算法

在GF((22)2)中，假設A=a0+a1α,B=b0+b1α及C=c0+c1α，對應的不可約多項式為f(x)=x2+f1x+f0，那么AB+C定義為

AB+C=(a0+a1α)(b0+b1α)×modf(x)+(c0+c1α)

(1)

因為初始元素α是f(x)的一個根，且根據(jù)GF域的基本特性α=-α，得到

f(x)=x2+f1x+f0?α2+f1α+f0=0?

α2=-f1α-f0?α2=f1α+f0

將α2=f1α+f0帶入公式(1), 得到下列等式[3]

R=AB+C=R0+R1α

其中R1=b1(a1f1+a0)+a1b0+c1,

(2)

R0=b1a1f0+a0b0+c0

(3)

考察等式(2)和(3)，可以將其分解為公式(4)及公式(5)所示的運算層次. 分析R1和R0的表達式，可以看出它們都可以通過3個獨立的積-和運算來實現(xiàn)，可以采用二級流水結構來提高數(shù)據(jù)運算的吞吐量，從而提高處理速度.

(4)

(5)

隨機以A=B=C=α8為例，簡單說明如何在GF(24)及GF((22)2)上進行AB+C運算. 首先，利用二值邏輯在GF(24)上計算AB+C，并依據(jù)表2，將其結果轉換為四進制表示.

AB+C=α8·α8+α8=α16mod15+α8=

α+α8=0100+1010=1110=α10=〈20〉

(6)

接下來，利用四值邏輯在GF((22)2)上計算AB+C.

步驟1:GF((22)2)的不可約多項式是x2+x+3,所以f1=1,f0=3；并依據(jù)表2的轉換，可以得到

A=B=C=α8=〈21〉

步驟2：根據(jù)等式(2)(3), 可得

(7)

等式 (6) 和 (7)表明采用上述兩種邏輯系統(tǒng)進行運算，所得結果相同.

依據(jù)等式(4)和(5)，在GF((22)2)上進行AB+C運算需要兩級積-和迭代. 據(jù)此，基于四值邏輯構建的并入并出脈動陣列電路結構如圖5所示，模塊 PE1和PE2見圖6所示， D觸發(fā)器和T 鎖存器用以同步信號，具體結構參見文獻[11].

圖5 四進制AB+C 脈動結構

圖6描述了AB+C脈動電路中的信號同步，a0a1,b0b1,c0c1和f0f1是原始輸入信號.

圖6 AB+C脈動電路中的信號同步

4 分析驗證

在0.18 μm CMOS工藝下對本文的設計進行了仿真驗證，圖7顯示了時鐘周期為10 ns 的輸入和輸出波形，可以看出經(jīng)過5個時鐘周期后，在時鐘下降沿輸出運算結果，圖中的豎線表示從該時刻開始輸出運算結果. 圖8給出了對應圖7的輸出時序分析，可以看到在第(n+5)個時鐘周期下降沿輸出第n個輸入的運算結果，輸出結果與理論計算值一致. 本設計中四值邏輯0、1、2、3對應的電壓值為0.3 V、1 V、1.3 V及1.8 V. 表3給出了與文獻中相應二值邏輯及四值邏輯實現(xiàn)技術的比較. 相對于文獻[3]基于二值邏輯的實現(xiàn)技術，本設計的首次延時減小了54%，晶體管數(shù)目與連線數(shù)目總和減少了5%，盡管相對于該文獻中基于神經(jīng)元MOSFET的多值電壓模實現(xiàn)技術，沒有明顯的改善.

圖7 AB+C輸入和輸出波形

圖8 AB+C的仿真數(shù)據(jù)的時序分析

表3 GF(24)上AB+C運算的性能對照

5 結 論

本文給出了一種基于四值邏輯的GF(24)上AB+C的算法及其基于MVCM并入并出脈動陣列結構的電路實現(xiàn). 在0.18 μm CMOS工藝下進行了HSPICE電路仿真，并與已發(fā)表的文獻進行了性能比較. 與相應的基于二值邏輯的CMOS實現(xiàn)相比，首次延遲明顯減少，晶體管和連線的數(shù)目和也有一定程度的減少. 本文所提的脈動陣列電路，結構簡單、規(guī)整、模塊化，適于作為算術運算處理器芯片的基本模塊，應用于加密、糾錯編碼、數(shù)字信號處理等領域. 本項工作顯示，MVCM電路與相應的基于MVL算法的結合是實現(xiàn)GF(2k)超高性能運算單元的一個潛在的解決方案. 在應用層面有限域運算通常是大數(shù)據(jù)位的運算，例如ECC加密的數(shù)據(jù)長度一般大于150 bit. 多值邏輯的運算優(yōu)勢在大數(shù)據(jù)位的運算系統(tǒng)中會有更為明顯的體現(xiàn)，因此研究基于多值邏輯的大數(shù)據(jù)位的GF (2k)的運算算法及其VLSI實現(xiàn)，將是未來研究工作的一個方向. 另外，噪聲一直是多值邏輯實現(xiàn)技術關注的問題，在保持高轉換速度的同時降低噪聲和靜態(tài)功耗將是未來研究工作的重點. 如果這些問題能夠很好解決，多值邏輯技術將成為獲得高性能運算芯片的一個切實可行途徑.