Finite State Machine (유한 상태 머신)
- Finite State Machine (유한 상태 머신)
- 일종의 메모리
- 메모리는 단순 값을 저장하지만 FSM은 유한한 갯수의 정해진 상태값을 저장하는 LOGIC
- FSM에선 메모리가 아닌 MACHINE이란 명칭이 붙는다 -> 단순 상태값을 저장하는 것 뿐만 아니라 다음상태값을 무엇으로 저장할 것인가에도 FSM이 능동적으로 결정하기 때문
- 현재상태를 저장하는 플립플롭(레지스터)로직과 현재 들어오는 입력값과 다음 상태값을 결정하는 로직(상태 결정 회로, 조합회로)의 조합으로 이루어져있다.
- 정해진 순서를 갖는 패턴을 출력으로 내보내는 로직
- State Machine 예시
안의 숫자 = 현재 상태
외부의 숫자 = 입력
- 현재입력이 000이라면 다음상태는 변하지 않고 000유지
- 입력값이 001이라면 현재상태가 000 -> 001로 상태이동하게 된다.
- 현재상태가 001인 상황에서 입력값이 101이 들어오면 101 -> 000의 상태가 되고 001이 들어오게 되면 001 -> 010의 상태가 되게 된다.
현재상태 000
-> 입력 = 001
-> 현재상태를 저장하는 플립플롭(레지스터) = 001
-> 다음 상태값을 결정하는 로직(조합회로) = 101, 001 (현재 레지스터를 기준으로 흐름을 피드백 해주는 부분(조합회로))
다음의 FSM을 베릴로그 코드로 나타낸다면 밑의 코드로 구성
...
reg currentState;
...
always@(posedge clk) begin
case (currentState)
3'b000 : begin
if(Signal_Input == 3'b001)
currentState <= current+1'b1;
end
3'b001 : begin
if(Signal_Input == 3'b001)
currentState <= current+1'b1;
else if(Signal_Input == 3'b101)
currentState <= 3'b000;
end
3'b010 : begin
if(Signal_Input == 3'b001)
currentState <= current+1'b1;
end
3'b011 : begin
if(Signal_Input == 3'b001)
currentState <= current+1'b1;
else if(Signal_Input == 3'b101)
currentState <= 3'b000;
end
...유한상태머신의 현재상태는 값을 저장하고있으므로 reg로 저장.
다음의 상태는 case문으로 구성되어있다.
- Moore and Mealy
프로그래밍에서도 STATE머신이 사용
베릴로그와 FPGA에서는 STATE머신이 2가지 종류가 존재
- Moore Machine = 현재의 입력이 state를 결정하는데에는 영향을 미치지만, 출력에는 영향을 미치지 않는다.
- Mealy Machine = 현재의 입력이 state를 결정하는데에도 영향을 미치고, 출력에도 영향을 미친다.
- 출력에 Synchronous하게 작용하지 않는다.
- 입력의 값이 변하는 순간 출력의 값이 변하기 때문에 클럭의 rising edge를 기다리지 않고 바로 출력값이 나올 수 있다
- Moore Machine 보다 동작관점에서 빠를 수 있지만 clock에 Synchronous하게 동작하지 않기 때문에 State Machine이 복잡해짐에 따라서 propagation delay time(전파 지연 시간)에 의한 타이밍 유출 또한 발생 가능
STATE머신 = 현재 입력과 현재 자신의 상태를 기준으로 다음상태값을 결정한다.
Moore과 Mealy은 둘다 같은 state machine으로 보일 수 있지만 세부적으로 다르다.
현재의 입력이 출력에 영향을 끼치는가 아닌가의 차이.
- 신호등 예제
빨간색 -> 초록색 -> 주황색 -> 빨간색 순을 유지
새벽의 신호등은
점멸신호라 하여 주황색신호만 점등된다
현재입력이 새벽이라면 주황색불에서만 점등 -> State Machine을 사용해서 구현가능
//일반 설계
if(현재 상태 == 빨강)
현재상태 <= 초록;
else if(현재 상태 == 초록)
현재 상태 <= 주황;
else
현재상태 <= 빨강;
if(현재 상태 == 빨강 && !새벽)
red <= 1;
else if(현재 상태 == 초록 && !새벽)
green <= 1;
else
yellow <= 1;
//Moore case
always @ (새벽) begin
if(현재 상태 == 초록)
현재상태 <= 주황;
else if(현재 상태 == 주황 && !새벽)
현재 상태 <= 빨강;
else
현재상태 <= 초록;
end
always @ (posedge clk) begin
if(현재 상태 == 빨강)
red <= 1; green <= 0; yellow <= 1;
else if(현재 상태 == 초록)
red <= 0; green <= 1; yellow <= 0;
else if(현재 상태 == 주황)
red <= 0; green <= 0; yellow <= 1;
end
//Mealy case
always @ (posedge clk or 새벽) begin
if(현재 상태 == 빨강)
현재상태 <= 초록;
else if(현재 상태 == 초록)
현재 상태 <= 주황;
else
현재상태 <= 빨강;
if(현재 상태 == 빨강 && !새벽)
red <= 1;
else if(현재 상태 == 초록 && !새벽)
green <= 1;
else
yellow <= 1;
end
일반적으론 Moore Machine으로 설계하는 것이 좋다. 베릴로그에서는 시뮬레이션과 검증하는 것이 까다롭기 때문에 디버깅하기 까다롭다. 그래서, Mealy Machine으로 설계했다 타이밍 이슈에 의해 내가 설계했던 흐름대로 state가 변동하지 않는 경우가 발생가능.
그래서 일반적으로 Moore Machine으로 설계하는 것이 좋다. (그러나, Moore Machine은 상승엣지에서 동작하기 때문에 현재의 상태값과 다음의 상태값에 의해 출력의 결정이 1cycle 씩 밀릴 수 있다.)
- 신호등 예제 코드
- 초록 = 000
- 주황 = 001
- 빨강 = 010
//FSM Moor case
`timescale 1ns / 1ps
module FSM(
input clk,
input A,
output reg red,
output reg green,
output reg yellow
);
reg [2:0] stateNow = 3'b0;
always @(posedge clk) begin
case(stateNow)
3'b000 : begin
stateNow <= 3'b001;
end
3'b001 : begin
if(A)
stateNow <= 3'b010;
else
stateNow <= 3'b001;
end
3'b010 : begin
stateNow <= 3'b000;
end
endcase
end
always @ (posedge clk) begin
case(stateNow)
3'b000 : begin
{red, green, yellow} <= 3'b010;
end
3'b001 : begin
{red, green, yellow} <= 3'b001;
end
3'b010 : begin
{red, green, yellow} <= 3'b100;
end
endcase
end
endmodule//테스트 벤치 코드
`timescale 1ns / 1ps
module FSM_TB();
reg clk;
reg A;
wire red;
wire green;
wire yellow;
FSM tb (.clk(clk), .A(A), .red(red), .green(green), .yellow(yellow));
initial begin
clk = 1'b0;
repeat (1000000) #5 clk <= ~ clk;
end
initial begin
A <= 1'b0;
#50;
A <= 1'b1;
#50;
A <= 1'b0;
end
endmodule
