Hardware Reference
In-Depth Information
5.4.8 Datapath Control for a Greatest Common Divisor Calculator
Before we examine this example, a review of section 3.13 is suggested. Particular
attention should be paid to comment number 4 at the end of that section, which is
helpful here.
This section shows another example of a datapath-based circuit. The datapath must
compute the GCD (greatest common divisor) between two integers. The corresponding
algorithm is shown in i gure 5.12; the largest value is substituted with the difference
between it and the other value until the values become equal, which is then declared
to be the GCD. A corresponding l owchart is also included in i gure 5.12. As in the
previous example, a
dv
bit, when asserted (during one clock period), must start the
computations.
The datapath to be used in this example is depicted in i gure 5.13a. The ALU's
opcode table is shown in i gure 5.13b. The ALU has also an auxiliary output (
sign
) that
indicates whether its output (
ALUout
) is zero (“00”), positive (“01”), or negative (“10”),
as listed in i gure 5.13c.
As shown, the datapath's control signals are
selA
and
selB
(select the data sources
for registers A and B),
wrA
and
wrB
(enable writing into registers A and B), and
ALUop
(produces the ALU opcode, dei ning its operations, according to the table in i gure
5.13b). The control unit (FSM) is responsible for generating all control signals.
An illustrative timing diagram for an FSM that controls this datapath such that the
desired computations occur is presented in i gure 5.13d. Dashed lines indicate “don't
care” values. Because
inpA
= 9 and
inpB
= 15 were adopted, the following computations
are expected: Iteration 1, 9
→
A, 15
→
B; Iteration 2, B
>
A, then 15
−
9 = 6
→
B; Itera-
tion 3, A
>
B, then 9
−
6 = 3
→
A; Iteration 4, B
>
A, so 6
−
3 = 3
→
B. Because A = B,
GCD = A = 3.
Observe in i gure 5.13d that the time slots are identii ed as
idle
(waiting for a
dv
bit),
load
(
inpA
and
inpB
are stored in A and B),
writeA
(
ALUout
is stored in A), and
Figure 5.12
GCD algorithm and l owchart.
