FSM(Finite state machines)
말 그대로 상태를 가진 machine
가질 수 있는 상태(state)가 유한한 sequential logic 을 의미한다
FSM을 만들 때는
1. state transition diagram을 그리고
2. state transition table을 작성한다.
3. 그리고 표를 이용해 next state logic을 만들면 완성된다.
이때 output이 현재 상태(present state)에 의해 결정될 수도 있고
output이 state뿐만 아니라 input의 영향도 받을 수 있다.
Moore machine
present state에 의해서만 output이 결정되는 FSM을 Moore machine이라고 한다.
예를 들어 설명해보겠다.
두 사이클 이상 연속으로 input이 1인 경우 output이 1, 나머지 경우 output이 0인 FSM을 만들어보자.
1. state transition diagram
[해석]
각 원은 상태를 의미하며 3가지 상태(0, 1, 2)가 존재함을 알 수 있다.
상태 간 이동하는 화살표는 input을 의미한다.
상태의 [0], [1]은 output을 의미한다.
moore machine에서는 현재 state에 의해 output이 결정되기에 하나의 상태에 output이 고정되어있다.
state 0: 이전 사이클에 0이었던 state
state 1: 2사이클 이상 1이었던 state
state 2: 연속 1은 아니지만 바로 직전이 1이었던 state
2. state transition table
input, present state, next state, output 으로 표를 만들 수 있다.
이때 상태(state)는 3가지 경우의 수가 존재하므로 다음과 같이 바꿀 수 있다.
이진 상태 하나로 3가지 상태를 나타낼 수 없기에 P1 P0, N1 N0 각 2개씩 필요하다.
Mealy machine
present state와 더불어 input에 의해 결정되는 FSM을 Mealy machine 이라 한다.
앞의 예를 밀리 머신으로 나타내자면
1. state transition diagram
[해석]
역시 각 원은 상태를 의미하며 2가지 상태(0, 1)가 존재한다.
상태 간 이동하는 화살표는 input/output 을 의미한다.
상태에 output이 고정되어있지 않다.
state 0: 이전 사이클에 0이었던 state
state 1: 이전 사이클에 1이었던 state
2. state transition table
다음과 같이 나타낼 수 있다.
주의할 것은 모두 무어머신이나 밀리머신으로 나타낼 수 있는 것이 아니다.
예를 들어 무어머신으로 나타낼 수 없지만 밀리머신으로는 나타낼 수 있는 것이 있다.
예제1
예제2
예제3