Example: Prime GenerationCofactorsCofactors and PrimesExampleSimilar Fast Techniques to Generate RowsApproximate AlgorithmEspresso-II algorithm (approx)Espresso-II exampleEspresso-II presented here very simplifiedReturn to Exact MethodsEspresso-SignatureTwo-Level Synthesis SummaryImplementations of Two-level LogicTwo-level Logic Using NAND GatesTwo-level Logic Using NAND Gates (cont’d)Two-level Logic Using NOR GatesTwo-level Logic Using NOR Gates (cont’d)Combinational Logic SummaryHardware Description Languages: VerilogQuick History of HDLsDesign MethodologyVerilog/VHDLVerilogKey Problem (Both Verilog AND VHDL)Verilog IntroductionStructural ModelSlide 32Simple Behavioral ModelVerilog ModuleVerilog Continuous AssignmentComparator ExampleSlide 41Simple Behavioral Model: the always blockalways Block“Complete” AssignmentsIncomplete TriggersOne Latch or Two?Slide 47Verilog ifSlide 49Verilog caseSlide 51Verilog case vs C switchSlide 53Verilog case (cont)Parallel Casecasex ExampleCS 150 - Spring 2008 – Lec #3: Combinational Logic - 1Example: Prime GenerationProblem: “in practice” efficiently generate all primes for a functionSolution: Use recursive-evaluation method on “cofactors”CS 150 - Spring 2008 – Lec #3: Combinational Logic - 2CofactorsPartial evaluation of functionFa = F evaluated at a=1Fa’ = F evaluated at a=0Example: F=a’b’d’ + abd’ +a’b Fa = bd’Fa’ = b’d’ + bFor any function F, variable a:F = a Fa + a’ Fa’ (“Shannon Expansion”)Example: F = a bd’ + a’(b’d’ + b) [Check it!]CS 150 - Spring 2008 – Lec #3: Combinational Logic - 3Cofactors and PrimesTheorem: Any Function F, variable a, Primes are maximal implicants of set: {a Primes(Fa), a’ Primes(Fa’), Primes(Fa) Primes(Fa’)}In other wordsFind the primes of Fa, multiply each by aFind the primes of Fa’, multiply each by a’Multiply each prime of Fa by each prime of Fa’Maximal members of these sets are primes of FCS 150 - Spring 2008 – Lec #3: Combinational Logic - 4Example0 01 1X 0X 1DA1 10 X0 00 0BCF =0 01 11 10 XFa’ =Primes(Fa’) = d, bcX 0X 1A0 00 0Fa =Primes(Fa) = bc’,c’d’Primes(F) = a’d, a’bc, abc’,ac’d’, bc’dCS 150 - Spring 2008 – Lec #3: Combinational Logic - 5Similar Fast Techniques to Generate RowsRecurse down cofactor tree, throwing out primes when they disagreeStop when:Cofactor of on-set is empty (no rows)All the remaining primes cover the whole space (1 row, with those primes)Still one very fast technique, “Espresso-Signature” (to follow approximate algorithm)CS 150 - Spring 2008 – Lec #3: Combinational Logic - 6Approximate AlgorithmDon’t try to generate minimum coverGiven a cover (sum-of-products for on-set and don’t-care set)Generate a prime cover smaller than given coverKeep generating smaller prime covers until you can’t anymoreProgram – Espresso-IICS 150 - Spring 2008 – Lec #3: Combinational Logic - 7Espresso-II algorithm (approx)Given Cover C = c1 + c2 +…+cnWhile (we keep making improvement) PrimeCover = 0Foreach cube c_i of the cover, C Find a prime p_i containing c_i that contains as many c_j’s as possible PrimeCover = PrimeCover + p_iWe now have a prime cover p1+…+pn, Make the cover “irredundant” (example next slide). Result is a smaller prime cover“Reduce” each cube away from a prime while still retaining a cover (this permits a different expansion in next iteration)CS 150 - Spring 2008 – Lec #3: Combinational Logic - 8Espresso-II exampleF=a’b’d’ + abc’d’ + abc+ a’b, DC = abcdExpand: a’b’d’ => a’d’abc’d’ => bd’abc => bca’b => a’bPrime Cover a’d’ + bd’ + bc + a’bPrime bc is redundant: covered by bd’ + a’b + don’t-careIrredundant cover is:a’d’ + bd’ + a’bReduce to a’b’d’ + bd’ + a’bd for next iterationCS 150 - Spring 2008 – Lec #3: Combinational Logic - 9Espresso-II presented here very simplifiedSee text for fuller descriptionWhat I left outDetails of EXPAND (how to pick the primes)Details of IRREDUNDANTDetails of REDUCEESSENTIAL_PRIMES (identified early and tossed into don’t-care set for efficiency)LAST_GASP (radical reduction to get new starting point)MAKESPARSE (final pruning of literals in the output plane)CS 150 - Spring 2008 – Lec #3: Combinational Logic - 10Return to Exact MethodsRealization (mid-nineties): The only purpose of generating primes was to get to covering table!Specifically: to get to “non-dominated” rows of covering tableRealization (beyond the scope of this class)Can identify non-dominated rows without generating primes or minterms!“Espresso Signature”: first radical revision of exact two-level synthesis algorithma’d’0XX0bd’X1X0a’b01XXbcX11X0 (0000)12 (0010)15 (0101)112 (1100)1CS 150 - Spring 2008 – Lec #3: Combinational Logic - 11Espresso-SignatureEspresso-Signature AlgorithmGenerate non-dominated rows of covering tableThis forms a cover, the “canonical cover” of a logic functionUse modified Espresso EXPAND to generate non-dominated columns of covering tableSolve the covering problemMuch more efficient than standard algorithmCS 150 - Spring 2008 – Lec #3: Combinational Logic - 12Two-Level Synthesis SummaryTwo exact methods: Quine-McCluskey and Espresso-SignatureIn practice, both highly efficientTheoretically: exponential complexityAlgorithms work well because they fit circuits people actually design (though this set is not characterized well)One approximate method shown, EspressoOthers (McBoole, e.g.) similarAlso theoretically exponential complexity!In practice, fast, gives results within a few percent of optimum.CS 150 - Spring 2008 – Lec #3: Combinational Logic - 13Implementations of Two-level LogicSum-of-productsAND gates to form product terms(minterms)OR gate to form sumProduct-of-sumsOR gates to form sum terms(maxterms)AND gates to form productCS 150 - Spring 2008 – Lec #3: Combinational Logic - 14Two-level Logic Using NAND GatesReplace minterm AND gates with NAND gatesPlace compensating inversion at inputs of OR gateCS 150 - Spring 2008 – Lec #3: Combinational Logic - 15Two-level Logic Using NAND Gates (cont’d)OR gate with inverted inputs is a NAND
View Full Document
Unlocking...