CS61c Representations of Combinational Logic Circuits J Wawrzynek October 12 2007 1 Introduction In the previous lecture we looked at the internal details of registers We found that every register regardless of its use has the same internal structure Combinational logic CL blocks on the other hand are all different from one another The internal circuit structure of each is tailored to the functional requirements of that particular circuit In this lecture we will look at three different ways to represent the function and structure of a combination logic block 2 Truth Tables Combinational logic circuit behavior can be specified by enumerating the functional relationship between input values and output values For each input pattern of 1 s and 0 s applied to the CL block there exists a single output pattern This input output relationship is commonly enumerated in a tabular form called a truth table In general a truth table takes the form shown below In this case for a generic block of four inputs a 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 b 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 c 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 d 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 y F 0 0 0 0 F 0 0 0 1 F 0 0 1 0 F 0 0 1 1 F 0 1 0 0 F 0 1 0 1 F 0 1 1 0 F 0 1 1 1 F 1 0 0 0 F 1 0 0 1 F 1 0 1 0 F 1 0 1 1 F 1 1 0 0 F 1 1 0 1 F 1 1 1 0 F 1 1 1 1 Wawrzynek 2007 c UCB 2 For each row of the table the output column shows the output value of the block for the input pattern shown in the input columns Many CL blocks have more than one output or a single output that is more than one bit wide In these cases each single bit output gets its own truth table Often they are combined into a single table with multiple output columns one for each single bit output Below are some example truth tables 1 Consider a CL block with two inputs a b and a single output y The output y has value 1 if one but not both of the inputs is a 1 a 0 0 1 1 b 0 1 0 1 y 0 1 1 0 2 A 2 bit wide unsigned adder circuit with a 3 bit wide output A a1 a0 00 00 00 00 01 01 01 01 10 10 10 10 11 11 11 11 B b1 b0 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 C c2 c1 c0 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 CS61c Lecture Notes 3 3 From the lecture notes State Elements Circuits That Remember the finite state machine next state and output logic PS 00 00 01 01 10 10 INPUT 0 1 0 1 0 1 NS 00 01 00 10 00 00 OUTPUT 0 0 0 0 0 1 B 000 0 000 1 111 1 C 000 00 000 01 111 10 4 32 bit unsigned adder with 33 bit output A 000 0 000 0 111 1 This table has 26 4 rows In principle the function of any combination logic circuit can be completely specified with truthtables in practice some are too big 5 Three input majority circuit The output y takes on the value that matches the majority of the input values a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c 0 1 0 1 0 1 0 1 y 0 0 0 1 0 1 1 1 Wawrzynek 2007 c UCB 4 3 Logic Gates What do we do if we need to determine the circuit details for a combinational logic block In most cases we will use a collection of smaller combination logic circuits called logic gates Logic gates are simple circuits each with only a handful of transistors that can be wired together to implement any CL function In CS61c we consider logic gates are primitive elements they are the basic building blocks for our circuits Here are some common logic gates For each we show its name its graphical representation and a truth table that defines its function AND OR NOT XOR NAND NOR ab 00 01 10 11 ab 00 01 10 11 c 0 0 0 1 c 0 1 1 1 a b 0 1 1 0 ab c 00 0 01 1 10 1 11 0 ab c 00 1 01 1 10 1 11 0 ab c 00 1 01 0 10 0 11 0 The NOT gate is commonly called an inverter Except for NOT we have shown 2 input versions of these gates Versions of these gates with more than two inputs also exist However for performance reasons the number of inputs to logic gates is usually restricted to around a maximum of four The function of these gates with more than two inputs is obvious from the function of the two input version except in the case of the the exclusive or gate CS61c Lecture Notes 5 XOR For more than two inputs the XOR gate generates a 1 at its output if the number of 1 s at its input is odd Below is shown the truth table for a three input XOR gate a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c 0 1 0 1 0 1 0 1 y 0 1 1 0 1 0 0 1 These simple logic gates can be wired together to build useful circuits In fact any CL block can be implemented with nothing but logic gates For instance below is the circuit for the majority function If we want to understand the operation of the circuit for any particular set of input values we can manually apply the values to the circuit propagating the correct value to the output of each logic gate and finally to the output In this case applying an input pattern of 001 would result in an output of 0 whereas an input pattern of 101 would result in a 1 at the output We could fully characterize the function of this circuit by trying all possible input patterns to generate a true table Here is another example It is the OUTPUT function from the finite state machine problem presented last time The truth table and corresponding circuit is shown below PS 00 00 01 01 10 10 INPUT 0 1 0 1 0 1 OUTPUT 0 0 0 0 0 1 In this case the circuit should output a 1 iff the input pattern is 101 …
View Full Document
Unlocking...