CS61c: Representations of Combinational Logic CircuitsJ. WawrzynekMarch 5, 20031 IntroductionRecall that synchronous systems are composed of two basic types of circuits, combination logic circuits,and state elements. Combination logic circuits without memory that produce outputs based purely ontheir input signals. State elements, on the other hand, are circuits that remember their input signalvalues. In the previous lecture we looked at the internal details of registers. We found that everyregister, regardless of its use has the same internal structure. Combinational logic (CL) blocks, on theother hand, are all different from one another. The internal circuit structure of each is tailored to thefunctional requirements of that particular circuit.In this lecture we will look at three different ways to represent the function and structure of acombination logic block.2 Truth-TablesCombinational logic circuit behavior can be specified by enumerating the functional relationship be-tween input values and output values. For each input pattern of 1’s and 0’s applied to the CL circuitblock, there exists a single output pattern. This input/output relationship is commonly enumerated in atabular form, called a truth-table. In general, a truth-table takes the form shown below. Below is thegeneral form for a truth-table representing a circuit block with four inputs:12 Wawrzynek 2003cUCBa b c d y0 0 0 0 F(0,0,0,0)0 0 0 1 F(0,0,0,1)0 0 1 0 F(0,0,1,0)0 0 1 1 F(0,0,1,1)0 1 0 0 F(0,1,0,0)0 1 0 1 F(0,1,0,1)0 1 1 0 F(0,1,1,0)1 1 1 1 F(0,1,1,1)1 0 0 0 F(1,0,0,0)1 0 0 1 F(1,0,0,1)1 0 1 0 F(1,0,1,0)1 0 1 1 F(1,0,1,1)1 1 0 0 F(1,1,0,0)1 1 0 1 F(1,1,0,1)1 1 1 0 F(1,1,1,0)1 1 1 1 F(1,1,1,1)For each row of the table, the output column shows the output value of the block for the input patternshown in the input columns.Many CL blocks have more than one output, or a single output that is more than one bit wide. Inthese cases, each single bit output gets its own truth-table. Often they are combined into a single tablewith 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 ifone, but not both, of the inputs is a 1.a b y0 0 00 1 11 0 11 1 0CS61c Lecture Notes 32. A 2-bit wide unsigned adder circuit with a 3-bit wide output:A B Ca1a0b1b0c2c1c000 00 00000 01 00100 10 01000 11 01101 00 00101 01 01001 10 01101 11 10010 00 01010 01 01110 10 10010 11 10111 00 01111 01 10011 10 10111 11 1103. 32-bit unsigned adder with 33-bit output:A B C000 ... 0 000 ... 0 000 ... 00000 ... 0 000 ... 1 000 ... 01. . .. . .. . .111 ... 1 111 ... 1 111 ... 10This table has 264 rows!In principle, the function of any combination logic circuit can be completely specified with truth-tables, in practice some are too big.4 Wawrzynek 2003cUCB4. From the lecture notes “State Elements: Circuits That Remember”, the finite state machine nextstate and output logic.PS INPUT NS OUTPUT00 0 00 000 1 01 001 0 00 001 1 10 010 0 00 010 1 00 15. Three input majority circuit. The output y takes on the value that matches the majority value ofthe inputs:a b c y0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1CS61c Lecture Notes 53 Logic GatesWhat do we do if we need to determine the circuit details for a combinational logic block? In mostcases we will use a collection of smaller combination logic circuits called logic gates. Logic gates aresimple circuits (each with only a handful of transistors) that can be wired together to implement any CLfunction. In CS61c we treat logic gates as primitive elements; they are the basic building blocks for ourcircuits.Here are some common logic gates. For each we show its name, its graphical representation, and atruth-table that defines its function:ANDab c00 001 010 011 1ORab c00 001 110 111 1NOTa b0 11 0XORab c00 001 110 111 0NANDab c00 101 110 111 0NORab c00 101 010 011 0The NOT gate is commonly called an inverter.Except for NOT, we have shown 2-input versions of these gates. Versions of these gates with morethan two inputs also exist. However, for performance reasons, the number of inputs to logic gates isusually restricted to around a maximum of four. The function of these gates with more than two inputsis obvious from the function of the two input version, except in the case of the the exclusive-or gate,6 Wawrzynek 2003cUCBXOR. For more than two inputs, the XOR gate generates a 1 at its output if the number of 1’s at its inputis odd. Below is shown the truth-table for a three input XOR gate.a b c y0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1These simple logic gates can be wired together to build useful circuits. In fact, any CL block can beimplemented 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 canmanually 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 of0, whereas an input pattern of 101 would result in a 1 at the output. We could fully characterize thefunction 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 presentedlast time. The truth-table and corresponding circuit is shown below:PS INPUT OUTPUT00 0 000 1 001 0 001 1 010 0 010 1 1In this case, the circuit should output a 1 iff the input pattern is 101. The circuit for that purposeessentially just matches the 101 pattern, when a match occurs, it outputs a 1—for all other input patternsit outputs a 0. Try it!CS61c Lecture Notes 7In general, the complete set of logic gates shown above is not needed to implement any CL function.Select subsets are sufficient. Any CL function can be implemented with nothing other than the setof AND and NOT, the set of OR and NOT, NAND gates only, and NOR gates only. However, forsimplicity, a larger subset is usually employed.A particularly nice subset is the set of AND, OR, and NOT. This set has a directly relationship toBoolean algebra, a mathematical system that we can use to manipulate circuits.Above we explained how to generate a true-table from a given circuit (we simply need to evaluate itfor input combinations). The big question is: How do we go the
View Full Document
Unlocking...