状态化简 1)完全确定的时序电路 ◆完全确定的时序电路 e Completely Specified Circuil ◆不完全确定的时序电路 ◆ Equivalent States ●状态表中包含不确定的输出或不确定的下 若S和S为时序电路的两个状态。作为当前状态时,不 论加入何种形式的输入(激励),电路输出均相同,且下 个状态,则称为不完全描述的状态表 一个状态等价,则称S和S是等价状态:否则称S和S ◆本质上化简问题是相同的,常用化简方法 不等价或可区分 ●观察法(1) ●从输入、输出角度看,两个等价状态无法区分,故可以 ●蕴涵表(2) 合井 完全定的时序电路eg53 e93状态化有工里她渣 ◆设计判断输入序列为101的检测器。输入为 X,输出为Z。画出状态图 输入X/输出Z ●对输入序列每3位进行一次判决:若3位代码是 101,则对应其最后一个1时,输出乙为1:其它 情况Z为0 ●例如X=010100101010 Z=000000001000 eg53状态化简 eg54状态化简 ◆观察法 ◆蕴涵表法 示例原始状态(转移) 当前状|下 ●找最大等价类(含所有彼此等价状态的等价类) 态S(n)X4 35 状态化简 ‹完全确定的时序电路 ‹不完全确定的时序电路 z状态表中包含不确定的输出或不确定的下一 个状态，则称为不完全描述的状态表 ‹本质上化简问题是相同的，常用化简方法 z观察法(1) z蕴涵表(2) 36 1)完全确定的时序电路 ‹Completely Specified Circuit ‹Equivalent States z 若Si 和Sj 为时序电路的两个状态。作为当前状态时，不 论加入何种形式的输入(激励)，电路输出均相同，且下 一个状态等价，则称Si 和Sj 是等价状态；否则称Si 和Sj 不等价或可区分 z 从输入、输出角度看，两个等价状态无法区分，故可以 合并 37 完全确定的时序电路 e.g.5.3 ‹设计判断输入序列为101的检测器。输入为 X，输出为Z。画出状态图 z对输入序列每3位进行一次判决；若3位代码是 101，则对应其最后一个1时，输出Z为1；其它 情况Z为0 z例如 X = 010 100 101 010 Z = 000 000 001 000 检测器 X Z CP 38 0/0 1/0 0/0 0/0 1/0 0/0 1/0 1/0 0/0 1/0 0/0 1/1 0/0 1/0 原始状态表 Pre- Next State Output Z sent State X=0 X=1 X=0 X=1 S0 S1 S2 0 0 S1 S3 S4 0 0 S2 S5 S6 0 0 S3 S0 S0 0 0 S4 S0 S0 0 0 S5 S0 S0 0 1 S6 S0 S0 0 0 S0 S1 S2 S3 S4 S5 S6 1/0 0/0 1/1 状态转移图 输入X/输出Z e.g.5.3 e.g.5.3 状态化简 39 ‹观察法 z找最大等价类(含所有彼此等价状态的等价类) S3、S4、S6 0/0 1/0 0/0 0/0 1/0 0/0 1/0 1/0 0/0 1/0 0/0 1/1 0/0 1/0 S0 S1 S2 S3 S4 S5 S6 1/0 0/0 0/0 1/0 0/0 1/0 0/0 0/0 1/1 1/0 S0 S1 S2 S3 S5 e.g.5.3 e.g.5.3 状态化简 40 ‹蕴涵表法 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × √ × × × ×× × × × √ 1,7 × × × 1,2 5,6 1,7 5,3 1,7 5,2 2,7 6,3 2,7 6,2 7,7 3,2 示例 原始状态(转移)表 当前状 下一个状态 S(n+1) 输出 Z(n) 态 S(n) X=0 X=1 X=0 X=1 S1 S7 S1 0 0 S2 S7 S1 0 0 S3 S1 S5 0 1 S4 S2 S6 0 1 S5 S7 S3 0 1 S6 S7 S2 0 1 S7 S1 S7 0 0 e.g.5.4 e.g.5.4 状态化简