CHAPTER OUTLINE Chapter 2 of the textbook discusses the design and implementation of combinational design circuits. 1. Introduction Circuits are networks that are used to process discrete variables. Black boxes help describe these circuits, giving details about their inputs, outputs, timing and the functional relationships between inputs and outputs. Circuits can either be combinational or sequential. Combinational circuits are memoryless and the output is based exclusivly on the inputs. Combinational circuits functionality specifications are described either by a truth table, or a Boolean equation. Sequential circuits depend both on the current and the previous inputs. For a circuit to be combinational it must be composed of only combinational elements, it must have no cyclical paths, and every node must be either an input, or be connected to a single output of a circuit element. 2. Boolean Equations Boolean equations are the best way to represent the functionality of circuits because digital logic is based on 2 values, on or off. Boolean equations also describe functions with variables with only two values, TRUE or FALSE. The order of precedence in Boolean logic goes from NOT to AND to OR, with NOT having the highest precedence and OR having the least. This section describes two ways to derive a Boolean equation from a truth table: Sum-of-Products form and Product-of-Sums form. The Sum-of-Products from is found by adding (or “ORing”) each minterm in which the corresponding output is TRUE in the truth table. The Product-of-Sums form is found by taking the product of each maxterm where its corresponding output is FALSE in the truth table. Sum-of-Products produces a shorter equation when there are less TRUE rows than FALSE rows on the truth table and otherwise the Product-of-Sums produces a shorter equation. 3. Boolean Algebra Boolean algebra is used to rewrite Boolean equations, just as you would rewrite a normal equation with algebra. The axioms of Boolean algebra are used to prove the theorems that we use to help simplify these equations. In Boolean algebra, every axiom and theorem must obey the principle of duality. That is, if every 1 and 0 were flipped and if every AND and OR were flipped, the equation would still be true. Imporant single variable theorems from this section include: the identity theorem, the null element theorem, the idempotency theorem, the involution theorem and the complement theorem. Important multiple variable theorems include: commutativity, associativity, distributivity, covering, combining, consensus and De Morgans theorem. De Morgans theorem essentially says that if you invert the inputs of an OR gate, you end up with a NAND gate. If you invert the inputs to an AND gate you end up with a NOR gate. To prove a theorem with finite variables is true, all you have to do is show that the theorem holds true for every single possible value for these variables. 4. From Logic to Gates Schematics for circuits are easiest to read and debug when they are drawn consistently. For example, it is best to put the inputs on the top or on the left hand side and the outputs on the right or bottom side of the schematic. Most gates and wires should flow from right to left or up to down. Wires that cross at T junctions and 4 way junctions with a dot in the middle connect, otherwise they don’t. To make logic gates out of a Boolean equation in Sum-of-Products form first create columns for each input and use AND gates to combine the minterms, then OR the outputs together to get the output for the circuit. 5. Multilevel Combinational Logic Two-level logic is a circuit with logic that combines a layer of AND gates with a layer of OR gates, like when a sum-of-products equation is implemented. Circuits can be created with less gates if they are made in a multilevel fashion. For example, a 3 input XOR gate can be made with 4 AND gates and an OR gate, or it can be made with only 2 2-input XOR gates. When working with multilevel circuits that deal with NAND and NOR gates, bubble pushing can be useful to help get an idea for what it is doing. 6. X’s and Z’s, Oh My In digital logic, X’s are used to describe illegal outputs that can be either 1 or 0 based on the logic. When X is describing an input it can mean that it is undefined. When X appears in a truth table it means that the value doesn’t matter to the designer. Z’s are used to represent nodes that have neither a value of 1 or 0. These are not always considered an error. Tristate buffers are circuits that output Z’s if they are not enabled, but if they are they output 1 or 0. These were useful when connecting multiple chips to a bus so they don’t “interrupt” the other chip’s output. 7. Karnaugh Maps K-maps can be used to help minimize Boolean equations. Computer programs can give the most efficient form of logic possible, but the K-maps and Boolean algebra are insightful tools to help learn about how digital logic works. 8. Combinational Building Blocks A application of abstraction is using building blocks to represent circuits more simply and to show the bigger picture more clearly. Examples of building blocks include: full-adders, priority circuits, and seven segment displays. Multiplexers are combinational building blocks that choose an input value as its output based on an input signal. Decoders are combinational building blocks that, given 2 inputs, output a 1 on one of its 4 outputs based on the combination given by the 2 inputs. The first output would be 1 if both inputs were 0. If the second input was 1 and the other was 0, the second output would be one, and so forth. 9. Timing A propagation delay in a circuit is the maximum time it takes for a circuits outputs to change when its inputs have changed. A contamination delay is the minimum time it takes for an output to change when one of its inputs has changed. The critical path of a circuit is the shortest line from input to output. The output of this line is faster than the rest of the circuit. Glitches occur in a circuit when the output is changed incorrectly momentarily due to inner timing of the circuit. They eventually straighten themselves out, so it is the designers decision to either allow it to exist or design around it. 10. Summary Combinational logic is logic that only depends on the current values of the inputs. Their functionality can either be described by Boolean equations or truth tables. Boolean equations can be simplified by either using Boolean algebra, or K-maps. Circuits can be abstracted using combinational building blocks, which allow you to describe more complicated circuits quickly and clearly. The timing of a circuit can either be described by the propagation delay or the contamination delay, and these delays can cause glitches.