8. FSM Optimization

7장에서 FSM 설계하는 과정 중 state encoding 과정이 있었다.

 

state 개수가 너무 많다면, state encoding 과정에서 많은 수의 bit를 state에 할당해야 할 것이다.

이 경우 equation도 길어지고, 복잡해질 것이다.

 

그래서 state minization을 통해 stae에 할당되는 bit 수를 줄일 수 있고, equation도 간단하게 만들 수 있으며 회로 구조도 간단하계 설계할 수 있는 것이다!! 이를 통해 필요한 gate, flip-flop의 수도 줄어들 것이고, 비용도 줄일 수 있다.

 

이러한 이유들 때문에 state minimization이 중요하다.

 

 

 

 

그렇다면 어떻게 state minimization을 할 수 있을까?

첫 번째로 해야 할 일은 equivalent한 state를 찾는 것이다.

equivalent state가 될 조건은 다음과 같다.

1. 같은 output을 가질 것.
2. 모든 input 조합에 대해, state transition이 같은 state가 되거나 아니면 서로의 state가 될 경우.

 

 

 

equivalent한 state를 찾을 수 있다면 이제 state minimization이 필요하다.

state minimization을 하는 방법에는 두 가지가 있다.

• Row Matching method
• implication chart method

 

 

Row Matching method

state transition table에서 equivalent states를 반복해서 찾으면서 reduced state transition table을 찾음으로써 state minimization을 시켜주는 방법이다.

하지만 이 방법에는 문제가 있다.

항상 우리가 원하는 최적의 state minimization을 할 수 없다는 것이다.

 

 

이 그림을 보면 왼쪽과 오른쪽은 같은 FSM state diagram이다.

즉, 오른쪽 state diagram에서 state minimization을 통해 왼쪽 state diagram이 될 수 있는 것이다.

state transition table을 그리고... Row Matching methode를 사용하면 왼쪽 state diagram으로 minimization할 수 있을 까?

실제로 해보면 알겠지만, Row Matching method를 사용해도 왼쪽의 state diagram을 얻을 수 없다.

 

 

 

이러한 문제를 해결하기 위해 나온 것이 Implication Chart Method이다.

 

Implication Chart Method

 

이 그림이 6개의 state가 존재하는 경우에 대한 implication chart이다.

row에는 제일 처음부터 마지막에서 1개 전의 state까지, column에는 제일 처음에서 1개 뒤의 state부터 제일 마지막의 state까지를 표기한다.

 

그리고 각 칸 안에는 equivalent state가 되기 위해 서로 같아야 하는 state를 표기한다.

 

 

예를 들어 이 그림에서 a와 b state가 같기 위해서는 d와 f state가 같아야 하고, c와 h state가 같아야 한다.

그렇다면 (a,b)에 해당하는 칸에 d-f, c-h를 표기한다.

b와 c state의 경우 output z가 다르기 때문에 애초에 equivalent state가 될 수 없다. 

그래서 (b,c)에 해당하는 칸에 x표시를 해준다.

 

해당 과정을 반복하며 reduced state transition table을 만들 수 있다. 

 

 

이렇게 implication chart method를 사용하면 오른쪽 state diagram을 왼쪽 state diagram으로 minimize할 수 있다.

 

 

---

 

 

그렇다면 minimize된 state를 통해 구현한 회로가 항상 최고의 회로일까?

정답은 '그렇지 않다' 이다.

 

 

이러한 state transtition table에 대하여 우리는

 

1번 state diagram

2번 state diagram

 

이와 같은 2가지의 state diagram을 그려볼 수 있다.

2번 state diagram이 minimize된 버전이니 회로도 더 간단하계 설계될 것처럼 생각된다.

하지만 equation을 구하고 회로를 그려보면 오히려 1번 state diagram이 더 간단하게 설계되는 것을 확인할 수 있다.

 

 

---

 

 

state에 binary code를 어떻게 할당하는 지도 회로를 간단하게 만들기 위해서 중요하다.

 

우리가 취할 수 있는 방법으로는 다음과 같은 것들이 있다.

• sequential
• random
• onehot
• output
• heuristic

이것들 중에서 어떤 방법이 가장 효과적이라고는 단정지을 수 없다.

이 글에서 나는 heuristic 방법에 대해 써보고자 한다.

 

 

Heuristics for State Assignment

이것을 위해서 먼저 state들 간의 우선순위를 파악할 필요가 있다.

그 다음 우선순위가 높은 state들 부터 먼저 인접한 binary code를 할당할 수 있다.

 

- high priority

공통된 next state를 가지는 state들을 말한다.

 

- medium priority

공통된 조상 state를 가지는 state들을 말한다.

 

- low priority

같은 input에 대해 같은 output을 가지는 state들을 말한다.

 

 

 

이 그림에서 high, medium, low priority state를 찾아보자.

- high priority state: S3', S4'

S0라는 공통된 next state를 가진다.

 

- medium priority state: S3', S4'

S1'이라는 공통된 조상 state를 가진다.

 

- low priority state: 

0/0: S1;', S0, S3'

1/0: S0, S1', S3', S4'

 

그렇기 때문에 karnaugh map에서 S3'과 S4'을 인접한 위치에 먼저 할당해주고, 나머지 state들을 채워준다.

 

 

 

---

 

 

 

Partitioning

input이 너무 많은 경우에 회로가 복잡해지는 것을 방지하기 위해서 partitioning을 통해 여러 그룹의 input에 대한 회로를 각각 구성할 수 있다.

 

 

이 그림처럼 회로를 partitioning을 통해 2개의 partition으로 나눠서 구성하는 것이다.

 

 

또 다른 예를 보면

 

 

이러한 state diagram을 가지는 FSM에 대해 생각해보자.

이것을 회로로 구현하려하면 상당히 복잡한 회로가 만들어 질 것이다.

그래서 partitioning을 사용한다.

 

 

partitioning을 통해 이 그림처럼 두 부분으로 나누고 각각에 대해 회로를 구현할 수 있는 것이다.

 

 

 

partitioning에는 몇 가지 규칙이 존재한다.

1. Source State Transformation; SA is the Idle State

SA는 transition state가 자기 자신이어야 한다.

 

 

2. Destination State Transformation

 

destination state에서 transition 할 때는 해당 state이면서 알맞은 input이 들어왔을 때 transition 하도록 바꿔준다.

이 그림에서는 S6 state이면서 C2 input이 들어왔을 때 S1으로 transition된다.

 

 

3. Multiple Transitions with Same Source or Destination

SA로 transition 하는 state가 여러 개일 때(partition을 넘어가는 transition)  OR을 사용하여 input 조건을 표기한다.

이 그림에서 보면 S2는 C3, C5에 대하여 모두 다른 partition의 state인 S5, S4로 transition한다.

그래서 partitioning을 하면, C3+C5 조건을 통해 SA로 transition할 수 있다.

SB에서는 2번 규칙과 3번 규칙에 의해 C3*S2 + C4*S3일 때 S5로 transition한다. 

 

 

4. Hold Condition for Idle State

 

SA에서 destination state transformation 조건에 만족하지 않을 때는 hold되어야 한다.