[VerilogHDL] 22_유한 상태 머신(Finite State Machine)

1. 유한 상태 머신(Finite State Machine)

Verilog HDL에서 FSM (Finite State Machine)은 순차 논리(Sequential Logic) 구성 요소 중 하나로, 여러 상태와 상태 전이(Transition)를 가지며, 입력 신호에 따라 상태를 변경하는 동작을 수행하는 회로입니다. FSM은 주어진 입력에 따라 미리 정의된 상태 전이 테이블을 기반으로 동작하며, 각 상태에서의 출력을 제어할 수 있습니다.

1.1 상태(State)

FSM이 취할 수 있는 여러 상태를 나타냅니다. 상태는 유한한 개수로 정의되며, 각 상태는 유일한 식별자로 구분됩니다. 예를 들어 “S0”, “S1”, "S2"와 같은 형태로 표현될 수 있습니다.

1.2 입력(Input)

FSM이 받는 외부 입력 신호를 나타냅니다. 입력은 FSM의 동작을 결정하는 데 사용됩니다. 입력은 주어진 상태에서 다음 상태로 전이하는 조건을 결정하는데 사용될 수 있습니다.

1.3 출력(Output)

각 상태에서의 출력 신호를 나타냅니다. 출력은 상태에 따라 변화할 수 있으며, 특정 상태에서만 활성화될 수 있습니다.

FSM은 일반적으로 두 가지 설계 형태가 있습니다.

• Mealy FSM: 입력에 따라 상태 전이와 출력을 결정합니다. 입력에 따라 출력이 변경될 수 있으며, 출력은 상태 전이 조건과 입력에 의존할 수 있습니다.

• Moore FSM: 입력에 따라 상태 전이를 결정하고, 상태에 따라 출력을 결정합니다. 출력은 현재 상태에만 의존하며, 입력에 따라 직접적으로 변경되지 않습니다.

FSM을 Verilog HDL로 구현할 때는 상태와 상태 전이를 나타내는 논리 회로와 출력을 제어하는 논리 회로를 설계합니다. 이를 위해 reg와 always 블록을 사용하여 각 상태와 전이를 나타내는 조건을 구현합니다.

2. 예제 코드

2.1 Mealy FSM Example

module mealy_fsm(
   input wire clk,
   input wire reset,
   input wire in,
   output wire out,
   output wire [1:0] count
);
   reg [1:0] state;
   reg [1:0] next_state;
   reg out;

   always @(posedge clk or posedge reset) begin
      if (reset) begin
         state <= 2'b00;
      end else begin
         state <= next_state;
      end
   end

   always @(*) begin
      case (state)
         2'b00: begin
            if (in) begin
               next_state = 2'b01;
               out = 1'b0;
            end else begin
               next_state = 2'b00;
               out = 1'b1;
            end
         end
         2'b01: begin
            if (in) begin
               next_state = 2'b10;
               out = 1'b1;
            end else begin
               next_state = 2'b00;
               out = 1'b0;
            end
         end
         2'b10: begin
            if (in) begin
               next_state = 2'b10;
               out = 1'b1;
            end else begin
               next_state = 2'b00;
               out = 1'b0;
            end
         end
         default: begin
            next_state = 2'b00;
            out = 1'b0;
         end
      endcase
   end

   always @(posedge clk) begin
      count <= state;
   end
endmodule

위의 예제 코드에서 mealy_fsm 모듈은 클럭(clk), 리셋(reset), 입력 신호(in) 및 출력 신호(out, count)를 가지고 있습니다. Mealy 상태 기계에서 출력은 조합적으로 결정되며, 출력 신호는 상태와 입력에 의존하여 업데이트됩니다.

이 예제에서는 in 입력 신호가 1인 경우, 출력 신호 out은 0이 되고, 다음 상태는 현재 상태에서 01로 전이합니다. 반대로, in 입력 신호가 0인 경우, 출력 신호 out은 1이 되고, 다음 상태는 현재 상태에서 00로 전이합니다.

Mealy 상태 기계는 Moore 상태 기계와는 달리 출력이 상태에 따라 변하는 특성을 가지므로, 출력과 상태 전이를 조합적으로 설계해야 합니다.

2.2 Moore FSM Example

module serial_parallel_converter(
   input wire clk,
   input wire reset,
   input wire serial_in,
   output wire [1:0] parallel_out
);
   reg [1:0] state;
   reg [1:0] next_state;
   reg [1:0] parallel_data;

   always @(posedge clk or posedge reset) begin
      if (reset)
         state <= 2'b00;
      else
         state <= next_state;
   end

   always @(state or serial_in) begin
      case (state)
         2'b00: begin
            next_state = 2'b01;
            parallel_data = 2'b00;
         end
         2'b01: begin
            next_state = 2'b10;
            parallel_data = {serial_in, parallel_data[0]};
         end
         2'b10: begin
            next_state = 2'b01;
            parallel_data = {serial_in, parallel_data[0]};
         end
         default: begin
            next_state = 2'b00;
            parallel_data = 2'b00;
         end
      endcase
   end

   assign parallel_out = parallel_data;
endmodule

위의 예제 코드에서 serial_parallel_converter 모듈은 클럭(clk), 리셋(reset), 직렬 입력(serial_in), 병렬 출력(parallel_out)을 가지고 있습니다. 상태는 2비트 레지스터 state로 표현되며, 다음 상태를 결정하는 논리는 always 블록 내에서 조합적으로 구현됩니다. 출력 parallel_out은 현재 상태에 따라 결정되는 논리 회로로 구현됩니다.

위의 예제는 상태 전이 테이블을 기반으로 상태 전이와 출력을 제어하는 논리를 구현한 것입니다. 각 상태에서의 동작은 case 문을 사용하여 정의되며, 입력 신호와 현재 상태에 따라 다음 상태와 출력이 결정됩니다.

3. 정리

FSM은 복잡한 순차 동작을 표현하고 제어하는 데 사용됩니다. 다양한 응용 분야에서 사용되며, 상태 기계, 제어 장치, 프로토콜 구현 등에 활용됩니다.

3.1 Mealy 상태 기계의 장단점

3.1.1 장점

• 상태 전이 테이블 크기가 작습니다. Mealy 기계는 출력이 입력과 현재 상태에 의존하기 때문에 출력을 상태 전이 테이블에서 직접 정의할 수 있습니다. 따라서 상태 전이 테이블의 크기가 상대적으로 작아집니다.
• 출력이 더 빠릅니다. Mealy 기계에서 출력은 입력과 현재 상태에 의존하므로, 출력이 변경되는 시점이 Moore 기계보다 빠를 수 있습니다.

3.1.2 단점

• 상태 전이 테이블이 복잡할 수 있습니다. 출력이 입력과 상태에 의존하므로, 상태 전이 테이블이 복잡해질 수 있습니다. 이는 설계 및 디버깅을 어렵게 만들 수 있습니다.
• 출력의 변화가 상태 전이와 동시에 발생합니다. 이로 인해 출력의 변화가 제대로 동작하지 않을 수 있습니다. 출력의 변화 시기와 상태 전이 시기가 일치해야 올바른 결과를 얻을 수 있습니다.

3.2 Moore 상태 기계의 장단점

3.2.1 장점

• 설계가 상대적으로 간단합니다. Moore 기계에서는 출력이 현재 상태에만 의존하기 때문에 상태 전이 테이블이 단순화됩니다. 따라서 설계 및 디버깅이 상대적으로 쉬울 수 있습니다.
• 출력의 변화와 상태 전이가 동기화됩니다. Moore 기계에서는 출력이 상태에 의해 결정되므로, 출력의 변화 시기가 상태 전이와 동기화되어 정확한 결과를 얻을 수 있습니다.

3.2.2 단점

• 상태 전이 테이블의 크기가 큽니다. Moore 기계에서는 출력이 상태에만 의존하므로, 상태 전이 테이블에는 출력이 포함되지 않습니다. 따라서 상태 전이 테이블의 크기가 Mealy 기계에 비해 크게 될 수 있습니다.
• 출력의 변화가 느릴 수 있습니다. Moore 기계에서는 상태 전이 이후에만 출력이 변경됩니다. 따라서 출력의 변화가 Mealy 기계에 비해 느릴 수 있습니다.

이러한 장단점을 고려하여 상태 기계를 설계할 때는 특정한 요구사항과 제약사항을 고려해야 합니다. Mealy 기계는 상태 전이 테이블의 크기를 줄이고 출력을 빠르게 변경해야 하는 경우에 적합할 수 있습니다. Moore 기계는 설계의 간소화와 출력의 안정성이 우선적인 경우에 유용할 수 있습니다.