22. 유한 상태 기계 (Finite State Machine)

상태 (State)

플립플롭이 저장하고 있는 데이터를 상태라고 한다. 순차 회로의 출력 결과는 입력과 회로 내부의 플립플롭의 이전 상태에 의해 결정된다.

Present State	Next State		Output
	x=0	x=1	x=0	x=1
$S_0$ = 00	00	10	0	0
$S_1$ = 01	10	10	0	0
$S_2$ = 10	00	11	0	0
$S_3$ = 11	10	11	0	1

Present State는 현재 플립플롭에 저장된 값, Next State는 다음 Rising Edge에서 변화할 플립플롭의 상태를 의미한다.

Mealy Machine and Moore Machine

Mealy Machine의 출력은 현재의 입력과 상태에 의해 바로 결정된다. 반면에 Moore Machine은 State에 의해서만 출력이 결정되는데, 이 둘의 차이는 아래 그림을 보고 이해하면 쉽다.

Mealy Machine

Moore Machine

Mealy Machine은 입력이 직접 출력에 영향을 주는 반면, Moore Machine은 입력이 무조건 순차 회로를 한 번 거쳐 출력된다.

유한 상태 기계 (Finite State Machine)

상태 기계 개념은 컴퓨터 하드웨어를 Datapath와 Control로 나눈다. Datapath에는 Register, 조합회로(ALU 등..), Bus와 같은 데이터를 다루는 회로 전반이 포함되며, Control은 유한 상태 기계로 구성된다. Control은 Datapath에 Control 신호를 제공하거나 Datapath가 다음에 수행할 연산을 지정해주는 등의 역할을 수행하며, Datapath는 Control에 입력과 같은 데이터를 제공한다.

유한 상태 기계는 이름처럼 유한한 갯수의 상태를 갖는데, 각 상태에 할당된 Signal에 따라 Datapath가 동작하게 된다.

유한 상태 기계를 설계하는 과정은 다음과 같이 정의할 수 있다.

1. 문제를 정의한다.
2. 각 상태에 이진 값을 정의한다. (00: 전원 켜는 중, 01: 작동 중 10: 오버클럭 모드 등..)
3. State Table을 만든다.
4. K-Map 등을 활용하여 최적화한다.
5. 적절한 논리 회로도를 설계한다.

1의 연속 입력을 감지하는 회로의 state diagram

State Reduction

회로 내의 플립플롭을 줄임으로써 회로를 최적화 할 수 있다.

Row Matching

만약 두 상태가

• 같은 출력을 갖고, 다음 상태로의 변환도 일치하거나
• self-loop을 돈다면

이 두 상태는 동일한 상태이다. 이러한 동일한 상태들을 합쳐서 상태의 갯수를 줄일 수 있다.

예를들어, 위에서 S0과 S2는 같은 상태이다.