第十九课:全加器(Full Adder),把输入进位算进去

用两颗半加器和一颗 OR 门,把三个单比特相加,得到本位和与输出进位。

本章目录CONTENTS ↓

上一课的半加器(Half Adder)只能计算 a+b。如果低一位又传来一个 1,当前这一位实际要计算的是 a+b+c。能接收这个额外输入的电路叫全加器(Full Adder,官方芯片名 FullAdder)。官方把来自低位的输入进位(carry-in)端口命名为 c;把传给高位的输出进位(carry-out)端口命名为 carry。两者方向相反,不要因为都叫“进位”而接混。

先看它要满足什么

三个输入都只有一位,和的范围是 0 到 3。输出仍是两位:本位和 sum 与输出进位 carry。每一行都满足 a+b+c = sum + 2×carry。

a b 输入进位 c a+b+c 输出进位 carry 本位和 sum
0 0 0 0 0 0
0 0 1 1 0 1
0 1 0 1 0 1
0 1 1 2 1 0
1 0 0 1 0 1
1 0 1 2 1 0
1 1 0 2 1 0
1 1 1 3 1 1

留意 a=b=0、c=1:全加器的 sum=1,正好补上半加器漏算低位进位的问题。a=b=c=1 时结果是 3=11₂,所以 sum 和 carry 都是 1。

用两颗半加器分两次相加

第一颗 HalfAdder 先算 a+b,产生临时本位和 partialSum 与临时进位 carryAB。第二颗再把 partialSum 和输入进位 c 相加,产生最终 sum 与另一条临时进位 carryWithC。只要两次加法有一次向高位进位,最终 carry 就应为 1,所以用逻辑或(OR,芯片名 Or)合并:

HalfAdder(a, b) → partialSum, carryAB
HalfAdder(partialSum, c) → sum, carryWithC
Or(carryAB, carryWithC) → carry

例如 a=1、b=1、c=1:第一颗算 1+1,得到 partialSum=0、carryAB=1;第二颗算 0+1,得到 sum=1、carryWithC=0;最后 carry=1 OR 0=1。输出 carry sum = 11₂,与 1+1+1=3 一致。

两条临时进位不会同时为 1:若 carryAB=1,必有 a=b=1,第一颗的 partialSum 就是 0,第二颗不可能再产生进位。因此把两条进位用 Or 合并,不会丢掉“进了两次”的情况。

写成 FullAdder.hdl

CHIP FullAdder {
IN a, b, c;
OUT sum, carry;
PARTS:
HalfAdder(a=a, b=b, sum=partialSum, carry=carryAB);
HalfAdder(a=partialSum, b=c, sum=sum, carry=carryWithC);
Or(a=carryAB, b=carryWithC, out=carry);
}

这里 c 是官方接口中接收输入进位的名字;carry 是最终送出的进位。两个临时信号 carryAB、carryWithC 只是本电路内部的连线。将代码放入 FullAdder 后,可用官方的 FullAdder.tst 与 FullAdder.cmp 核对全部输入情况。

本节的关键是:半加器能算两个位,全加器再接入第三个位 c;两次产生的临时进位合并为一个输出进位。下一节会把多个全加器连起来,计算 16 位加法。读完并完成页面调试后,告诉我,我们再按一题一题的节奏练习。

参考资料:官方 Project 2 规格与测试契约、官方 FullAdder.hdl 接口。

这一页,先记到这里。