查看“︁加法器”︁的源代码

{{NoteTA
|G1=Communication
|G2=Electronics
|1=zh:一位; zh-cn:一位; zh-tw:一位元;
}}
在[[电子学]]中，'''加法器'''（{{lang-en|'''adder'''}}）是一种用于执行[[加法]]运算的[[数位电路]]部件，是构成[[电子计算机]]核心[[微处理器]]中[[算术逻辑单元]]的基础。在这些[[电子系统]]中，加法器主要负责[[计算]][[地址]]、[[索引]]等[[数据]]。除此之外，加法器也是其他一些[[硬件]]，例如[[二进制数]]的[[乘法器]]的重要组成部分。

尽管可以为不同[[计数系统]]设计专门的加法器，但是由于[[数位电路]]通常以[[二进制]]为基础，因此[[二进制]]加法器在实际应用中最为普遍。在数字电路中，二进制数的[[减法]]可以通过加一个[[负数]]来间接完成。为了使负数的计算能够直接用加法器来完成，计算中的负数可以使用[[二补数]]（[[补码]]）来表示，具体的细节可以参考数位电路相关的书籍。{{R|Stephen|page=244-248}}

== 半加器 ==
[[File:half Adder.svg|right|thumb|一位半加器的符号]]
（{{lang-en|half adder}}）的功能是将两个一位[[二进制数]]相加。它有两个输出：

* [[和]]：记作 ''S''，来自对应的英语 {{lang|en|Sum}}；
* [[进位]]：记作 ''C''，来自对应的英语 {{lang|en|Carry}}一位的数字。因此，这两个一位[[二进制数]]的和用十进制表示即等于{{nobreak|2''C'' + ''S''}}。右图是一个最简单的半加器设计，使用一个[[异或门]]来产生 ''S''，一个[[与门]]来产生 ''C''。和 '''S''' 的布尔逻辑是 '''A'B+AB''''，进位 '''C''' 的布尔逻辑是 '''AB'''。如果再添加一个[[或门]]处理两个半加器的进位信号，就构成了一个'''全加器'''。
<ref>{{cite book
 | title = Excel HSC Software Design and Development'''
 | author = Geoffrey A. Lancaster
 | publisher = Pascal Press
 | year = 2004
 | isbn = 9781741251753
 | page = 180
 | url = http://books.google.com/books?id=PZkDpS4m0fMC&pg=PA180
 | access-date = 2013-02-24
 | archive-date = 2013-12-31
 | archive-url = https://web.archive.org/web/20131231222803/http://books.google.com/books?id=PZkDpS4m0fMC&pg=PA180
 | dead-url = no
 }}</ref>

半加器将两个输入位加和，产生进位与和，是半加器的两个输出。半加器的输入[[变量_(程序设计)|变量]]叫做'''被加数'''或'''被加位'''。输出[[变量]]为和与进位。

半加器的[[真值表]]如下：

{| class="wikitable" style="text-align:center"
|-
!colspan="2"| 输入 !!colspan="2"| 输出
|-
! ''A'' !! ''B'' !! ''C'' !! ''S''
|-
| 0 || 0 || 0  || 0
|-
| 1 || 0 || 0  || 1
|-
| 0 || 1 || 0  || 1
|-
| 1 || 1 || 1  || 0
|-
|}

== 全加器 ==
[[File:1-bit full-adder.svg|thumb|right|一位[[全加器]]的符号，它与[[半加器]]不同之处在于它还能接收一个低位[[进位]][[输入信号]]''C''<sub>in</sub>。图中的蓝框是为了表明它作为一个整体可以级联构成多位二进制数的加法器。]]

'''全加器'''（full adder）将两个一位二进制数相加，并根据接收到的低位进位信号，输出和、进位输出。全加器的三个输入信号为两个加数''A''、''B''和低位进位''C''<sub>in</sub>。<ref name=Mano79>{{Cite book|author=M. Morris Mano|title=Digital Logic and Computer Design|url=https://archive.org/details/digitallogiccomp00mano|publisher=Prentice-Hall|year=1979|isbn=0-13-214510-3|page=[https://archive.org/details/digitallogiccomp00mano/page/119 119]-123}}</ref>[[全加器]]通常可以通过[[级联]]（cascade）的方式，构成多位（如8位、16位、32位）[[二进制数]][[加法器]]的基本部分。全加器的[[输出]]和半加器类似，包括向高位的进位信号''C''<sub>out</sub>和本位的和信号''S''，相加结果的总和用十進位表达为<math>\mathrm{sum} = 2 \times C_{out} + S</math>。一位全加器的[[真值表]]为：

[[File: Full-adder logic diagram.svg|thumb|right|全加器的符号]]

{| class="wikitable" style="text-align:center"
|-
!colspan="3"| 输入 !!colspan="2"| 输出
|-
! ''A'' !! ''B'' !! ''C''<sub>in</sub> !! ''C''<sub>out</sub> !! ''S''
|-
| 0 || 0 || 0  || 0 || 0
|-
| 1 || 0 || 0  || 0 || 1
|-
| 0 || 1 || 0  || 0 || 1
|-
| 1 || 1 || 0  || 1 || 0
|-
| 0 || 0 || 1  || 0 || 1
|-
| 1 || 0 || 1  || 1 || 0
|-
| 0 || 1 || 1  || 1 || 0
|-
| 1 || 1 || 1  || 1 || 1
|}

在实际的应用中，全加器可以通过不同的方式制造，例如直接利用[[晶体管]]级的[[电路]]，或者由其他现成的[[逻辑门]]来构成。[[和]]、[[进位]]信号对应的[[布林函數|逻辑函数]]表达式分别为<math>S = A \oplus B \oplus C_{in}</math>以及<math>C_{out} = (A \cdot B) + (B \cdot C) + (A \cdot C)</math>。另一种全加器电路与之前的方式略有不同，它用一个异或门来代替或门对其中两个输入信号进行求和，其进位信号对应的逻辑函数表达式分别为<math>C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))</math>。通过适当的逻辑函数变化，可以证明它与前面的计算方法结果一致。{{R|Stephen|page=238, 260}}

在这个实现中，将最后的[[或门]]换成[[异或门]]不会影响逻辑。如果电路使用的是每个芯片上只有一种閘的简单集成电路芯片，仅使用两种閘会比较方便。

全加器可以用两个半加器来构造，将输入端''A''和''B''连接到一个半加器上，然后将其和输出信号与进位输入信号分别作为第二个半加器的两个输入，并将两个进位输出信号进行逻辑或运算。全加器的关键路径（critical path，即经历最多逻辑门的路径）经过两个异或门，终止于和位 <math>s</math>。假定异或门耗费3个延迟来完成，一个全加器的关键路径上施加的延迟等于
:<math>T_{FA} = 2 \cdot T_{XOR} = 2 \cdot 3 D = 6 D</math>
进位模块(carry-block)包括2个逻辑门，因此延迟为
:<math>T_c = 2 D</math>

全加器还可以使用一个三输入的异或门来求和，再使用一个两级与或结构来实现进位信号对应的积之和（sum of products）式。

== 多位加法器 ==
=== 波纹进位加法器（脉动进位加法器） ===

[[File:4-bit ripple carry adder.svg|thumb|用四个一位全加器构成的四位波纹进位加法器]]

可以使用多个一位全加器来构成''N''位加法器，其中对应低位的全加器将其进位输出信号''C<sub>out</sub>''连接到高一位的全加器的进入输入端''C<sub>in</sub>''。这种构成多位加法器的形式被称为“波纹进位加法器”或“脉动进位加法器”（ripple-carry adder），“波纹”形象地描述了进位信号依次向前传递的情形。如果不需要连接其他进位信号，则最低位的全加器可以用半加器替换。

波纹進位加法器的[[布局 (集成电路)|电路布局]]形式较为简单，设计这种[[电路]]花费时间较短。然而，[[波纹进位]]加法器的进位输出、输入所经过的路径上比其他布局方式具有较多的[[邏輯閘]]，高位的计算必须等待低位的进位输出信号被计算出来才能开始，因此造成了更大的[[傳播延遲|延迟时间]]。{{R|Deng|page=49}}

下面简单计算信号在加法器中的延迟。每一个全加器具有[[三级]][[逻辑函数]]。在一个32位的波纹进位加法器中，有32个全加器，随之产生的[[邏輯閘]]延迟则可以根据关键路径的延迟时间来决定，即2倍的最高位全加器输入信号、进位输出延迟，加上31乘以3倍的其他全加器上的延迟，总共等于95倍的邏輯閘延迟。一个 ''n'' 位波纹進位加法器的最坏情形延迟方程为
:<math>T_{CRA}(n) = T_{HA} + (n-1) \cdot T_c + T_s = T_{FA} + (n-1) \cdot T_c = 6 D + (n-1) \cdot 2 D = (n+2) \cdot 2 D</math>
从位位置0到进位输出的进位有一点不同：
:<math>T_{CRA_{[0:c_{out}]}} = T_{HA} + n \cdot T_c = 3 D + n \cdot 2 D</math>
输入进位必须经过 ''n'' 个[[进位生成器]][[模块]]来得到进位输出的效果
:<math>T_{CRA_{[c_0:c_n]}}(n) = n \cdot T_c = n \cdot 2 D</math>

交替进位[[极性]]和[[优化]]的{{le|与或非门|AND-OR-Invert}}的设计可以减少一半的延迟时间。<ref>
{{cite journal
 | journal = 20th IEEE Symposium on Computer Arithmetic
 | title = Fast Ripple-Carry Adders in Standard-Cell CMOS VLSI
 | author = Burgess, N.
 | pages = 103–111
 | year = 2011
 | url = http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F5991607%2F5992089%2F05992115.pdf%3Farnumber%3D5992115&authDecision=-203
 }}</ref>

=== 超前进位加法器===

[[File:4-bit carry lookahead adder.svg|thumb|四位[[超前进位]]加法器]]

为了减少多位[[二进制数]][[加减计算]]所需的时间，工程师设计了一种比脉动进位加法器速度更快的加法器电路，这种加法器被称为“[[超前进位加法器]]”（carry-lookahead adder）。

下面简述超前进位加法器的主要原理。<ref>{{Cite web|url=http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/lookahead.html|title=Fast Addition: Carry Lookahead Adders|publisher=University of Maryland|accessdate=2013-02-28|archive-date=2013-03-04|archive-url=https://web.archive.org/web/20130304144816/http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/lookahead.html|dead-url=no}}</ref>{{R|Stephen|page=255-262}}我们先来考虑构成多位加法器的单个全加器从其低一位获得的进位[[信号]]<math>c_{i+1} = (x_i \cdot y_i) + (x_i \cdot c_i) + (y_i \cdot c_i)</math>，我们可以将它变换为<math>c_{i+1} = (x_i \cdot y_i) + ( x_i + y_i ) \cdot c_i</math>。现在为[[二进制数]]的每一位[[构建]]两个新[[信号]]：

* [[生成]]（Generate）[[信号]]：<math>G_i = x_i \cdot y_i</math>
* [[传输]]（Propagate）信号：<math>P_i = x_i + y_i</math>

于是，某位全加器从低一位获得的进位可以表示为<math>c_{i+1} = G_i + P_i \cdot c_i</math>，例如次低位全加器从最低位获得的进位为<math>c_1 = G_0 + P_0 \cdot c_0</math>，而从最低位开始第三位的那个全加器获得的进位信号则为<math>c_2 = G_1 + P_1 \cdot c_1</math>。在多位脉动进位加法器中，<math>c_2</math>必须连接到低一位的进位输出信号，如果使用这种方式构成多位全加器，则[[逻辑门]]的延迟会发生累加，导致降低电路的[[计算效率]]下降。超前进位加法器采取的方式是，将<math>c_1</math>的[[逻辑函数]]代入到<math>c_2</math>，即<math>c_2 = G_1 + P_1 \cdot ( G_0 + P_0 \cdot c_0 )</math>，于是，这一位的进位输出就只取决于<math>x_1</math>、<math>y_1</math>、<math>x_0</math>、<math>y_0</math>、<math>c_0</math>几个信号，而这几个信号都是计算电路外部的已知信号，而非低一位的计算结果。上面考虑的是从最低位开始第三位的情况。采用类似的代入方法，可以用各位的生成信号<math>G_i</math>、[[传输信号]]<math>P_i</math>，以及最低位从外部获取的进位信号<math>c_0</math>来表示多位全加器的所有进位信号。

[[File:64-bit lookahead carry unit.svg|thumb|六十四位全加器可以逻辑划分为四个十六位超前进位加法器]]
通过列出多位加法器各位的进位输出，可以发现高位的进位输出表达式（积之和式）涉及的变量更多，对应的逻辑电路连线会变得更复杂，而且在实际应用中会遭遇逻辑门的[[扇入]]问题。因此有必要对位数过高的全加器进行逻辑划分，如将六十四位全加器分为四个十六位超前进位加法器来实现（如右图）。多位二进制数加法器的标准芯片通常具有超前进位的组成形式，例如:[[7400系列]]的7483、74283芯片。{{R|Deng|page=50}}

==延伸==
#[[全加器]]
#[[半加器]]
#[[減法器]]
#[[波纹进位加法器]]
#[[超前进位加法器]]

== 参考文献 ==
{{Reflist|refs=
<ref name = "Stephen">{{Cite book|author=Stephen Brown, Zvonko Vranesic|title=Fundamentals of Digital Logic with Verilog Design|year=2002|url=https://archive.org/details/fundamentalsofdi0000brow_t0c5|publisher=McGraw-Hill Education|isbn=0-07-283878-7}}</ref>

<ref name="Deng">{{cite book|title=数字设计基础与应用|author=邓元庆，关宇，贾鹏，石会|publisher=清华大学出版社|isbn=978-7-302-21406-9}}</ref>
}}

== 外部链接 ==
* [http://www.aoki.ecei.tohoku.ac.jp/arith/mg/algorithm.html Hardware algorithms for arithmetic modules]{{Wayback|url=http://www.aoki.ecei.tohoku.ac.jp/arith/mg/algorithm.html |date=20070409104525 }}, includes description of several adder layouts with figures.
* [http://dev.code.ultimater.net/electronics/8-bit-full-adder-and-subtractor/ 8-bit Full Adder and Subtractor]{{Wayback|url=http://dev.code.ultimater.net/electronics/8-bit-full-adder-and-subtractor/ |date=20130301015725 }}, a demonstration of an interactive Full Adder built in JavaScript solely for learning purposes.

{{数字电路}}

{{DEFAULTSORT:Adder (Electronics)}}
[[Category:計算機算術]]
[[Category:加法器|加法器]]