数字逻辑设计及应用教学课件：7-5 同步状态机设计2

1、7.4 Clocked Synchronous State-Machine Design时钟同步状态机设计-217.4 Clocked Synchronous State-Machine DesignConstruct a state/output table (状态输出表) corresponding to the word description.(Optional)Minimize the number of states.State assignment.（choose a set of state variables）Substitute the state-variable com

2、bination into a state/output table to create a transition/output tableChoose a flip-flop type for the state memory.Construct an excitation table ,get excitation equation and output equation.Draw a logic diagram.2Examples for Clocked Synchronous State-Machine DesignTwo simple examplesDesign a 3 bit m

3、odulo-8 binary counter设计一个3位二进制模8计数器 Design a 110 sequence detector设计一个110序列检测器 Examples for state table designExample 1（P558）；Example 2（P566）；Example 3（P570）State diagram design（T-bird tail-light ）The Guessing Game 3Examples for Clocked Synchronous State-Machine DesignTwo simple examplesDesign a 3

4、bit modulo-8 binary counter设计一个3位二进制模8计数器 Design a 110 sequence detector设计一个110序列检测器 Examples for state table designExample 1（P558）；Example 2（P566）；Example 3（P570）State diagram design（T-bird tail-light ）The Guessing Game 4State table design（example 1）(P554)Design a clocked synchronous state machine

5、with two inputs, A and B, and a single output Z that is 1 if: A had the same value at each of the two previous clock ticks, or B has been 1 since the last time that the first condition was true. Otherwise, the output should be 0.设计一个具有2个输入（A、B），1个输出（Z）的时钟同步状态机，Z为1的条件是：在前2个脉冲触发沿上，A的值相同从上一次第1个条件为真起，B的

6、值一直为1500100111000011111006SAB00 01 11 10S*ZState ExpressInitial state INIT0A0A0A1A1A0Got a 0 on AGot a 1 on AA10OK0OK0Two equal,A=0 last OK0A1A10A0A0OK1Two equal,A=1 last OK1OK11OK0OK0OK1BA1因B而OK，A为1 OK1B1A0OK0BOK1OK1因B而OK，A为0 OK0B1A0OK0BOK1OK11OK0OK0OK1BA11、state table 7SAB00 01 11 10S*ZState Expre

7、ss1、state transition tableInitial state INIT0A0A0A1A1A0Got a 0 on A Got a 1 on A A10OK0OK0Two equal,A=0 last OK0A1A10A0A0OK1Two equal,A=1 last OK1OK11OK0OK0 OK1BA1因B而OK，A为1 OK1B1A0OK0BOK1OK1因B而OK，A为0 OK0B1A0OK0BOK1OK11OK0OK0OK1BA12、minimize the number of states OK1 OK1 OK0 OK0OK，A=0OK，=0OK，A=18初始状态

8、INITA0A上捕获一个0 A上捕获一个1 A1OK，A值为0 OK0OK，A值为1 OK1SAB00 01 11 10S*Z0A0A0A1A10OK0OK0A1A10A0A0OK1OK11OK0OK0 A11A0OK1OK1OK0 OK11、transition table 2、minimize 真的需要一一尝试吗？合理的状态赋值（P412）最简单的分解的单热点的准单热点的0001001011101113、 State assignment.从23中选5种一共有 种8!5!3!8!5!3!5种编码5个状态，又有5!种5!共有 94、transition /output tableINITA0

9、A1OK0OK1SAB00 01 11 10S*Z0A0A0A1A10OK0OK0A1A10A0A0OK1OK11OK0OK0 A11A0OK1OK1OK0 OK1 000100100100100100100101110101101101101101110110110110110111111111111111111Q1Q2Q3Q1*Q2*Q3*5 input variables： A,B,Q1,Q2,Q34 output variables ： Z,D1,D2,D3D1 D2 D3transition/excitationtable5、choice the Flip-Flop，get the

10、excitation equation and output equation.Use D Flip-Flop10AB00 01 11 10Z00011000100101110111Q1Q2Q3100100100100100101101101101110110110110101110111111111111111Q1*Q2*Q3*D1 D2 D3Q2Q3AB00 01 11 1000011110Q1=0D2Q2Q3AB00 01 11 1000011110Q1=100001100001101111110000000000000Minimal risk (最小冒险)，未用状态初始状态Output

11、 equation：Z = Q1Q211Q2Q3AB00 01 11 1000011110Q1=0D20000000000000000Minimal risk最小冒险，未用状态初始状态Q2Q3AB00 01 11 1000011110Q1=11100001101111110D2 = Q1Q3A + Q1Q3A + Q1Q2BQ2Q3AB00 01 11 1000011110Q1=0D20000dddddddddddd Minimal cost.最小成本，未用状态作为无关项D2 = Q1Q3A + Q3A+ Q2B12D1D2 = Q1Q3A + Q1Q3A + Q1Q2BD1 = Q2Q3 +

12、 Q1思考：最小成本法D1？13D3D3 = Q2Q3A + Q1AD2 = Q1Q3A + Q1Q3A + Q1Q2BD1 = Q2Q3 + Q1激励方程D3 = Q2Q3A + Q1A思考：最小成本法D3？146、draw the logic circuit（略）D3 = Q2Q3A + Q1AD2 = Q1Q3A + Q1Q3A + Q1Q2BD1 = Q2Q3 + Q1Excitation equationD3 = Q2Q3A + Q1AOutput equation：Z = Q1Q2说明： 最小冒险法 所有未用状态 “安全”状态. 最小成本法 所有未用状态的下一状态作为无关项 电路的

13、激励方程简单，不够安全.15合理的状态赋值选择复位时容易进入的状态作为初始状态.使每次转移时要发生改变的状态变量数最小化使一组相关状态中不变化的状态变量数最大化发现和利用问题描述中的对称性将状态变量组分解为有明确含义的位或字段，相对于状态机的输入效果或者输出特性可以使用多于最小值的状态变量数（便于分解）未用状态的考虑16Example 2： 1s-counting machine (“1”计数器)（P566）Design a clocked synchronous state machine with two inputs, X and Y, and one output, Z. The ou

14、tput should be 1 if the number of 1 inputs on X and Y since reset is a multiple of 4, and 0 otherwise.对两个输入X和Y同时计数，当1的个数为4的整数倍时输出为1.17Example 2 1s-counting machine （P567）1Got zero 1s S0S0XY 00 01 11 10Zmeaning SS*S1Got one 1s S1S2Got two 1s S2S10S1S2S3Got three 1s S3S20S2S3S0S3S3S0S1S000001111018Exa

15、mple 3：combination lock （P568）a “combination lock” state machine that activates an “unlock” output when a certain binary input sequence is received:Design a clocked synchronous state machine with one input, X, and two outputs, UNLK and HINT. The UNLK output should be 1 if and only if X is 0 and the

16、sequence of inputs received on X at the preceding seven clock ticks was 0110111. The HINT output should be 1 if and only if the current value of X is the correct one to move the machine closer to being in the “unlocked” state (with UNLK = 1).设计一个具有个输入和个输出（和）的时钟同步状态机当且仅当为并且前面个脉冲触发沿到来时接收到的输入序列为时，输出为当且

17、仅当的当前值是上述序列中的个正确值以使状态机逐步接近于“解锁”（即）状态时，输出为19Example 3：combination lock （P568）注意：输出是中间过程，应用时应隐藏207.5 Designing State Machines Using State Diagrams T-bird tail-light(570)LALBLCRARBRCINPUT：LEFT(左转)、RIGHT(右转)、HAZ（应急闪烁) , that requests the tail lights to be operated in hazardmodeall six lights flashing on

18、 and off in unison. a free-running clock signal (时钟信号)output：LC,LB,LA,RA,RB,RC(控制6个灯亮或灭 可以完全由状态控制) 21Step 1: set up enough state with different meaning ;Examples : T-bird tail lights control 22IDLE：全灭L1：左边1个灯亮L2：左边2个灯亮L3：左边3个灯亮R1：右边1个灯亮R2：右边2个灯亮R3：右边3个灯亮LR3：全亮状态输 出直接利用状态控制输出231、Initial state diagram

19、and output table 构造状态图IDLE：全灭L1：左边1个灯亮L2：左边2个灯亮L3：左边3个灯亮R1：右边1个灯亮R2：右边2个灯亮R3：右边3个灯亮LR3：全亮IDLEL1LL21L311R1RR21R311LR3H1HLRH+LRLHRRHL24IDLEL1LL21L311R1RR21R311LR3H1HLRH+LRLHRRHL1、构造状态图完备性 离开某一状态的弧线上的所有转移表达式的逻辑和为1。无二义性的HRH+RH+RHRHLHLH+LH+L改进互斥性 离开某一状态的弧线上的任意一对转移表达式的逻辑积为025Ambiguous(二义性) A state table i

20、s an exhaustive listing of the next states for each state/input combination. No ambiguity is possible. A state diagram contains a set of arcs labeled with transition expressions. Even when there are many inputs, only one transition expression is required per arc. However, when a state diagram is con

21、structed, there is no guarantee that the transition expressions written on the arcs leaving a particular state cover all the input combinations exactly once.26Ambiguous(二义性)In an improperly constructed (ambiguous) state diagram, the next state for some input combinations may be unspecified, which is

22、 generally undesirable, while multiple next states may be specified for others, which is just plain wrong. Thus, considerable care must be taken in the design of state diagrams; 272、状态编码Q2Q1Q00 0 00 0 10 1 10 1 01 0 11 1 11 1 01 0 01、构造状态图IDLEL1L2L3R1R2R3LR3合理的状态赋值3、得到转移列表 P427Output-Coded State Ass

23、ignment 282、状态编码1、构造状态图3、得到转移列表 P427HLRLHRRHL0 0 00 0 00 0 00 0 0H+LR0 0 00 0 11 0 11 0 0IDLEQ2Q1Q0 S转移表达式S* Q2*Q1*Q0*IDLEL1R1LR329Q2Q1Q0 S转移表达式S* Q2*Q1*Q0*HLRLHRRHLH+LR0 0 00 0 00 0 00 0 00 0 00 0 11 0 11 0 0IDLEIDLEL1R1LR3L10 0 10 0 1L2LR30 1 11 0 0HRH+RL20 1 10 1 1L3LR30 1 01 0 0HRH+RL30 1 0IDLE0

24、 0 01R11 0 11 0 1R2LR31 1 11 0 0HLH+LR21 1 11 1 1R3LR31 1 01 0 0HLH+LR31 1 0IDLE0 0 01LR31 0 0IDLE0 0 011111Q0* = Q2Q1Q0(LHR)+ Q2Q1Q0(RHL)+ Q2Q1Q0(HR)+ Q2Q1Q0(HL)= Q2Q1Q0 H(LR) + Q2Q1Q0(HR) + Q2Q1Q0(HL)用转移表综合状态机 P57730The Guessing Game猜谜游戏机（P580）Design a clocked synchronous state machine with four i

25、nputs, G1G4, that are connected to pushbuttons. The machine has four outputs, L1L4, connected to lamps or LEDs located near the like-numbered pushbuttons. There is also an ERR output connected to a red lamp. In normal operation, the L1L4 outputs display a 1-out-of-4 pattern. At each clock tick, the

26、pattern is rotated by one position; the clock frequency is about 4 Hz. Guesses are made by pressing a pushbutton, which asserts an input Gi.When any Gi input is asserted, the ERR output is asserted if the “wrong” pushbutton was pressed, that is, if the Gi input detected at the clock tick does not ha

27、ve the same number as the lamp output that was asserted before the clock tick. Once a guess has been made, play stops and the ERR output maintains the same value for one or more clock ticks until the Gi input is negated, then play resumes. 31The Guessing Game猜谜游戏机（P580）4个灯（G1G4）由时钟控制轮流亮起如果按下的按钮（L1L4

28、）与亮的灯对应，则猜对否则，ERR灯亮，表示猜错输入：G1、G2、G3、G4（4个按钮）输出：L1、L2、L3、L4、ERR（5个灯）状态：6个，S1S4对应L1L4 Serr对应ERR；SOK表示猜对32G1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G44个灯（L1L4）由时钟控制轮流亮起（没有按钮按下）S1L1=1S4L4=1S2L2=1S3L3=133G1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G4S1L1=1S4L4=1S2L2=1S3L3=1如果按下的按钮与亮的灯对应，则猜对（SOK）SOKG1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G4

29、34G1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G4S1L1=1S4L4=1S2L2=1S3L3=1SOKG1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G4否则猜错（Serr）SerrERR=1G2+G3+G4G1+G3+G4G1+G2+G4G1+G2+G335G1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G4S1L1=1S4L4=1S2L2=1S3L3=1SOKG1G2G3G4G1G2G3G4G1G2G3G4G1G2G3G4SerrERR=1G2+G3+G4G1+G3+G4G1+G2+G4G1+G2+G3G1+G2+G3+G4G1G2G3G4G1G

30、2G3G4G1+G2+G3+G4状态转换图361、状态转换图2、状态编码3、转移列表状态S编码Q2Q1Q0S1S2S3S4SOKSERR0 0 00 0 10 1 10 1 01 0 01 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 X X X X 0 1 X X X 0 0 1 X X 0 0 0 1 X 0 0 0 0 0 0 0 0 0 1用输出作为状态编码L1 L2 L3 L4 ERR 无关项的使用L1 L2 L3 L4 ERRP585表7-16P585表7-17P434表7-1737Minimal risk.(P563)Minima