5.1 Sequential- Circuit(时序辽电路 第五章时序电路设计 ●同步时序电路设计原理 具有 忆性的 同步时序电路设计实践 系统 同步电路故障与亚稳定性 ●异步时序电路分析与设计 ◆时序逻辑电路:组合逻辑+记忆电路 ●同步时序电路 ●异步时序电路 同步时序电路 同步时序电路 Synchronous Sequential Logic O Synchronous Sequential Logi ◆ State Diagran状态图) ◆ State Diagram(状态图)中,离开某个特定状 ● Moore机的输出只是当前状态的函数 态的所有转移条件,满足 ●Meab机的输出是当前输入和当前状态的函数 ● Mutual exclusion(互斥性),否则相同输入组合对应 不同的下一状态(二义性) Note:Meab机的状态图中,当状态机处于 态并且在当前输入作用下,立即产生状态图对应输 dll Inclusion(完备性),每种输入组合都有确定的下 出,而不必等到状态机转移为下一状态才出现输出 状态(有时需要根据设计需求,在不违背题意的 前提下作出合理安排) ●称为完全确定的时序电路 51同步附序电路设计 同步慰序电路谩计租 ◆ Digital Design:7.4 ◆得到状态转移图 ◆同步时序电路 ◆建立状态转移输出表 ●Moe型和 Melay型电路,可以相互转化 ◆导出状态方程、激励方程和输出方程 ◆同步时序电路模型 ◆画时序电路逻辑图 ●状态机相当于计数器驱动的存储器 检查电路:避免挂起(该步骤有时可省略) ●输出级是组合电路,也可以用通用存储器来实现
1 1 第五章 时序电路设计 z 同步时序电路设计实践 z 同步时序电路设计原理 z 同步电路故障与亚稳定性 z 异步时序电路分析与设计 11 5.1 Sequential-Circuit Sequential-Circuit (时序逻辑电路) 时序逻辑电路：组合逻辑+记忆电路 z同步时序电路 z异步时序电路 具有 记忆性的 系统 a b c x y z 12 同步时序电路 Synchronous Sequential Logic State Diagram(状态图) zMoore机的输出只是当前状态的函数 zMealy机的输出是当前输入和当前状态的函数 Note: Mealy机的状态图中，当状态机处于所示的状 态并且在当前输入作用下，立即产生状态图对应输 出，而不必等到状态机转移为下一状态才出现输出 13 同步时序电路 Synchronous Sequential Logic State Diagram(状态图)中，离开某个特定状 态的所有转移条件，满足 zMutual Exclusion(互斥性)，否则相同输入组合对应 不同的下一状态(二义性) zAll Inclusion(完备性)，每种输入组合都有确定的下 一状态(有时需要根据设计需求，在不违背题意的 前提下作出合理安排) z称为完全确定的时序电路 14 5.1 同步时序电路设计 Digital Design: 7.4 同步时序电路 zMoore型和Melay型电路，可以相互转化 同步时序电路模型 z状态机相当于计数器驱动的存储器 z输出级是组合电路，也可以用通用存储器来实现 18 得到状态转移图 建立状态转移/输出表 导出状态方程、激励方程和输出方程 画时序电路逻辑图 检查电路：避免挂起 (该步骤有时可省略) 同步时序电路设计流程
eg51罔步序谩计 eg51同步肘序设计 ◆5状态组成的计数器,周期性工作 ◆控制信号通过同步置数使电路保持初态 ◆5状态→3位码→右移码 2=Q2Q1Q0 Z=02 210+0, 00+2012 00+02 ggo eg51同步慰序谩计 步时序电路设计租 n+1时刻 ◆得到状态转移图 ●逻辑抽象,原始状态转移图 状态化简 D=DX g0+-=x/:88 Q2(n+1) ◆建立状态转移输出表( Transition/output table) ◆导出状态方程、激励方程和输出方程 ◆或者直接按真值表(图)进行设计 ◆画时序电路逻辑图( Logic diagran) D:=2,2+01 2 20=2,212o D=2.2.+0,9 ◆检查电路:避免挂起 =Q23 同步序电路设计滤霍 eg52获得状态转巷图杀剑 ◆1.逻辑抽象,原始状态转移图 ◆设计一个2输入八A和B),1输出(乙)同步时序电 ●将每一个状态预设为电路当前状态,按设计要求和各种 路,Z为1的条件是 可能的输入,确定当前输出和下一状态:注明输入和 ●情形1:前两个时钟采样时刻,A输入值相同 出,给出原始状态图 ●情形2:从情形1出现时刻起,B的值一直为1 ●为避免遗,可多设状态 ◆2.状态化简:状态数目最小化( State Minimization ●状态化简:申路状态数越少,存储申路越简单 ◆3.状态编码( State assignment ●状态编码:编码方案选择得当,电路可以简化
2 19 e.g.5.1 e.g.5.1 同步时序设计 5状态组成的计数器，周期性工作 控制信号通过同步置数使电路保持初态 T0 T1 T2 T4 T3 置数X 20 e.g.5.1 e.g.5.1 同步时序设计 5状态 Æ 3位码 S2 S5 S1 Z0=1 Z1=1 0 0 0 1 00 1 0 0 1 10 1 1 0 1 11 1 1 1 0 11 0 1 1 0 00 0 0 1 0 00 0 1 0 0 00 1 0 1 0 00 Z0 = Q2Q1Q0 1 0 1 20 21 2 0 1 1 20 0 1 Z Q QQ QQQ QQQ QQ QQQ =++ = + Q2 Q1 Q0 Q2 Q1 Q0 S0 S4 S6 S3 S7 置数X n时刻 n+1时刻 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 Æ 右移码 21 e.g.5.1 e.g.5.1 同步时序设计 或者直接按真值表(图)进行设计 Z0 = Q2Q1Q0 Z11 0 = + Q QQ QQ 201 0 2 1 1 1 2 1 2 0 D Q Q D Q Z D Q Z ′ = ⋅ ′ = ⋅ ′ = ⋅ Di = Di ′⋅ X X Di ′ "0" Di 2 22 1 11 0 00 ( 1) ( 1) ( 1) Qn D D X Qn D D X Qn D D X += = ⋅ ′ += = ⋅ ′ += = ⋅ ′ 2 20 1 0 1 2 21 0 0 21 D QQ QQ D QQ QQ D QQ ′ = + ′ = + ′ = 0 0 0 1 00 1 0 0 1 10 1 1 0 1 11 1 1 1 0 11 0 1 1 0 00 0 0 1 0 00 0 1 0 0 00 1 0 1 0 00 Q2 Q1 Q0 Q2 Q1 Q0 n时刻 n+1时刻 22 得到状态转移图 z 逻辑抽象，原始状态转移图 z 状态化简 z 状态编码 建立状态转移/输出表(Transition/output table) 导出状态方程、激励方程和输出方程 画时序电路逻辑图(Logic diagram) 检查电路：避免挂起 同步时序电路设计流程 23 1. 逻辑抽象，原始状态转移图 z 将每一个状态预设为电路当前状态，按设计要求和各种 可能的输入，确定当前输出和下一状态；注明输入和输 出，给出原始状态图 z 为避免遗漏，可多设状态 2. 状态化简: 状态数目最小化(State Minimization) z 状态化简：电路状态数越少，存储电路越简单 3. 状态编码(State assignment) z 状态编码：编码方案选择得当，电路可以简化 同步时序电路设计流程 25 e.g.5.2 e.g.5.2 获得状态转移图示例 设计一个2输入(A和B)，1输出(Z)同步时序电 路，Z为1的条件是 z情形1：前两个时钟采样时刻，A输入值相同； z情形2：从情形1出现时刻起，B的值一直为1。 采样时刻
eg52款得状态转移图杀侧 状态化简( 移到OK1毒 ◆设计一个2输入(A和B),1输出(2)同步时序电路,Z ◆2输入A和B),1输出(2同步时序电路4=1的条件 为1的条件是 ●情形1:前两个时钟采 A输入值 ●情形1:前两个时钟采样时刻,A输入值相同 ●情形2:从情形1出现时 B的值一 含义 含义 011110 Init, So S,St 时钟采样时刻,A=0s 时钟果样时制,A=0s。 Ok OK S1s-o 时钟采样时刻,A=1s 时钟果样时A=1s1s。s。okok0 Two equal, A=0 last Oko ot 00 or 11 on Ao equal,A=1lastor wo equal, A=0 last oko ok.bk Jok, s, 录简状悫表(录小化状态表 录简状感歌又m ◆2输入(A和B),1输出()同步时序电路,Z=1的条件 时钟采样时刻,A=0 ●情形1 时钟采样时刻,A=1 so S, Ok, Ok,0 两个A输入相同,A=0。k nts。s。s1s1 时钟采样时刻,A=0s。10k。0k0S1S10 时钟采样时刻,A=1s:|s。s。Ok1O 两个A输入相同,A=0ok。 OKo Oko Ok1s 6@ 两个A输入相同,A=10k:s。Ok0Ok1Ok 昨录小化状态表示侧「(态转移表 非录小化含m ●情形1:前两个时钟采样时刻,A ●情形2:从情形1出现时刻赶 直为 删己a 含 轴入AB got a 1 on A l oka, I 5o Oka, Oku,:I1 时钟果样时制A=0s。ok。ok。s1s1 时蝉采样时A=1s1|s。s。ok1Ok Got 0o on aokoo okooko oka, s Got 11 on A, Iso Oka: 1 Ok, got a o on Alokao okoo Koo Oka, S ok,gota1 on A loka1|s。oka。ok1ok1
3 26 e.g.5.2 e.g.5.2 获得状态转移图示例 设计一个2输入(A和B)，1输出(Z)同步时序电路，Z 为1的条件是 z 情形1：前两个时钟采样时刻，A输入值相同 z 情形2：从情形1出现时刻起，B的值一直为1 State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 Ok 时钟采样时刻, A=0 时钟采样时刻, A=1 Got 00 or 11 on A 含义 Ok Ok S1 S1 0 S0 S0 Ok Ok 0 1 27 状态化简 2输入(A和B)，1输出(Z)同步时序电路，Z=1的条件 z 情形1：前两个时钟采样时刻，A输入值相同 z 情形2：从情形1出现时刻起，B的值一直为1 State Init Ok1 初态 S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 Ok0 时钟采样时刻, A=0 时钟采样时刻, A=1 Two equal, A=1 last Two equal, A=0 last 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 1 1 Ok1 Ok0 Two equal, A=1 last Two equal, A=0 last Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 转移到OK0态 AB=01ÆA＝0 转移到OK1态 AB=11ÆA＝1 28 最简状态表(最小化状态表) 2输入(A和B)，1输出(Z)同步时序电路，Z=1的条件 z 情形1… z 情形2… State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 时钟采样时刻, A=0 时钟采样时刻, A=1 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 Ok1 Ok0 两个A输入相同, A=1 两个A输入相同, A=0 Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 30 最简状态表 State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 时钟采样时刻, A=0 时钟采样时刻, A=1 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 Ok1 Ok0 两个A输入相同, A=1 两个A输入相同, A=0 Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 0X S0/0 S1/0 Ok0/1 Ok1/1 输入AB Init/0 1X 1X 0X 0X 0X 11 1X 10 01 1X 00 31 非最小化状态表 非最小化状态表 示例 z 情形1：前两个时钟采样时刻，A输入值相同 z 情形2：从情形1出现时刻起，B的值一直为1 State Init Ok11 初态 S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 Ok00 时钟采样时刻, A=0 时钟采样时刻, A=1 Got 11 on A Got 00 on A 含义 Ok00Ok00 S1 S1 0 S0 S0 Ok11Ok11 0 Ok00Ok00Oka1 S1 1 S0 Oka0Ok11Ok11 1 Oka1 Oka0 Ok，got a 1 on A Ok，got a 0 on A Ok00Ok00Oka1 S1 1 S0 Oka0Ok11Ok11 1 状态转移表(图) 怎样画简？ 33 非最小化… State Init Ok11 初态 S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 Ok00 时钟采样时刻, A=0 时钟采样时刻, A=1 Got 11 on A Got 00 on A 含义 Ok00 Ok00 S1 S1 0 S0 S0 Ok11Ok11 0 Ok00 Ok00Oka1 S1 1 S0 Oka0Ok11Ok11 1 Oka1 Oka0 Ok，got a 1 on A Ok，got a 0 on A Ok00Ok00Oka1 S1 1 S0 Oka0 Ok11Ok11 1 0X S0/0 S1/0 Ok00/1 Ok11/1 输入AB Init/0 1X 1X 0X 0X 0X 11 1X 10 1X 00 Oka0/1 Oka1/1 11 0X 1X 10 00 11 01
状态化简 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)X
4 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 状态化简
eg54状悫化简 eg54状态化简 ●蕴含表是一个直角梯形网格,特点是缺头少尾,任何 个状态都能在一个网格中相遇一 ●相同输入下输出相同,且下1个状态相同,等价填"v ●相同输入下输出相同,且下1个状态交错或自环,等价 ●不等价网格中填”×”;其它情形填相F ×|×(x eg54状态化简:=一柔叠 2)不完全确定的时序电路 最小化状态表 Incompletely Specified Circuit ◆ Compatible States 两个状态S和S相容:当且仅当对于每一种可能的输 入,S和S确定的输出相容或确定的次态相容 00 ◆寻找相容状态 ●利用“蕴涵表 ◆关联结果 ●最大等价类(S1S2,S7) 区K区 ◆寻找最大相容类 (S3S),(S4),(S) x×1 ●当且仅当相容类包含所有与之相容状态 ●从每个最大等价类中选一个状 ●通过“归井图( Merger diagram)得到 态,列出最小化状态表 √×× Is state minimization really necessary 状态分配(状志躺码 O These procedures are seldom used by most designers 状态分配( State assignment) O By carefully matching state meanings to the ●把状态表中每个字符表示的状态对应地规定一个二 requirements of the problem, experienced digital 进制代码,得出代码形式状态表——状态编码 designers produce state tables for small problems with ●分配合理,能使电路得到简化 a minimal or near-minimal number of states. without ◆状态分配方案 using a formal minimization procedure ●n个变量有2种组合,用来对s个状态进行编码共有 OAlso, there are situations where increasing the number 叫/(2-s)分配方案 of states may simplify the design or reduce the cost, so ●已证明,独立的状态分配方案数为(2-1)/(2s)n even an automated state-minimization procedure 码方案数 doesn t necessarily help L图 7L8 140420840840[0810800 5
5 41 示例 原始状态表 当前状 下一个状态 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 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 z 蕴含表是一个直角梯形网格，特点是“缺头少尾”，任何 两个状态都能在一个网格中相遇一次； z 相同输入下输出相同，且下1个状态相同，等价填″√″ z 相同输入下输出相同，且下1个状态交错或自环，等价 z 不等价网格中填‘″×″；其它情形填相应等价条件 e.g.5.4 e.g.5.4 状态化简 42 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × 9 × × × ×× × × × 9 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 1,7 3,2 9 8 9 8 8 8 8 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × √ × × ××× × × × √ × × × × × × × × √ √ e.g.5.4 e.g.5.4 状态化简 43 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × √ × × ××× × × × √ × × × × × × × × √ √ 最小化状态表 当前状 下一个状态 S(n+1) 输出 z(n) 态 S(n) X=0 X=1 X=0 X=1 S1 S1 S1 0 0 S3 S1 S3 0 1 S4 S1 S6 0 1 S6 S1 S1 0 1 关联结果 z 最大等价类(S1，S2，S7)， (S3，S5)，(S4)，(S6) z 从每个最大等价类中选一个状 态，列出最小化状态表 示例 原始状态表 当前状 下一个状态 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 状态化简 44 2)不完全确定的时序电路 Incompletely Specified Circuit Compatible States z 两个状态Si 和Sj 相容：当且仅当对于每一种可能的输 入，Si 和Sj 确定的输出相容或确定的次态相容 寻找相容状态 z 利用“蕴涵表” 寻找最大相容类 z 当且仅当相容类包含所有与之相容状态 z 通过“归并图”(Merger diagram)得到 45 Is state minimization really necessary? These procedures are seldom used by most designers By carefully matching state meanings to the requirements of the problem, experienced digital designers produce state tables for small problems with a minimal or near-minimal number of states, without using a formal minimization procedure Also, there are situations where increasing the number of states may simplify the design or reduce the cost, so even an automated state-minimization procedure doesn’t necessarily help 46 状态分配(状态编码) 状态分配(State assignment) z把状态表中每个字符表示的状态对应地规定一个二 进制代码，得出代码形式状态表——状态编码 z分配合理，能使电路得到简化 状态分配方案 zn个变量有2n种组合，用来对s个状态进行编码共有 2n!/ (2n-s)!分配方案 z已证明，独立的状态分配方案数为(2n-1)!/ (2n-s)! n! 编码方案数 s 2 3 4 5 6 7 8 9 n 1 2 2 3 3 3 3 4 N 1 3 3 140 420 840 840 10810800
eg55状态分配示侧 状态分配方索(1) ◆用D触发器设计如下表的时序电路 Karnaugh Maps(1) Output Excitation Equations(1) 00011110 Ago 1110 D,=A=C,X, +B,CX+A, B, C,+A, B,c D=B=C,X, +B. X+A, B, C.+A. B. Bo+ Dc=Cn=A, BX,+BCrX,+BCrX 10[2。。 +AB.X+ABC.X+ABcx Z=AB+AC+ABc ◆电路显得复杂 改进才食:状悫分配方食(2) 状态分配方(2)
6 47 状态表 当前状 下一个状态 输出 态 X=0 X=1 X=0 X=1 S1 S3 S2 1 1 S2 S7 S8 0 0 S3 S6 S1 0 0 S4 S4 S5 0 0 S5 S3 S2 0 0 S6 S4 S5 1 1 S7 S6 S1 1 1 S8 S7 S8 1 1 状态分配方案(1) 状态 状态代码 A B C S1 0 0 0 S2 0 0 1 S3 0 1 0 S4 0 1 1 S5 1 0 0 S6 1 0 1 S7 1 1 0 S8 1 1 1 e.g.5.5 e.g.5.5 状态分配示例 用D触发器设计如下表的时序电路 48 方案(1)状态转换表 当前状态 下一个状态 An Bn Cn 输入 Xn An+1 Bn+1 Cn+1 输出 Zn 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 状态分配方案(1) 49 Karnaugh Maps(1) Karnaugh Maps(1) Cn+1 An+1 AnBn CnX 00 01 11 10 00 01 11 10 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 AnBn CnX 00 01 11 10 00 01 11 10 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 Zn AnBn CnX 00 01 11 10 00 01 11 10 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 Bn+1 AnBn CnX 00 01 11 10 00 01 11 10 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 50 Zn = AnBn + AnCn + AnBnCn DA = An+1 =Cn Xn + BnCn Xn + AnBnCn + AnBnCn Output & Excitation Equations(1) Output & Excitation Equations(1) 电路显得复杂 DB = Bn+1 =Cn Xn + BnCnXn + AnBnCn + AnBnCn n n n n n n n n n n n n n A B C X A B C X A B C X DC C AnBnXn BnCnXn BnCnXn + + + = +1 = + + 51 状态分配方案(2) 状态 状态代码 A B C S1 1 0 1 S2 1 1 0 S3 0 1 0 S4 0 0 0 S5 1 0 0 S6 0 0 1 S7 0 1 1 S8 1 1 1 改进方案：状态分配方案(2) 52 方案(2)状态转换表 当前状态 下一个状态 An Bn Cn 输入 Xn An+1 Bn+1 Cn+1 输出 Zn 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 状态分配方案(2)
Karnaugh Maps(2) Output Excitation Equations (2) 000111 o11 cn+2010 D,=A,=X Zn 状态分配(状态躺码) 次佳状态分配方食 ◆怎样选择最好的状态分配方案? ◆相邻状态分配法 ●n个变量有2种组合,用来对个状态进行编码共有 ●次态相同,现态相邻 2/(2-s)分配方案 使下一个状态较少依赖于当前状态 ●已证明,独立的状态分配方案数为(22-1)/(2-s)m On-I=g(gn, Wn) ●遗憾的是:至今没有找到普遍有效的算法实现最佳 同一现态,次态相邻 状态分配,唯一途径是将所有分配方案都试个遍 一使下一个状态较少依赖于输入变量 ●次佳状态分配方案:相邻状态分配法,建立通用方 On+=On, Xn) 程法,减少相关法 ●输出相同,现态相邻 使输出较少依赖于当前状态 Zn=Z(Qn, Km) 次佳状忐分配示侧 状态分配方余(3) 状态分 p ◆规则1(次态相同):S1SS2S8,S3S7,Ss6 ◆规则2(现态相同):S1S8,S5823878 ◆规则3(输出相同):S1S6SS8S2S3S5 7
7 53 Cn+1 An+1 Karnaugh Maps(2) Karnaugh Maps(2) Zn AnBn CnX 00 01 11 10 00 01 11 10 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 AnBn CnX 00 01 11 10 00 01 11 10 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 Bn+1 AnBn CnX 00 01 11 10 00 01 11 10 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 AnBn CnX 00 01 11 10 00 01 11 10 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 54 DA = An+1 = X n Output & Excitation Equations(2) Output & Excitation Equations(2) DB = Bn+1 = An DC = Cn+1 = Bn Zn = Cn Xn CP D Q D Q D Q A B C Zn 55 状态分配(状态编码) 怎样选择最好的状态分配方案？ zn个变量有2n种组合，用来对s个状态进行编码共有 2n!/ (2n-s)!分配方案 z已证明，独立的状态分配方案数为(2n-1)!/ (2n-s)! n! z遗憾的是：至今没有找到普遍有效的算法实现最佳 状态分配，唯一途径是将所有分配方案都试个遍 z次佳状态分配方案：相邻状态分配法，建立通用方 程法，减少相关法 56 次佳状态分配方案 相邻状态分配法 z 次态相同，现态相邻 ——使下一个状态较少依赖于当前状态 Qn+1= Q(Qn , Wn) z 同一现态，次态相邻 ——使下一个状态较少依赖于输入变量 Qn+1= Q(Qn , Xn) z 输出相同，现态相邻 ——使输出较少依赖于当前状态 Zn = Z(Qn , Xn) 57 次佳状态分配示例 Pre-sent Next State OutPut State X=0 X=1 X=0 X=1 S1 S3 S2 1 1 S2 S7 S8 0 0 S3 S6 S1 0 0 S4 S4 S5 0 0 S5 S3 S2 0 0 S6 S4 S5 1 1 S7 S6 S1 1 1 S8 S7 S8 1 1 规则1(次态相同): S1S5, S2S8 , S3S7 , S4S6 规则2(现态相同): S1S6 , S4S5, S2S3, S7S8 规则3(输出相同): S1S6 S7S8, S2S3 S4S5 S4 S3 S7 S2 S8 S1 S5 S6 58 状态分配方案(3) 状态 状态代码 A B C S1 0 0 0 S2 1 0 1 S3 1 1 1 S4 1 1 0 S5 1 0 0 S6 0 1 0 S7 0 1 1 S8 0 0 1 状态分配方案(3) S6 S7 S3 S8 S2 S1 S5 S4 000 010 110 100 111 001 101 011
状态分配才食(3) Output Excitation Equations(3) 匚在状毒 D4=A= Da=B=X 1 : B D=B=X 0■0■01 1001 寧种编码才食录佳?A17 寧种编码方食录佳? ◆ Digital Design:74 ◆ Digital Design:7.4 ◆唯一途径是把所有编码方案都试一把 ◆2">S时,存在未用状态 ised states)状态 ◆状态编码:从2种可能组合中选择S种编码 编码可根据应用要求选用两种方法 2=3,S=5时,可能性(2”).s!=6720种 ●最小成本法( Minimal cost S!·(2-S)! ●最小冒险法( Minimal risk ●采用相邻状态编码方案,或可根据应用选用两种 处理方法 常用状态编码方囊A19 eg52同步时序设计 ● Sequential state assignment(顺序赋值) ◆设计一个2输入八A和B),1输出(乙)同步时序电 ● Decomposed state assignment(分解賦值) 路,Z为1的条件是 >一个大型状态机用着千小型状态机的集合来实夷 ●情形1:前两个时钟采样时刻,A输入值相同 ● Cyclic- code assignment(循环码) ●情形2:从情形1出现时刻起,B的值一直为1 多余状态较多 >激勵方程筒单 ● One-hot assignment(单热点) 多余状态很多 激励方程筒单,尤其适合选1编码输出情形 ● Almost one- hot assignment(准单热点) 采时离 相对于 One-hot assignment,加金Q状
8 59 方案(3)状态转换表 现在状态 下一个状态 An Bn Cn 输入 Xn An+1 Bn+1 Cn+1 输出 Zn 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 1 状态分配方案(3) DA = An+1 = Cn DB = Bn+1 = X n DC = Cn+1 = Bn Zn = An S6 S7 S3 S8 S2 S1 S5 S4 000 010 110 100 111 001 101 011 60 Output & Excitation Equations(3) Output & Excitation Equations(3) DA = An+1 = Cn DB = Bn+1 = X n DC = Cn+1 = Bn Zn = An CP D Q D Q D Q B C A Zn Xn 61 哪种编码方案最佳？A17 Digital Design：7.4 唯一途径是把所有编码方案都试一把 状态编码：从2n种可能组合中选择S种编码 zn=3, S=5时，可能性 z采用相邻状态编码方案，或可根据应用选用两种 处理方法 (2 ) ! 6720 (2 )! n n S S S ⋅ = ⋅ − ！ 种 ！ 62 哪种编码方案最佳？ Digital Design：7.4 2n>S时，存在未用状态(unused states). 状态 编码可根据应用要求选用两种方法 z最小成本法(Minimal cost) z最小冒险法(Minimal risk) 63 常用状态编码方案A19 zSequential state assignment (顺序赋值) zDecomposed state assignment (分解赋值) ¾一个大型状态机用若干小型状态机的集合来实现 zCyclic-code assignment (循环码) ¾多余状态较多 ¾激励方程简单 zOne-hot assignment (单热点) ¾多余状态很多 ¾激励方程简单，尤其适合s选1编码输出情形 zAlmost one-hot assignment (准单热点) ¾相对于One-hot assignment，增加全0状态 65 e.g.5.2 e.g.5.2 同步时序设计 设计一个2输入(A和B)，1输出(Z)同步时序电 路，Z为1的条件是 z情形1：前两个时钟采样时刻，A输入值相同； z情形2：从情形1出现时刻起，B的值一直为1。 采样时刻
录简状态表(录小化状态表) 录简状库学 ◆2输入(A和B),1输出(2)同步时序电路,Z=1的条件 时钟采样时刻,A=0s ●情形1 时钟采样时刻,A= ss s, Ok, OK,o 情形2 两个A输入相同,A=0k 两个A输入相同,A=1|ok1s。0k0k2Ok ints。sos1s 时钟采样时刻,A=0s。ok0k。s1S1 时钟采样时刻,A=1s1|s。s。Ok:0 |@@似少 两个A输入相同,A=0ok。ok。 Oko Ok, S1 两个A输入相同,A=1ok:|s。ok。Ok:Ok Moore机:轴入AB 逻綜合 Minimal risk approach状态躺哥 ◆最小风险法 ◆状态编码时钟采样时到A=1 Ok, Ok ●基于状态机有可能进入未用状态的假设 状态机每种未用状态,都明确其下一个状态为初始态 Decomposed:其余空闲态下一状态均指向全0初态 空闲态或其它”安全”状态 常用设置—全0状态 ● Almost one-ho 00010 01000 0000 辽辑综合 Minimal risk approach 辽辑综合 Minimal cost approach ◆最小风险法z=QQ2Q3+QQ2Q=Q·Q ◆最小成本法 ●未用状态标识为无关项 ●利用无关项,可以达到画简之目的 D2 AB 0203 0111 ◆最小成本法 ●基于状态机不可能进入未用状态这一前提 [。p 旦状态机进入未用状态,行为不用预知 因此,需要增加检查步骤:确认能进入正常状态 叫吨aaa 0102.B
9 66 最简状态表(最小化状态表) 2输入(A和B)，1输出(Z)同步时序电路，Z=1的条件 z 情形1… z 情形2… State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 时钟采样时刻, A=0 时钟采样时刻, A=1 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 Ok1 Ok0 两个A输入相同, A=1 两个A输入相同, A=0 Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 67 最简状态表 State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 时钟采样时刻, A=0 时钟采样时刻, A=1 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 Ok1 Ok0 两个A输入相同, A=1 两个A输入相同, A=0 Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 0X S0/0 S1/0 Ok0/1 Ok1/1 Moore机：输入AB Init/0 1X 1X 0X 0X 0X 11 1X 10 01 1X 00 68 逻辑综合Minimal risk approach 最小风险法 z基于状态机有可能进入未用状态的假设 z状态机每种未用状态，都明确其下一个状态为初始态、 空闲态或其它”安全”状态 常用设置——全0状态 69 State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 时钟采样时刻, A=0 时钟采样时刻, A=1 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 Ok1 Ok0 两个A输入相同, A=1 两个A输入相同, A=0 Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 状态编码 状态编码 z Sequential z Decomposed z One-hot z Almost one-hot S0 S1 : 其余空闲态下一状态均指向全0初态 70 逻辑综合Minimal risk approach 最小风险法 1 1 23 2 1 13 12 3 3 1 23 D Q QQ D QQ A QQ AQQ B D QAQQ A =+ ⋅ = ⋅ ⋅+ ⋅ ⋅+ ⋅ ⋅ = ⋅+ ⋅ ⋅ Z =⋅⋅ +⋅⋅=⋅ QQQ QQQ QQ 12 123 12 3 71 逻辑综合Minimal cost approach 最小成本法 z未用状态标识为无关项 z利用无关项，可以达到画简之目的 最小成本法 z基于状态机不可能进入未用状态这一前提 z一旦状态机进入未用状态，行为不用预知 因此，需要增加检查步骤：确认能进入正常状态
状态编母说A 逞辑综合 Minimal cost approach ◆状态编码 两个A输入相同,A= ◆最小成本法z=Q ● Sequential[两个A入相同,A D1=1 D,=0034+034+0 ● Almost on 01000 逻桿综合 Minimal cost approach|g56李列检阅墨(會吗锁) ◆最小成本法z=Q2 ◆ Combination lock D ◆设计一个1输入X)2输出Unk,Hint同步时序电 D,=0034+0A+0, B 路.当且仅当 ●X=0且前面7个时钟采样时刻X收到的输入序列为 0110111时,输出Unk为1 X当前输入是上述序列(01101110中使状态机逐步 接近于解锁状态即Unk=1的比特时,输出Hint为 显然,它是 Mealy machine eg56李列检测暴(會喝帧) eg56序列检测暴(會嗔) ◆1输入()2输出(unk,Hint同步时序电路当且仅当 D,=g02 x+20, 9,x+90: g X=0且之前时刻X收到的输入序列为0110111,输出Unk为1 ●X当前输入是上述序列中使Unk=1的比特时,输出Hin为1 =2+2+2x+F+,xam ◆状态化简与编码 状态化简 ● Sequential顺序编码 Got D CEDD A0o Ol Got 0110 E B, 00 (,OD Got 01 1011 G E, 00 (HOD I 00l.1l000 State and S·,UNLK 02.03 UNLK HINT Q1023°UNLK 10
10 72 State 初态 Init S0 S0 S1 S1 0 Inputs AB= 00 01 11 10 Output Z S0 S1 时钟采样时刻, A=0 时钟采样时刻, A=1 含义 Ok0 Ok0 S1 S1 0 S0 S0 Ok1 Ok1 0 Ok1 Ok0 两个A输入相同, A=1 两个A输入相同, A=0 Ok0 Ok0 Ok1 S1 1 S0 Ok0 Ok1 Ok1 1 状态编码 状态编码 z Sequential z Decomposed z One-hot z Almost one-hot S0 S1 73 逻辑综合Minimal cost approach 最小成本法 1 21 3 2 3 3 D 1 D QQ A QA QB D A = = ++ = Z = Q2 74 逻辑综合Minimal cost approach 最小成本法 Z = Q2 1 21 3 2 3 3 D 1 D QQ A QA QB D A = = ++ = 75 e.g.5.6 e.g.5.6 序列检测器（密码锁） Combination Lock 设计一个1输入(X)2输出(Unlk, Hint)同步时序电 路. 当且仅当 zX=0且前面7个时钟采样时刻X收到的输入序列为 0110111时，输出Unlk为1 zX当前输入是上述序列(01101110)中使状态机逐步 接近于解锁状态即Unlk=1的比特时，输出Hint为1 z显然，它是Mealy machine 76 e.g.5.6 e.g.5.6 序列检测器（密码锁） 1输入(X)2输出(Unlk, Hint)同步时序电路. 当且仅当 z X=0且之前时刻X收到的输入序列为0110111，输出Unlk为1 z X当前输入是上述序列中使Unlk=1的比特时，输出Hint为1 Transition/ excitation table State and output table 77 e.g.5.6 e.g.5.6 序列检测器（密码锁） 1 1 123 12 2 3 2 32 2 3 3 1 13 2 23 2 13 3 D QQ X QQQ X QQ Q D QQX QQX D QQ Q QQ X Q X Q Q X Q Q X =+ + = + = + ++ + Transition/ excitation table 状态化简与编码 z 状态化简 z Sequential 顺序编码
