Computation Structures笔记

第1章数字抽象

第1.1节信息和数字抽象

第1.2节离散变量的表示

第1.3节组合设备

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

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

传播延迟 (propagation delay)

t_{pd}

的通常解释为, 每当特定的输入值组合应用于设备并维持至少

t_{pd}

秒, 那么相应的输出值集合就会出现. 而且, 这些输出值至少在输出端能够维持到输入改变的时候. 因此, 一集输入值应用

t

秒将导致相应的输出值至少维持

t - t_{pd}

秒. 注意一下,

t_{pd}

是新输入值反映到输出端所需的最大用时, 一般而言最小用时默认为零. 后一个假设带来的后果之一在于输出值总是立即被任何输入的改变所污染, 不管

t_{pd}

如何.
组合设备的重要性质在于其互联以合成新的组合函数的简单性. 特别地, 新的组合设备可由组合无环路电路中的组合元素得到, 只要小心不将输出连接在一起. 更精确地说, 我们可以利用基本的复合规则构造组合设备:

第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$ .

Computation Structures笔记

第1章数字抽象

第1.1节信息和数字抽象

第1.2节离散变量的表示

第1.3节组合设备

第2章二进制表示与记号

第3章组合设备与电路

第4章序列和状态

第5章数字系统的合成

第6章有限状态机器

第7章控制结构与自律

第8章性能度量与取舍

Computation Structures笔记

第1章 数字抽象

第1.1节 信息和数字抽象

第1.2节 离散变量的表示

第1.3节 组合设备

第2章 二进制表示与记号

第3章 组合设备与电路

第4章 序列和状态

第5章 数字系统的合成

第6章 有限状态机器

第7章 控制结构与自律

第8章 性能度量与取舍

第1章数字抽象

第1.1节信息和数字抽象

第1.2节离散变量的表示

第1.3节组合设备

第2章二进制表示与记号

第3章组合设备与电路

第4章序列和状态

第5章数字系统的合成

第6章有限状态机器

第7章控制结构与自律

第8章性能度量与取舍