薛宏熙《数字逻辑设计》cha

2008.11,1,数字逻辑设计-谨供授课教师参考-欢迎批评指正-,清华大学计算机系薛宏熙xuehx,2008.11,2,第1章逻辑电路导论,【课前思考】【学习指南】1.1开关电路数学表示方法初步1.2逻辑代数1.3用“与”门、“或门”和“非”门进行逻辑综合1.4公式法化简逻辑函数1.5卡诺图1.6逻辑函数的标准形式1.7*表格法化简逻辑函数1.8解题示例【本章小结】,2008.11,3,1.1开关电路数学表示方法初步,例1.1楼梯照明灯的控制电路,2008.11,4,楼梯照明灯控制电路的真值表,2008.11,5,真值表的要点,真值表中的0和1仅代表逻辑命题的真或假，不代表数值的大小。设自变量的个数为n，则自变量取值的组合有2n种。真值表的行数为2n，每一行定义自变量在该种取值组合下函数的值。由此可以得出2个结论：（1）真值表可以唯一地定义一个逻辑函数，若函数f与g的真值表相同，则f与g等价。（2）当n的数值很大时，真值表的规模急剧增大，这是真值表的缺点。,2008.11,6,真值表的习惯表示方法,输入变量的排序可由设计者任意指定，如果是变量组的话，可以采用升序，例如；也可以采用降序，例如2.真值表的第1列（行号）是可有可无的，本书中有时加上行号是为了文字叙述的方便。3.输入变量取值的组合可以转换为对应的二进制数，可令此二进制数和行号对应起来。于是，输入变量取值的组合可以表示为mi,其下标i恰是对应的行号。例如，输入变量a,b取值为10时，可表示为m2。,2008.11,7,分析与综合,分析（analysis）：由已知电路推导其电路的功能。例1.1楼梯照明灯控制电路导出其功能表，是分析的过程。引入真值表。综合（synthesis）：由给定的功能描述推导其电路实现。由真值表推导其电路实现，需要引入其它的数学工具，逻辑代数（布尔代数）便是其中之一。,2008.11,8,1.2逻辑代数,英国数学家乔治布尔（GeorgeBoole）提出了逻辑代数的基本形式和概念，将形式逻辑问题归结为一种代数运算，被人们称为布尔代数（Booleanalgebra），即我们所说的逻辑代数。1.2.1逻辑代数的基本运算：“与”运算,2008.11,9,逻辑代数（续）,1.2.1逻辑代数的基本运算：“或”运算,2008.11,10,逻辑代数（续）,1.2.1逻辑代数的基本运算：“非”运算,2008.11,11,逻辑代数（续）,1.2.1逻辑代数的基本运算：逻辑运算符的优先级：逻辑运算符的优先级由高到低依次为：“非”“与”“或”。在有括号的情况下，先括号内后括号外；先内层后外层。与基本运算对应的逻辑门：,2008.11,12,逻辑代数（续）,1.2.2逻辑函数：逻辑函数的表示方法：真值表；由变量、常量以及逻辑运算符构建的逻辑表达式。逻辑函数的等价性判断：真值表形式具有唯一性：若函数f与g的真值表相同，则f与g等价。反之，二者不等价。逻辑表达式不具有唯一性：若函数f与g的逻辑表达式相同，则f与g等价；反之，若函数f与g的逻辑表达式不同，则f与g可能等价也可能不等价。,2008.11,13,逻辑代数（续）,1.2.3逻辑代数的基本公式和运算规则：逻辑代数的基本公式：,2008.11,14,逻辑代数的基本公式（续）,2008.11,15,逻辑代数的基本公式（续）,2008.11,16,逻辑代数的基本公式（续）,上述公式具有对偶性：把a组公式中的运算符“”替换成“+”，把运算符“+”替换成“”，把常数0替换成1，把常数1替换成0，将得到b组的对应公式。对b组中的公式作同样的替换，将得到a组的对应公式。,2008.11,17,公式证明举例,【例1.2】用真值表法证明公式（1-9b）的正确性。令等式两边的逻辑表达式分别用函数f和g表示：,2008.11,18,公式证明举例（续）,【例1.3】用公式法证明公式（1-13a）的正确性。【证】,2008.11,19,逻辑代数的基本规则,对偶规则的应用：设函数f的对偶式记作f，函数g的对偶式记作g。若函数f与g等价，则其对偶式f与g也等价。对函数f执行2次对偶变换，将得到函数f本身。代入规则：对于一个已经成立的等式，若将其中某个变量x用另一个逻辑表达式f代替，则等式仍然成立。分解规则：香农展开定理（ShannonsExpansionTheorem）可称为分解规则，即任何一个逻辑函数都可以重新表示为,子函数（f0,f1）的变量个数减少！,2008.11,20,逻辑代数的基本规则（续）,分解规则应用举例：,2008.11,21,逻辑代数的基本规则（续）,反演规则：德摩根定律的一般形式称为反演规则,2008.11,22,1.3用与门、或门和非门进行逻辑综合,实例：待综合函数的真值表逻辑表达式逻辑表达式电路图,2008.11,23,1.4公式法化简逻辑函数,求最简的“积之和”表达式：表达式中含乘积项个数最少。在满足上述条件下，每个乘积项所含变量个数最少。举例：1.合并乘积项法：利用基本公式（111a）2.吸收法：利用基本公式（110b）3.消去法：利用基本公式（19b）,2008.11,24,公式法化简逻辑函数（续）,举例：4.添加项法：利用基本公式（14b）5.配项法：利用互补律，基本公式（15b）,2008.11,25,公式法化简逻辑函数（续）,优点：用逻辑表达式描述数字电路的功能，是理论上的重大贡献。优化逻辑表达式优化逻辑电路。缺点：化简过程无一定规律可循，需要经验和技巧，灵活、交替地使用各种方法。不易判断是否已经达到最简形式。需要寻找更好的方法。,2008.11,26,1.5卡诺图化简逻辑函数,卡诺图是真值表的图形表示卡诺图中1个小方格对应于真值表中的1行。,2008.11,27,卡诺图化简逻辑函数（续）,名词术语：乘积项（productterm，简称积项）变量以原变量或反变量的形式出现，多个变量之间执行“与”操作而构成乘积项。文字（literal）乘积项中的变量或该变量的反变量称作一个文字。最小项（minterm）对于n变量的逻辑函数来说，若某个乘积项中包含的文字个数为n，则称该乘积项为最小项。换句话说，若每一个变量或以原变量形式、或以反变量形式在一个乘积项中出现1次、且仅出现1次，则该乘积项是最小项。最小项对应于卡诺图中的一个小方格，它可以表示为n个变量之积，也可以记作mi。例如最小项的另一个等价表示形式是m1。最大项（maxterm）对于n变量的逻辑函数来说，若某个“或”项中包含的文字个数为n，则称该“或”项为最大项。,2008.11,28,卡诺图化简逻辑函数（续）,举例：最小项的性质：全体最小项之和（“或”运算）为1。任意2个最小项互不相交，故任意2个最小项之积（“与”运算）为0。若2个最小项之间只有1个文字不同，即在一个最小项中该文字为原变量，而在另一个最小项中该文字为反变量，则称这2个最小项“逻辑相邻”。根据公式（1-11a），逻辑相邻的2个最小项可以合并为1个乘积项，并且合并所得乘积项中的文字个数减少1个。卡诺图是把逻辑相邻的最小项尽量安排成几何位置相邻，通过观察即可判定哪些最小项可以合并。,2008.11,29,卡诺图化简逻辑函数（续）,举例：,2008.11,30,卡诺图化简逻辑函数（续）,逻辑相邻与几何相邻：2个逻辑相邻的乘积项在卡诺图中表现为几何位置的相邻，使我们通过观察图形即可实现块的合并，达到化简逻辑函数的目的。可以把卡诺图想象为一张图纸，将其卷成一个圆筒，则原来两边不相邻的部分就变成相邻的部分了。,2008.11,31,卡诺图化简逻辑函数（续）,5变量卡诺图：,变量个数5时，很难画出对应的卡诺图！,2008.11,32,卡诺图化简逻辑函数（续）,概念提升：蕴含项（implicant）若某乘积项能指明输入变量的取值组合可使给定逻辑函数f取值为1，则该乘积项是函数f的蕴含项。蕴含项的包含关系（contain）设蕴含项A由相邻最小项集合Sa合并而成，蕴含项B由相邻最小项集合Sb合并而成。若，即Sa中的每一个最小项都存在于Sb中，则称蕴含项B包含蕴含项A，记作。质蕴含项（primeimplicant）若某蕴含项不被其他任何一个蕴含项所包含，则该蕴含项是质蕴含项。在卡诺图中，若某个由相邻最小项构成的块已经是维数最大的块，不被其它任何一个块所包含，则该块对应的乘积项是质蕴含项。,2008.11,33,卡诺图化简逻辑函数（续）,概念提升：特征最小项和必要质蕴含项（essentialprimeimplicant）若某最小项仅被唯一的一个质蕴含项所包含，则该最小项称为特征最小项，包含特征最小项的质蕴含项称为必要质蕴含项。,2008.11,34,卡诺图化简逻辑函数（续）,概念提升：覆盖（cover）若一个蕴含项的集合能说明给定逻辑函数f为1的所有情况，则称此蕴含项集合是函数f的覆盖。覆盖和函数的“积之和”表达式相对应。最小覆盖（minimalcover）函数的最小覆盖和成本最低的“积之和”表达式相对应，其要求为：1.最小覆盖中包含的蕴含项个数最少。2.每一个蕴含项的文字个数尽量少，即蕴含项的维数尽量大。必要质蕴含项必定是最小覆盖的元素。无冗余覆盖（non-redundantcover）1.覆盖中每一个蕴含项必须是质蕴含项。2.覆盖中不含冗余项。当变量个数很多时，若求解函数的最小覆盖有困难，可退而求其次，转而求无冗余覆盖。,2008.11,35,卡诺图化简逻辑函数（续）,概念提升：冗余项（redundantterm）设A是覆盖C中的一个蕴含项，若A所包含的每一个最小项皆存在于C中其它的蕴含项之中，则称A是相对于覆盖C的冗余项。换句话说，没有独立贡献的蕴含项是冗余项。,2008.11,36,1.6逻辑函数的标准形式,函数的积之和表达式:式（1-19）和式（1-20）都是积之和表达式。式（1-19）中每一个乘积项都是最小项，被称为积之和的标准形式。积之和标准形式的另一种表示方法：,2008.11,37,1.6逻辑函数的标准形式,函数的和之积与积之和表达式:将反演规则施加于式（1-19）：若函数，则,和之积表达式,2008.11,38,逻辑函数的标准形式（续）,最大项与最小项的对应关系：,2008.11,39,逻辑函数的标准形式（续）,最大项与最小项的对应关系：和之积标准形式的另一种表示方法：,2008.11,40,包含无关项的逻辑函数的化简,【例1.10】父亲、母亲为小女儿买一件衣服，是否购买取决于3个人对该商品的态度：3人全部赞成则购买；2人赞成则可买可不买；1人赞成或无人赞成则不买。,2008.11,41,包含无关项的逻辑函数的化简（续）,用卡诺图化简不完全确定的逻辑函数d的取值可为0也可为1，以简化效果最佳为目的。本例化简结果为：,2008.11,42,包含无关项的逻辑函数的化简（续）,【例1.11】假定用4位二进制代码表示1位十进制数，判断此种十进制数的值是否大于等于5。,2008.11,43,包含无关项的逻辑函数的化简（续）,【例1.11】逻辑表达式化简结果：,2008.11,44,1.7*表格法化简逻辑函数,WillaredQuine和EdwardMcCluskey在二十世纪五十年代提出了表格法化简逻辑函数，表格法也因而被称为Quine-McCluskey法，简称Q-M法。表格法的优点：变量的个数不受限制，适合于多变量逻辑函数的化简。规律性很强，可以写出严格的算法。表格法的缺点：当函数的变量很多时，手工操作仍不胜其烦。计算机程序擅长于处理多重循环和复杂的操作，所以它适合于编写逻辑综合软件。与其它逻辑综合算法相比较，表格法出现较早，不是最高效的却是最简单的。学习表格法的目的：了解EDA工具的工作原理，从而更好地使用EDA工具。有助于学习更先进的逻辑综合算法。,2008.11,45,表格法化简逻辑函数（续）,表格法化简逻辑函数的步骤：1.从函数的真值表描述求出其全部质蕴含项的集合，记作Z。2.从质蕴含项集合Z中挑选出一个子集M，要求M是最小覆盖。即（1）M覆盖全部最小项。至于无关项，属于可覆盖、可不覆盖之列。（2）M的成本最低。,2008.11,46,求质蕴含项集合Z的算法流程图,2008.11,47,用表格法求函数的质蕴含项集合Z的实例（例1.12）,step1建立初始表格（表1.10）：求质蕴含项集合时，可对最小项和无关项不加区分，一律用mi表示。按0维块中含“1”的个数将其分组，组号即该0维块中含“1”的个数，分组的目的是为了提高“逐对”比较的效率，因为相邻块只可能在相邻组中出现。,若某个0维块被后续形成的1维块包含，则用“”作标记。,2008.11,48,用表格法求函数的质蕴含项集合Z的实例（续）,step2相邻块合并：表1.11,2008.11,49,用表格法求函数的质蕴含项集合Z的实例（续）,step2相邻块继续合并：表1.12凡是没有标记“”的蕴含项都是质蕴含项，从而构成全部质蕴含项集合Z。为了下一步求最小覆盖的方便，我们用速记符标记每一个质蕴含项，分别写在表1.11和表1.12的第4列。即P1,P2,P3,P4,P5,P6,2008.11,50,*求最小覆盖,2008.11,51,求最小覆盖的实例（例1.13）,例1.12已经求出了函数f的质蕴含项集合Z，现在求其最小覆盖。step1建立初始表格：建立质蕴含项覆盖表（表1.13）。每一个质蕴涵项在表中占据一行，每一个应被覆盖的最小项在表中占据一列，然后用标志符“”指明该最小项被哪些质蕴涵项所覆盖。,2008.11,52,求最小覆盖的实例（续）,Step2选优：如果表1.13某列中只有一个标志符“”，则覆盖该最小项的质蕴涵项是必要质蕴涵项，它必须被包含在所求的最小覆盖中。对于本例，p6是必要质蕴涵项，将p6加入M。将对应于必要质蕴涵项p6的行以及被p6覆盖的列（m0，m4，m8，m12）从表中删除，,2008.11,53,求最小覆盖的实例（续）,Step2选优继续：删除必要质蕴含项P6之后,2008.11,54,求最小覆盖的实例