binary adder

Adder (also called summator in some languages is a device for performing the operation of addition. While adders can be constructed for various numerical representations of numbers, they most often use a typical binary representation[1]. It also describes subtractor that is not much different from the adder.

Implementation

The easiest way to build the adder is to combine XOR and AND logic gates. When we add two binary digits, the first digit of the sum is the output of the XOR element (00 = 0, 01 = 1, 10 = 1 and 11 = 0) and the second digit is the output of the AND element (all combinations apart 11 give 0, 11 gives 1). Hence the device can be described as:

,

where is the output signal indicating that the result of addition does not fit into the dedicated single digit (a carry signal).

Half adder that adds two single digit binary numbers (A and B) and produces the two digit binary sum.

This circuit can add single digit numbers but cannot be scaled to add the larger numbers. Remembering the addition rules, for adding arbitrary bin numbers, three digits must be added: the bit in the first number, the bit in the second member at the same position and the carry value from the previous position. Device, capable to add the three binary digits (full adder, or simply adder) is more complex, and it is possible to see elements of the two connected and cooperating half-adders in this circuit:

Full adder that adds two single digit binary numbers (A and B) and the carry value from the previous position. It produces the two digit binary sum.

This second adder can be cascaded as described in [2] to add numbers of any length. Cascading requires to have a one adder per bit. For the first pair of digits, half adder can be used (as it cannot be a carry value there).

The work of the full adder can be described by the following formulas:

,

where are the input and output signals of the carry.

All three inputs (two values and carry) are equal and interchangeable.

Cascading

See also Carry look-ahead adder

Full adders can be arranged into chain, adding numbers of arbitrary length. Each adder adds three binary numbers (first value digit, second value digit and carry bit from the previous cell) and produces value and carry digits. The carry bit of the highest (right most) cell is presented as the fifth, most significant digit of the sum. The carry input of the lowest cell is assumed to be 0.

Chain of adders to add the two four digit binary numbers. The least significant digit is numbered as 1

This arrangement is called a ripple carry adder. It is scalable but not parallel, as adder from any non-lowest digit needs to wait for the carry output from the previous digit to produce its value (and carry bit for the next higher digit). Hence operation of addition actually propagates from lowest to highest bit (from left to right in the schema). As even highest digits may depend on the lowest digits (1111 + 0001 = 10000, 1111+0000=00000), this design is too slow to add really big (say 128 bit) numbers. There are other, more advanced designs that allow more parallelism. They are described in separate article, Carry look-ahead adder.

Problems of the ripple carry adder become obvious after we add delay elements that simulate delays in the logic gates of each cell

Subtractor

Adder can be relatively easily converted to subtractor. For the binary operation, the first digit of the result for addition and subtraction operation stays the same and still can be computed with XOR element. The overflow is no longer possible but we need to support situation when one is subtracted from zero, producing a single digit negative value. Following usual rules of subtraction, in such case we need to set the flag of the negative result (the second output of the subtractor, borrow) and set 1 as the output of the first digit. The borrow for A - B can only happen when A = 0 and B = 1 that can be implemented with AND and NOT element. Hence a single NOT element in front of the input of AND element converts adder into subtractor:

where R is the result and Z is the borrow signal indicating that B > A.

Half subtractor that subtracts two single digit binary numbers (A and B) and produces value (first digit) and borrow (second digit) outputs

Similarly as the two input adder, the provided two input device is only half-subtractor that cannot be scaled to subtract binary numbers of arbitrary length.

The full subtractor must have additional borrow input, taking into consideration if the borrow signal has been produced by the subtraction of the previous digit. The equations of the full subtractor are:

Binary multiplier is also built using binary adders.

References

  1. 1 Hardware algorithms for arithmetic modules
  2. 2 Adding Binary Numbers