数字模块

本文将基于前几篇文章关于组合逻辑电路和时序逻辑电路的描述，以及前文介绍的计算机数值系统，介绍常见的组合电路和时序电路模块，包括算术电路、计数器、移位寄存器、存储器阵列等，探究电路是如何处理计算机数据的。

1.1 加法器

1.1.1 半加器（half adder）

半加器接受两个1 bit的输入值`A`和`B`，输出1 bit它们相加的和`S`和1 bit进位值`C_(out)`。半加器可以由一个异或门(XOR)和一个与门实现，具体实现和真值表如下所示。（备注：异或门布尔表达式为 `F=A\oplusB=A'B+AB'`，对于n个异或操作 `F=A_1\oplusA_2\oplus...\oplusA_n`，当输入1的个数为奇数个时，输出才为TRUE。）

`S=A\oplusB`
`C_(out)=AB`

半加器真值表
`A`	`B`	`C_(out)`	`S`
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

1.1.2 全加器（full adder）

相比于半加器，全加器多了一个进位输入`C_(i n)`，以便于构建多位加法器，如上图所示。其真值表和相应布尔表达式如下所示。

`S=A\oplusB\oplusC_(i n)`
`C_(out)=AB+AC_(i n)+BC_(i n)`

全加器真值表
`C_(i n)`	`A`	`B`	`C_(out)`	`S`
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

1.1.3 进位传播加法器(Carry Propagate Adder, CPA)

N位加法器接收两个N位的输入`A`和`B`，和一个进位值`C_(i n)`，产生一个N位的结果`S`和一个输出进位`C_(out)`，由于1位进位要传播到下一位中，因此这种加法器也被称为进位传播加法器(Carry Propagate Adder, CPA)。

(1) 行波进位加法器

构建N位进位传播加法器最简单的办法就是串联N个全加器，如上图所示，这被称为行波进位加法器 (Ripple-carry Adder)。行波进位加法器的缺点是当N比较大时，电路计算的延迟也会变大。设`t_(FA)`是单级全加器的延迟，则含有N级全加器的行波进位加法器的延迟为`t_(r i p p l e)=Nt_(FA)`。

(2) 先行进位加法器

    造成行波进位加法器计算延迟过高的原因是进位信号必须逐位计算推进。因此工程师们开始考虑在行波进位加法器的基础上添加独立电路，以加快进位信号的计算，这就有了先行进位加法器(Carry-Lookahead Adder)。要构造产生进位信号的独立电路，首先我们必须推导出单独一列的进位信号输出的布尔表达式。在第i位，进位信号 `C_i` 当且仅当在以下两种情况为1：
    1. 当输入 `A_i` 和输入 `B_i` 都为1时；
    2. 当前一位的进位 `C_(i-1)` 为1，且输入 `A_i` 或输入 `B_i` 为1时。
    因此我们可以得到：`C_i=A_i\cdotB_i+C_(i-1)\cdot(A_i+B_i)`。当属于上述第一种情况时，我们说第i位产生了进位，并用 `P_i` 代替表示 `A_i\cdotB_i`，即`P_i=A_i\cdotB_i`；当属于上述第二种情况时，我们说第i位传播了进位，并用 `G_i` 代替表示 `A_i+B_i`，即`G_i=A_i+B_i`。因此进位信号 `C_i` 的布尔表达式可以化简为：`C_i=G_i+C_(i-1)\cdotP_i`。
    分析完单独一列的进位信号布尔表达式，下面我们基于此开始分析连续几列的进位信号输出的布尔表达式，注意下面我们称一个能计算连续几列的加法器为一个CLA块。与上面道理类似，以第3列到第0列的CLA块为例，其进位信号 `C_(3:0)` 当且仅当在以下两种情况为1：
    1. CLA块产生进位：最高有效列产生了一个进位，或者最高有效列传播了前面的列产生的进位，即：
        `G_(3:0)=\underbrace{G_3}_{最高有效列产生进位}+P_3\underbrace{(G_2+P_2(G_1+P_1G_0))}_{前面几列产生进位}`
    2. CLA块传播进位：CLA块中的所有列都能传输输入进位信号，即：
        `P_(3:0)=P_3P_2P_1P_0`
    因此，我们可以得到，第3列到第0列的四位CLA块的进位信号输出布尔表达式为：
        `C_(3:0)=G_(3:0)+C_(0)\cdotP_(3:0)`
    扩展到一般情况，即：
        `C_(i:j)=G_(i:j)+C_(j)\cdotP_(i:j)`
    综上，我们得到了一个四位CLA块的进位信号输出的布尔表达式。注意CLA块同时计算加法和进位信号，进位信号的加速计算，使得下一个CLA块能够更快地进行计算，下面给出一个32位先行进位加法器的例子，注意最后一个CLA块可以只是一个短的4位行波进位加法器。

1.2 减法器

在数值系统一节中，我们知道了计算机实现二进制减法的原理是采用补码的形式利用加法器实现的，即:

`A-B=A+f_(补码)(B)`

因此，当我们使用电路来处理减法时，可以通过先使用电路将减数转化为补码形式，然后再与被减数相加的形式来实现，具体的实现形式如下所示。注意到将减数`B`转化为补码的方式采用的是先转化为反码再加1的方法实现的，“反转”操作使用非门实现，“加1”操作通过在加法器的进位输入 `C_(i n)` 上输入1实现。

1.3 比较器

(1) 相等比较器(equality comparator)

相等比较器用于比较两个二进制数是否相等，如上图所示，其原理是使用同或门(XNOR)和与门判断两个二进制数每一位是否相等。

(2) 量值比较器(magnitude comparator)

量值比较器用于比较两个数的大小，如上图所示，其原理是使用减法电路得到差值后，判断最高位符号位，若为1则`A < B`，否则`A \geq B`。

1.4 算术逻辑单元 (Arithmetic/Logic Unit, ALU)

ALU运算
`F_(2:0)`	功能	`F_(2:0)`	功能
`000`	`A` AND `B`	`001`	`A` OR `B`
`010`	`A` + `B`	`011`	Not Used
`100`	`A` AND `\bar{B}`	`101`	`A` OR `\bar{B}`
`110`	`A` - `B`	`111`	SLT (运行 S = A − B，如果 A < B (S 的符号位为 1)，则提取 S 的符号为，并且扩展为 N 位数进行输出)

如上所示是一个基本的 ALU 的基本设计，其接受两个 `N` 位的数，输出一个 `N` 位的数，通过调节 `F[2:0]` 来选择其功能。结合图表可以推理具体功能的实现方式，此处不再赘述。

有些 ALU 设计还会在做运算之后有额外的输出，称为 flags，比如 overflow flag、zero flag 等。

1.5 Shifter (移位器) 和 Rotator (循环移位器)

顾名思义，Shifter 用于对一个数进行移位操作，Shifter 可以分为两类：Logical Shifter (逻辑移位器) 和 Arithmetic Shifter (算术移位器)。

对于 Logical Shifter 来说，它就是简单的把二进制数向左 (LSL) 或者向右 (LSR) 移动，并且使用 0 来填充空出来的比特位。比如: 11001 LSR 2 = 00110、11001 LSL 2 = 00100。

而对于 Arithmetic Shifter，在把二进制向右移动 (ASR) 时则是以拷贝最高位 (i.e. 符号位) 来填充空出来的比特位的方式进行移动，而对于向左移动 (ASL) 则照常，比如: 11001 ASR 2 = 11110、11001 ASL 2 = 00100。

左移位 (LSL/ASL) 是一种特殊的乘法，一个数左移 `N` 位相当于乘以 `2^N`; 算术右移位 (ASR) 是一种特殊的除法，一个数右移 `N` 位相当于除以 `2^N`。

而对于一种特殊的移位器 —— Rotator 来说，它则会在移动时空出来的比特位上按顺序填充被移出的比特位，即循环移位。11001 ROR 2 = 01110、11001 ROL 2 = 00111。

如上图所示，分别是左移位 (<<)、右逻辑移位 (>>) 和右算术移位 (>>>) 的实现原理。

2.1 计数器 (Counter)

如上图所示是一个 N-bits Counter 的基本设计原理，由一个加法器和一个带 Reset 信号的寄存器构成。

2.2 移位寄存器 (Shift Register)

如上图所示是一个移位寄存器的基本设计，它有一个串行输入 `S_{in}`，一个串行输出 `S_{out}`，一个 `N` 位并行输出 `Q_{N-1:0}` 和一个时钟信号组成。事实上可以把移位寄存器理解为一个 serial-to-parallel converter，每一个时钟周期的上升沿到来时，它都会把之前接受到的比特位向后进行移位。

移位寄存器可以被改造为如下形态以同时支持 serial-to-parallel converter 和 parallel-to-serial converter 的功能。当 Load 信号被使能时，它充当的是 parallel-to-serial converter，反之则是 serial-to-parallel converter。

1. David Money Harris, Sarah L, Harris, 机械工业出版社, 数字设计和计算机体系结构

Zobin

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Feb.11 2021

1. 组合逻辑算术电路