数字逻辑与数字集成电路-第1章.ppt

卡诺图化简,卡诺图化简的核心是找到并且合并相邻最小项。 相邻三种情况：相接，相对，相重。5变量卡诺图才会出现相重的情况。 合并过程中先找大圈合并，圈越大消去的变量越多；使每一最小项至少被合并包含过一次；每个合并的圈中，至少要有一个“1”没有被圈过，否则这个圈就是冗余的。,4个变量卡诺图的最小项,m1,m0,m3,m2,m5,m4,m7,m6,m13,m12,m15,m14,m9,m8,m11,m10,m1 的相邻最小项是m0,m3,m5,m9，其中m9 是相对的，其余为相接；同样，m0与m8 相对，与m2也相对。,“与或”表达式化简：例3,“与或”表达式化简：,如果在上图中的m10=1,可以出现8个1相连，消去3个变量。,“与或”表达式化简：,此时，图上有13个最小项为1, 只有3个最小项为0，写F的表达式更简单。,注意：经常是写F比直接写F简单。,5变量卡诺图的最小项,CBA,同样以m1为例，它的相邻最小项有5个：m0,m3, m9,m17,m5,其中m17为相对的， m5为相重的，其余为相接。,例题：5变量卡诺图化简,化简结果:,1.4 逻辑函数的表格法化简(Q-M法 ) 计算机辅助逻辑设计的方法,卡诺图化简法直观方便，过程简单明了，但只适合于变量数4的函数，化简过程有规律，可编程，便于计算机实现。,4变量卡诺图的最小项,m1,m0,m3,m2,m5,m4,m7,m6,m13,m12,m15,m14,m9,m8,m11,m10,“相邻两个最小项中有一个变量互补”如何体现？ 从最小项的编号上看有什么规律？,Q-M方法的基本思想,“相邻两个最小项中有一个变量互补”在最小项编号上的规律： 以4变量卡诺图为例分析观察： m1同 m0,m3,m5,m9相邻，（每个mi都有4个相邻） 它们的下标编号为：0001与0000,0011,0101,1001 结论：相邻最小项编号中“1”的个数差等于1； m1同 m2,m4,m8,3个最小项不相邻，它们的下标编号中“1”的个数差等于0； m1还有 m6,m7, m10, m11, m12, m13, m14,m15等8个最小项不相邻，它们的下标0110,0111,1010,1011,这些最小项编号中“1”的个数差可能等于1，也可能不等于1。,Q-M方法的基本思想（续）,根据最小项编号中“1”的个数差就能判断是否相邻！ 最小项编号中“1”的个数差： 等于0，最小项肯定不相邻！ 等于1，最小项有可能相邻！ 算法步骤：（1）最小项分组：将最小项编号中“1”的个数相同的最小项分在一组，并按组号大小排序； （2）相邻组比较：合并最小项编号中“1”的个数差等于1的所有相邻最小项，得到函数的全部质蕴涵项； （3）求必要质蕴涵项：从全部质蕴涵项中消去冗余项，得到必要质蕴涵项，即为化简结果。,步骤1 求函数的全部质蕴涵项,函数的“质蕴涵项”就是不能再合并的最小项.,先把F中的各mi，按下标i中“1”的个数，由少到多， 分组排队列表I。组号是mi中i所包含“1”的个数。,在表I的相邻组间进行逐项搜索，寻找相邻项。把可以合并的记在表II中，并在表I中相应的最小项旁作记号“”。表II所列均是变量数为n-1的与项（n是F的变量数），它们同样按与项所含“1”的个数由少到多，分组排列。 重复上述过程，直到不能合并为止。,步骤1 求函数的全部质蕴涵项(续) 例:,1,1,1,1,15,1,0,1,1,13,3 4,0,0,1,1,12,0,1,0,1,10,1,0,0,1,9,0,1,1,0,6,2,0,0,0,1,8,0,0,1,0,4,0,1,0,0,2,1,A,B,C,D,最小项,组号,表I,问：1组需要和3，4组比吗？,步骤1 求函数的全部质蕴涵项(续),P1,P2,P3,P4,P5,P6,P7,在表I、II、III中，未打“” 的，标以P1P7，称质蕴涵 项。全部质蕴涵项覆盖了F的 所有最小项。,对表II继续上述过程,得表III；这一过程一直要进行到没有可合并的相邻组为止。,步骤1 求函数的全部质蕴涵项(续),用卡诺图画出F的全部质蕴涵项,P1，P4，P5是冗余的。 下面的目的是要用表格法找出必要的质蕴涵项。,P1DBA，P2CBA ,从卡诺图看哪些是冗余的？,步骤1 求函数的全部质蕴涵项(续),由图可见，P1 P7覆盖了F的全部最小项；对每个P项，它们是不能再和其它P项或最小项合并了。 由图还可见，P1 P7中有不必要的质蕴涵项： 例如，若P2，P3必要，则P1就不必要。 为此，下一步骤就要从全部质蕴涵项中消去冗余项，选出必要的质蕴涵项。,步骤2 寻找必要的质蕴涵项,寻找必要质蕴涵项的过程，就是在表格中消去冗余质蕴涵项的过程。 作全部质蕴涵项P1 P7与全部最小项mi对应的二维表格：例如：P1包含了最小项m2和m6，在对应位置画三角；m2被包含P1和P2所包含,表IV,质蕴 涵项,最小项,只有P7包含4个最小项，其它只有2个最小项,步骤2 寻找必要的质蕴涵项（续）,判断哪些行是必要的？先行消去，再列消去： 方法：先找只有一个的列，它们所对应的行一定要保留，这个P项是必要质蕴涵项。 对表IV，只有m9和m15对应的列只有一个（在卡诺图中表示这两个最小项只被画一次）,这些列肯定是必要的；m9它所对应的P7有4个，分别对应m8,m9,m12,m13. 因此P7为必要的。由于P7必要，P7所蕴涵的m8,m9,m12,m13可从表中暂时删去，以简化表IV。 同理，由于m15是必要的，P6也为必要，P6所蕴涵的m13, m15可以从表中暂时删去，如下图。 “行消去”找到的是要保留的必要质蕴涵项，暂时从表格中消去的目的是为了简化表格。,步骤2 寻找必要的质蕴涵项（续）,质蕴 涵项,最小项,步骤2 寻找必要的质蕴涵项（续）,“行消去” 暂时消去了要保留的必要质蕴涵项，使表格简化。 “列消去”的目的是去掉不必要的质蕴涵项 方法：先找只有一个的行，如果在它所对应的列上也有，则表示这个P项被其它行所包含，这个P项就可以消去。 在Pi行记有的各列，若在Pj行对应列中也均记有，则Pi行就是不必要的质蕴涵项。,步骤2 寻找必要的质蕴涵项（续）,表V,表VI,表V中，P4行只有一个，它所对应的m4列包含在P3行中，故P4为非必要的质蕴涵项。同理，P5也为非必要的质蕴涵项。表V简化为表VI。,步骤2 寻找必要的质蕴涵项（续）,最后，再对简化后的表VI进行“行消去” 。,P2,P3为必要质蕴涵项 （因 为m4 和m10列只有一个， 所以P2,P3 必须保留）,因P2,P3蕴涵了表VI中所列 全部m项（m2, m4, m6, m10)， 故P1为非必要质蕴涵项,化简结果为,必要质蕴涵项的卡诺图表示,根据最小项编号中“1”的个数差判断是否相邻。 第一步求全部质蕴涵项。分组后在相邻组间反复比较，两个最小项间只要有一个变量不同，就可以消去一个变量，最后得到覆盖F所有最小项的全部 质蕴涵项。 第二步求必要质蕴涵项。找出只有一个的mi列，它所对应的P项一定是要保留的；找出只有一个的Pi行，如果在它所对应的m列上也有，则表示这个P项是可以消去的。反复这一过程得到所有的必要质蕴涵项。 多输出逻辑函数的表格法化简不要求(p38-45). 计算机辅助逻辑化简的其他算法还在继续研究。,逻辑函数的表格化简法(Q-M法)小结,1.5 特殊形式的逻辑函数化简,基本形式的逻辑函数： 单输出逻辑函数，Ff(A,B,C) 特殊形式的逻辑函数： 1. 多输出逻辑函数 2. 包含不管项的逻辑函数 只要求掌握卡诺图化简法,(1)多输出逻辑函数的化简,多输出逻辑函数：同一组输入变量，有两个以上的输出。 F1 f(A,B,C) F2 f(A,B,C) 化简时，在“与或”表达式中要尽量寻找公共的“或”项，使公共项为多个函数共享，这时从单个输出看可能不是最简，但总体是最简。,ABC是公共项,单独看F1，F2都是最简，但没有公共项。,(2)有“不管项”的逻辑函数化简,包含不管项（Dont Care）的逻辑函数：函数F的取值只和一部分最小项有关，另一部分最小项既可以取“0”，也可以取“1”，这些最小项称“不管项”或“任意项”。 “不管项”的两种情况： 1. 这些输入组合不可能出现 2. 其输入组合虽能出现，但最小项的值是“1”还是“0”，人们不关心。,例：设计一位十进制数的数值范围判断器， 当x=5，F=1；否则，F=0。 (ABCD表示一位十进制数,A是低位,D是高位),1,0,1,1,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,F,D,C,B,A,有“不管项”的逻辑函数化简（续）,F的卡诺图,F=D+AC+BC,把项当作“1”,1.6 逻辑函数的实现,由最小项和函数式表达的逻辑函数要用逻辑电路来实现。实现时要考虑的问题包括可用集成电路的种类、逻辑函数的形式、集成电路的级数等。 下列三种，”与非与非”结构最常用。 与非与非实现 与或非实现 或非或非实现,门电路符号,传统符号 IEEE标准符号 习惯符号,门电路符号,例1: 异或逻辑,A,B不相同时, F为1； A,B相同时, F为0；因此称异或逻辑或半加逻辑。 表示为：FA B,逻辑符号,异或逻辑的实现,例题,逻辑问题的描述：逻辑设计的第一步。 由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现。 例1：设计一个多数表决逻辑电路，判别A B C三人中是否为多数赞同。 解：输入为0，表示反对； 输入为1，表示赞同； 当ABC中有两个和两个以上为“1”时，表示多数赞同，F1；否则F0。,C B A F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1,多数表决逻辑电路的真值表,Fm3+m5+ m6+m7,例2：1位二进制全加器的设计与实现 （不考虑进位叫半加，考虑进位叫全加）,真值表,1,1,1,1,1,1,0,0,1,1,1,0,1,0,1,0,1,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,0,0,0,Cn,Fn,Cn-1,Yn,Xn,3个输入 2个输出,输 入 输 出,全加器逻辑的卡诺图化简,实现方案一,Fn用异或门实现,Cn用”与非”门实现,Cn用”与或非”门实现,实现方案二,直接由最小项用与或非门实现，需要3级门,实现方案三,写 的表达式,经变换后只要2级门。,实现方案三（续）,组合逻辑：电路的输出只是和当前状态有关，和过去的状态无关。,A B,F,A B F,理想情况：门电路没有延迟,FA B,组合逻辑：电路的输出只是和当前