Building a 5-bit Multiplier

I'm currently learning digital logic and have been tasked with building a 5-bit multiplier using only simple gates. I saw it recommended here to use a truth table to help you build the circuit. Unfortunately, for 5x5 multiplication a truth table isn't very realistic as far as I know. Is there another way I could derive a formula that could then be converted to a circuit? Thank you for any help!

• Are you familiar with the long multiplication method? Implement it. It will turn your multiplication into a series of additions. – Eugene Sh. Sep 15 '16 at 20:26
• What have you found in your research? – Voltage Spike Sep 15 '16 at 20:33
• Can you make one adder ? Can you combine several adders ? (And take care, there is a difference between signed and unsigned multipliers) – TEMLIB Sep 15 '16 at 21:26

To build on Eugene's comment, look at the following schematic:

simulate this circuit – Schematic created using CircuitLab

Note that each bit of the 5-bit value of $B$ is used to either gate, or not gate, the 5-bit value of $A$ to its associated partial product term. (Numbered as $PP_0$ to $PP_4$.) $PP_0$ is unshifted. $PP_1$ is shifted left by 1 bit, so you might think of it as a 6-bit binary value. But I show it as just 5 bits since there's no reason wasting a "0" when all you are doing is a lane-shift.

However, I decided to show that the lowest order bit of $PP_0$ is actually the lowest order bit of the result. You can see that in the schematic. At this point, you need to use a half-adder to add the next lowest order bit of $PP_0$ (now the lowest bit of the shown 4-bit bus) to the lowest order bit of $PP_1$. This will result in $R_1$ as the next lowest order result bit. The carry will then ripple over to the next full-adder needed, as you add the remaining 3 bits of $PP_0$ to the associated ones of the lane-shifted $PP_1$.

Since half adders and full adders are made from simple gates, too, you should be able to generate the entire thing in very simple gates. A lot of them. But the process isn't at all complex. It's just repetitive.

EDIT: For an unsigned $N\times N$ multiplier, where $N\ge 1$, you will need $N\times N$ AND gates to create the $N$ partial products for the first stage. This is fast and has a fixed delay. Then you will need $N-1$ adder tiers, arranged something like the following 4-bit example (I used 4 bits because 5 bits would have taken too much room on the page.)

simulate this circuit

Hopefully, that gets the idea across and you can manage to extend it to 5 bits.

• To make sure I'm understanding this correctly, After I've used all the bits from PP0, I should take the remaining bit from PP1 and add it to the lowest from PP2? – Raviga Sep 16 '16 at 0:05
• @Raviga The first bit of PP0 is the first bit of your result. The next 4 bits of PP0 are added to PP1. Let me update the answer a bit. – jonk Sep 16 '16 at 0:06