数字电路karnaughmap化简.ppt

Combinational-circuit minnimization,-Karnaugh maps,卡诺图化简的基本原则,Two formulae:,The logic foundation of karnaugh map simplifying ：,combining：,Adjacent logic: 只有一个变量原非取值不同;其余都同,The basic principle of building a karnaugh map:,Adjacent logic and adjacent cell of karnaugh map are unified 逻辑上相邻和几何上相邻 相统一,构建卡诺图,Truth table,Karnaugh map,A,B,0,1,0,1,0,1,2,3,0,1,2,3,0,1,1,0,2-dimentional=2-input 2-input XOR logic,Notice,Row,column,1、the code of input combination: gray code.,input combination,Output,Minterm number,2、the output of each cell = the output of corresponding row of the truth table.,3维卡诺图,3-dimentional karnaugh map,AB,C,00,01,11,10,0,1,A,BC,0,1,00,01,11,10,A,BC,0,1,00,01,11,10,0,0,0,1,0,1,1,1,Combining adjacent 1-cells,一,二,三,circle1：,circle2：,Circle3:,3维卡诺图,A,BC,0,1,00,01,11,10,Please simplify the logic function using karnaugh map,Notice : gray code is a cyclic code, so the cell 04 and 15 of karnaugh map is adjacent.,A,BC,0,1,00,01,11,10,A,BC,0,1,00,01,11,10,One circle,Please write out the result.,4维卡诺图,4-dimentional karnaugh map,AB,CD,00,01,11,10,00,01,11,10,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,AB,CD,00,01,11,10,00,01,11,10,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,AB,CD,00,01,11,10,00,01,11,10,Combining adjacent 0-cells,F,Redundant term,逻辑函数的一些基本概念在卡诺图中的体现,最小和（minimal sum） 与门最少并且与门输入变量最少的积之和表达式,画简的终极目标,最小积（minimal product）： 或门最少并且或门输入变量最少的 和之积表达式,P隐含于F（P implies F or F covers P）： If P=1,then F=1,蕴涵项（implicant）： If P=1,then F=1,逻辑函数的一些基本概念在卡诺图中的体现,Some description of the left karnaugh map,1. F1+F3 implies logic F,2. F4+F5+F2 implies logic F,3. And so on,4. F1F5 are all the impllicant of logic F,5. All the implicant of F are written out?,主蕴涵项(prime implicant)：如果一个与项P隐含于F，并且移去P中任何2一个变量，P就不再隐含于F，则称P为F的主蕴含项；,Which is the prime implicant in F1F5 ?,逻辑函数的一些基本概念在卡诺图中的体现,Five prime implicant of the logic F,Prime implilcant corresponds to the circles which cannot make any larger in karnaugh map,Redundant,主蕴涵项定理(prime-implican theorem)： A minimal sum is a sum of prime implicants,主蕴涵项定理是个充要条件（necessary and sufficient condition）吗？,逻辑函数的一些基本概念在卡诺图中的体现,完全和 (complete sum)：所有主蕴含项之和,完全积（complete product）,Complete sum,Minimal sum,奇异1单元（distinguished 1-cell）： 仅被单一的主蕴含项覆盖的输入组合,卡诺图中仅效忠于一个主蕴含项圈（最大圈）的1单元格,质主蕴含项（essential prime implicant）： 覆盖一个或者多个奇异1单元的主蕴含项,卡诺图中至少包括一个奇异1单元格的主蕴含项圈,逻辑函数的一些基本概念在卡诺图中的体现,F,Three distinguished 1-cell,Three essential prime implicant,次质主蕴含项 (secondary essential implicant)： 除所有的质主蕴含项外剩下的1单元格可圈一个蕴含项,1,1,次质主蕴含项,如果除质主蕴含项外的1单元格构成次质主蕴含项，则圈之,Y,卡诺图化简方法,通过圈卡诺图中的相邻的“1”单元格可以实现逻辑表达式的最简积之和表达式,有如下的原则需要大家掌握：,1、圈相邻的2M个逻辑“1”的单元格可以将所对应的M个最小项之和的逻辑表达式化简成一个与项；如果是N维卡诺图，则该与项有N-M个逻辑变量组成；,2、在上述的过程中，消失的M个逻辑变量即在这M个单元格的输入中既有逻辑1，又有逻辑0的变量；反之，如果在这M个单元格中只有逻辑1输入，则以原变量形式出现在最终的与项中，如果只有逻辑0输入，则以反变量的形式出现在最终的与项中；,是2M个相邻单元格，不是2*M个单元格,利用卡诺图将逻辑表达式化成最简与或式圈圈的方法,卡诺图化简方法,3、如果要将卡诺图化简成最简式，即最终表达式中出现的文字最少的式子，则在圈“1”圈时必须满足下面的原则：,圈子应该尽量的大,圈子越大则最终与门的输入量就越少；,圈子应该尽量的少,圈子越少则最终所需的与门数目就越少；,“1”单元格一个都不能少,“1”单元格全部都包含才能保证逻辑的完整；但是可以多次被圈；,每个圈都必须有新的“1”单元格,避免重复；,每个圈子所含的“1”单元格的数目应该是2的幂，故包围圈只能是矩形，同行的最左及最右，同列的最上与最下都是相邻项，可以圈。,4、上面的步骤完成之后，将最终得到的各个与项相加即是最简的与或表达式；,卡诺图化简方法,利用卡诺图将逻辑表达式化成最简或与式（1）,通过圈卡诺图中的相邻的“0”单元格可以实现逻辑表达式的最简和之积表达式,有如下的原则需要大家掌握：,1、圈相邻的2M个逻辑“0”的单元格可以将所对应的M个最大项之积的逻辑表达式化简成一个或项；如果是N维卡诺图，则该或项有N-M个逻辑变量组成；,2、在上述的过程中，消失的M个逻辑变量即在这M个单元格的输入中既有逻辑1，又有逻辑0的变量；反之，如果在这M个单元格中只有逻辑1输入，则以非变量形式出现在最终的或项中，如果只有逻辑0输入，则以原变量的形式出现在最终的或项中；,是2M个相邻单元格，不是2*M个单元格,卡诺图化简方法,3、如果要将卡诺图化简成最简式，即最终表达式中出现的文字最少的式子，则在圈“0”圈时必须满足下面的原则：,圈子应该尽量的大,圈子越大则最终或门的输入量就越少；,圈子应该尽量的少,圈子越少则最终所需的或门数目就越少；,“0”单元格一个都不能少,“0”单元格全部都包含才能保证逻辑的完整；但是可以多次被圈；,每个圈都必须有新的“0”单元格,避免重复；,每个圈子所含的“0”单元格的数目应该是2的幂，故包围圈只能是矩形，同行的最左及最右，同列的最上与最下都是相邻项，可以圈。,4、上面的步骤完成之后，将最终得到的各个或项相乘即是最简的或与表达式；,对于圈0圈也有主蕴含项、质主蕴含项和奇异0等概念圈圈的顺序也是先圈质主蕴含项，再完成其他0单元格的圈取,Please write out the prime implicant, distinguished 1-cell, essential prime implicant, and the minimal sum of the logic F,F,卡诺图化简举例,卡诺图化简举例,Example1: simplify the logic function using karnaugh map：,AB,CD,00,01,11,10,00,01,11,10,1,1,1,1,1,1,1,1,圈4个消两个变量,请找出它们的奇异1单元,Y,卡诺图化简举例,Example2: find out the minimal sum of th logic Y,AB,CD,00,01,11,10,00,01,11,10,1,1,1,1,1,1,1,1,1,1,1,1,圈8个消三个变量,Y,卡诺图化简举例,Example3：simplify the logic function Y,AB,CD,00,01,11,10,00,01,11,10,1,1,1,1,1,1,1,1,1,1,Y,卡诺图化简举例,Find out the minimal product of logic Y in example3,AB,CD,00,01,11,10,00,01,11,10,卡诺图化简举例,Example4: find out the minimal sum of th logic Y,AB,CD,00,01,11,10,00,01,11,10,Y,卡诺图化简举例,Example4: find out the minimal sum of th logic Y,AB,CD,00,01,11,10,00,01,11,10,Y,卡诺图化简举例,Find out the minimal product of logic Y in example4,AB,CD,00,01,11,10,00,01,11,10,0,0,0,0,0,0,0,0,0,无关输入组（dont care）的卡诺图化简,无关（dont care）,一般用字母“d”表示,Example5:请构建一个一位BCD码的素数检测器；要求，如果是素数，则输出逻辑“1”，否则，输出逻辑“0”；,真值表,0,1,1,1,0,1,0,1,0,0,d,d,d,d,d,d,超出BCD码计数范围，是无关输入组合,F,AB,CD,00,01,11,10,00,01,11,10,1,1,1,1,1,d,d,d,d,d,d,大家尝试一下化简成和之积形式,无关输入组（do