Digital Circuit

Credit to《Digital Design and Computer Architecture, Second Edition》🤯 Let’s quickly review this subject. The diagram is powered by @drawio

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio

1. Logic Gates

第一章主要认识最基础的逻辑门元件，然后熟悉其对应的真值表(Truth Table),主要是为第二章的组合电路(combinational circuit)做铺垫。

NOT 门（非门）: 输出是输入的逻辑反， $Y = \neg A$

BUF 门（缓冲器）: 输出与输入相同，用于信号强化。$Y = A$

AND 门（与门）: 所有输入均为1时，输出才为1。$Y = A \cap B$

OR 门（或门）: 任意输入为1时，输出为1。$Y = A \cup B$

NAND 门（与非门）: 与门输出取反。 $ Y = \neg (A \cap B) $

NOR 门（或非门）: 或门输出取反。 $ Y = \neg (A \cup B) $

XOR 门（异或门）: 相异为1，相同为0。 $ Y = A \oplus B $

XNOR 门（同或门）: 相同为0，相异为1。 $ Y = \neg (A \oplus B) $

三态缓冲器（tristate buffer） 是一种数字电路元件，其输出可以处于三种状态之一：高电平（1）、低电平（0）或高阻态（Z）。高阻态表示输出像断开一样，不驱动任何电流，可以用于总线控制等应用。

高水平有效（Active High）

在高水平有效的三态缓冲器中，当控制信号为高电平（1）时，缓冲器输出有效，即输出输入信号的值。当控制信号为低电平（0）时，缓冲器输出高阻态（Z）。

• 控制信号 = 1：输出 = 输入信号
• 控制信号 = 0：输出 = 高阻态（Z）

低水平有效（Active Low）

在低水平有效的三态缓冲器中，当控制信号为低电平（0）时，缓冲器输出有效，即输出输入信号的值。当控制信号为高电平（1）时，缓冲器输出高阻态（Z）。

• 控制信号 = 0：输出 = 输入信号
• 控制信号 = 1：输出 = 高阻态（Z）

2. Combinational Logic Circuit

组合逻辑电路（Combinational Logic Circuit）是一种数字电路，其中输出仅依赖于当前输入，而不依赖于之前的输入状态。这意味着组合电路没有存储元件，因此它没有记忆功能。其主要特性包括：

• 无记忆功能：输出仅由当前输入决定，与之前的输入无关。

• 固定的逻辑功能：根据输入信号的组合，输出信号以确定的方式变化。

• 构建简单：组合电路通常由基本逻辑门（如AND、OR、NOT、NAND、NOR、XOR、XNOR）构建，可以用来实现任意逻辑功能。

在有逻辑门的基础知识下，还需要有布尔表达式以及卡诺图的基础下才能完成组合电路的设计。

2.1 Boolean Equation

与或式（Sum of Products, SOP） 是一种布尔表达式形式，表示多个与项（积项）之间的或操作。每个积项由一个或多个变量通过与操作连接而成。与或式通常用于表达布尔函数的标准形式之一。例如：

$ Y = A \cdot B + \overline{A} \cdot C + B \cdot \overline{C} $

或与式（Product of Sums, POS） 是布尔表达式的另一种形式，表示多个或项（和项）之间的与操作。每个和项由一个或多个变量通过或操作连接而成。或与式也常用于表达布尔函数的标准形式之一。例如：

$ Y = (A + B) \cdot (\overline {A} + C) \cdot (B + \overline{C}) $

最小项 (Minterms) 是布尔函数的标准形式之一，其中每个最小项对应一个输出为1的输入组合。最小项由所有变量的与运算构成，每个变量可能是原变量或其补变量。通俗解释就是输出为1对应积项为1的累加。

示例：考虑一个布尔函数 ( F(A, B, C) )：

• 当 ( A = 1 ), ( B = 0 ), ( C = 1 ) 时，最小项为 $ ( A \cdot \overline{B} \cdot C )$
• 当 ( A = 0 ), ( B = 1 ), ( C = 0 ) 时，最小项为 $ ( \overline{A} \cdot B \cdot \overline{C} )$

假设布尔函数在以下输入组合下输出为1：

A	B	C	F
0	0	1	1
0	1	0	1
1	0	1	1

相应的最小项表示为：

$ F(A, B, C) = \overline{A} \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C $

最大项 (Maxterms) 是布尔函数的另一种标准形式，其中每个最大项对应一个输出为0的输入组合。最大项由所有变量的或运算构成，每个变量可能是原变量或其补变量。通俗解释就是输入为0所对应的和项为0的累乘

示例：同样考虑布尔函数 ( F(A, B, C) )：

这两个组合对应的最大项为：

• 当 ( A = 0 ), ( B = 0 ), ( C = 0 ) 时，最大项为$ (A + B + C) $
• 当 ( A = 1 ), ( B = 0 ), ( C = 1 ) 时，最大项为$ (\overline{A} + B + \overline{C} ) $

假设布尔函数 ( F(A, B, C) ) 在以下输入组合下输出为0：

A	B	C	F
0	0	0	0
1	1	0	0

因此，相应的最大项表达式为：

\[ F(A, B, C) = (A + B + C) \cdot (\overline{A} + \overline{B} + C) \]

总结

• 最小项：布尔函数输出为1时，对应输入组合的与运算。
• 最大项：布尔函数输出为0时，对应输入组合的或运算。

这些概念在布尔代数和数字电路设计中非常有用，也是这门课的高频考点

2.2 Boolean Operation Rules

布尔运算的基本定律，和卡诺图一样，是逻辑电路化简的主要手段

2.2.1 交换律（Commutative Law）

交换律表示在布尔运算中，操作数的位置可以互换。

• 与运算：$ A \cdot B = B \cdot A $
• 或运算：$ A + B = B + A $

2.2.2 结合律（Associative Law）

结合律表示在布尔运算中，操作数的组合方式不影响运算结果。

• 与运算：$ (A \cdot B) \cdot C = A \cdot (B \cdot C) $
• 或运算：$ (A + B) + C = A + (B + C) $

2.2.3 分配律（Distributive Law）

分配律表示一种运算可以分配到另一种运算上。

• 与对或：$ A \cdot (B + C) = (A \cdot B) + (A \cdot C) $
• 或对与：$ A + (B \cdot C) = (A + B) \cdot (A + C) $

2.2.4 吸收律（Absorption Law）

吸收律表示通过某些布尔运算可以简化表达式。

• $ A + (A \cdot B) = A $
• $ A \cdot (A + B) = A $

2.2.5 合并律（Combining Law）

合并律表示布尔变量和其补变量的某些组合具有特定的结果。

• $ A + \overline{A} = 1 $
• $ A \cdot \overline{A} = 0 $

2.2.6 一致律（Identity Law）

一致律表示布尔变量与1和0的运算结果。

• 与1：$ A \cdot 1 = A $
• 与0：$ A \cdot 0 = 0 $
• 或1：$ A + 1 = 1 $
• 或0：$ A + 0 = A $

2.2.7 德摩根律（De Morgan’s Laws）

德摩根律表示对布尔表达式取反的规则。

• $ \overline{A \cdot B} = \overline{A} + \overline{B} $
• $ \overline{A + B} = \overline{A} \cdot \overline{B} $

2.2.8 部分二级公式推导

• $ A + \overline{A}B = A + B$

证明: $A(1 + B) + {A}B = A + AB + \overline{A}B = A + B $

• $ (A + B) \cdot (A + C) = A + (B \cdot C) $

证明: $ AA + AC + AB + BC = A + AB + AC + BC = A(1 + B + C) + BC = A + BC $

• $A \cdot (A + B) = A$

证明: $AA + AB = A + AB = A(1 + B) = A$

• $BC + B\overline{C} = B$

证明: $B \cdot (C + \overline{C}) = B \cdot 1 = B$

• $(A + B) \cdot (A + \overline{B}) = A$

证明: $AA + A\overline{B} + AB + B\overline{B} = A + A(B + \overline{B}) = A + A = A$

• $AB + \overline{A}C + BC = AB + \overline{A}C$

证明关键：使用吸收律 $A + AB = A$, 推广为$AB + ABC = AB$

$$
\begin{aligned}
&AB + \overline{A}C + BC \\
&= AB + \overline{A}C + (A + \overline{A})BC \\
&= AB + \overline{A}C + ABC + \overline{A}CB \\
&= AB + ABC + \overline{A}C + \overline{A}CB \text{(使用推广公式)} \\
&= AB + \overline{A}C
\end{aligned}
$$

根据吸收律可继续推广下去：
$$AB + \overline{A}C + BC\cdot(\text{其他任何项}) = AB + \overline{A}C $$

在表达式中，无论包含 $B$ 和 $C$ 的项如何复杂（例如 $BCDEFGH$），它都不会改变整个表达式的最终结果。

渲染上述公式太折磨了！修考一般不考如此复杂的化简，一般掌握K-Map化简足够应付

2.3 K-Map

在绘制卡诺图的时候需要用到格雷码的表格。首先引入一个格雷码的概念。

2.3.1 Gray Code

格雷码（Gray Code）是一种特殊的二进制编码方式，其特点是相邻的两个数码之间仅有一位二进制数不同。格雷码的发明即是用来将误差之可能性缩减至最小，编码的方式定义为每个邻近数字都只相差一个位元，因此也称为最小差异码，可以使装置做数字步进时只更动最少的位元数以提高稳定性。

格雷码的特性

• 相邻差一位：每个相邻编码仅一位不同，减少了转换时的误差风险。
• 非权重编码：格雷码不按照传统二进制编码的权值（如 $1, 2, 4, 8, \dots$）累加。

2 位格雷码卡诺图

	0	1
0	00	01
1	11	10

3 位格雷码卡诺图

	00	01	11	10
0	000	001	011	010
1	110	111	101	100

4 位格雷码卡诺图

	00	01	11	10
00	0000	0001	0011	0010
01	0110	0111	0101	0100
11	1110	1111	1101	1100
10	1010	1011	1001	1000

上述表格，无论是以x轴对称，或者y轴对称，或者中心对称，均只有1位的差异

2.3.2 卡诺图化简步骤

1. 构建 K 图：根据布尔函数的输入变量数量，构建相应大小的 K 图：

   • 2 位变量：4 格（2×2）
   • 3 位变量：8 格（2×4）
   • 4 位变量：16 格（4×4）

横轴和纵轴的变量顺序需按照格雷码排列，以确保相邻格子之间只有一个变量不同。

2. 填写真值表和无关项：

   • 根据逻辑函数或真值表，在 K 图中标记输出为 1 的位置。
   • 将无关项标(Don’t Care Conditions)记为 X。无关项是那些对最终结果没有影响的输入组合，可以被自由选择为 1 或 0，以帮助扩大合并区域。

3. 寻找最大合并区域：

   • 在 K 图中，寻找可以合并的 1 和 X 区域。合并的目标是形成2 的幂次方大小的区域（例如 1、2、4、8 等格），并使每个 1 尽量包含在最大的区域中。
   • 合并时遵循以下规则：
     • 只允许合并相邻的 1 和 X（上下、左右、包围环绕相邻）。
     • 尽量优先选择包含更多无关项 X 的区域，以增加合并区域的大小。
     • 合并区域可以是矩形、正方形，甚至是环绕 K 图的封闭区域。

4. 合并相邻项：

   • 每个合并区域中的变量中，如果某个变量在区域内既有 0 又有 1，则忽略该变量（因为它在该区域中无关紧要）。
   • 将每个合并区域的共同变量提取为一个积项。对于每个变量：
     • 如果变量在区域内始终为 1，则使用原变量（如 $A$）。
     • 如果变量在区域内始终为 0，则使用其反码（如 $\overline{A}$）。

5. 写出最简化表达式：

   • 将所有合并区域的积项求和，得到逻辑函数的最简化形式。
   • 所有包含在化简表达式中的项应尽量少，以确保表达式是最简形式。

多练多化简就行了，没什么难度

2.4 常见数字模块

这一小节跟计算机组成中的算术运算关联度很高，数字电路就是来讲解计算机所呈现出来的算术运算在底层是如何用逻辑元器件实现的。

2.4.1 Half Adder

半加器 (Half Adder) 是一个基本的数字电路，用于计算两个单比特二进制数的和。它的功能是执行二进制加法，并且产生两个输出：

• Sum：表示两个输入二进制数加法的结果（不考虑进位）。这里用$S$来表示和。
• Carry：表示加法结果中产生的进位。这里用$Cout$来表示产生的进位了。

根据如下K-Map我们可以得出和与进位的表达式，分别为：$S = A \oplus B$ , $Cout = A\cdot B$，再把组合电路进行封装📦(encapsulation)可以得到半加器这个电路元件

2.4.2 Full Adder

全加器 (Full Adder) 是数字电路中的一种基本元件，用于对二进制数进行加法运算。与半加器（Half Adder）相比，全加器可以对两个二进制数和一个进位位进行加法运算，并输出结果和新的进位位。

全加器的输入包括三个位：

• A（第一个加数位）

• B（第二个加数位）

• Cin（输入进位位）

全加器的输出包括两个位：

• S（和位）：表示加法结果的当前位。

• Cout（输出进位位）：表示加法结果的进位位。

首先分析真值表写出最小项表达式，对于$S$有：

$$
\begin{aligned}
S &= \overline{A} \cdot B \cdot \overline{C_{in}} + A \cdot\overline{B} \cdot \overline{C_{in}} + \overline{A} \cdot \overline{B} \cdot C_{in} + A \cdot B \cdot C_{in} \\
&= \overline{C_{in}}(A \oplus B) + C_{in} \overline{(A \oplus B)} \\
&= A \oplus B \oplus C_{in}
\end{aligned}
$$

对于$C_{out}$有：

$$
\begin{aligned}
C_{out} &= AB \overline{C_{in}} + \overline{A}BC_{in} + A \overline{B}C_{in} + ABC_{in} \\
&= AB + C_{in}(A \oplus B)
\end{aligned}
$$

思考🤔 ：为什么黑书给的是 $C_{out} = AB + AC_{in} + BC_{in}$ ，这时候可以借助K-Map化简：如下图所示

根据K-Map化简，我们的全加器的画法会得出上图的电路，而如果根据真值表进行表达式化简，我们会得到下图的全加器。

我们可以用2个半加器和一个或门封装成一个全加器,具体的计算过程就不赘述了，这是修考重点！

2.4.3 Ripple-Carry Adder

Ripple-Carry Adder （行波进位加法器）是一种用于二进制数加法的简单组合逻辑电路，由多个一位全加器（Full Adder）级联而成，每个全加器负责处理输入位和进位。

1. 组成结构

   • Ripple-Carry Adder 包括 $n$ 个全加器，用于计算 $n$ 位二进制数的加法。
   • 每个全加器接收两个输入位 $A[i]$ 和 $B[i]$，以及前一位的进位 $C[i]$。
   • 输出为和 $S[i]$ 和进位 $C[i+1]$。

2. 进位传播

   • 第一个全加器处理最低有效位 $A[0]$ 和 $B[0]$ 以及初始进位（通常为 0），产生和 $S[0]$ 和进位 $C[1]$。
   • 进位 $C[1]$ 传递到下一个全加器，依次类推，直到最高有效位。

3. 优缺点

   • 优点

     • 设计简单，硬件实现容易。

   • 缺点

     • 进位传播延迟：每个全加器必须等待前一级的进位信号，导致延迟随位数线性增长，影响运算速度。

   Ripple-Carry Adder 适用于简单、低速应用；但无法满足更高速的加法需求。

2.4.4 Carry-Lookahead Adder (CLA)

Carry-Lookahead Adder (CLA) ，即先行进位加法器，是一种改进的加法器，用于快速执行二进制加法，解决 Ripple-Carry Adder 中进位传播延迟的问题。

Carry-Lookahead Adder 通过并行计算进位信号，而不依赖逐级传播，从而显著提高速度。其核心思想是利用生成信号和传播信号：

1. 生成信号 (Generate) ：表示某一位的加法会直接产生一个进位：
   $G_i = A_i \cdot B_i$

2. 传播信号 (Propagate) ：表示某一位的加法会将来自上一位的进位传递下去：
   $P_i = A_i + B_i$

3. 进位计算公式 ：根据生成和传播信号，计算每一位的进位：
   $C_{i+1} = G_i + P_i \cdot C_i$ 其中，$C_0$ 是初始进位。

推导证明：
根据前面全加器的结论，我们有：

1. 初始公式
   $$C_{i + 1} = A_{i} \cdot B_{i} + (A_{i} + B_{i}) \cdot C_{i}$$

2. 引入生成信号和传播信号(都是已知信号)
   $$G_{i} = A_{i} \cdot B_{i}$$
   $$P_{i} = A_{i} + B_{i}$$

3. 公式代换
   $$C_{i + 1} = G_{i} + P_{i} \cdot C_{i} \quad \text{(用 $P_{i}$ 代换 $(A_{i} + B_{i})$)}$$

那么我就可以用已知的输入 $A_{0}$ ~ $A_{n-1}$ 和 $B_{0}$ ~ $B_{n-1}$ 以及 $C_{0}$ 来确定进位是什么了。比如：

$$C_{1} = G_{0} + P_{0} \cdot C_{0}$$

$$C_{2} = G_{1} + P_{1} \cdot C_{1} = G_{1} + P_{1} G_{0} + P_{1}P_{0}C_{0}$$
不断迭代我们可以得出 $C_{3}$ 和 $C_{4}$ ，甚至到 $C_{n-1}$ ，但是！考虑到电路的复杂程度和电路成本的情况下，我们可以稍微妥协一下，采用分块的策略，比如实现一个32bit的加法器，我们可以将四个全加器分成一个块使用上面推导出来的门电路封装成一个块打包好。然后我们就可以迅速确定当前块的进位，减少等待进位的时间。在不考虑其他门延迟的情况下

• 不分块的情况下：需要等32次进位的传递
• 4个为一块的情况下：只需要等$32/4 = 8$次进位传递

优点

• 减少延迟：进位计算是并行完成的，速度显著快于 Ripple-Carry Adder。
• 高效的硬件实现：适合多位二进制数加法的高速场景。

缺点

• 硬件复杂度增加：需要额外的逻辑电路来计算生成和传播信号，随着位数增加，复杂性迅速提高。
• 功耗较高：更多逻辑门导致功耗增加。

Carry-Lookahead Adder 是一种高效的加法器设计，常用于高速处理器中。相比 Ripple-Carry Adder，它通过并行化进位计算显著提高了运算速度，但也牺牲了一定的硬件简单性。

2.4.5 Half Subtractor

半减法器（Half Subtractor）可以对两个单个位的二进制数进行减法运算。它有两个输入：被减数$A$和减数$B$，输出包括差值（Difference, $D$）和借位（Borrow, $B_{0}$）。

• 差值 $D = A \oplus B$

• 借位$B_{0} = \overline{A}B$

2.4.6 Full Subtractor

全减法器（Full Subtractor）可以对两个单个位的二进制数以及一个借位输入进行减法运算。它有三个输入：被减数$X$，减数$Y$，来自低位借位输入（Borrow_in, $B_{in}$），输出包括差值（Difference, $D$）和向高位的借位输出（Borrow_out, $B_{out}$）。

差值$D = X ⊕ Y ⊕ B_{in}$

借位输出$
B_{out}= \overline{X}B_{in} + \overline{X}Y + YB_{in}
$

上述公式可以通过真值表和K-map得出，这里就省略了

Q：如何用N-bit全加器实现全减器？

计算机中的加减运算都是通过补码进行的，根据补码运算有$A - B$ 实现的时候可以转化为$A + (-B)$, 我们又有 $\overline{B} + 1 = -B$，所以$Y = A - B = A + \overline{B} + 1$

2.4.7 Multiplexer

复用器(Multiplexer)是一种数字电路元件，它的主要功能是将多个输入信号中的一个传递到输出端。复用器可以被视为一个多路选择开关，通过控制选择信号选择特定的输入线路。

工作原理：

• 输入信号：有 $2^n$ 个输入信号线，每条线路可传递一个信号。
• 选择信号：通过 $n$ 条选择线决定选取哪一个输入信号。
• 输出信号：仅有一个输出，输出选定的输入信号。

复用器的输出可表示为：
$$
Y = I_i \quad (i \text{由选择信号确定})
$$
其中 $I_i$ 是第 $i$ 个输入。下图是一个用门电路设计2:1 MUX并封装的过程

基本结构：

• 数据输入端（Data Inputs）：多路信号的输入端口。
• 选择端（Select Lines）：控制信号，决定选用哪个输入。
• 输出端（Output Line）：传递选定信号的端口。

例如：
对于一个 4路复用器（4-to-1 MUX）：

• 有 4 个输入线：$I_0, I_1, I_2, I_3$。
• 有 2 个选择线：$S_1, S_0$。
• 有 1 个输出线：$Y$。

输出由选择信号 $S_1$ 和 $S_0$ 确定：

$$
Y =
\begin{cases}
I_0, & \text{if } S_1S_0 = 00 \\
I_1, & \text{if } S_1S_0 = 01 \\
I_2, & \text{if } S_1S_0 = 10 \\
I_3, & \text{if } S_1S_0 = 11
\end{cases}
$$

通过增加选择信号线数，复用器可以扩展为更大的多路选择器（如 8-to-1、16-to-1）。

2.4.8 Decoder

译码器是一种组合逻辑电路，其主要功能是将输入的二进制代码转换为独热码（one-hot code），即在输出中只有一条线路为高电平，其余为低电平。

独热码工作原理:如果有 $n$ 个类别，则需要一个长度为 $n$ 的二进制向量。对应某个类别的位置为1，其余位置为0。例如，对于3个类别：A, B, C：

• 类别 A 编码为：$[1, 0, 0]$
• 类别 B 编码为：$[0, 1, 0]$
• 类别 C 编码为：$[0, 0, 1]$

译码器工作原理

• 输入信号：有 $n$ 条输入信号线，用于表示二进制编码。
• 输出信号：有 $2^n$ 条输出信号线，每个输出对应一种输入组合。
• 控制信号（可选）：部分译码器可能需要使能信号（Enable），用于控制译码器的工作状态。

译码器根据输入信号的值，激活唯一对应的输出线。例如：

• 输入：$00, 01, 10, 11$
• 输出：$Y_0, Y_1, Y_2, Y_3$ 依次被激活。

译码器基本结构

对于一个 $n$ 位输入的译码器：

• 有 $2^n$ 个输出信号线。
• 每个输出信号线对应一个输入组合。

例如，一个 2-to-4 译码器（2位输入，4个输出）：

• 输入：$A_1, A_0$。
• 输出：$Y_0, Y_1, Y_2, Y_3$。
• 输出逻辑：
  $$
  Y_0 = \overline{A_1} \cdot \overline{A_0}, \quad
  Y_1 = \overline{A_1} \cdot A_0, \quad
  Y_2 = A_1 \cdot \overline{A_0}, \quad
  Y_3 = A_1 \cdot A_0
  $$

译码器是数字电路中重要的基础模块，用于信号的解码与路由。

2.5 传播延迟和最小延迟

传播延迟（Propagation Delay, $t_{pd}$）

• 定义：信号从输入端变化到输出端完全稳定所需的时间。对于组合电路来说就是关键路径上面每一个元件的传播延迟之和
• 影响因素：
  • 器件特性：如晶体管的开关速度、驱动能力。
  • 负载电容：较大的负载电容会增加传播延迟。
  • 电路拓扑：更复杂的路径结构会增加延迟。
• 意义：传播延迟决定了电路的速度性能，即最大运行频率。

最小延迟（Contamination Delay, $t_{cd}$）

• 定义：信号在电路中传输所需的最短时间，反映信号可能在某些路径上过快到达输出端的时间。对于组合电路来说是最短路径上面每个元件的最小延迟之和。
• 影响因素：
  • 布线长度和材料特性。
  • 逻辑门数量与优化设计。
• 意义：
  • 保持时间（Hold Time）违规：最小延迟可能导致竞争冒险或保持时间问题。
  • 必须确保最小延迟不会破坏电路的时序完整性。

Note: 每个门的传播延迟和最小延迟要看参数表,而且传播延迟和最小延迟这个问题非常艰深…

2.6 Glitch

毛刺（Glitch） 是数字电路中由于信号传播延迟或竞争冒险导致的短暂错误信号脉冲，通常表现为在信号稳定之前出现的意外高电平或低电平跳变。

产生原因：

• 竞争冒险（Hazards）：当多条信号路径的传播延迟不一致时，可能导致某一时刻输出信号短暂错误。
• 门延迟： 逻辑门的延迟导致信号在不同路径上到达输出端的时间不同。
• 不完全同步：异步信号未正确对齐，导致输出出现瞬时错误信号。

为了消除毛刺，可以通过添加冗余项优化逻辑表达式，确保信号在所有可能的变化路径中保持稳定。

步骤：

• 构造卡诺图：根据真值表将逻辑表达式填入卡诺图。
• 标记相邻格子：将输出为“1”的相邻单元块分组，覆盖现有的逻辑区域。
  检查是否有相邻的“1”之间存在空隙（可能导致冒险）。
• 添加冗余项：对于无法完全覆盖的相邻“1”之间的空隙，添加额外的逻辑项来补充。
  确保每一个相邻的“1”都连通，避免由于输入信号变化导致逻辑的不连续。
• 生成优化后的逻辑表达式：将包含冗余项的逻辑表达式写出并实现。

通过使用卡诺图消除毛刺的关键是：

1. 识别相邻逻辑之间的不连续性。
2. 添加冗余项确保逻辑表达式的稳定性。
3. 优化后可减少信号跳变，避免毛刺的产生。

3. Sequential Logic Circuit

时序逻辑电路（Sequential Logic Circuit） 是一类输出不仅取决于当前输入，还与电路的历史状态相关的电路。它通过存储元件（如触发器、锁存器等）记录状态，具有记忆功能。

时序逻辑电路特点:

• 记忆功能：与组合逻辑电路不同，时序逻辑电路可以存储数据。
• 状态变化：状态的变化通常由时钟信号控制，随着时钟信号的边沿（上升沿或下降沿）进行更新。
• 输出依赖性：输出依赖于当前输入和之前的状态。

3.1 Latch

锁存器（Latch）是一种基本的存储元件，用于存储一个单个位的二进制信息。它的输出状态会随输入信号的变化而更新，具体取决于使能信号（通常称为控制信号或使能信号）。

工作方式为电平触发： 锁存器根据控制信号的电平（高电平或低电平）决定是否更新输出。

• 当使能信号为有效电平时，输出跟随输入变化。
• 当使能信号为无效电平时，锁存器保持当前状态（记忆功能）。

1. 锁存器类型：

• SR锁存器（Set-Reset Latch）：

  • 基于两个交叉耦合的与非门（NAND）或或非门（NOR）构成。
  • 通过 $S$（置位）和 $R$（复位）信号控制状态。
  • 存在不允许 $S = R = 1$ 的无效状态（对于NOR实现）。

• D锁存器（Data Latch）：

  • 又称为数据锁存器。
  • 有效控制信号时，输出 $Q$ 跟随输入 $D$；无效时，输出保持不变。

• JK锁存器：

  • 改进了SR锁存器的无效状态问题，能够实现翻转（Toggle）功能。

2. 锁存器特点：

• 电平敏感：锁存器会在控制信号有效的整个时间内更新状态，而不是像触发器那样在时钟边沿更新。
• 记忆功能：能够存储当前状态，直到输入或控制信号改变。

3. 锁存器应用

• 数据暂存：存储单个位的信息。
• 寄存器的构成：多个锁存器组合可以组成寄存器，用于数据存储和处理。
• 时序电路：如简单的状态存储元件。

锁存器是电平触发的基本存储元件，可以根据输入和使能信号存储信息或保持状态。其在数字电路中的作用类似“开关”，用以暂存和传递数据。

3.1.1 SR锁存器（Set-Reset Latch）

SR锁存器是一种基本的锁存器类型，用于通过置位信号（Set）和复位信号（Reset）控制输出状态。它是由两个交叉耦合的逻辑门（通常是 NAND 或 NOR 门）构成的。

SR Latch工作方式：

• 输入信号：
  • $S$（Set）：置位信号，用于将输出 $Q$ 设置为高电平（1）。
  • $R$（Reset）：复位信号，用于将输出 $Q$ 设置为低电平（0）。
• 输出信号：
  • $Q$：当前状态输出。
  • $\overline{Q}$：$Q$ 的反相输出，满足 $Q \cdot \overline{Q} = 0$。

SR 锁存器的状态随 $S$ 和 $R$ 的变化而更新，具体规则如下：

$S$	$R$	$Q$	$\overline{Q}$	状态
0	0	保持	保持	保持当前状态
0	1	0	1	复位（Reset）
1	0	1	0	置位（Set）
1	1	无效	无效	无效状态（禁止）

SR Latch特点：

• 电平敏感：
  SR锁存器根据 $S$ 和 $R$ 的电平信号控制输出状态。
• 无效状态：
  当 $S = 1$ 且 $R = 1$ 时，$Q$ 和 $\overline{Q}$ 都为 0，这种状态被定义为无效状态，通常在设计中需要避免。

SR Latch实现： SR锁存器可以通过以下两种逻辑门实现：

• NOR门实现：：
  • 当 $S = 1$ 时，置位 $Q = 1$；当 $R = 1$ 时，复位 $Q = 0$。
• NAND门实现：：
  • 信号逻辑与 NOR 门相反，通常 $S$ 和 $R$ 信号需要取反。

SR Latch应用：

• 状态存储： 记录电路中的状态信号。
• 控制电路： 用于实现简单的时序控制功能。
• 锁存电路： 用作更复杂存储元件（如触发器）的基础单元。

SR锁存器是最基本的锁存器，通过置位和复位信号控制输出状态，但需要避免无效状态。它在简单存储和状态保持电路中有广泛应用。

还有一种是由NAND门构成的SR锁存器，注意真值表和由NOR门构成的SR锁存器的区别

$S$	$R$	$Q$	$\overline{Q}$	状态
0	0	1	1	无效状态（禁止）
0	1	1	0	复位（Reset）
1	0	0	1	置位（Set）
1	1	保持	保持	保持当前状态

3.1.2 D锁存器（Data Latch）

D锁存器是一种基本的时序逻辑电路，用于存储1位二进制数据。它根据时钟信号的状态决定是否允许数据输入被存储。

1. 输入和输出：

   • D（Data）输入：需要存储的数据。
   • 使能信号（Enable/Clock，通常用E或EN表示）：控制数据存储的信号。
   • Q（输出）和 Q̅（反输出）：锁存器的输出和反输出。

2. 工作原理：

   • 当 使能信号为高（E = 1）：锁存器“打开”，D输入的值直接通过电路输出到 Q。
   • 当 使能信号为低（E = 0）：锁存器“锁住”，Q 保持之前存储的值，不受 D 输入变化的影响。

3. 特性：

   • 数据在 使能信号有效期间 会被更新。
   • D锁存器消除了竞争（Race）条件，因为它只有一个数据输入（D），避免了像 SR 锁存器中的非法状态（S=R=1）。

4. 应用：

• 数据存储单元：用作基本的位存储器。
• 数据保持电路：维持信号的稳定性。
• 边沿触发寄存器（如 D 触发器）的基本构造单元。

Enable (E)	Data (D)	Output (Q)
0	X (任意)	保持原值
1	0	0
1	1	1

D锁存器逻辑门组成：

• 两个与非门（NAND）或与门（AND）用来生成控制信号。
• 两个交叉耦合的 NAND 门（或 NOR 门）构成一个基本的锁存器（SR 锁存器）。

3.1.3 JK锁存器（JK Latch）

JK锁存器是一种增强型的时序逻辑电路，是对 SR 锁存器的改进，避免了 SR 锁存器中 S=1 和 R=1 时的非法状态问题。它被广泛用于时序电路中，能够实现多种功能，如保持、置位、复位和翻转。

1. 输入和输出：

   • J（Set）：对应置位功能。
   • K（Reset）：对应复位功能。
   • 使能信号（Enable 或 Clock）：控制锁存器工作状态。
   • Q（输出）和 Q̅（反输出）：锁存器的输出和反输出。

2. 功能定义：

   • J=0, K=0：保持状态（Q 保持不变）。
   • J=0, K=1：复位（Q=0）。
   • J=1, K=0：置位（Q=1）。
   • J=1, K=1：翻转状态（Q 从 0 变为 1，或从 1 变为 0）。

Enable (E)	J	K	Q (Next State)
0	X	X	保持原值
1	0	0	保持原值
1	0	1	0
1	1	0	1
1	1	1	Q̅（翻转）

3. JK锁存器应用:

• 寄存器设计：作为存储单元使用。
• 计数器：通过翻转功能实现二进制计数器。
• 时序电路：作为基本的控制逻辑单元。

3.2 Flip-FLop

触发器是数字电路中的一种基本时序逻辑电路，用于存储一个二进制位的信息。它具有存储能力和同步性，是寄存器、计数器等时序电路的基础组件。

触发器的特点：

1. 存储能力：可以存储1位二进制数据（0或1）。
2. 同步性：大多数触发器通过时钟信号（Clock）控制状态的改变。
3. 状态保持：在没有输入信号变化时，触发器会保持当前状态。

常见触发器类型：

SR触发器：

• 基本类型，具有两个输入：Set（置1） 和 Reset（清0）。
• 特点：
  • S=1, R=0：输出为1。
  • S=0, R=1：输出为0。
  • S=0, R=0：保持状态。
  • S=1, R=1：不稳定状态（无效）。

D触发器（数据触发器）：

• 具有一个数据输入端（D）和一个时钟输入端（CLK）。
• 特点：
  • 在时钟信号的有效边沿（上升沿或下降沿）到来时，将输入D的值传递到输出Q。
• 应用：
  • 常用于数据同步和寄存器设计。

JK触发器：

• 是RS触发器的改进型，消除了S=1, R=1的无效状态。
• 输入为J和K：
  • J=1, K=0：置1。
  • J=0, K=1：清0。
  • J=K=1：状态翻转。
• 应用：
  • 广泛用于计数器和状态机设计。

T触发器（触发翻转器）：

• 只有一个输入（T）。
• 特点：
  • T=1：状态翻转。
  • T=0：状态保持。
• 应用：
  • 常用于计数器电路。

触发器是数字电路中存储单元的核心，用来实现数据存储和同步控制。不同类型的触发器适用于不同的功能需求：

• SR触发器用于简单存储；
• D触发器用于数据锁存；
• JK触发器适合复杂逻辑控制；
• T触发器常用于计数和分频。

3.2.1 SR Flip-Flop

SR触发器是一种基本的双稳态存储单元，用于存储1位二进制信息。SR触发器由 Set（S） 和 Reset（R） 两个输入控制输出状态，常用于简单的存储和逻辑控制。

工作原理

• S（Set）：设置触发器的输出为1（Q=1）。
• R（Reset）：重置触发器的输出为0（Q=0）。
• $Q$ 和 $\overline{Q}$：为触发器的输出和其反向输出。

逻辑功能表

S	R	Q（输出）	状态
0	0	保持	保持上次状态
0	1	0	清零
1	0	1	置1
1	1	无效	不允许状态

状态说明

1. S=0, R=0：触发器保持当前状态，不发生变化。
2. S=1, R=0：输出Q被置为1（Set）。
3. S=0, R=1：输出Q被重置为0（Reset）。
4. S=1, R=1：为无效状态，因Q和Q’会同时为1，违背Q和Q’互补的逻辑。

应用场景

• 存储单元：用于存储1位数据。
• 逻辑控制：作为简单的状态保持和切换电路。
• 锁存器：用于构成其他类型的触发器（如D触发器和JK触发器）。

SR触发器是最基本的触发器类型，但存在S=1, R=1的不允许状态，限制了它在复杂电路中的使用。改进型触发器（如JK触发器）解决了这一问题。

SR触发器状态转移公式：
$$
\begin{cases}
Q_{n+1} = S + \overline{R}Q_{n} \\
S \cdot R = 0 (约束条件)
\end{cases}
$$

3.2.2 D Flip-Flop

D触发器（Data Flip-Flop, DFF）是数字电路中一种基本的时序逻辑电路，用于存储1位二进制数据。它通过 数据输入端（D） 和 时钟信号（CLK） 实现同步数据存储。D触发器也经常称为主从触发器（master-slave flip-flop），边沿触发器（edge-triggered flip-flop）或者正边沿触发器（positive edge-triggered flip-flop）。

工作原理:

• D输入：决定触发器的输出值。
• CLK输入：控制触发器的状态更新，确保输出只有在特定时钟条件下（如上升沿或下降沿）才更新。
• 当时钟信号有效时，D的值会传递到输出Q，同时Q’为Q的反相。

逻辑功能表:

CLK（时钟）	D（数据）	Q（输出）	状态
上升沿	0	0	输出清零
上升沿	1	1	输出置1
其他	-	保持	状态不变

DFF特点:

1. 同步性：依赖时钟信号控制，输出只在时钟有效时更新。
2. 无争议状态：相比SR触发器，D触发器没有无效状态。
3. 锁存功能：在时钟无效时，输出保持上一次的状态。

DFF应用场景:

1. 寄存器：用于存储和传输数据。
2. 移位寄存器：通过多级D触发器实现数据位移。
3. 计数器：作为计数器电路的基础单元。
4. 同步电路：用于数据同步或信号稳定。

D触发器是一种简单高效的存储单元，它通过时钟信号的控制实现数据的同步存储，广泛应用于各种数字电路中。一个D触发器可以由反相时钟控制的2个背靠背的D锁存器构成。

对于上升沿触发的DFF的时序图：

至于为什么是上升沿触发，可以画一下主锁存器的值和从锁存器的值的时序图，此处省略

当然还有下降沿触发的DFF的时序图：

D触发器状态转移公式：
$$Q_{n+1} = D$$

3.2.3 JK Flip-Flop

JK触发器是一种改进型的双稳态触发器，是对SR触发器的增强，解决了SR触发器中S=1, R=1的无效状态问题。它通过输入信号J和K以及时钟信号CLK实现状态控制，具有更强的功能和更广的应用。

JKFF工作原理：

• J（Set）：与SR触发器的S功能类似，用于设置输出Q=1。
• K（Reset）：与SR触发器的R功能类似，用于清零输出Q=0。
• CLK（时钟信号）：用于同步控制，触发器的状态仅在时钟信号的有效边沿发生变化。

JKFF逻辑功能表：

J	K	$Q_{n}$（输出）	$Q_{n+1}$（下一状态）	状态描述
0	0	Q	保持	状态保持
0	1	0	清零	Reset
1	0	1	置1	Set
1	1	Q’（反相）	翻转	Toggle（翻转）

JKFF特点：

1. 无无效状态：J=1, K=1 时，触发器的输出状态翻转，解决了SR触发器的争议状态问题。
2. 同步性：在时钟信号控制下工作，确保状态变化的同步。
3. 功能多样：可以通过J和K的输入实现保持、置1、清零、翻转等功能。

JKFF结构组成：

• 由SR触发器扩展而来，增加了逻辑门以控制输入S和R，确保J=1, K=1 时实现输出翻转。
• 常采用 边沿触发（Edge-triggered） 的设计，使其适用于复杂的时序电路。

JKFF应用场景：

1. 计数器：JK触发器在计数器电路中广泛应用，用于实现递增或递减计数。
2. 状态机：设计复杂的同步时序电路。
3. 分频器：利用J=1, K=1的翻转特性实现时钟信号分频。

JK触发器的实现可以通过主从结构，由两个SR触发器级联完成。

下面是下降沿触发的JKFF的时序图:

我们可以得出JKFF的状态转移公式：

$$Q_{n+1} = J\overline{Q_{n}} + \overline{k}Q_{n}$$

JKFF时序图口诀：00不变，11翻转，10置1，01置0

3.2.4 T Flip-Flop

T触发器（Toggle Flip-Flop）是一种基本的时序逻辑电路，用于实现状态翻转或分频功能。

TFF工作原理：

• T输入（Toggle）：用于控制触发器的翻转功能。
  • T=0：保持当前状态
  • T=1：状态翻转
• CLK（时钟信号）：控制T触发器的状态更新，输出仅在时钟信号的有效边沿发生变化。

TFF逻辑功能表：

CLK（时钟）	T（输入）	$Q_{n}$（输出）	$Q_{n+1}$（下一状态）	状态描述
上升沿	0	Q	保持	状态保持
上升沿	1	Q’	翻转	Toggle（翻转）
其他	-	保持	保持	状态不变

TFF特点：

1. 状态翻转：当T=1时，输出状态在每个时钟边沿发生翻转。
2. 分频功能：每次翻转需要一个时钟信号，因此输出频率为输入时钟频率的一半。
3. 简化结构：通过将JK触发器的J和K输入连接为同一信号T，简化了设计。

TFF实现方式：

1. 由JK触发器实现：将J=K=T，形成T触发器的逻辑。
2. 直接实现：通过逻辑门电路设计，实现T输入控制翻转功能。

TFF应用场景：

1. 计数器：用于实现二进制计数器的单个计数位。
2. 分频器：将时钟信号的频率降低一半，用于时钟分频。
3. 状态机：在简单状态转换电路中用作基本单元。

TFF的一种实现如下图：

TFF的时序图如下：

我们可以得出TFF的状态转移方程式为：

$$Q_{n+1} = T \oplus Q_{n}$$

3.3 Synchronous Sequential Logic

Synchronous Sequential Logic（同步时序逻辑）是一类数字逻辑电路，其输出不仅取决于当前的输入，还取决于电路的状态（通常存储在触发器中）。这种电路的状态变化由一个全局时钟信号同步控制。

同步时序电路可以设计为两种类型：

• Mealy电路：输出依赖于当前状态和输入（对应有限自动机中的 Mealy 机）。
• Moore电路：输出仅依赖于当前状态（对应有限自动机中的 Moore 机）。

记忆：摩尔庄园–>摩尔当前–>摩尔电路只依赖于当前状态

根据上图可以再深入理解一下两种有限状态机（Finite State Machine, FSM），举个例子，判断输出1是如何依赖的：

• Mealy型FSM输出1需要同时依赖当前状态和输入
  • 当前状态B并且输入1，可以输出1
  • 当前状态B并且输入0，可以输出1
• Moore型FSM输出1只依赖当前状态：
  • 当前状态是B是，输出1
  • 当前状态是C，输出1

关于同步时序电路的设计一般有如下步骤：

1. 原始状态图
2. 状态图化简（当两个状态具有同样的输入时，也具有相同的输出和相同的次态时，可以合并）
3. 状态分配（画状态表的时候与卡诺图一一对应比较合理高效！例如00、01、11、10这样子）
4. 选触发器（D、JK；3个状态选2个FF，5个状态选3个FF； $2^{n-1} < M \leq 2^{n}$）
5. 确定激励方程组以及输出方程组
6. 画图✍️检查能否自启动

常见的同步时序电路设计一般包含：计数器，序列检测器，串行数据检测器等。

同步时序电路设计的思路都很固定，参考过去问巩固练习即可

计数器过去问典型题目：马不停蹄🐎

序列检测器典型题目：马不停蹄🐎

串行数据检测器典型题目：马不停蹄🐎

3.4 Asynchronous Sequential Logic

Asynchronous Sequential Logic（异步时序逻辑） 是一种不依赖全局时钟信号的逻辑电路设计。其状态的变化由输入信号的变化直接触发，而不是由时钟脉冲控制。与同步时序逻辑相比，异步逻辑更灵活，但设计和调试更复杂。

异步时序逻辑特点：

1. 无全局时钟信号：异步电路的状态变化完全由输入信号或内部信号的变化触发，而不需要时钟信号协调。
2. 依赖传播延迟：异步逻辑的行为受门延迟和信号传播时间的影响，可能会导致竞争和冒险现象。
3. 更快的响应速度：输入变化会立即影响输出，因此响应速度通常比同步电路快。
4. 更复杂的设计：需要解决元态（Metastability）、竞争（Race Condition）和冒险（Hazard）问题，设计和验证复杂度较高。

修考基本很少考异步时序电路设计，参考过去问巩固练习。

异步时序电路设计题目：马不停蹄🐎

4. 偷偷说

数字电路的重点就是组合电路和时序电路的设计，在理解每个元件特性的基础上，设计类的题目都非常固定。数字电路的黑书说实话写的很差劲：一是逻辑不连贯，二是忽略了很多推导细节。相反，《論理回路入門》by：坂井 修一，这本书我觉得写的非常不错，短小精悍，非常适合修考备考。

Thanks @drawio for generating the powerful diagrams.

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio