Resolução cap5-Introdução aos sistemas digitais-Ercegovac

Prévia do material em texto

55
Chapter 5
Exercise 5.1
f
1
0 1 0 1
0 1 0 0
z
y
x
f
0
-
0 1 1
-
0 0 1
z
y
x
Exercise 5.2
(a) the K-map for E(x; y; z) =
P
m(1; 5; 7) is:
0 1 0 0
0 1 1 0
z
y
x
(b)E(w; x; y; z) = w
0
x
0
y + y
0
z + xz
0
0 1 1 1
1 1 0 1
1 1 0 1
0 1 0 0
z
y
x
w
Exercise 5.3
(a) E(w; x; y; z) =
Q
M(1; 3; 4; 7; 10; 13; 14; 15) =
P
m(0; 2; 5; 6; 8; 9; 11; 12)
1 0 0 1
0 1 0 1
1 0 0 0
1 1 1 0
z
y
x
w
(b)E(w; x; y; z) =
P
m(0; 4; 5; 9; 11; 14; 15); dc(w; x; y; z) =
P
m(2; 8)
56 Solutions Manual - Introduction to Digital Design - January 26, 1999
1 0 0
-
1 1 0 0
0 0 1 1
-
1 1 0
z
y
x
w
(c) E(x; y; z) =
P
m(0; 1; 4; 6) =
Q
M(2; 3; 5; 7)
1 1 0 0
1 0 0 1
z
y
x
Exercise 5.4 f(w; x; y; z) =
P
m(0; 1; 2; 3; 5; 7; 8; 10; 11; 15)
(a) Kmap and prime implicants
1 1 1 1
0 1 1 0
0 0 1 0
1 0 1 1
z
y
x
w
�
�
�
�
�
�
	
��
��
�
�
	
�
�
�
�
prime implicants: w
0
x
0
; w
0
z; x
0
y; yz; x
0
z
0
(b) essential prime implicants: w
0
z; yz; x
0
z
0
(c)The minimal sum of products for this function is unique:
f(w; x; y; z) = w
0
z + yz + x
0
z
0
Exercise 5.5
(a) More implicants than minterms
0 1 1 0
0 0 0 0
z
y
x
�
�
	
�
�
	
�
�
	
implicants: x
0
yz; x
0
y
0
z, and x
0
z
minterms: x
0
yz and x
0
y
0
z
(b) Equal number of implicants and minterms
Solutions Manual - Introduction to Digital Design - January 26, 1999 57
1 0 0 0
0 0 0 0
z
y
x
�
�
	
implicant: x
0
y
0
z
0
minterm: x
0
y
0
z
0
Exercise 5.6
(a) E(w; x; y; z) =
Q
M(1; 3; 4; 7; 10; 13; 14; 15) =
P
m(0; 2; 5; 6; 8; 9; 11; 12)
1 0 0 1
0 1 0 1
1 0 0 0
1 1 1 0
z
y
x
w
�
�
	
�
�
	
�
�
	
�
�
	
�
�
	
minimal sum of products: wy
0
z
0
+ wx
0
z + w
0
x
0
z
0
+ w
0
yz
0
+ w
0
xy
0
z
1 0 0 1
0 1 0 1
1 0 0 0
1 1 1 0
x
y
w
z
�
�
	
�
�
	
�
�
	
�
�
	
�
�
	
minimal product of sums: (w + x+ z
0
)(w
0
+ y
0
+ z)(x
0
+ y
0
+ z
0
)(w
0
+ x
0
+ z
0
)(w + x
0
+ y + z)
58 Solutions Manual - Introduction to Digital Design - January 26, 1999
(b)E(w; x; y; z) =
P
m(0; 4; 5; 9; 11; 14; 15); dc(w; x; y; z) =
P
m(2; 8)
1 0 0
-
1 1 0 0
0 0 1 1
-
1 1 0
z
y
x
w
�
�
	
�
�
	
�
�
	
�
�
	
minimal SP: w
0
y
0
z
0
+ w
0
y
0
x+ wx
0
z + wxy
1 0 0
-
1 1 0 0
0 0 1 1
-
1 1 0
z
y
x
w
�
�
	
�
�
	
�
�
�
�
��
	
minimal PS: (w+x+z')(w+y')(x+y'+z)(w'+x'+y)
(c) E(x; y; z) =
P
m(0; 1; 4; 6) =
Q
M(2; 3; 5; 7)
1 1 0 0
1 0 0 1
z
y
x
�
�
	
�
	
�
minimal sum of products: x
0
y
0
+ xz
0
1 1 0 0
1 0 0 1
z
y
x
�
�
	
�
�
	
minimal product of sums: (x+ y
0
)(x
0
+ z
0
)
Solutions Manual - Introduction to Digital Design - January 26, 1999 59
Exercise 5.7
f(w; x; y; z) = one set(1; 5; 7; 8; 9; 10; 14)
0 1 0 0
0 1 1 0
0 0 0 1
1 1 0 1
z
y
x
w
�
�
	
�
�
�
�
��
� �
�
�
	
�
�
	
�
�
	
�
�
�
�
(a) prime implicates are:
(w + z); (w + x+ y
0
); (x + y
0
+ z
0
); (w
0
+ y
0
+ z
0
); (w
0
+ x
0
+ z
0
); (w
0
+ x
0
+ y); (x
0
+ y + z)
(b) essential prime implicate is: (w + z)
(c) a minimal product of sums expression that implements f(w; x; y; z) is:
E(w; x; y; z) = (w + z)(x+ y
0
+ z
0
)(w
0
+ x
0
+ z
0
)(x
0
+ y + z)
the solution is not unique because there are other ways to cover the 0-cells (not covered by the
essential prime implicate) with the same number of terms.
Exercise 5.8
Input: (a; b; c; d), with a; b; c; d 2 f0; 1g
Output: y 2 f0; 1g
Function:
y =
(
1 if (8a+ 4b+ 2c+ d) is prime
0 otherwise
input value abcd y
0 0000 0
1 0001 0
2 0010 1
3 0011 1
4 0100 0
5 0101 1
6 0110 0
7 0111 1
8 1000 0
9 1001 0
10 1010 0
11 1011 1
12 1100 0
13 1101 1
14 1110 0
15 1111 0
60 Solutions Manual - Introduction to Digital Design - January 26, 1999
0 0 1 1
0 1 1 0
0 1 0 0
0 0 1 0
d
c
b
a
�
�
	
� �
� �
�
�
	
�
�
�
�
�
�
	
From the Kmap we get the following prime implicants: a
0
bd; b
0
cd; a
0
b
0
c; a
0
cd, and bc
0
d
The essential prime implicants are: b
0
cd; a
0
b
0
c, and bc
0
d
A minimal sum of products for function y is:
y = b
0
cd+ a
0
b
0
c+ bc
0
d+ a
0
cd
and the gate network that implements this expression is shown in Figure 5.1.
b’
c
d
a’
b’
c
b
c’
d
a’
c
d
y
Figure 5.1: AND-OR gate network for \prime detector" (Exercise 5.8)
0 0 1 1
0 1 1 0
0 1 0 0
0 0 1 0
d
c
b
a
�
�
�
�
�
�
�
�
��
��
�
�
	
�
�
	
From the Kmap we get the following prime implicates: (b
0
+d); (a
0
+d); (b+ c); (c+d) and (a
0
+
b
0
+ c
0
). Only the (c+ d) prime implicate is not essential. So, the minimal product of sums in this
case is:
y = (b
0
+ d)(a
0
+ d)(b+ c)(a
0
+ b
0
+ c
0
)
and the gate network that implements this expression is shown in Figure 5.2. Notice that the cost
of the product of sums is lower.
Solutions Manual - Introduction to Digital Design - January 26, 1999 61
b’
d
a’
d
b
c
a’
b’
c’
y
Figure 5.2: OR-AND gate network for \prime detector" (Exercise 5.8)
Exercise 5.9
To repeat the Exercise 5.8 using the Quine-McCluskey minimization method we make use of
two tables. The �rst table is used to obtain the prime implicants and the second to select the
minimum cover.
The one set for this function is one set= f2; 3; 5; 7; 11; 13g
Minterms 3-literal Prods 2-literal Prods 1-literal Prods
0010 N 001-
0011 N -101
0101 N -011
0-11
0111 N 01-1
1011 N
1101 N
The second table consider the prime-implicants obtained in the previous table:
Prime Implicants 2 3 5 7 11 13 Essential
001- x x �
-101 x x �
-011 x x �
0-11 x x
01-1 x x
Based on the table, the function is represented by 3 essential terms and the minterm 7 must be
covered with either 0� 11 or 01� 1. The minimal SP expressions are:
y = a
0
b
0
c+ bc
0
d+ b
0
cd+ a
0
cd
or
y = a
0
b
0
c+ bc
0
d+ b
0
cd+ a
0
bd
62 Solutions Manual - Introduction to Digital Design - January 26, 1999
Exercise 5.10 A high-level description for this system is:
Input: a; b; c; d; e 2 f0; 1g
Output: f 2 f0; 1g
Function:
f =
(
1 if (a+ b+ c+ d+ e) � 3
0 otherwise
Using Quine-McCluskey minimization method we obtain the following table:
Minterms 4-literal products 3-literal products
00111 N 0-111 N - -111
01011 N -0111 N -1-11
10011 N 01-11N 1- -11
01101 N 10-11 N -11-1
10101 N 1-011 N 1-1-1
11001 N 011-1 N 11- -1
01110 N -1101 N -111-
10110 N 101-1 N 1-11-
11010 N 1-101 N 11-1-
11100 N 110-1 N 111- -
11-01 N
01111 N 0111- N
10111 N -1110 N
11011 N 1011- N
11101 N 1-110 N
11110 N 1101- N
11-10 N
11111 N 1110- N
111-0 N
-1111 N
1-111 N
11-11 N
111-1 N
1111- N
To obtain a cover for the minterms we use a second table to identify the essential prime impli-
cants, as shown below:
7 11 13 14 15 19 21 22 23 25 26 27 28 29 30 31 Essential Prime
- -111 x x x x �
-1-11 x x x x �
1- -11 x x x x �
-11-1 x x x x �
1-1-1 x x x x �
11- -1 x x x x �
-111- x x x x �
1-11- x x x x �
11-1- x x x x �
111- - x x x x �
All the terms obtained in the �rst table are essential prime implicants. The minimal expression
is:
f = abc+ abd+ abe+ acd+ ace+ ade+ bcd+ bce+ bde+ cde
Solutions Manual - Introduction to Digital Design - January 26, 1999 63
and the corresponding two-level gate network is shown in Figure 5.3 on page 63. Note that the OR
gate has 10 inputs, which might make a two-level implementation impractical.
a
b
d
a
b
c
b
c
d
a
c
d
c
d
e
b
c
e
b
d
e
a
b
e
a
d
e
a
c
e
f
Figure 5.3: Majority function - Exercise 5.10
Exercise 5.11 A high-level speci�cation for the error detector is:
Input: x is a 2-out-of-5 code represented as x = (a; b; c; d; e), where a; b; c; d; e 2 f0; 1g.
Output: f 2 f0; 1g.
Function:
f =
(
0 if the number of 1s in the input is 2
1 otherwise
The synthesis of this function using Quine-McCluskey minimization method is shown in Table
5.1. The obtained 3-literal products generate a Prime-implicant chart similar to the one shown in
Exercise 5.10, where it was concluded that all products are essential. The minimal sum of products
is:
f = a
0
b
0
c
0
d
0
+ abc+ abd+ acd+ bcd+ abe+ ace+ ade+ bce+ bde+ cde
+a
0
b
0
c
0
e
0
+ a
0
b
0
d
0
e
0
+ a
0
c
0
d
0
e
0
+ b
0
c
0
d
0
e
0
The gate network that implements the function f is shown in Figure 5.4. Note that the OR
gate has 15 inputs, which might make a two-level implementation impractical.
64 Solutions Manual - Introduction to Digital Design - January 26, 1999
Minterms 4-literal prods 3-literal prods
00000 N 0000- - -111
000-0 -1-11
00001 N 00-00 -11-1
00010 N 0-000 -111-
00100 N -0000 1- -11
01000 N 1-1-1
10000 N 0-111 N 1-11-
-0111 N 11- -1
00111 N 01-11 N 11-1-
01011 N -1011 N 111- -
01101 N 011-1 N
01110 N -1101 N
10011 N 0111- N
10101 N -1110 N
10110 N 1-011 N
11001 N 10-11 N
11010 N 1-101 N
11100 N 101-1 N
1-110 N
01111 N 1011- N
10111 N 11-01 N
11011 N 110-1 N
11101 N 11-10 N
11110 N 1101- N
111-0 N
11111 N 1110- N
1111- N
111-1 N
11-11 N
1-111 N
-1111 N
Table 5.1: Quine-McCluskey table for Exercise 5.11
Solutions Manual - Introduction to Digital Design - January 26, 1999 65
a
b
c
a
b
d
a
c
d
b
c
d
a
b
e
a
c
e
a
d
e
b
c
e
b
d
e
c
d
e a’
b’
c’
e’a’
b’
d’
e’ a’
c’
d’
e’b’
c’
d’
e’
f
a’
b’
c’
d’
Figure 5.4: Network for Exercise 5.11
Exercise 5.12 A high-level speci�cation for this exercise is:
Input: a; b 2 f0; 1; 2; 3g and c
in
2 f0; 1g.
Output: z 2 f0; 1; 2; 3; 4; 5; 6; 7g
Function: z = a+ b+ c
in
The input is represented by 2-bit vectors (a
1
; a
0
) and (b
1
; b
0
), and the output is represented
by a 3-bit vector z = (z
2
; z
1
; z
0
). Using Quine-McCluskey tabular method we obtain the following
tables, based on the switching function table presented in Exercise 2.46. The synthesis for z
0
is
shown in Table 5.2, z
1
is shown in Table 5.3, and z
2
is shown in Table 5.4.
66 Solutions Manual - Introduction to Digital Design - January 26, 1999
z
0
Minterms 4-literal prods 3-literal prods
00001 N 000-1 N 0-0-1
00100 N 0-001 N 0-1-0
10000 N 001-0 N 1-0-0
0-100 N
00011 N 100-0 N 1-1-1
00110 N 1-000 N
01001 N
01100 N 0-011 N
10010 N 0-110 N
11000 N 010-1 N
011-0 N
01011 N 1-010 N
01110 N 110-0 N
10101 N
11010 N 101-1 N
1-101 N
10111 N
11101 N 1-111 N
111-1 N
11111 N
1 3 4 6 9 11 12 14 16 18 21 23 24 26 29 31 Essential Prime
0-0-1 x x x x �
0-1-0 x x x x �
1-0-0 x x x x �
1-1-1 x x x x �
Table 5.2: Exercise 5.12 - synthesis of z
0
output
Solutions Manual - Introduction to Digital Design - January 26, 1999 67
z
1
Minterms 4-literal prods 3-literal prods
00010 N 0001-
01000 N 00-10
00011 N -0010
00101 N 0100-
00110 N 01-00
01001 N -1000
01100 N
10001 N -0101
10010 N 10-01
10100 N 1010-
11000 N
-1111
10101 N 11-11
1111-
01111 N
11011 N
11110 N
11111 N
2 3 5 6 8 9 12 15 17 18 20 21 24 27 30 31 Essential Prime
0001- x x �
00-10 x x �
-0010 x x �
0100- x x �
01-00 x x �
-1000 x x �
-0101 x x �
10-01 x x �
1010- x x �
-1111 x x �
11-11 x x �
1111- x x �
Table 5.3: Exercise 5.12 - synthesis of z
1
output
68 Solutions Manual - Introduction to Digital Design - January 26, 1999
z
2
Minterms 4-literal prods 3-literal prods 2-literal prods
01010 N 0101- N 01-1- N -1-1-
01-10 N -101- N
00111 N -1010 N -1-10 N
01011 N
01101 N 0-111 N - -111
01110 N -0111 N -1-11 N
10011 N 01-11 N -11-1
10110 N -1011 N -111- N
11001 N 011-1 N 1- -11
11010 N -1101 N 1-11-
11100 N 0111- N 11- -1
-1110 N 11-1- N
01111 N 10-11 N 111- -
10111 N 1-011 N
11011 N 1011- N
11101 N 1-110 N
11110 N 110-1 N
11-01 N
11111 N 1101- N
11-10 N
1110- N
111-0 N
-1111 N
1-111 N
11-11 N
111-1 N
1111- N
7 10 11 13 14 15 19 22 23 25 26 27 28 29 30 31 Essential Prime
-1-1- x x x x x x x x �
- -111 x x x x �
-11-1 x x x x �
1- -11 x x x x �
1-11- x x x x �
11- -1 x x x x �
111- - x x x x �
Table 5.4: Exercise 5.12 - synthesis of z
2
output
Solutions Manual - Introduction to Digital Design - January 26, 1999 69
The resulting expressions are:
z
0
= x
0
y
0
c
in
+ x
0
0
y
0
0
c
in
+ x
0
y
0
0
c
0
in
+ x
0
0
y
0
c
0
in
z
1
= x
0
1
x
0
y
0
1
c
in
+ x
0
1
y
0
1
y
0
c
in
+ x
0
1
x
0
y
0
1
y
0
+ x
1
x
0
y
1
c
in
+ x
1
y
1
y
0
c
in
+ x
1
x
0
y
1
y
0
+ x
0
1
x
0
0
y
1
c
0
in
+ x
0
1
y
1
y
0
0
c
0
in
+ x
0
1
x
0
0
y
1
y
0
0
+ x
1
y
0
1
y
0
0
c
0
in
+ x
1
x
0
0
y
0
1
c
0
in
+ x
1
x
0
0
y
0
1
y
0
0
z
2
= x
1
y
1
+ x
1
x
0
y
0
+ x
0
y
1
y
0
+ y
1
y
0
c
in
+ x
0
y
1
c
in
+ x
1
x
0
c
in
+ x
1
y
0
c
in
The AND-OR networks are shown in Figure 5.5. They assume that the complement of inputs are
also available. Because of the large number of inputs to the OR gates, a two-level implementation
might not be practical.
x0
y0
cin
x0’
y0’
cin
x0
y0’
cin’
x0’
y0
cin’
z0
x1’
x0
y1’
y0’
x1
x0’
y1’
y0’
z2
x1
y1
x1
x0
y0
x1
y0
cin
z1
total of 12 AND gates
total of 7 AND gates
Figure 5.5: Network for Exercise 5.12
70 SolutionsManual - Introduction to Digital Design - January 26, 1999
Exercise 5.13
Input: x in the range [0; 15]
Output: y in the range [0; 7]
Function: y = x mod 7
The switching functions are shown in the table
x = (x
3
x
2
x
1
x
0
) y = (y
2
y
1
y
0
)
0000 000
0001 001
0010 010
0011 011
0100 100
0101 101
0110 110
0111 000
1000 001
1001 010
1010 011
1011 100
1100 101
1101 110
1110 000
1111 001
From K-maps (not shown) we obtain the following minimal switching expressions
y
2
= (x
3
+ x
2
)(x
0
2
+ x
0
1
+ x
0
0
)(x
0
3
+ x
0
1
+ x
0
)(x
2
+ x
1
)
= x
2
x
0
1
+ x
3
x
0
2
x
1
x
0
+ x
0
3
x
2
x
0
0
y
1
= (x
3
+ x
1
)(x
1
+ x
0
)(x
3
+ x
0
2
+ x
0
0
)(x
0
3
+ x
0
2
+ x
0
1
)(x
0
3
+ x
0
1
+ x
0
0
)
= x
3
x
0
1
x
0
+ x
0
3
x
0
2
x
1
+ x
0
3
x
1
x
0
0
+ x
0
2
x
1
x
0
0
y
0
= (x
3
+ x
0
)(x
0
3
+ x
2
+ x
0
0
)(x
0
3
+ x
1
+ x
0
0
)(x
0
2
+ x
0
1
+ x
0
)(x
3
+ x
0
2
+ x
0
1
)
= x
3
x
0
1
x
0
0
+ x
3
x
0
2
x
0
0
+ x
3
x
2
x
1
x
0
+ x
0
3
x
0
1
x
0
+ x
0
3
x
0
2
x
0
Using the lowest cost version of the network that produces each output, we obtain the gate
network shown in Figure 5.6.
Exercise 5.14
The multiplier is speci�ed as follows:
Inputs: x; y where x; y 2 f0; 1; 2; 3g
Output: z 2 f0; 1; 2; 3; 4; 6; 9g
Function: z = x � y
Coding the inputs and outputs in a binary code, produces the switching function of the following
table:
Solutions Manual - Introduction to Digital Design - January 26, 1999 71
y2
y1
y0
x3
x0
x3’
x2
x0’
x3’
x1
x0’
x2’
x1’
x0
x3
x2’
x1’
x2
x1’
x3’
x2
x0’
x3
x2’
x1
x0
x3
x1’
x0
x3’
x2’
x1
x3’
x1
x0’
x2’
x1
x0’
Figure 5.6: Exercise 5.13
x y z
x
1
x
0
y
1
y
0
z
3
z
2
z
1
z
0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 0 0 0 0 0
0 1 0 1 0 0 0 1
0 1 1 0 0 0 1 0
0 1 1 1 0 0 1 1
1 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0
1 0 1 0 0 1 0 0
1 0 1 1 0 1 1 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 1
1 1 1 0 0 1 1 0
1 1 1 1 1 0 0 1
From the table we get the following K-maps and expressions for the multiplier binary outputs:
72 Solutions Manual - Introduction to Digital Design - January 26, 1999
z
2
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 1
y
0
y
1
x
0
x
1
�
�
	
�
�
	
z
1
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
y
0
y
1
x
0
x
1
�
�
	
�
�
	
�
�
	
�
�
	
z
0
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
y
0
y
1
x
0
x
1
�
�
�
�
z
0
= x
0
y
0
z
1
= x
1
x
0
0
y
0
+ x
0
y
1
y
0
0
+ x
0
1
x
0
y
1
+ x
1
y
0
1
y
0
z
2
= x
1
x
0
0
y
1
+ x
1
y
1
y
0
0
Output z
3
corresponds to only one minterm (no Kmap is needed in this case):
z
3
= x
1
x
0
y
1
y
0
The NAND-NAND network is obtained directly from the sum of products. The correspoding
network is presented in Figure 5.7.
x0
y0
x1
x0’
y0
x0
y1
y0’
x1’
x0
y1
x1
y1’
y0
x1
x0’
y1
x1
y1
y0’
x1
x0
y1
y0
z0
z1
z2
z3
Figure 5.7: Network for a 2x2 bit multiplier. Exercise 5.14
Solutions Manual - Introduction to Digital Design - January 26, 1999 73
Exercise 5.15
Input: binary code represented as b = (b
3
b
2
b
1
b
0
), where b
i
2 f0; 1g
Output: Gray code represented as g = (g
3
g
2
g
1
g
0
), where g
i
2 f0; 1g
Function: g is the Gray code that corresponds to b. The correspondence between binary and
Gray codes is shown in the following table:
Binary Gray
b
3
b
2
b
1
b
0
g
3
g
2
g
1
g
0
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000
The correspoding Kmaps are as follows:
0 0 1 1
1 1 0 0
1 1 0 0
0 0 1 1
b
0
b
1
b
2
b
3
g
1
��
��
�
�
�
�
0 1 0 1
0 1 0 1
0 1 0 1
0 1 0 1
b
0
b
1
b
2
b
3
g
0
�
�
	
�
�
	
0 0 0 0
0 0 0 0
1 1 1 1
1 1 1 1
b
0
b
1
b
2
b
3
g
3
�
�
�
�
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
b
0
b
1
b
2
b
3
g
2
�
�
	
�
�
	
74 Solutions Manual - Introduction to Digital Design - January 26, 1999
To obtain a NOR-NOR network we produce the minimal product of sums:
g
3
= b
3
g
2
= (b
2
+ b
3
)(b
0
2
+ b
0
3
)
g
1
= (b
1
+ b
2
)(b
0
1
+ b
0
2
)
g
0
= (b
0
+ b
1
)(b
0
0
+ b
0
1
)
The gate network is presented in Figure 5.8.
b0
b1
b0’
b1’
b1
b2
b1’
b2’
b2
b3
b2’
b3’
g0
g1
g2
g3b3
Figure 5.8: Exercise 5.15
Exercise 5.16
Using Quine-McCluskey minimization method to solve Exercise 5.15 we get Tables 5.5, 5.6, 5.7,
and 5.8. Minterms are obtained from the switching function presented in Exercise 5.15. From the
QM tables we obtain the expressions:
g
3
= b
3
g
2
= b
2
b
0
3
+ b
0
2
b
3
g
1
= b
1
b
0
2
+ b
0
1
b
2
g
0
= b
0
b
0
1
+ b
0
0
b
1
Solutions Manual - Introduction to Digital Design - January 26, 1999 75
g
3
Minterms 3-literal prods 2-literal prods 1-literal prods
1000 N 100- N 1-0- N 1- - -
10-0 N 10- - N
1001 N 1-00 N 1- -0 N
1010 N 1-0- N
1100 N 10-1 N
1-01 N 1- -1 N
1011 N 101- N 11- - N
1101 N 1-10 N 1-1- N
1110 N 110- N
11-0 N
1111 N
1-11 N
11-1 N
111- N
Table 5.5: Exercise 5.16 - synthesis of g
3
output
g
2
Minterms 3-literal prods 2-literal prods
0100 N 010- N 01- -
1000 N 01-0 N 10- -
100- N
0101 N 10-0 N
0110 N
1001 N 01-1 N
1010 N 011- N
10-1 N
0111 N 101- N
1011 N
Table 5.6: Exercise 5.16 - synthesis of g
2
output
g
1
Minterms 3-literal prods 2-literal prods
0010 N 001- N -01-
0100 N -010 N -10-
010- N
0011 N -100 N
0101 N
1010 N -011 N
1100 N 101- N
-101 N
1011 N 110- N
1101 N
Table 5.7: Exercise 5.16 - synthesis of g
1
output
76 Solutions Manual - Introduction to Digital Design - January 26, 1999
g
0
Minterms 3-literal prods 2-literal prods
0001 N 0-01 N - -01
0010 N -001 N - -10
0-10 N
0101 N -010 N
0110 N
1001 N -101 N
1010 N -110 N
1-01 N
1101 N 1-10 N
1110 N
Table 5.8: Exercise 5.16 - synthesis of g
0
output
Exercise 5.17
A high-level speci�cation of the system is:
Input: x is an alphanumeric character coded in ASCII
Output: z 2 f0; 1g
Function:
z =
(
1 if x 2 fA;B;C;D;Eg
0 otherwise
(5:1)
x
6
x
5
x
4
x
3
x
2
x
1
x
0z
A 1 0 0 0 0 0 1 1
B 1 0 0 0 0 1 0 1
C 1 0 0 0 0 1 1 1
D 1 0 0 0 1 0 0 1
E 1 0 0 0 1 0 1 1
otherwise 0
Since all combinations producing output 1 have x
6
x
5
x
4
x
3
= 1000, we de�ne m = x
6
x
0
5
x
0
4
x
0
3
.
The K-map for this function is:
0
m m m
m m
0 0
x
0
x
1
x
2
From the Kmap:
z = mx
2
x
0
1
+mx
0
2
x
0
+mx
0
2
x
1
A two-level NAND network is obtained from this expression. It has 3 6-input NAND gates and
one 3-input NAND gate. The description of it is:
NAND(NAND(x
6
; x
0
5
; x
0
4
; x
0
3
; x
2
; x
0
1
); NAND(x
6
; x
0
5
; x
0
4
; x
0
3
; x
0
2
; x
0
); NAND(x
6
; x
0
5
; x
0
4
; x
0
3
; x
0
2
; x
1
))
For a NOR-NOR implementation we need to obtain an expression in PS form as follows:
z = m(x
0
2
+ x
0
1
)(x
2
+ x
1
+ x
0
) = x
6
x
0
5
x
0
4
x
0
3
(x
0
2
+ x
0
1
)(x
2
+ x
1
+ x
0
)
Solutions Manual - Introduction to Digital Design - January 26, 1999 77
that corresponds to the following description:
z = NOR(x
0
6
; x
5
; x
4
; x
3
; NOR(x
0
2
; x
0
1
); NOR(x
2
; x
1
; x
0
))
The gate networks are easily obtained from these expressions and descriptions.
Exercise 5.18 A high-level speci�cation for the system is:
Input: x is a decimal digit, represented in BCD
Output: y is an unsigned integer represented in binary
Function: y = x
2
The switching functions for this exercise are given as:
x (BCD) y = x
2
(Binary)
0000 0000000
0001 0000001
0010 0000100
0011 0001001
0100 0010000
0101 0011001
0110 0100100
0111 0110001
1000 1000000
1001 1010001
Using K-maps we obtain:
y
0
= x
0
y
1
= 0
y
2
= x
1
x
0
0
y
3
= x
0
2
x
1
x
0
+ x
2
x
0
1
x
0
y
4
= x
2
x
0
1
+ x
2
x
0
y
5
= x
2
x
1
y
6
= x
3
The PLA implementation of this system is shown in �gure 5.9.
Exercise 5.19 The high-level speci�cation for this system is:
Input: b is a decimal digit, represented in BCD
Output: e is a decimal digit, represented in Excess-3 code
Function: e = b
The conversion of a BCD code, represented as b = (b
3
; b
2
; b
1
; b
0
) to an Excess-3 code, represented
by e = (e
3
; e
2
; e
1
; e
0
), is de�ned by the following K-maps:
78 Solutions Manual - Introduction to Digital Design - January 26, 1999
AND Array
OR Array
-- programmable connection
x 0x 1
y 3y 4
1
2
6
-- connection made
3
4
5
x 2x 3
y 5y 6 y 0y 1y 2
9
7
8
Figure 5.9: PLA implementation for Exercise 5.18
e
3
:
0 0 0 0
0 1 1 1
- - - -
1 1
- -
b
0
b
1
b
2
b
3
�
�
�
�
�
�
�
�
�
�
�
�
e
2
:
0 1 1 1
1 0 0 0
- - - -
0 1
- -
b
0
b
1
b
2
b
3
��
��
��
��
�
�
	
Solutions Manual - Introduction to Digital Design - January 26, 1999 79
e
1
:
1 0 1 0
1 0 1 0
- - - -
1 0
- -
b
0
b
1
b
2
b
3
�
�
�
�
e
0
:
1 0 0 1
1 0 0 1
- - - -
1 0
- -
b
0
b
1
b
2
b
3
�
�
	
�
�
	
The minimal sum of products are:
e
3
= b
1
b
2
+ b
0
b
2
+ b
3
e
2
= b
1
b
0
2
+ b
0
b
0
2
+ b
2
b
0
1
b
0
0
e
1
= b
1
b
0
+ b
0
1
b
0
0
e
0
= b
0
0
The implementation of these expressions by a PLA is shown in �gure 5.10.
AND Array
OR Array
-- programmable connection
b0b1
e 0e 1
1
2
6
-- connection made
3
4
5
b2b3
e 2e 3
9
7
8
Figure 5.10: PLA implementation of a BCD to Excess-3 converter
Exercise 5.20 A high-level speci�cation for this system is:
Input: x is a decimal digit, represented in Excess-3 code
Output: y is a decimal digit, represented in 2-out-of-5 code
80 Solutions Manual - Introduction to Digital Design - January 26, 1999
Function: y = x
The table that shows the correspondence between the excess-3 code (x) and the 2-out-of-5 code
(y) is show in page 28 of the textbook (Table 2.3).
From the table we get the following K-maps:
y
0
:
- -
1
-
0 0 0 0
1
- - -
0 0 1 1
x
0
x
1
x
2
x
4
�
�
	
��
��
y
1
:
- -
1
-
0 0 1 0
0
- - -
1 1 0 0
x
0
x
1
x
2
x
4
�
�
	
��
��
y
2
:
- -
0
-
0 1 0 1
1
- - -
0 1 0 0
x
0
x
1
x
2
x
4
�
�
	
�
�
	
�
�
	
y
3
:
- -
1
-
0 0 0 1
0
- - -
0 1 1 0
x
0
x
1
x
2
x
4
�
�
	
��
��
y
4
:
- -
0
-
1 1 1 0
0
- - -
0 0 0 1
x
0
x
1
x
2
x
4
�
�
�
�
�
�
�
�
�
�
	
Using the K-maps we obtain the following minimal expressions for output y = (y
4
; y
3
; y
2
; y
1
; y
0
):
y
0
= x
3
x
2
+ x
0
2
x
1
y
1
= x
0
2
x
0
1
+ x
0
3
x
1
x
0
y
2
= x
0
1
x
0
+ x
3
x
2
+ x
2
x
1
x
0
0
y
3
= x
0
2
x
0
+ x
2
x
1
x
0
0
y
4
= x
2
x
0
+ x
0
3
x
0
1
+ x
3
x
1
x
0
0
The implementation of these expressions using a PAL is shown in �gure 5.11.
Exercise 5.21 A high-level speci�cation for this system is:
Input: x is a decimal digit represented in BCD
Output: y = (y
(1)
y
(0)
), where y
(1)
and y
(0)
are both BCD digits.
Function: y = 3x.
From this speci�cation we de�ne y = (y
7
; y
6
; :::; y
1
; y
0
), y
i
2 f0; 1g. The table for the switching
functions is shown next:
Solutions Manual - Introduction to Digital Design - January 26, 1999 81
x = (x
3
x
2
x
1
x
0
) y
7
y
6
y
5
y
4
y
3
y
2
y
1
y
0
0000 0000 0000
0001 0000 0011
0010 0000 0110
0011 0000 1001
0100 0001 0010
0101 0001 0101
0110 0001 1000
0111 0010 0001
1000 0010 0100
1001 0010 0111
The implementation of this function using a PAL is shown in Figure 5.12. Output y
7
and y
6
were not mapped to the PAL since they are always zero. No minimization was performed in this
solution. An enable input was included to activate the circuit outputs.
82 Solutions Manual - Introduction to Digital Design - January 26, 1999
0 4 8 12 16 20 24 28
0
8
16
24
32
40
48
56
I1
I2
I3
I4
I5
I6
O1
IO2
IO3
IO4
IO5
IO6
IO7
O8
I10
I7
I8
I9
x0
x1
x2
x3
Enable
y0
y1
y2
y3
y4
Figure 5.11: PAL implementation for Exercise 5.20
Solutions Manual - Introduction to Digital Design - January 26, 1999 83
0 4 8 12 16 20 24 28
0
8
16
24
32
40
48
56
I1
I2
I3
I4
I5
I6
O1
IO2
IO3
IO4
IO5
IO6
IO7
O8
I10
I7
I8
I9
x0
x1
x2
x3
y0
y1
y2
y3
y4
y5
enable
Figure5.12: PAL implementation for Exercise 5.21