What Every Programmer Should Know Computer 002

发表于 2022-07-26 更新于 2023-02-02 分类于 Computer 阅读次数： Changyan：本文字数： 2.8k 阅读时长 ≈ 5 分钟

What Every Programmer Should Know About Computer 002

上一篇我们介绍了早期计算机和现代计算机构成位的不同硬件，计算机最底层的抽象“从硬件层抽象出二进制值”，以及二进制值的简单计算(和对应的门电路)。这一篇文章，将介绍一些更复杂的门电路(Gate Combinations )。

加法器

上一篇我们介绍了二进制数的加法，将两个比特相加时，实际上当前位的计算结果是两个比特的XOR值，进位值是2个比特的AND值。

半加器

A	B	A+B	XOR	AND
0	0	00	0	0
0	1	01	1	0
1	0	01	1	0
1	1	10	0	1

根据上述表格，我们基于门电路实现ALU的两个bit相加的逻辑。

上图所示电路被称为半加器，有两个输入(A和B)，和两个输出(半加和数，进位数); 所谓半加就是不考虑进位的加法.半加器虽能产生进位值，但半加器本身并不能处理进位值(上图右边接了一个数值显示器，这个显示器是支持进位的)，抽象表示如下图。

全加器

如果要计算超过1位的加法，由于涉及进位，因此有3个输入(C是进位)，真值表如下:

A	B	C	Carry(进位)	Sum(和)
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
1	0	0	0	1
0	1	1	1	0
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

全加器逻辑上可以由2个半加器和or门组合而成。原理图如下

对于全加器来说，它有3个输入，A，B,C（下级进位）和2个输出，SUM(总和)和Carry(进位)完整的电路图版本的全加器如下

多位全加器

接下来我们可以通过半加器和全加器的组合来实现多位加法器，这里我们以4位加法器举例(如果不需要连接其他进位信号-这里指C0，则最低位的全加器可以用半加器替换)。

在上图中A0-A3(低位到高位)代表4位二进制数A，B0-B3(低位到高位)代表4位二进制数B。S0-S3(低位到高位)代表A+B的总和，C4代表A+B的进位，如果C4没有得到处理，那么C4也常被称为溢出，为了处理溢出，可以考虑增加位数。

上图所示的多位加法器，也被成为4位行波进位加法器。行波进位加法器得名于从一个位进位到下一个位的方式，两位之间进位的方式就像波浪一样。可以看到每个位都有两个门发生延迟，如果构建一个32位或64位的加法器，延迟会增加很多。于是有了超前进位加法器。

行波进位加法器的高位的运算必须等待低位的进位输出信号，超前进位加法器(Lookahead Carry Adder)的优化思路就是”能否提前计算出「进位输出信号」？”.

超前进位加法器

对于每一位全加器的输入, $ai$ , $b_i$ , $c{i-1}$ 和输出 $s_i$, $c_i$ 有以下公式.

$s_i = a_i \oplus b_i \oplus c_i$ $c_{i+1} = a_i b_i + c_i \oplus ( a_i \oplus b_i )$

其中，

$a \oplus b$ 表示 a异或b
$ab$ 表示 a与b
$a+b$ 表示 a或b

假设我们有如下定义:

$P_i = a_i \oplus b_i$ $G_i = a_i b_i$

注意，P和G实际上刚好是半加器。对于N比特超前进位加法器，进位与和公式将重新书写如下：

$s_i = P_i \oplus c_i , i= 0...N-1$ $c_{i+1} = G_i + P_i c_i , i= 0...N-1$

以4比特LCA加法器为例，其进位链与和公式分别计算如下：

$c_1 = G_0 + P_0 c_0$ $c_2 = G_1 + P_1 c_1 = G_1 + P_1(G_0 + P_0c_0)= G_1+G_0P_1+P_1P_0c_0$ $c_3 = G_2 + P_2 c_2 = G_2 +G_1P_2+G_0P_2P_1+P_2P_1P_0c_0$ $c_4 = G_3 + P_3 c_3 = G_3 +G_2P_3+G_1P_3P_2+G_0P_3P_2P_1+P_3P_2P_1P_0c_0$ $s_0=P_0 \oplus c_0$ $s_1=P_1 \oplus c_1$ $s_2=P_2 \oplus c_2$ $s_3=P_3 \oplus c_3$

可以发现，$c_4$ 和 $s_0$~ $s_3$ 这些参数，全部已知。由此我们得到了提前计算进位输出的方法，用这样的方法实现了加法器就被称为超前进位加法器。

C4门电路

如上图所示电路，可以直接从输入计算出S1-S3以及C4。

先从Ai和Bi生成Pi和Gi
利用LCA,生成对应的Ci
通过Ai,Bi和Ci生成Si

对于位宽更大的LCA如16，32，64bitLCA等可以并行生成所有的PG和进位C，但这会造成电路极大的扇入和扇出；另外可以根据4bitLCA级联而成，如16bitLCA可由4个bit级联而成(这也被成为递归超前进位加法器-RLCA)。

Enabler(开关)

Decoder(解码器)

解码器的作用是将编码后的二进制值解码为一组独立的位，是一种具有N路输入和$2^N$路输出的复杂门电路。下图是2线-4线Decoder的电路图。

可以发现电路实质上是输出了输入的所有最小项表达式。上面的每个输出都分别对应了一个最小项表达式。

最小项：n个变量的逻辑乘，即与形式，每个变量以原变量或者反变量的形式出现一次.

解码器包括2线－4线解码器、3线－8线解码器或4线－16线解码器。在有使能信号输入的情况下，2个2线－4线解码器可以组成1个3线－8线解码器，同样，2个3线－8线解码器可以组成1个4线－16线解码器。

在这类电路设计中，2个3线－8线解码器的使能输入都来自于第四个输入端，这一输入在2个3线－8线解码器间起到了选择器的作用。这使得第四个输入端可以使2个解码器中的任何一个工作，其中第一个解码器产生输出D(0)至D(7)，第二个解码器产生输出D(8)至D(15)。包含使能输入的解码器又称解码器－多路分配器。因此，将第四个输入端作为2个解码器共享的输出就能组成1个4线－16线解码器，能产生16个输出。

ALU(算数逻辑单元)

算术逻辑单元（英语：Arithmetic logic unit，简称：ALU）是一种可对二进制整数执行算术运算或位运算的组合逻辑数字电路。ALU 是许多类型的计算电路的基本部件，这些计算电路包括计算机的中央处理单元（CPU）、浮点处理单元（FPU）和图形处理单元（GPU）。单个CPU、FPU 或 GPU 可能包含多个 ALU。 — wikipedia

通常来说ALU分为2个单元,1个算术单元和1个逻辑单元。算术单元负责算术运算,比如加减法，增量运算（给某个数字+1）。逻辑单元执行逻辑操作，比如之前讨论过的 AND，OR 和 NOT 操作，它也能做简单的数值测试，比如一个数字是不是负数。

ALU 的输入包括需要运算的数据（也称为运算数）和表明了运算操作类型的指令码。ALU 的输出是其执行运算的结果。在许多的设计中，ALU 还带有状态输入或输出，可将其之前操作或当前操作的信息在 ALU 和外部状态寄存器间传递。图中控制信号从左侧输入，状态信号从右侧输出；数据从上到下流动。