[Verilog]Moore FSM으로 신호등 만들기

오늘은 Moore FSM(Finite State Machine)으로 신호등을 만들어 보겠습니다. 보통 신호등은 색깔별로 시간이 정해져 있지만, 오늘은 차량 통행의 유무에 따라 작동하는 신호등을 만들어 보겠습니다.

IDE: Intel Quartus 18.1
Device: Cyclone V 5CSXFC6D6F31C6(밑에서 6번째)
Simulation: ModelSim-Altera, Verilog HDL
Project Name & the name of Top-level: fsm_traffic_light

1. 신호등 규칙 설명

신호등 규칙
보통 신호등은 색깔별로 시간이 정해져 있지만, 오늘은 차량 통행의 유무에 따라 작동하는 신호등을 만들어 보겠다고 말씀드렸습니다.
A, B 도로가 있습니다.
Reset이 1이 되면(rising edge) A 도로의 신호등에는 초록 불이, B 도로의 신호등에는 빨간 불이 켜집니다. A 도로에 차량 통행이 있는 동안에는 A 도로 신호등의 초록 불이 유지됩니다.
A 도로에 차량 통행이 더 이상 없으면 A 도로의 신호등이 노란 불로 바뀝니다.
그 다음 A 도로의 신호등은 빨간 불로, B 도로의 신호등은 초록 불로 바뀝니다. B 도로에 차량 통행이 있는 동안에는 B 도로 신호등의 초록 불이 유지됩니다.
B 도로에 차량 통행이 더 이상 없으면 B 도로의 신호등이 노란 불로 바뀝니다.
그 다음 A 도로의 신호등은 초록 불로, B 도로의 신호등은 빨간 불로 바뀝니다.

2. Structural Design

2.1. FSM 설계

2.1.①. FSM State Transition Diagram을 설계합니다.

\(T_A\): A 도로의 차량 통행 여부(있으면 1, 없으면 0)
\(T_B\): B 도로의 차량 통행 여부(있으면 1, 없으면 0)
\(L_A\): A 도로의 신호등 색깔
\(L_B\): B 도로의 신호등 색깔

1번 문단에서 설명드린 내용이 위의 이미지와 같이 설계됩니다. 신호등 색깔에 따라서 state를 S0~S3으로 나누었습니다. 이것 중에서 S0~S1만 자세히 설명을 드리고 넘어가겠습니다.
Reset이 1이 되면(rising edge) A 도로의 신호등에는 초록 불이(S0 상태, \(L_A\): green), B 도로의 신호등에는 빨간 불이(\(L_B\): red) 켜집니다. A 도로에 차량 통행이 있는 동안에는(\(T_A\)) A 도로 신호등의 초록 불이 유지됩니다(S0 유지).
A 도로에 차량 통행이 더 이상 없으면(\(\overline{T_A}\)) A 도로의 신호등이 노란 불로 바뀝니다(S1으로 변경, \(L_A\): yellow, \(L_B\): red).

2.1.②. FSM State Transition Table을 만듭니다. Current State는 Q이고, Next State는 D입니다.
흰색 1~2번째 줄(Q=S0)만 설명을 드리자면,
Q=S0, \(T_A=0\)이면 \(T_B\)에 상관없이 D=S1이 됩니다.
Q=S0, \(T_A=1\)이면 \(T_B\)에 상관없이 D=S0이 됩니다.

FSM Encode State Transition Table
2.1.③. 위의 이미지 왼쪽부터 보시면 됩니다.
S0~S3을 무엇으로 Encoding할지 Encoding Table을 만듭니다.
S개의 state를 binary encoding할 때 \(\lceil \log_2 S \rceil\)비트로 encoding됩니다. 지금은 state가 4개이니 \(\lceil \log_2 4 \rceil = 2\)비트가 되네요.
↓
앞서 만든 FSM State Transition Table과 Encoding Table을 토대로 FSM Encode State Transition Table을 만듭니다.
↓
\(D_1\)과 \(D_0\) 각각의 boolean equation을 도출합니다.
Karnaugh Map을 그려 본 결과
\(D_1 = Q_1 \oplus Q_0\)
\(D_0 = {Q_1}’{Q_0}’{T_A}’+Q_1{Q_0}’{T_B}’\)
가 나왔습니다.

2.1.④. 신호등 색깔별로 Encoding합니다. 신호등 색깔은 3개이므로 binary encoding하면 \(\lceil \log_2 3 \rceil = \lceil 1. \text x \text x \rceil = 2\) 비트로 encoding되네요.
Current State에 따라 \(L_A\)와 \(L_B\)를 어떻게 출력할 것인지 FSM Output Table을 그립니다. 가령 \(Q_1=0\), \(Q_0=0\)이면 \(L_A\)는 green, \(L_B\)는 red이므로 \(L_A=00_2\), \(L_B=10_2\)가 됩니다.
그러면 신호등의 boolean equation은 아래와 같이 나옵니다.
\(L_{A1}=Q_1\)
\(L_{A0}=\overline{Q_1} Q_0\)
\(L_{B1}=\overline{Q_1}\)
\(L_{B0}=Q_1 Q_0\)

FSM Schematic
2.1.⑤. State Register를 그립니다.
2.1.⑥. Next State Logic을 만듭니다.
2.1.⑦. Output Logic을 만듭니다.

저는 추가로 bubble pushing도 해 주었습니다.

2.1.⑧. Timing analysis를 합니다. 다만, 오늘 Verilog 설계를 할 때는 timing analysis를 생략하겠습니다. Intel Quartus로 timing analysis하는 방법은 지난 글을 참고하시기 바랍니다.
Intel Quartus로 Verilog Timing Analysis(https://sooseongcom.com/post/verilog-timing-quartus)

2.2. reg2.v

module reg2(clk, reset_n, d, q);
	input clk, reset_n;
	input [2:0] d;
	output reg [2:0] q;
	
	always @ (posedge clk or negedge reset_n)
	begin
		if(reset_n==0)	q<=0;
		else	q<=d;
	end
endmodule
 

2.3. fsm_traffic_light.v

module fsm_traffic_light(clk, reset_n, traffic_a, traffic_b, light_a, light_b);
	//inputs and outputs
	input clk, reset_n;
	input traffic_a, traffic_b;
	output [1:0] light_a, light_b;
	
	//states
	wire [1:0] d;	//Next State
	wire [1:0] q;	//Current State
	
	//wire for NAND gate
	wire w_nd1, w_nd2;
	
	//d[1]=q[1]^q[0]
	xor(d[1], q[1], q[0]);
	
	//d[0]=~((~(~q[1]&~q[0]&~traffic_a))&(~(q[1]&~q[0]&~traffic_b)))
	nand(w_nd1, ~q[1], ~q[0], ~traffic_a);
	nand(w_nd2, q[1], ~q[0], ~traffic_b);
	nand(d[0], w_nd1, w_nd2);
	
	reg2 state_reg(clk, reset_n, d, q);
	
	assign light_a[1]=q[1];
	and(light_a[0], ~q[1], q[0]);
	
	not(light_b[1], q[1]);
	and(light_b[0], q[1], q[0]);
endmodule

[Line 4]
input traffic_a, traffic_b;
traffic_a는 \(T_A\)이고, traffic_b는 \(T_B\)입니다.

[Line 5]
output [1:0] light_a, light_b;
light_a는 \(L_A\)이고, light_b는 \(L_B\)입니다.

[Line 7~9 states]
d와 q를 2-bit wire로 선언합니다.

[Line 11~12 wire for NAND gate]
12행) wire w_nd1, w_nd2;
NAND gate의 output을 연결할 wire를 선언합니다.

[Line 14~20]
Next State Logic입니다.

[Line 22]
reg2 state_reg(clk, reset_n, d, q);
State Register는 reg2를 instantiation하여 구현합니다.

[Line 24~28]
Output Logic입니다.

2.4. tb_fsm_traffic_light.v

`timescale 1ns/100ps
 
module tb_fsm_traffic_light();
	reg clk, reset;
	reg traffic_a, traffic_b;
	reg [1:0] light_a_expected, light_b_expected;
	wire [1:0] light_a, light_b;
	reg [31:0] vectornum, errors;	//bookkeeping variables
	reg [31:0] testvectors[10000:0];	//array of testvectors
	
	//instantiate device under test
	fsm_traffic_light dut(clk, ~reset, traffic_a, traffic_b, light_a, light_b);
	
	//generate clock
	always
		begin
			clk=1; #5; clk=0; #5;
		end
	
	//at start of test, load vectors and pulse reset
	initial
		begin
			$readmemb("./tv_fsm_traffic_light.tv", testvectors);	//Put testvector file at simulation\modelsim
			vectornum=0; errors=0;
			reset=1; #27; reset=0;
		end
		
	//apply test vectors on rising edge of clk
	always @(posedge clk)
		begin
			#1; {traffic_a, traffic_b, light_a_expected, light_b_expected}=testvectors[vectornum];
		end
		
	//check results on falling edge of clk
	always @(negedge clk)
		if(~reset) begin //skip during reset==1
			if({light_a, light_b}!=={light_a_expected, light_b_expected}) begin
				$display("Error: inputs=%b", {traffic_a, traffic_b});
				$display("	outputs=%b (%b expected)", {light_a, light_b}, {light_a_expected, light_b_expected});
				errors=errors+1;
			end
			
	//increment array index and read next testvector
			vectornum=vectornum+1;
			if(testvectors[vectornum]===32'bx) begin
				$display("%d tests completed with %d errors.", vectornum, errors);
				$finish;
			end
		end
endmodule
 

2.5. simmulation\modelsim\tv_fsm_traffic_light.tv

각 줄이 <traffic_a><traffic_b>_<light_a_expected><light_b_expected>입니다.
<light_a_expected>와 <light_b_expected>는 각각 2-bit이며, Current State에 따른 출력 값을 기준으로 합니다.
예) 00_0110은 traffic_a=0, traffic_b=0, light_a_expected=01, light_b_expected=10입니다.

2.6. RTL View

Structural RTL View

2.7. RTL Simulation

Structural RTL Simulation

2.8. Flow Summary

Structural Flow Summary

Logic utilization (in ALMs): 3 / 41,910 (<1%)
Total registers: 3
Total pins: 8 / 499 (2%)

3. Behavioral Design

3.1. FSM State Transition Diagram

Behavioral Design도 FSM State Transition Diagram을 그립니다. FSM State Transition Diagram은 Structural Design과 같습니다.

3.2. fsm_traffic_light.v

module fsm_traffic_light(clk, reset_n, traffic_a, traffic_b, light_a, light_b);
	//inputs and outputs
	input clk, reset_n;
	input traffic_a, traffic_b;
	output reg [1:0] light_a, light_b;
	
	//encoded states
	parameter S0=2'b00;
	parameter S1=2'b01;
	parameter S2=2'b10;
	parameter S3=2'b11;
	
	//encoded outputs
	parameter GREEN=2'b00;
	parameter YELLOW=2'b01;
	parameter RED=2'b10;
	
	//sequential circuit part
	reg [1:0] d;	//Next State
	reg [1:0] q;	//Current State
	
	always @ (posedge clk or negedge reset_n)
	begin
		if(reset_n==0)	q<=S0;
		else	q<=d;
	end
	
	//combinational circuit part
	always @ (*)
	begin
		casex({q, traffic_a, traffic_b})
			{S0, 1'b0, 1'bx}: d=S1;
			{S0, 1'b1, 1'bx}: d=S0;
			{S1, 1'bx, 1'bx}: d=S2;
			{S2, 1'bx, 1'b0}: d=S3;
			{S2, 1'bx, 1'b1}: d=S2;
			{S3, 1'bx, 1'bx}: d=S0;
		endcase
		
		case(q)
			S0: {light_a, light_b}={GREEN, RED};
			S1: {light_a, light_b}={YELLOW, RED};
			S2: {light_a, light_b}={RED, GREEN};
			S3: {light_a, light_b}={RED, YELLOW};
		endcase
	end
endmodule

[Line 4]
input traffic_a, traffic_b;
traffic_a는 \(T_A\)이고, traffic_b는 \(T_B\)입니다.

[Line 5]
output reg [1:0] light_a, light_b;
light_a는 \(L_A\)이고, light_b는 \(L_B\)입니다. reg로 선언합니다.

[Line 7~11 encoded states]
S0부터 S3까지를 parameter로 선언하고 각각의 binary encoding으로 초기화합니다. parameter 이름은 일반적으로 대문자로 짓습니다.

[Line 13~16 encoded outputs]
신호등 색깔을 parameter로 선언하고 각각의 binary encoding으로 초기화합니다. 7~11행의 states와 마찬가지로 이름은 대문자로 짓습니다.

[Line 19~20]
d와 q를 2-bit reg로 선언합니다.

[Line 21~25]
State Register입니다.

[Line 21]
always @ (posedge clk or negedge reset_n)
clk가 0→1 상승하거나(posedge) reset_n이 1→0 하강할 때(negedge) 출력 값을 업데이트합니다.

[Line 23]
if(reset_n==0) q<=S0;
reset_n==0이면 즉시 q<=S0;을 수행합니다.

[Line 24]
else q<=d;
reset_n!=0이면(즉, reset_n==1이면) q<=d;를 수행합니다.

[Line 29]
always @ (*)
Next State Logic과 Output Logic은 combinational circuit이므로 always문의 조건을 *로 합니다.

[Line 31~38]
Next State Logic입니다.

[Line 31]
casex({q, traffic_a, traffic_b})
x 기호를 don’t care로 사용하기 위해서 case 대신 casex를 사용합니다.
중괄호는 concatenation으로서 어떤 두 signal을 연결해 줍니다.
{q, traffic_a, traffic_b}의 값에 따라 case문이 작동하게 됩니다.
32~37행 코드를 보시면 어떤 원리로 작동되는지 아실 것 같습니다.

[Line 40~45]
Output Logic입니다.

[Line 41~44]
41행) S0: {light_a, light_b}={GREEN, RED};
concatenation은 값을 대입할 때도 사용 가능합니다. 41행 코드는 q==S0일 때 light_a에는 GREEN을, light_b에는 RED를 대입합니다.

3.3. tb_fsm_traffic_light.v & simmulation\modelsim\tv_fsm_traffic_light.tv

testbench와 testvector는 Structural Design에서 사용한 것과 동일합니다.

2.4. tb_fsm_traffic_light.v
2.5. simmulation\modelsim\tv_fsm_traffic_light.tv

3.4. RTL View

Behavioral RTL View
Decoder가 사용되었습니다. Concatenation을 사용한 것들이 다 decoder로 변환된 듯 보입니다.

3.5. RTL Simulation

Behavioral RTL Simulation

3.6. Flow Summary

Behavioral Flow Summary

Logic utilization (in ALMs): 3 / 41,910 (<1%)
Total registers: 3
Total pins: 8 / 499 (2%)

Structural Design과 똑같이 나왔습니다.

4. 글 마무리

오늘은 이렇게 신호등 Moore FSM을 Structural Design과 Behavioral Design으로 각각 구현해 보았습니다.
제 글을 읽어 주셔서 감사합니다. 다음에 만나요!

5. 참고 문헌

1) David Money Harris, Sarah L. Harris. 2013. Digital Design and Computer Architecture. 2nd Edition. Elsevier Korea L.L.C.

필자(수성컴)의 노트북은 갤럭시 북 Flex2입니다.(Windows 11)

목차