建立原始状态图的步骤： 假定一个初态S0 。 从S0出发，每加入一个要记忆的输入信号，就用其次态 “记忆”，并标出相应的输出值。 （该次态可能是S0本身，也可能是另一个已有的状态，也可 能是新增的状态。） 重复直到没有新的状态出现，并且从每个状态出发，输入 的各种可能取值引起的状态转移一一考虑。
化简方法： 1）观察法：适用于简单状态表化简。 2）隐含表法：基本思想是两两比较原始状态表中的所有状 态，找出等效状态对，再利用传递性，得到等效类和最大 等效类，合并最大等效类中的状态，得到最小化状态表。
例3、观察法化简下列状态表
1
例4、隐含表法化简下列状态表
隐含表：直角三角形网格。 横向从左到右依次标 注1~n-1个状态名， 纵向从上到下依 次标注2~n个 状态名。
最小化状态表的状态数N与状态编码长度n的关系：
2 n1 N 2 n
编码方案将会影响输出函数、激励函数的表达式，从而影 响电路的复杂程度。
状态分配的基本原则 1）在相同输入条件下具有相同次态的现态，应尽可能分配 相邻的二进制代码。 2）在不同输入条件下，同一现态的次态应尽可能分配相邻 的二进制代码。 3）输出完全相同的现态应尽可能分配相邻的二进制代码。 4）最小化状态表中出现次数最多的状态应分配逻辑0。 通常，第一条原则较重要，需优先考虑。上述原则和 优先次序的考虑，目的是使次态函数和输出函数在卡诺图 上“1”的分布是相邻的，使函数表达式最简。
例5、简化下列状态表。
解：1）作隐含表，寻找相容状态对。 (A,B)，(A,F)，(B,C)，(B,D)，(B,E)，(B,F) (C,D)，(C,E)，(C,F)，(D,F)，(D,E)，(E,F)
例5、简化下列状态表。 解：1）作隐含表，寻找相容状态对。 (A,B)，(A,F)，(B,C)，(B,D)，(B,E)，(B,F) (C,D)，(C,E)，(C,F)，(D,F)，(D,E)，(E,F) 2）作状态合并图，求最大相容类。 (A,B,F)状态合并图，(B,C,D,E,F) 3）作最小化状态表 可任选一组能覆盖原始状态所有 状态的相容类来作闭覆盖表。
解：1）作隐含表。 2）顺序比较，寻找等效状态对。 比较结果有状态对等效、不等效、不能确定三种。等效 时在相应方格填“√” ；不等效时在相应方格填“╳”， 不能确定时，将次态对填入相应方格 CF
X
X BE √
X
X
解：1）作隐含表。 2）顺序比较，寻找等效状态对。 比较结果有状态对等效、不等效、不能确定三种。等效 时在相应方格填“√” ；不等效时在相应方格填“╳”， 不能确定时，将次态对填入相应方格
原状态表中所有最大等效类是：(A,B,E)、(C,F)、(D)、(G)
解：4）确定最大等效类，作最小化状态表。
2）不完全确定状态表的化简（建立在“状态相容”的概念上） 相容状态：对所有的有效输入序列（长度和结构任意），分 别从状态S1和S2出发，所得到的输出响应序列（除不确定的 那些位之外）是完全相同的，则S1和S2相容，或称S1、S2是 相容对，记作（S1，S2）。 相容状态无传递性：若S1，S2相容，S2，S3相容，但S1，S3 不一定相容。 相容类：所有状态之间都是两两相容的状态集合。 最大相容类：不包含在其它相容类中的相容类。
y1( n1) X y 2 y1 X y 2 y1 X y 2 y1 Xy2 y1
( n 1) y2 ( X y1 ) y 2 Xy2
J 2 X y1 J1 1 , (1) y1
2）确定输出函数表达式
设计步骤： 1．根据设计要求，设定状态，画出原始状态转换图。 2．状态化简 3．状态分配，列出状态转换编码表 4．选择触发器的类型，求出状态方程、驱动方程、输出方程 5．根据驱动方程和输出方程画逻辑图。 6．检查电路有无自启动能力
1. 建立原始状态图 原始状态图：直接从设计命题的文字描述得到的状态图。 状态图和状态表能反映同步时序电路的逻辑功能，所以 它是设计同步时序电路的依据。
例6、对下列状态表进行状态编码。
解：1）确定编码长度 有4个状态（N=4），所以编码长度为n=2。即需要两个 触发器，假设触发器状态变量为y2和y1。 2）确定状态分配方案 原则1：状态A、B分配相邻代码；A、C也应分配相邻代码。 原则2：状态C和D、C和A、B和D、A和B应分配相邻代码。 原则3：状态A、B、C应分配相邻代码。 原则4：状态A分配逻辑0，即A的编码为y2y1=00。 注意：满足状态分配原则的方案不一定是唯一的。
√
√ √ √
AB → CF √ AE → BE → AE (次态循环) CF √ BE → AE √ CF √ DG → CD × DE ×
解：3）关联比较，确定等效状态对
√
√ √
√
所以，等效对为(A,B)、(A,E)、(B,E)、 (C,F)。 它们属于两个等效类： (A,B,E)、(C,F)。 状态D，G没有与它们等效的 状态，因此各自单独构成一个最 大等效类。
2.状态化简 从原始状态表中消去冗余状态，得到最小化状态表的过程。 即使状态表不仅能表征逻辑命题的全部要求，且状态数又最少。 1）完全确定状态表的化简（建立在“状态等效”的概念上） 等效状态：对所有可能的输入序列，分别从状态S1和S2出发， 所得到的输出响应序列完全相同，则S1、S2等效，或称S1、S2 是等效对，记作(S1，S2)。等效状态可以合并。 等效状态的传递性：若(S1，S2)、(S2，S3),则(S1，S3)。记 作：(S1，S2)，(S2，S3)→(S1，S2，S3) 等效类：彼此等效的状态集合。 最大等效类：不包含在其它等效类中的等效类或状态。 状态化简的根本任务就是从原始状态表中找出最大等效类集 合。其关键是要找出原始状态表中所有等效状态对。
4.确定激励函数和输出函数 依据状态分配得到的二进制状态表和所选定的触发器的 激励表或次态方程求出激励函数表达式和电路的输出函数表 达式。
例7.用JK触发器实现下列二进制状态表，确定其激励函数和 输出函数表达式。
解：1）确定激励函数表达式 由二进制状态表得次态方程为：
( n 1) y2 X y 2 y1 Xy2
0/0
完全确定状态表： 状态表中的次态和输出 都有确定状态和确定的 输出值。
0/0
0/0 1/1
S3
S2
例2、设计一个用于引爆控制的同步时序电路，该电路有 一个输入端X和一个输出端Z。平时输入X始终为0，一旦 需要引爆，则从X连续输入4个1信号（不被0间断），电 路收到第4个1后在输出端Z产生一个1信号点火引爆，该 电路连同引爆装置一起被炸毁。试建立该电路的mealy型 状态图。 S0
3）作最小化状态表 如若选择（A，B，F）和（B，C，D，E，F）作闭覆盖 表。可以看出这两个相容类集合覆盖了原始状态表的全部状 态，而且每个最大相容类在任何一种输入情况下的次态组合 完全属于最大相容类集合中的一个相容类。因此满足闭合和 覆盖条件。此外最大相容类的数目已最少，满足最小条件。
3）作最小化状态表 选择（A，B，F）和（B，C，D，E，F）作闭覆盖表。 闭覆盖表画法是：在表的左边自上而下列出所选最大相容类， 表的中间覆盖部分自左到右列出全部状态，表的右边闭合部 分列出各相容类在输入各种取值组合下的次态组合。
通过上述分析，就可得到完整的原始状态图。
原始状态图的画法举例 例1、某序列检测器有一个输入端X和一个输出端Z。输入 端X输入一串随机的二进制代码，当输入序列中出现011 时，输出Z产生一个1输出，平时Z输出0。试做出该序列 检测器的原始状态图。（mealy型实现） 1/0 S0 1/0
0/0
S1 1/0
覆盖性：所选相容类集合应包含原始状态表的全部状态。
最小性：所选相容类集合中相容类个数应最少。 闭合性：所选相容类集合中的任一相容类，在原始状态表 中任意输入条件下产生的次态应该属于该集合中的某一个 相容类。 最小闭覆盖：同时具备最小、闭合、覆盖三个条件的相容 类（包括最大相容类）集合。 不完全确定状态表的化简就是寻找一个最小闭覆盖。 闭覆盖表：反映闭合和覆盖这两个性质的表。
同步时序逻辑电路设计
目的与要求： 1. 掌握同步时序电路的设计方法 2. 通过举例、做练习掌握方法。 重点与难点： 1. 同步时序电路的状态设定、状态化简、状态分配 2. 同步时序电路设计中驱动方程的求解 3. 能否自启动的判断
同步时序逻辑电路设计
同步时序电路的设计是分析的逆过程。是根据对设计要求 分析得到的状态图，设计出同步时序逻辑电路的过程。
3）作最小化状态表
若用A代替状态A、B、F；C代替状态B、C、D、E、F,可得 最小化状态表：
3.状态编码（状态分配） 状态编码就是给最小化状态表中的每个字母或数字表示的 状态指定一个二进制代码，形成二进制状态表。
编码的目的：用触发器实现状态表。
编码的任务：确定编码的长度（二进制位数或）；寻找一种 最佳或接近最佳的状态分配方案。
S i和S j等效的条件 （1）其输出完全相同； （2）其次态满足下列条件之一： 次态相同 次态交错：即在某种输入取值下，Si的次态为Sj，而Sj的 次态为Si。 次态循环：即次态之间的关系构成闭环。如： Si，Sj→Sk，Sl，而Sk，Sl→Si，Sj 次态对等效：如S1和S2的次态对为S3，S4，S3和S4满足 等效的2个条件（输出完全相同，次态相同/交错/循环）
相容的条件： （1）输出完全相同，或者其中的一个(或2个)输出为任意值
（2）次态满足下列条件之一： • 次态相同 • 次态交错 • 次态循环 • 其中的一个或二个为任意状态 • 次态对相容
不完全确定状态表的化简过程分为：作隐含表寻找相容 对；作状态合并图找最大相容类；作最小化状态表3个步骤。
状态合并图：将不完全确定状态表的状态以“点”的形式均 匀地绘在圆周上，然后把所有相容对都用线段连接起来而得 到的图。因此，所有点之间都有连线的多边形就构成一个最 大相容类。