Hardware Reference
In-Depth Information
Figure 11.11
Sequential add-and-shift multiplier. (a) Algorithm. (b) Flowchart.
two halves, called
prodL
(product left) and
prodR
(product right). In this example the
inputs are “1100” (multiplicand = 12) and “1011” (multiplier = 11), so the expected
result is “10000100” (product = 132).
Initially, the multiplicand is stored in a (i xed) register, and the multiplier is loaded
into
prodR
, with
prodL
loaded with zeros. The algorithm checks the LSB (least signii -
cant bit) of the product; if it is '0', the product register is simply shifted to the right
one position (empty position i lled with the carry bit); if, however, it is '1',
mult
is
added (with carry) to
prodL
before the shift operation is executed. After
N
iterations
the product will be available in the product register.
The algorithm is described in ASM form in i gure 11.11b. A data-valid bit (
dv
= '1'
during one clock period) is used to tell the circuit when the computation should start.
The algorithm runs
N
times (for
i
= 0 to
N
− 1), so when
i
=
N
occurs the algorithm
returns to the beginning, ready to start a new computation when
dv
is asserted again.
Note that a nop (no operation) stage was included in the left branch to consume one
clock cycle, so the computations will always take a i xed amount of time (depending
on the application, the nop stage can be suppressed). Observe in the l owchart the
recursive equation
i
=
i
+ 1, which characterizes a category 3 FSM.
Figure 11.12a shows the parts of a datapath used to implement this multiplier,
consisting of an ALU, two registers (REG1, REG2), and a multiplexer (MUX). It is
assumed that it is a 16-bit system. The control unit (FSM) must generate the signals
wrR1
and
wrR2
(to enable writing into REG1 and REG2, respectively),
sel
(for mux
input selection),
ALUop
(to control the ALU operation), and
shift
(to shift REG2 to the
