What Every Programmer Should Know Computer 002
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$ 有以下公式.
其中,
- $a \oplus b$ 表示 a异或b
- $ab$ 表示 a与b
- $a+b$ 表示 a或b
假设我们有如下定义:
注意,P和G实际上刚好是半加器。对于N比特超前进位加法器,进位与和公式将重新书写如下:
以4比特LCA加法器为例,其进位链与和公式分别计算如下:
可以发现,$c_4$ 和 $s_0$~ $s_3$ 这些参数,全部已知。由此我们得到了提前计算进位输出的方法, 用这样的方法实现了加法器就被称为超前进位加法器。
如上图所示电路,可以直接从输入计算出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 和外部状态寄存器间传递。图中控制信号从左侧输入,状态信号从右侧输出;数据从上到下流动。