考研数电·零基础讲义 第17讲（上）｜同步时序电路设计：状态化简与编码

考研数电·零基础讲义 · 第 17 讲（上）｜同步时序电路设计：逻辑抽象、状态化简与状态分配 学完这一讲，你能把一句文字要求（例如"连续输入三个 1 就报警"）翻译成状态转换图和状态转换表，会找出并合并等价状态，会确定要几个触发器、怎样给状态编码。预计用时 90–110 分钟。

本讲地图#

• 设计是分析的逆过程：第 14 讲是"给电路 → 求功能"，这一讲是"给功能 → 求电路"。
• 六个步骤：逻辑抽象 → 状态化简 → 状态分配 → 选触发器求方程 → 画逻辑图 → 检查自启动。本讲讲前三步，后三步和完整实例在第 17 讲（下）。
• 逻辑抽象：确定输入、输出、状态的含义，画出原始状态转换图/表；分清米利型和穆尔型。
• 状态化简：等价状态的定义、观察法和"分组细化法"。
• 状态分配：触发器个数$n$满足$2^{n-1}<M\le2^{n}$⁠；编码方案不同，电路繁简不同。
• 华师怎么考：考纲要求时序逻辑电路，真题第 7 题考了"由 D 触发器构成的电路分析"；设计题（序列检测器、指定进制计数器）是分析题的"反向版本"，同样需要掌握。教材对应第 6 章 6.4.1 节。

前置知识#

• 状态转换表、状态转换图的画法，现态$S$⁠、次态$S^{*}$（见第 14 讲）。
• 触发器的特性方程（见第 13 讲（下））。
• 卡诺图化简与无关项（见第 04 讲（中）、第 04 讲（下））。

---

一、设计和分析：方向相反的同一条路#

1.1 大白话#

分析像"看菜品猜菜谱"：给你一个电路，让你说出它干什么。 设计像"按点菜要求写菜谱"：给你一个功能要求，让你造出电路。

第 14 讲的分析路线是：

逻辑图 → 驱动方程 → 状态方程 → 状态转换表/图 → 说明功能

设计正好倒过来：

功能要求 → 状态转换图/表 → （化简、编码）→ 状态方程 → 驱动方程 → 逻辑图

所以只要分析会了，设计的每一步其实都"见过"，只是方向反了。

1.2 设计的六个步骤#

图 1：同步时序逻辑电路设计的六个步骤（红框依次移动，动画循环播放）

教材对"最简"的标准：用小规模器件（触发器 + 门）时，触发器和门的数目最少、输入端也最少；用中大规模集成电路时，芯片数目和种类最少、连线最少。

---

二、第一步：逻辑抽象#

2.1 大白话#

逻辑抽象就是把一段中文描述"翻译"成状态转换图。翻译时要回答三个问题：

1. 输入是什么？ 一般取"原因、条件"作输入变量（例如串行输入的数据 X、投入的硬币）。
2. 输出是什么？ 一般取"结果"作输出变量（例如报警 Y、给出饮料）。
3. 电路需要记住什么？ 每一种"需要区分的历史情况"就是一个状态。

第 3 问最关键。状态就是电路的"记忆"——它不需要记住全部历史，只需要记住对将来有影响的那部分。

2.2 米利型与穆尔型#

• 米利（Mealy）型：输出由现态和输入共同决定。状态图上，输出写在箭头上，标成"输入/输出"，例如 1/0。
• 穆尔（Moore）型：输出只由现态决定，与当前输入无关。计数器就是典型的穆尔型：没有输入变量，进位输出只看当前状态。

两种都能用，考试中序列检测器多数按米利型写，计数器是穆尔型。

2.3 例题 1：串行数据检测器（教材例 6.4.2）#

题：设计一个串行数据检测器：连续输入 3 个或 3 个以上的 1 时输出为 1，其他情况输出 0。

第 1 步，定输入输出：输入数据 X，输出检测结果 Y。

第 2 步，定状态：电路要记住的是"到目前为止，末尾已经连续有几个 1"：

• $S_{0}$⁠：末尾没有 1（刚开始，或刚输入了 0）；
• $S_{1}$⁠：末尾连续 1 个 1；
• $S_{2}$⁠：末尾连续 2 个 1；
• $S_{3}$⁠：末尾连续 3 个或更多 1。

第 3 步，逐个状态问"来 0 怎样、来 1 怎样"：

• 任何状态下来 0：连续被打断，回$S_{0}$⁠，输出 0。
• $S_{0}$来 1 → $S_{1}$⁠，输出 0；$S_{1}$来 1 → $S_{2}$⁠，输出 0；
• $S_{2}$来 1 → 已经连续 3 个，去$S_{3}$⁠，输出 1；
• $S_{3}$来 1 → 仍然是"3 个以上"，留在$S_{3}$⁠，输出 1。

原始状态转换表（表中写"次态/输出"）：

这就把文字要求变成了一个"时序逻辑函数"。

2.4 同一个要求，写成穆尔型会怎样？#

如果把例题 1 改成穆尔型（输出只看现态），那么"已经连续 3 个以上 1"必须是一个单独的状态，输出 Y=1 写在这个状态里：

穆尔型里$S_{2}$和$S_{3}$的输出不同（0 和 1），所以不能合并，要 4 个状态（Python 按穆尔型分组细化，结果仍是 4 组）。

两者在时间上也有差别：米利型在"第三个 1 正在输入"的那个时钟周期里，Y 就已经是 1（输出跟着输入走）；穆尔型要等时钟沿把电路送进$S_{3}$之后，下一个周期 Y 才变 1，晚一拍。以输入序列 1,1,1,1,0,1,1,1 为例，两种写法得到的"1"出现在同样的第 3、4、8 位上，只是穆尔型的每个 1 都在对应时钟沿之后才出现。

一般来说：米利型状态数少，穆尔型输出更"干净"（不会因为输入抖动而抖动）。考试没有特别说明时，按题意自然的那种写即可。

2.5 例题 2：自动售饮料机（教材例 6.4.3，看抽象思路）#

题：投币口每次只能投一枚五角或一元硬币。投满一元五角给一杯饮料；投入两元（两枚一元）时给饮料并找回五角。

抽象：

• 输入：A=1 表示投入一元，B=1 表示投入五角（同时投两枚不可能，所以 AB=11 是无关项）。
• 输出：Y=1 给饮料，Z=1 找五角。
• 状态：电路要记住"已经投了多少钱"：$S_{0}$没投，$S_{1}$已投五角，$S_{2}$已投一元。

表中"/"后面是 YZ。例如$S_{2}$再投一元（AB=10）：总共两元，给饮料并找五角，回$S_{0}$⁠，输出 YZ=11。

⚠️ 易错点：

1. 状态要按"对将来有影响的历史"来分，不要按"输入过什么"一个个列——否则状态会多得没法收拾。
2. 每个状态对每一种输入都要有去向，表格不能留空（真正不会出现的组合标 ×）。
3. 米利型的输出写在箭头/表格的"/"后面，属于"转移"；穆尔型的输出写在状态圈里，属于"状态"。

---

三、第二步：状态化简#

3.1 大白话#

原始状态图往往"想多了"：有些状态看起来不同，其实对外表现一模一样。好比两个服务窗口，规则、出口都完全相同，那合成一个就行。状态越少，需要的触发器和门就越少。

3.2 等价状态的定义#

若两个状态在相同的输入下有相同的输出，并且转换到同样的次态，则称这两个状态为等价状态。等价状态可以合并为一个。

更一般地说，"转换到同样的次态"也可以放宽为"转换到的次态本身是等价的"——下面的分组细化法就是按这个思路一步步做的。

3.3 观察法：例题 1 的化简#

看例题 1 的表，比较$S_{2}$和$S_{3}$⁠：

• $X=0$⁠：都是$S_{0}/0$⁠；
• $X=1$⁠：都是$S_{3}/1$⁠。

输出相同、次态相同 → $S_{2}$与$S_{3}$等价，合并为$S_{2}$⁠。化简后的表：

物理意义：在$S_{2}$时已经连续两个 1，只要下一个输入是 1 就"满 3 个"了；而"满 3 个"以后再来 1，情况和"刚满 2 个再来 1"完全一样，所以没必要单独设$S_{3}$⁠。我用 Python 拿 1000 组随机序列核对：原始 4 状态机、化简后 3 状态机、"直接看最近三位是不是 111"三者输出完全一致。

3.4 分组细化法（适合状态多的时候）#

观察法靠眼力，状态多了容易漏。有一个机械的办法，步骤如下：

1. 第 0 轮：按"各输入下的输出"把状态分组——输出不同的状态肯定不等价。
2. 第 1 轮：在每一组内部，再看各状态在每种输入下"去了哪一组"。去向组号不同的拆开。
3. 重复第 2 步，直到某一轮不再有组被拆开。这时同一组里的状态两两等价。

3.5 例题 3：用分组细化法化简 7 个状态#

题：化简下表（次态/输出）。

第 0 轮（按输出分组）：把每个状态的输出写成"(X=0 时, X=1 时)"：

• $S_{0},S_{1},S_{2}$⁠：(0,0) → 组 P；
• $S_{3},S_{6}$⁠：(0,1) → 组 Q；
• $S_{4},S_{5}$⁠：(1,0) → 组 R。

第 1 轮（看去向）：

• 组 Q：$S_{3}$去向 ($S_{0},S_{0}$) = (P,P)；$S_{6}$去向 (P,P)。相同，不拆。
• 组 R：$S_{4}$⁠、$S_{5}$去向都是 (P,P)，不拆。
• 组 P：$S_{0}$去向 ($S_{1},S_{2}$) = (P,P)；$S_{1}$去向 ($S_{3},S_{4}$) = (Q,R)；$S_{2}$去向 ($S_{5},S_{6}$) = (R,Q)。三者各不相同，拆成三组$\{S_{0}\}$⁠、$\{S_{1}\}$⁠、$\{S_{2}\}$⁠。

第 2 轮：组 Q、R 内部的去向仍然一致，没有再拆。结束。

结论：$S_{3}\equiv S_{6}$⁠，$S_{4}\equiv S_{5}$⁠，7 个状态化简为 5 个：$S_{0},S_{1},S_{2},S_{3},S_{4}$（把表中的$S_{6}$换成$S_{3}$⁠、$S_{5}$换成$S_{4}$⁠）。（Python 分组细化结果相同。）

值得注意的地方：$S_{1}$和$S_{2}$的输出相同，次态也"都在 Q、R 里"，乍一看很像等价。但$S_{1}$是"0→Q、1→R"，$S_{2}$是"0→R、1→Q"，同一个输入去了不同的组，所以不等价。比较时一定要"按同一个输入"逐列对比。

3.6 例题 4："110"序列检测器——从啰嗦的原始图化简#

题：输入 X 串行送入，每当最近三位是 110 时输出 Y=1（允许重叠）。某同学列出了 5 个状态：A 初始；B 收到 1；C 收到 11；D 刚收到 110；E 刚收到 0。原始表：

化简：

• 第 0 轮：只有 C 在 X=0 时输出 1 → 分成$\{A,B,D,E\}$和$\{C\}$⁠。
• 第 1 轮：在$\{A,B,D,E\}$中，看 X=1 时的去向：A、D、E 都去 B（第一组），B 去 C（第二组）→ B 单独拆出。得到$\{A,D,E\}$⁠、$\{B\}$⁠、$\{C\}$⁠。
• 第 2 轮：A、D、E 在 X=0 都去 E、X=1 都去 B，去向组一致，不再拆。

所以$A\equiv D\equiv E$⁠，合并为 A′，只剩 3 个状态。

图 2：左为原始 5 状态图（橙色三个状态等价），右为化简后的 3 状态图

为什么合并等价状态不会改变功能？ 想象两个人分别从 A 和 D 出发，接下来收到完全相同的输入序列。第一拍他们输出相同、走到的状态也等价；既然等价，下一拍又输出相同、走到等价的状态……一直推下去，两人的输出序列永远一模一样。外面的人只能看到输出，根本分不出电路是从 A 还是从 D 出发的，所以把 A、D 合成一个状态，对外的行为不会有任何变化。这也是为什么化简后一定要用一些输入序列去核对：核对通过，说明化简没出错。

物理意义：D（刚检测到 110）和 E（刚收到 0）的共同点是"末尾是 0，手里没有可用的 1"，这和初始状态 A 对将来的影响完全一样。验证：输入 1101100110，原始机和化简机的输出都是 0010010001（Python 核对）。

⚠️ 易错点：

1. 等价要求每一种输入下输出都相同、次态都等价，少比一列都不行。
2. 合并后要把表中所有指向被合并状态的次态都改名，否则表就错了。
3. 计数器的 M 个状态代表"已输入 M 种不同个数的脉冲"，一般不能化简（教材例 6.4.1 的十三进制计数器就是这样）。

---

四、第三步：状态分配（状态编码）#

4.1 要几个触发器？#

$n$个触发器有$2^{n}$种组合。要表示 M 个状态，取满足下式的$n$⁠：

$$2^{n-1}<M\le2^{n}$$

例：M=3 → $n=2$（⁠$2<3\le4$⁠）；M=6 → $n=3$⁠；M=10 → $n=4$⁠；M=13 → $n=4$⁠。

4.2 编码方案有多少种？#

M<$2^{n}$时，从$2^{n}$种组合里挑 M 种、再排给 M 个状态，方案数是排列数$A_{2^{n}}^{M}$⁠。例如 3 个状态、2 个触发器：$A_{4}^{3}=4\times3\times2=24$种（这正是教材复习思考题 R6.4.1 的答案）。

方案很多，选得好电路简单，选得差电路复杂。没有万能公式，常用的经验是：

• 次态相同的几个现态，编码尽量相邻（只差一位）；
• 同一个现态在不同输入下的几个次态，编码尽量相邻；
• 输出相同的状态，编码尽量相邻；
• 计数器一般直接用自然二进制或 8421 码，便于识别。

（"相邻"的好处是在卡诺图里能圈在一起，化简后式子短。这几条是经验，不是定理。）

4.3 例题 5：两种编码的繁简对比#

题：对例题 4 化简后的"110"检测器（A′、B、C），用 D 触发器实现。比较两种编码：

• 方案甲：A′=00，B=01，C=10；
• 方案乙：A′=00，B=01，C=11。

解：用$Q_{1}Q_{0}$表示状态，未用的编码作无关项，按次态表化简（用 sympy 求最简与或式并核对）：

方案乙明显更简单：$D_{0}$直接接 X，连门都不用！原因是：在方案乙中，"收到 1"后的两个状态 B=01、C=11 的低位都是 1，正好等于"刚输入的 X"；而且 B、C 编码相邻（只差$Q_{1}$⁠），符合"同一类次态编码相邻"的经验。

4.4 拓展了解：用更多触发器换更简单的逻辑#

上面都假设用"最少"的触发器。实际工程中有时会故意多用触发器，例如每个状态用一个触发器、任何时刻只有一个触发器为 1（叫"独热码"，3 个状态就编成 001、010、100）。好处是次态逻辑往往很简单、容易看懂；代价是触发器多。考试按教材要求，一般取最少的$n$⁠，这一条了解即可。

4.5 第四步预告：选触发器、求方程#

编码确定后，状态转换表就变成了"现态代码 + 输入 → 次态代码 + 输出"的真值表，用卡诺图（无关项要用上）求出状态方程，再根据所选触发器的特性方程变换出驱动方程：

• D 触发器：$Q^{*}=D$⁠，状态方程就是驱动方程；
• JK 触发器：把状态方程凑成$Q^{*}=J\overline{Q}+\overline{K}Q$的形式，对照得 J、K。

这部分连同"自启动检查"放在第 17 讲（下）结合完整实例讲。

⚠️ 易错点：

1. $n$取满足$2^{n}\ge M$的最小整数，不是越多越好。
2. 未使用的编码在卡诺图里是无关项，化简时可以利用；但它们最终会被"指定"一个次态，所以设计完必须检查自启动。

---

速记卡#

---

自测练习#

1. 分别需要几个触发器才能实现 6 个状态、9 个状态、16 个状态的同步时序电路？

答案与提示

6 → 3 个（⁠$4<6\le8$⁠）；9 → 4 个（⁠$8<9\le16$⁠）；16 → 4 个（⁠$8<16\le16$⁠）。

2. 例题 1 化简后有 3 个状态，用 2 个触发器编码，共有多少种不同的编码方案？

答案与提示

$A_{4}^{3}=24$种。

3. 化简下表（次态/输出）：

答案与提示

第 0 轮按输出：$\{A,D,E\}$（0,0）、$\{B,C\}$（0,1）。第 1 轮：A、D、E 去向都是（第二组，第二组）；B 去向 (A,D)、C 去向 (A,E)，都在（第一组，第一组）。不再拆分。结论$A\equiv D\equiv E$⁠，$B\equiv C$⁠，化简为 2 个状态（Python 分组细化结果一致）。

4. 判断下列电路是米利型还是穆尔型：(1) 74HC161 构成的十六进制计数器，输出为进位 C；(2) 例题 1 的串行数据检测器（Y 取决于现态和 X）。

答案与提示

(1) 穆尔型：没有输入变量，C 只由现态决定（⁠$C=Q_{3}Q_{2}Q_{1}Q_{0}$⁠，ET 视为常 1）。(2) 米利型。

5. 设计一个"01"序列检测器（米利型，允许重叠：每当最近两位是 01 时输出 1）。至少需要几个状态？写出状态转换表。

答案与提示

2 个状态：$S_{0}$（末尾不是 0）、$S_{1}$（末尾是 0）。

现态	X=0	X=1
$S_{0}$	$S_{1}/0$	$S_{0}/0$
$S_{1}$	$S_{1}/0$	$S_{0}/1$

用 1000 组随机序列与"直接判断最近两位"比对，全部一致。

6.（华师设计题风格） 设计一个串行检测器：连续输入两个或两个以上的 0 时输出 1（米利型）。(1) 写出原始状态表（设$S_{0}$无 0、$S_{1}$末尾一个 0、$S_{2}$末尾两个以上 0）；(2) 化简；(3) 需要几个触发器？

答案与提示

(1)

现态	X=0	X=1
$S_{0}$	$S_{1}/0$	$S_{0}/0$
$S_{1}$	$S_{2}/1$	$S_{0}/0$
$S_{2}$	$S_{2}/1$	$S_{0}/0$

(2) $S_{1}$⁠、$S_{2}$⁠：X=0 时都输出 1，次态$S_{2}$与$S_{2}$⁠；X=1 时都是$S_{0}/0$⁠。等价，合并为$S_{1}$（⁠$S_{1}$在 X=0 时自循环、输出 1）。只剩 2 个状态。(3) 1 个触发器。（Python 核对化简前后输出一致。）

---

下一讲预告#

第 17 讲（下）完成后三步：用 D 和 JK 触发器把序列检测器、指定进制计数器真正"搭"出来，并学会检查自启动、在不能自启动时修改设计。

👉 点击进入下一讲：第17讲（下）｜设计实例与自启动检查