数字逻辑技术CHAP1.ppt

1、2008.11,1,数字逻辑设计- 谨供授课教师参考 - - 欢迎批评指正 -,清华大学计算机系 薛宏熙 ,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 仅代表逻

2、辑命题的真或假，不代表数值的大小。 设自变量的个数为n，则自变量取值的组合有2n种。真值表的行数为2n，每一行定义自变量在该种取值组合下函数的值。由此可以得出2个结论： （1）真值表可以唯一地定义一个逻辑函数，若函数 f与 g 的真值表相同，则 f 与 g 等价。 （2）当 n 的数值很大时，真值表的规模急剧增大，这是真值表的缺点。,2008.11,6,真值表的习惯表示方法,输入变量的排序可由设计者任意指定，如果是变量组的话，可以采用升序，例如； 也可以采用降序，例如 2. 真值表的第1列（行号）是可有可无的，本书中有时加上行号是为了文字叙述的方便。 3. 输入变量取值的组合可以转换为对应的二

3、进制数，可令此二进制数和行号对应起来。于是，输入变量取值的组合可以表示为m i ,其下标 i 恰是对应的行号。 例如，输入变量a, b取值为10时，可表示为m2。,2008.11,7,分析与综合,分析（analysis）：由已知电路推导其电路的功能。 例 1.1 楼梯照明灯控制电路导出其功能表，是分析的过程。 引入真值表。 综合（synthesis）：由给定的功能描述推导其电路实现。 由真值表推导其电路实现，需要引入其它的数学工具， 逻辑代数（布尔代数）便是其中之一。,2008.11,8,1.2 逻辑代数,英国数学家乔治布尔（George Boole）提出了逻辑代数的基本形式和概念，将形式逻辑

4、问题归结为一种代数运算，被人们称为布尔代数（Boolean algebra），即我们所说的逻辑代数。 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 逻辑函

5、数： 逻辑函数的表示方法 ： 真值表； 由变量、常量以及逻辑运算符构建的逻辑表达式 。 逻辑函数的等价性判断： 真值表形式具有唯一性：若函数 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,

6、逻辑代数的基本公式（续）,上述公式具有对偶性： 把 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

7、，函数 g 的对偶式记作g。若函数 f 与g 等价，则其对偶式 f与 g也等价。 对函数 f 执行2 次对偶变换，将得到函数 f 本身。 代入规则： 对于一个已经成立的等式，若将其中某个变量 x 用另一个逻辑表达式 f 代替，则等式仍然成立。 分解规则： 香农展开定理（Shannons Expansion Theorem）可称为分解规则，即任何一个逻辑函数 都可以重新表示为,子函数（f0, f1）的变量个数减少！,2008.11,20,逻辑代数的基本规则（续）,分解规则应用举例：,2008.11,21,逻辑代数的基本规则（续）,反演规则：德摩根定律的一般形式称为反演规则,2008.11,22,

8、1.3 用与门、或门和非门进行逻辑综合,实例： 待综合函数的真值表 逻辑表达式 逻辑表达式 电路图,2008.11,23,1.4 公式法化简逻辑函数,求最简的“积之和”表达式： 表达式中含乘积项个数最少。 在满足上述条件下，每个乘积项所含变量个数最少。 举例： 1. 合并乘积项法：利用基本公式（111a） 2. 吸收法：利用基本公式（110b） 3. 消去法：利用基本公式（19b）,2008.11,24,公式法化简逻辑函数（续）,举例： 4. 添加项法：利用基本公式（14b） 5. 配项法：利用互补律，基本公式（15b）,2008.11,25,公式法化简逻辑函数（续）,优点： 用逻辑表达式描述

9、数字电路的功能，是理论上的重大贡献。 优化逻辑表达式 优化逻辑电路。 缺点： 化简过程无一定规律可循，需要经验和技巧，灵活、交替地使用各种方法。 不易判断是否已经达到最简形式 。 需要寻找更好的方法。,2008.11,26,1.5 卡诺图 化简逻辑函数,卡诺图是真值表的图形表示 卡诺图中1个小方格对应于真值表中的1行。,2008.11,27,卡诺图 化简逻辑函数（续）,名词术语： 乘积项（product term，简称积项） 变量以原变量或反变量的形式出现，多个变量之间执行“与”操作而构成乘积项。 文字（literal） 乘积项中的变量或该变量的反变量称作一个文字。 最小项（minterm）

10、对于n 变量的逻辑函数来说，若某个乘积项中包含的文字个数为 n，则称该乘积项为最小项。换句话说，若每一个变量或以原变量形式、或以反变量形式在一个乘积项中出现 1 次、且仅出现 1 次，则该乘积项是最小项。 最小项对应于卡诺图中的一个小方格，它可以表示为 n 个变量之积，也可以记作 m i 。 例如最小项 的另一个等价表示形式是 m1。 最大项（maxterm） 对于n 变量的逻辑函数来说，若某个“或”项中包含的文字个数为 n，则称该“或”项为最大项。,2008.11,28,卡诺图 化简逻辑函数（续）,举例： 最小项的性质： 全体最小项之和（“或”运算）为1。 任意2个最小项互不相交，故任意2个

11、最小项之积（“与”运算）为0。 若2个最小项之间只有1个文字不同，即在一个最小项中该文字为原变量，而在另一个最小项中该文字为反变量，则称这2个最小项“逻辑相邻”。根据公式（1-11a），逻辑相邻的2个最小项可以合并为1个乘积项，并且合并所得乘积项中的文字个数减少1个。 卡诺图是把逻辑相邻的最小项尽量安排成几何位置相邻，通过观察即可判定哪些最小项可以合并。,2008.11,29,卡诺图 化简逻辑函数（续）,举例：,2008.11,30,卡诺图 化简逻辑函数（续）,逻辑相邻与几何相邻： 2个逻辑相邻的乘积项在卡诺图中表现为几何位置的相邻，使我们通过观察图形即可实现块的合并，达到化简逻辑函数的目的。

12、 可以把卡诺图想象为一张图纸，将其卷成一个圆筒，则原来两边不相邻的部分就变成相邻的部分了。,2008.11,31,卡诺图 化简逻辑函数（续）,5变量卡诺图：,变量个数 5时， 很难画出对应的卡诺图！,2008.11,32,卡诺图 化简逻辑函数（续）,概念提升： 蕴含项（implicant） 若某乘积项能指明输入变量的取值组合可使给定逻辑函数 f 取值为1，则该乘积项是函数 f 的蕴含项。 蕴含项的包含关系（contain） 设蕴含项 A 由相邻最小项集合 Sa 合并而成，蕴含项 B 由相邻最小项集合 Sb 合并而成。若，即 Sa 中的每一个最小项都存在于Sb中，则称蕴含项B包含蕴含项A，记作

13、。 质蕴含项（prime implicant） 若某蕴含项不被其他任何一个蕴含项所包含，则该蕴含项是质蕴含项。在卡诺图中，若某个由相邻最小项构成的块已经是维数最大的块，不被其它任何一个块所包含，则该块对应的乘积项是质蕴含项。,2008.11,33,卡诺图 化简逻辑函数（续）,概念提升： 特征最小项和必要质蕴含项（essential prime implicant） 若某最小项仅被唯一的一个质蕴含项所包含，则该最小项称为特征最小项，包含特征最小项的质蕴含项称为必要质蕴含项。,2008.11,34,卡诺图 化简逻辑函数（续）,概念提升： 覆盖（cover） 若一个蕴含项的集合能说明给定逻辑函数 f

14、 为 1 的所有情况，则称此蕴含项集合是函数 f 的覆盖。覆盖和函数的“积之和”表达式相对应。 最小覆盖（minimal cover） 函数的最小覆盖和成本最低的“积之和”表达式相对应，其要求为： 1. 最小覆盖中包含的蕴含项个数最少。 2. 每一个蕴含项的文字个数尽量少，即蕴含项的维数尽量大。 必要质蕴含项必定是最小覆盖的元素。 无冗余覆盖（non-redundant cover） 1. 覆盖中每一个蕴含项必须是质蕴含项。 2. 覆盖中不含冗余项。 当变量个数很多时，若求解函数的最小覆盖有困难，可退而求其次，转而求无冗余覆盖。,2008.11,35,卡诺图 化简逻辑函数（续）,概念提升： 冗

15、余项（redundant term） 设 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.

16、11,38,逻辑函数的标准形式（续）,最大项与最小项的对应关系 ：,2008.11,39,逻辑函数的标准形式（续）,最大项与最小项的对应关系 ： 和之积标准形式的另一种表示方法：,2008.11,40,包含无关项的逻辑函数的化简,【例1.10】父亲、母亲为小女儿买一件衣服，是否购买取决于3个人对该商品的态度：3人全部赞成则购买；2人赞成则可买可不买；1人赞成或无人赞成则不买。,2008.11,41,包含无关项的逻辑函数的化简（续）,用卡诺图化简不完全确定的逻辑函数 d 的取值可为 0 也可为 1，以简化效果最佳为目的。 本例化简结果为：,2008.11,42,包含无关项的逻辑函数的化简（续）,

17、【例1.11】 假定用 4 位二进制代码表示 1 位十进制数，判断此种十进制数的值是否大于等于 5。,2008.11,43,包含无关项的逻辑函数的化简（续）,【例1.11】 逻辑表达式 化简结果：,2008.11,44,1.7 *表格法化简逻辑函数,Willared Quine和Edward McCluskey在二十世纪五十年代提出了表格法化简逻辑函数，表格法也因而被称为Quine-McCluskey法，简称Q-M法。 表格法的优点： 变量的个数不受限制，适合于多变量逻辑函数的化简。 规律性很强，可以写出严格的算法。 表格法的缺点： 当函数的变量很多时，手工操作仍不胜其烦。 计算机程序擅长于处

18、理多重循环和复杂的操作，所以它适合于编写逻辑综合软件。 与其它逻辑综合算法相比较，表格法出现较早，不是最高效的却是最简单的。 学习表格法的目的： 了解EDA 工具的工作原理，从而更好地使用EDA工具。 有助于学习更先进的逻辑综合算法。,2008.11,45,表格法化简逻辑函数（续）,表格法化简逻辑函数的步骤： 1. 从函数的真值表描述求出其全部质蕴含项的集合，记作Z。 2 . 从质蕴含项集合Z中挑选出一个子集M，要求M是最小覆盖。即 （1）M覆盖全部最小项。至于无关项，属于可覆盖、可 不覆盖之列。 （2）M的成本最低。,2008.11,46,求质蕴含项集合Z 的算法流程图,2008.11,47

19、,用表格法求函数的质蕴含项集合Z 的实例（例1.12）,step1 建立初始表格（表1.10 ）： 求质蕴含项集合时，可对最小项和无关项不加区分，一律用m i 表示。 按 0 维块中含“1”的个数将其分组，组号即该 0 维块中含“1”的个数，分组的目的是为了提高“逐对”比较的效率，因为相邻块只可能在相邻组中出现。,若某个 0 维块被后续形成的1 维块包含， 则用“”作标记。,2008.11,48,用表格法求函数的质蕴含项集合Z 的实例（续）,step2 相邻块合并： 表1.11,2008.11,49,用表格法求函数的质蕴含项集合Z 的实例（续）,step2 相邻块继续合并： 表1.12 凡是没

20、有标记“”的蕴含项都是质蕴含项，从而构成全部质蕴含项集合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,求最小覆盖的实例（续）,St