Transcript Logic gate level part 1

Logic Gate Level
Combinational Circuits, Part 1
Circuits
• Circuit: collection of devices
physically connected by wires
to form a network
• Net can be:
– combinational: input
determines output
– sequential: output not entirely
dependent on input
• We will focus first on
combinational networks
Black box view of
network
Inputs: a, b, c
Outputs: x, y
Describing combinational networks
• 3 common methods for describing
combinational networks, ordered from most
to least abstract:
– Truth tables
– Boolean expressions
– Logic diagrams
Truth tables
• Most like black box view:
– specifies what network does, not how
– lists output for every possible combination of
input values
• Next slide illustrates truth table for a 3-input,
2-output combinational network
• Note that the table has 8 entries – in general,
n inputs translates to 2n entries
Truth table
a
b
c
x
y
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
1
0
0
1
1
0
0
0
1
1
1
0
0
Boolean algebra
• A Boolean algebraic expression describes both
what a network does and how it does it
• Boolean values:
1 = true
0 = false
• Binary operations in order of precedence:
 = AND (may be omitted; ab same as a  b)
+ = OR
• Unary operation: ’ = NOT
Fundamental properties of Boolean
algebra
Commutative
a+b=b+a
Associative
(a + b) + c = a + (b + c)
Distributive
a + (bc) = (a + b)(a + c)
Identity
a+0=a
Complement
a + a’ = 1
ab =ba
(ab)c = a(bc)
a(b + c) = ab + ac
a1=a
a  a’ = 0
Note, in particular, how the distributive property of Boolean
algebra differs from regular algebra – in regular algebra,
multiplication (denoted with ) distibrutes over addition (+), but
not vice versa, as the operations represented by these symbols
(AND and OR) do in Boolean algebra
Duality
• Boolean algebra has symmetry that doesn’t
exist in regular algebra: every property (and
thus every expression) has a dual
• To construct the dual of an expression:
– exchange + and  operations
– exchange 1 and 0
• Examples
– the dual of c(a + b) is c + ab
– the dual of x + 0 is x  1
Simplifying expressions
• Duality is a useful property in the
simplification of expressions
• Associative properties also permit
simplifications; when a single operator is
involved in a compound expression,
parentheses can be removed
• Example:
– (a + b) + c = a + b + c
Idempotent property
• Weird and fancy way to say that any value ORed with
itself yields the same value:
x+x=x
• Proof:
x + x = (x + x)  1 by the identity property
(x + x)  1 = (x + x)  (x + x’) by complement
(x + x)  (x + x’) = x + (x  x’) by distribution
x + (x  x’) = x + 0 by complement
x + 0 = x by identity
• Same sequence of steps can be used to prove the dual
– so any value ANDed with itself will also yield the
same value
Notes on proofs
• A proof is a sequence of statements in which
substitutions based on the fundamental
properties of Boolean algebra are used to
demonstrate the validity of a theorem
• Once a theorem is proven, we can
immediately assert that its dual is true
More Boolean algebra properties
• Absorption:
–x+1=1
–x0=0
– x + xy = x
– x(x + y) = x
• DeMorgan’s Laws:
– (ab)’ = a’ + b’
– (a + b)’ = a’b’
More Boolean algebra properties
• To prove that one expression is the
complement of another, show that:
– expr1 + expr2 = 1 and
– expr1  expr2 = 0
• DeMorgan’s laws:
– illustrate proving complements
– generalize to more than two variables – e.g. (abc)’
= a’ + b’ + c’
• Complements of complements:
– (x’)’ = x
– 1’ = 0
– 0’ = 1
Another useful operation
• Although any Boolean expression can be written as the
combination of AND, OR and NOT operations, other
operations are common
• The XOR (exclusive or) operation, denoted by the symbol 
has the following truth table for 2 variables (and
generalizes, as the other operations do, to more than 2):
a
1
1
0
0
b
1
0
1
0
ab
0
1
1
0
• XOR takes precedence over OR, has lower precedence than
AND
Logic diagrams
• Logic diagrams are drawings representing the
most detailed version of a circuit
• Each Boolean operation (AND, OR, NOT) is
represented by a gate symbol with multiple
inputs and a single output
• The lines in the drawing represent the wires in
the circuit
Three basic logic gates
Logic diagrams
• It is possible to read a logic diagram as a kind
of blueprint for a circuit, and to construct
physical circuits from such blueprints
• It is actually far more common to use a slightly
different set of gates in physical circuits, as
these are easier to construct
• The next slide illustrates three of the most
common gates
Common logic gates
NAND and NOR gates are logically equivalent to AND and OR
gates followed by inverters. Since NAND is actually easier to
build, ANDs are often constructed as inverted NAND gates.
Relationship between various
representations of combinational nets
• As the illustration below suggests, there is a
one-to-one correspondence between a
boolean expression and a logic diagram
• Each of these might correspond to a single line
in a truth table
Constructing logic diagram from
Boolean expression
• For every  draw a
• For every + draw a
• For every ’ draw a
• Show input(s) as line(s) coming into gate,
output as line coming out
• Final output is output from final gate (not
connected to input of another)
Example: logic diagram for a + b’c
More complicated expression
• The logic diagram above depicts ((ab + bc’)a)’
• For a parenthesized expression, construct
parenthesized portion first
• Note the connectors () used to indicate a
continuation of the same input (for a and b)
Same expression, abbreviated
• Two inverters eliminated: first by including c’ as
an input (instead of c) and second by making the
third AND gate a NAND gate
• In this version, inputs a and b are shown multiple
times – use same symbols, so we know they’re
the same inputs
One more example
• To translate logic diagram to Boolean
expression:
– label output of each gate (starting from left) with
appropriate sub-expression
– output of last gate is full expression