三值T门组合网络自动综合的理论和算法

姜恩华， 姜文彬

(淮北师范大学 物理与电子信息学院， 安徽 淮北 235000)

0 引 言

随着集成电路工艺特征尺寸的缩小和芯片中器件面积的减小，电路布线所占面积增大. 多值逻辑电路因携带的信息密度较高，可减少电路连线，节省芯片面积. 因此，研究多值逻辑电路与系统设计具有重要意义. 文献[1]基于多值代数提出了用于多值数字电路设计的CMOS门通用集，并应用于四路选择器和四值触发器的设计与实现. 文献[2]利用多值逻辑(四值逻辑)模代数运算，提出模4中的算术运算及其CMOS电路实现. CMOS动态三值逻辑电路[3]、纳米场效应管三值逻辑门和算术运算电路[4]、纳米场效应管三值全加器电路[5]、单电子晶体管(single electron transistor，SET)和MOSFET组合构成的多值逻辑电路和存储电路[6]，受到了较多关注.目前，多值逻辑CMOS集成电路由二值CMOS集成电路实现. 文献[7]提出了一种新的CMOS传输管逻辑电路和互补CMOS逻辑电路混合型的高速CMOS二值全加器电路. 三值T门是一种通用逻辑模块(器件)，利用三值T门模块可实现任意三值逻辑函数. 根据多值逻辑电路设计原理[8]，将三值T门电路分为阈门逻辑电路和三值逻辑信号传输电路两部分. 用CMOS传输门可构成三值T门的信号传输电路部分. 阈门逻辑电路可将三值逻辑信号转换为二值逻辑信号，并作为CMOS传输门的栅极信号. 基于上述原理，本文提出了三值T门模块电路的设计，该模块是用二值CMOS管设计的，其三值信号传输部分由CMOS传输门实现，阈值逻辑信号产生部分由互补CMOS电路实现，即采用混合型逻辑电路构建. 不同于文献[8]提出的三值T门电路，本文提出的三值T门电路未用变阈值MOS管.

三值T 门逻辑网络的化简(最小化)及其计算机算法，是三值逻辑电路与系统领域一个重要的研究课题. 文献[9]提出了基于多值T门组合电路模块分解方法的多值T门电路化简方法. 文献[10]研究了三值逻辑函数简化的不相交积之和(reduced disjoint sum-of-products，RDSOP)形式的代数理论，提出采用混合控制变量排序的三值T门组合网络的化简和设计的一种代数方法. 但在该文给出的算法的第2步，求取待实现函数在其变量集上合适的划分，缺少相关定理和选取依据. 本文基于三值逻辑函数RDSOP形式的代数理论，讨论求取待实现函数在其变量集上选取合适划分的相关定理及其选取依据，提出三值T门组合网络设计(化简)的一种混合控制变量排序算法，该算法可使待设计的三值T门网络最小化，易实现三值T门组合网络的自动综合. 将该三值T门模块用于三值T门网络的仿真实验，结果表明，该三值T门网络的逻辑功能正确，算法有效.

1 三值格代数系统和三值T代数系统的基本运算和定理

设逻辑值集合为L={0，1，2}，全序关系为 2>1>0.对于变量x,y∈L及常量j∈L，引进具有补运算的三值格代数系统，“或”(取大)、“与”(取小)、“阈”(文字)3种基本运算和补运算[8]，分别为

(1)

(2)

式中，符号“-”为算术减法运算，符号“·”可以省略. 式(1)的3种基本运算已构成代数完备系统，即三值格代数系统. 由式(1)和式(2)组成含有冗余运算的三值格代数系统.在该代数系统中，0 与2互补，1自补.为了简化符号，常将jxj简记为xj.由式(1)和式(2)，易证得下述性质：

三值T门实现的T运算(T算子)定义为[9]

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

(3)

式中x,fi∈{0,1,2}，其中x为T门的控制(地址)变量，fi,0≤i≤2为T门的数据输入.式(3)所示的T运算构成一个代数完备系统，即三值T代数系统.在三值格代数系统中，式(3)可表示为

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

(4)

在三值格代数系统中，设有一个定义在变量集X={x1,x2,…,xn}上的n变量三值函数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.将香农(Claude E. Shannon)展开定理推广到三值格代数系统，对于上述函数及划分式(5)，则有[8]

(6)

(7)

(8)

(9)

三值函数中所含变量的个数n定义为该函数的Ln空间(超立方体)的维数，称为该函数的维数，并称该函数为n维函数.一个n维函数在空间Ln上共有3n个点.每个点的变量取值，对应于相应文字组成的最小项.函数值为0的点(0值点)对应的最小项(0值最小值)在该函数表达式中可以不列出.1值点和2值点

分别对应于该函数所含的 1值最小项和2值最小项.用该函数中全部最小项表示的式子称为该函数的最小项表达式，其中，0值最小值可忽略不计.最小项表达式也称最小项展开式，可通过对该函数的每个变量依次利用推广的展开定理即式(6)展开得到.例如，一个二变量三值函数的最小项表达式为

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}，该函数可用二维平面中的点表示，如图1所示，其中0值最小值可省略.

图1 二变量函数的平面图形表示Fig.1 The plane graphic representation of the two variable functions

对于定义在变量集X={x1,x2,…,xn}上的n变量三值函数f，将X中的变量排序后划分为

(10)

对子集B1中的每个变量，依次利用推广的展开定理即式(6)，可导出该函数按照划分式(10)的展开式为

(11)

在一个n变量三值函数的RDSOP形式[10]中，一个积项p所含该函数的最小项数目称为该函数的尺度(大小)，用符号“‖p‖”表示.例如，一个文字xij，j∈{0,1,2}，i∈{1,2,…,n}，所含该函数的最小项数目为‖xij‖=3n-1.

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

必要性. 若fpk=d∈{1,2}，由式(8)可知，fpk中只含除pk中l个不同变量外的其余变量，共(n-l)个变量，组成3n-l个子最小项，且这些子最小项之和为2.而将积项fpk·pk展开成f的最小项之和为fpk·pk=d·2·pk，将该式右边的逻辑值2以上述3n-l个子最小项之和代入后，可得该积项d·pk含有函数f的3n-l个d值最小项，即‖(d·pk)‖=3n-l.证毕.

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

证明由式(11)、定理1和定理2，可推得该推论成立.

需注意，对某个(或某些)pq，若有‖(da·pa)‖=‖(dq·pq)‖，可推得fpq=dq为平凡子函数，此时，pq中变量集X含有不同文字的数目也为l个.

证明由式(11)和定理1，可推得该推论成立.

由推论1和推论2，求得平凡子函数的维数为(n-l)，称之为(n-l)维平凡子函数.可以看出，平凡子函数的维数越高，对T门网络化简越有利.对于混合控制变量排序算法，T门网络化简(最小化)目标是在待实现函数的每级网络中，使待实现函数按照扩展的展开定理即式(6)展开后得到的非平凡子函数类型(nontrivial sub-function patterns，NTSP)的数目最小，此时得到的T门网络称为最小化T门网络.

2 三值T门组合网络设计实例

2.1 三值T门组合网络设计步骤

Step1将待实现的函数化为 RDSOP形式.并对所用T门数目的变量num 赋初值num： =1.

Step2由推论1和推论2，求取该函数变量集X上(或求取该函数每个不能用单个T门实现的非平凡子函数关于X的子集上)合适的划分，使函数(或相关子函数)按照扩展的展开定理即式(6)展开后得到的非平凡子函数类型数目最小(min).

Step3利用限制运算，按照所选划分，求出各函数限制.检验各函数限制是否能用单个T门实现： “N”( 非平凡子函数类型的序数)表示不能用单个T门实现，“S”(非平凡子函数类型的序数)表示能用单个T门实现.将表示所用T门数目的变量num之值修改为num： =num+(min).

Step4在求出的函数限制中，判断是否有不能用单个T门实现的非平凡子函数，若有，则重复step2～step3. 否则，输出设计结果. 该算法的程序流程图如图2所示.

2.2 应用案例

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

例用三值T门通用逻辑模块实现4变量函数f的最小化T门网络：

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).

解算法的执行过程如下：

Step1利用代数化简法[10]，将待实现的函数f转化为 RDSOP形式：

(12)

num： =1.

(N,1)

(N,2)

(N,3)

num： = num+3.

num： = num+4.

num： = num+3.

Step6在求得的函数限制中，若全为能用单个T门实现的非平凡子函数，则输出设计结果.

所设计的T门组合网络每级(从输出级计算)所需的T门数目分别为1，3，4，3，共需11个T门.由求得的各个函数限制作待设计的T门逻辑网络图如图3所示.

图3 实例函数的最小化T门网络实现Fig.3 The minimization T gate network of the implementation instance function

3 三值T门模块电路设计和HSPICE仿真实验

利用三值格代数的基本性质和式(4)，由T门逻辑模块表示的T运算(T算子)为

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

(13)

实验中的T门模块电路用CMOS管实现,式(13)表示T门模块的逻辑表达式适合用NMOS管实现. 利用PMOS管和NMOS管的互补性，可得用CMOS传输门实现T门模块的表达式：

(14)

应该指出，在图4(a)所示的 T门逻辑模块电路中，阈值逻辑部分采用传统互补CMOS电路实现，共用12个MOS管.该电路中MOS管的扇出系数较大，输出的各阈值逻辑信号可为控制变量相同的T门模块电路中CMOS传输门MOS管的栅极信号公用.

采用HSPICE软件和 TSMC 0.18 μm CMOS工艺模型，利用本文提出的T门模块组成对如图3所示的实例函数的最小化T门网络进行仿真实验.在仿真实验中，共用124个MOS管，其中，NMOS管65个、PMOS管59个. 若采用文献[8]提出的变

阈值设计的T门模块电路来实现本文的T门网络，则需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可知，利用本文方法设计的最小化T门网络可以完成正确的逻辑功能.

图4 T门逻辑模块的CMOS管电路实现Fig.4 The CMOS transistor circuit implementation of T gate logic module

图5 实例函数的最小化T门网络的仿真实验波形Fig.5 Simulation experimental waveform of the minimization T gate network of the implementation instance function

4 结 论

利用三值格代数和三值T代数的基本运算和性质，讨论了求取待实现函数在其变量集上选取合适划分的定理及其选取判据. 基于此，提出了三值T门组合网络设计(化简)的一种混合控制变量排序算法，并给出了应用实例. 本文算法可使待实现的三值T门网络化简到最小, 并减少了搜索次数. 采用HSPICE软件和 TSMC 0.18 μm CMOS工艺模型，利用本文设计的T门模块电路，验证了采用该算法设计的最小化T门组合网络的逻辑功能是正确且有效的.