CS270 Colorado State University ------------------------------------------------------------------------ Goals corresponding to Ch. 3 is to learn the answers to the following: ------------------------------------------------------------------------ (1) What is the truth table and symbol for each of the following gates: and, or, not, nand, nor, and xor. (2) Is it possible to fully test a digital logic gate? Why or why not? (3) Given a circuit construct a truth table and a function that are equivalent. (4) Given a truth table construct a circuit and a function that are equivalent. (5) Given a function construct a circuit and a truth table that are equivalent. (6) Is the following set of gates, S = {X, ...}, logically complete? Why or why not? (7) How are the following circuits constructed and what do they do? Mux, Decoder, half-adder, full-adder. (8) How could you construct an X-Bit binary adder? (9) What is the difference between combinational and sequential circuits? (10) How are the following circuits constructed and what do they do? r-s latch, d-latch, and master-slave flip-flop. (11) How could you construct a 2^X-by-Y-Bit Memory? What components to you need and how are they organized? How many bits does such a memory contain? (12) How is a finite state machine implemented in digital logic? ====================== Combinational Logic ====================== Ch 3 through 3.3 ----------------------- Logic Gates and Symbols inverter/not gate AND gate OR gate NAND gate NOR gate XOR gate ------------------------ Unit Testing Logic Gates From wikipedia: "In computer programming, unit testing is a method of testing that verifies the individual units of source code are working properly." Example units include a gate, a function, method, or procedure. Ideally a unit test would ensure that given all possible inputs the unit being tested generates the correct output. At this point you should be able to answer the following: (1) What is the truth table and symbol for each of the following gates: and, or, not, nand, nor, and xor. (2) Is it possible to fully test a digital logic gate? Why or why not? ------------------------------- Building formulas from circuits Example: (see Slide 2 in 05-comb.pdf) - determine number of inputs for circuit - one formula for each output - trace wires backwards from each output to construct the formula based on gates in the circuit ------------------------------- Building circuits from formulas Just reverse the above process or Create truth table first and translate to sum-of-products (disjunctive normal form) ----------------------------------------- Sum-of-Products (disjunctive normal form) -Each term is a minterm. A minterm is a boolean conjunction (AND) in which each input or its negation appears once. -From this form need only a layer of AND gates followed by a layer of OR gates. ----------------------------------------- Process of converting a formula to disjunctive normal form: 1) Create truth table for formula. 2) Create formula with minterm for each set of inputs that results in a 1 as output. 3) Create an AND gate for each minterm. 4) Use disjunctive normal form formula to determine which minterms connect into the OR gate for the output. -------------------------------------- Example to practice building all three Create a truth table, formula, and circuit that implements a 3-bit majority voter circuit. The circuit has 3 bits of input. The output is 1 if two or more of the inputs are 1. Truth Table Function Circuit --------------- De Morgan's Law not (A and B) = (not A) or (not B) also not (A or B) = (not A) and (not B) At this point you should be able to answer the following: (3) Given a circuit construct a truth table and a function that are equivalent. (4) Given a truth table construct a circuit and a function that are equivalent. (5) Given a function construct a circuit and a truth table that are equivalent. --------------------- Logical Completeness (see http://cnx.org/content/m13240/latest/ for more info) A set of gates are logically complete if they are capable of implementing any truth table. AND, OR, and NOT are the only gates we used above to implement any truth table. Therefore, AND, OR, and NOT are logically complete. We can show any set of gates is logically complete by showing their equivalence to the AND, OR, NOT set. (or any other logically complete set). Example: Show {NAND} is a logically complete set. Exercise: Show {NOR} is a logically complete set. At this point you should be able to answer the following: (6) Is the following set of gates, S = {X, ...}, logically complete? Why or why not? ------------------------------ Example Combinational Circuits Decoder -Has n inputs and 2^n outputs. -Output i is 1 iff the n inputs represent the unsigned integer 1. -Only one output is 1, all others are 0. -Really is the set of all possible minterms for a set of inputs. -Useful for interpreting a bit pattern, for example decoding an opcode. Multiplexer (MUX) -Has 2^n data inputs, n select inputs, and 1 output. -The selection inputs determine which one of the 2^n data inputs becomes the output of the MUX. Half Adder 2 inputs 2 outputs (sum and carry) a_i b_i s_i c_{i+1} ----------------------- 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 s_i = (a_i' b_i) OR (a_i b_i') c_i = a_i b_i Full Adder -performs binary addition for column i a_{n-1} a_{n-2} ... a_1 a_0 b_{n-1} b_{n-2} ... b_1 b_0 c_{n-1} c_{n-2} ... c_1 0 -------------------------------- s_{n-1} s_{n-2} ... s_1 s_0 a_i b_i c_i c_{i+1} s_i --------------------------- ------------------ X-bit binary adder -Chain together X full adders. The initial carry bit is zero. At this point you should be able to answer the following: (7) How are the following circuits constructed and what do they do? Mux, Decoder, half-adder, full-adder. (8) How could you construct an X-Bit binary adder? ------------------------ mstrout@cs.colostate.edu, 9/7/08