Announcements u Today Section 3 3 Combinational Memoryless Logic u Friday Storage Memory 3 4 3 6 u Monday Chapter 4 the von Neumann computer model Examples of Combinational Logic Structures u u u Some important combinational logic structures are the following Decoder MUX Multiplexer Full adder We describe each of these as a logic structure a logic gate network Each gate is physically realized by a circuit such as the MOS circuit implementations discussed earlier Decoder A n input decoder has 2n outputs u Output i 1 iff the n bit input word is unsigned 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 u Example 2 input Decoder also called 2 to 4 decoder MUX Multiplexer 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 the n bit select input is unsigned binary i u A multiplexer thus behaves like a multiposition channel select switch permitting any selected channel one at a time to be switched to a common output earphone TV screen u Example 4 Input MUX also called 4 to 1 MUX Full Adder u Given two n bit operands an 1 an 2 a1 a0 bn 1 bn 2 b1 b0 a full adder realizes the binary addition of one 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 Adder What is the weight of each input and output Describe the ci function in words the si function Gate Level Description of a Full Adder Row 0 1 2 3 4 5 6 7 3 6 5 7 1 2 4 A Circuit for Adding Two 4 bit Numbers Arbitrary Combinational Logic u The analysis done for these special logic functions can be generalized to realize an arbitrary combinational logic function u Draw a Truth Table for the desired n operand function Build an n to 2n Decoder Note the ith gate is asserted by the input combination in row i of the Truth Table Choose the Decoder gates whose Truth Table row has function 1 and OR their outputs together u u u This yields the canonical Sum of Products SOP 2 level AND OR logic circuit for the function Logical Completeness u Any n operand logical operation function as specified by an n 1 column 2n row truth table can be realized by a combinational logic structure consisting exclusively of AND OR and NOT gates u A set of gate types having this property is said to be logically or functionally complete Combinational Logic Design u This proof of the logical completeness of AND OR NOT thus yields an algorithm for designing a combinational logic circuit consisting of these gates beginning with the specification of the function in a truth table u Typically the resulting circuit will have more gates than needed i e there exist designs with lower cost that realize the same function u Concepts and methods aimed at minimizing circuit structure cost are deferred until EECS 270 Other Logically Complete Sets u Now that we have established the logical completeness of AND OR NOT it can be shown further that other sets of gate types are likewise 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 proved as follows Eliminating OR or AND gates From 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 Set 2 level AND OR converts to NAND NAND is equivalent to And since A AND B A OR B we have A OR B A AND B A NAND B is just another way to draw So a NAND gate assumes a 1 input NAND implements the NOT function
View Full Document
Unlocking...