第二十课:16 位加法器(Add16),让进位逐位传递

从两位加法器扩展到 Add16,理解逐位进位、16 位输出与最高位进位的舍弃。

本章目录CONTENTS ↓

上一课把一颗 HalfAdder 接到一颗 FullAdder,完成了两位相加。把同一条进位连线继续向高位延伸,就得到 16 位加法器(16-bit adder,官方芯片名 Add16)。它的输入 a[16]、b[16] 各是一条 16 位总线,输出 out[16] 也是 16 位;out[i] 表示第 i 位的和。

从最低位开始接

a[0] 和 b[0] 是最低有效位(least significant bit,LSB)。这里没有来自更低位的输入进位,用半加器即可。它产生 out[0],同时把进位送给第 1 位。第 1 位起使用全加器:每一级接收本位的 a[i]、b[i] 和前一级的进位,再输出 out[i] 与传给下一级的进位。这种逐位向高位传递的结构称为逐位进位加法器(ripple-carry adder)。

第 0 位:HalfAdder(a[0], b[0]) → out[0], c1
第 1 位:FullAdder(a[1], b[1], c1) → out[1], c2
第 2 位:FullAdder(a[2], b[2], c2) → out[2], c3
……
第 15 位:FullAdder(a[15], b[15], c15) → out[15], 最终进位

这里 c1 是第 0 位传给第 1 位的进位,依此类推;它们只是电路内部的连线,不是 Add16 的输出端口。

例如 a=0000 0000 0000 0111、b=0000 0000 0000 0001。第 0 位算 1+1,写下 out[0]=0,传出进位 1;第 1、2 位各算 1+0+1,仍写 0 并向上进 1;第 3 位算 0+0+1,写 1,进位到此为 0。结果是 0000 0000 0000 1000,也就是 7+1=8。

为什么没有第 17 位输出

官方 Add16 只定义了 OUT out[16],没有单独的最终进位端口。比如 1111 1111 1111 1111 + 0000 0000 0000 0001 的完整数学结果需要 17 位,但 Add16 只保留低 16 位,所以 out=0000 0000 0000 0000。若把输入看作无符号数,这叫无符号溢出(unsigned overflow);对这颗芯片而言,最高位传出的进位被舍弃。换句话说,out 等于数学结果除以 2¹⁶ 后的余数。

写成 Add16.hdl

CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
HalfAdder(a=a[0], b=b[0], sum=out[0], carry=c1);
FullAdder(a=a[1], b=b[1], c=c1, sum=out[1], carry=c2);
FullAdder(a=a[2], b=b[2], c=c2, sum=out[2], carry=c3);
FullAdder(a=a[3], b=b[3], c=c3, sum=out[3], carry=c4);
FullAdder(a=a[4], b=b[4], c=c4, sum=out[4], carry=c5);
FullAdder(a=a[5], b=b[5], c=c5, sum=out[5], carry=c6);
FullAdder(a=a[6], b=b[6], c=c6, sum=out[6], carry=c7);
FullAdder(a=a[7], b=b[7], c=c7, sum=out[7], carry=c8);
FullAdder(a=a[8], b=b[8], c=c8, sum=out[8], carry=c9);
FullAdder(a=a[9], b=b[9], c=c9, sum=out[9], carry=c10);
FullAdder(a=a[10], b=b[10], c=c10, sum=out[10], carry=c11);
FullAdder(a=a[11], b=b[11], c=c11, sum=out[11], carry=c12);
FullAdder(a=a[12], b=b[12], c=c12, sum=out[12], carry=c13);
FullAdder(a=a[13], b=b[13], c=c13, sum=out[13], carry=c14);
FullAdder(a=a[14], b=b[14], c=c14, sum=out[14], carry=c15);
FullAdder(a=a[15], b=b[15], c=c15, sum=out[15]);
}

最后一行没有连接 carry,因为 Add16 没有对应的输出端口。检查接线时,重点看每一级的 c 是否接前一级的进位,以及每个 sum 是否接同索引的 out[i]。你可以用官方 Add16.tst 与 Add16.cmp 检查结果。

本节只需抓住一条链:最低位产生进位,高位逐级接收并继续传递;16 位之外的最终进位被舍弃。读完并完成页面调试后告诉我,我们再一题一题地检验你的理解。

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

这一页,先记到这里。