Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

DIGITAL DESIGN FUNDAMENTALS

Logical Gates
• Keep in mind that computers work on an electrical flow where
a high voltage is considered a 1 and a low voltage is considered
a 0
...

• Electronic circuits must be designed to manipulate these
positive and negative pulses into meaningful logic
...
Combinations of logic gates form circuits designed
with specific tasks in mind
...

2

Binary Logic and Gates
• Binary variables take on one of two values
...

• Basic logical operators are the logic functions AND, OR and
NOT
...


3

Binary Variables
• Recall that the two binary values have different names:
–
–
–
–

True/False
On/Off
Yes/No
1/0

• We use 1 and 0 to denote the two values
...

• OR is denoted by a plus (+)
...


5

AND
x
out
y

amplitude

x

y

out =
xy

0

0

0

0

1

0

1

0

0

1

1

1

0 1 0 1
Y(t)

• Output is one if every input has value of 1
• More than two values can be “and-ed” together

0 0 1 1
X(t)

• For example xyz = 1 only if x=1, y=1 and z=1

0 0 0 1
out(t)= x(t) and y(t)
6

OR
x

y

out =
x+y

0

0

0

0

1

1

1

0

1

1

1

1

x
out
y

amplitude
• Output is 1 if at least one input is 1
...

• For example x+y+z = 1 if at least one of the
three values is 1
...

• Its output is the complement of its input
...


0 1 0 1
Y(t)
0

0 1

1
X(t)

1

1 1 0
out(t)= x(t) NAND y(t)
9

NOR
x

out = x
NOR y

y

0

0

1

0

1

0

1

0

0

1

1

0

x
out
y

• Output value is the complemented output
from an “OR” function
...


amplitude
0 1 0 1
Y(t)
0 0 1

1
X(t)

0 1 1

out

0
out(t)= x(t) xor y(t)

•More than two values can be “xor-ed”
together
...


11

XNOR
x

y

out =x
xnor y

0

0

1

0

1

0

1

0

0

1

1

1

amplitude
0

1

0

x
out
y

• Output value is the complemented output
from an “XOR” function
...
B

OR

A+B

NOT
NAND
NOR
EX-OR
EX-NOR

A’
(A
...
B) + (A
...
B) + (A’B’) or (A ⊕ B)’

1
0
0
1

13

Truth Tables
• Used to evaluate any logic function
• Consider F(X, Y, Z) = X Y + Y Z

X

Y

Z

XY

Y

YZ

F=XY+YZ

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
0
0
0
0
0
1
1

1
1
0
0
1
1
0
0

0
1
0
0
0
1
0
0

0
1
0
0
0
1
1
1
14

Logic Diagrams and Expressions
Truth Table
XYZ

F = X + Y ×Z

000

0

001

1

010

0

011

0

100

1

101

1

110

1

111

1

Logic Equation

F = X +Y Z
Logic Diagram
X
F

Y
Z

• Boolean equations, truth tables and logic diagrams describe the same function!
• Truth tables are unique, but expressions and logic diagrams are not
...

15

Why UNIVERSAL GATES
• NAND and NOR both are called as universal gate
...

• In practice, this is advantageous since NAND and NOR gates are
economical and easier to fabricate and are the basic gates used in all IC
digital logic families
...


One NAND input pin is connected to the input signal A while all other input
pins are connected to logic 1
...


17

REALIZATION USING NAND
• AND GATE
An AND gate can be replaced by NAND gates as shown in the figure (The
AND is replaced by a NAND gate with its output complemented by a
NAND gate inverter)
...


19

REALIZATION USING NOR
• NOT GATE
All NOR input pins connect to the input signal A gives an output A’
...
The output will be A’
...

• We study Boolean algebra as a foundation for designing and
analyzing digital systems!
1854: Logical algebra was published by George Boole  known
today as “Boolean Algebra”
– It’s a convenient way and systematic way of expressing and
analyzing the operation of logic circuits
...

23

Commutative Laws
• The commutative law of addition for two variables is written
as: A+B = B+A
A
B

A+B



B
A

B+A

• The commutative law of multiplication for two variables is
written as: AB = BA
A
B

AB



B
A

B+A

24

Associative Laws
• The associative law of addition for 3 variables is written as:

A+(B+C) = (A+B)+C
A
B
C

A+(B+C)



A

A+B

B
C

B+C

(A+B)+C

• The associative law of multiplication for 3 variables is written
as: A(BC) = (AB)C
A
B
C

A(BC)
BC



A
B
C

AB

(AB)C

25

Distributive Laws
• The distributive law is written for 3 variables as follows:

A(B+C) = AB + AC
B

A

B+C

C

X

A



B

X

A
C

X=A(B+C)

AB

AC

X=AB+AC

26

Rules of Boolean Algebra
1
...
A + 1 = 1
3
...
A  1 = A
5
...
A + A = 1

7
...
A  A = 0
9
...
A + AB = A
11
...
( A + B)( A + C ) = A + BC

___________________________________________________________
A, B, and C can represent a single variable or a combination of variables
...


28

deMorgan’s theoreMs
• The complement of two or
more ANDed variables is
equivalent to the OR of the
complements of the
individual variables
...


NAND

Negative-OR

X Y = X + Y
NOR

Negative-AND

X + Y = X Y
29

deMorgan’s theoreMs (exercises)
• Apply DeMorgan’s theorems to the expressions:
X Y  Z
X +Y + Z
X +Y + Z
W  X Y  Z
( A + B + C)D
ABC + DEF
AB + C D + EF
A + BC + D ( E + F )

30

Boolean Expression for a Logic Circuit
• To derive the Boolean expression for a given logic circuit,
begin at the left-most inputs and work toward the final output,
writing the expression for each gate
...


X +0= X

2
...
1=X

3
...


X
...


X+X=X

6
...
X = X

Idempotence

7
...


X
...


X=X

10
...


XY = YX

Commutative

12
...
X(Y + Z) = XY + XZ

13
...


X + YZ = (X + Y) (X + Z)

Distributive

16
...
Y

17
...
Y = X + Y

DeMorgan’s
32

Some Properties of Boolean Algebra
 Boolean Algebra is defined in general by a set B that can have more than
two values
 A two-valued Boolean algebra is also know as Switching Algebra
...
Switching circuits can be
represented by this algebra
...


 The identities appear in dual pairs
...
e
...



Sometimes, the dot symbol ‘’ (AND operator) is not written when the
meaning is clear

33

Dual of a Boolean Expression
• Example: F = (A + C) · B + 0
dual F = (A · C + B) · 1 = A · C + B
• Example: G = X · Y + (W + Z)
dual G = (X+Y) · (W · Z) = (X+Y) · (W+Z)
• Example: H = A · B + A · C + B · C
dual H = (A+B) · (A+C) · (B+C)
• Unless it happens to be self-dual, the dual of an expression
does not equal the expression itself
• Are any of these functions self-dual? H is self-dual
(A+B)(A+C)(B+C)=(A+BC)(B+C)=AB+AC+BC

34

Boolean Operator Precedence
 The order of evaluation is:



1
...


NOT

3
...


OR

Consequence: Parentheses appear
around OR expressions

 Example: F = A(B + C)(C + D)
35

Boolean Algebraic Proof – Example 1
• A+A·B=A
Proof Steps
A+A·B
=A·1+A·B
= A · ( 1 + B)
=A·1
=A

(Absorption Theorem)
Justification
Identity element: A · 1 = A
Distributive

1+B=1
Identity element

• Our primary reason for doing proofs is to learn:
– Careful and efficient use of the identities and theorems of
Boolean algebra, and
– How to choose the appropriate identity or theorem to apply to
make forward progress, irrespective of the application
...
1 + A’C
...
Interchange AND and OR operators
2
...

• Given that each binary variable may appear normal (e
...
, x) or
complemented (e
...
x’ ), there are 2n minterms for n variables
...


43

Maxterms
• Maxterms are OR terms with every variable in true or
complemented form
...
g
...
g
...

• Example: Two variables (X and Y) produce
2 x 2 = 4 combinations:
X + Y (both normal)
X + Y (x normal, y complemented)
X + Y (x complemented, y normal)
X + Y (both complemented)

44

Minterms & Maxterms for 2 variables
• Two variable minterms and maxterms
...

• The maxterm is the complement of the minterm

45

Minterms & Maxterms for 3 variables
x
0
0
0
0
1
1
1
1

y
0
0
1
1
0
0
1
1

z
0
1
0
1
0
1
0
1

Index
0
1
2
3
4
5
6
7

Minterm
m0 = x y z
m1 = x y z
m2 = x y z
m3 = x y z
m4 = x y z
m5 = x y z
m6 = x y z
m7 = x y z

Maxterm
M0 = x + y + z
M1 = x + y + z
M2 = x + y + z
M3 = x + y + z
M4 = x + y + z
M5 = x + y + z
M6 = x + y + z
M7 = x + y + z

Maxterm Mi is the complement of minterm mi
Mi = mi and mi = Mi
46

Purpose of the Index
• Minterms and Maxterms are designated with an index
• The index number corresponds to a binary pattern
• The index for the minterm or maxterm, expressed as a binary
number, is used to determine whether the variable is shown in
the true or complemented form
• For Minterms:
– ‘1’ means the variable is “Not Complemented” and
– ‘0’ means the variable is “Complemented”
...

47

Standard Order
• All variables should be present in a minterm or maxterm and
should be listed in the same order (usually alphabetically)
• Example: For variables a, b, c:
– Maxterms (a + b + c), (a + b + c) are in standard order
– However, (b + a + c) is NOT in standard order
(a + c) does NOT contain all variables
– Minterms (a b c) and (a b c) are in standard order
– However, (b a c) is not in standard order
(a c) does not contain all variables

48

Sum-Of-Minterm (SOM)
• Sum-Of-Minterm (SOM) canonical form:
Sum of minterms of entries that evaluate to ‘1’

x

y

z

F

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
1
0
0
0
0
1
1

Minterm
m1 = x y z

Focus on
the ‘1’
entries

m6 = x y z
m7 = x y z

F = m1 + m6 + m7 = ∑ (1, 6, 7) = x y z + x y z + x y z
49

Sum-Of-Minterm Examples
•

F(a, b, c, d) = ∑(2, 3, 6, 10, 11)

• F(a, b, c, d) = m2 + m3 + m6 + m10 + m11

a b c d+ a b c d+ a b c d+ a b c d+ a b c d
• G(a, b, c, d) = ∑(0, 1, 12, 15)
• G(a, b, c, d) = m0 + m1 + m12 + m15

a b c d+ a b c d+ a b c d+ a b c d

50

Product-Of-Maxterm (POM)
• Product-Of-Maxterm (POM) canonical form:
Product of maxterms of entries that evaluate to ‘0’

x

y

z

F

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

1
1
0
1
0
1
0
1

Maxterm
M2 = (x + y + z)

Focus on
the ‘0’
entries

M4 = (x + y + z)
M6 = (x + y + z)

F = M2·M4·M6 = ∏ (2, 4, 6) = (x+y+z) (x+y+z) (x+y+z)
51

Product-Of-Maxterm Examples
• F(a, b, c, d) = ∏(1, 3, 6, 11)
• F(a, b, c, d) = M1 · M3 · M6 · M11

(a+b+c+d) (a+b+c+d) (a+b+c+d) (a+b+c+d)
• G(a, b, c, d) = ∏(0, 4, 12, 15)
• G(a, b, c, d) = M0 · M4 · M12 · M15

(a+b+c+d)(a+b+c+d) (a+b+c+d)(a+b+c+d)
52

Observations
• We can implement any function by "ORing" the minterms
corresponding to the ‘1’ entries in the function table
...

• We can implement any function by "ANDing" the maxterms
corresponding to ‘0’ entries in the function table
...

• The same Boolean function can be expressed in two canonical
ways: Sum-of-Minterms (SOM) and Product-of-Maxterms
(POM)
...

However, if it has fewer ‘0’ entries then the POM form will
have fewer literals than SOM
...
M2 = ∏ (2, 5)

58

Function Complements
• The complement of a function expressed as a sum of
minterms is constructed by selecting the minterms missing
in the sum-of-minterms canonical form
• Alternatively, the complement of a function expressed by a
Sum of Minterms form is simply the Product of Maxterms
with the same indices
• Example: Given F(x, y, z) = ∑ (1, 3, 5, 7)

F(x, y, z) = ∑ (0, 2, 4, 6)
F(x, y, z) = ∏ (0, 2, 4, 6)

59

• A Simplification Example:

(1,4,5,6,7)
S
Writing the minterm expression:
F( A, B, C) =

•

F = A B C + A B C + A B C + ABC + ABC
• Simplifying:
F = A B C + A (B C + B C + B C + B C)
F = A B C + A (B (C + C) + B (C + C))
F = A B C + A (B + B)
F=ABC+A
F=BC+A
• Simplified F contains 3 literals

60

AND/OR Two-Level Implementation
• The two implementations for F are shown below
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C

A

F

B
C

F

It is quite
apparent
which is
simpler!
61

Example
• Minimize the following Boolean function using
sum of products (SOP):
• f(a,b,c,d) = m(3,7,11,12,13,14,15)

abcd
3 0011
7 0111
11 1011
12 1100
13 1101
14 1110
15 1111

f(a,b,c,d) = m(3,7,11,12,13,14,15)

a`b`cd
a`bcd
ab`cd
abc`d`
abc`d
abcd`
abcd

=a`b`cd + a`bcd + ab`cd + abc`d`+ abc`d + abcd`
+ abcd
=cd(a`b` + a`b + ab`) + ab(c`d` + c`d + cd` +
cd )
=cd(a`[b` + b] + ab`) + ab(c`[d` + d] + c[d` + d])
=cd(a`[1] + ab`) + ab(c`[1] + c[1])
=ab+ab`cd + a`cd
=ab+cd(ab` + a`)
=ab+ cd(a + a`)(a`+b`)
= ab + a`cd + b`cd
= ab +cd(a` + b`)
62

Example
f(a,b,c,d) = M(0,1,2,4,5,6,8,9,10)
=m(3,7,11,12,13,14,15)
=[(a+b+c+d)(a+b+c+d`)(a+b`+c`+d`)
(a`+b+c`+d`)(a`+b`+c+ d)(a`+b`+c+ d`)
(a`+b`+c`+d)(a`+b`+c`+d`)]

63

Karnaugh maps
• A graphical technique for simplifying an expression into a minimal sum of
products (MSP) form:
– There are a minimal number of product terms in the expression
...

• Circuit-wise, this leads to a minimal two-level implementation
...

• K-maps are tables of rows and columns with entries represent
1`s or 0`s of SOP and POS representations
...

• K-map cells are labeled with the corresponding truth-table row
...

• If mi is a minterm of f, then place a 1 in cell i of the K-map
...

• If di is a don’t care of f, then place a d or x in cell i
...
We can re-arrange
these minterms into a Karnaugh map
...

– Minterms on the left and right sides contain y’ and y respectively
...

Y

X

0
1

0
x’y’
xy’

1
x’y
xy

X’
X

Y’
x’y’
xy’

Y
x’y
xy

66

Karnaugh map simplifications
• Imagine a two-variable sum of minterms:
x’y’ + x’y
X

x’y’
xy’

Y
x’y
xy

• Both of these minterms appear in the top row of a Karnaugh map, which
means that they both contain the literal x’
...

Y
x’y
xy

x’y’
xy’

X

– Both minterms appear in the right side, where y is uncomplemented
...


• How about x’y’ + x’y + xy
X

x’y’
xy’

Y
x’y
xy

– We have x’y’ + x’y in the top row, corresponding to x’
...

– This whole expression can be reduced to x’ + y
...

Y

X

x’y’z’
xy’z’

x’y’z
xy’z

x’yz
xyz

x’yz’
xyz’

Z

x’y’z + x’yz
= x’z(y’ + y)
= x’z  1
= x’z

• “Adjacency” includes wrapping around the left and right sides:
Y
X

x’y’z’
xy’z’

x’y’z
xy’z

x’yz
xyz
Z

x’yz’
xyz’

=
=
=
=

x’y’z’ + xy’z’ + x’yz’ + xyz’
z’(x’y’ + xy’ + x’y + xy)
z’(y’(x’ + x) + y(x’ + x))
z’(y’+y)
z’

• We’ll use this property of adjacent squares to do our
simplifications
...

• First, you should convert the
expression into a sum of minterms
form, if it’s not already
...

– You can either write out the
literals or use the minterm
shorthand
...

– Apply the distributive law in reverse to add in missing variables
...

xy + y’z + xz = (xy  1) + (y’z  1) + (xz  1)
= (xy  (z’ + z)) + (y’z  (x’ + x)) + (xz  (y’ + y))
= (xyz’ + xyz) + (x’y’z + xy’z) + (xy’z + xyz)
= xyz’ + xyz + x’y’z + xy’z

• In both cases, we’re actually “unsimplifying” our example expression
...

72

Making the example K-map
• Next up is drawing and filling in the K-map
...

– You can use either the minterm products or the shorthand to show you
where the 1s and 0s belong
...

f(x,y,z) = x’y’z + xy’z + xyz’ + xyz

f(x,y,z) = m1 + m5 + m6 + m7

Y
X

x’y’z’
xy’z’

x’y’z
xy’z

x’yz
xyz

Y

x’yz’
xyz’

X

Z

m0
m4

m1
m5

m3
m7

m2
m6

Z

• In either case, the resulting K-map is shown below
...

– The output in row i of the table goes into square mi of the K-map
...
”
x

y

z

f(x,y,z)

0
0
0
0

0
0
1
1

0
1
0
1

0
1
0
0

Y
X

0
0
1
1

0
1
0
1

0
1
1
1

m1
m5

m3
m7

m2
m6

Z
Y
X

1
1
1
1

m0
m4

0
0

1
1

0
1

0
1

Z

74

Grouping the minterms together
• The most difficult step is grouping together all the 1s in the K-map
...

– All of the 1s in the map should be included in at least one rectangle
...

Y

X

0
0

1
1

0
1

0
1

Z

• Each group corresponds to one product term
...

– Make each rectangle as large as possible, to minimize the number of
literals in each term
...

75

Reading the MSP from the K-map
• Finally, you can find the MSP
...

– The product is determined by finding the common literals in
that rectangle
...
(This is
one of the additional algebraic laws from last time
...

Y
X
Z

Y
X

m0
m4

m1
m5

m3
m7

m2
m6

Z

77

Solutions for practice K-map 1
• Here is the filled in K-map, with all groups shown
...

– Minterm m6 is in a group all by its lonesome
...


78

Four-variable K-maps
• We can do four-variable expressions too!
– The minterms in the third and fourth columns, and in the third and fourth
rows, are switched around
...

Y

W

w’x’y’z’
w’xy’z’
wxy’z’
wx’y’z’

w’x’y’z
w’xy’z
wxy’z
wx’y’z

w’x’yz
w’xyz
wxyz
wx’yz
Z

Y

w’x’yz’
w’xyz’
X
wxyz’
wx’yz’

W

m0
m4
m12
m8

m1
m5
m13
m9

m3
m7
m15
m11

m2
m6
X
m14
m10

Z

• Grouping minterms is similar to the three-variable case, but:
– You can have rectangular groups of 1, 2, 4, 8 or 16 minterms
...

79

Example: Simplify
m0+m2+m5+m8+m10+m13
• The expression is already a sum of minterms, so here’s the K-map:
Y

W

1
0
0
1

0
1
1
0

0
0
0
0

1
0
0
1

Y

X
W

Z

W

0
1
1
0

0
0
0
0
Z

m1
m5
m13
m9

m3
m7
m15
m11

m2
m6
m14
m10

X

Z
Y

Y
1
0
0
1

m0
m4
m12
m8

1
0
0
1

X

W

w’x’y’z’
w’xy’z’
wxy’z’
wx’y’z’

w’x’y’z
w’xy’z
wxy’z
wx’y’z

w’x’yz
w’xyz
wxyz
wx’yz

w’x’yz’
w’xyz’
X
wxyz’
wx’yz’

Z

• We can make the following groups, resulting in the MSP x’z’ + xy’z
...
The K-map below
yields two valid and equivalent MSPs, because there are two
possible ways to include minterm m7
...


1
1

81

Examples
• Two variable K-map
f(A,B)=m(0,1,3)=A`B`+A`B+AB

B 0

A 0

1

1

1

0

1

1

82

Examples-Three variable map
• f(A,B,C) = m(0,3,5)=
A`B`C`+A`BC+AB`C
A`B` A`B
0 0 0 1
C`
0
C
1

A B
1 1

A B`
1 0

1
A`B`C`

1

1

A`BC

AB`C
83

Universal set
A

Example

BC

Simplify f= A`BC`+ A B C`+ A B C using;
(a) SumCof minterms
...

B
AB
• Each cell of an n-variable K-map
has n logically adjacent
(a)
cells
...
(b) Maxterm form
...

R

S

T

U

F3

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

0

1

0

0

0

0

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

0

0

0

0

1

0

0

1

1

1

0

1

0

0

1

0

1

1

0

1

1

0

0

1

1

1

0

1

0

1

1

1

0

1

1

1

1

1

1

V

92

Example : 4 Variable K-Map
Example:
After labeling and transferring the truth-table data into the K-Map, write
the simplified sum-of-products (SOP) logic expression for the logic
function F3
...

• A don’t care condition can be treated as a (0) or a (1) in a K-Map
...

• Treating a don’t care as a (1) allows you to make a grouping
larger, resulting in a simpler term in the SOP equation
...
This
allowed the grouping of a single one to become a
grouping of two, resulting in a simpler term
...

95

Example : don’t care Conditions
Example:
After labeling and transferring the truth table data into the K-Map, write
the simplified sum-of-products (SOP) logic expression for the logic
function F4
...

V
R

S

T

U

F4

0

0

0

0

X

0

0

0

1

0

0

0

1

0

1

0

0

1

1

X

0

1

0

0

0

0

1

0

1

X

0

1

1

0

X

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

X

1

1

0

0

X

1

1

0

1

0

1

1

1

0

0

1

1

1

1

0

96

Example : don’t care Conditions
Example:
After labeling and transferring the truth table data into the K-Map, write
the simplified sum-of-products (SOP) logic expression for the logic
function F4
...
R T

Solution:

R

S

T

U

F4

0

0

0

0

X

0

0

0

1

0

0

0

1

0

1

0

0

1

1

X

0

1

0

0

0

0

1

0

1

X

0

1

1

0

X

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

X

1

1

0

0

X

1

1

0

1

0

1

1

1

0

0

1

1

1

1

0

TU

TU

TU

TU

RS

X

0

X

1

RS

0

X

1

X

RS

X

0

0

0

RS

1

1

X

1

F4 = R T + R S

RS

97



---