Computation Structures笔记

这是曾经MIT 6.004课程的教材, 但是它已经过时了. 我想MIT已不再使用这本书, 并且也没有更新这本书. 不过, 我想这本书仍然具有永恒的价值.

这是我对于本书的草率翻译, 其中有的部分使用了机器翻译. (鉴于此书内容甚多, 非我人力之所及也.)

第1章 数字抽象

复杂系统的有序设计的关键, 无论是数字系统还是其他系统, 在于将其功能分解为可以独立且简洁地规定其行为的模块. 为了促进这种功能模块化并简化每个模块的规格说明, 我们采用各种工程规范并同意遵守它们所施加的约束; 例如在编程中, 数据表示和参数传递的约定是典型的自我施加的约束. 每一种这样的规范都涉及一组基本元素, 每个元素执行某种规定的基本功能, 以及通过组合现有元素来构造新元素的规则. 工程规范的力量来自于通过将本质功能从非本质细节中抽象出来, 从而简化每个模块的功能规格说明; 例如, 对平方根过程的描述必须面对其输入和输出之间的算术关系, 但不需要处理用于表示它们的位模式.

我们可以观察到在复杂系统的结构化过程中存在两大类活动. 第一类也是更常见的一类涉及在单一规范内工作, 通过组合现有功能来定义新功能, 从而丰富其repertoire. 相应的软件类比是在特定编程语言的框架内构建一个过程库来执行各种有用的功能. 第二类更激进的结构化活动涉及使用一个规范的模块来定义和支持一个新的更高层次的抽象, 该抽象具有自己的基本元素和组合规则. 在软件设计中, 这种激进的结构化通常涉及使用较低层次的语言 (连同其支持过程库) 来实现一个较高层次的语言, 其基本元素和组合规则在某种 (也许是应用相关的) 意义上更加强大. 新层次的主要特征是它将用户与底层实现技术隔离开来, 而不是简单地为其添加新选项.

第1.1节 信息和数字抽象

第1.2节 离散变量的表示

第1.3节 组合性设备

组合性设备是数字工程领域中最简单也最根本性的抽象, 其可以被我们形式化如下. 一个组合性设备是具有以下性质的电路元素:

• 一个或多个离散值输入端子;
• 一个或多个离散值输出端子;
• 一个函数式描述, 刻画了每个可能的输入值组合所对应的每个输出的值;
• 一个时延描述, (至少)包含有从任意输入值组合中设备计算出所刻画的输出值所用的时间上界$t_{\mathrm{pd}}$.

第1.4节 静态原则: 逻辑层次

第1.5节 信息流的速率

第1.6节 转换和validity

第1.7节 逻辑族

第1.8节 数字电路实现

第1.9节 总结

第1.10节 上下文

第1.11节 问题

第2章 二进制表示与记号

$n$(二进制)位可表示$2^n$个状态. 对于通常的二进制表示$b_{n-1}\dots b_0$, 其代表了值$\sum _{i=0}^{n-1}{b}_i\cdot 2^i$. 如果我们在想象中为某个固定的间隙插入了小数点, 那么就如同通常的十进制那样, 可以表示一些有理数, 这就是所谓的定点表示.

表示有符号的整数的话, 主要有三种约定, 即2's complement, 1's complement和sign/magnitude. 这三种表示的最高位都用来指示正负, 0表示正, 1表示负. 正数的情况下, 都是通常的无符号表示.

或许最直接的方式就是sign/magnitude. 除了最高位指示正负之外, 其余位就和通常表示一样指示大小. 例如, 1101可以表示$-5$.

对于1's complement表示而言, 负数的话, 在sign/magnitude的基础之上, 除了最高位全部取反, 即0变成1, 1变成0. 例如, 1010可以表示$-5$.

第3章 组合性设备与电路

第4章 序列和状态

第5章 数字系统的合成

第6章 有限状态机器

第7章 控制结构与自律

第8章 性能度量与取舍

第9章 通信: 问题和结构

第10章 解释

第10.1节 Turing机器和可计算性

第10.2节 通用性 (universality)

第10.3节 不可计算函数

第10.4节 解释和编译的对比

第10.5节 上下文

第11章 微解释器架构