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", "*", middle dot, conjunction symbol [called
wedge, caret, or circumflex]; also implicit when two single-letter
variables are written together)
logical sum ("or", "+", disjunction symbol [called vee or reversed
caret]; sometimes a single vertical bar)
inversion (prefix of "not", "~", negation symbol, "/", sometimes an
exclamation point ("!"); a bar across the top of a variable or term
[called overline]; an apostrophe as suffix)
- any function can be written as a formula involving the three operations
Properties (see also p. B-6)
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, A**A
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
xor symbol is circled plus
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. B-17)
logic minimization
Karnaugh maps (mentioned on p. B-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
e.g., espresso gives two-level gate SOP implementation
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
(pp. B-12 to B-16)
first stage is AND plane - form product terms;
second stage is OR plane - form logical sums
decoder (p. B-9)
n inputs, 2^n outputs (only one of which will be true)
multiplexer (p. B-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 (pp. B-26 to B-30)
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., http://faculty.cs.niu.edu/~berezin/463/lec/03/pla_adder.png)
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)
**