Booth algorithm for multiplying signed numbers

[mathmari]

Hey!

The algorithm of the Booth for multiplying signed numbersrs of fixed complement representation decimal point by 2 is implemented by multi-consecutive digit stain control of the multiplier, so after each test the algorithm proceeds by $N$ digits (e.g. for $3$-bit control step $N$ is equal to $2$)

a) Starting with the algebraic expression of the value of a given number and transforming it accordingly, find the relations from which the Booth algorithm for $N = 3$ and $N = 4$ is derived. So, once you find their form, apply the relations for the possible combinations of digits and determine for each of the two cases what operations must be done in each iteration, based on the possible values of the digits of the multiplier.

b) What kind of work do algorithms need before their first act, and what does that tell you about the practical implementation of Booth's algorithm for $N\geq 3$?

c) Test in principle Booth for $N = 1$ and $N = 2$ in the two digits of 16 bits $X=0111001010011001$ and $Y=1010011100101101$, for a constant-expansion multiplication unit with successive prostheses and slides that performs the $X \times Y$, where $X$ is multiplicand and $Y$ the multiplier, by constructing a table with the values of the units at each stage of the operation. The unit shall be based on improved material with the single registrant Product / Multiple, and with the minimum range as possible.

d) Repeat for the two new cases $N = 3$ and $N = 4$.



I am trying to understand how Booth algorithm works but I am facing some problems.

I found the below diagram :

But what relation is it asked for at question (a) ? The relation that is also shown in the diagram just for a specific $N$ ?

 

[Future Bruno]

For (b), I assume the algorithms need to know the number of bits in the given numbers and the sign of the numbers before they can start their work. For (c), I assume that for $N = 1$ and $N = 2$ we need to construct a table with 16 rows, where $X$ and $Y$ are the multiplicand and multiplier respectively and the columns will contain the values of the units at each stage of the operation. For (d), I assume that we need to use the same procedure as in (c), but with the relations derived from (a) for $N = 3$ and $N = 4$.