7. FSM(유한 상태 기계)

FSM(Finite State Machine)

 

state, transition, clock 요소 고려하기....

 

FSM 구조 구하는 법

1. state diagram 구하기

2. state transition table(=truth table) 찾기

3. state encoding

: state에 binary code를 부여하는 과정이다.

4. karnaugh map을 통해 minimize eqation 찾기

5. 회로 구성하기.

: d flip-flop을 사용한다.

 

 

state가 6개일 경우 3bit를 사용해서 binary code를 부여할 것이다. 

이때 3bit binary code는 총 8개인데, 그러면 남은 2개는 어떻게 해줄 것인가?

우리는 모든 code를 사용해야 하기 때문에 이 2개에 대해서는 사용되지 않은(=남은) next state의 binary code를 부여하거나, don't care state로 생각한다.

 

 

그러면 또 문제가 발생한다.

회로가 시작할 때 어떤 binary code에서 시작할지 알 수 없는데, 만약 don't care state에서 시작한다면?

이 경우 제대로된 state로 진입할 수 없을 것이다.

이러한 문제를 해결하기 위해  self-starting 방법을 사용한다.

 

self-starting

 

self-starting 설명 예시

 

 

이 그림에서 001, 100, 111 state code는 사용되지 않는 don't care state 상태이다. 

그렇기 때문에 만약 저 셋중 하나의 상태에서 시작한다면 우리가 원하는 state로 진입할 수 없을 것이다.

그래서 self-starting 방법을 사용하여 저 3개의 state를 우리가 사용하는 state와 연결시켜 주는 것이다.

그렇게 되면 어떤 state에서 시작하더라도 결국 우리가 원하는 state로 진입할 수 있게 된다.

 

---

State machine

state machine에는 2가지 종류가 있다.

 

1. Moore machine(무어 머신)

이 경우 output이 현재 state에만 의존한다.

무어 머신은 밀리 머신보다 사용하기에 더 안전하다.

왜냐하면 output이 clock edge에만 바뀌기 때문이다. 즉, input이 입력된 후 한 사이클 뒤에 값이 변화한다.

밀리 머신에서는 input이 output에 영향을 바로 미치기 때문에 2개 이상의 기계에서 비동기화 문제가 발생할 수 있다.

 

무어 머신 예시

 

이 그림에서 보면, 무어 머신은 output이 현재 상태에 의존하기 때문에, A->B로 변할 때 A state에서 output은 0이므로 output이 0이다. B->D로 변하는 경우 B state에서 output은 1이므로 output은 1이다.

 

 

 

2. Mealy machine(밀리 머신)

이 경우 output이 현재 state와 input에 의존한다.

밀리 머신은 무어 머신보다 더 빠르게 반응한다.

즉, clock을 한 사이클 기다리지 않고, 같은 사이클에서 input을 바로 output에 반영한다.

 

밀리 머신 예시

 

이 그림에서 보면, 밀리 머신은 output이 현재 상태와 input 의존하기 때문에, A->C로 변할 때 input 1에 대한 output은 0이므로 output이 0이다. B->C로 변하는 경우 input 1에 대한 output이 1이므로 output은 1이다.

밀리 머신이 무어 머신보다 더 적은 개수의 state를 갖는다.

 

 

 

 

무어 머신과 밀리 머신의 장점을 합친 것이 synchronous Mealy machine이다.

flip-flop을 사용하여 clock에 맞춰 state를 동기화한다.

즉, 밀리 머신 처럼 output을 빠르게 계산하면서 flip-flop을 이용해 next state와 동기화 함으로써, 밀리 머신에서 발생할 수 있는 glitchy에 대한 문제를 피할 수 있다.

마찬가지로 synchronous Moore machine도 만들 수 있다.

current state로 부터 output 계산을 하는데 발생하는 delay을 없애기 위해 current state 값을 flip-flop에 넣기 전 output 계산을 하고, output, current state 계산 값들을 flip- flop에 넣어 동기화 할 수 있다.

 

---

 

FSM 구조 구하기

그럼 자판기 예시를 한번 보자.

 

15cent가 들어오면 음료수를 먹을 수 있는 자판기가 있다.

자판기가 인식할 수 있는 동전은 dime(=10cent), nickel(=5cent) 뿐이다. 편의상 거스름돈은 없다...!!

 

 

1. state diagram 그리기

state diagram

 

그럼 state diagram을 다음과 같이 무어/밀리 모델로 나타낼 수 있다.

어느쪽이 무어/밀리 모델인지는 한번 맞춰 보기....

 

 

 

 

 

는 개뿔 오른쪽이 밀리 머신 모델이다.

차이점을 알겠는가? 밀리 머신 모델에서는 next machine으로 transition 될 때 input에 의해 output이 결정된다.

5cent -> 15cent로 갈 때 바로 output 1이 출력되는 것이다.

반면에 무어 머신 모델에서는 현재 state에 의해 output이 결정된다.

그렇기 때문에 5cent -> 15cent로 갈 때 5cent라는 현재 state에 의해 output이 결정되므로 output 0이 출력된다.

 

 

 

2. state transition table 구하기 + 3. state encoding하기

 

밀리 머신 모델에 대한 state transition table

 

 

4. karnaugh map으로 minimize equation 구하기

 

밀리 모델 사용

 

 

5. 회로 구성하기

 

밀리 모델 사용

 

이 회로에서 하단 output 부분에 flip-flop을 추가하여 output을 동기화 시켜준다면, 그것이 바로 synchronous mealy machine이다.

 

sybchronous mealy machine