What Every Programmer Should Know Computer 002

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

复杂门电路的重要设计思想:Design small circuits to be used in a bigger circuit。

加法器

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

半加器

ABA+BXORAND
000000
010110
100110
111001

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

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

全加器

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

ABCCarry(进位)Sum(和)
00000
00101
01001
10001
01110
10110
11010
11111

电路组件示意图如下:

全加器逻辑上可以由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)的优化思路就是"能否提前计算出「进位输出信号」?".

超前进位加法器

对于每一位全加器的输入: ci1c_{i-1}, aia_i ,bib_i 和输出 sis_i,cic_i 有以下公式.

si=aibicis_i = a_i \oplus b_i \oplus c_i

ci+1=aibi+ci(aibi)c_{i+1} = a_i b_i + c_i \oplus ( a_i \oplus b_i )

其中,

  • aba \oplus b 表示 a异或b
  • abab 表示 a与b
  • a+ba+b 表示 a或b

假设我们有如下定义:

Pi=aibiP_i = a_i \oplus b_i

Gi=aibiG_i = a_i b_i

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

si=Pici,i=0...N1s_i = P_i \oplus c_{i} , i= 0...N-1

ci+1=Gi+Pici,i=0...N1c_{i+1} = G_i + P_i c_i , i= 0...N-1

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

c1=G0+P0c0c_1 = G_0 + P_0 c_0

c2=G1+P1c1=G1+P1(G0+P0c0)=G1+G0P1+P1P0c0c_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

c3=G2+P2c2=G2+G1P2+G0P2P1+P2P1P0c0c_3 = G_2 + P_2 c_2 = G_2 +G_1P_2+G_0P_2P_1+P_2P_1P_0c_0

c4=G3+P3c3=G3+G2P3+G1P3P2+G0P3P2P1+P3P2P1P0c0c_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

s0=P0c0s_0=P_0 \oplus c_0

s1=P1c1s_1=P_1 \oplus c_1

s2=P2c2s_2=P_2 \oplus c_2

s3=P3c3s_3=P_3 \oplus c_3

可以发现,c4c_4s0s_0~ s3s_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(开关)

Enabler有两个输入:

  • 开关(标识着开启和关闭,1bit)
  • data(数据部分,可能是多个bit)

当开关开启时,输出是data;当开关关闭时,输出为0。

Decoder(解码器)

解码器的作用是将编码后的二进制值解码为一组独立的位,是一种具有N路输入和 2N2^N 路输出的复杂门电路。最小的解码器是1线-2线解码器:

下图是2线-4线Decoder的电路图。

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

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

解码器还包括3线-8线解码器或4线-16线解码器等等。我们可以通过小的解码器去组合成大解码器。下图通过两个1线-2线解码器组成2线-4线解码器。

当然,我们也可以使用一个1线-2线解码器和一个2线-4线解码器以及一些门电路元件组成3-8线解码器。

一种通用的电路设计方案是: 在有使能信号输入的情况下,2个2线-4线解码器可以组成1个3线-8线解码器,同样,2个3线-8线解码器可以组成1个4线-16线解码器。

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

Encoder(解码器)

编码器是一种能将多个二进制输入压缩成更少数目输出的电路。encoder和decoder的输入输出刚好相反。简单编码器电路可以接受 2n2^n 条中的一个有效输入,并在n条并行输出线上生成一个二进制码。

例如,下图是4线-2线编码器的真值表:

I3I2I1I0O1O0
000100
001001
010010
100011

我们可以用两个或门实现4线-2线编码器:

O1=I3+I2O1 = I3+I2

O0=I3+I1O0 = I3+I1

上面描述的编码器被称为简单编码器,它仍有不少局限性:

  1. 普通编码器的输入端只能同时存在一个高电平信号,当我们不小心输入了多个高电平信号,就会得到错误的结果。
  2. 如果想设计8线-3线编码器,当前的4线-2线编码器并不能派上用场,不符合门电路模块化和层次化的设计思想。

因此产生了一种新的编码器设计,解决了上述的局限性,这种编码也被称为优先编码器。4线-2线编码器的真值表如下:

I3I2I1I0O1O0v
0000xx0
0001001
001x011
01xx101
1xxx111

如果同时有两个或以上的输入作用于优先编码器,优先级最高的输入将会被优先输出。上表中最高优先级的输入在表左侧,而x代表无关项,即可是1也可是0,不论无关项的值是什么,都不影响输出,只有最高优先级的输入有变化时,输出才会改变。v输出指示输入是否有效,该输出用于构建更大的编码器。

Multiplexer(多路复用器)

多路复用器,也称为数据选择器,用于从 2N2^N 个输入信号中通过N个选择行选择一个信号用于输出。多路复用器的基本功能:将多个输入组合成一个数据流。例如下图是一个 2-1 多路复用器。

参考资料