Editing adder

An '''adder''' (sometimes called a '''summer''') is a [[digital circuit]] that 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.

== Basic design ==
<div style="float:right;">
<math>
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
</math>
</div>
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>
S = A \oplus B \\
C_{out} = A \cdot B
</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>
S = A \oplus B \oplus C \\
C_{out} = \text{Majority}(A, B, C)
</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}}
{{empty section}}

===== 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}}


[[Category:Adders]]
@@ Line 1: / Line 1: @@
-{{title|Adder}}
+An '''adder''' (sometimes called a '''summer''') is a [[digital circuit]] that 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.
-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;">
+<div style="float:right;">
-\begin{align}
+<math>
-A + B &= Q \\
+A + B = Q \\
-_2 + 0_2 &= 00_2 \\
+_2 + 0_2 = 00_2 \\
-_2 + 1_2 &= 01_2 \\
+_2 + 1_2 = 01_2 \\
-_2 + 0_2 &= 01_2 \\
+_2 + 0_2 = 01_2 \\
-_2 + 1_2 &= 10_2 \\
+_2 + 1_2 = 10_2
-\end{align}
 </math>
+</div>
 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
@@ Line 39: / Line 35: @@
 <math>
-\begin{align}
+S = A \oplus B \\
-S =& A \oplus B \\
+C_{out} = A \cdot B
-C_{out} =& A \cdot B
-\end{align}
 </math>
@@ Line 48: / Line 42: @@
 === 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..).
@@ Line 54: / Line 49: @@
 <math>
-\begin{align}
+S = A \oplus B \oplus C \\
-S =& A \oplus B \oplus C \\
+C_{out} = \text{Majority}(A, B, C)
-C_{out} =& \text{Maj}(A, B, C)
-\end{align}
 </math>
@@ Line 131: / Line 124: @@
 ===== Brent-Kung adder =====
 {{main|Brent-Kung adder}}
-{{Brent-Kung adder is a very well-known logarithmic
+{{empty section}}
-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 =====
@@ Line 178: / Line 163: @@
 {{main|Dadda tree}}
 {{empty section}}
-== See also ==
-* [[adder (analog)]]
 [[Category:Adders]]