How to create a logic circuit that multiplies two 4 bit numbers, using only 16 2-input AND gates and 3 4-bit adders?

Question

"Sketch a combinational circuit which takes as input, two 4-bit binary numbers, A3A2A1A0 and B3B2B1B0, and which outputs the 8-bit product P7P6P5P4P3P2P1P0. Assume that you have available sixteen 2-input AND gates and three 4-bit adders. Please explain the reasoning behind your design."

After a bit of fiddling I got close to the final circuit but I found that three 4-bit adders wouldn't be enough. To save time (and my complete lack of being able to explain anything) I found this, which is almost exactly what I need except it used two 4-bit adders and one 6-bit adder. I want to know if it's even possible to construct a circuit that can multiply two 4-bit numbers using the gates specified above, and if so, how can you do it?

Thanks in advance.

Answer 1

The first step is ANDing all the combinations of inputs which takes all the 16 AND gates available.

Lets call those results $S_{00}$ $S_{01}$ $S_{02}$ $S_{03}$ $S_{10}$ etc.

Is we arrange them in how we need to add them we get:

$$ \begin{matrix} & & & S_{03}&S_{02}& S_{01} & S_{00} \\ & & S_{13}&S_{12}& S_{11} & S_{10} & \\ & S_{23}&S_{22}& S_{21} & S_{20} & & \\ S_{33}&S_{32}& S_{31} & S_{30} & & \\ \end{matrix} $$

$S_{00}$ is the low bit of the output.

Then you use 1 4-bit adder to add {0,$S_{03}$, $S_{02}$, $S_{01}$} and {$S_{13}$, $S_{12}$, $S_{11}$, $S_{10}$} Output is {$A_c$, $A_3$, $A_2$, $A_1$, $A_0$}

If we substitute that result in the original table we see that this collapses the top 2 rows:

$$ \begin{matrix} & A_c & A_3 & A_2 & A_1 & A_0 & S_{00} \\ & S_{23}&S_{22}& S_{21} & S_{20} & & \\ S_{33}&S_{32}& S_{31} & S_{30} & & \\ \end{matrix} $$

$A_0$ is bit 1 of the output

Then you use the second 4-bit adder to add {$A_c$, $A_3$, $A_2$, $A_1$} and {$S_{23}$, $S_{22}$, $S_{21}$, $S_{20}$} output is {$B_c$, $B_3$, $B_2$, $B_1$, $B_0$}

$$ \begin{matrix} B_c & B_3 & B_2 & B_1 & B_0 & A_0 & S_{00} \\ S_{33}&S_{32}& S_{31} & S_{30} & & \\ \end{matrix} $$

$B_0$ is bit 2 of the output

Then you use the third 4-bit adder to add {$B_c$, $B_3$, $B_2$, $B_1$} and {$S_{33}$, $S_{32}$, $S_{31}$, $S_{30}$} output is {$C_c$, $C_3$, $C_2$, $C_1$, $C_0$}

The carry input on all the 4-bit adders is 0.

The total output is then: {$C_c$, $C_3$, $C_2$, $C_1$, $C_0$, $B_0$, $A_0$, $S_{00}$}