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$ 这些参数,全部已知。由此我们得到了提前计算进位输出的方法, 用这样的方法实现了加法器就被称为超前进位加法器。

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 和外部状态寄存器间传递。图中控制信号从左侧输入,状态信号从右侧输出;数据从上到下流动。

参考资料