前言

在日常的软件开发中，我们很少需要真正关心计算机的底层是如何工作的。编译器、操作系统以及各种高级抽象层为我们开发者提供了一个相对稳定而统一的接口，使得人们能够专注于算法与应用逻辑。然而，在这些抽象层之下，计算机本质上只是由大量简单电子元件构成的系统：电信号在导线中传播、逻辑门对信号进行运算、寄存器保存状态，而处理器按照既定规则执行指令。我们能否尝试回答一个看似简单但实际上非常深刻的问题：如果从最基础的逻辑电路开始，我们能否一步一步构建出一个完整的 CPU？为了回答这个问题，我们将暂时抛开操作系统、编译器以及复杂的体系结构，从最基本的数学与逻辑出发，逐步搭建计算机的核心组件。

首先，我们需要理解数字电路的数学基础。计算机内部所有的数据最终都以二进制形式表示，因此逻辑运算可以通过布尔代数或伽罗瓦域的运算进行描述。通过这些数学工具，可以形式化地分析逻辑函数以及电路行为。在此基础上，我们将构建最基本的逻辑门，例如与门、或门、非门以及异或门。这些逻辑门是数字电路的基本构件，通过组合这些简单的运算单元，可以实现任意布尔函数。

随后，我们将逐步构建更复杂的算术电路。例如，从半加器与全加器开始，构建多位加法器，并进一步实现算术逻辑单元（ALU）。ALU 是处理器中最核心的计算模块，它负责执行加法、减法以及各种逻辑运算。

在完成算术电路之后，我们将引入“状态”这一概念：通过锁存器和触发器，可以构建寄存器与计数器，从而使电路能够在不同的时钟周期之间保存数据。这一步是从纯组合电路迈向完整计算系统的关键。

最终，通过将寄存器、ALU、控制逻辑以及指令译码电路组合在一起，我们将得到一个能够执行指令序列的处理器。虽然这个处理器在功能上可能非常简单，但它已经包含了现代 CPU 的基本结构：数据通路、控制单元以及指令执行机制。

我开这个系列的目标并不是构建一个高性能处理器，而是通过从零开始构建 CPU 的过程，理解计算机体系结构最核心的思想。通过这种自底向上的方式，可以清晰地看到从数学、逻辑电路到处理器结构之间的联系。当我们真正理解这些基础之后，再回过头来看现代处理器中的复杂机制，例如流水线、乱序执行或缓存系统，就会发现这些复杂结构其实都是建立在同样简单的逻辑基础之上。

希望本系列文章能够帮助您以一种更加本质的视角理解计算机： 计算机并不是一个神秘的黑盒，而是由大量简单规则逐步构建而成的系统。

第一部分 算术逻辑单元

在现代计算机系统中，大部分数据处理操作都依赖于算术与逻辑运算。处理器在执行程序时，需要对二进制数据进行加法、减法等以及各种逻辑运算，这些运算均由算术逻辑单元（Arithmetic Logic Unit，简称 ALU）完成。因此，ALU 构成了处理器数据通路中的核心计算模块，其结构与实现方式直接决定了系统的运算能力。

从抽象层次上看，ALU 可以被视为一个将输入数据映射为输出结果的函数。设两个 位二进制操作数为，并具有如下的向量表示： 在控制信号的作用下，ALU 对输入数据执行某种运算，并产生输出向量 以及若干状态标志信号，例如进位标志、零标志和溢出标志等。不同的控制信号对应不同的运算功能，例如加法、减法或按位逻辑运算。

尽管 ALU 的功能看起来较为复杂，但从电路实现的角度来看，这些运算都可以通过基本逻辑门电路构造。逻辑门构成最基本的电路单元，而复杂的算术运算则是通过对这些基本单元进行组合而实现的。因此，理解 ALU 的实现过程，需要从最基本的逻辑运算开始。

在数学上，二进制逻辑运算可以通过布尔代数进行描述。布尔代数提供了一套形式化的代数结构，用于刻画逻辑变量之间的运算关系。在二值逻辑系统中，每一个变量只能取两个可能的值，即 与 。这些运算在结构上与伽罗瓦域 具有密切联系，因此可以利用代数方法对逻辑函数进行分析与化简。

在掌握布尔代数的基础上，可以进一步研究逻辑门电路的实现方式。逻辑门是数字电路中最基本的硬件单元，例如与门、或门、非门和异或门等。通过组合这些基本逻辑门，可以实现任意布尔函数，从而构造复杂的组合逻辑电路。

众所周知，现代计算机的 ALU整体是建立在逻辑电路理论的基础上的，因此，要搞清楚计算机的运算原理，就必须搞清楚逻辑电路原理。我们将从基本逻辑运算与抽象代数结构的角度出发，论证 ALU 的运算原理，并在必要位置给出严谨的数学证明。

第一章 基本逻辑门

在数字电路中，逻辑门是实现布尔运算的基本电路单元。每一个逻辑门都接收若干输入信号，并根据特定的逻辑规则产生输出信号。从抽象角度来看，逻辑门可以被视为一个函数，其输入与输出均取值于二值集合 其中通常表示逻辑假或低电平，而表示逻辑真或高电平。

设一个逻辑门具有个输入信号，则可以将其输入表示为一个向量 其中每个 。逻辑门根据内部实现的逻辑函数，将这些输入映射为输出信号，因此可以将逻辑门表示为函数 该函数称为布尔函数。换言之，一个具有个输入的逻辑门本质上实现了一个映射 称为逻辑门的扇入。不同类型的逻辑门对应不同的布尔函数，例如，与门实现逻辑与运算，或门实现逻辑或运算，而非门则实现逻辑取反运算。从电路结构上看，逻辑门的输入端通常连接到其他电路单元的输出端，而其输出端则作为后续电路的输入信号。因此，逻辑门可以通过导线相互连接，从而构成更复杂的逻辑电路。

在组合逻辑电路中，输出仅由当前输入决定；而在更复杂的时序电路中，输出还可能依赖于电路的历史状态。为了描述逻辑门在不同输入情况下的行为，通常使用真值表。真值表列出了所有可能输入组合及其对应的输出结果。例如，对于一个具有两个输入的逻辑门，其输入共有种可能的组合，因此真值表中需要列出四种情况。通过真值表，可以完整地描述逻辑门实现的布尔函数。

在本章中，我们将首先介绍几种最常见的基本逻辑门，包括与门、或门、非门以及异或门，并分析它们的逻辑性质。随后将讨论逻辑门之间的代数关系，以及如何通过组合这些基本门电路实现更复杂的逻辑函数。

1.1 非门（NOT Gate）

1.1.1 定义

非门又称反相器、，是最简单的逻辑门，仅具有一个输入端口和一个输出端口，其核心功能是实现逻辑非运算，即对输入信号进行取反：

• 输入为 (0) 时输出为 (1)
• 输入为 (1) 时输出为 (0)

在逻辑上，这等价于对命题取否定。

1.1.2 真值表

其中

1.1.3 运算表达式

也可表示为

1.1.4 实现

非门可通过晶体管（二极管、MOS管）实现，核心原理是利用晶体管的导通与截止状态对应逻辑 和 ：当输入为高电平（）时，晶体管导通，输出低电平（）；当输入为低电平（）时，晶体管截止，输出高电平（）。实际应用中，常用CMOS反相器，具有功耗低、抗干扰能力强的特点。下图是一种使用MOS管的非门：

1.2 与门（AND Gate）

1.2.1 定义

与门具有两个及以上输入端口和一个输出端口，核心功能是实现“逻辑与”运算，仅当所有输入信号均为 （真）时，输出才为 （真）；只要有一个输入为 （假），输出即为 （假），遵循“同时为真才为真”的逻辑。

1.2.2 真值表

对应表达式：

1.2.3 运算表达式

也可写为

1.2.4 实现

与门可通过二极管串联实现：两个二极管的阳极连接在一起作为输出端，阴极分别作为输入端口，电源通过电阻连接到输出端。当所有输入均为高电平（）时，二极管均截止，输出高电平（）；只要有一个输入为低电平（），对应二极管导通，输出被拉低为低电平（）。如下图：

实际应用中，常用CMOS与门，然而它不是由单级电路构成的。它实际上是将一个与非门和一个非门级联而成的。如下图：

1.3 或门（OR Gate）

1.3.1 定义

或门具有两个及以上输入端口和一个输出端口，核心功能是实现“逻辑或”运算，只要有一个输入信号为 （真），输出即为 （真）；仅当所有输入均为 （假）时，输出才为 （假），遵循“有一个为真即为真”的逻辑。

1.3.2 真值表

1.3.3 运算表达式

1.3.4 实现

或门可通过二极管并联实现：两个二极管的阴极连接在一起作为输出端，阳极分别作为输入端口，电源通过电阻连接到输出端。当有一个输入为高电平（）时，对应二极管导通，输出高电平（）；当所有输入均为低电平（）时，二极管均截止，输出低电平（）。如下图：

实际应用中，常用CMOS或门，由一个或非门加一个非门组成，与CMOS与门结构对称。如下图：

1.4 异或门（XOR Gate）

1.4.1 定义

异或门（Exclusive OR）具有两个及以上输入端口和一个输出端口，核心功能是实现“逻辑异或”运算，当输入信号“不同”时（一个为 ，一个为 ），输出为（真）；当输入信号“相同”时（均为 或均为 ），输出为（假）。异或运算在数电中应用极广。

1.4.2 真值表

1.4.3 运算表达式

异或运算可以由基本逻辑门组合实现：

1.5 同或门（XNOR Gate）

1.5.1 定义

同或门（Exclusive NOR）是异或门的反相，具有两个及以上输入端口和一个输出端口，核心功能是实现“逻辑同或”运算，当输入信号“相同”时（均为 或均为 ），输出为（真）；当输入信号“不同”时（一个为 ，一个为 ），输出为（假），与异或运算互为非运算。

1.5.2 真值表

1.5.3 运算表达式

其与异或关系为

第二章 逻辑运算的代数结构

逻辑变量取值集合为，该系统可用布尔代数描述。逻辑运算还可嵌入到伽罗瓦域的多项式结构中。在中只有两种基本运算：

• 加法

• 乘法

逻辑运算可通过如下映射关系，与伽罗瓦域中的运算对应，实现逻辑运算的代数化表示：

由此可见，逻辑非运算对应伽罗瓦域中“ 加变量”的运算，逻辑异或运算对应伽罗瓦域中的加法运算，逻辑与运算对应伽罗瓦域中的乘法运算。而逻辑或运算无法直接对应伽罗瓦域的基本运算，需通过上述映射关系推导得出，其多项式表示为

该表达式属于布尔环多项式表示，是逻辑或运算在伽罗瓦域 中的代数等价形式。

2.1 非运算性质

由逻辑非运算与伽罗瓦域 运算的映射关系，非运算可表示为

双重否定律

对逻辑变量 进行两次非运算，结果仍为 本身，即：

证：根据非运算的代数表达式，对 再次进行非运算，可将 整体代入公式，得到： 在伽罗瓦域 中，加法运算满足特殊性质：两个 相加的结果为 ，即

利用加法结合律，将上式中的优先计算，可得：

又因为在伽罗瓦域 中， 为加法单位元，满足 ，因此：

即 ，得证。

互补律

一个逻辑变量与其非变量的或运算结果恒为 ，与运算结果恒为 ，即：

证：结合非运算的代数表达式 和逻辑运算的伽罗瓦域映射关系，分别证明两个等式：

1. 证明 ：

由逻辑或的布尔环多项式表示 ，令 ，代入得：

展开右边多项式： 在伽罗瓦域 中， （异或运算自反性），且 （幂等性），代入化简：

故

2. 证明 ：

由逻辑与的映射关系 ，代入 ，得：

综上，互补律的两个等式均成立，得证。

2.2 与运算性质

逻辑与运算对应伽罗瓦域 中的乘法运算 ，因此其性质可由伽罗瓦域乘法的性质推导得出。

交换律

两个逻辑变量进行与运算时，交换变量顺序，结果不变，即：

证：由与运算与伽罗瓦域乘法的映射关系， ， 。

在伽罗瓦域 中，乘法运算满足交换律，即 ，因此

，得证。

结合律

三个及以上逻辑变量进行与运算时，改变运算顺序（添加括号），结果不变，即：

证：根据映射关系， ， 。

在伽罗瓦域 中，乘法运算满足结合律，即 ，因此

，得证。

幂等律

一个逻辑变量与自身进行与运算，结果仍为该变量本身，即：

证：由映射关系， 。

在伽罗瓦域 中，对于任意逻辑变量（取值为 或 ），均满足 （当时， ；当时， ），因此 ，得证。

单位元

一个逻辑变量与 进行与运算，结果仍为该变量本身，即：

证：由映射关系， 。

在伽罗瓦域 中， 是乘法单位元，满足 ，因此 ，得证。

零元

一个逻辑变量与 进行与运算，结果恒为 ，即：

证：由映射关系， 。

在伽罗瓦域 中， 是乘法零元，满足 ，因此

，得证。

吸收律

一个逻辑变量与该变量和另一个变量的或运算结果进行与运算，结果仍为该变量本身，即：

证：结合逻辑或的布尔环多项式表示 ，将其代入左边表达式：

展开多项式，利用伽罗瓦域乘法分配律：

由幂等性 ，代入化简：

在伽罗瓦域 中， ，因此：

即：

得证。

2.3 或运算性质

逻辑或运算并没有直接对应的伽罗瓦域基本运算，需借助其布尔环多项式表示 ，结合伽罗瓦域的运算性质，推导其各类性质。

交换律

两个逻辑变量进行或运算时，交换变量顺序，结果不变，即：

证：根据或运算的多项式表示， ， 。

在伽罗瓦域 中，加法满足交换律（ ），乘法满足交换律（ ），因此：

，即 ，得证。

分配律

一个逻辑变量与另外两个变量的或运算结果进行与运算，等价于该变量分别与两个变量进行与运算后，再进行或运算，即：

证：分别对等式左右两边进行代数化简，验证其等价性。

1. 化简左边 ：

代入或运算多项式表示，结合与运算映射关系，得：

2. 化简右边 ：

先计算 ， ，再代入或运算多项式表示：

由幂等性 ，化简得：

，得证。

2.4 德摩根定律

德摩根定律揭示了非运算和与、或运算之间的反向关系，可将与运算的非运算转化为非运算的或运算，或将或运算的非运算转化为非运算的与运算：

证：此处以第一个等式 为例，结合伽罗瓦域运算和逻辑映射关系证明，第二个等式可同理推导。

1. 化简左边 ：

由与运算映射关系 ，结合非运算表达式 ，令 ，得：

2. 化简右边 ：

先由非运算表达式得出 ， ，再代入或运算多项式表示：

展开右边多项式，利用伽罗瓦域运算性质化简：

代入原式并合并同类项：

在伽罗瓦域 中， 、 、 ，因此：

左边 与右边化简结果一致，故 ，得证。

同理，可证明 ，此处不再赘述。

2.5 异或运算性质

由前文映射关系可知，逻辑异或运算直接对应伽罗瓦域 中的加法运算，即

由于伽罗瓦域 中的加法运算满足阿贝尔群的所有条件（交换律、结合律、单位元存在、逆元存在），因此集合

构成阿贝尔群（交换群），其各项性质均可由伽罗瓦域加法性质推导得出。

交换律

两个逻辑变量进行异或运算时，交换变量顺序，结果不变，即：

证：由异或与伽罗瓦域加法的映射关系， ， 。

在伽罗瓦域 中，加法运算满足交换律，即 ，因此有：

得证。

结合律

三个及以上逻辑变量进行异或运算时，改变运算顺序（添加括号），结果不变，即：

证：由映射关系， ， 。

在伽罗瓦域 中，加法运算满足结合律，即 ，因此有：

得证。

单位元

一个逻辑变量与 进行异或运算，结果仍为该变量本身，即：

证：由映射关系， 。

在伽罗瓦域 中，0是加法单位元，满足 ，因此有：

得证。

逆元

一个逻辑变量与自身进行异或运算，结果为单位元 ，即：

证：由映射关系， 。

在伽罗瓦域 中，任意元素与自身相加的结果为 ，即 ，因此有：

得证。

反转性质

一个逻辑变量与1进行异或运算，结果等价于该变量的非运算，即：

证：由映射关系， 。

由非运算的代数表达式可知， ，而伽罗瓦域加法满足交换律，因此有：

得证。

奇偶校验性质

多个逻辑变量的异或运算结果，等价于所有变量取值之和对 取模，即：

若参与运算的变量中，取值为 的个数为奇数，则异或结果为 ；若为偶数，则结果为 。

证：采用数学归纳法证明，结合异或运算与伽罗瓦域加法的等价性（ ）。

1. 当时， ， ，等式成立；

2. 假设当（）时，等式成立，即： 当时，有： 由归纳假设和映射关系： 因此，当时，等式仍成立。

综上，对任意正整数，等式均成立，得证。

2.6 同或运算性质

同或运算定义为异或运算的非运算，即

结合异或运算与伽罗瓦域加法的映射关系（ ）和非运算的代数表达式（ ），同或运算可进一步表示为

交换律

两个逻辑变量进行同或运算时，交换变量顺序，结果不变，即：

证：根据同或运算的代数表达式 ， 。

在伽罗瓦域 中，加法满足交换律（ ），因此：

，即 ，得证。

结合律

三个及以上逻辑变量进行同或运算时，改变运算顺序（添加括号），结果不变，即：

证：

左边：

将括号内的 展开：

利用异或与取反的性质：

因此：

于是得到：

右边：

将括号内的 展开：

利用异或与取反的性质：

于是：

因此：

得证。

自反性质

一个逻辑变量与自身进行同或运算，结果恒为 ，即：

证：将 代入同或运算的代数表达式，得： 在伽罗瓦域 中， ，因此 ，即 ，得证。

第三章 加法器

在现代计算机体系结构中，加法运算是最基本的算术运算之一。几乎所有复杂算术操作，例如减法、乘法、除法以及地址计算等，都可以归结为若干次加法运算的组合。例如，减法可以通过补码表示转化为加法；乘法通常通过移位与加法的组合实现；除法可以通过迭代减法或恢复算法实现；而在处理器执行内存访问时，地址的计算通常表现为基址与偏移量之间的加法运算。因此，在计算机硬件层面，实现高效可靠的加法运算是算术逻辑单元设计的核心问题之一。

在数字电路中，所有数据均以二进制形式表示。第二章已经讲过，二进制数的每一位仅可能取 或 ，因此其运算规则可以完全用布尔代数来描述，且布尔代数与伽罗瓦域 之间存在严格的代数对应关系，其中逻辑与运算对应于伽罗瓦域中的乘法运算，而逻辑异或运算则对应于伽罗瓦域中的加法运算。利用这一映射关系，可以将二进制加法转化为布尔多项式运算，从而为数字电路设计提供严格的数学基础。本章首先分析实现一位加法的最基本逻辑单元——半加器，然后进一步引入来自低位的进位输入，研究全加器的结构，并推导多位加法器的进位传播规律。

3.1 半加器

半加器是实现两个一位二进制数相加的最基本逻辑电路。设两个输入变量 在执行加法运算时，结果可能包含两个部分，其中一部分是当前位的结果，称为本位和（Sum），另一部分是当运算结果超过 1 时产生的高位进位，称为进位（Carry）。

因此，一位加法可以表示为一个映射： 其中 表示当前位的计算结果，而 表示向高位产生的进位。

下面我们来推导 与 的代数表达式。

3.1.1 本位和

根据二进制加法规则可以得到本位和 的取值规律：当两个输入变量均为 时，结果为 ；当其中恰有一个为 时，结果为 ；而当两个输入同时为 时，由于产生进位，本位结果重新变为 。这一规律说明，本位和为 的情况恰好出现在两个输入取值不同的情形，而当两个输入相同时结果为 。这一性质与逻辑异或运算的定义完全一致。通过上述穷举，我们可以将本位和 看作两个输入变量作异或运算的结果。

从代数的角度看，第二章已经证明，异或运算可以映射到伽罗瓦域中的加法运算，即： 因此，一位二进制加法的本位和可以表示为： 这一公式表明，本位和的计算仅需要一个异或门即可完成。

3.1.2 进位

根据二进制加法规则，仅当两个输入变量同时为 时才会产生进位。例如： 在这一运算中，最低位结果为 ，而高位产生进位 。若任一输入变量为 ，则运算结果不会产生进位。这一条件又和逻辑与运算的定义完全一致。在第二章中，我们已经给出逻辑与运算与伽罗瓦域乘法之间的对应关系：

其中右侧表示伽罗瓦域中的乘法运算。因此进位可以表示为：

从代数角度看，这说明进位实际上由乘法项决定。当两个输入变量均为 时，其乘积为 ，从而产生进位；只要其中任意一个变量为 ，乘积便为 ，因此不会产生进位。

综合以上分析可以得到，半加器的逻辑结构完全由两个基本逻辑运算决定，因此半加器电路只需要两个基本逻辑门：一个异或门用于计算本位和，一个与门用于计算进位。因此，我们可以得到半加器的逻辑电路图：

简记为：

需要注意的是，半加器只能处理两个输入变量的加法运算，而在实际的多位加法中，每一位运算还可能接收到来自低位的进位信号。因此在实际处理器中，需要使用更一般的加法单元——全加器。

3.2 全加器

在多位二进制加法运算中，每一位的计算不仅依赖当前位的两个输入，还依赖来自低位的进位信号。因此，在第 位执行加法运算时，需要考虑三个输入变量： 其中 表示第一个加数在第 位的值， 表示第二个加数在第 位的值，而 表示来自第 位的进位。

该运算单元产生两个输出，其中 表示当前位的结果，而 表示向更高位传播的进位。能够同时处理两个输入位和一个进位输入的加法单元称为全加器。

3.2.1 全加器的进位

我们现在先不关心全加器和半加器的具体联系，暂且将其看作是半加器的多输入推广。要将半加器推广到三个输入，其核心问题是推导进位信号在各个位之间传播的数学表达式。在现代处理器设计中，全加器不仅用于构建最简单的串行进位加法器，还为更高速的结构，例如超前进位加法器，提供理论基础。因此，对全加器进位关系的严格数学推导具有重要意义。

易知，产生进位存在两种情况。第一种情况是当前位的两个输入变量直接产生进位，此时有： 该信号称为生成信号（Generate）。第二种情况是当前位允许低位的进位向高位传播，此时定义传播信号： 若此时存在输入进位 ，则该进位会被传播到更高位。

因此进位的逻辑表达式为： 由式，令 得： 对第三项进行分配律展开： 由式及式，得： 由于交叉项恒为 0，进位多项式坍缩为纯加法形式： 此即全加器的基本进位关系。

我们从式的形式中观察到，多项式的第一项与半加器的进位数的表达式在形式上完全一致，而在第二项中，令 代入，得到： 此处的在形式上与半加器的本位和同样完全一致。由此可见，我们可以将全加器看作两个半加器以及一个与门的组合，建立下图所示的等效电路：

下面我们从数学归纳法出发，给出式的另一种证明方式。