Glitches & HazardsSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Quine-McClusky MethodSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Factoring and DecompositionSlide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Glitches & HazardsGlitches / HazardsGates have an inherent delayWe have been ignoring this  but delays do existA glitch is an unwanted pulse at the output of a combinational circuitGlitches can result from gate delaysGlitches depend on the input patterns  glitches may not occur if the input pattern that would cause the glitch never occursA circuit with the potential for a glitch has a hazardA circuit with a hazard may or may not glitchGlitch ExampleF = AB + A'C: assume all gate delays = 10nsAn input change from ABC = 111 to 011 results in a glitch  output changes from 1  0  1 againA static hazard: result should have stayed statically at 1Static & Dynamic HazardsStatic hazards:Dynamic hazards:1 1 0 0 1 0 0 1 1 0 1 0Removing Static HazardsGlitch occurs in moving from one implicant to another within a coverWhen two adjacent 1's are not covered by a single implicantSolution: add an extra implicant to provide that coverageF = AB + A'C + BCNo longer minimum form  but no hazard now B C A00 01 11 100 0 1 1 01 0 0 1 1Hazard Removal: ExampleF(A,B,C,D) = m(6,7,8,9,12,13,14,15)The red prime implicant removes the static-1 hazard C D A B00 01 11 1000 0 0 0 001 0 0 1 111 1 1 1 110 1 1 0 0Dynamic HazardsDynamic hazards do not occur in two-level combinational circuits  only in multi-level circuitsx 2 x 1 x 3 x 4 b a c d f x 2 x 3 x 4  x 1 b a c d f One gate delayCauses of Dynamic HazardsFor an output to change 0101 (i.e. 3 times) in response to a single input change, there must be at least 3 paths of different length in the circuit2 gate delays: x1  b  f3 gate delays: x1  a  b  f4 gate delays: x1  a  c  d  fx 2 x 1 x 3 x 4 b a c d fRemoving Dynamic HazardsRemoving dynamic hazards is very difficultEven detecting dynamic hazards is very difficultStick to two level designs to ensure combinational circuits do not have dynamic hazardsSequential circuits do not have this problemQuine-McClusky MethodQuine-McClusky MethodAn algorithm that CAD tools can and do useUses tables to:Compute all prime implicantsIdentify essential prime implicantsSelect the minimum number of prime implicants for a coverIs based on the combining property againx y + x y' = x (y + y') = xGrouping the Mintermsf(A,B,C,D) = m(0,4,8,10,11,12,13,15)Arrange all minterms according to the number of 1’s in the binary representationSort and group themThese are called 0-cubesLike vertices of a 4D cube0 00004 01008 100010 101012 110011 101113 110115 1111Forming 1-cubesCompare each 0-cube in one group with each 0-cube in an adjacent groupUse combining property to form 1-cubes0 cubes0 0000 X4 0100 X8 1000 X10 1010 X12 1100 X11 1011 X13 1101 X15 1111 X1 cubes0,4 0x000,8 x0008,10 10x04,12 x1008,12 1x0010,11 101x12,13 110x11,15 1x1113,15 11x1Forming 2-cubesCompare each 1-cube in one group with each 1-cube in an adjacent groupUse combining property to form 2-cubes2 cubes0,8,4,12 xx001 cubes0,4 0x00 X0,8 x000 X8,10 10x04,12 x100 X8,12 1x00 X10,11 101x12,13 110x11,15 1x1113,15 11x1mark each 1-cube that contributes to a 2-cubeThe Prime ImplicantsAll “unchecked” cubes are prime implicantsThey did not get combined into a larger cube2 cubes0,8,4,12 xx001 cubes0,4 0x00 X0,8 x000 X8,10 10x04,12 x100 X8,12 1x00 X10,11 101x12,13 110x11,15 1x1113,15 11x10 cubes0 0000 X4 0100 X8 1000 X10 1010 X12 1100 X11 1011 X13 1101 X15 1111 XAll prime implicants are:P = { 10x0, 101x, 110x, 1x11, 11x1, xx00 }Prime Implicant Cover TableFor each prime implicant, mark all minterms covered by that implicantprime mintermsimplicants 0 4 8 10 11 12 13 15p1 10x0 X Xp2 101x X Xp3 110x X Xp4 1x11 X Xp5 11x1 X Xp6 xx00 X X X XFind Essential Prime Implicantsp6 is an essential prime implicant  minterms 0 and 4 must be covered by p6Minimum cover C = { p6 } at the momentprime mintermsimplicants 0 4 8 10 11 12 13 15p1 10x0 X Xp2 101x X Xp3 110x X Xp4 1x11 X Xp5 11x1 X Xp6 xx00 X X X XRow Dominancep2 row dominates p1 since p2 covers everything that p1 coversp1 can be eliminatedNote: we remove the dominated rowprime mintermsimplicants 10 11 13 15p1 10x0 Xp2 101x X Xp3 110x Xp4 1x11 X Xp5 11x1 X Xp5 row dominates p3Column DominanceColumn 11 column dominates column 10 since everything that covers column 10 also covers column 11Column 11 can be eliminatedNote: we remove the dominating columnWe could also have considered p2 and p5 as essential at this pointprime mintermsimplicants 10 11 13 15p2 101x X Xp4 1x11 X Xp5 11x1 X Xcolumn 15 dominates column 13Final CoverThe final cover is C = { p6, p2, p5 }f = xx00 + 101x + 11x1 = C'D' + AB'C + ABDprime mintermsimplicants 10 13p2 101x Xp4 1x11p5 11x1 XAnother Examplef(A,B,C,D) = m(0,2,4,5,6,7,8,10,11,12,15)0 cubes0 00002 00104 01008 10005 01016 011010 101012 11007 011111 101115 1111Cubes2 cubes0,2,4,6 0xx00,2,8,10 x0x00,4,8,12 xx004,5,6,7 01xx1 cubes0,2 00x0 X0,4 0x00 X0,8 x000 X2,6 0x10 X2,10 x010 X4,5 010x X4,6 01x0 X4,12 x100 X8,10 10x0 X8,12 1x00 X5,7 01x1 X6,7 011x X10,11 101x7,15 x11111,15 1x110 cubes0 0000 X2 0010 X4 0100 X8 1000 X5 0101 X6 0110 X10 1010 X12 1100 X7 0111 X11 1011 X15 1111 XAll prime implicants are:P = { 101x, x111, 1x11, 0xx0, x0x0, xx00, 01xx }Cover TableC = { p6, p7 } since p6 and p7 are essentialprime mintermsimplicants 0 2 4 5 6 7 8 10 11 12 15p1 101x X Xp2 x111 X Xp3 1x11 X Xp4 0xx0 X X X Xp5 x0x0 X X X Xp6 xx00 X X X Xp7 01xx X X X XRow DominanceRow p5 dominates row p4Row p3 dominates row p2prime mintermsimplicants 2 10 11 15p1 101x X Xp2 x111 Xp3 1x11 X Xp4 0xx0 Xp5 x0x0 X XColumn DominationColumn 10 dominates column 2Column 11 dominates column 15Final min cover is C = { p6, p7, p3, p5 }f = xx00 + 01xx + 1x11 + x0x0 = C'D' + A'B + ACD + B'D'prime mintermsimplicants 2 10 11 15p1 101x X Xp3 1x11 X Xp5 x0x0 X XHandling Don't Caresf(A,B,C,D) = m(0,3,10,15) +