计算机科学与技术：模拟与数字逻辑电路

1. 数字逻辑基础

计算机无法直接处理模拟信号。

2. 数制与编码

2.1 数的表示

首先是定点整数的表示：

整数原码（ $-(2^n-1)\sim 2^n-1$ ）：

$[x]_原=\begin{cases} 0 x_1 x_2\dots x_n&,x\ge 0,\\ 1 x_1 x_2\dots x_n&,x\le 0 \end{cases}$

原码的减法需要比较绝对值，用大的减小的。

整数反码（ $-(2^n-1)\sim 2^n-1$ ）：

$[x]_反=\begin{cases} 0 x_1 x_2\dots x_n&, x\ge 0\\ 1 \overline {x}_1 \overline{x}_2\dots \overline{x}_n&, x\le 0. \end{cases}$

反码的加减法直接进行，但是最高位的进位要移动到最低位上。因为运算是在模 $2^{n+1}-1$ 意义下进行的，最高位进位得到的结果是 $1$ 。

整数补码（ $-2^n\sim 2^n-1$ ）：

$[x]_反=\begin{cases} 0 x_1 x_2\dots x_n&, x\ge 0\\ 1 \overline {x}_1 \overline{x}_2\dots \overline{x}_n+1 &, -2^n<x<0,\\ 100\dots 0&,x=-2^n. \end{cases}$

由于是在模 $2^n$ 意义下进行的，因此直接进行加减法就可以。

然后是定点小数的表示，形如 $x_0\ .\ x_1x_2\dots x_n$ 。其中第 $i$ 位表示 $2^{-i}$ 。

对于定点小数的补码表示，加上的就是 $2^{-n}$ ，因为是在模 $2$ 意义下进行的。

2.2 BCD 码

Binary-Coded Decimal，即用二进制编码十进制数，核心思想是用 4 位二进制数表示 1 位十进制数。

最常用的是 8421 BCD 吗，即取前十个二进制码，剩余六个是非法码。

余 3 码（Excess-3），是 8421 码然后每个数加上 3（0011）。

然后是 2421 码和 5421 码，分别代表每一位的权值，当 $x\ge 5$ 时，第一位强制为 $1$ 。

2.3 可靠性编码

2.3.1 Gray Code

2.3.2 奇偶校验码

2.3.3 海明码

3. 逻辑代数

德摩根定理用于拆解取反，即 $\overline{AB}=\overline A + \overline B,\overline{A+B}=\overline A \cdot \overline B$ 。

反演（取反）：颠倒所有的 $+$ 、 $\cdot$ 和 $01$ 和变量得到反函数。其实就是等式两边同时取反。

对偶： $F'$ 表示将所有的 $+$ 、 $\cdot$ 和 $01$ 颠倒，得到对偶表达式，这显然是个可逆运算。最关键的作用是 $F=G\iff F'=G'$ ，比如摩根律只需要一半就可以证明另一半。

3.1 逻辑函数的表示

有三种方式去表示逻辑函数：逻辑表达式，真值表，卡诺图。注意卡诺图的顺序一般是 00 01 11 10。

首先是最小项表达式（积之和），即标准与或式，写作 $F=\sum m(为 1 的编号)$ ，编号规则为原变量视为 $1$ ，反变量视为 $0$ 。无关项以 $\sum d(\cdots)$ 表示。

最大项表达式（和之积），即标准或与式，写作 $F=\prod M(为 0 的编号)$ ，编号规则为原变量视为 $0$ ，反变量视为 $1$ 。因此我们有 $m_i=\overline M_i$ （摩根定律）。

同一个逻辑函数的两种表达式的编号是互补的，这是因为一些组合的编号会使得 $F=1$ ，集合为 $S$ ，构成了与或表达式。而其补集会使得 $F=0$ ，构成了 $\overline F$ 的与或表达式，然后两边取反右边由摩根律就得到了 $F$ 的或与表达式。出于这个事实，拿卡诺图写或与表达式只需要找 $0$ 项去写，这样就可以找到那些“编号”。

求对偶的话，换成另一种表达式，每个编号改写为 $2^n-1-i$ 。这个也是拿定义写一下就可以。

然后是用卡诺图化简逻辑函数。找大小为 $2^i$ 的矩形（可以跨过边界，变量取值是连续的就可以），写与或式就找全 $1$ 矩形去合并，可以消掉 $i$ 个变量，或与式就找全 $0$ 矩形合并。

4. 组合逻辑电路

4.1 逻辑门

基本门：与或非。
复合门：与非，或非（这两个是通用门），异或，同或（ $A\odot B=AB+\bar A\bar B$ ）。

非门后面有一个空心圈。

或门是 >= 1，异或门是 = 1，同或门是 = 或者异或门取反。

4.2 编码器

Encoder， $2^n$ 个输入， $n$ 个输出。任一时刻最多只有一个输入有效，电路输出该输入对应的 $n$ 位二进制代码。

但这样有一个问题，任一时刻必须且只能有一个输入为 1。如果同时按下多个键，输出会错误叠加。

因此通常使用优先编码器（Priority Encoder），允许多个输入同时有效，电路只对优先级最高的有效输入进行编码。最经典的（也是一般的教学案例）就是 8 线-3 线优先编码器 74LS148。

VCC 为接正极，GND 接负极。就实际上它应该长左边那样，但在教学时我们看右边那张图来方便理解它的功能。

$\overline{ST}$ 代表 selected，也即 enabled，低电平时 74LS148 工作。 $\overline{Y_S},\overline{Y_{EX}}$ 在两片级联时有用，大概是编码时 $\overline{Y_{EX}}$ 有效，开启但不编码时 $\overline{Y_S}$ 有效。

我们来看该芯片的功能表：

非常好理解，就是从 $7\sim 0$ 一个一个看过去，找到一个有效电平就编码这个东西。

为什么要设计成低电平有效？这是因为 TTL（Transistor-Transistor Logic）门电路有一个特点：如果输入引脚悬空，内部电路会使得它等效于接高电平。所以如果什么都不做，它自己就是高电平，那么设计成高电平无效就很合理了。

74LS148 的级联。

4.3 译码器

4.4 数据选择器

即多路开关，从多路数据中选择一路作为输出。

首先是集成 8 选 1 数据选择器 74LS151，根据 $A_{0\sim 2}$ （地址线）编码选择哪个信号输出，注意输出是一组 $Y,\bar Y$ ，不多说。

74LS153 是集成双 4 选 1 数据选择器，但是其地址线是共用的，输出总共有两个 $Y_1,Y_2$ 。非常牛逼：

实现任意 3 变量组合逻辑函数 $F(A,B,C)$ ，直接地址线连 $A,B$ 然后剩下的相应连 $C,\bar C,0,1$ 即可。
内部级联变成 8 选 1，大概就是让 $A_2$ 分别取正和取反接两个使能端 $E_1,E_2$ 来判断开启哪个选择器。但是这样芯片就没有使能了，需要在输出之前搞一个。
实现 4 变量的组合逻辑函数 $F(A,B,C,D)$ ，用刚才的方法让它变成 8 选 1，然后直接搞！
To be continued…

4.5 二进制加法器

4.6 竞争与冒险

由于不同信号到达的时间有延迟，信号经过不同路径到达同一点时引发“竞争”，由此产生的尖峰脉冲叫做“冒险”。不产生险象的竞争叫做非临界竞争，产生险象的竞争叫做临界竞争。

静态冒险是输出有毛刺，动态冒险是本来只有 1 次变化却出现了 3 次或多次。

如果存在 $A+\bar A,A\bar A$ ，那么存在冒险。因此可以画出卡诺图，找出所有相切的圈（两圈相邻但不重叠），此时会产生冒险。这样把产生冒险的改变的元素的这一项时其它的元素的逻辑函数加进逻辑表达式里即可。

也可能在输出端加滤波电容，将毛刺滤。

5. 时序逻辑电路

组合逻辑电路是“即时的”，输出只取决于当前输入。

5.1 触发器

触发器是一种能存储一个 bit 的基本逻辑电路。

首先是基本 RS 触发器，又叫 RS 锁存器，可以由两个与非门或两个或非门交叉耦合构成。这里给出一个与非门耦合的例子，依然是低电平有效：

那么可以看出如果 $\bar R=\bar S=0$ 那么爆炸了（所以理论上需要禁止这种情况出现，后续的改进确实避免了这一点）， $\bar =\bar S=1$ 则 $Q_{n+1}=Q_n$ ， $\bar R=1,\bar S=0$ 则置 1， $R=0,S=1$ 则置 0。

电平触发式触发器（更准确地常称为“锁存器”，Latch）是这样一个电路：在控制信号（通常是时钟或使能）的某个固定电平期间，输出会“透明”地跟随输入变化；而在另一个电平期间，输出被锁存，保持不变。

基本有四种，RS、D、JK、T。

模拟与数字逻辑电路