Digital Design - Faculty Support Site

Combinational Logic Design Process Step Description Step 1 Capture the function Create a truth table or equations, whichever is most natural for the given problem, to describe the desired behavior of the combinational logic. Step 2 Convert to equations This step is only necessary if you captured the function using a truth table instead of equations. Create an equation for each output by ORing all the miniterms for that output. Simplify the equations if desired. Step 3 Implement as a gatebased circuit For each output, create a circuit corresponding to the outputs equation. (Sharing gates among multiple outputs is OK optionally.) 1 Example: Three 1s Detector Problem: Detect three consecutive 1s in 8-bit input: abcdefgh 00011101 1 11110000 1 10101011 0 Step 1: Capture the function Truth table or equation? Truth table too big: 28 = 256 rows Equation: create terms for each possible case of three consecutive 1s y = abc + bcd + cde + def + efg + fgh Step 2: Convert to equation -- already done Step 3: Implement as a gate-based circuit a b c

abc bcd d cde e y def f g efg fgh h 2 Example: Number of 1s Count Problem: Output in binary on two outputs yz the number of 1s on three inputs 010 01 101 10 000 00 Step 1: Capture the function Truth table or equation? Truth table is straightforward Step 2: Convert to equation y = abc + abc + abc + abc z = abc + abc + abc + abc Step 3: Implement as a gatebased circuit a b c a b c a b c a b y a b c z

a b c a b c 3 More Gates NAND NOR XOR XNOR x x F y F y x y F x y F x y F x y F 0 0 1 0 0 1 0 0 0

0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 NAND: Opposite of AND (NOT AND)

NOR: Opposite of OR (NOT OR) XOR: Exactly 1 input is 1, for 2-input XOR. (For more inputs -- odd number of 1s) XNOR: Opposite of XOR (NOT XOR) 4 Decoders and Muxes Decoder: Popular combinational logic building block, in addition to logic gates Converts input binary number to one high output d0 1 d0 0 d0 0 0 i0 d1 0 1 i0 d1 1 0 i0 d1 0 1 i0 d1 0 0 i1 d2 0 0 i1 d2 0 1 i1 d2 1 1 i1 d2 0 d3 0 d3 0 d3 0 d3 1 2-input decoder: four possible input binary numbers So has four outputs, one for each possible input binary number

d0 0 Internal design AND gate for each output to detect input combination A decoder decodes an input n-bit binary number by setting exactly one of the decoders 2n outputs to 1. i1 i1i0 d0 i1i0 d1 i1i0 d2 i1i0 d3 i0 5 Decoder Example New Years Eve Countdown Display Microprocessor counts from 59 down to 0 in binary on 6-bit output Want illuminate one of 60 lights for each binary number Use 6x64 decoder 21 0 210 0 1 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 i0 i1 i2 i3 i4 i5 d0 d1 d2 d3 d58 e d59 d60 d61 6x64 d62 dcd d63 0 0 1 0 0 1 0 0 1 0 0 0 0 Happy New Year 1 2 3

0 0 0 0 0 0 58 59 4 outputs unused 6 Multiplexor (Mux) Mux: Another popular combinational building block Routes one of its N data inputs to its one output, based on binary value of select inputs 4 input mux needs 2 select inputs to indicate which input to route through 8 input mux 3 select inputs N inputs log2(N) selects Like a railyard switch 7 Mux Internal Design 21 i0 d i1 s0 21 i0 d i1 s0 0 i0 i0 (0+i0=i0) s0 1 0 s0 4 1 i0 i1 i2 i0 i1

d d i2 i3 s1 s0 A set of select inputs determines which input to pass through. 0 0 2x1 mux An Mx1 multiplexer has M data inputs and one output, and allows only one input to pass through to that output. d 1 i1 d i1 i0 (1*i0=i0) i0 21 i3 4x1 mux s1 s0 8 Additional Considerations Non-Ideal Gate Behavior -- Delay Real gates have some delay Outputs dont change immediately after inputs change 9