计算机是如何做加法的?(2)——构建一位加法器

摘要:关于如何在半加器的基础上构建全加器。

目录
[隐藏]

在上一篇中,通过对多位加法器结构的分析,我们得到了一位加法器的原型,也即所谓的全加器(Full Adder, FA)

full adder FA

现在考虑如何去实现它。

分解

观察一下所谓的进位输入,还是以前述的十位上的加法为例:

其实就是做了一次三个一位数的加法“5+2+1”而已。

怎么做三个数加法呢?很简单,依然是运用分而治之的原则。分两次来做,5+2=7,7+1=8。

进位可完全视作是一个特殊的加数(只能为 1 或者为 0),与其余两个加数等价,要把三个数相加,显然你需要知道如何把两个数相加,之后再把结果与第三个数相加。

半加器

因此,还是要回到两个数相加的情况,我们需要一个更为基础的能处理两数相加的构件:

half adder

这样的一个东西,我们称之为半加器(Half Adder,HA)。它能接收两个输入,并产生两个输出:一个加位(Sum),一个进位(Carry)。

用半加器构建全加器

与前面类似,先不考察半加器的细节,假定它已经有我们想要的功能,我们如何用它来构建全加器?

考察一个例子:7+8+1(1 代表一个进位输入),最终结果是 16,要得到一个 6 和一个新的进位。

既然实质就是做两次两个数的加法,

还记得前面关于串行与并行策略的讨论不?

那么作为一种简单粗暴的方式,依旧是弄它两个半加器,然后连起来,代表两次加法:

two half adder example 871

在这里,第二个半加器的进位输入被我们丢弃了,只取了第一个的进位作为最后输出。

对上述例子而言,目前的做法显然是 OK 的,但能否适应更一般的情况呢?

让我们来看另一个例子:4+5+1
two half adder example 541

结果悲剧了,应该是 10,但输出却是 00,在第二个半加器里才出现了进位,但被丢弃了,导致了错误的结果。

由于无法预料会在哪里产生进位,丢弃哪一个都不行。简单的处理就是再引入一个半加器,把这俩再加一下:

full adder by three half adder

注:是把第三个半加器的加位作为最终的进位输出,进位则丢弃(最终只需要两个输出,势必要丢掉一个)。

如果我们观察一下人做加法的一般过程,那么我们的确是在不知不觉中做了三次两个数的加法:

three adding example

现在考察以下两种情况,都能够满足要求:

three half adder example 541
three half adder example 871

两次进位的问题

现在,即便前面两个都产生了进位,1+1=2,第三个半加器结果最大也不过是 2,要满 10 才能产生进位,因此,丢弃它的进位是安全的。

但另一方面,最终的进位输出(CO)可能会参与到下一级的进位输入(CI)中去,比如前面构建多位加法器时:

two fa adder co as next ci

如果真的产生了两次进位,则违反了我们关于进位输入只能为 1 或 0 的假设。

仔细审查一下,我们可以断言,如果进位输入满足了假定,两个半加器都产生进位的情况是不存在的。

因为这意味着三个数之和至少达到了 20!

impossible carry issue

考虑其中的进位输入最大也就是 1,三个数最极端的情况也就是  9+9+1=19,不可能超过 20。

因此,只要一开始没有违反进位输入(CI)的假定,那么进位输出(CO)也是可控的,因此级联多个一位全加器组成多位加法器是可行的。

对进位逻辑的再思考

综上所述,进位或者来自第一个半加器,或者来自第二个半加器;又或者都没有进位,但不可能同时产生进位!

概括地讲,第三个半加器只需处理这三种情况:0+0,0+1,1+0。

它甚至不用处理我们通常认为最简单的 1+1。

这对于一个我们设想能够处理任何两个个位数相加的半加器来说,的确是有点屈才了,从它的进位输出被丢弃也可看出它没有得到充分利用。

事实很明显:这里的逻辑其实无需用一个半加器去实现。

到目前为止,我们的全加器由三个半加器构成:

full adder by three half adder

它是能够满足我们的要求的,但我们希望或许能够简化并用一个更简单的器件代替第三个半加器:

full adder by two half adder and an unknown part

到目前为止,讨论都在十进制的基础上,但不难注意到,对于进位逻辑而言,它只涉及 0 和 1,这或许是开始逐步引入二进制的一个不错的契机。下一篇,将进一步探讨如何简化及改进目前的全加器结构,焦点将位于第三个半加器上。

发表评论

电子邮件地址不会被公开。 必填项已用*标注