第四章时序电路 Sequential circuits 432同步时序电路设计 状态化简( Reduction of state)(书页168 176) 在根据文字描述的设计要求建立原始状态 图的过程中,由于状态设置的考虑与方法不同, 可能得到多种形式的原始状态图。但只要过程正 确,所得的各种形式原始状态图都是正确的,但 状态图中的状态数和结构可能存在较大差别。 例:推导一时序电路原始状态图。其功能是 对一随机串行输入序列进行检测,当对电路连续 输入三个和三个以上的1时,输出Z为1,其它 情况输出Z均为0。 解1:为对连续输入的三个二进值进行检 测,对可能出现的八种情况设置状态进行记忆 SA:000,S:001,S:010,S:011,SE: 100,SF:101,S:110,S:111
第四章 时序电路 Sequential Circuits 4.32 同步时序电路设计 … 状态化简（Reduction of State）(书页 168－ 176) 在根据文字描述的设计要求建立原始状态 图的过程中，由于状态设置的考虑与方法不同， 可能得到多种形式的原始状态图。但只要过程正 确，所得的各种形式原始状态图都是正确的，但 状态图中的状态数和结构可能存在较大差别。 例：推导一时序电路原始状态图。其功能是 对一随机串行输入序列进行检测，当对电路连续 输入三个和三个以上的 1 时，输出 Z 为 1，其它 情况输出 Z 均为 0。 解 1：为对连续输入的三个二进值进行检 测，对可能出现的八种情况设置状态进行记忆。 SA：000，SB：001，SC：010，SD：011，SE： 100，SF：101，SG：110，SH：111
分别以每种情况为现态,求出输入X为0 和1时的次态及输出值,可得所有状态的转移连 接。从而得如下状态图表。 0/0 0/0 0 0 1/0 1/0 1/0 1/1 解1的原始状态图 次态NS 输出 现态 X=1 X=0 X=1 Sc:010 Sp: 011 SE:100 SF:101 00000000 解1原始状态表 解2:直接设置状态记忆连续输入1的个数: S:输入一个0和连续输入0; s1:输入一个1 S2:连续输入二个和二个以上1。 如上设置电路状态,无论电路处于何态,对 于任何输入,其次态均为三种状态之一。当处于 S2态时,可检测连续输入三个和三个以上1的情
分别以每种情况为现态，求出输入 X 为 0 和 1 时的次态及输出值，可得所有状态的转移连 接。从而得如下状态图表。 SA 000 0/0 SB 001 SC 010 SD 011 SE 100 SF 101 SG 110 SH 111 1/1 1/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/0 1/1 1/0 1/0 1/0 1/0 解 1 的原始状态图 现态 次态 NS 输出 Z x=0 x=1 x=0 x=1 SA:000 SA SB 0 0 SB:001 SC SD 0 0 SC:010 SE SF 0 0 SD:011 SG SH 0 1 SE:100 SC SB 0 0 SF:101 SC SD 0 0 SG:110 SE SF 0 0 SH:111 SG SH 0 1 解 1 原始状态表 解 2：直接设置状态记忆连续输入 1 的个数： S0：输入一个 0 和连续输入 0； S1：输入一个 1； S2：连续输入二个和二个以上 1。 如上设置电路状态，无论电路处于何态，对 于任何输入，其次态均为三种状态之一。当处于 S2态时，可检测连续输入三个和三个以上 1 的情
况。连接三种状态之间的转移连接,可得状态设 置方案2的原始状态图表如下。 0/0 004100 0/0 解2原始状态图 现态 次态 输出 x=1 X=0 000 解2的原始状态表 从例看到,实现同样逻辑功能,解1用八个 状态,解2用3个状态。状态数多则电路实现复 杂,成本高,应尽量减少状态数。 同一时序逻辑,不同状态设置方案所得原 始状态图中状态数之所以不同是因为状态数目 较多的设计结果中存在着多余状态。 ●如消除多余态,则可得相同的设计结果。 无法确保通过合适的状态设置直接得到 最少状态数的原始状态图,但有某些规范方法将 原始状态图中的多余状态消除。将原始状态图中 多余状态消除的过程之为状态化简
况。连接三种状态之间的转移连接，可得状态设 置方案 2 的原始状态图表如下。 1/0 S0 S1 S2 1/0 0/0 0/0 0/0 1/1 解 2 原始状态图 解 2 的原始状态表 从例看到，实现同样逻辑功能，解 1 用八个 状态，解 2 用 3 个状态。状态数多则电路实现复 杂，成本高，应尽量减少状态数。 ⚫ 同一时序逻辑，不同状态设置方案所得原 始状态图中状态数之所以不同是因为状态数目 较多的设计结果中存在着多余状态。 ⚫ 如消除多余态，则可得相同的设计结果。 ⚫ 无法确保通过合适的状态设置直接得到 最少状态数的原始状态图，但有某些规范方法将 原始状态图中的多余状态消除。将原始状态图中 多余状态消除的过程之为状态化简。 现态 次态 输出 x=0 x=1 x=0 x=1 S0 S0 S1 0 0 S1 S0 S2 0 0 S2 S0 S2 0 1
●随着集成电路密度的提高和可编程器件 的发展,对时序电路状态化简的考虑有所变化。 出于设计中的特殊考虑,不一定将电路状态化至 最简。但电路尽量简化的原则还是应该遵循的。 ●状态化简工作可由计算机完成。 ●所谓多余状态就是状态图中存在着可被 另一状态所代替的状态。 ●可以相互代替的状态称之为状态等价 如能找出原始状态图中所有相互等价态, 则可只留不相互等价态,得到最简状态图。 状态等价 如果将同一时序电路的两个状态S1和S分 别作为起始态,不论加入任何可能的输入序列, 电路均产生相同的输出序列,我们称S和S是 等价状态或等价对,记作S~S 等价具有传递性。即如有S~S,S~SK, 则有S~Sk 等价类:多个相互等价状态之集合。如上述 sSS构成一等价类。 最大等价类:在同一时序电路中,包含所有 相互等价的状态的等价类。不与其它任何状态等
⚫ 随着集成电路密度的提高和可编程器件 的发展，对时序电路状态化简的考虑有所变化。 出于设计中的特殊考虑，不一定将电路状态化至 最简。但电路尽量简化的原则还是应该遵循的。 ⚫ 状态化简工作可由计算机完成。 ⚫ 所谓多余状态就是状态图中存在着可被 另一状态所代替的状态。 ⚫ 可以相互代替的状态称之为状态等价。 ⚫ 如能找出原始状态图中所有相互等价态， 则可只留不相互等价态，得到最简状态图。 状态等价 如果将同一时序电路的两个状态 Si 和 Sj分 别作为起始态，不论加入任何可能的输入序列， 电路均产生相同的输出序列，我们称 Si 和 Sj 是 等价状态或等价对，记作 Si～Sj。 等价具有传递性。即如有 Si～Sj，Sj～SK， 则有 Si～SK。 等价类：多个相互等价状态之集合。如上述 SiSjSk构成一等价类。 最大等价类：在同一时序电路中，包含所有 相互等价的状态的等价类。不与其它任何状态等
价的单个状态也看成一个最大等价类。 等价的时序电路:满足等价条件的两个状态 分别在两个时序电路M和M中,两个状态也为 等价态。两个时序电路MM,它们各自的每个状 态都能在对方电路中至少找到一个等价态,则称 MM2是等价的时序电路,否则,是可区分的时序 电路。 等价态是可以互相替代或合并:因从输入和 输出的角度看,等价态的表现相同,无法区分。 状态化简:找出时序电路原始状态图中所有 的最大等价类,并从每个最大等价类选一状态作 为代表留用,消除其余态,得到最小化的状态图 和表。 完全确定的时序电路:原始状态图表中,对 应输入和现态的所有组合都有唯一确定的次态 和输出。它具有完全描述的状态表。包含有不确 定输出或次态的状态表为不完全描述的状态表, 对应的时序电路为不完全确定时序电路。 化简原则:最小闭覆盖。 1.最小性。简化后的状态数最少。 2.完备或覆盖性。原始状态表中的每个状 态都属于简化后状态中的一个
价的单个状态也看成一个最大等价类。 等价的时序电路：满足等价条件的两个状态 分别在两个时序电路 M1 和 M2 中，两个状态也为 等价态。两个时序电路 M1M2，它们各自的每个状 态都能在对方电路中至少找到一个等价态，则称 M1M2 是等价的时序电路，否则，是可区分的时序 电路。 等价态是可以互相替代或合并：因从输入和 输出的角度看，等价态的表现相同，无法区分。 状态化简：找出时序电路原始状态图中所有 的最大等价类，并从每个最大等价类选一状态作 为代表留用，消除其余态，得到最小化的状态图 和表。 完全确定的时序电路：原始状态图表中，对 应输入和现态的所有组合都有唯一确定的次态 和输出。它具有完全描述的状态表。包含有不确 定输出或次态的状态表为不完全描述的状态表， 对应的时序电路为不完全确定时序电路。 化简原则：最小闭覆盖。 1． 最小性。简化后的状态数最少。 2．完备或覆盖性。原始状态表中的每个状 态都属于简化后状态中的一个
3.封闭性。对简化后的最小化状态表中的 每个状态而言,在任何一种输入情况下,其次态 只能是简化后状态中的一个(而不是多个)。对 完全确定的时序电路,封闭性是自动满足的。而 对不完全确定的时序电路,不合理的选择简化后 的状态,将导致不满足封闭性。 完全确定的时序电路状态化简: 方法1:蕴含图法。 方法2:分隔法。 蕴含图法化简: 原理与步骤: 1.原始状态集中寻找所有的状态等价对; 2.组合出最大等价类集; 3.状态合并,构成最简状态集; 4.由最简状态集导出最小化状态图和表。 关键步骤是从原始状态集中寻找所有的等 价对:1.状态组对,2.等价判定。 组对易,判定难,利用推论。 判定等价就是考察在任一相同输入作用下
3． 封闭性。对简化后的最小化状态表中的 每个状态而言，在任何一种输入情况下，其次态 只能是简化后状态中的一个（而不是多个）。对 完全确定的时序电路，封闭性是自动满足的。而 对不完全确定的时序电路，不合理的选择简化后 的状态，将导致不满足封闭性。 完全确定的时序电路状态化简： 方法 1：蕴含图法。 方法 2：分隔法。 蕴含图法化简： 原理与步骤： 1．原始状态集中寻找所有的状态等价对； 2．组合出最大等价类集； 3．状态合并，构成最简状态集； 4．由最简状态集导出最小化状态图和表。 关键步骤是从原始状态集中寻找所有的等 价对：1.状态组对，2.等价判定。 组对易，判定难，利用推论。 判定等价就是考察在任一相同输入作用下
判定作为起始的两态及产生对应次态序列的输 出的是否相同,相同则等价,否则不等价。由此 可得判定两态等价的推论1和2。 推论1:在任一相同输入条件下,两态的输 出不同,两态一定不等价;两态输出相同,则需 继续判定对应次态是否等价。 推论2:在任一相同输入条件下,两态的输 出相同,若对应次态等价,则两态等价;对应次 态不等价,两态也不等价。 次态输出相同,需再考察次态对情况。如 设需等价判定的两态为SS,次态对的情况可分 两类:1.不变(即仍为SS),交错(即为SS1), 相同(即同为S)2.不属1的其它情况(即为 SnS)。 当次态属1类情况时,无论谁作起始态,任 一相同输入产生相同输出。 当次态属2类情况时状态SS等价否取决 与SSn,我们称之为状态隐含。状态隐含需对次 态继续进行追踪判定。如次态符合输入同,输出 同的同时,出现次态的次态又为原态,称之为互 为隐含。当互为隐含时,在任一相同输入作用下, 次态序列的输出也相同
判定作为起始的两态及产生对应次态序列的输 出的是否相同，相同则等价，否则不等价。由此 可得判定两态等价的推论 1 和 2。 推论 1：在任一相同输入条件下，两态的输 出不同，两态一定不等价；两态输出相同，则需 继续判定对应次态是否等价。 推论 2：在任一相同输入条件下，两态的输 出相同，若对应次态等价，则两态等价；对应次 态不等价，两态也不等价。 次态输出相同，需再考察次态对情况。如 设需等价判定的两态为 SiSj，次态对的情况可分 两类：1.不变（即仍为 SiSj），交错（即为 SjSi）， 相同（即同为 Sk）2.不属 1 的其它情况(即为 SmSn)。 当次态属 1 类情况时，无论谁作起始态，任 一相同输入产生相同输出。 当次态属 2 类情况时，状态 SiSj等价否取决 与 SmSn，我们称之为状态隐含。状态隐含需对次 态继续进行追踪判定。如次态符合输入同，输出 同的同时，出现次态的次态又为原态，称之为互 为隐含。当互为隐含时，在任一相同输入作用下， 次态序列的输出也相同
综上所述,可得推论3 推论3:在任一相同输入条件下,两态的 输出相同,且对应次态为不变、交错、相同和互 为隐含四种情况之一时,则两态等价。 根据推论1、2、3,可对状态对进行直观地 等价判定。 观察法等价对判定:适于比较简单的原始状 态图表化简。 例:观察法简化三位一判101检测器。观察 可得,状态S3、S4和S5在同样输入输出相同,且 次态相同,因此相互等价,可合并为一个状态, 用状态S代表。得最小化的状态图 三位一判101检测器 简化状态图 0/0 0/ 0/1/0 1/0 0/0 三位一判101检测器 0/01/00/01/1 原始状态图
综上所述，可得推论 3。 推论 3： 在任一相同输入条件下，两态的 输出相同，且对应次态为不变、交错、相同和互 为隐含四种情况之一时，则两态等价。 根据推论 1、2、3，可对状态对进行直观地 等价判定。 观察法等价对判定：适于比较简单的原始状 态图表化简。 例：观察法简化三位一判 101 检测器。观察 可得，状态 S3、S4和 S5在同样输入输出相同，且 次态相同，因此相互等价，可合并为一个状态， 用状态 S3代表。得最小化的状态图。 图4.12 例4.3三位一判101检测 电路的原始状态图 S0 1/0 0/0 S1 S2 S3 S4 S5 S6 0/0 0/0 0/0 0/0 0/0 0/0 1/0 1/0 1/0 1/0 1/0 1/0 1/0 S0 S1 S2 1/0 0/0 0/0 S3 S5 1/0 0/0 0/0 1/0 0/0 1/1 三位一判 101 检测器 原始状态图 三位一判 101 检测器 简化状态图
例:观察法化简不重码101检测器原始状态 图。S和S3输出同态,相互等价,合并为一状 态S,得简化状态图。 不重码101检测器 不筒化状态图 0/0 1/0 0/0 不重码101检测器 1/10/0 原始状态图 蕴含表法等价对判定:适于比较复杂的原始 状态图表,可防止遗漏,条理清晰。 蕴含表格式: S0S3等价 隐含状态 S2S5不等价 设全部原始状态按序排列为S.」S 1.建立网格,“掐头”“去尾”标注 2.逐格进行初始判定并填写结果。(等价
例：观察法化简不重码 101 检测器原始状态 图。 S0和 S3 输出同态，相互等价，合并为一状 态 S0，得简化状态图。 图4.13 例4.3不重码101检测电路 的原始状态图 S0 S1 S2 S3 0/0 0/0 1/0 1/1 0/0 1/0 0/0 1/0 1/0 S0 S1 S2 1/0 0/0 1/1 0/0 0/0 蕴含表法等价对判定：适于比较复杂的原始 状态图表，可防止遗漏，条理清晰。 蕴含表格式： S4 S5 S6 S3 S2 S1 × S2S3 S0S4 S1S3 S1 S2 S3 S4 S5 S0 S0 S3 等价 隐含状态 S3S5不等价 设 全 部 原 始 状 态 按 序 排 列 为 S0…SN 。 1.建立网格，“掐头”“去尾”标注。 2． 逐格进行初始判定并填写结果。（等价， 不重码 101 检测器 原始状态图 不重码 101 检测器 不简化状态图
不等价,隐含。) 3.对隐含进行追踪判定,直至判定结果确 定为等价或不等价。 完成追踪判定后,隐含表中所有非打“×” 方格对应的状态对即是我们要找的全部等价对。 例:对连续3个1检测解1的原始状态图表 表格法状态化简。 解1原始状态表 现态 次态 输出Z SA:000 B:001 010 SD:011 SF: 101 SG:110 SH: 111 0 AC AC AEVI CE C BF DF C BFV DF S××× ××× AC DE FBX EC DFX FBM × AC EC F BD FD × E F BD X × FDX BD AE CE X CECE AEV CE CEV CE G BF DF BFDF G BMV DF X × BFV DFX ××× × ××× ×× H ABCDEFG ABCDEFG (a)初始判定后 (b)追踪判定后
不等价，隐含。） 3． 对隐含进行追踪判定，直至判定结果确 定为等价或不等价。 完成追踪判定后，隐含表中所有非打“×” 方格对应的状态对即是我们要找的全部等价对。 例：对连续 3 个 1 检测解 1 的原始状态图表 表格法状态化简。 解 1 原始状态表 现态 次态 NS 输出 Z x=0 x=1 x=0 x=1 SA:000 SA SB 0 0 SB:001 SC SD 0 0 SC:010 SE SF 0 0 SD:011 SG SH 0 1 SE:100 SC SB 0 0 SF:101 SC SD 0 0 SG:110 SE SF 0 0 SH:111 SG SH 0 1 SE SF SG SD SC SB × AC BD SB SC SD SE SF SA SH SG × × × × × × × × × × × AE BF CE DF AC DF EC FB AC BD AE BF CE DF EC FD BD CE BF CE DF SE SF SG SD SC SB × AC BD× SB SC SD SE SF SA SH SG × × × × × × × × × × × AE BF CE DF× AC DF× EC FB AC BD× AE BF CE DF× EC FD× BD CE BF CE DF× (a)初始判定后 (b)追踪判定后