0
$\begingroup$

I've been experimenting with making a binary calculator lately, and I've got the addition and subtraction working. I now want to start making a multiplier, but I have no idea where to even start. I know how to multiply two binary numbers. After all, it's the same as how we used to learn how to multiply. Observe this -5 * 7 operation as an example.

 1011 x 0111 ------------ 11111011 1111011X 111011XX ------------ (10)11011101

This would result in -35 written as decimal, which is correct. The first two bits are discarded as a result of overflow, hence the brackets. This works fine, but I don't see an obvious and concise way to put this in a logic circuit. Which leads me to my first question:

How do I multiply 2 signed (2's complement) 4 bit numbers in/using a logic circuit?

If I find out a way to do that, I can try to fit it into my "calculator". But there's another problem: I have two signed 8 bit inputs but only one mere 8 bit output to work with. So I'll need some way of knowing that the output (or input(s)) is too big to fit in an 8 bit number, so my second (but less important) question is:

How do I know if the output is too big to fit in an 8 bit number? And, is this already possible using the multiplier we just made?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

As a basic block, you take an eight bit adder producing a nine bit result. You need seven of these.

Create eight 8-bit numbers Z0 to Z7. Zk is the AND of X AND bit k of Y, shifted left by k bit position, so the result is the sum of the Zk. Use the first adder to add Z0 and Z1. The lowest bit of Z0 is taken unchanged. Then you add 7 and 8 bits with a 9 bit result. Then you add Z2; you keep the lowest bit of the first sum unchanged and get 9 more bits. You continue and get the full 16 bit result. To detect overflow, you check if any of the highest 8 bits is non-zero.

It’s not a difficult circuit, it’s just BIG. And it’s almost what a modern CPU would do for a 64x64 bit multiplier. The difference is that you wouldn’t perform 63 additions in a row, but for create 64x64 bits, then use (4096 / 3) full adders which each take 3 bits of input and produce two bits of output, giving you about 2750 output bits. Then 920 full adders to reduce this to 1840 output bits and so on. This only takes logarithmic time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is very difficult to implement tho.Its better to use Booth's algorithm for multiplication instead.Use the sign|magnitude format convert a number from the signed magnitude to 2's complement,use Booth's algorithm to calculate the result in 2's complement then convert the 2's complement result to sign|magnitude format. $\endgroup$ Commented May 29 at 23:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.