三值T門組合網(wǎng)絡(luò)自動(dòng)綜合的理論和算法

姜恩華， 姜文彬

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

0 引 言

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

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

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

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

(1)

(2)

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

三值T門實(shí)現(xiàn)的T運(yùn)算(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運(yùn)算構(gòu)成一個(gè)代數(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è)有一個(gè)定義在變量集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)，對(duì)于上述函數(shù)及劃分式(5)，則有[8]

(6)

(7)

(8)

(9)

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

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

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ù)可用二維平面中的點(diǎn)表示，如圖1所示，其中0值最小值可省略.

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

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

(10)

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

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 應(yīng)用案例

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

例用三值T門通用邏輯模塊實(shí)現(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í)行過(guò)程如下：

Step1利用代數(shù)化簡(jiǎn)法[10]，將待實(shí)現(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ù)限制中，若全為能用單個(gè)T門實(shí)現(xiàn)的非平凡子函數(shù)，則輸出設(shè)計(jì)結(jié)果.

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

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

3 三值T門模塊電路設(shè)計(jì)和HSPICE仿真實(shí)驗(yàn)

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

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

(13)

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

(14)

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

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

閾值設(shè)計(jì)的T門模塊電路來(lái)實(shí)現(xiàn)本文的T門網(wǎng)絡(luò)，則需132個(gè)MOS管，其中，NMOS管和PMOS管各66個(gè). NMOS管和PMOS管的寬長(zhǎng)比(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.輸出端上的負(fù)載電容為25 fF.仿真實(shí)驗(yàn)的輸入和輸出波形如圖5所示. 由圖5可知，利用本文方法設(shè)計(jì)的最小化T門網(wǎng)絡(luò)可以完成正確的邏輯功能.

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

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

4 結(jié) 論

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