基于四值邏輯的伽羅華域AB+C電路設(shè)計(jì)

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

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

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

1 建立四值邏輯與伽羅華域的關(guān)系

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

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

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

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

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

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

2 MVCM電路的基本原理

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

圖2 MVCM電路的基本結(jié)構(gòu)

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

圖4 模乘和模加符號(hào)

3 基于四值邏輯的脈動(dòng)積-和AB+C運(yùn)算算法

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

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

(1)

因?yàn)槌跏荚卅潦莊(x)的一個(gè)根，且根據(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)所示的運(yùn)算層次. 分析R1和R0的表達(dá)式，可以看出它們都可以通過3個(gè)獨(dú)立的積-和運(yùn)算來實(shí)現(xiàn)，可以采用二級(jí)流水結(jié)構(gòu)來提高數(shù)據(jù)運(yùn)算的吞吐量，從而提高處理速度.

(4)

(5)

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

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

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

(6)

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

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

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

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

(7)

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

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

圖5 四進(jìn)制AB+C 脈動(dòng)結(jié)構(gòu)

圖6描述了AB+C脈動(dòng)電路中的信號(hào)同步，a0a1,b0b1,c0c1和f0f1是原始輸入信號(hào).

圖6 AB+C脈動(dòng)電路中的信號(hào)同步

4 分析驗(yàn)證

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

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

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

表3 GF(24)上AB+C運(yùn)算的性能對(duì)照

5 結(jié) 論

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