1 08 Simple Sequential Logic Design with Finite State Machines & Timing Design.

Presentation on theme: "1 08 Simple Sequential Logic Design with Finite State Machines & Timing Design."— Presentation transcript:

1 1 08 Simple Sequential Logic Design with Finite State Machines & Timing Design

2 2 Recap – D FF with asynchronous inputs The below is a D flip-flop with active-low asynchronous inputs. Direct inputs to set or reset the flip-flop S’R’ = 11 for “normal” operation of the D flip-flop

3 3 JK-FF & T-FF JK=11 are used to complement the flip-flop ’ s current state. A T flip-flop can only maintain or complement its current state.

4 4 Contents Finite state machine  Mealy Machine  Moore Machine FSM in VHDL Techniques for simple Sequential logic design

5 5 Required reading S. Brown and Z. Vranesic, Fundamentals of Digital Logic with VHDL Design Chapter 8, Synchronous Sequential Circuits Sections 8.1-8.5 M. Morris Mano, Digital Design 3 rd Edition, Chapter 5, Synchronous Sequential Logic

6 6 Finite State Machines (FSMs) Any Circuit with Memory can be represented with a Finite State Machine  Even computers can be viewed as huge FSMs Design of FSMs (State Machines in short) Involves  Defining states  Defining transitions between states  Optimization / minimization Manual Optimization/Minimization Is Practical for Small FSMs Only

7 7 Moore FSM Output Is a Function of a Present State Only Present State register Next State function Output function Inputs Present State Next State Outputs clock reset

8 8 Mealy FSM Output Is a Function of a Present State and Inputs Next State function Output function Inputs Present State Next State Outputs Present State register clock reset

9 9 Moore Machine state 1 / output 1 state 2 / output 2 transition condition 1 transition condition 2

10 10 Mealy Machine state 1 state 2 transition condition 1 / output 1 transition condition 2 / output 2

11 11 Moore vs. Mealy FSM (1) 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

12 12 Moore vs. Mealy FSM (2) 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 more likely to have a shorter critical path

13 13 Moore FSM - Example 1 Moore FSM that Recognizes Sequence “ 10 ” S0 / 0S1 / 0S2 / 1 0 0 0 1 1 1 reset Meaning of states: S0: No elements of the sequence observed S1: “1” observed S2: “10” observed

14 14 Mealy FSM - Example 1 Mealy FSM that Recognizes Sequence “ 10 ” S0S1 0 / 0 1 / 0 0 / 1 reset Meaning of states: S0: No elements of the sequence observed S1: “1” observed

15 15 Moore & Mealy FSMs – Example 1 clock input Moore Mealy 0 1 0 0 0 S0 S1 S2 S0 S0 S0 S1 S0 S0 S0

16 16 Contents Finite state machine  Mealy Machine  Moore Machine FSM in VHDL Techniques for simple Sequential logic design

17 17 FSMs in VHDL Finite State Machines Can Be Easily Described With Processes Synthesis Tools Understand FSM Description If Certain Rules Are Followed State transitions should be described in a process sensitive to clock and asynchronous reset signals only Outputs described as concurrent statements outside the process

18 18 Moore FSM Present State Register Next State function Output function Inputs Present State Next State Outputs clock reset process(clock, reset) concurrent statements

19 19 Mealy FSM Next State function Output function Inputs Present State Next State Outputs Present State Register clock reset process(clock, reset) concurrent statements

20 20 Moore FSM - Example 1 Moore FSM that Recognizes Sequence “ 10 ” S0 / 0S1 / 0S2 / 1 0 0 0 1 1 1 reset

21 21 Moore FSM in VHDL (1) TYPE state IS (S0, S1, S2); SIGNAL Moore_state: state; U_Moore: PROCESS (clock, reset) BEGIN IF(reset = ‘1’) THEN Moore_state <= S0; ELSIF (clock = ‘1’ AND clock’event) THEN CASE Moore_state IS WHEN S0 => IF input = ‘1’ THEN Moore_state <= S1; ELSE Moore_state <= S0; END IF;

22 22 Moore FSM in VHDL (2) WHEN S1 => IF input = ‘0’ THEN Moore_state <= S2; ELSE Moore_state <= S1; END IF; WHEN S2 => IF input = ‘0’ THEN Moore_state <= S0; ELSE Moore_state <= S1; END IF; END CASE; END IF; END PROCESS; Output <= ‘1’ WHEN Moore_state = S2 ELSE ‘0’;

23 23 Mealy FSM - Example 1 Mealy FSM that Recognizes Sequence “ 10 ” S0S1 0 / 0 1 / 0 0 / 1 reset

24 24 Mealy FSM in VHDL (1) TYPE state IS (S0, S1); SIGNAL Mealy_state: state; U_Mealy: PROCESS(clock, reset) BEGIN IF(reset = ‘1’) THEN Mealy_state <= S0; ELSIF (clock = ‘1’ AND clock’event) THEN CASE Mealy_state IS WHEN S0 => IF input = ‘1’ THEN Mealy_state <= S1; ELSE Mealy_state <= S0; END IF;

25 25 Mealy FSM in VHDL (2) WHEN S1 => IF input = ‘0’ THEN Mealy_state <= S0; ELSE Mealy_state <= S1; END IF; END CASE; END IF; END PROCESS; Output <= ‘1’ WHEN (Mealy_state = S1 AND input = ‘0’) ELSE ‘0’;

26 26 Moore FSM – Example 2: State diagram Cz1=  resetn Bz0=  Az0=  w0= w1= w1= w0= w0= w1=

27 27 Present Next state Output state w=0w=1 z AAB0 BAC0 CAC1 Moore FSM – Example 2: State table

28 28 Moore FSM Present State Register Next State function Output function Input: w Present State: y Next State Output: z clock resetn process(clock, reset) concurrent statements

29 29 USE ieee.std_logic_1164.all ; ENTITY simple IS PORT (clock : IN STD_LOGIC ; resetn : IN STD_LOGIC ; w : IN STD_LOGIC ; z : OUT STD_LOGIC ) ; END simple ; ARCHITECTURE Behavior OF simple IS TYPE State_type IS (A, B, C) ; SIGNAL y : State_type ; BEGIN PROCESS ( resetn, clock ) BEGIN IF resetn = '0' THEN y <= A ; ELSIF (Clock'EVENT AND Clock = '1') THEN Moore FSM – Example 2: VHDL code (1)

30 30 CASE y IS WHEN A => IF w = '0' THEN y <= A ; ELSE y <= B ; END IF ; WHEN B => IF w = '0' THEN y <= A ; ELSE y <= C ; END IF ; WHEN C => IF w = '0' THEN y <= A ; ELSE y <= C ; END IF ; END CASE ; Moore FSM – Example 2: VHDL code (2)

31 31 Moore FSM – Example 2: VHDL code (3) END IF ; END PROCESS ; z <= '1' WHEN y = C ELSE '0' ; END Behavior ;

32 32 Moore FSM Present State Register Next State function Output function Input: w Present State: y_present Next State: y_next Output: z clock resetn process (w, y_present) concurrent statements process (clock, resetn)

33 33 ARCHITECTURE Behavior OF simple IS TYPE State_type IS (A, B, C) ; SIGNAL y_present, y_next : State_type ; BEGIN PROCESS ( w, y_present ) BEGIN CASE y_present IS WHEN A => IF w = '0' THEN y_next <= A ; ELSE y_next <= B ; END IF ; WHEN B => IF w = '0' THEN y_next <= A ; ELSE y_next <= C ; END IF ; Alternative VHDL code (1)

34 34 WHEN C => IF w = '0' THEN y_next <= A ; ELSE y_next <= C ; END IF ; END CASE ; END PROCESS ; PROCESS (clock, resetn) BEGIN IF resetn = '0' THEN y_present <= A ; ELSIF (clock'EVENT AND clock = '1') THEN y_present <= y_next ; END IF ; END PROCESS ; z <= '1' WHEN y_present = C ELSE '0' ; END Behavior ; Alternative VHDL code (2)

35 35 A w0=z0= / w1=z1= / B w0=z0= / resetn w1=z0= / Mealy FSM – Example 2: State diagram

36 36 Present Next stateOutput z state w=0w=1w=0w=1 AAB00 BAB01 Mealy FSM – Example 2: State table

37 37 Mealy FSM Next State function Output function Input: w Present State: y Next State Output: z Present State Register clock resetn process(clock, reset) concurrent statements

38 38 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY Mealy IS PORT ( clock : IN STD_LOGIC ; resetn : IN STD_LOGIC ; w : IN STD_LOGIC ; z : OUT STD_LOGIC ) ; END Mealy ; ARCHITECTURE Behavior OF Mealy IS TYPE State_type IS (A, B) ; SIGNAL y : State_type ; BEGIN PROCESS ( resetn, clock ) BEGIN IF resetn = '0' THEN y <= A ; ELSIF (clock'EVENT AND clock = '1') THEN Mealy FSM – Example 2: VHDL code (1)

39 39 Mealy FSM – Example 2: VHDL code (2) CASE y IS WHEN A => IF w = '0' THEN y <= A ; ELSE y <= B ; END IF ; WHEN B => IF w = '0' THEN y <= A ; ELSE y <= B ; END IF ; END CASE ;

40 40 Mealy FSM – Example 2: VHDL code (3) END IF ; END PROCESS ; WITH y SELECT z <= w WHEN B, z <= ‘0’ WHEN others; END Behavior ;

41 41 Contents Finite state machine  Mealy Machine  Moore Machine FSM in VHDL Techniques for simple Sequential logic design (Timing Design)

42 42 Timing Design - 강의순서 State Machine 응용 Shift Register 응용 Counter 응용 주어진 타이밍도로부터 회로를 설계하는 방 법을 다양한 형태의 접근 방법을 통해 습득한 다. 각종 디바이스의 데이터 북 상에 나타나 는 타이밍 도의 이해를 위한 더욱 심화된 지 식을 배양한다.

43 43 Timing Design – State Machine Application 1. 아래와 같은 Timing 입출력 파형을 갖는 회로를 설계해보자 해석 : WindowAct 신호가 0 에서 1 로 변하는 순 간부터 다음 clock 의 rising edge 까지 RiseShot 을 1 로 만들고 WindowAct 신호가 1 에서 0 으로 변하는 순간부 터 다음 clock 의 rising edge 까지 FallShot 을 1 로 만들어야 함. 해석 : WindowAct 신호가 0 에서 1 로 변하는 순 간부터 다음 clock 의 rising edge 까지 RiseShot 을 1 로 만들고 WindowAct 신호가 1 에서 0 으로 변하는 순간부 터 다음 clock 의 rising edge 까지 FallShot 을 1 로 만들어야 함.

44 44 Timing Design – State Machine Application S0 S1 0/00 1/00 0/01 1/10 2. Exercise: Mealy-machine state diagram 을 완성하고 VHDL 로 coding 해보라. WindowAct / RiseShot, FallShot 입력 / 출력 1, 출력 2

45 45 Timing Design – State Machine Application S0 S1 0/00 1/00 0/01 1/10 상태도에서 입력에 따른 상태의 변화만 을 기술

46 46 Timing Design – State Machine Application S0 S1 0/00 1/00 0/01 1/10 상태도에서 입력에 따른 출력의 변화만을 기술 Note: The outputs react to input asynchronously.

47 47 Timing Design – State Machine Application Result

48 48 Timing Design 3. 상태도를 이용하지 않는 다른 방법은 ?  Timing 만을 고려한 설계 Q 는 WindowAct 를 D F/F 으로 통 과시킨 출력 13 2 4 1,3 에서 RiseShot= WindowAct and Q’ 1,3 에서 RiseShot= WindowAct and Q’ 2,4 에서 FallShot= WindowAct’ and Q 2,4 에서 FallShot= WindowAct’ and Q

49 49 Timing Design 3. Timing 만을 고려한 설계방식 - BDF Q 는 WindowAct 를 D FF 으로 통과시 킨 출력 not Q WindowAct and Q’ WindowAct’ and Q not WindowAct

50 50 Timing Design library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; entity RiseFallShot_time is port( WindowAct : in std_logic; clk,nclr : in std_logic; RiseShot,FallShot: out std_logic ); end RiseFallShot_time; architecture a of RiseFallShot_time is signal q : std_logic; signal RisingShotPules : std_logic; begin -- shift register 1bits process(nclr,clk) begin if( nclr='0') then q <='0'; elsif(clk'event and clk='1') then q <= WindowAct; end if; end process; -- rising shot pulse gen. RiseShot <= WindowAct and not q; FallShot <= not WindowAct and q; end a; 같은 회로 3. Timing 만을 고려한 설계방식 - VHDL

51 51 Timing Design ▣아래와 같은 Timing 입출력 파형을 갖는 회로를 설계해보자. 입력신호 : reset, clk, WindowAct 출력신호 : y0, y1, y2, y3, y4, y5, y6

52 52 Timing Design 1. 먼저 아래의 회로를 만들어보자. 입력신호 : reset, clk, WindowAct 출력신호 : y0 어떤 방식으로 설계해야 하는가 ?  1 차적으로 생각할 수 있는 방법은 Shift Register 를 이용하는 방법

53 53 Timing Design – Shift Register Application 그림과 같은 Shift Register 를 사용하 게 되면 Q0, Q1, Q2 의 타이밍을 예 상할 수 있다. 출력신호 y0 는 Q1 가 1 이 되는 부 분과 Q2 가 0 이 되 는 700-900ns 부 분에서 1 이 된다. Y0=Q1 and Q2’ 출력신호 y0 는 Q1 가 1 이 되는 부 분과 Q2 가 0 이 되 는 700-900ns 부 분에서 1 이 된다. Y0=Q1 and Q2’ Y0 = Q1 and not Q2

54 54 Timing Design – Shift Register Application 2. 이번에는 y1 을 만들어보자.

55 55 Timing Design – Shift Register Application Y0 를 clk 의 falling edge 를 이용하여 shift 하면 반클럭 shift 된 Y1 을 만들 수 있다.

56 56 Timing Design – Shift Register Application 3. 이번에는 y2 를 만들어보자.

57 57 Timing Design – Shift Register Application Y2 는 Y0 와 Y1 을 OR 한 것임을 알 수 있다. Y2 = Y0 or Y1 Y2 는 Y0 와 Y1 을 OR 한 것임을 알 수 있다. Y2 = Y0 or Y1

58 58 Timing Design – Shift Register Application 4. 이번에는 y3 을 만들어보자.

59 59 Timing Design – Shift Register Application Y3 는 11 개의 shift register 중에서 Q9 가 1 이면 Q10 이 0 인 구간에 1 이 출력되는 신호. 11 bits Shift Registe r 회로는 다음 쪽 참조

60 60 Timing Design – Shift Register Application Y3 는 11 개의 shift register 중에서 Q10 과 Q9 를 이용한 신호임. Y3 = Q9 and Q10’ Y3 는 11 개의 shift register 중에서 Q10 과 Q9 를 이용한 신호임. Y3 = Q9 and Q10’

61 61 Timing Design – Shift Register Application 5. 이번에는 y4 을 만들어보자.

62 62 Timing Design – Shift Register Application Y4 는 Y1 와 Y3 을 OR 한 것임 을 알 수 있다. Y4 = Y1 or Y3 Y4 는 Y1 와 Y3 을 OR 한 것임 을 알 수 있다. Y4 = Y1 or Y3

63 63 Timing Design – Shift Register Application 6. 이번에는 y5 을 만들어보자.

64 64 Timing Design – Shift Register Application Y5 는 Q2 가 1 이 며 Q10 이 0 인 구간에 1 을 출력.

65 65 Timing Design – Shift Register Application 7. 이번에는 y6 을 만들어보자.

66 66 Timing Design – Shift Register Application Y6p 는 Q1 이 1 이며 Q9 가 0 인 구간에 1 을 출력. Y6 는 Y6p 를 Clk 의 Falling Edge 를 이용 하여 반 클럭 밀어준 신호임.

67 67 Timing Design – Shift Register Application library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; entity shift_app2 is port( clk,nclr,WindowAct : in std_logic; y : buffer std_logic_vector(0 to 6)); end shift_app2; architecture a of shift_app2 is signal q : std_logic_vector(0 to 10); signal y6p : std_logic; begin ShiftRegster : process(nclr,clk) begin if( nclr='0') then q<="00000000000"; elsif(clk'event and clk='1') then q(0)<= WindowAct; for i in 0 to 9 loop q(i+1) <= q(i); end loop; end if; end process; y(0) <= q(1) and not q(2); 동일회로동일회로 동일회로동일회로 동일회로동일회로 동일회로동일회로

68 68 Timing Design – Shift Register Application process(nclr,clk) begin if( nclr='0') then y(1)<='0'; elsif(clk'event and clk='0') then y(1)<=y(0); end if; end process; y(2) <= y(0) or y(1); y(3) <= q(9) and not q(10); y(4) <= y(1) or y(3); y(5) <= q(2) and not q(10); y6p <= q(1) and not q(9); process(nclr,clk) begin if( nclr='0') then y(6)<='0'; elsif(clk'event and clk='0') then y(6)<=y6p; end if; end process; end a; 동일회로동일회로 동일회로동일회로 동일회로동일회로 동일회로동일회로 동일회로동일회로 동일회로동일회로

69 69 Result

70 70 Result

71 71 Resource Usage

72 72 Timing Design – Counter Application ▣아래와 같은 Timing 입출력 파형을 갖는 회로를 Shift Register 가 아 닌 다른 방식 (Counter 응용 ) 으로 설계해보자. 입력신호 : reset, clk, WindowAct 출력신호 : y0, y1, y2, y3, y4, y5, y6

73 73 Timing Design – Counter Application 1. 입력신호 들로부터 cnt[3..0] 을 만들 수 있는가 ?

74 74 Timing Design – Counter Application 이 카운터는 WindowAct 가 1 일 때만 증가되며, WindowAct 가 0 일 때는 0 으로 된다. process(nclr,clk) begin if( nclr='0') then cnt<="0000"; elsif(clk'event and clk='1') then if(WindowAct='0') then cnt<="0000"; else cnt <= cnt+1; end if; end process; library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; entity cnt_app2 is port( clk,nclr,WindowAct : in std_logic; y : buffer std_logic_vector(0 to 6)); end cnt_app2; architecture a of cnt_app2 is signal cnt : std_logic_vector(3 downto 0); begin Cnt[3..0] 을 사용 Cnt 회로

75 75 Timing Design – Counter Application 2. 입력신호 들과 cnt[3..0] 로 부터 Y0, Y3 을 만들 수 있는가 ?

76 76 Timing Design – Counter Application process(cnt) begin if( cnt=2) then y(0)<='1'; else y(0)<='0'; end if; end process; process(cnt) begin if( cnt=10) then y(3)<='1'; else y(3)<='0'; end if; end process; Y0 발생부 Y3 발생부

77 77 Timing Design – Counter Application 3. Y1,Y2,Y4 의 발생은 ?

78 78 Timing Design – Counter Application process(nclr,clk) begin if( nclr='0') then y(1)<='0'; elsif(clk'event and clk='0') then y(1)<=y(0); end if; end process; y(2) <= y(0) or y(1); y(4) <= y(1) or y(3); Y2,Y 4 발 생부 Y2 는 Y0 와 Y1 을 OR 한 것임을 알 수 있다. Y2 = Y0 or Y1 Y2 는 Y0 와 Y1 을 OR 한 것임을 알 수 있다. Y2 = Y0 or Y1 Y0 를 clk 의 falling edge 를 이용하여 시프 트하면 반클럭 시프트된 Y1 을 만들 수 있다. Y4 는 Y1 와 Y3 을 OR 한 것임을 알 수 있다. Y2 = Y0 or Y1 Y4 는 Y1 와 Y3 을 OR 한 것임을 알 수 있다. Y2 = Y0 or Y1

79 79 Timing Design – Counter Application 4. Y5,Y6 의 발생은 ?

80 80 Timing Design – Counter Application process(nclr,clk) begin if( nclr='0') then y(5)<='0'; elsif(clk'event and clk='1') then if(cnt=2) then y(5)<='1'; elsif(cnt=10) then y(5)<='0'; else y(5)<=y(5); end if; end process; Y5 발생부 : Cnt=2 일 때 1 로 변하고 Cnt=0 일 때 0 으로 변한다. Clk 의 rising Edge 기 준 Y6 발생부 : Cnt=2 일 때 1 로 변하고 Cnt=0 일 때 0 으로 변한다. Clk 의 Falling Edge 기준 process(nclr,clk) begin if( nclr='0') then y(6)<='0'; elsif(clk'event and clk='0') then if(cnt=2) then y(6)<='1'; elsif(cnt=10) then y(6)<='0'; else y(6)<=y(6); end if; end process; end a;

81 81 Result

82 82 Result

83 83 Result