整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L12 注解幻灯片。

源网页：12.1 Annotated Slides | Procedures and Stacks

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L12：过程与栈（Procedures and Stacks）

本讲讲清过程（procedure）抽象为何需要激活记录（activation record），以及为何 LIFO 栈能自然支持嵌套与递归；随后给出 Beta 上的 SP/LP/BP 约定、栈帧布局、callee-saves 契约，并用阶乘与“栈侦探”题目串起整套调用约定。

1. 过程：软件抽象（Procedures: A Software Abstraction）

过程/子程序：完成特定任务的指令序列，有唯一命名入口。可有形式参数（formal parameters）；调用时实参（arguments）与之对应。过程体可定义仅在执行期间存在的局部变量；可返回值，也可只为副作用而执行。

例：COPRIMES 只需知道 GCD 的入参/返回类型即可调用——实现被封装成黑盒。标准库提供大量预建过程（数学、容器、文件等）。过程抽象是高级语言表达力的核心。

2. 实现过程（Implementing Procedures）

两种思路：

1. 内联（inline）：用过程体副本替换调用，实参代入形参（类似宏）。短过程有时值得；长过程多次调用会膨胀代码。递归在编译期无法终止展开 → 内联失败。
2. 链接（link）：过程代码只保留一份；调用方求实参、存约定位置，BR 到入口并保存返回地址（return address）；过程算完把结果放约定位置，再 JMP 回返回地址。

3. 过程调用约定（Procedure Calling Convention）

需约定：实参放哪、返回值放哪。可尝试用寄存器：如 R1 起传参、R28 存返回地址（linkage pointer）、R0 返回值。BR/JMP 正好对应 call/return。

目标：所有调用与过程体用同一约定——含递归 fact(n-1) 与顶层 fact(3)。

4. 过程链接：初试（Procedure Linkage: First Try）

按上述约定编译 fact()：入参进 R1，BR 保存返回地址到 R28；递归时又把 n-1 写入 R1、新返回地址写入 R28——覆盖外层还需要的 n 与返回地址。深度为 $d$ 时需要约 $2d$ 个存储槽，寄存器不够。禁止递归可绕过，但语言通常允许递归 → 必须动态为每次活跃调用分配存储。

5. 过程的存储需求（Procedure Storage Needs）

每次活跃调用需要：实参、返回地址、返回值、局部变量、以及调用方寄存器现场。不想限制参数/局部变量个数 → 每次调用一块存储，即激活记录。不能静态只为某过程留一块（递归有多份同时活跃）→ 调用时分配、返回时回收。

6. 激活记录（Activation Records）

fact(3)→fact(2)→fact(1)→fact(0)：每层调用创建自己的激活记录；嵌套调用返回后其记录先丢弃。LIFO：被调方记录总在调用方之前释放——调用方必须等被调返回才能结束。需要高效支持这种分配/释放的结构。

7. 洞察：需要栈！（Insight: We Need a Stack!）

激活记录按 LIFO 进出 → 栈（stack）：PUSH 加顶、POP 去顶。C 过程通常只访问栈顶记录；Java 等可访问其他活跃帧。闭包 / continuation（如 Python yield）需在返回后仍保留帧 → 纯栈不够，属更高级课程话题。

8. 栈实现（Stack Implementation）

Beta：专用 R29 = SP（stack pointer）。PUSH 时递增 SP，栈向高地址生长。约定：SP 指向下一个未用字；低于 SP 的地址是已分配内容。

栈纪律（stack discipline）：一段代码 PUSH 的内容必须在结束前 POP 掉，使 SP 恢复原值。栈放在大块内存区，系统常设最大栈长，溢出报错。Beta 用现有指令实现栈，纯软件约定；有的 ISA 有专用栈指令。

9. 栈管理宏（Stack Management Macros）

UASM 宏：

• PUSH：先 ADDC 分配栈顶，再 ST 初始化（顺序重要：中断可能夹在两指令之间；先分配再写更安全）
• POP：先 LD 取值，再 SUBC 释放
• ALLOCATE / DEALLOCATE：预留/释放 $N$ 个字（不必初始化）

见 PUSH/ALLOCATE 应能找到配对的 POP/DEALLOCATE。

10. 玩转栈（Fun With Stacks）

临时占用寄存器前可 PUSH 旧值，用完按相反顺序 POP 恢复（LIFO）。有了栈，即可解决激活记录的分配/释放问题。

11. 解决过程链接问题（Solving Procedure Linkage Problems）

栈上放激活记录：实参、局部变量、以及保存的 LP（以便嵌套调用）。职责分摊：

• 调用方（caller）：求实参并逆序 PUSH（第一实参最后压栈）；BR 到入口，返回地址进 LP=R28；返回后 DEALLOCATE 去掉实参。
• 被调方完成帧的其余部分（下页）。

逆序原因后文说明（可变参数）。

12. 栈帧作激活记录（Stack Frames as Activation Records）

入口序列完成帧（也称 stack frame）：保存 LP；再保存调用方的 BP=R27，并用当前 SP 设本帧 BP；ALLOCATE 局部变量；再 PUSH 本过程将破坏的寄存器（callee saves：除 R0 外寄存器跨调用保持）。

有了 BP，帧内访问用相对 BP 的固定偏移，比相对 SP 更稳（SP 会随 PUSH/POP 变）。

13. 栈帧细节（Stack Frame Details）

回到问题：为何实参逆序压栈？

14. 实参顺序与 BP（Argument Order & BP Usage）

逆序后，第一实参（arg 0）相对 BP 偏移固定（如 $-12$），与共压几个实参无关；第二参 $-16$…… C 的可变参数（如 printf：格式串在第一个实参）依赖这一点。局部变量亦固定偏移：第一局部 $0$，第二 $+4$…… 帧上更高地址可用于嵌套调用建新帧。

15. 过程链接契约（Procedure Linkage: The Contract）

Caller：逆序压实参 → BR 到入口（返回地址→LP）→ 返回后卸掉实参。

Callee：计算结果放 R0 → JMP 返回地址 → 卸掉自己压上的内容，栈恢复入口时模样 → 除 R0 外保持所有寄存器。

16. 过程链接模板（Procedure Linkage Templates）

入口：保存 LP、BP；MOVE(SP,BP)；ALLOCATE 局部；PUSH 将用寄存器。出口：按相反顺序 POP 恢复；MOVE(BP,SP) 隐式撤销 ALLOCATE；最后 JMP(LP) 回调用方。

17. 综合：阶乘（Putting It All Together: Factorial）

C 版 fact 的编译结果：入口/出口序列清晰；嵌套调用栈上传参并在返回后 DEALLOCATE；体用上讲模板。链接开销约十余条指令；对极短非递归过程，优化器可能选择内联。

18. 递归？（Recursion?）

已解决：每次调用新栈帧；返回按逆序释放。沿 BP 链可读出活跃调用、实参、局部变量 → stack trace（运行时出错时常打印）。能解读栈帧 ≈ 理解调用约定（测验常见题）。

19. 栈侦探（Stack Detective）

练习：已知 PC=0x40、栈转储，推断：

• 当前 fact 实参为 3；沿保存的 BP/LP 找到原始调用实参为 6
• 原始调用的 BR 在 0x7C（保存的 LP=0x80 为下一指令）
• 即将执行的是 DEALLOCATE(1)（递归返回后的指令）
• BP 等可由帧布局与十六进制地址推出

关键：会读帧布局、十六进制算术、区分递归返回地址与外部返回地址。

20. 专用寄存器小结（Summary of Dedicated Registers）

21. 小结（Summary）

激活记录由 caller/callee 共同建造，返回时丢弃；含实参、保存的 LP/BP、其他被保存寄存器、局部变量。BP 指向当前帧；callee saves（除 R0）保证嵌套与递归安全。至此可编译并执行任意 C 程序（在约定意义下）。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L11 注解幻灯片。

源网页：11.1 Annotated Slides | Compilers

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L11：编译器（Compilers）

本讲从高级语言出发，对比解释（interpretation）与编译（compilation），再用递归下降模板把 C 表达式/语句翻译成 Beta 汇编；随后拆解现代编译器前端（词法/语法/语义）、中间表示（IR / CFG）与多遍优化，最后做代码生成。

1. 编程语言（Programming Languages）

已学 Beta ISA：对寄存器中的 32 位数据做 datapath 操作，并访存、改 PC；指令由 opcode / 源 / 目的等字段组成 32 位字。汇编一句对应一条指令，程序员自己管寄存器与主存，并把数组访问等拆成 Beta 操作序列。

高级语言用变量与数据结构抽象存储与搬移；用表达式与赋值 = 等紧凑描述本需大量汇编的计算。本讲核心：如何把高级语言程序翻译成可在 Beta 上运行的代码。

2. 高级语言（High-Level Languages）

以欧几里得求 GCD 的 C 代码为例；课程用 C 的简单子集作示例语言。C 由 Dennis Ritchie 在 AT&T Bell Labs 为 Unix 而开发；此后语言不断加入 OOP、新数据结构与控制结构。

用高级语言可不提寄存器、具体指令等 ISA 细节 → 写得更快、更易读、更易维护；类型检查可拦下把字符串赋给数值变量等错误；动态分配等可自动化。因抽象掉具体 ISA，同一源码可移植到不同机器。代价取决于执行策略：解释还是编译。

3. 解释（Interpretation）

在真实机器 M1 上跑解释器，模拟易编程的抽象机 M2：每条 M2 操作由一段 M1 指令序列实现。解释器 + M1 ≡ M2 的一种实现。

常见多层解释：笔记本 x86 跑 Python 解释器 → 加载 SciPy → 一条 SciPy 命令展开为大量 Python 语句 → 每条 Python 再变成数百条 x86。适合一次性计算或探索算法；不必手写全部机器指令。

4. 编译（Compilation）

对需反复执行、愿付前期成本的任务用编译：把高级程序 P2 逐语句翻译成 M1 上的等价程序 P1（并不在翻译时“跑”P2）。做翻译的程序叫编译器（compiler）。

编译一次得 P1，之后直接跑 P1，避免运行时解析源码与多层解释开销。换不同编译器可把同一 P2 落到 M2、M3… 而不改写源码。解释与编译都能改源码、抽象真实机器，且在现代系统中并存。

5. 解释 vs. 编译（Interpretation vs. Compilation）

对语句 x+2：解释器处理时立刻取 x 并加 2；编译器则生成 LD/ADD 等指令，留待以后执行。循环中解释器会反复处理同一语句；编译器只生成指令一次。

一般编译代码快得多；解释器可按 x 的实际类型改变行为。

6. 编译器（Compilers）

编译器：把高级语言程序翻译成功能等价的机器指令序列（汇编）。先检查良构性：语句是否合法、有无无意义的运算（字符串+整数）、未初始化就用等；并警告浮点转整型可能溢出等。

通过检查后生成高效指令，常重排计算使序列更短更快。现代优化编译器耐心探索替代方案，往往难被手写汇编全面超越。本节先看简单编译策略，再看现代编译器结构。

7. 简单编译策略（A Simple Compilation Strategy）

两主例程：compile_statement 与 compile_expr。源程序是语句序列，反复调前者。关注四类语句：无条件（求一次表达式）、复合（顺序执行子语句）、条件（if：测表达式真则执行 then）、以及迭代（后文 WHILE）。

compile_expr：生成求值表达式并把结果放在某寄存器的代码。表达式含常量、标量/数组变量、赋值、一元/二元运算、过程调用等。复杂算术可拆成一元/二元序列。过程调用留待下讲；其余表达式与语句可直接模板化。

8. compile_expr(expr) → Rx

• 小常量（$-32768\sim +32767$）：CMOVE 符号扩展进寄存器；过大则存主存再 LD。
• 变量：与大常量类似，LD 对应地址。
• 数组访问：元素连续存放；先 compile_expr 得下标于 Rx，再乘元素字节数 bsize（如 int 为 4）得字节偏移，LD 基址+偏移取元素。
• 赋值：compile_expr 得右值，再 ST 到左值变量。
• 算术：分别编译操作数到寄存器，再生成对应 ALU 指令。

9. 编译表达式（Compiling Expressions）

例：含减、乘、加的赋值。按赋值模板递归编译 RHS；遇乘则再编译左操作数（减）……直至叶节点（变量/常量）生成 LD/CMOVE，再沿表达式树上返回生成 SUB/MUL/ADD 等。

此即递归下降（recursive descent）：每层表达式更简单，直到叶。相邻指令还可做窥孔优化（peephole）：如 CMOVE 后跟算术常可合并为带常量操作数的单条指令。

10. compile_statement

• 无条件语句：多为赋值或过程调用 → 交给 compile_expr。
• 复合语句：对每个子语句递归 compile_statement；生成代码首尾相接，顺序执行。

11. compile_statement：条件（Conditional）

最简 if：编译 test；若寄存器为 FALSE，分支跳过 THEN 子句代码。完整 if–else 用分支与标签保证：真走 then，假走 else，最后汇合。

编译本质：套用许多小模板，逐步把代码生成拆成更小任务，并用分支把碎片粘成正确控制流。

12. compile_statement：迭代（Iteration）

while 模板类似 if，末尾再分支回测表达式，直到为假。可重组使每轮只需一条 BT（原模板每轮 BF+BR），循环内小优化可累积为大收益。

for 可改写成带更新的 while，再套上述模板。

13. 综合：阶乘（Putting It All Together: Factorial）

把模板套到迭代版阶乘：生成代码可与前述模板一一对应。非最优，但递归下降已够用。

14. 优化：值留在寄存器（Optimization: keep values in regs）

让变量住在专用寄存器而非主存，可少掉大量 LD/ST。例：循环内指令从 10 条减到 4。优化编译器擅长找此类机会。下文改谈更一般的现代编译器流程。

15. 现代编译器解剖（Anatomy of a Modern Compiler）

• 前端 / 分析：检查语法与语义（类型等），把源程序变成机器无关的中间表示（IR）。多语言前端可共享同一 IR。
• 后端 / 综合：先对 IR 做优化（如把与循环下标无关的运算提出循环），再为目标 ISA 生成指令，并做 ISA 相关窥孔优化（如 Beta 上 CMOVE+算术合并）。

16. 前端：词法分析（Frontend Stages: Lexical Analysis）

扫描源文本 → token 序列；空格/制表/换行仅作分隔，扫描后去掉。token 带文件名、行号、列号以便报错。非法 token（如 C 中 3x）在此阶段报错。

17. 前端：语法分析（Frontend Stages: Syntactic Analysis）

解析（parsing）把 token 建成语法树（syntax tree）：操作数挂到一元/二元结点，语句各部件标好角色。树结点标签与前述代码模板对应；深度优先遍历即可按标签选模板——但先还要做语义分析与变换。

18. 前端：语义分析（Frontend Stages: Semantic Analysis）

在语法树上检查语义：如 x = "bananas" 语法合法（左变量、右表达式），但若 x 声明为 int、右为 string，则类型不兼容。查符号表比对类型。完成后：语法树表示语法正确且语义有效的、语言无关的操作序列。

19. 中间表示 IR（Intermediate Representation）

语法树是常用 IR：独立于源语言与目标 ISA；保留运算顺序与分组信息；允许多前端共用一后端。后端可再分：机无关 IR 优化 → 代码生成到目标 ISA。

20. 常用 IR：控制流图（Common IR: Control Flow Graph）

把语法树重组为控制流图（CFG）：结点为基本块（basic block）——以分支结束的赋值/表达式序列；一旦进入块，块内其余操作会连着执行。边表示跳转到哪一块。基本块边界清晰，便于寄存器暂存变量等优化。

21. GCD 的控制流图（Control Flow Graph for GCD）

条件分支块有标 T/F 的两条出边；无条件则单出边。若某块仅一个前驱，可继承前驱关于寄存器中已有 x、y 等知识；多前驱时只能用所有前驱共有的知识。CFG 很像高级 FSM 的状态转移图。

22. IR 优化（IR Optimization）

对 CFG 多遍简单优化，反复直到无进展；简单变换可叠加出复杂效果。例：

• 死代码消除（dead code elimination）：删从未用的赋值、不可达块
• 常量传播（constant propagation）：已知常量的变量用常量替换引用
• 常量折叠（constant folding）：编译期求常量表达式

23. IR 优化示例 I（Example IR Optimizations I）

略造作的源程序及其 CFG：复杂表达式拆成简单二元运算，中间结果用临时名如 _t1。

24. IR 优化示例 II（Example IR Optimizations II）

死代码消除去掉第一块中对 Z 的赋值（后续再赋且中间未用）；发现 X=3 且不再赋值 → 传播常量 3；再常量折叠。

25. IR 优化示例 II（续）（Example IR Optimizations II continued）

更新后的 CFG 再一轮：死代码 → 常量传播 → 常量折叠。

26. IR 优化示例 III（Example IR Optimizations III）

两轮后赋值大减。第三轮：死代码；并可判定条件分支结果 → 删空块或不可达块。

27. IR 优化示例 IV（Example IR Optimizations IV）

IR 明显变小。继续常量传播、折叠、死代码消除。

28. IR 优化示例 IV（续）（Example IR Optimizations IV continued）

直到无更多优化。简单变换反复应用，得到算同一最终 Z 的更小程序。还可加：公共子表达式消除、循环无关代码外提、短循环展开等。

29. 代码生成（Code Generation）

1. 为变量分配专用寄存器；不够则部分进内存，必要时 LD/ST
2. 用模板把赋值/运算译成指令
3. 按块发射，加标签与分支
4. 重排基本块以尽量消除无条件跳转
5. 目标相关窥孔优化

30. 综合 I（Putting It All Together I）

GCD 的原 CFG 与略优化 CFG：主要是常量传播/折叠。顶块关于变量的知识不能简单传到多前驱的 if 块。

31. 综合 II（Putting It All Together II）

为 x、y 专配寄存器；按块生成；重排消除无条件分支。结果已接近人手难再明显改进的质量。

32. 小结（Summary）

编译流水线按序把源码变为高质量汇编：词法 → 语法 → 语义 → IR/CFG 优化 → 代码生成。耐心多遍优化常优于手写汇编；程序员专注功能正确性，细节交给编译器。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L10 注解幻灯片。

源网页：10.1 Annotated Slides | Assembly Language, Models of Computation

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L10：汇编语言与计算模型（Assembly Language, Models of Computation）

本讲介绍 Beta 的 UASM 汇编（符号、标号、宏、伪指令），再上升到计算模型：FSM 局限、图灵机、Church 论题、通用机与不可计算性（停机问题），说明 Beta ISA 的图灵完备性。

1. Beta ISA 回顾（Beta ISA Summary）

回顾：32 个通用寄存器 + PC；主存最多 $2^{32}$ 字节（$2^{30}$ 个 32 bit 字），指令与数据同存。指令 32 bit：6 bit OPCODE，5 bit Ra/Rb/Rc；两种格式（三寄存器 / 两寄存器+16 bit 常数）。三类：ALU、Load/Store、分支与跳转。

2. 编程语言（Programming Languages）

手写二进制编码不现实 → 汇编用符号写 opcode 与操作数；仍需管寄存器与指令序列。高级语言再升一层：变量与数学运算。本讲 UASM；下讲 C→汇编。还可再叠解释器（如 C 实现 Python）——选合适语言表达，经多层翻译落到 Beta 指令。

3. 汇编语言（Assembly Language）

汇编器读文本 → 产出初始化主存的 32 bit 字数组。BSim 内建 UASM：实质是花哨计算器——求值算术表达式得字节，依次填入字节数组。支持符号/标号命名值与地址，宏封装指令/数据的字段拼装。

4. UASM 源文件例子（Example UASM Source File）

通常一行一条语句。注释：// 至行末，或 /* … */ 跨行。

• 符号（symbol）：常量的名字，如 N=12；改一处即可。R0–R31 预定义为 0–31，便于区分寄存器与立即数
• 标号（label）：某内存地址的名字（如下文 loop）

5. 如何汇编？（How Does It Get Assembled?）

维护符号表（初含寄存器符号）。逐行：定义符号/标号、展开宏、求值写字节。例：N=12 入表；ADDC(r31,N,r1) 展开为地址 0 的 32 bit 字；loop: 记下当前地址后展开 MUL。

两遍扫描：第一遍收齐符号/标号；第二遍生成二进制 → 支持前向引用（如向前分支）。

6. 寄存器是预定义符号（Registers Are Predefined Symbols）

寄存器无魔法：只是 0–31 的符号。ADDC(r31,N,r1) 实际变成 ADDC(31,12,1)。若把寄存器符号用在期望立即数处（或反之），UASM 仍按数值解释——操作数含义由 opcode 宏决定，不由写法直觉决定，写汇编须清醒。

7. 标号与偏移（Labels and Offsets）

分支用相对下一条指令的字偏移（$-1$ 指向分支自身）。宏内嵌偏移公式：程序员写目标标号，UASM 算 16 bit 补码。例：BNE 回跳 3 条 → 偏移 $-3$。

8. 强大的宏指令（Mighty Macroinstructions）

宏：参数替换后当原文再处理，可嵌套。WORD/LONG 把值拆成 2/4 字节。Beta 为 little-endian：最低有效字节在最低地址（如 0xDEADBEEF 在 0x100 处先存 0xEF）。亦有 big-endian；跨 ISA 传多字节值常需转换。名称源自《格列佛游记》大小端之争。

9. 指令的汇编（Assembly of Instructions）

辅助宏 BETAOP：三寄存器格式；.align 4 保证字对齐；LONG 拼字段：各域 % 截断再 << 到位。BETAOPC 处理含 16 bit 常数的格式。例：ADDC 把 opcode 0x30、RA、常数、Rc 移位或运算拼成一字——“assemble” 字面义。

10. 汇编例子（Example Assembly）

一次 ADDC 的完整宏展开链：格式与 opcode 知识封在宏体里。换一套宏定义，UASM 可服务几乎任意 ISA。

11. Beta 指令的 UASM 宏（UASM Macros for Beta Instructions）

定义在 beta.uasm（实验会 include）。便利宏：分支常丢弃 PC+4 → 两参数形式默认 Rc=R31，少打字、更易读。

12. 伪指令（Pseudoinstructions）

可读性宏：BR() 代替 BEQ(R31,…)；BF/BT 配合比较结果；PUSH/POP 展开为多指令操作 SP 栈。称 pseudoinstructions：表面上更大指令集，底层仍是 L09 那套。

13. 用伪指令写阶乘（Factorial with Pseudoinstructions）

例：CMOVE 表示“装小常数”，比展开后的 ADDC（加到 0）更易懂。减少认知噪音长期受益。

14. 原始数据（Raw Data）

LONG 分配并初始化数据；标号记地址（如 N→0，factN→4）。LD 便利宏默认 Ra=R31：地址 = 0 + 常数（标号值）→ 把该处字装入寄存器。

15. UASM 表达式与布局（UASM Expressions and Layout）

表达式在汇编时求值，不生成运行时 ADD/MUL。特殊符号 .（dot） = 下一个将填充的地址；初值 0，每写一字节递增。可赋 . 指定放置位置；k: 等价 k=.；也可增大 . 预留未初始化数组空间。

16. 小结：汇编语言（Summary: Assembly Language）

汇编 = 方便生成指令/数据二进制并跟踪地址。UASM：值、符号、标号、宏、.。鸡生蛋：第一个汇编器靠手工汇编二进制，再逐步加符号/宏等特性——且务必备份二进制。

17. 通用性？（Universality?）

NAND 对布尔函数通用。ISA 是否通用？能解 FSM 能解的问题吗？有 FSM 不能解的吗？Beta 能否解？答案依赖计算的数学模型。

18. 计算模型（Models of Computation）

CS 根源之一：比较各模型能表示的计算类，寻找通用模型——凡其它良构模型能描述的，通用模型也能。候选：FSM（时序逻辑可建；可用布尔与转移图 100% 预测行为）。FSM 是否万能数字计算装置？

19. FSM 的局限（FSM Limitations）

括号匹配：判定括号串是否良构（每个开括号有对应闭括号）。FSM 用有限状态记历史——括号检查需计数未匹配开括号，但状态数有上限 → 输入开括号过多则无法正确判定。

有限性限制了需无界计数的问题。转向 Alan Turing 的模型。

20. 图灵机（Turing Machines）

1930 年代 Turing 提出：FSM + 无限纸带（可读写）。输入编码在带上；FSM 读写、改态、写答案后停机 → 图灵机（TM）。

有限非空白输入可编码成大整数；TM 实现整数到整数的函数。FSM 真值表可枚举并赋索引 → 谈“TM 347 在输入 51 上得 42”。

21. 其它计算模型（Other Models of Computation）

Kleene、Post、Turing 等（Church 学生）探索递归函数、字符串重写、λ 演算等，并关注不可实现机解决的问题——亦即刻画可解决类。

22. 可计算性？（Computability?）

各模型能算的整数函数集相同（可互译）。Church 论题：凡可实现机可算的离散函数，皆可由某 TM 计算。尚无严格证明，但被普遍接受。“可计算”≈“某 TM 可计算”。不可计算函数见本讲可选视频。

23. 众多图灵机！（Turing Machines Galore!）

每种想做的计算对应一台（不同）TM。这对通用计算机设计有何启示？是否有些计算永远需要专用机？

24. 通用函数（The Universal Function）

希望有 $U(k,j)=$ 运行 $T_k$ 于输入 $j$ 的结果。$U$ 可计算：存在通用图灵机 $T_U$（且有无穷多；已知最小者约 4 态、6 带符号）。一台通用机可完成任意 TM 能做的计算。

25. 通用性（Universality）

$k$ 编码“程序”（某 TM 描述），$j$ 编码数据；$T_U$ 解释程序、模拟 $T_k$。解释编码计算 = 存储程序计算机的核心思想。

26. 图灵通用性（Turing Universality）

通用 TM 是现代通用计算机的范式。证明 ISA 图灵通用：展示能模拟某已知通用 TM。实际机器内存有限 → 仅对放得下的输入等价。门槛不高：有条件分支 + 简单算术 通常即足够。

27. 编码算法：CS 关键（Coded Algorithms: Key to CS）

程序可作为另一程序的数据 → 编译（高级语言→汇编）、软件组件复用、设计面向任务的语言。结论：拟建引擎能做任意可实现机上的计算；通用 TM 为存储程序机铺路 → Beta ISA 够用。

28. 不可计算！（Uncomputability!）

存在良定义离散函数，无任何 TM 能在有限步对任意有限输入算出 $f(x)$——可证明算法不存在。最著名：停机函数——给定 $(k,j)$，判定第 $k$ 个 TM 在输入 $j$ 上是停机还是永远循环。

29. 为何 $f_H$ 不可计算（Why fH is Uncomputable）

反证：若停机函数可算，则有 $T_H$。构造“nasty”机 $T_N$：$T_N[X]$ 在 $T_X[X]$ 停机时循环，在 $T_X[X]$ 循环时停机（靠 $T_H$ 查询）。再喂 $N$ 给 $T_N$：$T_N[N]$ 必须既停又不停 → 矛盾。故 $T_H$ 不存在，停机函数不可计算。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L09 注解幻灯片。

源网页：9.1 Annotated Slides | Designing an Instruction Set

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L09：指令集设计（Designing an Instruction Set）

从专用阶乘硬件出发，抽象出可编程 datapath 与控制 FSM，引入 von Neumann 存储程序模型，并定量设计本课的 Beta RISC ISA：寄存器、定长指令、ALU/访存/分支。

1. 例子：阶乘 I（Example: Factorial I）

$N!=N\cdot(N-1)\cdots 1$。用 C 描述：变量 a 累乘结果，b 为下一乘数（初值 $N$）；循环中 a=a*b，b=b-1。

2. 例子：阶乘 II（Example: Factorial II）

用高层 FSM 描述：各态“输出”是对变量的运算公式，而非简单电平。状态序列对应 C 程序步骤；b 新值为 0 时进入 DONE。

实现：32 bit 寄存器存 a/b，2 bit 状态寄存器；逻辑判断 b==0，并实现乘、减一与选通写入。

3. 阶乘的 Datapath（Datapath for Factorial）

Datapath：存值寄存器 + 组合运算。START：a←1，b←N；LOOP：a←a*b，b←b-1；DONE：保持。MUX（WASEL/WBSEL）选择写入值。

4. 阶乘的控制 FSM（Control FSM for Factorial）

Datapath 给出 Z（新 b 是否为 0）。控制 FSM：输入 Z，输出 WASEL/WBSEL；真值表含当前态 $S$ 与下一态 $S'$。

5. 控制 FSM 硬件（Control FSM Hardware）

乘/减一用组合电路；控制用寄存器+ROM：$Z$+2 bit 状态 → 3 输入，$2^3=8$ 单元，每单元 6 bit（WASEL、WBSEL、下一态各 2 bit）。

6. 目前：专用硬件（So Far: Single-Purpose Hardware）

流程：高层 FSM → datapath → 控制 FSM。整体也是 FSM，但 datapath 寄存器也算“状态”则约 66 bit → $2^{66}$ 行真值表不可行 → datapath 与控制 FSM 分离思考。

通用化：更多存储、更丰富运算集（最小充分集出人意料地小；复杂运算常拆成加减乘序列）。架构乐趣在折衷。

7. 简单可编程 Datapath（A Simple Programmable Datapath）

4 个数据寄存器；ASEL/BSEL 选操作数；OPSEL 选运算结果；WEN+WSEL 写回（寄存器带 load-enable）。控制 FSM 序列产生控制信号；Z 支持数据相关转移。

8. 阶乘的控制 FSM（A Control FSM for Factorial）

通用 datapath 每拍一运算 → 每轮循环需乘、减一、判零三态。通用机往往比专用电路更多周期、可能更多硬件。

9. 新问题 → 新控制 FSM（New Problem → New Control FSM）

同一硬件可做幂、除、开方等（寄存器 ≤4）。设计控制 FSM ≈ 编程：规定运算序列。

10. ENIAC 计算机（The ENIAC Computer）

早期数字计算机正是如此工作。图为 1943 宾大 ENIAC。

11. 给 ENIAC 编程（Programming The ENIAC）

ENIAC 支持循环、分支、子程序，但映射到机器常需数周；拨开关、插线需数日，再单步调试。急需更轻便的编程方式。

12. von Neumann 模型（The von Neumann Model）

现代机多基于 1945 von Neumann 存储程序模型，三部分：

1. CPU：datapath + 控制 FSM
2. 主存：约 $W$ 个 $N$ bit 字；CPU 发地址读写（延迟约数十 ns）
3. I/O：与外界通信、非易失存储等

13. 关键思想：存储程序计算机（Key Idea: Stored-Program Computer）

指令与数据同存主存，皆为二进制。指令含 opcode、源/目的寄存器等字段；CPU 解释并执行，再取下一条。

如何区分指令与数据？看值本身不行——看用法：进 datapath → 数据；被控制逻辑取用 → 指令。

14. von Neumann 机解剖（Anatomy of a von Neumann Computer）

• Datapath（肌肉）：寄存器、ALU、访存通路
• 控制单元（大脑）：从主存取指令，译成 ASEL/BSEL/DEST/FN 等；含 PC（program counter） 指向下一条；接收状态以支持条件执行

32 个寄存器 → 选择信号各 5 bit；ALU 功能码可 6 bit。

15. 指令（Instructions）

指令是基本工作单元。执行循环：按 PC 取指 → 译码控制 datapath → ALU 运算写回 → PC ← 下一指令地址。现代机能每秒数十亿条。

16. 指令集架构 ISA（Instruction Set Architecture）

ISA = 指令字段含义 + 存储/运算的功能规格，是硬件与程序员的契约。可换软件；硬件可升级而软件不变（x86 从约 30 万 IPS 到约 50 亿 IPS）。

警告：ISA 中嵌入的技术约束（寄存器数、字宽、地址空间）成功后难改——旧软件要跑在新机器上，坏选择可能背几十年。

17. ISA 设计（ISA Design）

难题：支持哪些运算？多少寄存器？多大内存？编码偏紧凑还是译码简单？

定量方法：选代表性 benchmark → 用拟议 ISA 实现并模拟 → 按速度/能耗/面积/成本评估。原则：识别常见操作并优化它们（通用计算中算术与访存极常见）。本课机器称 Beta。

18. Beta ISA：存储（Beta ISA: Storage）

Beta 是 RISC：多数指令只访问内部寄存器；访存用独立 LD/ST，地址计算简单。同类：ARM、MIPS；x86 更复杂。

CPU 状态：32 bit PC；32 个 32 bit 寄存器 R0–R31（指令中 5 bit 编号）。R31 恒为 0，写入无效。主存为 32 bit 字（4 字节），仅支持字访问，但用字节地址：相邻字地址差 4。常用 0x 十六进制。

19. 存储约定（Storage Conventions）

变量住在主存固定地址。算 y=x*37：LD x→R0，乘 37，ST 回 y。热数据尽量留在寄存器。模板：load → 计算 → store → load-store 架构。

20. Beta ISA：指令（Beta ISA: Instructions）

三类：计算、LD/ST、分支。全部 32 bit 定长，占一字 → 译码简单；多数指令下一地址 = PC+4。

定长常不如变长紧凑，但变长译码复杂、能耗/性能代价高；当今内存相对充裕，Beta 选择定长以换小而快的执行引擎。

21. Beta ALU 指令（Beta ALU Instructions）

字段：6 bit opcode，5 bit ra/rb 源，5 bit rc 目的；其余填 0。Opcode 固定在 [31:26]。

例：ADD，opcode 0b100000，ADD(r1,r2,r3) → R3←R1+R2；编码 0x80611000。同一寄存器可兼源与目的（如 R1←R1+R1 即 ×2）。助记符比二进制好写。

22. 实现草图 #1（Implementation Sketch #1）

ra/rb 选操作数（R31→常数 0）；rc 选写回。Opcode→ALU 功能可用 64 项 ROM。PC 每指令 +4。RISC 好处：许多字段可直接作控制信号。

23. 是否支持常数操作数？（Should We Support Constant Operands?）

用定量法评估“第二操作数可为小常数”：腾出 16 bit 常数域。看实际执行（非静态出现次数）：算术指令过半第二操作数为小常数；比较约 80%；地址计算亦常见 → 批准该特性（程序更小更快）。

24. 带常数的 Beta ALU 指令（Beta ALU Instructions with Constant）

第二格式：rb 换为 16 bit 补码常数（$-32768\sim 32767$）。例：ADDC(r1,-3,r3)。16→32 bit 用符号扩展（复制符号位），纯布线即可。助记符加后缀 C；超 16 bit 常数须放主存再 LD。

25. 实现草图 #2（Implementation Sketch #2）

多一个 MUX：BSEL=1 选符号扩展常数，否则选 rb。细节后几讲再展开。

26. Beta 的 Load / Store（Beta Load and Store Instructions）

访存唯一途径。地址 = Ra + 符号扩展(const)（与 ADDC 同硬件）。LD：内存→Rc；ST：Rc→内存。ST 特殊：唯一需读 Rc；符号形式中 Rc 写在前；唯一不写寄存器堆的指令。

27. 使用 LD 与 ST（Using LD and ST）

y=x*37 三条：LD(0x1008,r31,r?) 等。地址适合 16 bit 常数时直接编入；更大地址当大常数存内存。低内存放不下全部大常数时，可用后讲的 LDR（load relative）。

28. 仅用 ALU 能解阶乘吗？（Can We Solve Factorial with ALU Instructions?）

顺序执行不够：需循环/跳过 → 条件分支。条件成立则 PC 改到 branch target；否则 PC+4。用于循环、if、过程调用等。

29. Beta 分支指令（Beta Branch Instructions）

BEQ：先把 PC+4 写入 Rc（不需要可写 R31）；若 Ra==0 则 PC 加 字偏移×4（PC-relative）；否则 PC+4。偏移 0 = 下一条；$-1$ = 分支自身。负偏移常用于循环回跳；正偏移用于 if 前跳。

BEQ(R31,…) 恒成立 → 无条件分支。BNE：Ra≠0 时跳转。

30. 现在能写阶乘了吗？（Can We Solve Factorial Now?）

迭代阶乘：标号 L: 处 MUL、减一，BNE 回 L。符号形式写标号，由汇编器算偏移。与早先高层 FSM 各态高度对应（datapath 相似时常见）。

31. Beta JMP 指令（Beta JMP Instruction）

JMP：PC←Ra，并可选保存 PC+4 到 Rc。配合无条件分支：调用时 BEQ 跳到过程并保存返回地址；过程末 JMP 返回。同一过程可从多处调用（返回地址不同）。过程细节后讲。

32. Beta ISA 小结（Beta ISA Summary）

• 32 个寄存器；程序与数据在主存；$2^{32}$ 字节地址空间；字访问、地址为 4 的倍数
• 两种格式：opcode+三寄存器，或 opcode+两寄存器+符号扩展 16 bit 常数
• 三类指令：ALU、LD/ST、分支与 JMP

下一讲：用这套简单运算表达任意可计算过程。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L08 注解幻灯片。

源网页：8.1 Annotated Slides | Design Tradeoffs

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L08：设计折衷（Design Tradeoffs）

本讲讨论功耗（静态/动态）、降耗手段，以及加法器（ripple / carry-select / CLA）与乘法器（组合 / 流水 / 时序 carry-save）在延迟、吞吐与面积上的 $\Theta$ 折衷。完成本课程 Part 1 的收束。

1. 优化你的设计（Optimizing Your Design）

正确折衷取决于设计目标。显卡团队：优先性能，可在限度内换成本与功耗；尺寸有硬上限，再小收益不大。手表团队：尺寸与功耗关键（戴一天、不烫手腕）。

同一“是否流水”决策：流水寄存器增加成本；重叠执行与更高 $t_{\mathrm{CLK}}$ 抬高功耗与散热需求 → 两队结论可能相反。本章列举可用折衷；选对约束下的权衡是工程师的乐趣。

2. CMOS 静态功耗（CMOS Static Power Dissipation）

静态功耗：电路空闲（节点不变）时仍消耗的功率。理想开关模型下 CMOS 静态功耗为 0；早期接近理想，但尺寸缩小、电压降低后两大效应凸显（n/p 沟道皆有）：

1. 栅氧变薄 → 电场增强、速度提升，但电子可隧穿绝缘层，产生栅→衬底漏电流；数十亿管累积不可忽视
2. 亚阈导通（sub-threshold conduction）：名义截止（$V_{\mathrm{GS}}<V_{\mathrm{TH}}$）时仍有漏电，与 $V_{\mathrm{GS}}-V_{\mathrm{TH}}$（截止时为负）指数相关；$V_{\mathrm{TH}}$ 降低使漏电增大

缓解：FinFET / tri-gate（沟道成鳍、栅三面包围）可把亚阈漏电降一个数量级以上。

3. CMOS 动态功耗 I（CMOS Dynamic Power Dissipation I）

动态功耗：节点翻转充放电电容时消耗。以反相器为例：充/放电时电流经 MOSFET，瞬时功率 $I_{\mathrm{DS}}V_{\mathrm{DS}}$。对 1→0 积分（$I=C\,dV/dt$），若时钟周期 $t_{\mathrm{CLK}}$、每半周期一次翻转，经 pulldown 耗散的功率约为 $0.5\,f\,C\,V_{\mathrm{DD}}^2$（$f$ 为每秒翻转次数）。

完整充→放一周期耗散 $CV_{\mathrm{DD}}^2$ 焦耳；频率 $f$ 时平均功率为 $fCV_{\mathrm{DD}}^2$ 瓦；能量全部来自电源：一半充电容时耗散，一半存于电容后放电耗散。

4. CMOS 动态功耗 II（CMOS Dynamic Power Dissipation II）

整电路：每周期约 $N$ 个节点翻转时，可据此估算总能耗。信封估算：1 GHz、1 亿内部节点、每节点 $\sim 1\,\mathrm{fF}$、$V_{\mathrm{DD}}\sim 1\,\mathrm{V}$ → 约 100 W——接近白炽灯泡，散热困难。笔记本 CPU 远低于此，靠设计技巧压功耗。

单独降低 $V_{\mathrm{DD}}$（如 3.3 V→1 V）可降功耗一个数量级以上（因 $\propto V^2$）。技术趋势使晶体管更多更快，若不精打细算会撞上功耗墙。

5. 如何降低功耗？（How Can We Reduce Power?）

ALU 常含算术、布尔、移位、比较等独立模块；控制只选其一，其余结果被忽略——但仍在耗动态功耗。机会：关掉不需要的模块。

思路：阻止其输入变化 → 内部节点不动 → 动态功耗为零。

6. 更少翻转 → 更低功耗（Fewer Transitions → Lower Power）

手段：

• 各模块输入加 latch，仅当本周期需要该结果时打开 → 移位器等大模块多数时间不翻转
• 切断电源关断整块（更复杂，常用于特殊省电模式）
• 降频：无事时减慢时钟（对毫秒级外部事件尤其有效），有事件再加速

移动设备广泛使用上述技巧。计算是否必然耗能见课程笔记 §6.5。

7. 提速：加法器例子（Improving Speed: Adder Example）

瓶颈常在行波进位加法器（ripple-carry）：最长路径是进位链。触发：A 全 1、B 最低位 1 其余 0（加 $-1$ 与 $1$）→ 进位逐级 ripple。

延迟 $\approx (N-1)\times t_{\mathrm{carry}}+t_{\mathrm{sum}}$。$N$ 翻倍则延迟约翻倍 → 延迟 $\Theta(N)$（阶记号忽略相对次要项）。

8. 性能/成本分析（Performance/Cost Analysis）

渐近分析：标出 $N\to\infty$ 时主导项。例：$n^2+2n+3$ 被常数倍的 $n^2$ 上下夹住（除有限个 $n$）→ $\Theta(n^2)$。

• $\Theta(f)$：上下皆被 $f$ 的常数倍界定
• $O(f)$：仅上界

9. 进位选择加法器（Carry-Select Adders）

高半部不必等低半部进位：做两份高 16 位加法（假设 $C_{\mathrm{in}}=0$ 与 $1$），与低半部并行；再用低半部真实进位选结果 → carry-select adder。

32 bit 延迟约略高于 16 bit ripple，$\sim$ 减半延迟，代价约 +50% 电路。递归对更小块做同样事：$\log_2 N$ 层后延迟为常数加法 + $\log N$ 个 MUX → $\Theta(\log N)$。清晰的性能–面积折衷。

10. 32 位进位选择加法器（32-Bit Carry-Select Adder）

工程版：块大小使试算和与前级进位几乎同时到达 select MUX；select 负载大时加 buffer。相对 32 bit ripple：约 2.5× 更快，约 2× 电路——ALU 提速常记方案。

11. 要更快的进位逻辑！（Wanted: Faster Carry Logic!）

链 → 树可把线性延迟变对数。改写全加器进位：

• G（generate）：无需等 $C_{\mathrm{in}}$ 即产生进位
• P（propagate）：有 $C_{\mathrm{in}}$ 才传出

$C_{\mathrm{out}}=G\lor(P\land C_{\mathrm{in}})$。常把 P 从 $A\lor B$ 改为 $A\oplus B$，则和可写 $S=P\oplus C_{\mathrm{in}}$。进位 SOP 可用三个 2 输入 NAND 实现。

12. 超前进位加法器（Carry Look-Ahead Adders, CLA）

相邻两模块 H、L：块 generate / propagate：

$$G_{\mathrm{block}}=G_H\lor(G_L\land P_H),\quad P_{\mathrm{block}}=P_L\land P_H.$$

用 GP 模块组合两级进位信息，把两模块当作更大块。

13. 8 位 CLA（生成 G 与 P）（8-Bit CLA: generate G & P）

多层 GP 成树：$N$ 输入共 $N-1$ 个 GP 模块，延迟 $\Theta(\log N)$。下一步用 G/P 快速算各全加器的 $C_{\mathrm{in}}$。

14. 8 位 CLA（进位生成）（8-Bit CLA: carry generation）

给定最低位 $C_0$：块的低半直接用该进位；高半进位用低半 G/P 算出。C 模块再排成树，层层算出各全加器 $C_{\mathrm{in}}$，延迟仍 $\Theta(\log N)$。注意同一位置 C 的 $G_L,P_L$ 与 GP 树输入对应。

15. 8 位 CLA（完整）（8-Bit CLA: complete）

GP 与 C 合成 carry-lookahead 模块：向上传 G/P，向下传进位。上行+下行总延迟 $\Theta(\log N)$，再加一级 XOR 得和 → 整加法器延迟 $\Theta(\log N)$，远优于 ripple 的 $\Theta(N)$。全加器内原 carry-out 逻辑可删。同类策略的极致见 Kogge-Stone 等。

16. 二进制乘法（Binary Multiplication）

小学竖式：乘数每位 × 被乘数得部分积，左移对齐后相加。1 bit×1 bit 即 AND，无进位；部分积宽 $N$。$M$ 位乘数 → $M$ 个部分积；相加得 $N+M$ 位结果。贵在把 $M$ 个 $N$ 位部分积相加。

17. 组合乘法器（Combinational Multiplier）

$M\times N$ 个 AND 算部分积；行间用全加器/半加器累加。信息只向下或向左，最长路径至多 $N+M$ 个模块 → 延迟 $\Theta(N)$（$M,N$ 差常数倍）；吞吐 $=1/\textrm{latency}$；硬件 $\Theta(N^2)$。

18. 补码乘法（2’s Complement Multiplication）

补码最高位负权重 → 部分积需符号扩展到 $N+M$ 位；末个部分积因乘数符号位而改为减。技巧：在若干列加 1 再抵消，把符号扩展与减法化成：若干位取反 + 两处加常数 1——最终表几乎与无符号竖式同形。

19. 补码乘法器电路（2’s Complement Multiplier）

相对无符号版：部分 AND→NAND（取反），并改两处加 1 的逻辑。延迟、吞吐、硬件代价与无符号版同阶。

20. 流水提高吞吐（Increase Throughput with Pipelining）

原组合乘吞吐约每 $2N$ 拍出一个结果。画输出轮廓得 1-pipeline；再对半切可翻倍吞吐，但仍 $\Theta(1/N)$。关键洞察：整行在同一级 → 级延迟仍含 $N$ bit ripple → $\Theta(N)$。

21. Carry-Save 流水乘法器（Carry-Save Pipelined Multiplier）

重画进位链：进位仍向左一列，但接到下一行同列。水平流水线切断长进位；每级延迟常数（与 $N$ 无关）。需 $\Theta(N)$ 额外行收尾进位。

$\Theta(N)$ 级 → 级延迟/时钟/吞吐皆 $\Theta(1)$；系统延迟 $\Theta(N)$；硬件仍 $\Theta(N^2)$。吞吐显著提升的折衷。

22. 时序逻辑减面积（Reduce Area with Sequential Logic）

时序乘法器：每拍算一个部分积并累加到 P，共 $\Theta(N)$ 步。B 最低位 × 被乘数 → carry-save 加法器；P 与加法器输出为 carry-save 格式（数据和 + 保存的进位）。每拍 P、B 右移 1——等价于“部分积左移”的对偶。

无完整进位传播 → 时钟周期与 $N$ 无关（约一个全加器延迟）。再 $\Theta(N)$ 步收尾进位 → 总延迟仍 $\Theta(N)$，吞吐 $\Theta(1/N)$，硬件 $\Theta(N)$（相对组合 $\Theta(N^2)$ 大降）。Carry-save：可同硬件提吞吐，或同吞吐省面积。

23. 小结（Summary）

Part 1 收束：信息与编码 → 冗余检错/纠错 → 数字抽象与噪声容限 → MOSFET/CMOS 与组合综合 → 双稳态存储与动态纪律 → FSM 与亚稳态/同步 → 延迟与吞吐 → 本讲功耗与加法/乘法折衷。

设计时可在功耗、延迟 $\Theta(N)$ vs $\Theta(\log N)$、吞吐 $\Theta(1)$ vs $\Theta(1/N)$、面积 $\Theta(N)$ vs $\Theta(N^2)$ 之间按目标选型。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L07 注解幻灯片。

源网页：7.1 Annotated Slides | Performance Measures

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L07：性能度量（Performance Measures）

本讲引入电路性能的两个核心指标——延迟（latency）与吞吐（throughput），并用洗衣店类比说明流水线如何用略增延迟换取更高吞吐；随后给出构造良构 K 级流水线（K-pipeline）的系统方法，以及用交错（interleaving）与并行突破瓶颈；最后对比同步全局定时、握手与自定时等控制结构。

1. 先放下电路… 解决一个真实问题（Forget Circuits… Let’s Solve a Real Problem）

目标：提出衡量电路性能的指标，并研究如何提升。先放下电路，用日常例子帮助理解这些指标。

洗衣是人人都会遇到的“处理任务”。系统输入是若干篮脏衣，输出是洗净、烘干并叠好的同批衣物。两个部件：洗衣机 30 分钟洗一篮，烘干机 60 分钟烘一篮。路径简单：先洗后烘；假设尽快推进，一步能走就走下一步。攒多篮再洗往往更划算——下面说明原因。

2. 一次一篮（One Load at a Time）

单篮：洗 30 分钟 + 烘 60 分钟 = 从输入到输出共 90 分钟。若比作组合逻辑，传播延迟就是 90 分钟。接着考虑 $N$ 篮。

3. 洗 N 篮：哈佛式（Doing N Loads of Laundry）

想象“哈佛式”做法：严格按组合逻辑节奏——上一组输入算完、输出有效后，才喂下一组。步骤 1 洗第一篮，步骤 2 烘第一篮，共 90 分钟；再进入步骤 3 处理第二篮……总时间 $N\times 90$ 分钟。

类比清晰：烘干时洗衣机空闲，吞吐受拖累。

4. 洗 N 篮：6.004 式（Doing N Loads… The 6.004 Way）

重叠洗与烘：步骤 1 洗第一篮；步骤 2 烘第一篮的同时开始洗第二篮。步骤时长由烘干机决定为 60 分钟；洗衣机虽提早完成，但只有一台烘干机，系统节拍由最慢级决定。

这种重叠处理输入序列的系统叫流水线（pipelined system），每步叫一级（stage）。洗衣是 2 级流水线，每级处理时间 60 分钟。稳态下每 60 分钟开一篮洗、出一篮干——有效吞吐为每 60 分钟一篮；$N$ 篮约 $N\times 60$ 分钟。某一篮要经两级，约 120 分钟（首篮略不同；流水线性能分析关心有无穷输入的稳态）。

5. 性能度量（Performance Measures）

两个指标：

一入一出系统中，吞吐也等于输入被消耗的速率。哪个更好取决于目标：洗 100 篮要高吞吐；约会前 90 分钟内要干净内衣则更关心延迟。用流水线提吞吐时，各级需锁步，节拍由最慢级决定，延迟通常上升——这是常见的延迟–吞吐权衡。

6. 回到电路（Okay, Back to Circuits…）

组合电路：延迟 $= t_{\mathrm{PD}}$，吞吐 $= 1/t_{\mathrm{PD}}$（算完当前才开下一组）。

例：F、G 并行，结果再进 H。输入 $X$ 稳定后，F、G 出 $F(X)$、$G(X)$，再经 H 的 $t_{\mathrm{PD}}$ 得 $P(X)$。模块不变则延迟难再压；但 F、G 出结果后空闲等 H——能否让 F、G 处理下一输入，同时 H 仍在算上一拍？即把电路拆成两级：第一级算 $F(X)$、$G(X)$，第二级算 $H$。

7. 流水线电路（Pipelined Circuits）

用寄存器锁住 $F(X)$、$G(X)$ 供 H 使用，同时让 F、G 开下一输入。分析时先假定流水寄存器 $t_{\mathrm{PD}}$、建立时间为 0。

时钟周期由最慢级决定：含 F、G 的级至少需 20 ns；含 H 的级需 25 ns → 系统 $t_{\mathrm{CLK}}=25\,\mathrm{ns}$。一般做法：寄存器把组合逻辑切成若干级，每拍推进一级。本例 2 级、周期 25 ns → 延迟 50 ns（略高于未流水），吞吐每 25 ns 一个输出——吞吐明显提升，延迟略增。

8. 流水线时序图（Pipeline Diagrams）

行表示各级，列表示连续时钟周期。周期 $i$ 初输入 $X_i$ 有效；该周期内 F、G 处理，$i$ 末结果写入级间寄存器。周期 $i+1$ 中 H 处理 $X_i$，同时 F、G 处理 $X_{i+1}$。某一输入沿对角线每拍下移一级；$i+1$ 末 H 结果写入末级寄存器，于 $i+2$ 可用。总延迟两拍；之后每拍出一个结果。

9. 流水线约定（Pipeline Conventions）

K 级流水线（K-pipeline）：无环电路，从输入到输出每条路径恰有 K 个寄存器。未流水的组合电路是 0 级流水线。

约定：每一级（因而每个 K-pipeline）在输出端有寄存器，便于把流水部件拼成更大流水系统。用时序电路计时方法：对每条寄存器→寄存器、输入→寄存器路径，求输入寄存器 $t_{\mathrm{PD}}$ + 组合 $t_{\mathrm{PD}}$ + 输出寄存器建立时间，取最大者作为 $t_{\mathrm{CLK}}$ 下界。时钟正确且每条路径恰 K 个寄存器时，K-pipeline 与原组合电路功能等价。

• 延迟：$K\cdot t_{\mathrm{CLK}}$
• 吞吐：$1/t_{\mathrm{CLK}}$

10. 病态流水线（Ill-Formed Pipelines）

反例：经 A、C 的上路径 2 个寄存器，经 B、C 的下路径 2 个，经 A、B、C 的中路径只有 1 个——不是良构 K-pipeline。后果：不同“代”的输入混算（如周期 $i+1$ 中 B 用当前 $X$ 与上一拍 $Y$），结果与未流水电路不同。需要一种方法：在一条路径加寄存器时，保证所有路径同步加。

11. 流水线方法论（A Pipelining Methodology）

步骤：

1. 画一条穿过所有输出的等高线，两端记为后续等高线的端点。
2. 继续在模块间信号上画等高线，两端仍落在同一对端点；每条信号同向穿越等高线（输入一侧、输出另一侧）。等高线划分流水级。
3. 在信号与等高线交点放置流水寄存器。

端点到端点保证每条输入–输出路径都被穿过 → 良构。再找最长寄存器→寄存器或输入→寄存器延迟定 $t_{\mathrm{CLK}}$。例：理想零延迟寄存器时，C 模块要求 8 ns → 吞吐每 8 ns 一个；3 条等高线 → 3-pipeline，延迟 $3\times 8=24\,\mathrm{ns}$。

通常目标：用尽量少的寄存器达到最大吞吐——找出最慢部件（如 C），在其输入输出两侧画等高线，把 $t_{\mathrm{CLK}}$ 钉在该延迟，再布置其余等高线使级间最长路径不超过此时钟。同吞吐/延迟下画法可有多种（如 E 可与 F 同级）。

12. 流水线示例（Pipeline Example）

复习：先过全部输出 → 1-pipeline，吞吐/延迟与原组合相同。再画线隔离最慢件 → 2-pipeline，$t_{\mathrm{CLK}}=2$，吞吐翻倍。再加等高线只会加级数、增延迟，不提吞吐（合法但不划算）。路径长短不一时会出现背靠背寄存器，正常。

策略：流水通常提吞吐、增延迟；各级完美平衡时延迟可不增。流水电路的延迟不会低于未流水电路。隔离最慢件后吞吐无法再靠加级提升——瓶颈在该部件本身。

13. 流水线部件（Pipelined Components）

若有流水版部件可用：把 A 换成 2 级流水的 A′，重画等高线时须让 2 条等高线穿过 A′（计入内部寄存器），从而在系统其余处补上对齐两拍延迟的寄存器。例中各级最大 $t_{\mathrm{PD}}$ 降到 1 ns，吞吐从 $1/2$ 升到 $1/1$；4-pipeline，延迟 4 ns。若瓶颈无流水替代品，见下一节。

14. 6.004 学生怎么洗衣？（How Do 6.004 Students Do Laundry?）

绕过烘干机瓶颈：找“一台洗衣机配两台烘干机”的店。时间轴按 30 分钟一步：洗衣机每步都在用，每 30 分钟出一篮湿衣；烘干机交错——#1 烘奇数篮、#2 烘偶数篮，各烘两步（60 分钟）。整体每 30 分钟出一篮干净干衣。稳态吞吐每 30 分钟一篮，单篮延迟仍 90 分钟。

要点：烘干机本身未流水，但两台交错表现得像周期 30 分钟、延迟 60 分钟的 2 级流水线——用两份未流水部件交错，可等效 2 级流水。

15. 回到瓶颈（Back to Our Bottleneck…）

前例吞吐卡在 $1/8\,\mathrm{ns}$（C 的 8 ns 延迟定最小时钟）。要再提吞吐：要么找 C 的流水版，要么用两份未流水 C 做交错等效 2 级流水。

16. 电路交错 I（Circuit Interleaving I）

通用双路交错：两份 C（$C_0$、$C_1$）。各输入来自 D 锁存器（捕获并保持输入）；MUX 选哪路 C 输出写入输出寄存器。左下角极简 2 状态 FSM：下一状态为单反相器，状态在 0/1 间交替；状态位在上升沿后翻转。

17. 电路交错 II（Circuit Interleaving II）

波形：新 $X$ 在时钟上升沿后到达。FSM $Q$ 为低时 $C_0$ 输入锁存打开，$X_1$ 进入，$C_0$ 在约第 2 拍末出结果；第 2 拍初锁存关闭，保持 $X_1$ 稳定，使 $C_0$ 有近两拍时间计算。$C_1$ 类似，错开一拍。MUX：$Q$ 高选 $C_0$，低选 $C_1$；上升沿时输出寄存器采样。行为像 2 级流水：周期 $i$ 到达的输入经两拍，于 $i+2$ 可用。

18. 电路交错 III（Circuit Interleaving III）

时钟周期：上游流水寄存器、内部锁存与 MUX 的传播延迟，以及输出寄存器建立时间，使 $t_{\mathrm{CLK}}$ 须略大于 C 的 $t_{\mathrm{PD}}/2$。可把交错电路当作 2 级流水：每拍吃一个输入，两拍后出结果。

19. 组合技巧（Combine Techniques）

在流水图中，N 路交错部件当作 N 级流水，须有 N 条等高线穿过它。用 2 路交错的 C′ 替换慢 C：先过全部输出，再保证两条等高线穿过 C′，在交点加寄存器——穿过 C′ 的等高线会在 F 的其他输入上多加寄存器，以匹配 C′ 的两拍延迟。乐观设 C′ 最小 $t_{\mathrm{CLK}}=4\,\mathrm{ns}$，则系统时钟由 F 的 5 ns 决定 → 吞吐每 5 ns 一个；5 条等高线 → 5-pipeline，延迟 $5\times 5=25\,\mathrm{ns}$。

20. 再加一点并行（And Add a Little Parallelism…）

流水系统再并行：两台洗衣机 + 四台烘干机 ≈ 两份“1 洗 2 烘”。每步消耗/产出两篮 → 吞吐 2 篮 / 30 min，等效每 15 分钟一篮；单篮延迟仍 90 分钟。

即便部件慢，也可靠交错与并行继续提吞吐。上界存在：流水寄存器与交错逻辑的时序开销给出最小可行 $t_{\mathrm{CLK}}$，从而限制最大吞吐——现实世界没有无限加速。

21. 控制结构备选（Control Structure Alternatives）

此前流水各级锁步，时钟按各级最坏情况选取——同步、全局定时系统。

若处理时间有数据相关性（某些输入某级可更快）？一种做法：仍用单一系统时钟，但各级用握手表明“准备好要新输入 / 有新输出给下级”。两信号协议：上游 HERE-IS-X 表示下一上升沿将有新数据；下游 GOT-X 表示愿意在上升沿取数。仅在上升沿检查信号：两边同时看到两者为真则握手完成、该沿完成传输；任一方仍在忙可推迟。

也可做无全局时钟的异步自定时：四相握手——(1) 上游有新输出且 GOT-X 已撤时断言 HERE-IS-X；(2) 下游消费后断言 GOT-X；(3) 下游等 HERE-IS-X 变低；(4) 下游撤 GOT-X，准备下一轮。时序由握手边沿决定，无需全局时钟。

22. 自定时示例（Self-Timed Example）

多下游时：A 的输出同时给 B、C。黄色组合块合并 B、C 的 GOT-X，汇总给 A——两边都断言 GOT-X 后才向 A 断言；两边都撤消后才向 A 撤消。

23. 自定时示例（续）（Self-Timed Example continued）

动画式时序：上游向 A 传输入 → A 回 GOT-X → 完成四相。A 向 B、C 发 HERE-IS-X；B 先就绪断言 GOT-X，C 尚等第二输入。B 算完再给 C 第二输入；C 两边都收到后断言，黄盒才让 A 知道传输完成。整系统纯靠翻转信令：各模块自主决定消费/产出时刻，可按实际速度跑，而不必等全局最坏延迟。

24. 控制结构分类（Control Structure Taxonomy）

25. 小结（Summary）

• 用延迟与吞吐刻画性能；组合电路延迟 $= t_{\mathrm{PD}}$，吞吐 $= 1/\text{latency}$。
• K-pipeline：每级输出有寄存器；输入到输出每条路径恰 K 个寄存器；$t_{\mathrm{CLK}}$ 由最慢级决定；吞吐 $= 1/t_{\mathrm{CLK}}$，延迟 $= K\, t_{\mathrm{CLK}}$。
• 流水线是多数高性能数字系统提升吞吐的关键；交错与并行可在慢部件存在时继续推高吞吐，但受寄存器/交错开销限制。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L06 注解幻灯片。

源网页：6.1 Annotated Slides | Finite State Machines

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L06：有限状态机（Finite State Machines）

本讲在时序逻辑之上引入 FSM 抽象：状态转移图、Moore/Mealy、ROM/门级实现、等价状态化简，以及异步输入与亚稳态、同步器隔离策略。

1. 我们的新机器（Our New Machine）

上一章得到时序逻辑：组合逻辑云 + 状态寄存器。

• 组合逻辑：无环图，服从静态纪律——合法且稳定的数字输入 → 在最后一次输入跳变后的规定时间内得到合法且稳定的数字输出；功能规格给出每种输入组合的输出。图中有 $k+m$ 个输入、$k+n$ 个输出，真值表有 $2^{k+m}$ 行、$k+n$ 列输出。
• 状态寄存器：记住当前状态，用 $k$ 比特编码，最多 $2^k$ 个互异状态。状态以合适方式捕获输入序列中相关历史；过去输入若影响后续行为，正是通过这些状态比特。典型地，周期时钟上升沿触发 LOAD，把组合逻辑算出的新状态写入寄存器。

设计任务：决定期望输入序列应对应怎样的输出序列（一次输入可能引出一长串输出，或输出暂不变、靠内部状态逐步记住信息）→ 写出计算输出与下一状态的功能规格 → 画出实际电路。

2. 一个简单的时序电路（A Simple Sequential Circuit）

例：密码锁。1 比特输入按位串入口令；输出 UNLOCK 仅当最近四位输入为 0-1-1-0 时为 1。

是否必须记住最近四位（4 个状态比特）？不必。只需知道“最近输入是否构成正确口令的某个前缀”——输入不对时，不必记录“错成什么样”，只需知道“不对”。由此引入描述时序行为的抽象。

3. 今日抽象：有限状态机（Abstraction du jour: Finite State Machines）

FSM 描述时序逻辑的输入/输出行为，与具体实现无关。要素：

• 周期 CLOCK：上升沿触发当前状态 → 下一状态
• 有限个状态，上电有一个初始/起始状态。状态数本身是设计题：状态比特数与计算下一状态/输出的组合逻辑复杂度常有折衷
• 输入：传送外部信息。100 比特信息可一次并行送入，也可单线串行 100 拍——时序逻辑远快于被控物理过程时，常选比特串行以省互连，代价是传输时间
• 输出：同理可串行/并行编码
• 转移规则：由当前状态 $S$ 与输入 $I$ 定下一状态 $S'$，须对所有 $S,I$ 组合穷尽
• 输出规则：常可仅是 $S$ 的函数（更简单）；一般也可是 $S$ 与当前输入的函数

4. 状态转移图（State Transition Diagram）

用状态转移图描述密码锁 FSM。初始状态 SX：尚未收到任何口令位；圆圈表示状态，符号名提醒“记住了什么历史”。本例解锁输出 $U$ 仅依赖当前状态，写在圆内；SX 中 $U=0$。初始态用粗边框标出。

收到 0 → 转到 S0（已见口令首位）。箭头标转移条件；时钟上升沿触发转移。继续补全正确口令路径，最右态 S0110 表示已检出 0-1-1-0，$U=1$。从 SX 输入 0-1-1-0 会停在 S0110。

输入不是期望下一位时：例如 SX 收到 1，仍无正确前缀，留在 SX。错误输入不一定回到 SX——若在 S0110 再收 1，最近四位变成 1-1-0-1，但末两位 0-1 可能是合法口令前缀，故转到 S01。

输出仅是当前状态的函数 → Moore 机（输出写在状态圆内）。输出还依赖当前输入 → Mealy 机：转移箭头上用 / 分隔输入与输出，如 0/1。

5. 合法的状态图（Valid State Diagrams）

良构规则：

• 互斥（mutually exclusive）：同一状态下不能有两条转移带相同输入标签——否则下一状态有歧义，行为不一致
• 穷尽（collectively exhaustive）：每个可能输入值都应有转移；若某输入下应停留，画指向自身的自环

于是对每一对（当前状态，输入）恰选一条转移。

6. 状态转移图即真值表（State Transition Diagram as a Truth Table）

转移图可写成真值表：行 = 当前状态 + 输入的所有组合；输出列 = 下一状态与输出。用二进制替换符号状态名后，即第 4 章那种真值表。$K$ 个状态需 $\lceil\log_2 K\rceil$ 个状态比特（本例 5 态 → 3 比特）。

编码可任意（000、001…），但状态编码会强烈影响实现逻辑复杂度——找最简逻辑的编码本身很有趣。有了真值表，可用第 4 章方法做组合逻辑，或干脆用 ROM。

7. 落到硬件（Now Put It in Hardware）

ROM 由当前状态与输入计算下一状态与输出。5 态用 3 比特编码 → 3 比特状态寄存器（边沿触发矩形为多比特寄存器的示意；线上斜杠 + 数字表示位宽）。

ROM 共 4 根地址输入（3 状态 + 1 输入）→ $2^4=16$ 个单元，对应真值表 16 行；每单元 4 比特（3 下一状态 + 1 输出）→ 16×4 ROM。状态寄存器仍须服从动态纪律（第 5 章末时序分析）；暂假定输入跳变已与时钟上升沿正确同步。

8. 离散状态、离散时间（Discrete State, Discrete Time）

回顾设计选择：输出仅依赖状态 → Moore；依赖状态+输入 → Mealy。$S$ 个状态比特可编码 $2^S$ 态。每多 1 个状态比特，ROM 容量翻倍——用 ROM 实现时极想减少状态比特。

波形：时钟上升沿 → 状态寄存器输出更新 → ROM 算出下一状态（本周期某时刻稳定）→ 下一上升沿装入。周而复始，跟随转移图。

9. 杂务问题（Housekeeping Issues…）

• 复位：上电需把状态寄存器置为初始态编码；常用 RESET=1 强制初态，再置 0 开始运行
• 未用编码：3 比特最多 8 态，本例只用 5 个——可改用门级逻辑；若寄存器误入未用编码，可在 ROM 中令未用态一律指向初态，避免未知行为
• 编码优化：CAD 可帮找使组合逻辑最简的状态编码
• 另一实现：移位寄存器记住最近四位，再比较是否匹配口令——无需复杂的下一状态逻辑
• 异步输入：如何保证输入跳变不破坏状态寄存器的动态纪律——本章末节讨论

10. FSM 的状态（FSM States）

• 用 $K$ 个状态比特的 FSM，转移图中状态数至多 $2^K$
• 两台 FSM 串联（第一台输出 = 第二台输入）：整体仍是 FSM；不知内部细节时，状态数上界为 $M\times N$（第一台可在任一 $M$ 态，同时第二台在任一 $N$ 态）。上界与输入位宽 $X,Y$ 无关——更宽输入只让转移标签更长，不直接告诉内部状态数

11. 我的转移图是什么？（What’s My Transition Diagram?）

黑盒 FSM：按钮 0/1，灯输出。实验一小时：按 0 灯灭，按 1 灯亮。能否确定转移图？

两个图都能匹配“短时间”观察；第二个要连按 1 四次才暴露差异。若状态数无上界，永远无法确认已穷尽全部行为。 若知上界为 $K$，并每次从初态复位：可达态都能在少于 $K$ 步到达，枚举所有长度 ≤$K$ 的输入序列即可保证访问全部状态。

12. FSM 等价（FSM Equivalence）

不同状态数的 FSM 可能等价：对外不可区分即可互换。定义：当且仅当任意输入序列在两机上产生相同输出序列时，两 FSM 等价。工程上希望找最简（最便宜）的等价机——下一例说明如何化简。

13. 造一只机器蚁（Let’s Build a RoboAnt）

机器蚁以 FSM 为脑：触角 L、R（触碰为 1）；输出 F 前进、TL/TR 左转/右转。同时请求转向与前进时先转向。触角贴墙时可转，但无法前进。任务：在无孤岛墙的迷宫中用右手定则逃出。

14. 迷失太空（Lost in Space）

初态 LOST：断言 F，一直前进直到至少一根触角碰到墙（$L$ 或 $R$ 为 1）。

15. 撞上了！（Bonk!）

碰到墙后的三种姿态：为实现右手定则，逆时针左转直到两触角都离开墙 → 增加 rotate-counterclockwise 态，断言 TL，直到 $L=R=0$。

16. 稍向右转…（A Little to the Right…）

墙已在右侧，开始用右触角沿墙走：WALL1 断言 TR+F，然后看右触角决定下一步（期望立刻再碰到墙）。

17. 再稍向左转…（Then a Little to the Left…）

右触角如期碰到 → WALL2：TL+F，再检查触角。右触角仍碰 → 继续转；左触角碰 → 内角，回到 rotate-counterclockwise 把新墙放到右侧；两触角都空 → 回到 WALL1（与墙平行）。期望沿墙时 WALL1/WALL2 交替；遇内角则旋转后继续。

18. 处理外角（Dealing With Outside Corners）

WALL1 中前进并右转后，外角处右触角可能碰不到墙。策略：CORNER 态继续右转并前进，直到右触角再次碰到拐角后的墙，再转入 WALL2。

19. 等价状态化简（Equivalent State Reduction）

找可合并、对外不可区分的状态对。两态等价当且仅当：

1. 输出相同（输出对外可见）
2. 对每种输入组合，二者转到等价的下一状态

策略：反复找等价对并合并，直到不能再合并。

20. 进化一步（An Evolutionary Step）

蚁 FSM 中仅 WALL1 与 CORNER 输出相同（皆 TR+F）。二者转移只依赖 $R$：$R=0$ 都到 CORNER，$R=1$ 都到 WALL2 → 等价，可合并为 WALL1。

5 态 → 4 态；实现从 3 状态比特降到 2 比特——少 1 比特，ROM 减半。与布尔化简类似，合并等价态可省时序硬件。

21. 建转移表（Building the Transition Table）

不用 ROM、改用门实现时：把转移图逐条写入真值表。LOST（编码 00）：$F=1$；$L=R=0$ 则下一态仍 LOST；任一触角碰 → 转到 rotate-counterclockwise（01），对应 $L,R$ 的三种组合各占一行。再类似地填完其余状态的转移。

22. 实现细节（Implementation Details）

完整表可用 don’t-care 压缩行数。再对组合逻辑各输出（2 个下一状态比特 + 3 个运动输出）写布尔方程。下一状态比特用第 4 章 K-map 找素蕴涵项覆盖，得最小 SOP；运动控制输出同法。

23. 蚁脑原理图（Ant Schematic）

各 SOP 用 AND/OR 直接实现，即得蚁脑原理图：几个 D 寄存器 + 一把逻辑门就能走出迷宫。

24. 一路都是 FSM？（FSMs All the Way Down?）

简单 FSM 可产生复杂群体行为（群集、鸟群、鱼群）；电影大战场面可想成大量并行 FSM。元胞自动机（通信 FSM 阵列）有时比解 PDE 更易建模分子约束。若允许 FSM 改自身转移表——或许可作进化的粗糙模型。FSM 无处不在。

25. 世界不跟我们的时钟跑！（The World Doesn’t Run on Our Clock!）

异步输入：跳变时刻与系统时钟完全无关（来自外界）。第 5 讲末：状态寄存器要求相对时钟上升沿满足建立/保持时间；随时可变的输入必可能违反。思路：对每个异步输入加同步器，使输出只在时钟上升沿后不久才改变。

26. 有界时间同步器（The Bounded-Time Synchronizer）

规格：输入 IN、CLK，跳变时刻 $t_{\mathrm{IN}}$、$t_{\mathrm{C}}$。

• IN 充分早于 CLK → 在 CLK 后有界时间 $t_{\mathrm{D}}$ 内输出 1
• CLK 充分早于 IN → 在 $t_{\mathrm{D}}$ 内输出 0
• 两者间隔小于 $t_{\mathrm{E}}$ → $t_{\mathrm{D}}$ 内输出 0 或 1 皆可，但须是稳定的数字电平

结论：对任意有限的 $t_{\mathrm{E}},t_{\mathrm{D}}$，即使元件 100% 可靠，也无法造出保证满足该规格的同步器——问题不可解。

27. 不可解？那不可能…（Unsolvable? That Can’t Be True…）

能否用一个 D 寄存器当同步器？取 $t_{\mathrm{D}}$ = 寄存器传播延迟，$t_{\mathrm{E}}$ = setup/hold 中较大者。满足动态纪律时输出确定；违纪时规格允许 0 或 1——看似搞定。

陷阱：数字抽象诱使我们以为违纪后 $Q$ 在传播延迟后仍必为 0 或 1。看主锁存：当 B、C 几乎同时变时未必如此。

28. 神秘的亚稳态（The Mysterious Metastable State）

主锁存是宽容 MUX，用正反馈构成双稳态。存储模式 ≈ 两门环路：约束为两门电路的 VTC（绿）以及 $V_{\mathrm{IN}}=V_{\mathrm{OUT}}$（红）。两曲线交于三点；中间交点是问题所在。

IN 与 CLK 同时变时，MUX 关闭启用反馈时 $Q$ 可能正处过渡，环路初值恰在或极近中间交点电压 → 亚稳态（metastable state）：不稳定平衡。理论上可无限停留；微小扰动会推向稳定平衡。关键：无法给系统停留在亚稳态的时间设上界。

29. 亚稳态性质（Metastable State: Properties）

• 落在数字信令的禁止区 → 非法逻辑电平；违纪后寄存器不再保证有界时间内给出数字输出
• 逻辑危害：组合门对非法输入输出不可预测，可污染状态与输出
• 电气危害：CMOS 输入在亚稳电压时 PFET/NFET 可同时导通，$V_{\mathrm{DD}}$–GND 直通，功耗尖峰
• 终将落到两稳定点之一；亚稳电压在 VTC 高增益区，一旦偏离会快速走向 0 或 $V_{\mathrm{DD}}$
• 分辨时间取决于初值离亚稳点有多近——无下界 → 分辨时间无上界；给定 $t_{\mathrm{D}}$，总有一段初值区间在时限内分不开
• 任一有限 $T$ 后仍亚稳的概率 $>0$；好消息：该概率随 $T$ 指数下降
• 每个双稳态系统至少有一个亚稳态——正反馈存储的代价

更细的数学见课程笔记第 10 章。

30. 解法：延迟提高可靠性（Solution: Delay Increases Reliability）

做法：D 寄存器同步后再加第二级寄存器，把可能亚稳的值隔离（quarantine）。第一级违纪亚稳时，第二级挡住；半周期内第二级主锁存关闭，完全不看该值。要到下一时钟边沿（整周期后）第二级才需要合法稳定输入。整周期后仍亚稳的概率可通过加长时钟周期压到任意低——不是 100% 保证，但失效间隔可达年/十年量级；无第二级可能每几小时就失败一次。

时钟周期短却要长隔离时间：可串多级隔离寄存器——决定失败概率的是“第一级亚稳 → 内部逻辑使用该信号”的总延迟。

结论：用同步寄存器隔离可能亚稳的信号；仍亚稳概率随隔离时间指数下降，可把失败率压到任意低。非绝对保证，但配合隔离策略时，亚稳态在实践中不再是问题。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L05 注解幻灯片。

源网页：5.1 Annotated Slides | Sequential Logic

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L05：时序逻辑（Sequential Logic）

本讲在组合逻辑之上引入状态（state）与存储（memory）：从电容存储与反馈双稳态，到 D 锁存器、边沿触发 D 寄存器，再到单时钟同步电路的建立/保持时间与 $t_{\mathrm{CLK}}$ 约束。

1. 还不能造的东西（Something We Can’t Build (Yet)）

上一讲学会了按功能规格做组合逻辑：输出只由当前输入决定。

但有一类简单器件做不到：灯作输出、按钮作输入——灯灭时按一下灯亮，灯亮时再按一下灯灭。输出并不只是当前输入的函数：第奇数次按下亮、偶数次灭，器件在“记住”上次是奇次还是偶次。这种依赖输入历史的器件称为有状态。

更细微的一点：关心的是按钮从松开到按下的跳变时刻，而不只是“当前是否按下”。内部状态使相同输入可产生不同输出；纯组合器件做不到。本讲要把状态写进电路。

2. 数字状态：想造什么（Digital State: What We’d Like to Build）

引入存储器抽象：用一个或多个比特编码系统当前状态，这些比特作为数字值出现在输出（图中 “Current State”）。

当前状态与当前输入一起进入一块组合逻辑，产生两组输出：

• 下一状态（next state）：比特数与当前状态相同
• 系统输出：对外可见的信号

组合逻辑的功能规格（真值表或布尔方程）规定：下一状态与系统输出如何由当前状态与当前输入决定。

存储器有两个输入：LOAD 控制何时用下一状态替换当前状态，以及给出下一状态数据的输入。周期性触发 LOAD，就得到当前状态序列；序列中每一态由上一态与触发时刻的输入决定。

含组合逻辑与存储器的电路称为时序逻辑（sequential logic）。若存储器存 $K$ 比特，可能状态数至多为 $2^K$。本章讨论如何造可加载的存储元件；下一章讨论如何系统化设计时序行为。

3. 用电容做存储（Memory: Using Capacitors）

比特已用电压表示，可考虑用电容存某电压。电容是无源二端器件：两平行板隔绝缘体，电荷 $Q$ 与电压差 $V$ 满足 $Q=CV$。接到较高电压叫充电，接到较低电压叫放电。

电容存储单元示意：电容一端接稳定参考；另一端经 NFET 开关接到 bit line；开关栅极接 word line。

• 写：把 bit line 驱动到目标电压（数字 0/1），再令 word line 为 HIGH，电容充/放到与 bit line 同压；再令 word line 为 LOW，关断开关，理想情况下电荷可一直留在内部极板。

• 读：先把 bit line 充到中间电压，再开 word line，使 bit line 与存储电容电荷共享。存 1（较高压）时电荷流向 bit line，电压略升；存 0 则略降。变化通常很小，需灵敏放大器（sense amp）检出并还原成合法数字电压。

• 优点：存储电容极小，现代 IC 可在廉价 DRAM（dynamic random-access memory）上集成数十亿比特，单位比特成本低。

• 缺点：读写需要复杂的操作，所以访问慢；必须注意在外部电噪声干扰下，小心地保持储能电容器上的电荷；NFET 关断仍有泄漏，当前技术下须约每 10 ms 刷新（refresh）——读出再写回。所以我们需要搭配精心设计的模拟电子电路（analog electronics） ^[1]。

或许我们可以通过设计一种利用“反馈”持续刷新存储信息的电路来克服电容式存储的缺点。

4. 用反馈做存储（Memory: Using Feedback）

两只组合反相器接成正反馈环：一输入为数字 0 → 其输出为 1 → 另一反相器输出为 0，又接回原输入。只要接电源与地，该配置在噪声下仍可保持；两线数字值对调也是稳定的。有两种稳定配置，称为双稳态（bi-stable）存储元件。

把两反相器看成一个系统，其 VTC 给出 $V_{\mathrm{OUT}}$ 与 $V_{\mathrm{IN}}$ 关系；输出接回输入又要求 $V_{\mathrm{IN}}=V_{\mathrm{OUT}}$。图解求交点：两端交点为稳定——$V_{\mathrm{IN}}$ 小扰动几乎不影响 $V_{\mathrm{OUT}}$，系统会回到稳态。中间交点为亚稳态（metastable）：理论上可无限停在该电压，但极小扰动就会迅速滑向某一稳态。作存储用时须避免进入亚稳态（下章再谈）。

5. 可置位存储元件（Settable Memory Element）

用 2 选 1 MUX 做可置位存储：MUX 输出作状态输出 $Q$，并回接到 MUX 的 $D_0$；$D_1$ 作数据输入；选择端作加载信号（此处称 gate，$G$）。

• $G=\mathrm{LOW}$：输出经 $D_0$ 回环，形成上节的双稳态正反馈；电路出现环路，不再是组合电路。
• $G=\mathrm{HIGH}$：输出跟随 $D_1$（数据输入）。

加载：将 $G$ 置 HIGH 足够久，使 $Q$ 有效且稳定；真值表上 $G=1$ 时 $Q$ 跟随 $D$，变化时序由 MUX 的 $t_{\mathrm{PD}}$ 决定。再把 $G$ 置 LOW，进入“记忆模式”，正反馈无限保持稳定 $Q$。

6. 新器件：D 锁存器（New Device: D Latch）

该存储器称为 D 锁存器（D latch），原理图符号如图。

• 门控 $G$ 为 HIGH：打开（open），信息从 $D$ 流向 $Q$
• $G$ 为 LOW：关闭（closed），进入记忆模式，记住 $G$ 由 HIGH→LOW 时 $D$ 上的值

右侧时序图：稳定段为恒定 LOW/HIGH，变化段画成多次跳变。$G$ 为 HIGH 时，$D$ 稳定后至多再经 $t_{\mathrm{PD}}$，$Q$ 到达新稳定值。

理论期望：$G$ 变 LOW 后，$Q$ 保持跳变瞬间 $D$ 上的值。但一般组合器件在输入跳变后，$t_{\mathrm{CD}}$ 到 $t_{\mathrm{PD}}$ 之间输出可任意变化——若 $G$ 的 1→0 使 $Q$ 短暂失效，要记的正是 $Q$ 上的值！因此必须保证 $G$ 的 1→0 不影响 $Q$。^[2]

7. 请求宽容（A Plea for Lenience）

因此，存储元件选用的是宽容的（lenient）MUX；宽容 MUX 的真值表见上图。在下列任一条件下，即使输入发生跳变，输出仍保持有效且稳定：

1. 将 $G$ 置 HIGH 以加载锁存器时：一旦 $D$ 已有效稳定满 $t_{\mathrm{PD}}$，即可保证 $Q$ 稳定有效，且取值与 $D$ 相同，与 $Q$ 的初值无关。
2. 若 $Q$ 与 $D$ 均已有效稳定满 $t_{\mathrm{PD}}$，则此后 $G$ 上的跳变不影响 $Q$——正是靠这一点，$G$ 才能做 1→0 而不污染 $Q$。
3. 若 $G$ 为 LOW，且 $Q$ 已稳定至少 $t_{\mathrm{PD}}$，则此后 $D$ 上的跳变不影响输出。

宽容性是否足以保证锁存器正常工作？还不够——除非我们小心保证信号在正确时刻稳定，才能用上 MUX 的宽容行为。

8. 还须一点纪律（… With a Little Discipline）

保证锁存器按预期工作，需按下列步骤操作：

1. 先在 $G$ 为 HIGH 时，把待存值放到 $D$；经 $t_{\mathrm{PD}}$ 后，即可保证该值在 $Q$ 上稳定有效。这就是上节条件 1。

2. 再等一个 $t_{\mathrm{PD}}$，让 $Q'$ 输入上新值的信息传遍锁存器内部电路。此时 $D$ 与 $Q'$ 都已稳定至少 $t_{\mathrm{PD}}$，从而满足上节条件 2。
   因此若 $D$ 稳定满 $2\,t_{\mathrm{PD}}$，$G$ 上的跳变就不会影响 $Q$。对 $D$ 的这一要求称为锁存器的建立时间（setup time）：即 $G$ 做 HIGH→LOW 之前，$D$ 必须已稳定有效多久。

3. 这时可将 $G$ 置 LOW，同时仍保持 $D$ 稳定有效。再经一个 $t_{\mathrm{PD}}$，让新的 $G$ 值传遍内部电路后，就满足了上节条件 3，此后 $D$ 上的跳变不再影响 $Q$。
   对 $D$ 稳定性的这一进一步要求称为锁存器的保持时间（hold time）：即 $G$ 跳变之后，$D$ 还必须继续稳定有效多久。

建立时间与保持时间合称动态纪律（dynamic discipline），锁存器要正确工作就必须遵守。

简言之，动态纪律要求：在 $G$ 发生跳变的前后，$D$ 都必须稳定有效。只要电路设计遵守动态纪律，就能保证门控做 HIGH→LOW 时，该存储元件可靠地存下 $D$ 上的信息。

9. 试一把（Let’s Try it Out!）

把锁存器用作时序系统的存储：打开锁存器（$G$ HIGH），让新状态传到 $Q$（当前状态），再经组合逻辑更新下一状态。问题：$G$ 若 HIGH 过久，系统形成环路，新状态沿环快速变化，加载计划失败。

因此 $G$ 为 HIGH 的窗口既要够长以满足动态纪律，又要够短，使锁存器在新状态绕环一圈前重新关闭。精确间隔几乎无法保证——只有时序上下界，没有精确间隔。需要的是标记某一瞬间的加载信号，而不是一段时间。

10. 不可靠的控制系统（Flakey Control Systems）

类比：收费站闸门前排队的车 = 时序逻辑中的状态序列；闸门 = 锁存器。闸门关闭时车等候；打开后第一辆驶出——但何时关闸很难：开得够久让第一辆过，又不能太久让后面的车也过。与单锁存器作存储时的问题相同。

11. 解法：擒纵策略（双闸）（Solution: Escapement Strategy (2 Gates)）

用两道闸：起初 Gate 1 开、Gate 2 关，恰允许一辆进入；某一瞬间关 Gate 1、开 Gate 2，让站内那辆驶出，并挡住后续车辆。重复两步，逐辆处理。关键：任意时刻不存在同时穿过两道闸的通路。

这与机械钟表的擒纵机构（escapement）相同：保证发条齿轮一次只进一齿，防止整天一下子转完。观察输出：Gate 2 每次打开后不久驶出一辆；车辆按 Gate 2 打开间隔通过。把该思路用于时序逻辑的存储元件。

12. 边沿触发 D 寄存器（Edge-triggered D Register）

用两个背靠背锁存器做 D 寄存器（D register）：加载信号通常叫时钟（clock）；$D$/$Q$ 角色与锁存器相同。

从外部看，$D$ 接主锁存器（master），$Q$ 接从锁存器（slave）。时钟在进主锁存器前反相：主开则从关，反之亦然——任意时刻没有从寄存器 $D$ 到 $Q$ 的通路。

时钟反相器延迟可能会引发担心：上升沿时是否会有短暂两 Gate 都 HIGH？我们可以换用“$G$ LOW 时打开、$G$ HIGH 时关闭”类型的主锁存器，往往不必另加反相器。

因锁存器内正反馈双稳态（具有两个可以长期保持的稳定工作状态），寄存器也常被称为 flip-flop （触发器）。

13. D 寄存器波形（D-Register Waveforms）

整体行为简单：时钟 0→1 上升沿采样 $D$，并保持到下一上升沿；$Q$ 即寄存器中存的值。

时钟 LOW→HIGH 为上升沿，HIGH→LOW 为下降沿。主锁存器输出记为 STAR：

• 上升沿：主由开→关，采样输入并进入记忆；时钟为 HIGH 期间 STAR 保持稳定。
• 下降沿：主打开，STAR 再跟随 $D$（延迟为锁存器 $t_{\mathrm{PD}}$）。

从锁存器：上升沿时打开，输出跟随 STAR；但时钟 HIGH 时主已关，STAR 稳定，故 $Q$ 在可能的一次跳变后也稳定。下降沿时从由开→关，采样 STAR；时钟 LOW 期间 $Q$ 保持稳定。

单独看 $Q$：只在上升沿从锁存器打开时变化，故称正边沿触发 D 寄存器（positive-edge-triggered D register）。原理图时钟端用小三角标记。

14. 关于那个保持时间…（Um, About That Hold Time…）

下降沿时从锁存器由开→关，其输入 STAR 必须满足从锁存器的建立/保持时间。麻烦在于：主同时打开，STAR 可能在时钟边沿后很快变化。主的污染延迟 $t_{\mathrm{CD}}$ 告诉我们其输出旧值在下降沿后还能稳多久；从的保持时间告诉我们边沿后其输入还须稳多久。

正确工作要求：主的 $t_{\mathrm{CD}}$ $\ge$ 从的保持时间。分析须考虑工艺偏差、温度、电源等。必要时可在主从之间加额外门延迟（如两级反相器）增大相对下降沿的污染延迟。从锁存器保持时间问题只能靠改电路设计解决。

15. D 寄存器时序（D-Register Timing）

D 寄存器时序规格小结：

• $t_{\mathrm{PD}}$：上升沿后，$Q$ 变为有效稳定的上界
• $t_{\mathrm{CD}}$：上升沿后，旧 $Q$ 仍保持有效的下界

二者均相对时钟上升沿度量。寄存器设计为宽容：若新旧 $Q$ 相同，上升沿期间 $Q$ 稳定性有保证——$t_{\mathrm{CD}}$/$t_{\mathrm{PD}}$ 仅在 $Q$ 实际变化时适用。

为保证主锁存器正确，$D$ 须满足主的建立/保持：

• $t_{\mathrm{SETUP}}$：上升沿前 $D$ 须有效稳定多久
• $t_{\mathrm{HOLD}}$：上升沿后 $D$ 须再保持多久

使用厂商库中的 D 寄存器时，要从数据手册查这四个参数，再分析整电路时序。

16. 单时钟同步电路（Single-clock Synchronous Circuits）

6.004 中使用寄存器的约定称为单时钟同步纪律（single-clock synchronous discipline）：

上图左边的电路中，带边沿触发的符号的方形表示寄存器，小云朵表示组合逻辑电路。

• 寄存器输入到输出无组合通路，整个电路无组合环。换句话说，从系统输入和寄存器输出到寄存器输入的路径不会两次经过同一组合块。
• 所有时钟器件共享同一周期时钟。使用多时钟域也可以，但跨域时序很难分析，同钟更简单。
• 各数据信号何时变化大体不重要；关键是接到寄存器输入的信号稳定够久以满足建立时间，并保持够久以满足保持时间。

选时钟周期大于“寄存器输出 → 寄存器输入”每条路径的 $t_{\mathrm{PD}}$ 再加上建立时间，即可保证遵守动态纪律：

$$t_{\mathrm{CLK}} > t_{\mathrm{PD,path}} + t_{\mathrm{SETUP}}$$

额外好处：按这种方式选时钟周期后，上升沿瞬间电路中没有其它会引入噪声的逻辑跳变，因而更新各寄存器存储状态时不应有噪声问题。^[3]

17. 单时钟系统中的时序（Timing in a Single-clock System）

分析某条路径：上游寄存器 → 组合逻辑 → 下游寄存器（逻辑输出记 STAR）。大系统有多条路径，须逐条分析以找出决定最小可用时钟周期的路径（CAD 工具常代劳）。

上升沿触发上游寄存器：$Q_{\mathrm{R1}}$ 在至少 $t_{\mathrm{CD,REG1}}$ 内保持旧值，并在 $t_{\mathrm{PD,REG1}}$ 前达到新稳定值，直至下一上升沿。组合逻辑的 $t_{\mathrm{CD}}$/$t_{\mathrm{PD}}$ 再决定 STAR 最早失效与最晚稳定的时刻。

对下游 REG2：

• $t_1$ = REG1 的 $t_{\mathrm{CD}}$ + 组合逻辑的 $t_{\mathrm{CD}}$：上升沿后 STAR 仍有效多久；须 $t_1 \ge$ REG2 的保持时间。
• $t_2$ = REG1 的 $t_{\mathrm{PD}}$ + 组合逻辑的 $t_{\mathrm{PD}}$ + REG2 的建立时间：下一上升沿最早允许发生的时刻；须 $t_2 \le t_{\mathrm{CLK}}$（时钟周期）。过早则违反 REG2 动态纪律。

每条寄存器到寄存器路径都须满足这两个不等式。$t_{\mathrm{CLK}}$ 不等式中，上游 $t_{\mathrm{PD}}$ 与下游建立时间从可用于“有用逻辑工作”的时间里抠掉，故设计者倾向选用这两项更小的寄存器。

若上下游之间没有组合逻辑（移位寄存器、数字延迟线等），第一不等式要求上游 $t_{\mathrm{CD}} \ge$ 下游保持时间；实践中污染延迟常小于保持时间，往往要插入哑逻辑（如两级反相器）制造足够 $t_{\mathrm{CD}}$。

还须考虑时钟偏斜（clock skew）：因为时钟信号到达不同寄存器存在“时间差”（即时钟偏斜），为了确保数据不报错，下游寄存器不得不预留更宽裕的“稳定观察期”（即增加了等效的建立时间和保持时间）。

时钟周期 $t_{\mathrm{CLK}}$ 刻画了系统性能。Intel 等按不同时钟频率卖处理器，例如 1.7 GHz 与 2 GHz。这些芯片有何不同？其实没有：制造工艺波动使部分芯片的 $t_{\mathrm{PD}}$ 更好；逻辑 $t_{\mathrm{PD}}$ 更小，就可取更小 $t_{\mathrm{CLK}}$、更高频率。同一设计量产许多颗，测 $t_{\mathrm{PD}}$ 后把快的挑出来当更高性能档卖——这是芯片生意挣钱的秘诀。

18. 模型：离散时间（Model: Discrete Time）

用 D 寄存器作时序系统的存储很合适：每个时钟上升沿加载下一状态，在余下时钟周期内作为当前状态出现在输出。组合逻辑用当前状态与输入计算下一状态与输出。一串上升沿与输入产生状态序列，进而产生输出序列。下一章引入有限状态机（finite state machine）抽象，便于设计时序系统。

19. 时序电路时序分析（Sequential Circuit Timing）

对图示时序系统套用上述分析（寄存器与组合逻辑时序参数如图）：

• 组合逻辑 $t_{\mathrm{CD}}$ 未给：要正确工作，寄存器与逻辑的 $t_{\mathrm{CD}}$ 之和须 $\ge$ 寄存器保持时间 → 逻辑 $t_{\mathrm{CD}}$ 至少 1 ns。
• 最小 $t_{\mathrm{CLK}}$：须大于寄存器与逻辑的 $t_{\mathrm{PD}}$ 之和再加上建立时间 → 最小时钟周期 10 ns。
• 相对上升沿，Input 的建立时间 = 逻辑 $t_{\mathrm{PD}}$ + 寄存器建立时间 = 7 ns；保持时间 = 寄存器保持时间 − 逻辑 $t_{\mathrm{CD}}$ = 1 ns（换句话说，如果 Input 在时钟上升沿后保持至少 1 ns，那么 Next State 就能在时钟上升沿后保持至少 2 ns）。这样 Next State 才能分别满足寄存器的建立/保持。

20. 小结（Summary）

本讲完成时序逻辑入门：几乎所有数字系统都是时序系统，并遵守动态纪律施加的时序约束。下次看到 “1.7 GHz 处理器” 广告，就知道 “1.7” 从何而来。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L04 注解幻灯片。

源网页：4.1 Annotated Slides | Combinational Logic

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L04：组合逻辑（Combinational Logic）

本讲介绍如何把功能规格落地为组合逻辑电路：真值表与布尔方程、积之和（sum-of-products）综合、宽门与反相逻辑、布尔化简与卡诺图、MUX / ROM 等实现策略。

1. 功能规格（Functional Specifications）

功能规格是构建组合逻辑抽象时静态纪律（static discipline）的一部分。可用自然语言描述器件行为：表达紧凑、人人能读，但措辞不严时易有歧义，也难判断是否穷尽所有情况。

更好的替代：

• 真值表（truth table）：对每种数字输入组合明确给出输出。$N$ 个数字输入 → $2^N$ 行。例：3 输入共 $2^3=8$ 行，可系统枚举，不易漏项，输出显式，歧义少。输入很多时不实用——两个 32 位加数共 64 输入，真值表需 $2^{64}$ 行；若每秒填一行，约需 5840 亿年。
• 布尔方程（Boolean equation）：用 AND、OR、XOR（二元）与 NOT（一元）由输入算输出。0 ↔ FALSE，1 ↔ TRUE。

记号：输入用名字（如 $A,B,C$）；NOT 用上划线（如 $\overline{C}$）；AND 用乘法（显式点或隐式并置）；OR 用 $+$。输入多时布尔方程更合适，也易于画成电路图。真值表与布尔方程可互化：代入输入求方程可填表；由真值表可写成积之和（sum-of-products, SOP）。

2. 一种设计路径（Here’s a Design Approach）

问：“何时 $Y=1$？”——即何时 $Y$ 为 TRUE。若第 2、4、7、8 行 $Y=1$，则方程是这四项之 OR；每一项是对应该行输入组合的积项。

例：第 2 行 $C=0,B=0,A=1$ → $\overline{C}\cdot\overline{B}\cdot A$。第 4 行 → $\overline{C}\cdot B\cdot A$，其余类似。所得恒为积之和：“和”指 OR，“积”指 AND 组。

3. 积之和的积木（Sum-of-products Building Blocks）

电路库由厂商提供，或自己用 NFET/PFET 做成 CMOS 门：

• 反相器（inverter）：输出小圆表示反相；实现 NOT
• AND：全为 1 才输出 1；库中常有 3、4 输入等
• OR：至少一个输入为 1 则输出 1；同样有多输入版本

原理图：AND 输入侧平直，OR 输入侧弯曲。

4. 直接综合（Straightforward Synthesis）

电路结构追随方程：反相器做 NOT（SOP 中常对输入取反；原理图可为每个 NOT 单独画反相器，实作可共享 $\overline{C}$ 等信号）；每个积项用多输入 AND；再用多输入 OR 合并。典型层次：反相器层 → AND 层 → OR。

传播延迟 $t_{\mathrm{PD}}$ 看似短（最长路径约反相器 + AND + OR），但宽 AND/OR 往往要多层门拼出，会增加延迟。至此已有：真值表 → SOP 方程 → 门电路。

5. 多于 2 输入的 AND / OR（ANDs and ORs with > 2 Inputs）

假设库只有 2 输入门。AND 满足结合律，可用两两 AND 任意顺序做 $N$ 路 AND；OR、XOR 同理。

• 链（chain）：$N$ 输入需 $N-1$ 个 2 输入门；$t_{\mathrm{PD}}$ 约 $N-1$ 级，随 $N$ 线性增长
• 树（tree）：先并行再合并；$t_{\mathrm{PD}}$ 约 $\log_2 N$ 级，$N$ 大时明显更快

成本（门数）两者相同。若各输入到达时间不同（如前级 $t_{\mathrm{PD}}$ 不同），晚到输入经树可能还要多级，经链可能只多一级——子电路哪种最优，取决于输入何时到达。

CMOS 中单级门天然反相，高性能更倾向 NAND/NOR（单级 CMOS）；AND/OR 常要两级（如 NAND+反相器）。NAND、NOR 不结合：$\mathrm{NAND}(A,B,C)\neq\mathrm{NAND}(\mathrm{NAND}(A,B),C)$，不能简单用 2 输入 NAND 树拼宽 NAND。

6. 更多积木（More Building Blocks）

异或（XOR）在算术、奇偶校验中很有用；Lab 2 会看到 2 输入 XOR 比 2 输入 NAND/NOR 消耗更多 NFET/PFET。任意真值表都可写成 SOP，再用 INVERTER、AND、OR 实现。

7. 万能积木（Universal Building Blocks）

仅用 2 输入 NAND 即可实现任意功能——称其为万能门（universal gate）。SOP 的各积木都有 NAND-only 等价电路；2 输入 NOR 同样万能。反相逻辑初看别扭，却是 CMOS 低成本、高性能的关键。

8. CMOS 偏爱反相逻辑（CMOS Loves Inverting Logic）

库中既有反相门（反相器、NAND、NOR），也有非反相门（缓冲器、AND、OR）。对比 4 输入 AND 的三种实现（数值以库文档为例，重在相对比较）：

非反相门常做成小而慢（MOSFET 更窄）；反相门做成快。整电路 $t_{\mathrm{PD}}$ 由最长路径决定：非关键路径可用更小更慢的门省面积。底层树电路还用到 DeMorgan 定律：$\overline{A+B}=\overline{A}\cdot\overline{B}$ 等，可把 NOR 看成带反相输入的 AND，使第一层反相输出与第二层反相输入“对消”，等价于 AND 树。

9. 宽 NAND / NOR（Wide NANDs and NORs）

库中反相门通常做到约 4 输入：4 输入 NAND 的下拉链有 4 个串联 NFET，电阻累加；加宽管子又增大面积与输入电容。尺寸–速度权衡迅速变复杂，故库常止于 4 输入，更宽由设计者用 DeMorgan：交替 NAND/NOR 树拼 8 输入 NAND、NOR 等。中间层 NOR 可视为带反相输入的 AND，整体像带反相输出的 AND 树；中间层 NAND 则对应 OR 树。

10. CMOS 积之和实现（CMOS Sum-of-products Implementation）

同一 SOP 可用两层 NAND 或两层 NOR 实现。对输出侧 NAND 用 DeMorgan 变成“带反相输入的 OR”，再与第一层反相输出对消气泡，即得：反相器层 + AND 层 + OR。NOR/NOR 同理。

NOR/NOR 往往更多反相器；但可能减轻输入负载（例：NAND/NAND 中 $A$ 接 4 个 MOSFET，NOR/NOR 中 $A$ 只经反相器接 2 个）。需要快的 AND/OR 型 SOP 时，优先试 NAND/NAND，通常比 AND/OR 明显更快。

11. 逻辑化简（Logic Simplification）

能否用更少/更小的门实现同一功能？布尔恒等式可变换表达式。归约恒等式（reduction identity）等可把含两变量、多次运算的式子压成更简单形式。例：四积项方程中，中间两项令 $\alpha=C\cdot B$，消去 $A$；再对另两项令 $\alpha=\overline{C}\cdot A$ 继续归约——运算次数可从约 14 降到约 4，电路更便宜、$t_{\mathrm{PD}}$ 更小。手工化简繁琐易错，实际多用程序；最优形式搜索随输入数超指数增长，大方程靠启发式，结果很好但不一定最优。

12. 布尔最小化（Boolean Minimization）

另一种思路：在真值表中找无关（don’t-care）情形。例如原表第 1、3 行：$A=0$、$C=0$、$Y=0$，仅 $B$ 不同 → 当 $A,C$ 皆 0 时 $B$ 无关，在压缩表中把该行的 $B$ 记为 $X$。比较 $Y$ 相同的行，可继续找出其他 don’t-care。

13. 带无关项的真值表（Truth Tables with Don’t Cares）

带 don’t-care 的表中，$Y=1$ 的行往往更少。有的行冗余：例如某行匹配的输入组合（如 011 与 111）已被其他行覆盖。由第 2、4 行导出的积项，正是用归约恒等式得到的那些积项——几何/表格视角与代数归约殊途同归。

14. 为何不一定用最小 SOP（The Case for a Non-minimal SOP）

最小电路是否总最好？看 $A=1,B=1$、$C$ 从 1→0：原先由下 AND 维持 $Y=1$，过渡后上 AND 经反相器延迟才打开，中间可能两 AND 都关，$Y$ 短暂变 0——即 毛刺（glitch），传播会耗电。若保留第三积项 $BA$，则 $A,B$ 同高时 $Y$ 与 $C$ 无关，$C$ 翻转不引起 $Y$ 毛刺。上一章称此类电路为宽容的（lenient）。

15. 卡诺图：几何方法（Karnaugh Maps）

最小化时要找可合并的相邻积项。卡诺图（Karnaugh map, K-map）把真值表排成二维：行/列用输入取值标记，格内为输出。列序用 Gray 码：相邻标签恰差一位；左右列也视为相邻（想成圆柱）。立方体上相邻的 3 位输入，在表中也相邻。

16. 扩展到 4 变量（Extending K-maps to 4-variable Tables）

4 变量：行、列皆 Gray 码；左右列、上下行相邻。6 变量需 $4\times4\times4$ 三维，难画；更多维更不现实。实践上 K-map 适合 ≤4 变量；思想可推广到更高维（计算机处理）。

17. 寻找蕴涵项（Finding Implicants）

蕴涵项（implicant）：K-map 中全为 1 的矩形区域；宽、高须为 2 的幂（1、2 或 4）。可重叠。素蕴涵项（prime implicant）：不被任何更大蕴涵项完全包含。最终最小 SOP 的每个积项对应某个素蕴涵项。

18. 寻找素蕴涵项（Finding Prime Implicants）

例：孤立的 1 → $1\times1$；右上相邻两个 1 → $1\times2$。记得左右列相邻，可得到 $2\times2$ 等。对未圈住的 1，应找包含它的最大合法蕴涵项——更大素蕴涵项对应更短积项。

19. 写出方程（Write Down Equations）

每个蕴涵项对应一个积项：只对在区域内保持不变的输入写文字。例：$A=0,B=0,C=1$ 的单格 → $\overline{A}\cdot\overline{B}\cdot C$；$1\times2$ 且 $C=0,A=1$ 不变 → $A\cdot\overline{C}$。素蕴涵项越大，积项越短。