逻辑综合中的基本概念.doc

1. 逻辑综合 (Logic Synthesis) EDA工具把数字电路的功能描述(或结构描述)转化为电路的结构描述。实现上述转换的同时要满足用户给定的约束条件，即速度、功耗、成本等方面的要求。2. 逻辑电路(Logic Circuit)逻辑电路又称数字电路，在没有特别说明的情况下指的是二值逻辑电路。其电平在某个阈值之上时看作高电平，在该阈值之下时看作低电平。通常把高电平看作逻辑值1；把低电平看作逻辑值0。3. 约束(restriction)设计者给EDA工具提出的附加条件，对逻辑综合而言，约束条件一般包括速度、功耗、成本等方面的要求。4. 真值表(Truth Table)布尔函数的表格描述形式，描述输入变量每一种组合情况下函数的取值。输入变量组合以最小项形式表示，函数的取值为真或假(1 或0)。5. 卡诺图(Karnaugh Map)布尔函数的图形描述形式，图中最小方格和最小项对应，两个相邻的最小方格所对应的最小项只有一个变量的取值不同。卡诺图适合于用观察法化简布尔函数，但是当变量的个数大于4时，卡诺图的绘制和观察都变得很困难。6. 单输出函数(Single-output Function)一个布尔函数的单独描述。 7. 多输出函数(Multiple-output Function)输入变量相同的多个布尔函数的统一描述。8. 最小项(Minterm) 设a1,a2,ai,an是n个布尔变量，p为n个因子的乘积。如果在p中每一变量都以原变量ai或反变量的形式作为因子出现一次且仅出现一次，则称p为n个变量的一个最小项。最小项在卡诺图中对应于最小的方格；在立方体表示中对应于顶点。9. 蕴涵项(Implicant) 布尔函数f的与-或表达式中的每一乘积项都叫作f的蕴涵项。例如：f=+中的乘积项和都是函数f的蕴涵项。蕴涵项对应于立方体表示法中的立方体。10.质蕴涵项(Prime Implicant，PI) 设函数f有多个蕴涵项，若某个蕴涵项i所包含的最小项集合不是任何别的蕴涵项所包含的最小项集合的子集的话，则称i为函数f的质蕴涵项。质蕴涵项对应于立方体表示法中的质立方体。11.必要质蕴涵项(Essential Prime Implicant，EPI )若某个最小项只被一个质蕴涵项所包含，则称此最小项为特征最小项，包含特征最小项的质蕴涵项为必要质蕴涵项，在布尔函数最小化的过程中，必要质蕴涵项是必须选取的。必要质蕴涵项对应于立方体表示法中的必要质立方体。12.不顾项(Dont care) dont care的中文译名有：不顾项、任意项和随意项等，其主要含义是该最小项的取值可以是1或0中的任意一个。从化简布尔函数的角度来看，终选1还是选0取决于怎样对化简有利。13.完全规定的布尔函数(Completely Specified Boolean Function)若某布尔函数不包含不顾项，则它是一个完全规定的布尔函数。14.不完全规定的布尔函数(Incompletely Specified Boolean Function)若某布尔函数包含有不顾项，则它是一个不完全规定的布尔函数。15.立方体(Cube)在逻辑综合领域中，立方体是布尔函数的空间图形表示形式。设布尔函数的一般表示形式为：y=f(x1,x2,xi,xn)其中y为输出变量， 为输入变量。令每一输入变量和一个坐标轴相对应，则可得到函数y的空间图形。16.顶点(Vertex)顶点是立方体的一种特殊情况，其输入变量取值为0或1，其输出变量除一个取值为0或1之外，其余取值皆为u。也就是说，顶点只建立起输入变量和一个输出变量之间的对应关系。17.覆盖(Cover ) 输入、输出变量相同的，逐对一致的非退化立方体集合称为覆盖。覆盖C中每一立方体所包含的每一顶点都表示了输入变量和输出变量的对应关系，因此整个覆盖C就代表了布尔函数f。覆盖是真值表的一种扩展；而真值表则是覆盖的一种特殊情况。18.包含(Contain) 若顶点v|w可由下述方法从立方体a|b中得到，则称a|b包含v|w，记作：v|wa|b(1) 把a中取值为X者适当地改为0或1。(2) b中只保留一个取值为0或1者，其余取值为0或1者皆改为u。若立方体c|d的每一顶点都被立方体a|b所包含，则称立方体a|b包含立方体c|d，记作；c|da|b19.面(Face) 若立方体a|b包含立方体c|d，则称c|d是a|b的一个面。20.相交运算(intersection)单输出函数的立方体a和立方体c的交是它们的公共顶点所组成的立方体。多输出函数的立方体a|b 和立方体c|d的交是单输出函数交运算的扩展，但多输出函数的交运算不再具有公共顶点的含义。我们只把它看作一种有用的运算，可用于一致性判断。21.一致性(Consistence) 两个立方体作相交运算时，若其输出部分出现q而其输入部分不出现q的话，则称此二立方体是不一致的，反之，它们是一致的。一致性就是不矛盾性。用真值表描述布尔函数时不会出现不一致性，因为真值表中是对每一个最小项分别进行描述。用覆盖描述布尔函数时就可能出现不一致性，因为覆盖中是对每一个立方体分别进行描述。一个立方体可能包含多个最小项，一个最小项可能被多个立方体包含。如果不小心，某个最小项的取值可能在这里被隐式定义为1，而在另外一个地方被隐式定义为0。如果出现这种前后矛盾的原始描述，后续工作就无法进行。因此在作逻辑综合之前，首先应对原始数据作一致性检查。若发现不一致性，则应纠正原始数据中的错误。22.吸收 (Absorption) 运算吸收运算的目的是：在不改变覆盖所描述的函数性质的前提下减少覆盖中元素的个数。令C = S(C )代表对覆盖C作吸收运算，C 代表运算结果。其含义是：(1)若ci cj且ci, cjC则删去ci。(2)若ci C，且其输出部分取值全部为u，则删去ci。23.余面(Coface) 设c是属于覆盖C的一个立方体。如果：(1) c是立方体e的一个面，即：c e(2) e和覆盖C中的每一立方体相一致。则说e是c的(相对于覆盖C)一个余面。24.立方复合体(Cubical Complex) 覆盖C的立方复合体K(C)可由下述规则形成：(1) 覆盖C中的每一立方体都属于K。 (2) 设e是K中的一个立方体，则e的面以及相对于覆盖C的余面都属于K。通常情况下并不需要真的去求立方复合体，而是利用立方复合体的概念去阐述其他概念。25.锐积(Sharp Product) 运算令a 、b是单输出函数的2个立方体，锐积运算a # b的结果是一个立方体的集合C。由a包含的顶点减去a ? b包含的顶点所形成的维数最大的立方体都是C的元素。K0(C)=K0(a)-k0(a)K0(b)上面的表达式说明锐积的本质是顶点集合求差。26.星积(Star Product)运算设a和b是单输出函数的2个立方体，星积运算a * b的结果是一个新立方体c，c既不被a包含也不被b包含，c是被ab包含的顶点所构成的最大的一个立方体(c也可以为)。星积运算的特点是根据两个已知的立方体求一个新立方体，新立方体一定和原来的立方体不同。新立方体的维数可能增大也可能不增大，但是通过反复作星积运算就有可能求出维数更大的立方体。27.最小化覆盖(Minimum Cover)设初始覆盖为C，最小化覆盖M应满足以下要求：(1) M和C等价，即：MCOFF=CON#M=(2) M中所有元素都是质立方体。即；(3) M的成本最低。28.无冗余覆盖(Non-redundant Cover)设初始覆盖为C，无冗余覆盖N应满足以下要求：(1) N和C等价(2) N中所有元素都是质立方体(3) N中不存在冗余元素。即ni#(N-ni)CON niN29.极值(Extremal) 设SZ是质立方体集合Z的一个子集，e是SZ的一个元素，若e包含了某个不被SZ中其它元素所包含的真值顶点，则称e为极值。若： e#(SZ-e)CCeSZ (4-13)则e是一个极值。式中CC是立方体的集合，它包含且仅包含全部待包含的真值顶点，用选拔法实现最小化覆盖时，极值应当被选为M的元素。理由是每个真值顶点都应当被M包含，而包含该真值顶点的诸立方体中，e的成本最低，因为质立方体和它的面相比成本较低。 30.小于运算(Less Than) 小于运算是对覆盖A中的元素逐对进行比较，设被比较的两个元素是ai和aj，若：(1) ai的成本aj的成本(2) (ai#aj)CC=则说ai小于(劣于)aj，并从A中把ai删除。由此可知，小于运算实际上是删劣运算。 31.扇入(Fan In)逻辑门的输入端数。32.扇出(Fan Out)逻辑门的等价负载数。33.先农展开定理(Shannons Expansion Theorem) 先农展开把一个函数展开为2个函数的或，而这2个函数的输入变量个数都比原来的函数减少了1个，降低了复杂性。34.二叉判决图(Binary Decision Diagram, BDD)二叉判决图是基于先农展开的图形表示，当把输入变量的顺序排定之后。BDD就变成有序的BDD(Orded BDD, OBDD)。OBDD适合于计算机作业。OBDD已经应用于多级逻辑综合和形式验证。35.组合逻辑电路(Combinational Logic Circuit)组合逻辑电路输出信号的取值仅仅依赖于输入信号的当前值。36.时序逻辑电路(Sequential Logic Circuit)时序逻辑电路输出信号的取值不仅依赖于输入信号的当前值；还依赖于输入信号的历史值。37.有限状态机(Finite State Machine, FSM)时序逻辑电路的数学模型。有限二字限定该状态机的状态数不能是无限大。38.完全规定的有限状态机(Completely Specified FSM)状态表中若在每一输入组合情况下，其次态和输出都是唯一确定的，则称该有限状态机为完全规定的有限状态机。 不完全规定的有限状态机(Incompletely Specified FSM)状态表中若在每一输入组合情况下，其次态和输出不是唯一确定的，则称该有限状态机为不完全规定的有限状态机。所谓不确定是指次态一栏出现了未明确指定的状态(用?表示)；或输出一栏出现了未明确指定的值(用u表示)。39.状态化简(State Minimization)在不改变有限状态机性质的前提下，尽量把原始描述中的状态合并以减少状态的数量。40.状态分配(State Allocation)统一考虑给有限状态机的每一个状态分配一个代码，目标是造价最低。 41.等价状态对(Pair of Equivalent States)设状态si , sj 是某完全规定的有限状态机状态集合S中的两个状态，分别对其施加各种可能的输入组合Ip，若同时满足以下条件：(1)输出完全相同，即Z(si , Ip)= Z(sj , Ip) (IpI , si , sjS ) (=表示相同)(2)后继状态等价，即N(si , Ip)= N(sj , Ip) (IpI , si , sjS ) (=表示等价)则称si , 和sj 等价，它们是等价状态对。42.等价类(Equivalent Class)设S k是某完全规定的有限状态机状态集合的一个子集，若其中任意两个状态都?quot;等价状态对，则称S k为等价类。43.最大等价类(Maximum Class of Equivalent States)不被其它等价类所包含的等价类称为最大等价类。在完全规定的有限状态机的状态最小化运算中，可以把一个等价类归并为一个状态。44.相容状态对(Pair of consistent State)设状态si , sj是某不完全规定的有限状态机状态集合S中的两个状态，分别对其施加各种可能的输入组合Ip，当且龅痹谧刺碇忻魅饭娑牡