计算机结构与逻辑设计(4-1化简组合).ppt

1、1,计算机结构与逻辑设计,2.4 函数化简和组合逻辑电路,2,2.4 函数的化简,为什么要化简？ 表达式多种，逻辑电路多种。 后果：复杂度不一样。用的芯片数不一样。 引起成本、功耗、延迟的不一致。 大规模集成电路考虑计算机辅助测试、容错分析、标准化设计等方面，逻辑化简不是主要考虑因素。,3, 逻辑电路所用门的数量少, 每个门的输入端个数少, 逻辑电路构成级数少, 逻辑电路保证能可靠地工作,逻辑函数的简化,与或式中与项最少 每项的变量数最少,4,最简式的标准, 首先是式中乘积项最少, 与或表达式的简化,代数法化简函数,与门的输入端个数少, 消项： 利用A + AB = A消去多余的项AB,5,代

2、数法化简函数,解：, 或与表达式的简化,6,公式法化简原则,1）利用自己掌握的定律进行化简 2）先化成最小项之和形式，然后并项公式化简,最简不容易判定,相邻项合并原则,真值表,卡诺图方法,直观方便,7,图形法化简函数, 卡诺图（K图）,A B,0 0,0 1,1 0,1 1,m0,m1,m2,m3,A,B,AB,A,B,1,0,1,0,m0,m1,m2,m3,mi,A,BC,0,1,00,01,11,10,00,01,11,10,00,01,11,10,m0,m1,m2,m3,m4,m5,m6,m7,m0,m1,m2,m3,m4,m5,m6,m7,m12,m13,m14,m15,m8,m9,m

3、10,m11,AB,CD,8,输入变量,卡诺图的画法,（三输入变量从真值表到K图）,9,四输入变量卡诺图,10,逻辑函数以一般的逻辑表达式给出： 1）先将函数变换为与或表达式（不必变换为最小项之和的形式）， 2）在卡诺图上与每一个乘积项所包含的那些最小项（该乘积项就是这些最小项的公因子）相对应的方格内填入1， 3）其余的方格内填入0。,卡诺图的填写,从逻辑表达式卡诺图：,11,例：,变换为与或表达式,12,卡诺图化简原理,相邻项合并法则 可以合并： （1）相邻2块，包括两端，消1个变量。 （2）相邻4块，方块、一行、一列、相邻行两端、相邻列两端、四对角。消2个变量。 （3）相邻8块，两行、两列

4、、上下两行，左右两列。消3个变量。,13,3、卡诺图化简的依据,任何两个（21个）标1的相邻最小项，可以合并为一项，并 消去一个变量（消去互为反变量的因子，保留公因子）。,14,15,任何4个（22个）标1的相邻最小项，可以合并为一项， 并消去2个变量。,16,17,18,19,任何8个（23个）标1的相邻最小项，可 以合并为一项，并消去3个变量。,20,化简原则： 1）卡诺圈越少越好 2）卡诺圈越大越好 3）圈包含的项每次必须要有新的,21,适用输入变量为3、4个的逻辑代数式的化简；化简过程比公式法简单直观。,3）每一项可重复使用，但每一次新的组合，至少包含一个未使用过的项，直到所有为1的项

5、都被使用后化简工作方算完成。,1）上、下、左、右相邻 （n=0,1,2,3)个项，可组成一组。,2）先用面积最大的组合进行化简，利用吸收规则，可吸收掉n个变量。,用卡诺图化简的规则： 对于输出为1的项,4、卡诺图化简,22,4）每一个组合中的公因子构成一个“与”项，然后将所有“与”项相加，得最简“与或”表示式。 5）无所谓项当“1”处理。,用卡诺图化简规则（续）,例1,Y=A+B,或门,A,B,23,图形法化简的基本步骤,逻辑表达式或真值表,卡诺图,1,1,24,合并最小项,最简与或表达式,2,冗余项,2,3,3,将代表每个圈的乘积 项相加,25,例2,用卡诺图化简,26,F=(A,B,C,D

6、)= (0,2,3,5,7,8,9,10,11,12,13，14,15),用卡诺图化简,例3,27,例4：,首先: 逻辑代数式卡诺图,1,1,28,含约束项的逻辑函数的化简,函数可以随意取值（可以为0，也可以为1）或不 会出现的变量取值所对应的最小项称为随意项， 也叫做约束项或无关项。 用符号“”、“”或“d”表示。,1、约束项,29,例如：判断一位十进制数是否为偶数。,30,输入变量A，B，C，D取值为00001001时，逻辑函数Y 有确定的值，根据题意，偶数时为1，奇数时为0。,31,A，B，C，D取值为1010 1111的情况不会出现或不允许出现，对应的最小项属于随意项。用符号“”、“”

7、或“d”表示。,随意项之和构成的逻辑表达式叫做 随意条件或约束条件，用一个值恒为 0 的条件等式表示。,32,不利用随意项的化简结果为：,利用随意项的化简结果为：,33,例5：已知真值表如图，用卡诺图化简。,34,化简时可以将无所谓状态当作1或 0，目的是得到最简结果。,F=A,35,图形法化简函数总结, k图为方形图。n个变量的函数-k图有2n个小方格，分别对应2n个最小项；, k图中行、列两组变量取值按循环码规律排列，使变量各最小项之间具有逻辑相邻性。, 有三种几何相邻：邻接、相对（行列两端）和对称（图中以0、1分割线为对称轴）方格均属相邻, 几何相邻的2i（i = 1、2、3n）个小格可

8、合并在一起构成正方形或矩形圈，消去i个变量，而用含（n - i）个变量的积项标注该圈。,36,图形法化简函数总结, 与或表达式的简化, 然后将函数填入相应的卡诺图中，存在的最小项对应的方格填1，其它填0。, 合并：按作圈原则将图上填1的方格圈起来，要求圈的数量少、范围大，圈可重复包围但每个圈内必须有新的最小项。, 每个圈写出一个乘积项。按取同去异原则, 最后将全部积项逻辑加即得最简与或表达式, 先将函数表达式化为最小项标准表达式。,37,注意三个步骤的正确性,1）画卡诺图步骤： a) 逻辑式化成标准式，然后填卡诺图 b) 直接用逻辑表达式填卡诺图 2）卡诺图化简 3）化简后式子的整理：注意检查

9、,38, 根据函数填写卡诺图,1、已知函数为最小项表达式，存在的最小项对应的格填1，其余格均填0。,2、若已知函数的真值表，将真值表中使函数值为1的那些最小项对应的方格填1，其余格均填0。,例子,3、函数为一个复杂的运算式，则先将其变成与或式，再用直接法填写。,例子, 作圈的步骤,1、孤立的单格单独画圈,2、圈的数量少、范围大，圈可重复包围但每个圈内必须有新的最小项,3、含1的格都应被圈入，以防止遗漏积项,图形法化简函数总结,39, 含有无关项的函数的化简, 填函数的卡诺图时只在无关项对应的格内填任意符号“”、“d或“”。,处理方法：,对于变量的某些取值组合，所对应的函数值是不定。通常约束项和

10、任意项在逻辑函数中统称为无关项, 化简时可根据需要视为“1”也可视为“0”，使函数化到最简。,例子,图形法化简函数总结,40,解：,AB,AC,图形法化简函数总结,41,例：图中给出输入变量A、B、C的真值表，填写函数的卡诺图,1,1,1,图形法化简函数总结,42,例：图中给出输入变量A、B、C的真值表，填写函数的卡诺图,1,1,1,F=,+,得：,图形法化简函数总结,43,解：, 填函数的卡诺图,1,1,1,1,1,1,1, 化简,不考虑约束条件时：,考虑约束条件时：,44,解：,AC,AD,BC,化简得：,最简与非与非式为：,图形法化简函数总结,45,作业3,P 389页： 2.27 (2

11、)(4)(6)(8) 2.28 (1)(3)(5)(7) 2.29 (c)(d) 2.31 (3)(4),作业！,46,组合逻辑电路,47,组合逻辑电路,无反馈 可以，多输入，多输出 某一时刻的输出与当时输入相关，与历史无关,门网络 （组合逻辑）,Z1=f1(x1,x2,x3xi.xn),x1,x2,.,xn,.,z1,z2,zn,z2=f2(x1,x2,x3xi.xn),.,zn=fn(x1,x2,x3xi.xn),48,组合电路分析,逻辑图逻辑功能 逻辑图逻辑表达式：门输出为节点，按照顺序逐个写出每个节点逻辑表达式，一直到输出端。再化简。 书上的两个例子： 1）XOR 异或 2）全加器,电

12、路逻辑图,逻辑表达式,真 值 表,逻辑功能,表达式化简,49,组合逻辑电路的分析方法,逻辑图,逻辑表达式,1,1,最简与或表达式,化简,2,2,从输入到输出逐级写出,50,最简与或表达式,3,真值表,3,4,电路的逻辑功能,当输入A、B、C中有2个或3个为1时，输出Y为1，否则输出Y为0。所以这个电路实际上是一种3人表决用的组合电路：只要有2票或3票同意，表决就通过。,4,51,逻辑图,逻辑表达式,例1：,最简与或表达式,52,真值表,用与非门实现,电路的输出Y只与输入A、B有关，而与输入C无关。Y和A、B的逻辑关系为：A、B中只要一个为0，Y=1；A、B全为1时，Y=0。所以Y和A、B的逻辑

13、关系为与非运算的关系。,电路的逻辑功能,53,例2：,54,例3：,本图功能：二选一电路。,M=0时：门1输出恒为1， A信号被拒之门外。,55,异或、全加器性质,异或：符号，而同或是其反操作。 0=A A=0 A1= A=1 全加器 CI是低进位，是模2和，CO是进位。,56,混合逻辑(正、负混合),逻辑图常采用混合逻辑画法： 1）任何门电路内部功能由其限定符确定。 2）输入输出线正相或者反相。有圆圈为反相。有圆圈的输入输出端从外部看是低电平有效。 正负逻辑的对偶问题（参考书上） 正逻辑（与、或） 负逻辑（或、与） “非”是恒等器，影响输入输出低电平有效。 非逻辑体现在门电路之间的连线上：,

14、一根连线,两端都有小圈或者都没有小圈,匹配线,无非功能,一端有小圈，另一端没有小圈,失配线,有非功能,57,混合逻辑,有圆圈就是有非。失配线就存在“反”操作 变量与圆圈之间的匹配和失配关系： 正变量 无圆圈 (匹配) 反变量 有圆圈 (匹配),红颜色 失配,58,混合逻辑总结,匹配线之间是等价 同时在线两端增加或去掉圆圈，逻辑不变。 失配线之间也是等价 圆圈可从线一端移到另外一端，逻辑不变。 混合逻辑总结： 1）门电路逻辑功能由其限定符决定 2）传递中碰到失配线时，信号需反相。,举例子：书上的,可应用于逻辑图化简,59,组合逻辑的语言描述方法,EDA发展：VHDL 超高速集成电路硬件描述语言

15、VHDL三部分：软件包(package)，实体(Entity)，结构体（Architecture） 结构体描述三种方法： 1）类似电路逻辑图，各节点描述，一直到输出。 2）直接写出总体方程。 3）直接描述电路的行为方式。,行为级描述语言重要,60,常用的组合逻辑模块,MSI定义：中规模集成电路 (Medium Scale Integrated Circuit) 有以下几种： 1）编码器 (Encoder) 某个信号指定一组代码 2）译码器 (Decoder) 一组代码还原成一种信息 3）数据选择器 (MUX) 4）数据分配器 (DMUX),61,编码器,4线- 2线编码器,1）逻辑图 2）真值

16、表 3）逻辑符号 4）VHDL表示,一般情况,m输入，n输出，n = log2m,62,4( =22)种情况，需2位二进制码就能将所有情况表示；,2n种情况，只需要n位二进制码就能完全表示！,2n m,8 ( =23)种情况，需3位二进制码就能将所有情况表示；,16 ( =24)种情况，需4位二进制码就能将所有情况表示；,7种情况需几位二进制码表示？9种呢？,63, 用n 位二进制代码对2n个信号进行编码的电路就是二进制编码器。,74LS148是8-3线优先编码器,74LS148逻辑符号,二进制编码器,64,利用74LS148编码器监视8个化学罐液面的报警编码电路。 编码器输出3位二进制代码到

17、微控制器。 微控制器仅需要3根输入线就可以监视八个独立的被测点。,微控制器报警编码电路,74LS148 8-3线优先编码器 应用1,65,TTL74148,16-4编码器,66,注意读懂书上逻辑符号中的 关联符号,67, 例：一个简单的两位二进制代码的译码器。,输入是一组两位二进制代码AB，输出是与代码状态相对应的4个信号Y3Y2Y1Y0。,表4.12 译码器的真值表,真值表与我们前面学过的什么很相似？你发现了吗？,二、译码器,最小项发生器： Y0=m0 Y1=m1 Y2=m2 Y3=m3,68,1. 二进制译码器 二进制译码器是把二进制代码的所有组合状态都翻译出来的电路。如果输入信号有n 位

18、二进制代码，输出信号为m个，m = 2n。, 74LS138二进制译码器。(3-8译码器),表4.13 74LS138译码器功能表, 另有三个附加的控制端,69,74LS138译码器的逻辑符号,在S1=1， =0时，输出信号 才取决于输入信号A2、 A1、 A0的组合。, 当S1=0时，无论其他输入信号是什么，输出都是高电平，即无效信号。, 为高电平时，输出也都是无效信号。,三点说明：,70,例：用两片3-8线译码器74LS138构成4-16线译码器，电路如图4.7所示。, 电路中，当B3=0时，片（2）被禁止，片（1）工作，这时将B3B2B1B0的 00000111 这 8 个代码译成片（1

19、） 8 个低电平信号输出。 当B3=1时，片（1）被禁止，片（2）工作，这时则将B3B2B1B0的 10001111 这 8 个代码译成片（2） 8 个低电平信号输出。 由此，片（1）、（2）便构成了416线译码器。,VCC,71,例4.1 用全译码器实现逻辑函数,解 （1）全译码器的输出为输入变量的相应最小项之非，故先将逻辑函数式 f 写成最小项之反的形式。由摩根定理,（2）f 有三个变量，因而选用三变量译码器。 （3）变量C、B、A 分别接三变量译码器的C、B、A 端，则上式变为：,图4.18是用三变量译码器74LS138实现以上函数的逻辑图。,图4.18,74LS138 3-8译码器 应

20、用1实现逻辑函数,72,1、用二进制译码器实现逻辑函数,写出函数的标准与或表达式，并变换为 与非-与非形式。,73,画出用二进制译码器和与非门实现这些函 数的接线图。,74,例2：用一个3线8线译码器产生函数 F=m0+m2+m4+m7 （逻辑函数产生器）,75,例如：要将输入信号序列00100100 分配到Y0 通道输出。,在图中，如果D输入的是时钟脉冲，则由地址码的状态将该时钟脉冲分配到Y0Y7的某一个输出端，从而构成时钟脉冲分配器。,74LS138 3-8译码器 应用2数据分配器或时钟分配器,76,2. 二十进制译码器,将4位二十进制代码翻译成1位十进制数字的电路就是二十进制译码器，又称

21、为BCD十进制译码器。,74LS42译码器功能表,Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9,由功能表可知，该译码器有4个输入端A3A2A1A0，并且按8421BCD编码输入数据。 它有10个输出端，分别与十进制数09相对应，低电平有效。 当输入的二进制数超过BCD码时，所有输出端都输出高电平，呈无效状态。,74LS42二十进制译码器的逻辑图所示。,77,数据选择器 (MUX),单刀开关 完成对输入数据的选择。,78,集成8选1数据选择器74LS151,79,74LS151的真值表,80,根据已知输出函数来构成函数产生器的过程是： 1）将函数变换成最小项表达式； 2）根据最小项

22、表达式确定各数据输入端的二元 常量。,用数据选择器实现逻辑函数的步骤：,数据选择器的应用,81,例1：试用8选1数据选择器产生逻辑函数,解：把式,变换成最小项表达式,由上式可知C3、C5、C6、C7为逻辑1，其它输入为 逻辑0。由此得到逻辑函数产生器如下图所示：,82,83,例2：试用上例的数据选择器产生 L=ABC。,解：根据逻辑表达式 L=ABC列出真值表， 如右表所示。,由表中对应L为1的最小项可知，C1、C2、C4、 C7为1，其它输入为0。得到的函数产生器如下 图所示。,84,85,MUX注意点,1）注意书上的关联符的解释！ 2）MUX的扩展 (书上图2.54) 扩展的方式有两种：a

23、) 使能端扩展 b) 分级模式,86,数据分配器 (DMUX ),完成信号的数据选择 有使能功能的译码器就可以完成。,例如：要将输入信号序列00100100 分配到Y0 通道输出。,在图中，如果D输入的是时钟脉冲，则由地址码的状态将该时钟脉冲分配到Y0Y7的某一个输出端，从而构成时钟脉冲分配器。,87,组合逻辑设计,88,1.最小化设计方法步骤（小规模逻辑设计方法）,根据题意列真值表,组合逻辑电路设计的方法,方法分两种: 1）最小化设计；2）标准化设计,89,例1： 用与非门设计一个举重裁判表决电路。设举重比赛有3个裁判，一个主裁判和两个副裁判。 杠铃完全举上的裁决由每一个裁判按一下自己面前的

24、按钮来确定。只有当两个或两个以上裁判判明成功，并且其中有一个为主裁判时， 表明成功的灯才亮。,设主裁判为变量A，副裁判分别为B和C；表示成功 与否的灯为Y，根据逻辑要求列出真值表。,90,设主裁判为变量A，副裁判分别为B和C；表示成功 与否的灯为Y，根据逻辑要求列出真值表。,91,卡诺图,最简与或表达式,逻辑变换,逻辑电路图,1,1,1,Y=,AB,+AC,92,例2,设计一个三人表决逻辑电路，要求: 三人A、B、C各控制一个按键，按下为“1”，不按为“0”。多数（2）按下为通过。通过时L1，不通过L0。用与非门实现。,93,2、用画卡诺图化简,L= AC + BC + AB,3、 写出最简“

25、与或”式,1、列真值表,94,用与非门实现逻辑电路,95,例3: 交通灯故障监测逻辑电路的设计。,红灯R 黄灯Y 绿灯G,96,单独亮正常,黄、绿同时亮正常,其他情况不正常,2、卡诺图化简,3、写最简逻辑式,设：灯亮为“1”，不亮为“0”， 正常为“0”，不正常为“1”。,例3,97,用基本逻辑门构成逻辑电路,若要求用与非门构成逻辑电路呢？,98,用与非门构成逻辑电路,99,最小化设计,书上的两个例子 1）二进制码 转 循环码：多输出量，多个K图化简 2）四舍五入例子 : 无关项应用,100,标准化设计方法,关键：1）译码器的建立；2）译码输入变量顺序,根据题意列真值表,整理最小项,101,例

26、4.1 用全译码器实现逻辑函数,解 （1）全译码器的输出为输入变量的相应最小项之非，故先将逻辑函数式 f 写成最小项之反的形式。由摩根定理,（2）f 有三个变量，因而选用三变量译码器。 （3）变量C、B、A 分别接三变量译码器的C、B、A 端，则上式变为：,图4.18是用三变量译码器74LS138实现以上函数的逻辑图。,图4.18,74LS138 3-8译码器 应用实现逻辑函数,102,1、用二进制译码器实现逻辑函数,写出函数的标准与或表达式，并变换为 与非-与非形式。,103,画出用二进制译码器和与非门实现这些函 数的接线图。,104,例2：用一个3线8线译码器产生函数 F=m0+m2+m4

27、+m7 （逻辑函数产生器）,105,用数据选择器实现标准化设计,106,根据已知输出函数来构成函数产生器的过程是： 1）将函数变换成最小项表达式； 2）根据最小项表达式确定各数据输入端的二元 常量。,用数据选择器实现逻辑函数的步骤：,107,例1：试用8选1数据选择器产生逻辑函数,解：把式,变换成最小项表达式,由上式可知C3、C5、C6、C7为逻辑1，其它输入为 逻辑0。由此得到逻辑函数产生器如下图所示：,108,109,例2：试用上例的数据选择器产生 L=ABC。,解：根据逻辑表达式 L=ABC列出真值表， 如右表所示。,由表中对应L为1的最小项可知，C1、C2、C4、 C7为1，其它输入为

28、0。得到的函数产生器如下 图所示。,110,111,书上的卡诺图降维问题,卡诺图降维方法: 4 - 2 降了2维 4 - 3 降了1维 用数据选择器实现逻辑表达式功能。,112,可编程逻辑器件,PLD，Programmable Logic Device (PROM方法) （1）与阵列：生成最小项，n 2n (固定) （2）或阵列：生成输出逻辑，(可编程) 对多输入，多输出的中规模逻辑优势明显。 PROM,掩模 Mask,现场可编程 field,在系统编程 ISP,可擦除，紫外或电信号,113,PLD的基本结构,PLD的基本结构,门电路的简化画法,114,用ROM作函数运算表,用ROM构成能实现函数yx2的运算表电路。,例,设x的取值范围为015的正整数，则对应的是4位二进制正整数，用BB3B2B1B0表示。根据yx2可算出y的最大值是152225，可以用8位二进制数YY7Y6Y5Y4Y3Y2Y1Y0表示。由此可列出YB2即yx2的真值表。,115,真值表,116,逻辑表达式,117,阵列图,118,可编程逻辑阵列,PROM方法分析： （1）优点：简