combinational circuits digital / binary logic -- 0 and 1, based on low and high voltage 2-state physical device to easily maintain state separation transistors -> gates -> logic circuits combinational logic -- no memory involved, output depends only on input sequential logic -- memory involved, output depends on past sequence of inputs as well as current input Boolean Algebra - all variables have value either 0 or 1 - operations are logical product ("and", "*"), logical sum ("or", "+"), and inversion ("not", "~") - any function can be written as a formula involving the three operations Properties Identity A*1 = A A+0 = A Annihilation A*0 = 0 A+1 = 1 Idempotence A*A = A A+A = A Commutative A*B = B*A A+B = B+A Associative A*(B*C) = (A*B)*C A+(B+C) = (A+B)+C Distributive A*(B+C) = A*B + A*C A+(B*C) = (A+B)*(A+C) Absorption A*(A+B) = A A+(A*B) = A Cancellation ~(~A) = A Inverse A*(~A) = 0 A + (~A) = 1 DeMorgan's Laws ~(A*B) = (~A)+(~B) ~(A+B) = (~A)*(~B) universal operation sets (computational complete) { and, or, not } { and, not } { nand } { or, not } { nor } truth tables completely describe a logic function A | not A B | and A B | or A B | xor --+---- ----+---- ----+---- ----+---- 0 | 1 0 0 | 0 0 0 | 0 0 0 | 0 1 | 0 0 1 | 0 0 1 | 1 0 1 | 1 1 0 | 0 1 0 | 1 1 0 | 1 1 1 | 1 1 1 | 1 1 1 | 0 16 possible functions of two input variables A = 0 0 1 1 description B = 0 1 0 1 some common names ------------- ----------- --------------------------- 0 false 0 0 0 0 false, zero, clear 1 A and B 0 0 0 1 and 2 A and (not B) 0 0 1 0 and-not, inhibit, A>B 3 A 0 0 1 1 A 4 B and (not A) 0 1 0 0 inhibit, AA 12 not A 1 1 0 0 not A 13 B or (not A) 1 1 0 1 implies, implication, A=>B 14 A nand B 1 1 1 0 nand 15 true 1 1 1 1 true, one, set canonical forms sum of products - logical sum of all truth table rows with an output of 1 product of sums equivalent representations logic expression truth table logic circuit sometimes use don't care bits -- which can be either 0 or 1 according to which makes the logic simpler; shown as an 'x' (or 'd') (see p. C-17) logic minimization Karnaugh maps (mentioned on p. C-18) table of truth table entries with adjacent cells selected for product term simplifications typically done by hand, relies on visual skills limited in practicality to four, maybe five, variables \BC A\ 00 01 11 10 +----+----+----+----+ 0 | | | | | e.g., simplify F = A*B*C + A*B + (~C) +----+----+----+----+ 1 | | | | | +----+----+----+----+ steps for circuit synthesis logic expression -> truth table -> Kmap -> simple expression -> circuit CAD tools - automated minimization and synthesis practical issues gate implementation technology may easily provide nand and nor; see equivalence of two-level nand-nand circuit with and-or transistors are analog devices with non-zero switching times glitch - undesired signal lasting only a short time; race condition - output depends on small differences in signal timing e.g., consider the gate-level timing of A*(~A) implemented with one NOT gate and one AND gate -- is the output of the AND gate ever equal to 1? gate levels (circuit depth) - number of gates on longest path fan-in - number of inputs a logic gate can accept fan-out - number of inputs that can be driven by a logic gate output PLA - programmable logic array - can directly implement a truth table (p. C-12ff) first stage is AND plane - form product terms; second stage is OR plane - form logical sums decoder (p. C-9) n inputs, 2^n outputs (only one of which will be true) multiplexer (p. C-10) n control inputs, 2^n data inputs, one data output n control inputs are used to select one of the 2^n data inputs and route it to the output can be thought of as an extension of a decoder adder (p. C-26 ff) half adder logic - two one-bit inputs (A, B) and two one-bit outputs (carry_out, sum) A 0 0 1 1 + B + 0 + 1 + 0 + 1 -------------- ---- ---- ---- ---- carry_out sum 00 01 01 10 A B | HA_carry_out HA_sum ------+---------------------- 0 0 | 0 0 HA_carry_out = A and B 0 1 | 0 1 1 0 | 0 1 HA_sum = A xor B 1 1 | 1 0 for adding multiple bits, we need to add a carry_in A 0 0 0 0 1 1 1 1 + B + 0 + 0 + 1 + 1 + 0 + 0 + 1 + 1 + carry_in + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 -------------------- ---- ---- ---- ---- ---- ---- ---- ---- FA_carry_out FA_sum 00 01 01 10 01 10 10 11 A B carry_in | FA_carry_out FA_sum ---------------+---------------------- 0 0 0 | 0 0 0 0 1 | 0 1 0 1 0 | 0 1 0 1 1 | 1 0 1 0 0 | 0 1 1 0 1 | 1 0 1 1 0 | 1 0 1 1 1 | 1 1 full adder logic approaches: 1) cascade two half adders (sum output bit of first attached to one input line of the other) and or together the carry_outs 2) PLA (e.g., www.cs.mun.ca/~paul/cs3724/material/web/notes/node10.html) 3) 3x8 decoder with two four-input OR gates n-bit adder built by connecting n full adders, with carries propagating from right to left (i.e., connect the carry_out of an adder to the carry_in of the adder in the next leftmost bit position; the initial, that is, rightmost, carry_in is zero) A_3 B_3 A_2 B_2 A_1 B_1 A_0 B_0 | | .---. | | .---. | | .---. | | .-- 0 | | | | | | | | | | | | | | | V___V___V | V___V___V | V___V___V | V___V___V | full | | | full | | | full | | | full | |__adder__| | |__adder__| | |__adder__| | |__adder__| | | | | | | | | | | | V | `----' | `----' | `----' | carry_out V V V V sum_3 sum_2 sum_1 sum_0 subtraction - invert B_i signals and let initial carry_in = 1 (add inverter and mux, or just an xor, above each full adder to select B_i or ~B_i; select also routed to initial carry in)