Logic and Computer DesignCombinational LogicWhat is Combinational Logic?Uses for Combinational LogicBinary AdderHow does it work?In realityTTL for NAND gateNMOS Implementation of NANDPositive vs. Negative LogicCombining Logical GatesSlide 12Metrics for Combinational LogicReduction of Combinational LogicImplicantsReducing Boolean ExpressionsUsing the Karnaugh MapAnalog for Product of SumsHomogeneity of Logical GatesLogic and Computer DesignSimon Petruc-NaumCS 147 – Dr. S.M. LeeCombinational LogicWhat is it?What is it used for?How is it Implemented?Logical GatesWhat is Combinational Logic?Computers make decisions based on a combination of inputs.A combinational Logic Unit takes Boolean data as input and produces Boolean data as output.Uses for Combinational LogicCombinational Logic Units can be used to perform many functionsConsider the binary adder functionBinary AdderSingle Digit adderHow does it work?Boolean functions are created by combining logical gates.Examples of logical gates are NOT, AND, OR, NAND, NOR, XOR…In realityLogical gates are mathematical abstractions. I reality they are implemented using Transistor-Transistor Logic (TTL), or Complementary Metal Oxide Semiconductors (CMOS).TTL for NAND gateIf both A and B have a voltage than current will flow to GND otherwise it will flow to Q.NMOS Implementation of NANDSimilar to CMOS, NMOS uses onlyN-type transistors.Again we can see that if eitherA or B has voltage, F will havea currentPositive vs. Negative LogicAssigning a logical 1 to a voltage is positive LogicAssigning a logical 1 to a lack of voltage is negative logicA B F0 0 00 1 01 0 01 1 1A B F1 1 11 0 10 1 10 0 0Positive Logic AND gateNegative Logic OR gateCombining Logical GatesSum of Product form (SOP) F=A’B’C+A’BC’+AB’C’+A’B’C’Each product term is a minterm because it contains one of each variable. Each minterm has a value of 1 for exactly 1 row in the truth table (and 0 for the others)Combining Logical GatesProduct of Sum form (POS) F=(A’+B’+C)(A’+B+C’)(A+B’+C’)(A’+B’+C’)Each sum term is a maxterm because it contains one of each variable. Each maxterm has a value of 0 for exactly 1 row in the truth table (and 1 for the others)Metrics for Combinational LogicGate Count: number of logic gates in the logical unit.Gate Input Count: total number of inputs of the combined gates.Circuit Depth: Maximum number of gates along a path from inputs to outputs. (e.g. 2 for as POS and SOP)Reduction of Combinational LogicReducing the complexity of combinational logic can save cost, and improve performance.ImplicantsA product term is an implicant of a Boolean function if the function takes the value of 1 whenever the product term equals 1.A prime implicant is an implicant that cannot have any fewer literals. (i.e. cannot be reduced)Essential prime implicants cover the output of a function that no other prime implicant can cover.Reducing Boolean ExpressionsDetermine all prime implicants.Select all essential prime implicants.For non-essential prime implicants, select those that include all remaining minterms with the least amount of overlap withother prime implicants.Using the Karnaugh MapPrime implicants are rectancular groupings of adjacent minterms. (there must be 2-to-the-n minterms in each grouping).Make the biggest possible groups to reduce the number of literals in each term.Avoid overlaps to reduce the total number of terms.Analog for Product of SumsImplicants are sum terms that have a value of 0 whenever the function has a value of 0.On the K-map, we place 0’s for the maxterms.We group the 0’s into essential and non-essential prime implicants just as we did with the SOP K-map.F=AB’C+A’BC’=(A+B’+C)(A’+B+C’)Homogeneity of Logical GatesNAND and NOR can be combined to form any Boolean function. (they are universal)Using all NAND or all NOR gates can simplify the production process for integrated circuits, and reduce costs.Converting a logical expression to all NAND or NOR gates can however, increase circuit
View Full Document
Unlocking...