Editing adder

{{title|Adder}}
An '''adder''' (sometimes called a '''summer''') is a device that adds two numbers and generates the summed result.

In [[digital circuit]]s, an adder usually adds two ''N''-bit numbers and generates an ''N''-bit number. In addition to generating a sum, adders often also generate an [[overflow flag]] and a [[carry flag]]. Adders are used in many parts of the [[microprocessor]] such as the [[ALU]], [[program counter|PC]], [[counters]], calculating [[effective addresses]] and table indices, multipliers, filters, and in various other components.

In [[analog circuit]]s, [[adder (analog)|adders]] usually deal with two [[real number]]s instead.

== Basic design ==
<math style="float:right;">
\begin{align}
A + B &= Q \\ 
0_2 + 0_2 &= 00_2 \\
0_2 + 1_2 &= 01_2 \\
1_2 + 0_2 &= 01_2 \\
1_2 + 1_2 &= 10_2 \\
\end{align}
</math>
A 1-bit adder adds two single-bit values together. There are four such possible operations. All but the 1+1 operation result in a single-digit sum. The 1+1 operation produces a sum with two digits. The higher significant bit of that value is known as a carry. The digital component that performs the addition of two bits is called a '''half adder'''. When two multi-bit numbers are added together, the carry out from the lower bit must be accounted for in the higher addition of the higher bits. When a half adder accounts for a carry in, it becomes a '''full adder'''.

=== Half Adders (HA) ===
{{main|Half adder}}

{| class="wikitable left" style="float:left; margin: 15px;"
!colspan="5"|Half Adder
|-
!colspan="2"|Input!!C<sub>out</sub>!!S!!Q<sub>10</sub>
|-
|0||0||0||0||0
|-
|0||1||0||1||1
|-
|1||0||0||1||1
|-
|1||1||1||0||2
|}
[[File:1-bit addition.svg|right|150px]]
A '''half adder''' is a simple device that adds two single bit inputs. The result of a half adder (in base 10) is either 0, 1, or 2. Two bits are required to represent that output; they are called the '''sum''' S and '''carry-out''' C<sub>out</sub>. The carry-out of one half adder is typically used as the carry-in of the next half adder. For that reason it is said to have double the weight of the other bit.

The sum is 1 only when one of the operands is 1, otherwise it's 0. This can be realized by simply [[XORing]] them together. The carry out bit is one only when both addends are one; [[ANDing]] the two bits will generate the desired output.

<math>
\begin{align}
S =& A \oplus B \\
C_{out} =& A \cdot B
\end{align}
</math>

{{clear}}
=== Full Adder (FA) ===
{{main|full adder}}

[[File:Full adder black box.svg|right|150px]]
A major drawback of a half adder is that it lacks the ability to add two bits and account for a carry-in that might have been brought from the previous digit. As previously stated, the carry-out of one half adder is the carry-in of the next half adder. A '''full adder''' is a simple device that can receive a carry-in bit input in addition to adding two single bit inputs. A full adder has three inputs A, B, and C<sub>in</sub> and two outputs S and C<sub>out</sub>. Full adders are typically combined together in a cascading way (C<sub>in</sub> to <sub>out</sub>), creating ''N''-bit adders (16, 32, 64, etc..).

The sum output can be expressed as:

<math>
\begin{align}
S =& A \oplus B \oplus C \\
C_{out} =& \text{Maj}(A, B, C)
\end{align}
</math>

== BCD Adders ==
{{main|BCD Adder}}

Most adders typically use the [[binary numeral system]], however they can use any other numerical representation such as [[binary-coded decimal]]. Binary adders are typically simpler to design when compared to a BCD adder where roughly 20 percent more circuitry is required.

== Advanced Designs ==
Due to the adder's central role in so many digital circuits, it has been the subject of many researches. Various different designs have been developed over the years to meet a broad range of requirements (e.g. complexity, cost, space, and time trade-offs).

=== PGK Cell ===
{{empty section}}
Many complex adder designs relay on the ability to calculate carry bits quickly.

=== Two-operand adders ===
==== Ripple-carry adder (RCA) ====
{{main|Ripple-carry adder}}
{{empty section}}

==== Carry-lookahead adder  (CLA) ====
{{main|Carry-lookahead adder}}
{{empty section}}

===== Lookahead carry unit (LCU) =====
{{main|Lookahead carry unit}}
{{empty section}}

===== Ripple-block carry-lookahead adder (RCLA) =====
{{main|Ripple-block carry-lookahead adder}}
{{empty section}}

===== Block carry-lookahead adder (BCLA) =====
{{main|Block carry-lookahead adder}}
{{empty section}}

==== Ling adder ====
{{main|Ling adder}}
{{empty section}}

==== Manchester carry-chain adder ====
{{main|Manchester carry-chain adder}}
{{empty section}}

==== Carry-select adder ====
{{main|Carry-select adder}}
{{empty section}}

==== Carry-skip adder ====
{{main|Carry-skip adder}}
{{empty section}}

==== Conditional-Sum Adder ====
{{main|Conditional-sum adder}}
{{empty section}}

==== Parallel-prefix adders ====
{{main|Parallel-prefix adder}}
Parallel prefix adders are a class of highly-efficient binary adders. Several parallel-prefix adder topologies have been developed that exhibit various space and time characteristics.

===== Beaumont-Smith adder (BSA) =====
{{main|Beaumont-Smith adder}}
{{empty section}}

===== Ladner-Fischer adder =====
{{main|Ladner-Fischer adder}}
{{empty section}}

===== Kogge-Stone adder =====
{{main|Kogge-Stone adder}}
{{empty section}}

===== Brent-Kung adder =====
{{main|Brent-Kung adder}}
{{Brent-Kung adder is a very well-known logarithmic
adder architecture that gives an optimal number of stages from
input to all outputs but with asymmetric loading on all
intermediate stages. It is one of the parallel prefix adders.
Parallel prefix adders are unique class of adders that are based
on the use of generate and propagate signals. The cost and
wiring complexity is less in brent kung adders. But the gate
level depth of Brent-Kung adders is 0 (log2(n)), so the
speed is lower.}}

===== Han-Carlson adder =====
{{main|Han-Carlson adder}}
{{empty section}}

=== Multi-operand adders ===
(Partial product accumulator)

==== Carry-save adder array ====
{{main|Carry-save adder array}}
{{empty section}}

==== Wallace tree adder ====
{{main|Wallace tree adder}}
{{empty section}}

==== Balanced delay tree adder ====
{{main|Balanced delay tree adder}}
{{empty section}}

==== Overturned-stairs tree adder ====
{{main|Overturned-stairs tree adder}}
{{empty section}}

==== Compressors trees ====
{{empty section}}

===== 3:2 compressor tree =====
{{main|3:2 compressor tree}}
{{empty section}}

===== 4:2 compressor tree =====
{{main|4:2 compressor tree}}
{{empty section}}

===== Dadda tree =====
{{main|Dadda tree}}
{{empty section}}

== See also ==
* [[adder (analog)]]


[[Category:Adders]]