第四章时序电路 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．完备或覆盖性。原始状态表中的每个状 态都属于简化后状态中的一个