Designs based on Finite State Machines - Digital Design of Signal Processing Systems: A Practical Approach - page 384

program, sequentially implementing one iteration of the algorithm in one clock cycle. This
architecture results in HW optimization and usually requires a very simple controller. Those
algorithms that easily map to sequential architecture can also be effectively parallelized. Systolic
architecture can also be designed for optimized HW mapping [9].
Example: This example considers the design of a sequential multiplier. The multiplier multiplies
two N-bit signed numbers a and b in N cycles. In the first N 1 clock cycles the multiplier generates

the ith partial product (PP i ) for a b(i) and adds its ith shifted version to a running sum. For sign
by sign multiplication, the most significant bit (MSB) of the multiplier b has negative weight;
therefore the (N 1)th shifted value of the final PP N 1 for a b(N 1) is subtracted from the
running sum. After N clock cycles the running sum stores the final product of a b operation. The

pseudo-code of this algorithm is:

sum ¼ 0
for ði ¼ 0 ; i < N 1 ; i þþÞ
sum þ¼a b½i 2 i
sum ¼a b½N 1 2 N 1
prod ¼ sum

N)-bit sequential multiplier. The 2N-bit
shift register prod_reg is viewed as two concatenated registers: the register with N least
significant bits (LBSs) is tagged as prod_reg_L , and the register with N MSBs is tagged as
prod_reg_H , and for convenience of explanation this register is also named reg_b . Register
reg_a in the design stores the multiplicand a.AnN-bit adder/subtractor adds the intermediate
PPs and subtracts the final PP from a running sum that is stored in prod_reg_L . The ith left shift
of the PP i is successively performed by shifting the running sum in the prod_reg to the right in
every clock cycle. Before starting the execution of sequential multiplication, reg_a is loaded with

Figure 9.3 shows a hardware implementation of the (N

multiplier b

N

N

sign_bit

prod_reg_L
reg_b

prod_reg_H

rst_n

controller

1

shift_right

N

0 0

N

add/sub

N

1

reg_a

N

add /sub

N
multiplicand a

load

Figure 9.3 An N N-bit sequential multiplier