ASIC Design Laboratory Finite State Machines State Diagrams vs. Algorithmic State Machine (ASM) Charts

ASIC Design Laboratory Finite State Machines State Diagrams vs. Algorithmic State Machine (ASM) Charts

1. ASIC Design Laboratory Finite State Machines State Diagrams vs. Algorithmic State Machine (ASM) Charts 1

2. Structure of a Typical Digital System 2 Datapath (Execution Unit) Controller (Control Unit) Data Outputs Control & Status Outputs Data Inputs Control & Status Inputs Control Signals Status Signals

3. Datapath (Execution Unit) 3 Manipulates and processes data Performs arithmetic and logic operations, shifting/rotating, and other data- processing tasks Is composed of registers, multiplexers, adders, decoders, comparators, ALUs, gates, etc. Provides all necessary resources and interconnects among them to perform specified task Interprets control signals from the Controller and generates status signals for the Controller

4. Controller (Control Unit) 4 Controls data movement in the Datapath by switching multiplexers and enabling or disabling resources enable select Example: signals for registers Example: signals for muxes Provides signals to activate various processing tasks in the Datapath Determines the sequence of operations performed by the Datapath Follows Some ‘ program’ or Schedule

5. Finite State Machines 5 Controllers can be described as Finite State Machines (FSMs) FSM can be represented using State Diagrams and State Tables - suitable for simple controllers with a relatively few inputs and outputs Algorithmic State Machine (ASM) Charts - suitable for complex controllers with a large number of inputs and outputs All of these descriptions can be easily translated to the corresponding synthesizable HDL code

6. Finite State Machines 6 Controllers can be described as Finite State Machines (FSMs) FSM can be represented using: All of these descriptions can be easily translated to the corresponding synthesizable HDL code State Diagrams and State Tables Algorithmic State Machine ( ASM ) Charts suitable for simple controllers suitable for complex controllers with a relatively few inputs and outputs with a large number of inputs and outputs

7. Hardware Design with RTL HDL 7 Text Description or Pseudocode Datapath Controller Block diagram ASM chart code code Interface

8. Finite State Machines FSM 8

9. Finite State Machines (FSMs) 9 An FSM is used to model a system that transits among a finite number of internal states . The transitions depend on the current state and external input . The main application of an FSM is to act as the controller of a medium to large digital system Design of FSMs involves Defining states Defining the next- state and output functions Optimization / minimization Manual optimization/minimization is practical for small FSMs only

10. ASIC Circuit design FSM in Verilog 1 F 1 all 2022

11. Moore FSM 11 output is a function of the state only state register next- state logic output logic input state_next output state_reg clk reset

12. Mealy FSM 12 output is a function of the state and input signals state register next- state logic output logic input state_next output clk reset state_reg

13. State Diagrams 12

14. FSM State diagram: each circle represents state identifier. each line represents transaction between states. inner circles represents looping.

15. Finite State Machine basic Elements Current State Next State Transition Action Condition

16. Moore Machine 16 state 1 / output 1 state 2 / output 2 transition condition 1 transition condition 2

17. Mealy Machine 17 state 1 state 2 transition condition 1 / output 1 transition condition 2 / output 2

18. Moore FSM - Example 1 18 Moore FSM that Recognizes Sequence “10” (Non- Overlapping) S0 / S1 / S2 / 1 1 1 1 reset Meaning of states: S0: No elements of the sequence observed S1: '1' observed S2: '10' observed

19. Mealy FSM - Example 1 19 Mealy FSM that Recognizes Sequence "10" (Non- Overlapping) S0 S1 0 / 1 / 1 / 0 / 1 reset Meaning of states: S0: No elements of the sequence observed S1: '1' observed

20. Finite State Machine (Moore FSM) EX: FSM that can detect the 110 sequences State Diagram (Non- Overlapping)

21. Finite State Machine (Moore FSM) EX: FSM that can detect the 110 sequence Verilog code module FSMM(clk,clr_,in,out1); input clk,clr_,in; output reg out1; reg [1:0] state,next_state; localparam s0=2'b00, s1=2'b01, s2=2'b10, s3=2'b11; always @ (state,in) case (state) s0: if (in) next_state=s1; else s1: if (in) next_state=s2; else s2: if (in) next_state=s2; else s3: if (in) next_state=s1; else next_state=s0; next_state=s0; next_state=s3; next_state=s0; default: next_state=2'bXX; endcase always @(negedge clr_, posedge clk) if(!clr_ ) else state<=s0; state <=next_state; Always @(next_state) if (state==s3) out1=1; else out1=0; endmodule

22. Finite State Machine (Moore FSM) EX: FSM that can detect the 110 sequence Simulation

23. Finite State Machine (Moore FSM) EX: FSM that can detect the 100 sequences State Diagram (Non- Overlapping)

24. Finite State Machine (Moore FSM) EX: FSM that can detect the 100 sequence Verilog code module FSMM(clk,clr_,in,z); //solve it and check your answer with the instructor endmodule

25. Finite State Machine (FSM) EX: FSM that can detect the 100 sequence Simulation

26. Finite State Machine (FSM) EX: FSM that can detect the 110 and 101 sequences State Diagram (Non- Overlapping)

27. Finite State Machine (FSM) EX: FSM that can detect the 110 and 101 sequences Verilog code module FSMM(clk,clr_,in,z); //solve it and check your answer with the instructor endmodule

28. Finite State Machine (FSM) EX: FSM that can detect the 110 and 101 sequences Simulation

29. Algorithmic State Machine (ASM) Charts 29

30. Algorithmic State Machine 30 Algorithmic State Machine – representation of a Finite State Machine suitable for FSMs with a larger number of inputs and outputs compared to FSMs expressed using state diagrams and state tables.

31. ASM Chart 31 Flowchart- like diagram Provides the same info as a state diagram More descriptive, better for complex digital systems

32. ASM describing generalized FSM 32 Algorithmic state machines can model both Mealy and Moore Finite State Machines They can also model generalized machines that are of the mixed type

33. Elements used in ASM charts (1) 33 Output signals or actions (Moore type) State name Condition expression (False) 1 (True) Conditional outputs or actions (Mealy type) (a) State box (b) Decision box (c) Conditional output box

34. State Box 34 State box – represents a state. Equivalent to a node in a state diagram or a row in a state table. Contains register transfer actions or output signals Moore- type outputs are listed inside of the box. It is customary to write only the name of the signal that has to be asserted in the given state, e.g., z instead of z<=1. Also, it might be useful to write an action to be taken, e.g., count <= count + 1, and only later translate it to asserting a control signal that causes a given action to take place (e.g., enable signal of a counter). Output signals or actions (Moore type) State name

35. Decision Box 35 Decision box – indicates that a given condition is to be tested and the exit path is to be chosen accordingly. The condition expression may include one or more inputs to the FSM. Condition expression (False) 1 (True)

36. Conditional Output Box Denotes output signals that are of the Mealy type. The condition that determines whether such outputs are generated is specified in the preceding decision box. 36 Conditional output box Conditional outputs or actions (Mealy type)

37. ASM Chart The control generates the output signal Start while in state S_1 Then checks the status of input Flag . If Flag = 1, then R is cleared to 0; otherwise, R remains unchanged. In either case, the next state is S_2. A register operation is associated with S_2 “F  G” R  0: when the controller is in S_1, it must assert a Mealy ‐ type signal that will cause the register operation R  to execute in the datapath unit. It mixes descriptions of the datapath and the controller.

38. ASM Block One state box One or more (optional) decision boxes: with T (1) or F (0) exit paths One or more (optional) conditional output boxes: for Mealy outputs 26

39. Examples of ASM Block State diagram equivalent to the of ASM Block

40. ASM Chart Rules 40 Difference between a regular flowchart and an ASM chart: Transition governed by clock Transition occurs between ASM blocks Basic rules: For a given input combination, there is one unique exit path from the current ASM block Any closed loop in an ASM chart must include a state box

41. Incorrect ASM Charts 41

42. Correct ASM Chart 42

43. State Diagram of Moore FSM 43 Moore FSM that Recognizes Sequence “ 1 ” S0 / S1 / S2 / 1 1 1 1 reset Meaning of states: S0: No elements of the sequence observed S1: “ 1 ” observed S2: “ 10 ” observed

44. ASM Chart of Moore FSM 44 reset S0 S1 S2 input input 1 input 1 1 output

45. State Diagram of Mealy FSM 45 Mealy FSM that Recognizes Sequence “ 10 ” S0 S1 0 / 1 / 1 / 0 / 1 reset Meaning of states: S0: No elements of the sequence observed S1: “ 1 ” observed

46. ASM Chart of Mealy Machine 46 S1 reset S0 input input output 1 1

47. Moore vs. Mealy FSM (1) 47 Moore and Mealy FSMs Can Be Functionally Equivalent Equivalent Mealy FSM can be derived from Moore FSM and vice versa Mealy FSM Has Richer Description and Usually Requires Smaller Number of States Smaller circuit area

48. Moore vs. Mealy FSM (2) 48 Mealy FSM Computes Outputs as soon as Inputs Change Mealy FSM responds one clock cycle sooner than equivalent Moore FSM Moore FSM Has No Combinational Path Between Inputs and Outputs Moore FSM is less likely to affect the critical path of the entire circuit

49. Moore FSM 49 output is a function of the state only state register next- state logic output logic input state_next output state_reg clk reset

50. Mealy FSM 50 output is a function of the state and input signals state register next- state logic output logic input state_next output clk reset state_reg

51. Which Way to Go? 51 Safer. Less likely to affect the critical path. Moore FSM Mealy FSM Fewer states Lower Area Responds one clock cycle earlier

52. ASMs representing simple FSMs 52 Algorithmic state machines can model both Mealy and Moore Finite State Machines They can also model machines that are of the mixed type

53. Generalized FSM 53