Latest revision |
Your text |
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, 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 == | | == Basic design == |
− | <math style="float:right;">
| + | {{empty section}} |
− | \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 == | | == BCD Adders == |
Line 66: |
Line 10: |
| | | |
| == Advanced Designs == | | == 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}} | | {{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]] | | [[Category:Adders]] |