第十九课:全加器(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, carryABHalfAdder(partialSum, c) → sum, carryWithCOr(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 位加法。读完并完成页面调试后,告诉我,我们再按一题一题的节奏练习。
这一页,先记到这里。