卡诺图化简 卡诺图化简 ◆示例1F=∑m2,3457.81035 00011110 0d10 卡诺图化简 最小化积之和(MSOP) ◆示例 000111 o Minimum sum of products F=∑m02.34571415) ◆算法B(卡诺图) ●找出全部主蕴涵项 ●确定井表示所有的实质主蕴涵项(只圈过1次) ●在剩余的主蕴涵项中求出最小子集以形成覆盖,覆盖 所有其它最小项 F=.++,z+X,F 卡诺图化简 卡诺图化简 ◆示例1F=∑m(234578101315) ◆示例2 W.Z F=.F+,了+.X,F+x·Z
6 34 卡诺图化简 35 卡诺图化简 4 F m = ∑ (2 3 4 5 7 810 1315) ，，，，，，，， WX YZ 00 01 11 10 Y Y Z X W W 1 1 1 1 1 1 1 1 1 00 1 01 11 10 示例1 37 卡诺图化简 4 WX F m = ∑ (0 1 2 3 4 5 7 14 15) ，，，，，，，， YZ 00 01 11 10 Y Y Z X W W 1 1 1 1 1 1 1 1 00 1 01 11 10 示例2 F = 1 1 1 W X⋅ + ⋅ W Y + ⋅ W Z +WXY ⋅ ⋅ 38 最小化积之和(MSOP) Minimum sum of products 算法B (卡诺图) z 找出全部主蕴涵项 z 确定并表示所有的实质主蕴涵项(只圈过1次) z 在剩余的主蕴涵项中求出最小子集以形成覆盖，覆盖 所有其它最小项 39 1 1 1 1 卡诺图化简 4 F m = ∑ (2 3 4 5 7 810 1315) ，，，，，，，， WX YZ 00 01 11 10 Y Y Z X W W 1 1 1 1 1 1 1 1 1 00 1 01 11 10 示例1 41 卡诺图化简 4 WX F m = ∑ (0 1 2 3 4 5 7 14 15) ，，，，，，，， YZ 00 01 11 10 Y Y Z X W W 1 1 1 1 1 1 1 1 00 1 01 11 10 示例2 F = 1 1 1 W X⋅ +W Y⋅ +WXY ⋅ ⋅ + ⋅⋅ X Y Z + ⋅ W Z
组合逻辑函数的化简A 2. Multiple Output Minimization ◆ Boolean simplification(代数法) ◆示例1:全加器 e K-maps simplification F=∑m(1247)2 ● Simplifying SOP Multiple Output Minimization> ●" Don't Care" Input Combinations」 ee=∑m2为 e Automating simplification Quine-McCluskey Algorithm CO=B4+C-B+C/d ● Espresso Method a 未利用公用最小项化简! Multiple Output Minimization “ Dont Care"nput ◆示例2 重叠卡诺图F1F2F3 ◆禁止态:电路非法状态 F1=∑m0347)3 ●干扰导致错码引起 ●电路启动时,各部件不能同时进入工作状态 F2=∑m(0367 ◆禁止态出现方式 F3=∑m(346,7) 瞬态方式出现 ●稳态方式出现 克服措施 =BA+ ●人工干预或自恢复电路 F=B+ CB+ CB-A 燕止态测电隆通常是必须的若不影电路运行 此时可不必刻区分止态和其它状 E=B 4+ CB+ CBA 3)"Don't Care"Input Combinations 利用禁止态化简 ◆8421BcD译码 D ◆842-1BcD译码 D m。=DC·B·A 7
7 42 组合逻辑函数的化简A7 Boolean simplification(代数法) K-maps simplification z Simplifying SOP z Multiple Output Minimization z “Don’t Care” Input Combinations Automating simplification z Quine-McCluskey Algorithm z Espresso Method 43 2). Multiple Output Minimization 示例1：全加器 = ∑ 3 CO m(0，1，2，4) CO B A CI B CI A =⋅+ ⋅+ ⋅ A BA CI 00 01 11 10 CI CI B 0 1 1 1 1 1 B CO A BA CI 00 01 11 10 CI CI B 0 1 1 1 1 1 B F 未利用公用最小项化简！ = ∑ 3 F m(1，2，4，7) 44 Multiple Output Minimization 1 = ∑ 3 F m(0，3，4，7) 示例2 1 0 1 1 1 CB A A B A C C 2 = ∑ 3 F m(0，3，6，7) 3 = ∑ 3 F m(3，4，6，7) F3 =B⋅A+ C⋅B+ C⋅B⋅A F2 =B⋅A+ C⋅B+ C⋅B⋅A F1=B⋅A+ C⋅B⋅A+ C⋅B⋅A 1 1 0 1 1 1 1 0 1 1 重叠卡诺图: F1F2F3 45 “Don’t Care” Input “Don’t Care” Input 禁止态：电路非法状态 z 干扰导致错码引起 z 电路启动时，各部件不能同时进入工作状态 禁止态出现方式 z 瞬态方式出现 z 稳态方式出现 克服措施 z 人工干预或自恢复电路 z 禁止态检测电路通常是必须的, 若不影响电路运行, 此时可不必刻意区分禁止态和其它状态 46 3) “Don’t Care” Input Combinations 8-4-2-1BCD译码 DC BA B B A C D D m0 m1 Ø Ø Ø Ø Ø Ø m0 = D ⋅C ⋅ B ⋅ A DC BA B B A C D D m3 m2 Ø Ø Ø Ø Ø Ø m4 m5 m7 m6 m3 = C ⋅ B ⋅ A 47 利用禁止态化简 8-4-2-1BCD译码 DC BA B B A C D D Ø Ø Ø Ø m8 m9 Ø Ø m9 = D ⋅ A m8 = D ⋅ A
3)Don't Care"Input Combinations BCD七段峰码暴 ◆BcD一七段译码器 ●LED、LcD d mr e=me ●共阴极、共阳极 7=m,+m, *(m-m, g=m+m,+m, Light Emitting Diode 日a c 0101010101 BCD七段马暴 BCD七段马暴 1.检查专用最小项 2.检查化简对其它项的影响 g=( Go c)+(m)+(m)B e=(m)+(m2)+(m)+ =D,CB+CB,A b=C·B.A+(C·B.A) BCD七段马暴 K-map for 5-Var ◆锁存、译码、驱动三合一(显示四合一) ◆5个变量 ●|B|—灭零信号 测试值号 0 g 四22 L2 6 i4 10 Lia 22 so 26] 七段译码器 廿 日日日
8 48 3) “Don’t Care” Input Combinations BCD－七段译码器 z LED、LCD z 共阴极、共阳极 . . . . . . . . . a b c .…… f g Light Emitting Diode Liquid Crystal Display a b c d e f g h h 50 BCD七段译码器 a b c d e f g a b c d e f g h h N 0 1 2 3 4 5 6 7 8 9 DCB 0 00 0 00 0 01 0 01 0 10 0 10 0 11 0 11 1 0 0 1 00 0 1 0 1 0 1 0 1 0 1 A 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 a = m1 + m4 = m5 + m6 b = m2 c d = m1 + m4 + m7 = m1 + m2 + m3 + m7 f = m0 + m2 + m6 + m8 e = m0 + m1 + m7 g 51 BCD七段译码器 1. 检查专用最小项 DC BA B B A C D D 1 1 Ø Ø Ø Ø Ø Ø b CBA = ⋅⋅ C B⋅⋅+ A （ ） DC BA B B A C D D 1 1 Ø Ø Ø Ø Ø 1 Ø 0 2 68 em m m m =+++ ( )( )( ) 1 6 e =（ ）m + ⋅ C A 5 6 bm m = + ( ) 52 BCD七段译码器 2. 检查化简对其它项的影响 DC BA B B A C D D 1 1 Ø Ø Ø Ø Ø Ø 1 017 g = ++ ( )()( ) mmm 017 017 ( )()( ) ()( ) g mmm m m DCB m CBA = ⋅⋅+ + + = ++ = ⋅ ⋅ 53 BCD七段译码器 . . . . . . . . . a b c g h BI LT 锁存、译码、驱动三合一(显示四合一) z /BI——灭零信号 z /LT——测试信号 七段译码器 & & & & & & . . . . . . a b …… g h 54 K-map for 5-Var 5个变量 EDC BA B C D B A C D E 0 1 3 2 12 13 15 14 8 9 11 10 4 5 7 6 16 17 19 18 28 29 31 30 20 21 23 22 24 25 27 26
K-map for 5-Var BA)mo7 K-map for 6-var ◆5个变量 ◆6个变量 371m[s9"|4sl l614110 睡围 K-map for 6-Var 组合逻辑函数的化简 ◆6个变量 FE=00 ◆ Boolean simplification(代数法) ◆ K-maps simplification(卡诺图) e Simplifying SOP FE=0 e Multiple Output Minimization 9Don't Care"Input Combinations o Programmed simplification methods FE=11 e Quine-McCluskey Algorithm FE=10 Quine-McCluskey算法 Quine-McCluskey算法回 ◆QM方法的优点 ◆算法流程 啦,l ●直接,系统的计算方法 ·1.列出函数的所有最小项35m ●可以处理多于六个变量的函数 ●2.找出所有的主蕴涵项 ●可以处理多输出函数 首先将最小项按重量(1的个数)分组 其次穷尽地找出所有的主蕴涵项 ●3.找出最小的主蕴涵项覆盖 构造主蕴涵项图 选择最小数目的主蕴涵项覆盖 9"Digital Design"by J F Wakerly
9 56 K-map for 5-Var 5个变量 E=0 E=1 m0 m4 m12 m8 m1 m5 m13 m9 m3 m7 m15 m11 m2 m6 m14 m10 m16 m20 m28 m24 m17 m21 m29 m25 m19 m23 m31 m27 m18 m22 m30 m26 DC BA DC BA 57 K-map for 6-Var 6个变量 0 1 3 2 12 13 15 14 8 9 11 10 4 5 7 6 16 17 19 18 28 29 31 30 20 21 23 22 24 25 27 26 48 49 51 50 60 61 63 62 52 53 55 54 56 57 59 58 32 33 35 34 44 45 47 46 36 37 39 38 40 41 43 42 B A C D A B D C E F 59 K-map for 6-Var 6个变量 FE=00 m0 m4 m12 m8 m1 m5 m13 m9 m3 m7 m15 m11 m2 m6 m14 m10 m16 m20 m28 m24 m17 m21 m29 m25 m19 m23 m31 m27 m18 m22 m30 m26 DC BA m32 m36 m44 m40 m33 m37 m45 m41 m35 m39 m47 m43 m34 m38 m46 m42 m48 m52 m60 m56 m49 m53 m61 m57 m51 m55 m63 m59 m50 m54 m62 m58 FE=01 FE=11 FE=10 62 组合逻辑函数的化简 Boolean simplification(代数法) K-maps simplification(卡诺图) z Simplifying SOP z Multiple Output Minimization z “Don’t Care” Input Combinations Programmed simplification methods z Quine-McCluskey Algorithm z Espresso Method 63 Quine-McCluskey算法 Q-M方法的优点 z直接，系统的计算方法 z可以处理多于六个变量的函数 z可以处理多输出函数 64 Quine-McCluskey算法 算法流程 z1. 列出函数的所有最小项 z2. 找出所有的主蕴涵项 首先将最小项按重量(1的个数)分组 其次穷尽地找出所有的主蕴涵项 z3. 找出最小的主蕴涵项覆盖 构造主蕴涵项图 选择最小数目的主蕴涵项覆盖 z“Digital Design” by J. F. Wakerly DC BA 00 01 11 10 00 01 11 10 0 1 3 2 12 13 15 14 8 9 11 10 4 5 7 6
Programmed simplification methods 其它算法 ◆ Quine-McCluskey算法 Q Espresso Method: by U.C. Berkeley ● Prime implicant数目上限是3n ● Expand ●找到最小覆盖集是很困难的事情!!! e Irredundant cover: essentially the same as Q-M prime-implicant chart method e Reduce: try to find a better cover Continue repeating above steps Espresso Method 3.3 Race and hazard ◆eg1F=∑m012.456910113141 组合逻辑设计过程中,将化简得到的逻辑函数直 接映射成对应的逻辑电路 认门电路是理想逻辑功能实现载体这一前提 o Initial prime implicant ◆逻辑电路的瞬态特性可能和稳态特性的预期不一 e Result of"Reduce"step 致。由于电路延迟,可能出现尖峰或毛刺 Result of "Expand step ●门电路的稳态特性( Steady- state behavior ● Result of" redundant ●门电路的瞬态特性( Transient behavior 竞争(Race) 3.3 Race and hazard 录例1 经不同路径因而经历的延迟不同,若各入 变化不能同时传递到轴出级,就可能产生真 号,以两种形式出现在输出端,因传输时间不 二者某段时间不具有相应辑关系,造成错误 称为冒险或险象 A通过不同径,以两种形式出现(有竞争力的僧号) B=c=1,D=0 Static-I Hazard A=0 F=C 〔逻辑险象 没有竞争力的信号〔函数险象 10
10 65 Programmed simplification methods Quine-McCluskey算法 zPrime implicant数目上限是3n/n z找到最小覆盖集是很困难的事情！！！ 66 其它算法 Espresso Method: by U.C. Berkeley zExpand zIrredundant cover: essentially the same as Q-M prime-implicant chart method zReduce: try to find a better cover zContinue repeating above steps…… 67 Espresso Method 4 F m = ∑ (0 1 2 4 5 6 9 10 111314,15) ，，，，，，，，，， WX YZ 00 01 11 10 Y Y Z X W W 1 1 1 1 1 1 1 1 1 1 1 1 00 1 01 11 10 e.g.1 zInitial prime implicant zResult of “Reduce” step zResult of “Expand” step zResult of “Irredundant cover” step 69 3.3 Race and Hazard 组合逻辑设计过程中，将化简得到的逻辑函数直 接映射成对应的逻辑电路 默认门电路是理想逻辑功能实现载体这一前提！ 逻辑电路的瞬态特性可能和稳态特性的预期不一 致。由于电路延迟，可能出现尖峰或毛刺 z 门电路的稳态特性(Steady-state behavior) z 门电路的瞬态特性(Transient behavior) ` 竞争(Race) ` 冒险(Hazard) 70 3.3 Race and Hazard 输入信号经不同路径因而经历的延迟不同，若各输入 信号的变化不能同时传递到输出级，就可能产生真值 表以外的冒险信号 一个信号，以两种形式出现在输出端，因传输时间不 同，使二者某段时间不具有相应逻辑关系，造成错误 输出，称为冒险或险象 A A F Static-1 Hazard A F A 72 示例1 A通过不同路径，以两种形式出现(有竞争力的信号)， B=C=1，D=0 z Static-1 Hazard A=1 A=0 F 1 C A B 2 3 ≥1 4 & D & 1 F = A⋅ B + A⋅C + D F = A + A F = B + D F = C + D 逻辑险象 没有竞争力的信号 函数函数险象险象*