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?

$\endgroup$

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.