[Digital Logic] Finite State Machine (FSM)

이제 강의를 듣는 부분은 Finite State Machine이다. 말그대로 State가 유한개 존재하면서 특정상황에 어떤 입력이 들어오느냐에 따라 state와 output을 변화시키는 시스템이다. 사실 일전에 Tiva C Launchpad에 구현도 한번 한 내용이다. 한번 궁금한 사람은 밑의 링크를 참조해보길...

2014/03/30 - [About MOOC] - TrafficLight Simulation

아무튼 Finite State Machine을 설계하는데 원칙이 몇가지가 있다. 물론 내가 생각한게 아니라 강의 내용을 번역에서 갖고 오자면.

1) 현재 당면 문제를 상기하고, 주어진 것 중 입력과 출력이 뭔지를 구별해야 한다.

2) 문제를 상기하고 어떤 state가 필요한지를 고려하고 그에 따른 state diagram을 그려야 한다. 예를 들면 이렇게 해야 된다.

3) 그 후에 Finite State Machine이 어떤 형태로 구현이 되느냐를 고려해야 한다. FSM의 특성상 이전 State의 output의 current input에 영향을 끼치기 때문에 기억소자를 써야 하는데 보통 많이 쓰는게 D- FlipFlop이 된다. 그래서 현재 state가 몇개 필요한지를 따진 후 log2(#)를 구하면 그게 곧 FSM에 필요한 FlipFlop의 수가 된다. 그 값이 소수가 되면 그냥 ceiling해주면 된다. 예를 들어서 위의 예시는 state가 현재 3개 필요하다. 그러면 저걸 Binary로 표현하게 되면 00, 01, 10 이렇게 필요하기 때문에 필요한 flipflop의 수는 2개가 된다. bit수 2개로 state가 표현되기 때문이다.

4) 이제 필요요소를 나눴으니까 설계하면 된다. 

5) 그리고 마지막으로 중요한 것은 실제로 output transition table을 그려보면서 simulation을 해봐야 된다는 것이다. 참고로 이번 과제가 그걸 설계하는 과정이 포함되어 있어서 잠깐 소개해보려고 한다.

 

이렇게 과제가 주어져 있다. 그러면 우리한테 필요한 State는 4개가 되겠고,여기에 필요한 flipflop의 수는 log2(4) 이므로 2개가 된다. 그리고 output을 1로 만드는 조건, S1'을 1로 만드는 조건, S0'을 1로 만드는 조건을 나눠서 설계를 하면 된다. 아마 이 과정은 굳이 FSM이 아니더라도 다른 설계 과정에 많이 포함되어 있는 내용이므로 직접해보면 좋을거 같다. 내가 설계한 것은 다음과 같다.

그리고 여기에 따른 simulation 결과도 다음과 같다.

사실 컴퓨터의 내부구조도 살펴보면 수많은 state로 구성되어 있다. 그렇기 때문에 이런 FSM과 같은 기본 소자를 직접 구현해보면서 컴퓨터가 어떻게 동작하는지를 파악하는 것도 컴퓨터를 공부하는 사람 입장에서 중요하다고 생각한다. 그래서 쭉 공부하고 있는거고 그 내용을 여기에 담고 있는 것이다.