2
\$\begingroup\$

How can I add two 16-bit numbers using a 32-bit adder?

The 32-bit adder takes one cycle to add two numbers. How can I add "p+q" and "r+s" (16-bit numbers) in one cycle?

Note: The 32-bit adder is a black box; I can't modify anything inside. I can add combo logic outside, though.

\$\endgroup\$
6
  • \$\begingroup\$ Adder details, please. \$\endgroup\$
    – jonk
    Commented Mar 21, 2021 at 8:04
  • 1
    \$\begingroup\$ You break the carry chain halfway up. \$\endgroup\$
    – user16324
    Commented Mar 21, 2021 at 14:16
  • \$\begingroup\$ @jonk - its a FA \$\endgroup\$
    – sandy99
    Commented Mar 21, 2021 at 20:57
  • 1
    \$\begingroup\$ @BrianDrummond: internal modifications are not allowed inside 32bit adder. How will you make sure 16th bit adder carry is not feed to 17th bit adder? \$\endgroup\$
    – sandy99
    Commented Mar 21, 2021 at 20:59
  • 1
    \$\begingroup\$ cycle is a fun concept with combinational logic. \$\endgroup\$
    – greybeard
    Commented Mar 14, 2023 at 7:20

3 Answers 3

4
\$\begingroup\$

I am adding one more answer since I have been thinking a bit more about it. It is by far more optimal than my previous solution.

We have 32-bit operands A and B, on which we will perform 32-bit addition (as per the OP restrictions go). The lower 16 bits are Alow and Blow. The higher ones are Ahigh and Bhigh.

Before driving A and B operands to the 32-bit adder, set MSBs (i.e., 16th bits) of Alow and Blow to 0. This way we prevent overflowing to the 17th bit, which is the LSB of the high operands. After doing that, the high addition is performed correctly. The low part needs a very little correction described below.

The MSB of the low result is defined as XOR between MSBs of the low adder result, Alow, and Blow. That performs a single-bit addition with no carry-out signal driving. Other result bits are directly connected to the adder output.

See the example below applied on an 8-bit adder, where two independent 4-bit adds are performed. Your 32-bit addition is analogical.

schematic

simulate this circuit – Schematic created using CircuitLab

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Great answer (+1) but I think your example schematic needs some fixes. It should have two 5-bit outputs, not 4-bit, and needs to make use of the adder's carry-out. \$\endgroup\$ Commented Mar 23, 2021 at 0:49
  • 1
    \$\begingroup\$ @Dominik thank you for the solution. This looks like right answer. \$\endgroup\$
    – sandy99
    Commented Mar 23, 2021 at 4:00
  • \$\begingroup\$ @pericynthion, yes carry for lower bits needs to be generated, it is missing in this picture \$\endgroup\$
    – sandy99
    Commented Mar 23, 2021 at 4:11
  • \$\begingroup\$ carry for lower bits is (((AL3 xor BL3) and s3) or (AL3 and BL3)) \$\endgroup\$
    – sandy99
    Commented Mar 23, 2021 at 4:18
  • \$\begingroup\$ @pericynthion You are right. I have included it in the schematic in my last edit. \$\endgroup\$ Commented Mar 23, 2021 at 19:25
0
\$\begingroup\$

The easiest way to do it would be to catch the 16th adder carry-out signal and do not let it pass to the 17th adder carry-in signal. This will basically create two independent 16-bit adders, so this is probably not what you want but I still wanted to mention it.

If you have a 32-bit adder as a black box (i.e., no internal modification possible), I cannot see possible creating an optimal solution without any additional logic. I have prepared one suboptimal solution below to fully answer your question. Please note there are more those.

We will deduce the 16th adder carry out manually (Carry). We can do it based on the combination of the 17th bits of the input operands (Ai and Bi) and the 17th bit of the result output (Yo). See the table below.

Ai Bi Yo Carry
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

E.g., in the second row, we can see that the carry must have occurred since both input signals are 0 and the output signal is 1. That would be otherwise impossible.

When the carry signal is 1, it means that the upper 16 bits are incremented by one compared to their real 16 bits result. That needs additional combinational correction.


Another suboptimal solution may include detecting the 16th adder carry-out signal based on 16-bit input operands (e.g., using the carry-lookahead adder method) and modify 16th bits of the input operands accordingly so that the carry signal between individual 16-bit additions is never set.

\$\endgroup\$
2
  • \$\begingroup\$ "When the carry signal is 1, it means that the upper 16 bits are incremented by one compared to their real 16 bits result. That needs additional combinational correction." Can you elaborate more on what combination correction is required? How will you make sure 17th bit adder input carry is not from 16th bit adder output carry? \$\endgroup\$
    – sandy99
    Commented Mar 21, 2021 at 21:15
  • \$\begingroup\$ Actually, it will. AFAIU, that is your restriction (no internal modifications). To answer your question; you can use this single-bit carry signal and subtract it from the higher 16 bits. This is not optimal at all, though. But I just got an idea - let me add one more answer. \$\endgroup\$ Commented Mar 22, 2021 at 18:55
0
\$\begingroup\$

There are four places where one can add an external 1-bit adder, and two where the 2n-bit adder can be fed something other than operand bits to break the carry-chain.
At the MSB of either 2n-bit adder half, a full adder is required no matter what.
At the LSB, a half adder will do when no carry in is required; at the lower significant half, the 2n-bit adder would need to have a carry in.

schematic

simulate this circuit – Schematic created using CircuitLab

With adder inputs equal on the LSB of the upper half, the carry from the lower half will have no effect on the carry "into bit 1" of the upper half, but appear at its sum LSB.

\$\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.