Latches
Flip Flops
Algorithmic State Machines

low_key发布于2019/01/29

1.Lecture 7 Topics Latches Flip Flops Algorithmic State Machines

2.Latches

3.Possible States for Light Switch

4.S-R Latch S R Q + 0 0 Q 0 1 0 1 0 1 1 1 0 S-R latch is reset dominant Different ways to name/nomenclature for current/next state. Text uses Q+ for next.

5.Alternative Nomenclature for latches Present State Next State Output Symbol Output Symbol Q Q Q Q(t+1) Qt Q(t+1) Qn Q(n+1) Q0 Q Y Y + y Y

6.S-R Latch States S-R latch is reset dominant

7.Characteristic Equations for SR latch

8.Present State/Next State Table ( PS/NS) for SR Latch

9.Present State/Next State Table ( PS/NS) for SR Latch Another notation, stable states in circles, I think it is a better notation Students should be able to analyze and draw transitions in a machine Reset dominant

10.Timing Diagram for SR Latch

11.Detailed Discussion of Timing Diagram for SR Latch

12.Races Just as we used K-maps to not only reduce Boolean equations but to detect hazards, we can use K-maps to analyze anomalous latch behavior as well. Race is when two or more inputs change simultaneously. May or may not be a critical race. Depends upon the behavior of the circuit.

13.Critical Races Can happen when two signals change at the same time

14.Critical Race We start in State represented by minterm m3. (stable state) Q is 0, SR are 11s. Both S and R are transitioning to 0. Notice we take different paths through the K-map depending upon whether R or S transitions first. If S transitions first, we transition to state m0 where Q+ remains Q (no transitions on output). However , if R transitions first, we attempt to set the latch, resulting in Q+ = 1. Then , when S transitions we go to state m4 . Not only do we end up in different states, but we have different values on the Q output – all depending upon minor differences in relative timing between transitions on S/R. This is a critical race . Start from here

15.Critical Race Critical Race

16.Non-Critical Races

17.Non-critical race: Start in state m6 (stable) with SR 10. Both S and R are going to change. If S changes first, we go to state m4 (a stable state) with no transition on output. Then when R changes we transition to state m1, also a stable state, and with an output of 0. If R changes first, we transition to state m3 , a stable state with a transition to 0 on output. When S subsequently changes we transition to m1 , another stable state where Q remains 0. Non-critical race – OK and correct behavior regardless of which signal transitions first. Non-critical Race

18.Metastable State

19.Metastable State An often overlooked condition in which the output can remain in an illegal (even oscillating) state for an indeterminant period of time. Metastability can be caused by a runt pulse (a positive or negative pulse which never achieves either a value of a 1 or 0). This can occur when two inputs to a gate change near simultaneously (see hazards earlier). Metastability can also occur when two inputs to a latch change near simultaneously. Condition also arises when synchronizing with external events (e.g. asynchronous inputs to synchronous finite state machines).

20.Bistable element The simplest sequential circuit Two states One state variable, say, Q HIGH Let us set this to High and see what will happen First we discuss correct behavior of a bistable element

21.Bistable element The simplest sequential circuit Two states One state variable, say, Q HIGH LOW

22.Bistable element The simplest sequential circuit Two states One state variable, say, Q HIGH LOW LOW

23.Bistable element The simplest sequential circuit Two states One state variable, say, Q HIGH LOW LOW HIGH

24.Bistable element The simplest sequential circuit Two states One state variable, say, Q LOW Let us set this to Low and see what will happen

25.Bistable element The simplest sequential circuit Two states One state variable, say, Q LOW HIGH

26.Bistable element The simplest sequential circuit Two states One state variable, say, Q LOW HIGH HIGH

27.Bistable element The simplest sequential circuit Two states One state variable, say, Q LOW HIGH HIGH LOW

28.Analog analysis Assume pure CMOS thresholds, 5V rail Theoretical threshold center is 2.5 V

29.Analog analysis Assume pure CMOS thresholds, 5V rail Theoretical threshold center is 2.5 V 2.5 V Now we discuss incorrect behavior of a bistable element

30.Analog analysis Assume pure CMOS thresholds, 5V rail Theoretical threshold center is 2.5 V 2.5 V 2.5 V

31.Analog analysis Assume pure CMOS thresholds, 5V rail Theoretical threshold center is 2.5 V 2.5 V 2.5 V 2.5 V

32.Analog analysis Assume pure CMOS thresholds, 5V rail Theoretical threshold center is 2.5 V 2.5 V 2.5 V 2.5 V 2.5 V

33.

34.

35.

36.

37.ANIMATED = Analog analysis Assume pure CMOS thresholds, 5V rail Theoretical threshold center is 2.5 V 2.5 V 2.5 V 2.5 V 2.0 V 2.0 V 4.8 V 2.5 V 2.51 V 4.8 V 0.0 V 0.0 V 5.0 V

38.Metastability Metastability is inherent in any bistable circuit Two stable points , one metastable point stable stable

39.Another look at metastability

40.“ sube y baja ” behavior

41.Why all the harping on metastability ? All real systems are subject to it Problems are caused by “asynchronous inputs” that do not meet flip-flop setup and hold times. Details in Chapter-7 flip-flop descriptions and in Section 8.9 (later in quarter). Especially severe in high-speed systems since clock periods are so short, “ metastability resolution time” can be longer than one clock period. Many digital designers, products, and companies have been burned by this phenomenom .

42.Back to the bistable …. How to control it? Screwdriver Control inputs S-R latch Correct behavior

43.S-R latch operation without metastability Correct behavior

44.S-R latch operation with metastability Metastability is possible if S and R are negated simultaneously. (try it in Foundation) Correct behavior

45.State Machines

46.State Diagrams – example of state diagram for an SR Latch S R Q + 0 0 Q 0 1 0 1 0 1 1 1 0 S R Q Q + 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0

47.Algorithmic State Machines (ASM) false true The student should be able to transform state diagram to algorithmic state machine and vice versa

48.Clock Circuits

49.Clock (Oscillator) Circuit PS/NS Table K-map State Diagram Delay Model

50.Clock Waveforms, T , t p and f Delay Buffers Additional (maintain odd number) inverters RC circuit Crystal Oscillator

51.Clock signals Very important with most sequential circuits State variables change state at clock edge. State changes with leading slope State changes with falling slope

52.Gated Sequential Circuits Addition of control input Gated Latch (Level Activated) Edge-Triggered Flip Flop Pulse Triggered Flip Flop

53.Gated SR Latch

54.Gated SR Latch Using NANDs

55.Gated D Latch D Q + 0 0 1 1 D Latch is Hazard Free (product terms chain-linked)

56.Timing of a Gated D Latch Good behavior, signal D was long enough, longer than setup time t w = pulse width t su = setup time t h = hold time t si = t su +t h = sampling period Clock changes to 1 This pulse is too short, FF did not change to stable 1 Length of Signal D was longer than t si and D=1 included interval t si Illustration of correct behavior of Gated D Latch

57.Gated D Latch Timing Good behavior, signal D was long enough, longer than setup time Bad behavior, signal D was NOT long enough, setup time was violated Bad behavior, signal D was NOT long enough, hold time was violated Illustration of two cases of incorrect behavior of Gated D Latch

58.Use of gated D latches as Storage Elements Tri-state Tri-state

59.D Flip-Flop

60.Flip Flop Circuits Pulse Narrowing Circuit Explain pulse-narrowing circuit . Attach as front end to D flip flop’s C input.

61.Edge-Triggered D Flip Flop

62.Manual Reset of D Flip Flop Generates half clock frequency

63.74LS74A

64.Other D flip-flop variations Negative-edge triggered Clock enable We read to FF only when Enable signal is =1 Otherwise the old state of the FF is preserved in a feedback loop. This is an important circuit. The MUX on the input is important in other applications.

65.Important These were asynchronous circuits that are used as parts of synchronous circuits. Now we will be not concerned with designing asynchronous circuits, although they exist in every synchronous circuit. We will design on the level of SYNCHRONOUS circuits.

66.Simple Applications of Flip-Flops: Shifters and Counters

67.Shifters and Counters D Q c D Q c D Q c Shifter to right, analyze its behavior D Q c D Q c D Q c Johnson or Moebius counter, analyze its behavior Q’ All FFs connected to the same clock Students should be able to convert the logic diagrams like these to state graphs and state tables

68.Shifters that is Cyclical and shifts to right D Q c D Q c D Q c Shifter to right, analyze its behavior 000 111 100 010 001 110 011 101

69.D Q c D Q c D Q c Johnson or Moebius counter, analyze its behavior Q’ All connected to the same clock Shifters that takes negated output as input and works as an inexpensive counter. 000 100 110 001 011 111

70.State Diagrams for Binary Up Counters Students should be able to convert the state diagrams like these to finite state machine schemata from flip-flops and logic gates. Typical Problems. Build the counter from this state diagram using only T flip-flops . Build modulo-5 counter from D flip-flops

71.D Q c D Q c D Q Generalized Registers 1 2 3 0 1 2 3 0 1 2 3 0 Control bits select operation executed in the Generalized Register Green connection selected by control 00 are shift non-cyclically to right Blue connections selected by control 01 are shift cyclically to the lef t You should be able to add connections for any other operations on this Generalized Register

72.Shifters and Counters D Q c D Q c D Q c Linear Counter, analyze its behavior D Q c D Q c D Q c General Autonomous FSM with shifts and arbitrary logic function, analyze its behavior Q’ EXOR gate Arbitrary logic function Students should be able to convert the logic diagrams like these to state graphs and state tables ANALYSIS OF MACHINES IS IMPORTANT AND WILL BE ON EXAM

73.Flip-Flops for testing

74.SCAN Flip-flops are used for testing Scan TEST ENABLE TEST INPUT

75.Scan flip-flops -- for testing TE = 0 ==&gt; normal operation TE = 1 ==&gt; test operation All of the flip-flops are hooked together in a daisy chain from external test input TI. Load up (“scan in”) a test pattern, do one normal operation, shift out (“scan out”) result on TO.

76.Other types of Flip-Flops

77.JK Flip Flops J K Q + Comment 0 0 Q No change 0 1 0 Reset 1 0 1 Set 1 1 Q Toggle

78.JK FF is built from D FF and some gates J-K flip-flops Not used much anymore Don’t worry about them Interesting concept to be used in design

79.T Flip Flops J = K=T Q + Comment 0 0 0 Q No change 0 1 1 0 1 1 1 Q Toggle T flip-flop created from JK flip-flop T flip-flop working from leading slope of clock T flip-flop working from falling slope of clock

80.T flip-flops Important for counters When EN=1 it toggles, when EN=0 no change of state When EN=1 it toggles with leading slope of T, when EN=0 no change of state

81.Sequential PALs 16R8 Tri=state

82.Analysis of a Counter from JK Flip-Flops

83.4-Bit Binary Up Counter T flip flops ideal for counters (remain same or toggle)! A Counter built from JK flip-flops Question to students: Find what is the sequence of states of this counter by analyzing the circuit using method shown previously A B C D

84.Counter Timing Diagram 000 000 States of individual flip-flops What is a period of this counter? What is the binary sequence of states?

85.State Machines State Transition Diagrams Next State Tables Mealy and Moore Machines Mealy: Output logic uses current state and inputs Moore : Output logic uses only current state One Hot vs. Encoded State Machines

86.Iterative Circuits versus State Machines

87.Draw the graph of the table and explain in detail how the pattern recognition works REMINDER: Cell Table to design iterative circuits Cell table: analogous to state table Example: 0101 pattern detector Assuming the same assignment for states ( A : 00, B : 01, C : 11, D : 10): each cell same as the combinational logic of the sequential circuit derived for the 0101 sequence detector in future slides for state machine. Present states Next states outputs Two carry signals denote the state of recognition of our sequence 0101 Sequence 0101 recognized for the first time Sequence 0101 recognized for the second time Initial carry Input sequence of arbitrary length

88.Synthesis for Iterative Circuit Example: synthesize an n -cell iterative network Each cell has one cell input x i and one cell output z i z i = 1: if and only if either one or two of the cell inputs x 1 , x 2 , …, x i have value 1 States A , B , C , D : 0, 1, 2, (3 or more) of the cell inputs to preceding cells have value 1 Cell table Cell Output-carries and cell-output table Encode: A=00 B=01 C=11 D=10 After encoding the table becomes a KMap This is like three Kmaps in one. First for Y i1 , second for Y i2 , third for z i

89.X 1 X 2 X 3 X 4 Z 1 Z 2 Z 3 Z 4 0 0 Observations: This is a systematic method to design iterative circuits This method is very similar to designing finite state machines that will covered soon. Good example are comprators , adders, subtractors , comparators.

90.Synthesis for Finite State Machine yi1 yi2\ xi 0 1 00 0 0 01 0 1 11 1 1 10 1 1 Y i1 yi1 yi2\ xi 0 1 00 0 1 01 1 1 11 1 0 10 0 0 Y i2 yi1 yi2\ xi 0 1 00 0 1 01 1 1 11 1 0 10 0 0 z i D1 Q1 D2 Q2 These must be D ffs

91.D1 Q1 D2 Q2 Comparison of Iterative Circuit and Finite State Machine X 1 X 2 X 3 X 4 Z 1 Z 2 Z 3 Z 4 0 0 The internal state in Flip-flops in Finite State Machine corresponds to the value of the carry signal in Iterative Circuit. Data are given sequentially in FSM and in parallel in Iterative Circuit

92.Now we create a feedback through flip-flops , not an iterative circuit as before. Please understand similarity and difference. This is very important, you can expect this on Finals.

93.Larger Practical Examples of State Machines

94.Example 1: T-bird tail-lights

95.ANIMATED: T-bird tail-lights example

96.ANIMATED: T-bird tail-lights example

97.ANIMATED: T-bird tail-lights example

98.ANIMATED: T-bird tail-lights example

99.Inputs: LEFT, RIGHT, HAZ Outputs: Six lamps (function of state only ) LC, LB, LA, RC, RB, RA hazard Alarm state, all lights State diagram for lights Idle state, no lights Name of state Name of input

100.Encoded or One-Hot? Encoded 8 states 2 3 = 8 N eed 3 flip flops Need to determine state assignment One-hot Dedicate a flip flop per state Need 8 flip flops First we have decide what kind of encoding we need. The best method is to start synthesis starting from the state graph like in the last slide

101.First Method to calculate outputs for Moore Machine

102.Implementation (Encoded, Moore Machine) Next State Logic Output Logic Inputs Outputs Current State Realization of output logic

103.Output logic: outputs are functions of only states LC = L3 + LR3 LB = L2 + L3 + LR3 LA = L1 + L2 + L3 + LR3 RA = R1 + R2 + R3 + LR3 RB = R2 + R3 + LR3 RC = R3 + LR3 This table shows Output signals for internal states We create equations for outputs, based on the table from the left Observe that we need only OR gates applied to FFs that encode states This method is not minimal Inputs: LEFT, RIGHT, HAZ Outputs: Six lamps (function of state only ) LC, LB, LA, RC, RB, RA outputs states states This method can be used for both One –Hot encoding and binary encoding.

104.Variant to calculate output functions in which the binary encoding of internal states is used

105.Output logic: outputs are functions of only states LC = L3 + LR3 LB = L2 + L3 + LR3 LA = L1 + L2 + L3 + LR3 RA = R1 + R2 + R3 + LR3 RB = R2 + R3 + LR3 RC = R3 + LR3 LC = Q2’ × Q1 × Q0’ + Q2 × Q1’ × Q0’ LB = Q2’ × Q1 × Q0 + Q2’ × Q1 × Q0’ + Q2 × Q1’ × Q0’ LA = Q2’ × Q1’ × Q0 + Q2’ × Q1 × Q0 + Q2’ × Q1 × Q0’ + Q2 × Q1’ × Q0’ RA = Q2 × Q1’ × Q0 + Q2 × Q1 × Q0 + Q2 × Q1 × Q0’ + Q2 × Q1’ × Q0’ RB = Q2 × Q1 × Q0 + Q2 × Q1 × Q0’ + Q2 × Q1’ × Q0’ RC = Q2 × Q1 × Q0’ + Q2 × Q1’ × Q0’ Q2 Q1 Q0 This table shows Output signals for internal states This table shows Encoding of internal states We create equations based on the table from the left This method is not minimal but does not require Kmaps

106.Methods to create transition function

107.Two Methods to create the Next State Logic State transition table for encoded states Next step depends on implementation choice Synthesize or Structural with choice of FFs The next step is to calculate the excitation functions for D flip-flops Encoding of internal states This table is created from the state graph AND the encoding of internal states

108.Method 1 to create transition function. E This method is easy but not minimal

109.Transition Equations for Q2* = D2 Q2* = Q2’ × Q1’ × Q0’ × (HAZ + LEFT × RIGHT) + Q2’ × Q1’ × Q0’ × (RIGHT × HAZ’ × LEFT’) + Q2’ × Q1’ × Q0 × (HAZ) + Q2’ × Q1 × Q0 × (HAZ) + Q2 × Q1’ × Q0 × (HAZ’) + Q2 × Q1’ × Q0 × (HAZ) + Q2 × Q1 × Q0 × (HAZ’) + Q2 × Q1 × Q0 × (HAZ) Q2* = Q2’ × Q1’ × Q0’ × (HAZ + RIGHT) + Q2’ × Q0 × HAZ + Q2 × Q0 The simplification of equation for Q2* is done using transformations of equation on the left or using Kmaps .

110.Transition Equations for Q2* = D2 Q2* = Q2’ × Q1’ × Q0’ × (HAZ + LEFT × RIGHT) + Q2’ × Q1’ × Q0’ × (RIGHT × HAZ’ × LEFT’) + Q2’ × Q1’ × Q0 × (HAZ) + Q2’ × Q1 × Q0 × (HAZ) + Q2 × Q1’ × Q0 × (HAZ’) + Q2 × Q1’ × Q0 × (HAZ) + Q2 × Q1 × Q0 × (HAZ’) + Q2 × Q1 × Q0 × (HAZ) Q2* = Q2’ × Q1’ × Q0’ × (HAZ + RIGHT) + Q2’ × Q0 × HAZ + Q2 × Q0 The simplification of equation for Q2* is done using transformations of equation on the left or using Kmaps .

111.Transition Equations for Q0* = D0 Q0* = Q2’ × Q1’ × Q0’ × (LEFT × HAZ’ × RIGHT’) + Q2’ × Q1’ × Q0’ × (RIGHT × HAZ’ × LEFT’) + Q2’ × Q1’ × Q0 × (HAZ’) + Q2 × Q1’ × Q0 × (HAZ’) Q0* = Q2’ × Q1’ × Q0’ × HAZ ’ × (LEFT Å RIGHT) + Q1’ × Q0 × HAZ’ No guarantee these are minimal. They certainly aren’t SOP. What we do next depends upon how we’re going to implement the FSM. Could just give them whole thing to ABEL or some other tool and let it generate minimal SOP. Also, transition equation isn’t same as excitation equation (unless we’re using D FFs)

112.Optimizing the speed of my machine

113.Implementation (Encoded, Moore Machine) Next State Logic Output Logic Inputs Outputs Current State What should the clock’s period be?

114.How Fast Can the Clock Be? Combinational Logic Clock D1 Q D2 FF t pd Combinational t pd FF t setup FF 1 FF 2 You want the signal to propagate as fast as possible through this logic Propagation delay

115.Clock Skew Clock D1 Q D2 FF t pd Combinational t pd FF t setup Even with careful routing, clock will not arrive at all FFs at the same time. This s kew in clock arrival time affects max c lock rate. Clock Skew Clock Period min = FF t pd + FF t setup + C t pd + t skew

116.Clock Period min = FF t pd + FF t setup + C t pd + t skew t clk = t ffpd + t comb + t setup -time-margin + t setup Another notation to explain clock period calculations

117.Method 2 when costs of flip-flops are not that important to create transition function

118.One-Hot Transitions IDLE* = IDLE × (HAZ + LEFT + RIGHT)’ + L3 + R3 + LR3 L1* = IDLE × LEFT × HAZ’ × RIGHT’ R1* = IDLE × RIGHT × HAZ’ × LEFT’ L2* = L1 × HAZ’ R2* = R1 × HAZ’ L3* = L2 × HAZ’ R3* = R2 × HAZ’ LR3* = IDLE × (HAZ + LEFT × RIGHT) + (L1 + L2 + R1 + R2) × HAZ No decoding of state required Flip-flop L1 has value 1 when machine is in state L1. Otherwise it has value 0. This is one-hot coding. Easy and fast.

119.Behavioral Verilog If you understand Boolean Equations and the methods presented above, it is very easy to write Verilog code for every Finite State Machine. Below I give a template how to create a behavioral specification of any state machine in Verilog. You should be able to reuse this template, only change the Boolean Equations.

120.Better Still – Behavioral Verilog parameter IDLE = 8b00000001, L1 = 8b00000010, L2 = 8b00000100, L3 = 8b00001000, R1 = 8b00010000, R2 = 8b00100000, R3 = 8b01000000, LR3 = 8b10000000; reg [7:0] State, NextState; case (State) IDLE: begin if (Hazard | Left &amp; Right) NextState = LR3; else if ( Left ) NextState = L1; else if ( Right ) NextState = R1; else NextState = IDLE; end L1: begin if ( Hazard ) NextState = LR3; else NextState = L2; end L2: begin if ( Hazard ) NextState = LR3; else NextState = L3; end L3: begin NextState = IDLE; end R1: begin if ( Hazard ) NextState = LR3; else NextState = R2; end R2: begin if ( Hazard ) NextState = LR3; else NextState = R3; end R3: begin NextState = IDLE; end LR3:begin NextState = IDLE; end endcase Inputs: LEFT, RIGHT, HAZARD Outputs: Six lamps (function of state only ) LC, LB, LA, RC, RB, RA Encoding of outputs

121.Better Still – Behavioral Verilog case (State) IDLE: begin if ( Hazard | Left &amp; Right ) NextState = LR3; else if ( Left ) NextState = L1; else if ( Right ) NextState = R1; else NextState = IDLE; end Inputs: LEFT, RIGHT, HAZARD Outputs: Six lamps (function of state only ) LC, LB, LA, RC, RB, RA Left &amp; (Hazard | Left &amp; Right)’ = Left &amp; (Hazard’ &amp; (Left &amp; Right)’) = Left &amp; Hazard’ (Left’ | Right’) = Left &amp; Hazard’ &amp; Right’ Here we show how the Verilog Code can be transformed using Boolean Algebra to the state graph.

122.Example 2: Traffic Light Controller

123.Example: Traffic Light Controller N S E W Sensors in road detect approaching car on NS and EW roads, generating input signals NScar and EWcar respectively. Lights are controlled by outputs NSlite and EWlite . Traffic lights should change only if there is a car approaching from the other direction. Otherwise the lights should remain unchanged. NScar EWcar Clock Traffic Light Controller NSlite EW lite r sensors lights Internal state Internal state Output state

124.Example: Traffic Light Controller Transition Function r State assignment NSgreen = 0 EWgreen = 1 =1 = 0 State assignment Output function CurrentState ’ CurrentState

125.Example: Traffic Light Controller. General Method r 00 01, 11 10 00 01 10,11 State\ Inputs 00 01 11 10 NSgreen NSgreen EWgreen EWgreen NSgreen EWgreen EWgreen EWgreen NSgreen NSgreen Create directly Gray Code and KMap ENCODE Nsgreen = 0 Ewgreen = 1 After encoding you obtain an encoded table, which in general you separate to several KMaps , as shown in several examples before. You minimize these Kmaps using methods that you know from previous lectures. Draw the schematic with logic and FFs.

126.Example 3: NRZ to Manchester Encoder

127.Behavioral Verilog 2 If you understand Boolean Equations and the methods presented above, it is very easy to write Verilog code for every Finite State Machine. Below I give another template how to create a behavioral specification of any state machine in Verilog. You should be able to reuse this template, only change the Boolean Equations.

128.// // Moore FSM for serial line conversion: NRZ to Manchester encoding // module NRZtoManchester (Clock, Clear, BitIn , BitOut ); input Clock, Clear, BitIn ; output BitOut ; reg BitOut ; // define states using same names and state assignments as state diagram and table // Using one-hot method, we have one bit per state parameter S0 = 4b0001, S1 = 4b0010, S2 = 4b0100, S3 = 4b1000; reg [3:0] State, NextState ; // Update state or reset on every - clock edge always @( negedge Clock) begin if (Clear) begin State &lt;= S0; \$display(&quot;Reset: S0&quot;); end else begin State &lt;= NextState ; \$display(&quot;State: % d&quot;,State ); end end Verilog States and state assignment Description of sequential part with clearing and next state, this is universal. Changes with negative slope . BitIn Clock Clear NRZ to Manchester Encoder BitOut

129.// Outputs depend only upon state (Moore machine) always @(State) begin case (State) S0: BitOut = 1b0

130.Method 3 in which we minimize the transition functions optimally SYNTHESIS OF MACHINES IS IMPORTANT AND WILL BE ON EXAM SYNTHESIS OF NRZ TO MANCHESTER ENCODER USING KMAPS AND MINIMIZATION

131.S0 0 S1 0 S3 1 S2 1 0 0 0 1 1 1 PS B in = 0 B in = 1 S0 S1 S3 S1 S2 - S3 - S0 S2 S1 S3 00 01 11 10 Pay attention to don’t cares created

132.Example 4: Airplane Gear

133.Airplane Gear Example PilotLever GearIsUp Airplan e Landing Gear Control Valve PlaneOnGround GearIsDown Pump RedLED GreenLED PilotLever O perated by pilot to control landing gear (1:down 0:up) PlaneOnGround Sensor 1 when plane on ground GearIsUp Sensor 1 when landing gear fully up GearIsDown Sensor 1 when landing gear fully down TimeUp 1 when two second timer expired Valve Controls position of valve (1:lowering 0:raising) Pump Activates hydraulic pump (1: activate) ResetTimer 1 to reset count-down timer, 0 to count RedLED Indicates landing gear in motion GreenLED Indicates landing gear down Do not retract landing gear if plane on ground Plane should be airborne two seconds before retracting gear TimeUp ResetTimer inputs outputs Respond to changes in lever position (in case plane started with lever in up position)

134.State Transition Diagram Waiting for TakeOff Waiting for Timer Gear Up Raising Gear Lowering Gear ~PlaneOnGround PlaneOnGround TimeUp &amp; ~ PilotLever GearIsUp ~ PilotLever PilotLever PlaneOnGround Reset State Reset Timer Pump Valve RedLED GreenLED WaitingforTakeoff 1 0 X 0 1 WaitingforTimer 0 0 X 0 1 RaisingGear X 1 0 1 0 GearUp X 0 X 0 0 LoweringGear X 1 1 1 0 GearDown X 0 X 0 1 Gear Down ~ PilotLever GearIsDown PilotLever Output functions

135.Airplane Landing Gear Example Lever GearUp Airplan e Landing Gear Control Valve OnGround GearDown Pump RedLED GreenLED Lever O perated by pilot to control landing gear (0:down 1:up) OnGround Sensor 1 when plane on ground GearUp Sensor 1 when landing gear fully up GearDown Sensor 1 when landing gear fully down Valve Controls position of valve (0:lowering 1:raising) Pump Activates hydraulic pump RedLED Indicates landing gear in motion GreenLED Indicates landing gear down Do not retract landing gear if plane on ground Plane should be airborne two seconds before retracting gear

136.What students can do with this example ? You can complete this example using any of the several method shown above. I suggest first to use Method 2 based on One-Hot Encoding. Next use Method 3. Next describe the problem using Verilog.

137.Example 5: Design Using JK Flip-flops

138.Example 5: Design Using JK Flip-flops

139.Example 7: Registers, Shifters, Generalized Registers Bidirectional Shift Register with Parallel Load D Q C D Q C D Q C D Q C A 0 A 1 A 2 A 3 Clock I 0 I 1 I 2 I 3 Shift Register, non-cyclic, shifts to right D Q C D Q C D Q C D Q C Serial Input Clock Serial Output D Q C D Q C D Q C D Q C A 0 A 1 A 2 A 3 4 x 1 MUX 4 x 1 MUX 4 x 1 MUX 4 x 1 MUX Clock S 0 S 1 SeriaI Input I 0 I 1 I 2 I 3 Serial Input Register This is example of “Generalized Register” control Students please analyze this circuit and understand what it does.

140.Example 8: Counter modulo 16 with JK flip-flops that act as T flip-flops J K Q J K Q J K Q J K Q Clock Counter Enable A 0 A 1 A 2 A 3 Output Carry

141.Example 9: Vending Machine Taken from Katz &amp; Borriello , “Contemporary Logic Design”

142.Vending Machine FSM N D Reset Clock Open Coin Sensor Release Mechanism Example: vending machine Release item after 15 cents are deposited Single coin slot for dimes, nickels No change nickel dime

143.Example: vending machine. Create a tree Suitable abstract representation tabulate typical input sequences: 3 nickels nickel, dime dime, nickel two dimes draw state diagram: inputs: N, D, reset output: open chute assumptions: assume N and D asserted for one cycle each state has a self loop for N = D = 0 (no coin) S0 Reset S2 D S6 [open] D S4 [open] D S1 N S3 N S5 [open] N S8 [open] D S7 [open] N

144.Example: vending machine. Minimize machine to minimum number of states Minimize number of states - reuse states whenever possible symbolic state table present inputs next output state D N state open 0¢ 0 0 0¢ 0 0 1 5¢ 0 1 0 10¢ 0 1 1 – – 5¢ 0 0 5¢ 0 0 1 10¢ 0 1 0 15¢ 0 1 1 – – 10¢ 0 0 10¢ 0 0 1 15¢ 0 1 0 15¢ 0 1 1 – – 15¢ – – 15¢ 1 0 ¢ Reset 5 ¢ N N N + D 10 ¢ D 15 ¢ [open] D

145.present state inputs next state output Q1 Q0 D N D1 D0 open 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 – – – 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 – – – 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 – – – 1 1 – – 1 1 1 Example: vending machine: Encoding (or state assignment) of internal states Uniquely encode states

146.D1 = Q1 + D + Q0 N D0 = Q0 ’ N + Q0 N ’ + Q1 N + Q1 D OPEN = Q1 Q0 Example: Moore implementation Mapping to logic 0 0 1 1 0 1 1 1 X X 1 X 1 1 1 1 Q1 D1 Q0 N D 0 1 1 0 1 0 1 1 X X 1 X 0 1 1 1 Q1 D0 Q0 N D 0 0 1 0 0 0 1 0 X X 1 X 0 0 1 0 Q1 Open Q0 N D Remember location of don’t cares!

147.VII - Finite State Machines © Copyright 2004, Gaetano Borriello and Randy H. Katz present state inputs next state output Q3 Q2 Q1 Q0 D N D3 D2 D1 D0 open 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 - - - - - 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 - - - - - 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 - - - - - 1 0 0 0 - - 1 0 0 0 1 D0 = Q0 D ’ N ’ D1 = Q0 N + Q1 D ’ N ’ D2 = Q0 D + Q1 N + Q2 D ’ N ’ D3 = Q1 D + Q2 D + Q2 N + Q3 OPEN = Q3 Example: vending machine – One Hot Encoding One-hot encoding

148.Use Method 3 to calculate transition functions Various procedures for Moore sequential circuits State Graph of FSM Algorithmic State Machine Natural Language Specification of FSM Verilog Code State Table of FSM Logic Equations Red is most important Use Method 2 to calculate transition functions, calculate output functions Use Method 1 to calculate transition functions, calculate output functions Use other Methods to calculate transition functions, calculate output functions

149.Short Presentation of Mealy Machines

150.Comparison of Mealy and Moore state diagrams Moore machine outputs associated with state 0 ¢ [0] 10 ¢ [0] 5 ¢ [0] 15 ¢ [1] N ’ D ’ + Reset D D N N+D N N ’ D ’ Reset ’ N ’ D ’ N ’ D ’ Reset 0 ¢ 10 ¢ 5 ¢ 15 ¢ (N ’ D ’ + Reset)/0 D/0 D/1 N/0 N+D/1 N/0 N ’ D ’ /0 Reset ’ /1 N ’ D ’ /0 N ’ D ’ /0 Reset/0 Mealy machine outputs associated with transitions

151.VII - Finite State Machines © Copyright 2004, Gaetano Borriello and Randy H. Katz Example 10: Mealy implementation 0 ¢ 10 ¢ 5 ¢ 15 ¢ Reset/0 D/0 D/1 N/0 N+D/1 N/0 N ’ D ’ /0 Reset ’ /1 N ’ D ’ /0 N ’ D ’ /0 Reset/0 present state inputs next state output Q1 Q0 D N D1 D0 open 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 – – – 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 – – – 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 – – – 1 1 – – 1 1 1 D0 = Q0 ’ N + Q0N ’ + Q1N + Q1D D1 = Q1 + D + Q0N OPEN = Q1Q0 + Q1N + Q1D + Q0D 0 0 1 0 0 0 1 1 X X 1 X 0 1 1 1 Q1 Open Q0 N D

152.© Copyright 2004, Gaetano Borriello and Randy H. Katz Example 10: Mealy implementation ( cont ) D0 = Q0 ’ N + Q0N ’ + Q1N + Q1D D1 = Q1 + D + Q0N OPEN = Q1Q0 + Q1N + Q1D + Q0D make sure OPEN is 0 when reset – by adding AND gate When Reset is 1 then Reset’ is zero Then Open is zero

153.Types of FSMs Only Moore Machines will be discussed in detail in this class and will appear on exams state feedback inputs outputs reg combinational logic for next state logic for outputs inputs outputs state feedback reg combinational logic for next state logic for outputs inputs outputs state feedback reg combinational logic for next state logic for outputs Moore Mealy Synchronous Mealy Mealy not on exams ! ENJOY!

154.Example 11: Synchronous Mealy

155.Retiming D D Q Q D D Q Q D1 D2 D1 D2 D Q We are shifting AND gate back through flip-flops and adding one delay after it, to preserve timing of this gate. One FF Delay + one AND delay One FF Delay + one AND delay

156.Using Retiming to realize Synchronous Mealy

157.Using Retiming to realize Synchronous Mealy

158.Using Retiming to realize Synchronous Mealy

159.Questions and EXAM Problems (1) Explain in your own words how the SR latch from two NOR gates works. Explain in full detail timing of SR latch. Create a latch from two NAND gates, similar to one from two NOR gates and explain in detail its timing. Draw the table of this latch from NAND gates. What are critical races? Give example of a circuit. What are non-critical races? Give example of a circuit. What are metastable states? You must be able to derive a state machine table from the circuit of a latch. You must be able to derive a state machine table from a state machine graph. You must be able to derive a state machine table from a flowchart or Algorithmic State Machine. Explain how a simple generator works. Explain behavior of gated SR latch using NOR gates. Explain behavior of gated SR latch using NAND gates . Explain behavior of gated D latch using NOR gates. Explain behavior of gated D latch using NAND gates.

160.Questions and Problems 16. Explain in your own words how the Edge Triggered D Flip-Flop works. 17. Build a T flip-flop from D flip-flop and logic gates. 18. Build a JK flip-flop from D flip-flop and logic gates. 19. Build a T flip-flop from JK flip-flop. 20. Build a JK flip-flop from T flip-flop and logic gates . 21. Build a modulo 4 counter from D flip-flops and logic. 22. Build a modulo 4 counter from T flip-flops and logic . 23. Build a modulo 4 counter from JK flip-flops and logic . 24. Design a modulo 5 counter and draw its timing diagram. 25. How to design a modulo 32 counter? 26. How to design a modulo 33 counter? 27. Explain in your own words the difference of Mealy and Moore Machines. 28. What is the synchronous Mealy Machine and how it differs from standard Mealy Machine? 29. What is retiming? Questions and EXAM Problems (2)

161.Questions and Problems 29. Given is a circuit composed from D flip-flops and few logic gates. Create a state graph of this circuit. 30 . Given is a circuit composed from D flip-flops and few logic gates. Create a state table of this circuit. 31. TYPICAL PROBLEM FOR EXAM, DEFINITELY WILL BE COVERED: Given is an English Language formulation of some state machine. Create a state graph of this machine. Create a state table of this machine. (Moore). Create and minimize output logic functions of this machine. Create and minimize transition (excitation) functions of this machine. Draw the schematic of the machine with flip-flops and logic gates. Verify that your schematic really realizes the machine that its specification was given to you. Most Important EXAM Problems VERILOG NOT ON EXAM

162.Sources Prof. Mark G. Faust John Wakerly Gaetano Borriello Randy H. Katz