-1
\$\begingroup\$

In one of the interviews that I attended, I was asked the following question:

Design a circuit that we can use to add two 128-bit numbers, you have only one 4-bit adder and no other adder IC. You are not allowed to use any microprocessor/microcontroller.

I gave an answer that we can do it by adding 4 bits at a time, storing it and going to the next 4 bits, and they asked how exactly will you go to the next 4 bits?

Can someone help me in finding a solution to this? (During the interview drawing the block diagram was enough, a detailed description of the block was not needed)

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The 74181 (4-bit ALU slice) is what I used to develop an 8-bit ALU. It's pretty simple to extend from 4-bit to 8-bit. What mental difficulties did you encounter? I'm curious and perhaps a little confused about what difficulties you feel you face. \$\endgroup\$
    – jonk
    Jun 1 at 5:08
  • \$\begingroup\$ I am sorry, I have made a small change in the question. I was asked to use only one 4 bit adder IC, I was confused how can I add two such large numbers using only one 4 bit adder. \$\endgroup\$ Jun 1 at 5:15
  • \$\begingroup\$ It's an interview question which tells about how you approach problems. How to actually solve the problem depends how the bits are available to you to receive. Serially? Or parallel? How many bits at a time? Which is not specified. So there is no answer how to actually do it, there are details missing. \$\endgroup\$
    – Justme
    Jun 1 at 5:16
  • \$\begingroup\$ @NarsimhaKethiri Have a look at the RISC-V SERV. It is a bit-serial ALU. You can use the concept, adapting it for a 4-bit slice (instead of the 1-bit slice that the SERV uses.) This is not rocket-science. \$\endgroup\$
    – jonk
    Jun 1 at 5:24
  • 1
    \$\begingroup\$ They said you couldn't use other adders but other logic is fine. So chuck it in a couple of (shift) registers and do the job 4 bit at a time \$\endgroup\$ Jun 1 at 5:51

1 Answer 1

0
\$\begingroup\$

Right, if only there were a logic block to select one input from many? Some sort of "plexer", with "multi" inputs? :)

(Not trying to be snide, just... it's called a multiplexer, it's rather hard to name without giving it away, okay?..)

But then, what drives the selection? Okay so we're going to need a state machine. Not much of one, probably just a couple counters and latches to sequence everything. Right so you add the low bits, you get your 5 bits out (4 + carry), loop the one bit (carry) back in with the next nibble, and so on down the line, sourcing from input register N and latching into output register N, taking carry from N-1 (the first carry being provided from a separate carry input pin, most likely), and when the last register is strobed out, deassert all the internal enables/strobes, clear the counter(s) and set a flag "result ready", something like that maybe, so the surrounding system knows when to check for output.

Also, is this a "full" 4-bit adder i.e. with carry input, or do we actually need to chop it down by one i.e. do it 3 bits + carry at a time? Either way, same structure, just different bit assignments, and number of iterations.

Or you could do it with shift registers, since the input and output registers don't have to be addressable in any order, they're only ever used in strict sequence. In that case, four parallel-load serial-shift registers (32 bits long, each) could be used for the input, and serial-in, parallel-out for the output. Basically a bit-serial architecture but with a couple bits working in parallel. Or put another way: it's still digit-serial but it's in base 16 instead of base 2.

And then to make it a full proper block, we need some kind of access specification. Maybe we have a 4-bit bus assigning 32 individually addressable registers, or 8-bit x 16, etc.; this would be fine for a memory-mapped peripheral (many MCUs implement arithmetic extensions in this sort of way). Maybe it's streaming (bit- or word-serial) and the design has to be a bit more finely crafted to that (a transaction being packet-oriented or something; data is always in motion, no local memory needed (beyond the carry that is)). And probably some control signals, like bus strobe (read/write?), start cycle, stop cycle/reset, cycle complete, and clock.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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