Verilog 패턴 디텍터: '110101' 검출 FSM과 오버래핑 처리

앞선 '1011' 디텍터에 이어 더 긴 패턴 110101 (6비트) 검출기를 구현하고, 오버래핑 패턴 처리까지 다룹니다.

상태 정의 (7개 상태)

RTL 구현 (오버래핑 버그 포함 버전)

module det_110101 (
    input  wire clk,
    input  wire rstn,
    input  wire in,
    output wire out
);
    parameter IDLE=0, S1=1, S11=2, S110=3, S1101=4, S11010=5, S110101=6;
    reg [2:0] cur_state, next_state;

    assign out = (cur_state == S110101);

    always @(posedge clk) begin
        if (!rstn) cur_state <= IDLE;
        else       cur_state <= next_state;
    end

    always @(cur_state or in) begin
        case (cur_state)
            IDLE:     next_state = in ? S1      : IDLE;
            S1:       next_state = in ? S11     : IDLE;
            S11:      next_state = in ? S11     : S110;      // '1' 계속 들어오면 S11 유지
            S110:     next_state = in ? S1101   : IDLE;
            S1101:    next_state = in ? IDLE    : S11010;    // Bug 1: in=1 시 IDLE로?
            S11010:   next_state = in ? S110101 : IDLE;
            S110101:  next_state = in ? S1      : IDLE;      // Bug 2: 오버래핑 처리
            default:  next_state = IDLE;
        endcase
    end
endmodule

테스트벤치 및 시뮬레이션

module tb;
    reg clk, in, rstn; wire out;
    always #10 clk = ~clk;
    det_110101 u0 (.clk(clk), .rstn(rstn), .in(in), .out(out));
    initial begin
        clk=0; rstn=0; in=0; repeat(5) @(posedge clk); rstn=1;
        // 패턴: 1 1 0 1 0 1
        @(posedge clk) in=1; @(posedge clk) in=1; @(posedge clk) in=0;
        @(posedge clk) in=1; @(posedge clk) in=0; @(posedge clk) in=1;
        @(posedge clk) in=1; @(posedge clk) in=1; @(posedge clk) in=0;
        @(posedge clk) in=1; @(posedge clk) in=0; @(posedge clk) in=1;
        #100 $finish;
    end
endmodule

시뮬레이션 로그 분석

T=230  in=1  out=1  ← 첫 패턴 완료
T=350  in=1  out=1  ← 두 번째 패턴 완료

발견된 버그 2가지

1. S1101 상태에서 in=1 시 IDLE로 전이 (Bug 1): 패턴 '110101'에서 '1101' 다음이 '1'이면 '11011'이 되어 패턴이 깨지지만, 실제로는 '11011'의 접미사 '11'이 패턴 '110101'의 접두사 '11'과 일치하므로 S11로 가야 함 (KMP 알고리즘의 실패 함수 개념).
2. S110101 상태에서 in=1 시 S1로 전이 (Bug 2): 완전 매칭 후 입력이 '1'이면 마지막 '1'을 다음 패턴 첫 '1'로 재사용해 S1이 아닌 S11로 가야 함 (패턴이 '1'로 시작하므로 '11' 접두사 매칭).

올바른 다음 상태 로직 (KMP 기반)

패턴 '110101'의 접두사-접미사 매칭 테이블(실패 함수) 계산 후 각 상태에서 입력 0/1에 대한 올바른 다음 상태 결정 필요. 이는 다음 글에서 SystemVerilog always_comb와 함수로 깔끔하게 구현해보겠습니다.

교훈

• 시퀀스 디텍터 설계 시 오버래핑 패턴 고려 필수
• 상태 전이는 최장 진입 접두사 기준으로 결정 (KMP 알고리즘 적용)
• 수동 상태 머신 코딩은 버그 위험 높음 → 자동 생성 도구 또는 형식적 검증 활용 권장