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

Prévia do material em texto

249
Chapter 12
Exercise 12.1:
The controller has 6 states, and we are going to use the one-
ip-
op per state appoach for the
design. The inputs are:
Input condition
GO
A DIST > 10
B (DIST � 10) and (COUNT = 3)
C (DIST � 10) and (COUNT 6= 3)
Calling the inputs of the 
ip 
ops for each state as NS
i
, we generate the following expressions:
NS
0
= S
0
:GO
0
NS
1
= S
0
:GO + S
3
NS
2
= S
1
:C
NS
3
= S
2
+ S
4
NS
4
= S
1
:A
NS
5
= S
1
:B + S
5
These expressions are implemented in a PSA as shown in Figure 12.1.
Exercise 12.2:
A modulo-11 counter is expressed by the following state transition and output function table:
PS Input
y
3
y
2
y
1
y
0
x = 0 x = 1
0000 0000,0 0001,0
0001 0001,0 0010,0
0010 0010,0 0011,0
0011 0011,0 0100,0
0100 0100,0 0101,0
0101 0101,0 0110,0
0110 0110,0 0111,0
0111 0111,0 1000,0
1000 1000,0 1001,0
1001 1001,0 1010,0
1010 1010,0 0000,1
NS(Y
3
Y
2
Y
1
Y
0
), output
From this table, using Kmaps we obtain the following minimal expressions for the next state
bits and the output (terminal count - TC):
Y
3
= y
3
x
0
+ (y
3
y
0
1
+ y
2
y
1
y
0
)x = y
3
x
0
+ y
3
y
0
1
x+ y
2
y
1
y
0
x
Y
2
= y
2
x
0
+ (y
2
y
0
1
+ y
2
y
0
0
+ y
0
2
y
1
y
0
)x = y
2
x
0
+ y
2
y
0
1
x+ y
2
y
0
0
x+ y
0
2
y
1
y
0
x
Y
1
= y
1
x
0
+ (y
0
1
y
0
+ y
0
3
y
1
y
0
)x = y
1
x
0
+ y
0
1
y
0
x+ y
0
3
y
1
y
0
x
Y
0
= y
0
x
0
+ (y
0
1
y
0
0
+ y
0
3
y
0
0
)x = y
0
x
0
+ y
0
1
y
0
0
x+ y
0
3
y
0
0
x
TC = y
3
y
1
x
250 Solutions Manual - Introduction to Digital Design - August 2, 1999
AND Array
OR Array
-- programmable connection
1
2
6
-- connection made
3
4
5
9
7
8
State RegisterCK
S0 S1 S2 S3 S4 S5
NS0 NS1 NS2 NS3 NS4 NS5
S0 S1 S2 S3 S4 S5 GO A B C
Figure 12.1: PSA implementation of a controller - Exercise 12.1
The implementation of these equations using a PSA is shown in Figure 12.2.
Exercise 12.3:
The number of address lines should be 4, since a BCD digit is the single input. The maximum
value to be stored in the ROM is 9
2
= 81, which requires dlog
2
81e = 7 bits to be represented in
binary. Thus, at least a 16 � 7 ROM is required to implement the function.
Exercise 12.4:
The system that converts from BCD to Excess-3 is shown in Figure 12.3. It implements the
following table:
Solutions Manual - Introduction to Digital Design - August 2, 1999 251
OR Array
1
2
6
3
4
5
7
8
y2 y1 y0 xy3
AND Array
-- programmable connection
-- connection made
State RegisterCK
y3 y2 y1 y0
Y3 Y2 Y1 Y0 TC
9
10
11
12
13
14
Figure 12.2: Modulo-11 counter - Exercise 12.2
BCD Excess 3
b
3
b
2
b
1
b
0
q
3
q
2
q
1
q
0
0000 0011
0001 0100
0010 0101
0011 0110
0100 0111
0101 1000
0110 1001
0111 1010
1000 1011
1001 1100
Exercise 12.5:
For this implementation we need a 2
12
� 6 ROM. Twelve address lines receive the input bits
from a, b, and c 2 f0; 1; :::; 15g. Six bits are required to represent 0 � s � 45. The block diagram
of the component is shown in Figure 12.4.
252 Solutions Manual - Introduction to Digital Design - August 2, 1999
decoder
0
1
2
3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ROM
q1q3
q2 q0
b0
b1
b2
b3
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
- - - -
- - - -
- - - -
- - - -
- - - -
- - - -
Figure 12.3: BCD to Excess-3 converter - Exercise 12.4
Exercise 12.6:
The high-level speci�cation of the single-digit decimal adder is:
Input: A,B 2 f0; 1; 2; :::; 9g and c
in
2 f0; 1g
Output: S 2 f0; 1; 2; :::; 9g and c
out
2 f0; 1g
Function:
S =
(
A+B + c
in
if A+B + c
in
< 10
A+B + c
in
� 10 if A+B + c
in
� 10
c
out
=
(
0 if A+B + c
in
< 10
1 if A+B + c
in
� 10
Calling a, b and s the integers obtained from the Excess-3 representation we get:
a = A+ 3
b = B + 3
s = S + 3
Substituting these expressions on the equations above, we obtain:
s =
(
a+ b+ c
in
� 3 if a+ b+ c
in
� 6 < 10
a+ b+ c
in
� 13 if a+ b+ c
in
� 6 � 10
c
out
=
(
0 if a+ b+ c
in
� 6 < 10
1 if a+ b+ c
in
� 6 � 10
Solutions Manual - Introduction to Digital Design - August 2, 1999 253
de
co
de
r
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4095
ROM
0 0 0 0 0 0
0 0 0 0 0 1
1 0 1 1 0 1
s1s3
s2 s0
a3
a2
a1
a0
b3
b2
b1
b0
c3
c2
c1
c0
0 0 0 0 1 0
0 0 0 0 1 1
s5
s4
Figure 12.4: ROM implementation - 3-input 4-bit adder - Exercise 12.5
The ROM implementation of a single digit Excess-3 adder requires 9 addressing lines (512
words). Four bits are used by each Excess-3 digit a or b (represented by a and b), and one bit is
used for carry input (c
in
). Each word needs to have 5 bits: four bits for the output digit in Excess-3
(s) and one bit for carry output (c
out
). We de�ne the address vector as x = (a; b; c
in
), which is the
binary representation of x = 32a + 2b + c
in
and the contents of each word as w = (c
out
; s), which
corresponds to w = 16c
out
+ s. The value in each word position x of the ROM is given as:
w =
(
a+ b+ c
in
� 3 if a+ b+ c
in
< 16
a+ b+ c
in
+ 3 if a+ b+ c
in
� 16
A block diagram for the ROM showing some words' contents is presented in Figure 12.5. Address
102, for example, corresponds to the addition of A = 0 and B = 0 in Excess-3 (a = b = 3), and
c
in
= 0.
Exercise 12.7:
Part (a) - using one decoder and ROM modules of eight 4-bit words. Figure 12.6
COST = 4� (ROM) +DEC = 4� (ROM) + 4� (AND-2) + 2� (NOT)
#interconnections = 13
delay = �(ROM) + �(AND-2) + �(NOT)
where � represents the component delay.
Part (b) - using ROM modules and a multiplexer. Figure 12.7.
COST = 4� (ROM) +MUX = 4� (ROM) + 16� (AND-3) + 4� (OR-4) + 2� (NOT)
#interconnections = 29
254 Solutions Manual - Introduction to Digital Design - August 2, 1999
de
co
de
r
0
1
2
3
4
5
6
7
8
0
1
2
3
102
103
104
105
106
107
408
409
511
ROM
- - - - -
- - - - -
- - - - -
- - - - -
1 1 1 1 1
c
out
s1s3
s2 s0
c in
a0
a1
a2
a3
b0
b1
b2
b3
0 0 0 1 1
0 0 1 0 0
0 0 1 0 0
0 0 1 0 1
0 0 1 0 1
0 0 1 1 0
1 1 0 1 1
1 1 1 0 0
Figure 12.5: ROM implementation of an Excess-3 digit adder - Exercise 12.6
delay = �(ROM) + �(MUX) = �(ROM) + �(AND-3) + �(OR-4)
Thus, the �rst design is better than the second one in all aspects.
Exercise 12.8:
Since the number of products used by each output is not known, we need to assume the worst
case situation, when most of them are used by a single output, and 1 (or none) is used by the other
outputs. The PLA provides only 128 product terms, thus, we need to use two PLAs to obtain 256
product terms, combining their outputs with OR gates. The number of inputs is also larger than
the number of inputs in each PLA device, thus, a binary decoder is used to select among 4di�erent
PLA banks, each bank consisting of a pair of PLAs with ORed outputs. The design is shown in
Figure 12.8.
Exercise 12.9:
For the ROM implementation of the function we need 2
6
words of 2 bits. Thus, a complete
switching function table should be implemented, with 64 entries.
For the PLA implementation, it is important to notice that z
1
= 1 when a = b, and z
0
= 1
when a = (b� 1) mod 8. The minterms used to generate z
1
are shown in the following table:
Solutions Manual - Introduction to Digital Design - August 2, 1999 255
a b
f0 f1 f2 f3
0001
0010
0000
0100
0001
0010
1000
0000
E
decoder
0 1 2 3
1 0
0110
1000
0000
0100
1000
1000
0001
0000
E
c
d
e
c
d
e
1000
0010
0000
0001
0010
0010
1000
0100
E
c
d
e
0001
0010
1000
0000
0000
0100
1010
0000
E
c
d
e
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
2
1
0
2
1
0
2
1
0
2
1
0
ROM ROM ROM ROM
Figure 12.6: Implementation of switching function using one decoder and ROM- Ex. 12.7
a
2
a
1
a
0
b
2
b
1
b
0
product terms to generate z
1
000 000 a
0
2
a
0
1
a
0
0
b
0
2
b
0
1
b
0
0
001 001 a
0
2
a
0
1
a
0
b
0
2
b
0
1
b
0
010 010 a
0
2
a
1
a
0
0
b
0
2
b
1
b
0
0
011 011 a
0
2
a
1
a
0
b
0
2
b
1
b
0
100 100 a
2
a
0
1
a
0
0
b
2
b
0
1
b
0
0
101 101 a
2
a
0
1
a
0
b
2
b
0
1
b
0
110 110 a
2
a
1
a
0
0
b
2
b
1
b
0
0
111 111 a
2
a
1
a
0
b
2
b
1
b
0
For PLAs what matters is the number of product terms. It is not possible to reduce the number
of product terms shown in the table since both a and b change one bit from one row to another.
Thus, two literals are di�erent from one minterm to another, making impossible the combination
of two minterms. The number of product terms is already minimal.
Similarly, for z
0
(the case a = (b� 1) mod 8):
a
2
a
1
a
0
b
2
b
1
b
0
product terms to generate z
0
000 111 a
0
2
a
0
1
a
0
0
b
2
b
1
b
0
001 000 a
0
2
a
0
1
a
0
b
0
2
b
0
1
b
0
0
010 001 a
0
2
a
1
a
0
0
b
0
2
b
0
1
b
0
011 010 a
0
2
a
1
a
0
b
0
2
b
1
b
0
0
100 011 a
2
a
0
1
a
0
0
b
0
2
b
1
b
0
101 100 a
2
a
0
1
a
0
b
2
b
0
1
b
0
0
110 101 a
2
a
1
a
0
0
b
2
b
0
1
b
0
111 110 a
2
a
1
a
0
b
2
b
1
b
0
0
where again the number of product terms is minimal.
256 Solutions Manual - Introduction to Digital Design - August 2, 1999
1
0
a
b
0123 0123 0123 0123
4x4-input MUX
f0 f1 f2 f3
0110
1000
0000
0100
1000
1000
0001
0000
E
1
c
d
e
2
1
0
0
1
2
3
4
5
6
7
0001
0010
0000
0100
0001
0010
1000
0000
E
1
c
d
e
2
1
0
0
1
2
3
4
5
6
7
1000
0010
0000
0001
0010
0010
1000
0100
E
1
c
d
e
2
1
0
0
1
2
3
4
5
6
7
c
d
e
2
1
0
0
1
2
3
4
5
6
7
0001
0010
1000
0000
0000
0100
1010
0000
E
1
ROM ROM ROM ROM
Figure 12.7: Implementation of switching function using ROM and MUX - Ex. 12.7
Thus, the PLA would need to have 16 products, 6 inputs, and 2 outputs.
Exercise 12.10:
The design of the BCD counter can be done with the ROM module, 4-bit register and AND
gate, as shown in Figure 12.9. No need for the adder. The ROM module receives the Present State
of the counter (stored in the 4-bit register) as address bits. Each word contains the value of the
next state. Using the LOAD input of the register the circuit will load the next state only when
CNT = 1. The state is kept the same when CNT = 0. The terminal count output is generated by
the AND gate, as TC = Q
3
Q
0
.
PLA PLA
PLA bank
En Input En Input
outputs outputs PLA Bank
0
PLA Bank
1
PLA Bank
2
PLA Bank
3
binary
dec
0
1
0
1
2
3
x12
x13
E
1
(x11,x10,...,x1,x0)
z0 z1 z2 z3
Figure 12.8: Design using PLAs - Exercise 12.8
Solutions Manual - Introduction to Digital Design - August 2, 1999 257
ROM
de
co
de
r0
1
2
3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
00010
00100
00110
01000
01010
01100
01110
10000
10010
00001
-----
-----
-----
-----
-----
-----
LD
Register
CNT
CK
TC
Q3 Q2 Q1 Q0
Figure 12.9: BCD counter - Exercise 12.10
Exercise 12.11:
Size of state register and ROM for:
(a) Moore sequential system with 512 states, 3 inputs and 2 outputs. For 512 states, a minimum
of 9 bits are required to represent each state. The ROM needs to have as many address lines
as the number of state bits plus the number of inputs, which corresponds to a total of 12 bits.
Since this is a Moore machine the total number of ROM bits is reduced by using separate
ROMs to generate the next state and to generate the outputs. The ROM for the next state
will have 2
12
� 9 bits. The ROM to generate the output will be a 2
9
� 2 bits ROM. Thus, the
implementation will require a 2
12
� 9 ROM, a 2
9
� 9 ROM, a and a 9-bit register. Of course,
the implementation can use only one ROM, resulting the same as for the Mealy case.
(b) For a Mealy model, the system will have only a single 2
12
� 11 ROM, and a 9-bit register.
This time the output values are stored with the next state bits.
(c) When the state transition depends only on one input, a multiplexer (in this case a network of
multiplexer would be required, since the number of inputs is quite large). The multiplier is
used to select the correct input among the possible system inputs, depending on the present
state of the system. The output of the multiplexer is used as an address line for the ROM
258 Solutions Manual - Introduction to Digital Design - August 2, 1999
which will have a size of 2
10
� 9 bits, and generates the next state bits. Since this is a Moore
machine, another ROM is used to generate the outputs. Same way as done in part (a), a
2
9
� 2 ROM is required for the outputs. A 9-bit register is used to store the state values. A
block diagram of the system is shown in Figure 12.10.
MUX
Present
State
system 
inputs
active
in each
state
ROM
ROM
a
dd
re
ss
a
dd
re
ssCLK
outputs
Figure 12.10: Block diagram for Exercise 12.11(c)
(d) For a Mealy system, with the same conditions of the one considered in part (c), a 2
10
� 11
ROM, a network of muxes to select the input (same as in part (c)), and a 9-bit register are
used. The ROM stores both the next state bits and the output values.
(e) Since the system in part (c) is implemented as a Moore machine, the output doesn't depend
on the input values, and for this reason, this question doesn't make sense. If we apply this
idea to the system in part (d), then the output should be generated by a separate ROM with
11 addressing lines and 2-bit words. The generation of the next state would be done by a
2
10
� 9 ROM. The network of muxes to select the inputs would be used, and a 9-bit register
would store the state bits.
Exercise 12.12:
From Figure 12.18 of the text we obtain the following statetransition and output table:
PS Input z
y
2
y
1
y
0
x = 0 x = 1
000 000 100 1
001 010 110 0
010 000 100 0
011 011 111 0
100 001 101 1
101 000 100 0
110 011 111 0
111 001 101 1
NS
Using the name S
i
for state i we obtain the following high level description of the sequential
system:
Solutions Manual - Introduction to Digital Design - August 2, 1999 259
Input: x 2 f0; 1g
Output: z 2 f0; 1g
States: S
i
, with 0 � i � 7
State transition and output function table:
PS Input z
y
2
y
1
y
0
x = 0 x = 1
S
0
S
1
S
4
1
S
1
S
2
S
6
0
S
2
S
0
S
4
0
S
3
S
3
S
7
0
S
4
S
1
S
5
1
S
5
S
0
S
4
0
S
6
S
3
S
7
0
S
7
S
1
S
5
1
NS
The state diagram for the system is shown in Figure 12.11.
S0/1 S1/0 S2/0 S3/0
S4/1S5/0S6/0S7/1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Figure 12.11: State diagram for system in Exercise 12.12.
Exercise 12.13:
Observe that each state has transitions to another state based on only one input among 3
possible inputs 2 fa; b; cg. A multiplexer can be used to select the desired input, and the diagram
can be modi�ed to have only one input, let's call it x. The new transition table would be:
PS Inputs
x = 0 x = 1
S0 S3/10 S1/01
S1 S1/00 S2/01
S2 S3/00 S4/01
S3 S1/00 S0/00
S4 S4/00 S3/11
NS,z
1
z
0
260 Solutions Manual - Introduction to Digital Design - August 2, 1999
Assume that the state S
i
is represented by the vector i = (y
2
; y
1
; y
0
). The network that imple-
ments the state diagram is given in Figure 12.12.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ROM
MUX
0
1
2
3
4
5
6
7 2 1 0
01110
00100
01100
00100
10000
xxxxx
xxxxx
xxxxx
00101
01001
10001
00000
01111
xxxxx
xxxxx
xxxxx
x
Reg
CK
a
c
a
b
b
y2 y1 y0
y2
y1
y0
Y2Y1Y0
(next State)
(present state)
z0
z1
Y2
Y1
Y0
y2
y1
y0
Next
state
Present 
State
3
2
1
0
E
1
E
1
Figure 12.12: Network for Exercise 12.13
Solutions Manual - Introduction to Digital Design - August 2, 1999 261
Exercise 12.14:
Part (a): Based on the information that the ROM word contains:
� the next state bits (3 bits are required for a sequence of 8 clock cycles),
� the output bits for T
1
, T
2
, and T
3
, and
� one bit L that controls the load of the register that stores the sequence number s.
we conclude that each ROM word requires 7 bits. Since 16 di�erent sequences are generated by
the system, 16� 8 = 128 words are required. Thus, a 128� 7 ROM is used.
Part (b): The system diagram is shown in Figure 12.13. COMMENT: the s value is loaded at
the last clock cycle of the sequence, not the one before the last.
T1
T2
T3
s
CK
ce
D Q4s most significant
address bits
Q2Q1Q0
8 words
ROM
s=0
s=1
s=2
s=3
s=4
s=5
s=15
L
CK
3 3Q2Q1Q0
T1T2T3
L
Q2Q1Q0 T1T2T3 L
 0 0 1 0 1 1 0
 0 1 0 1 1 0 0
 0 1 1 1 1 1 0
 1 0 0 1 0 0 0
 1 0 1 1 0 1 0
 1 1 0 0 0 0 0
 1 1 1 0 0 1 0
 0 0 0 0 0 0 1
System
3
4
Figure 12.13: System implementation for Exercise 12.14
Part (c): The contents of the ROM for the case s = 5 is the following:
Address Next State T
1
T
2
T
3
L
101000 001 011 0
101001 010 110 0
101010 011 111 0
101011 100 100 0
101100 101 101 0
101101 110 000 0
101110 111 001 0
101111 000 000 1
262 Solutions Manual - Introduction to Digital Design - August 2, 1999
Exercise 12.15:
For this design we use a ROM that receives as input lines the values of the present state,
and 2 input bits. In fact, there are 3 conditions that are used as inputs, but making use the the
multiplexer we are able to select among two inputs: GO and DIST > 10. The third input is
inserted directly as an address signal to the ROM. The ROM contains the information on the next
state and the outputs (CLEAR,CHECK,TURNLEFT90,COUNTUP ,MOVE,STOP ). Thus 9
bits are required per ROM word. The design is shown in Figure 12.14.
0 000100000
1 000100000
2 001100000
3 001100000
4 010010000
5 101010000
6 100010000
7 100010000
8 011001000
9 011001000
10 --------
11 --------
12 001000100
13 001000100
14 --------
15 --------
16 011000010
17 011000010
18 --------
19 --------
20 101000001
21 101000001
22 --------
23 --------
24 --------
25 --------
26 --------
27 --------
28 --------
29 --------
30 --------
31 --------
0
1
2
3
4
de
co
de
r
ROM
Reg.
CK
COUNT=3
MUX
0
1
2
3
4
5
6
7
2 1 0
GO
DIST>10
0
0
0
0
0
0
STOP
MOVE
COUNTUP
TURNLEFT90
CHECK
CLEAR
Figure 12.14: Circuit for Exercise 12.15
Exercise 12.16:
The ROM used to design this counter should have 2
8
words of 8 bits each. We consider the design
of an autonomous counter. The block diagram for the circuit is shown in Figure 12.15. The contents
of the ROM would be too lengthy to describe using a table with all entries. It is easier to consider
the following tabular description that uses ranges of values. ROM addresses or word contents
are represented by a pair (x; y), with x; y 2 f0; 1; 2; :::15g. As an example, the range speci�ed as
(1; 10)� (1; 15) represents the ordered sequence of values: (1; 10); (1; 11); (1; 12); (1; 13); (1; 14); and
(1; 15).
Solutions Manual - Introduction to Digital Design - August 2, 1999 263
ROM
ad
dr
es
s
TC
CLK
Figure 12.15: ROM implementation of Decimal Counter - Exercise 12.16
Address Contents
(0,0)-(0,9) (0,1)-(0,9),(1,0)
(0,10)-(0,15) d.c.
(1,0)-(1,9) (1,1)-(1,9),(2,0)
(1,10)-(1,15) d.c.
(2,0)-(2,9) (2,1)-(2,9),(3,0)
(2,10)-(2,15) d.c.
(3,0)-(3,9) (3,1)-(3,9),(4,0)
(3,10)-(3,15) d.c.
(4,0)-(4,9) (4,1)-(4,9),(5,0)
(4,10)-(4,15) d.c.
(5,0)-(5,9) (5,1)-(5,9),(6,0)
(5,10)-(5,15) d.c.
(6,0)-(6,9) (6,1)-(6,9),(7,0)
(6,10)-(6,15) d.c.
(7,0)-(7,9) (7,1)-(7,9),(8,0)
(7,10)-(7,15) d.c.
(8,0)-(8,9) (8,1)-(8,9),(9,0)
(8,10)-(8,15) d.c.
(9,0)-(9,9) (9,1)-(9,9),(0,0)
(9,10)-(15,15) d.c.
The ROM address receives the present state bits and the contents of a ROM word provides the
next state value. A content of D.C. means that ANY value can be used. A Terminal Count signal
is generated when the next state is (0; 0).
Exercise 12.17:
The ROM implementation of the system is shown in Figure 12.16. The complete contents of
the ROM that generates (z
22
; z
21
; z
20
) (using decimal notation) is given in the next table:
264 Solutions Manual - Introduction to Digital Design - August 2, 1999
0
1
2
3
4
5
x
x
x
y
y
y
20
21
22
20
21
22
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
40
63
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
- - -
- - -
- - -
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
- - -
- - -
- - -
- - -
- - -
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
x
x
y
y
10
11
10
11
z z z22 21 20
0 0
0 0
0 0
- -
0 0
0 1
1 0
- -
0 0
1 0
0 1
- -
- -
- -
- -
- -
z z11 10
0
1
0
1
2
3
0
0
0
1
x
y
00
z
00
00
Figure 12.16: ROM implementation of Exercise 12.17
y
2
x
2
z
2
y
2
x
2
z
2
y
2
x
2
z
2
y
2
x
2
z
2
0 0 0 2 0 0 4 0 0 6 0 dc
0 1 0 2 1 2 4 1 4 6 1 dc0 2 0 2 2 4 4 2 3 6 2 dc
0 3 0 2 3 1 4 3 2 6 3 dc
0 4 0 2 4 3 4 4 1 6 4 dc
0 5 dc 2 5 dc 4 5 dc 6 5 dc
0 6 dc 2 6 dc 4 6 dc 6 6 dc
0 7 dc 2 7 dc 4 7 dc 6 7 dc
1 0 0 3 0 0 5 0 dc 7 0 dc
1 1 1 3 1 3 5 1 dc 7 1 dc
1 2 2 3 2 1 5 2 dc 7 2 dc
1 3 3 3 3 4 5 3 dc 7 3 dc
1 4 4 3 4 2 5 4 dc 7 4 dc
1 5 dc 3 5 dc 5 5 dc 7 5 dc
1 6 dc 3 6 dc 5 6 dc 7 6 dc
1 7 dc 3 7 dc 5 7 dc 7 7 dc
The PLA implementation of the system needs the representation of the output functions as a
sum of product terms. The switching expressions in sum-of-products form for the various outputs
are:
z
22
(y
22
; y
21
; y
20
; x
22
; x
21
; x
20
) = m
2
(12; 18; 27; 33)
z
21
(y
22
; y
21
; y
20
; x
22
; x
21
; x
20
) = m
2
(10; 11; 17; 20; 25; 28; 34; 35)
z
20
(y
22
; y
21
; y
20
; x
22
; x
21
; x
20
) = m
2
(9; 11; 19; 20; 25; 26; 34; 36)
Solutions Manual - Introduction to Digital Design - August 2, 1999 265
z
11
(y
11
; y
10
; x
11
; x
10
) = m
1
(6; 9)
z
10
(y
11
; y
10
; x
11
; x
10
) = m
1
(5; 10)
z
00
(y
00
; x
00
) = x
00
y
00
= m
0
(3)
Since the outputs z
2i
depend on the same set of inputs, they should be mapped to the same
PLA. If more inputs and products are available in the component, functions z
1i
and z
00
could also
be implemented in the same PLA. A total of 21 products were listed in the expressions above,
however, it is possible to reduce this number of products to 20. Using ESPRESSO we were able to
reduce the number of products to generate z
2
from 16 to 15 (the others cannot be reduced). One
possible solution is to combine m
2
(9) and m
2
(25) on the generation of z
20
and obtain the single
product term y
0
22
y
20
x
0
22
x
0
21
x
20
. ESPRESSO also reduces the number of literals in each product
term, however, this feature is not important for PLA implementation.
Exercise 12.18:
Number of Con�gurable Logic Blocks for
� an 8-to-1 multiplexer. Since a CLB can implement a 2-input multiplexer, and the 8-to-1
multiplexer can be designed with a tree of 7 2-input multiplexers, the total number of CLBs
required for this case is 7.
� a 4-bit right/left shift register with parallel load. For this implementation, a 4-input multi-
plexer is required for each register bit. A 4-input multiplexer uses 3 CLBs (tree organization),
thus a total of 12 CLBs are needed. The 
ip-
ops to store the register state are available in
the CLBs used to implement the multiplexers.
� a modulo-9 counter with parallel load and TC. A canonical design of an autonomous modulo-
9 counter (no control input, only the sequence of states changing with the clock input) would
generate the following expressions for the next state bits:
Y
3
= Q
2
Q
1
Q
0
Y
2
= Q
2
Q
0
1
+Q
0
2
Q
1
Q
0
+Q
2
Q
0
0
Y
1
= Q
1
Q
0
0
+Q
0
1
Q
0
Y
0
= Q
0
3
Q
0
0
A pair of these functions can be implemented by a CLB (two 3-input functions). When we
add the inputs CNT, LD, and parallel input, to the variable Y
i
(in order to generate the actual
value that is loaded as each state bit), we get a function of 4 inputs, that requires 1 CLB for
each state bit. Thus the total number of CLBs is 6. The required 
ip 
ops are available on
the CLBs used for combinational logic.
� an 8-bit two's complement adder. A Carry Ripple adder will require 8 Full Adders. Each
CLB can implement 1 FA, thus, the total number of CLBs in this implementation is 8.
� a 4 � 2 multiplier (positive integers). To generate the partial products 4 CLBs are used (2
product bits per CLB). These bits are summed in a 5-bit adder, which, based on the result
given in the previous item, will require 5 CLBs. Thus, the total number of CLBs required to
implement the multiplier is 9. The reader may also try to reduce this number by creating a
optmized mapping of the the product generation and addition funtions for the least signi�cant
bits.