Announcementsu Today: Section (3.3) Combinational (Memoryless) Logicu Friday: Storage (Memory) (3.4 - 3.6)u Monday: Chapter 4: the von Neumann computer modelExamples of CombinationalLogic Structuresu Some important combinational logicstructures are the following:¥ Decoder¥ MUX (Multiplexer)¥ Full adderu We describe each of these as a logic structure:a logic gate network.u Each gate is physically realized by a circuit, such asthe MOS-circuit implementations discussed earlier.Decoderu A n-input decoder has 2n outputs.u Output i = 1 iff the n-bit input word isunsigned binary i.u For each input word, exactly one output is 1(all others are 0).u Consider the set of input patterns as a code:Each output detects one (unique) code word.Each input code word asserts one output.Example: 2-input Decoder(also called 2-to-4 decoder)MUX (Multiplexer)u Generally, a MUX has 2n data inputs,n control inputs (select lines), and 1 output.u Input i is selected to drive the output iff then-bit select input is unsigned binary i.u A multiplexer thus behaves like a multi-position Òchannel selectÓ switch, permittingany selected channel (one at a time) to beswitched to a common output (earphone, TVscreen, É).Example: 4-Input MUX(also called 4-to-1 MUX)Full Adderu Given two n-bit operands an-1 an-2 É a1 a0 bn-1 bn-2 É b1 b0 a full adder realizes the binary addition ofone of the columns, say column i.u There are two outputs: si: the sum ai +bi +ci , where ci is the carry in from column i-1. ci+1 : the carry out to column i+1.Truth Table for a Full AdderWhat is the weight of each input and output?Describe the ci function in words; the si function.Gate Level Description of aFull Adder3 6 5 7 1 2 4Row 0 1 2 3 4 5 6 7A Circuit for AddingTwo 4-bit NumbersArbitrary Combinational Logicu The analysis done for these special logicfunctions can be generalized to realize anarbitrary combinational logic function.u Draw a Truth Table for the desired n-operand functionu Build an n-to-2n Decoder (Note: the ith gate is assertedby the input combination in row i of the Truth Table)u Choose the Decoder gates whose Truth Table row hasfunction = 1, and OR their outputs togetheru This yields the canonical Sum of Products (SOP)(2-level AND-OR) logic circuit for the function.Logical Completenessu Any n-operand logical operation (function), asspecified by an (n+1)-column, 2n-row truthtable, can be realized by a combinationallogic structure consisting exclusively of AND,OR, and NOT gates.u A set of gate types having this property is saidto be logically (or functionally) complete.Combinational LogicDesignu This Òproof Ó of the logical completeness of{AND, OR, NOT} thus yields an algorithm fordesigning a combinational logic circuit(consisting of these gates), beginning with thespecification of the function (in a truth table).u Typically, the resulting circuit will have moregates than needed, i.e., there exist designs withlower ÒcostÓ that realize the same function.u Concepts and methods aimed at minimizingcircuit (structure) cost are deferred untilEECS 270.Other Logically Complete Setsu Now that we have established the logicalcompleteness of {AND, OR, NOT}, it can beshown further that other sets of gate types arelikewise logically complete:¥ 2-gate sets: {AND, NOT} {OR, NOT}¥ 1-gate sets: {NAND} {NOR}u For example, the logical completeness of{AND, NOT} and of {NAND} can be provedas follows:Eliminating OR (or AND) gatesFrom DeMorganÕs Law: A OR B = (A¢ AND B ¢) ¢is equivalent to¥ Thus OR is not needed, if we have AND and NOT. Therefore {AND, NOT} is complete.¥ Similarly, {OR, NOT} is complete since A AND B = (A¢ OR B ¢) ¢NAND alone is a Complete Set2-level AND OR converts to NAND NANDis equivalent toAnd since A AND B = (A¢ OR B ¢) ¢, we haveA¢ OR B ¢ = (A AND B) ¢ = A NAND BSo,is just another way to draw a NAND gate(assumes a Ò1-input NANDÓ implements the NOT
View Full Document
Unlocking...