姜恩華， 姜文彬

(淮北師范大學(xué) 物理與電子信息學(xué)院， 安徽 淮北 235000)

0 引 言

隨著集成電路工藝特征尺寸的縮小和芯片中器件面積的減小，電路布線所占面積增大. 多值邏輯電路因攜帶的信息密度較高，可減少電路連線，節(jié)省芯片面積. 因此，研究多值邏輯電路與系統(tǒng)設(shè)計具有重要意義. 文獻[1]基于多值代數(shù)提出了用于多值數(shù)字電路設(shè)計的CMOS門通用集，并應(yīng)用于四路選擇器和四值觸發(fā)器的設(shè)計與實現(xiàn). 文獻[2]利用多值邏輯(四值邏輯)模代數(shù)運算，提出模4中的算術(shù)運算及其CMOS電路實現(xiàn). CMOS動態(tài)三值邏輯電路[3]、納米場效應(yīng)管三值邏輯門和算術(shù)運算電路[4]、納米場效應(yīng)管三值全加器電路[5]、單電子晶體管(single electron transistor，SET)和MOSFET組合構(gòu)成的多值邏輯電路和存儲電路[6]，受到了較多關(guān)注.目前，多值邏輯CMOS集成電路由二值CMOS集成電路實現(xiàn). 文獻[7]提出了一種新的CMOS傳輸管邏輯電路和互補CMOS邏輯電路混合型的高速CMOS二值全加器電路. 三值T門是一種通用邏輯模塊(器件)，利用三值T門模塊可實現(xiàn)任意三值邏輯函數(shù). 根據(jù)多值邏輯電路設(shè)計原理[8]，將三值T門電路分為閾門邏輯電路和三值邏輯信號傳輸電路兩部分. 用CMOS傳輸門可構(gòu)成三值T門的信號傳輸電路部分. 閾門邏輯電路可將三值邏輯信號轉(zhuǎn)換為二值邏輯信號，并作為CMOS傳輸門的柵極信號. 基于上述原理，本文提出了三值T門模塊電路的設(shè)計，該模塊是用二值CMOS管設(shè)計的，其三值信號傳輸部分由CMOS傳輸門實現(xiàn)，閾值邏輯信號產(chǎn)生部分由互補CMOS電路實現(xiàn)，即采用混合型邏輯電路構(gòu)建. 不同于文獻[8]提出的三值T門電路，本文提出的三值T門電路未用變閾值MOS管.

三值T 門邏輯網(wǎng)絡(luò)的化簡(最小化)及其計算機算法，是三值邏輯電路與系統(tǒng)領(lǐng)域一個重要的研究課題. 文獻[9]提出了基于多值T門組合電路模塊分解方法的多值T門電路化簡方法. 文獻[10]研究了三值邏輯函數(shù)簡化的不相交積之和(reduced disjoint sum-of-products，RDSOP)形式的代數(shù)理論，提出采用混合控制變量排序的三值T門組合網(wǎng)絡(luò)的化簡和設(shè)計的一種代數(shù)方法. 但在該文給出的算法的第2步，求取待實現(xiàn)函數(shù)在其變量集上合適的劃分，缺少相關(guān)定理和選取依據(jù). 本文基于三值邏輯函數(shù)RDSOP形式的代數(shù)理論，討論求取待實現(xiàn)函數(shù)在其變量集上選取合適劃分的相關(guān)定理及其選取依據(jù)，提出三值T門組合網(wǎng)絡(luò)設(shè)計(化簡)的一種混合控制變量排序算法，該算法可使待設(shè)計的三值T門網(wǎng)絡(luò)最小化，易實現(xiàn)三值T門組合網(wǎng)絡(luò)的自動綜合. 將該三值T門模塊用于三值T門網(wǎng)絡(luò)的仿真實驗，結(jié)果表明，該三值T門網(wǎng)絡(luò)的邏輯功能正確，算法有效.

1 三值格代數(shù)系統(tǒng)和三值T代數(shù)系統(tǒng)的基本運算和定理

設(shè)邏輯值集合為L={0，1，2}，全序關(guān)系為 2>1>0.對于變量x,y∈L及常量j∈L，引進具有補運算的三值格代數(shù)系統(tǒng)，“或”(取大)、“與”(取小)、“閾”(文字)3種基本運算和補運算[8]，分別為

(1)

(2)

式中，符號“-”為算術(shù)減法運算，符號“·”可以省略. 式(1)的3種基本運算已構(gòu)成代數(shù)完備系統(tǒng)，即三值格代數(shù)系統(tǒng). 由式(1)和式(2)組成含有冗余運算的三值格代數(shù)系統(tǒng).在該代數(shù)系統(tǒng)中，0 與2互補，1自補.為了簡化符號，常將jxj簡記為xj.由式(1)和式(2)，易證得下述性質(zhì)：

三值T門實現(xiàn)的T運算(T算子)定義為[9]

T(f0,f1,f2;x)=fi，x=i，

(3)

式中x,fi∈{0,1,2}，其中x為T門的控制(地址)變量，fi,0≤i≤2為T門的數(shù)據(jù)輸入.式(3)所示的T運算構(gòu)成一個代數(shù)完備系統(tǒng)，即三值T代數(shù)系統(tǒng).在三值格代數(shù)系統(tǒng)中，式(3)可表示為

T(f0,f1,f2;x)=f0·x0+f1·x1+f2·x2.

(4)

在三值格代數(shù)系統(tǒng)中，設(shè)有一個定義在變量集X={x1,x2,…,xn}上的n變量三值函數(shù)f(X)∈{0,1,2}，其中xi∈{0,1,2}，1≤i≤n.變量集X上各變量重新排序后取劃分為

(5)

式中，is∈{1,2,…,n},1≤s≤n,X的子集B1和B2稱為劃分塊，滿足B1∩B2=?且B1∪B2=X.將香農(nóng)(Claude E. Shannon)展開定理推廣到三值格代數(shù)系統(tǒng)，對于上述函數(shù)及劃分式(5)，則有[8]

(6)

(7)

(8)

(9)

三值函數(shù)中所含變量的個數(shù)n定義為該函數(shù)的Ln空間(超立方體)的維數(shù)，稱為該函數(shù)的維數(shù)，并稱該函數(shù)為n維函數(shù).一個n維函數(shù)在空間Ln上共有3n個點.每個點的變量取值，對應(yīng)于相應(yīng)文字組成的最小項.函數(shù)值為0的點(0值點)對應(yīng)的最小項(0值最小值)在該函數(shù)表達式中可以不列出.1值點和2值點

分別對應(yīng)于該函數(shù)所含的 1值最小項和2值最小項.用該函數(shù)中全部最小項表示的式子稱為該函數(shù)的最小項表達式，其中，0值最小值可忽略不計.最小項表達式也稱最小項展開式，可通過對該函數(shù)的每個變量依次利用推廣的展開定理即式(6)展開得到.例如，一個二變量三值函數(shù)的最小項表達式為

f(x1,x2)=a0·m0+a1·m1+…+a8·m8=

f(0,0)·x10x20+f(0,1)·x10x21+…+

f(2,2)·x12x22，

式中，x1,x2,f(x1,x2)∈L={0,1,2}，該函數(shù)可用二維平面中的點表示，如圖1所示，其中0值最小值可省略.

圖1 二變量函數(shù)的平面圖形表示Fig.1 The plane graphic representation of the two variable functions

對于定義在變量集X={x1,x2,…,xn}上的n變量三值函數(shù)f，將X中的變量排序后劃分為

(10)

對子集B1中的每個變量，依次利用推廣的展開定理即式(6)，可導(dǎo)出該函數(shù)按照劃分式(10)的展開式為

(11)

在一個n變量三值函數(shù)的RDSOP形式[10]中，一個積項p所含該函數(shù)的最小項數(shù)目稱為該函數(shù)的尺度(大小)，用符號“‖p‖”表示.例如，一個文字xij，j∈{0,1,2}，i∈{1,2,…,n}，所含該函數(shù)的最小項數(shù)目為‖xij‖=3n-1.

‖(d·pk)‖=3n-l.

必要性. 若fpk=d∈{1,2}，由式(8)可知，fpk中只含除pk中l(wèi)個不同變量外的其余變量，共(n-l)個變量，組成3n-l個子最小項，且這些子最小項之和為2.而將積項fpk·pk展開成f的最小項之和為fpk·pk=d·2·pk，將該式右邊的邏輯值2以上述3n-l個子最小項之和代入后，可得該積項d·pk含有函數(shù)f的3n-l個d值最小項，即‖(d·pk)‖=3n-l.證畢.

‖(xg·pk)‖=3n-l.

證明由式(11)、定理1和定理2，可推得該推論成立.

需注意，對某個(或某些)pq，若有‖(da·pa)‖=‖(dq·pq)‖，可推得fpq=dq為平凡子函數(shù)，此時，pq中變量集X含有不同文字的數(shù)目也為l個.

證明由式(11)和定理1，可推得該推論成立.

由推論1和推論2，求得平凡子函數(shù)的維數(shù)為(n-l)，稱之為(n-l)維平凡子函數(shù).可以看出，平凡子函數(shù)的維數(shù)越高，對T門網(wǎng)絡(luò)化簡越有利.對于混合控制變量排序算法，T門網(wǎng)絡(luò)化簡(最小化)目標是在待實現(xiàn)函數(shù)的每級網(wǎng)絡(luò)中，使待實現(xiàn)函數(shù)按照擴展的展開定理即式(6)展開后得到的非平凡子函數(shù)類型(nontrivial sub-function patterns，NTSP)的數(shù)目最小，此時得到的T門網(wǎng)絡(luò)稱為最小化T門網(wǎng)絡(luò).

2 三值T門組合網(wǎng)絡(luò)設(shè)計實例

2.1 三值T門組合網(wǎng)絡(luò)設(shè)計步驟

Step1將待實現(xiàn)的函數(shù)化為 RDSOP形式.并對所用T門數(shù)目的變量num 賦初值num： =1.

Step2由推論1和推論2，求取該函數(shù)變量集X上(或求取該函數(shù)每個不能用單個T門實現(xiàn)的非平凡子函數(shù)關(guān)于X的子集上)合適的劃分，使函數(shù)(或相關(guān)子函數(shù))按照擴展的展開定理即式(6)展開后得到的非平凡子函數(shù)類型數(shù)目最小(min).

Step3利用限制運算，按照所選劃分，求出各函數(shù)限制.檢驗各函數(shù)限制是否能用單個T門實現(xiàn)： “N”( 非平凡子函數(shù)類型的序數(shù))表示不能用單個T門實現(xiàn)，“S”(非平凡子函數(shù)類型的序數(shù))表示能用單個T門實現(xiàn).將表示所用T門數(shù)目的變量num之值修改為num： =num+(min).

Step4在求出的函數(shù)限制中，判斷是否有不能用單個T門實現(xiàn)的非平凡子函數(shù)，若有，則重復(fù)step2～step3. 否則，輸出設(shè)計結(jié)果. 該算法的程序流程圖如圖2所示.

2.2 應(yīng)用案例

圖2 算法流程圖Fig.2 Flow-process diagram of algorithm

例用三值T門通用邏輯模塊實現(xiàn)4變量函數(shù)f的最小化T門網(wǎng)絡(luò)：

f=1·∑(1,12,13,14,15,16,17,25,28,30,36,39,42,43,44,45,46,48,50,52,55,69,70,71,72,77,79)+2·∑(6,7,8,21,22,23,26,32,33,34,35,53,54,60,61,62,66,67,68,73,75,80).

解算法的執(zhí)行過程如下：

Step1利用代數(shù)化簡法[10]，將待實現(xiàn)的函數(shù)f轉(zhuǎn)化為 RDSOP形式：

(12)

num： =1.

(N,1)

(N,2)

(N,3)

num： = num+3.

num： = num+4.

num： = num+3.

Step6在求得的函數(shù)限制中，若全為能用單個T門實現(xiàn)的非平凡子函數(shù)，則輸出設(shè)計結(jié)果.

所設(shè)計的T門組合網(wǎng)絡(luò)每級(從輸出級計算)所需的T門數(shù)目分別為1，3，4，3，共需11個T門.由求得的各個函數(shù)限制作待設(shè)計的T門邏輯網(wǎng)絡(luò)圖如圖3所示.

圖3 實例函數(shù)的最小化T門網(wǎng)絡(luò)實現(xiàn)Fig.3 The minimization T gate network of the implementation instance function

3 三值T門模塊電路設(shè)計和HSPICE仿真實驗

利用三值格代數(shù)的基本性質(zhì)和式(4)，由T門邏輯模塊表示的T運算(T算子)為

t=T(f0,f1,f2;x)=

(13)

實驗中的T門模塊電路用CMOS管實現(xiàn),式(13)表示T門模塊的邏輯表達式適合用NMOS管實現(xiàn). 利用PMOS管和NMOS管的互補性，可得用CMOS傳輸門實現(xiàn)T門模塊的表達式：

(14)

應(yīng)該指出，在圖4(a)所示的 T門邏輯模塊電路中，閾值邏輯部分采用傳統(tǒng)互補CMOS電路實現(xiàn)，共用12個MOS管.該電路中MOS管的扇出系數(shù)較大，輸出的各閾值邏輯信號可為控制變量相同的T門模塊電路中CMOS傳輸門MOS管的柵極信號公用.

采用HSPICE軟件和 TSMC 0.18 μm CMOS工藝模型，利用本文提出的T門模塊組成對如圖3所示的實例函數(shù)的最小化T門網(wǎng)絡(luò)進行仿真實驗.在仿真實驗中，共用124個MOS管，其中，NMOS管65個、PMOS管59個. 若采用文獻[8]提出的變

閾值設(shè)計的T門模塊電路來實現(xiàn)本文的T門網(wǎng)絡(luò)，則需132個MOS管，其中，NMOS管和PMOS管各66個. NMOS管和PMOS管的寬長比(W/L)分別為(0.36 μm /0.18 μm)和(0.72 μm /0.18 μm).電源VDD=1.8 V，邏輯值0,1,2，分別為0,0.9,1.8 V.輸出端上的負載電容為25 fF.仿真實驗的輸入和輸出波形如圖5所示. 由圖5可知，利用本文方法設(shè)計的最小化T門網(wǎng)絡(luò)可以完成正確的邏輯功能.

圖4 T門邏輯模塊的CMOS管電路實現(xiàn)Fig.4 The CMOS transistor circuit implementation of T gate logic module

圖5 實例函數(shù)的最小化T門網(wǎng)絡(luò)的仿真實驗波形Fig.5 Simulation experimental waveform of the minimization T gate network of the implementation instance function

4 結(jié) 論

利用三值格代數(shù)和三值T代數(shù)的基本運算和性質(zhì)，討論了求取待實現(xiàn)函數(shù)在其變量集上選取合適劃分的定理及其選取判據(jù). 基于此，提出了三值T門組合網(wǎng)絡(luò)設(shè)計(化簡)的一種混合控制變量排序算法，并給出了應(yīng)用實例. 本文算法可使待實現(xiàn)的三值T門網(wǎng)絡(luò)化簡到最小, 并減少了搜索次數(shù). 采用HSPICE軟件和 TSMC 0.18 μm CMOS工藝模型，利用本文設(shè)計的T門模塊電路，驗證了采用該算法設(shè)計的最小化T門組合網(wǎng)絡(luò)的邏輯功能是正確且有效的.