# 3 bit binary multiplier?

I have the following 2-bit binary multiplier

(source: wikimedia.org)

How can I modify this 2-bit binary multiplier to make it a 3-bit binary multiplier?

I notice that there are 2 half-adders, and there are a bunch of ANDs to begin with. It is tricky to see a pattern here, I would normally use a truth table but there would be a wopping 64 combinations. Any other strategies I could use here?

• What research have you done? Where have you looked? I encourage you to do a significant amount of research, including checking standard resources (Wikipedia, standard textbooks, reading the references cited by Wikipedia) before asking. In this case, I expect this to be covered well by computer architecture textbooks. There's little point in us repeating material that's already documented well in standard resources.
– D.W.
Mar 14, 2017 at 21:47
• – D.W.
Mar 14, 2017 at 21:49
• Can you figure out why there are those ANDs? How would you do a multiplication with pencil and paper? Mar 14, 2017 at 21:49
• You have four bits of input, so there are only 16 combinations in the truth table. My feeling, though (and this has been echoed by the community here in the past) is that this kind of low-level electronics question is off-topic, here, and should be asked at Electrical Engineering instead. Also, it's essentially a programming question, which is another reason for feeling that it's off-topic. Mar 14, 2017 at 22:16
• @AppreciateIt "Not for the 3-bit multiplier." Brainfart -- sorry. Mar 14, 2017 at 22:50

There is a pattern in the first stage: the two pairs of ands stand for the four bitwise products. Then follows a three-bits adder stage with carries ($$C_0$$ is immediate).
For an n-bit by n-bit multiplier you use $$n^2$$ ANDs which each give a single bit in some bit position. For example in a 64 bit multiplier $$x_{52} and$$y_{22} would be a bit in position 74.
You arrange this in columns for each bit position, then any three bits in the same position are added with a full adder, giving one bit in the same and one in the next higher position. You repeat this as long as you have three bits in the same position, and then you have two numbers to add. Each full adder removes one bit, so you need $$n^2$$ full adders arranged in c * log n levels.