유한 상태 기계

동기 순차 회로의 일반형

조합 회로의 출력은 지금의 입력만으로 정해진다. 순차 회로의 출력은 지금까지 들어온 입력 전체에 달려 있다. 그러나 과거 전체를 다 기억할 수는 없으니, 앞으로의 동작에 필요한 만큼만 요약해 둔다. 이 요약이 상태(State)다. 상태를 \(k\)비트 플립플롭에 담으면 가능한 상태는 많아야 \(2^k\)개, 즉 유한하다. 이름의 "유한"이 바로 이 뜻이다.

클럭 하나로 모든 플립플롭을 함께 움직이는 동기 순차 회로(Synchronous sequential circuit)는 예외 없이 아래 세 덩어리로 나눌 수 있다. 카운터도, 시프트 레지스터도, CPU의 제어 장치도 마찬가지다.

이 틀의 핵심은 되먹임 고리가 반드시 플립플롭을 지난다는 것이다. 조합 논리만으로 고리를 만들면 8장의 래치처럼 값이 언제 자리 잡을지 알 수 없지만, 고리 중간에 에지 트리거 플립플롭을 두면 "한 클럭에 한 걸음"이라는 규칙이 생긴다. 그 덕에 우리는 지연이 몇 피코초인지 잊고, 상태가 클럭마다 하나씩 바뀌는 이산 시간 기계로 회로를 생각할 수 있다. 대가는 하나다. 다음 상태 논리가 한 클럭 안에 계산을 마쳐야 한다(10장).

아래 그림에서 2비트 업/다운 카운터를 이 틀로 돌려 보자. 다음 상태 논리는 "UP이면 +1, 아니면 −1"을 계산하고, 출력 논리는 무어 모드에서 "상태가 3인가", 밀리 모드에서 "이번 클럭에 한 바퀴를 넘어가는가(자리올림·자리내림)"를 계산한다.

카운터: 가장 단순한 상태 기계

입력이 없거나(클럭만 받는다) 허용 신호 하나뿐인 FSM의 대표가 카운터(Counter)다. \(n\)비트 이진 카운터의 상태는 \(2^n\)개이고, 다음 상태 함수는 \(\delta(s) = s+1 \bmod 2^n\)이다. 덧셈기를 붙여 구현할 수도 있지만, 비트 단위로 보면 훨씬 단순한 규칙이 보인다. 비트 \(i\)는 그보다 아래 비트가 모두 1일 때만 뒤집힌다.

토글 조건을 만드는 방법은 둘이다. 동기 카운터(Synchronous counter)는 모든 플립플롭이 같은 클럭을 받고, AND 사슬로 \(T_i\)를 만들어 XOR로 다음 값을 계산한다. 모든 비트가 같은 에지에서 \(t_{cq}\)만큼 뒤에 함께 바뀐다. 리플 카운터(Ripple counter, 비동기 카운터)는 더 교묘하다. 비트 \(i\)가 1→0으로 떨어지는 순간이 곧 비트 \(i+1\)이 뒤집혀야 하는 순간이므로, 각 비트의 출력을 다음 비트의 클럭으로 쓴다. 게이트가 하나도 없지만, 바뀜이 물결처럼 한 비트씩 번져 가므로 비트마다 \(t_{cq}\)가 쌓인다.

시뮬레이터에서 리플 카운터를 \(n=6\)으로 늘려 보자. 011111 → 100000에서 여섯 비트가 \(t_{cq}\) 간격으로 차례로 넘어지며 31 → 30 → 28 → 24 → 16 → 0 → 32를 지나간다. 동기 카운터는 같은 순간에 모든 비트가 바뀌므로(빨간 띠 없음) 값을 읽는 쪽이 안심할 수 있다. 대신 클럭 주기를 줄이다 보면 동기 카운터는 AND 사슬이 끝나기 전에 다음 에지가 와서 세는 값 자체가 틀리기 시작한다. 리플 카운터는 첫 비트만 \(t_{cq}\) 안에 뒤집히면 되므로 아주 빠른 클럭도 셀 수는 있지만, 그 값을 다른 동기 회로가 읽을 수는 없다.

DG-7 기준 공정의 교육용 추정값: \(t_{cq}\)=25 ps(약 3.3 FO4), \(t_{\text{setup}}\)=10 ps, AND2 10 ps, XOR 12 ps. 실제 칩의 카운터는 배선과 클럭 스큐 여유까지 더해 이보다 느리게 잡는다.

시프트 레지스터와 LFSR

플립플롭을 줄지어 놓고 각 출력을 다음 플립플롭의 입력에 이으면 시프트 레지스터(Shift register)가 된다. 클럭마다 모든 비트가 한 칸씩 옆으로 옮겨 간다. 직렬로 들어온 비트를 병렬로 펼치거나(SIPO, 직렬→병렬), 반대로 병렬 데이터를 한 줄로 내보내는(PISO) 직렬 통신의 기본 부품이고, 신호를 정확히 \(k\)클럭 늦추는 지연선이기도 하다. 끝을 처음으로 다시 이으면 1 하나가 빙빙 도는 링 카운터가 되는데, 이것이 곧 뒤에 나올 원핫 상태 레지스터다.

되먹임에 XOR을 넣으면 놀라운 일이 생긴다. 몇 개의 비트 위치(탭(Tap))를 골라 XOR한 값을 맨 앞에 넣는 선형 되먹임 시프트 레지스터(LFSR, Linear Feedback Shift Register)는, 탭을 잘 고르면 0을 뺀 모든 \(2^n-1\)개 상태를 한 번씩 다 거친 다음에야 처음으로 돌아온다. 이것을 최대 길이 수열(m-sequence)이라 한다.

LFSR이 사랑받는 이유는 값싸기 때문이다. \(n\)비트에 플립플롭 \(n\)개와 XOR 몇 개면 끝나고, 되먹임 경로에 XOR 한두 단만 있으므로 같은 비트 수의 이진 카운터보다 훨씬 빠르다. 쓰임새는 넓다.

• 의사 난수(Pseudo-random): 출력 비트열은 0과 1의 개수가 거의 같고(\(2^{n-1}\)개 대 \(2^{n-1}-1\)개) 자기상관이 작다. 통신의 스크램블러, 확산 스펙트럼 코드, 디더링에 쓴다. 단, 암호용으로는 안전하지 않다.
• CRC(Cyclic Redundancy Check): 데이터 비트를 XOR 되먹임에 섞어 넣으면 LFSR이 다항식 나눗셈의 나머지를 계산한다. 이더넷의 CRC-32가 바로 32비트 LFSR이다.
• 내장 자체 테스트(BIST): 칩 안에서 LFSR로 테스트 패턴을 만들고, 다른 LFSR(MISR)로 응답을 압축해 서명 하나와 비교한다(16장).
• 값싼 카운터: 정확한 이진값이 필요 없고 "\(N\)클럭이 지났는가"만 알면 되는 타이머는 LFSR로 만들고 끝 상태 하나만 비교한다.

상태도에서 회로로: "101" 검출기

카운터는 다음 상태 함수가 뻔했다. 일반적인 FSM은 요구 사항에서 출발해 다섯 단계를 거친다. 예제로 입력 비트열에서 "101"이 나타날 때마다 1을 내는 시퀀스 검출기(Sequence detector)를 만들자. "10101"처럼 겹치는 경우도 두 번 세는 겹침 허용 방식이다.

① 상태도. 상태는 "지금까지 본 꼬리가 목표의 앞부분과 얼마나 맞는가"로 정한다. S0: 아무것도 못 맞춤, S1: "1"까지 맞춤, S2: "10"까지 맞춤, S3: "101" 완성(출력 1). S3에서 1이 오면 "1"부터 다시(S1), 0이 오면 "10"까지 맞은 셈이므로 S2로 간다. 이 겹침 처리가 검출기 설계의 핵심이다.

② 상태표와 ③ 인코딩. 상태도를 표로 옮기고, 각 상태에 2비트 코드를 준다. 여기서는 가장 단순한 이진 인코딩 S0=00, S1=01, S2=10, S3=11을 쓴다.

④ 다음 상태 식. 표의 \(q_0^{+}\) 열을 보면 x 열과 똑같다. \(q_1^{+}\)은 세 행에서 1이고, 카르노 맵(2장)으로 묶으면 두 항이 된다. 출력은 상태가 S3일 때만 1이다.

⑤ 게이트. 식을 그대로 게이트로 옮기면 아래 회로가 된다. 선을 일일이 그리는 대신 같은 이름의 핀은 연결된 것으로 보고, 각 핀 이름의 색으로 지금 그 선의 논리값(1 0)을 표시했다.

무어 기계와 밀리 기계

출력을 상태만으로 정하면 무어 기계(Moore machine), 상태와 현재 입력으로 정하면 밀리 기계(Mealy machine)다. 같은 "101" 검출기를 밀리로 만들면 S3가 필요 없다. S2("10"까지 맞춤)에 있는데 입력이 1이면 그 자리에서 출력 1을 내면 되기 때문이다. 상태도에서 무어는 출력을 상태 동그라미 안에, 밀리는 화살표에 "입력/출력"으로 적는다.

FSM 놀이터

이제 여러 FSM을 직접 돌려 보자. 프리셋을 고른 뒤 입력 버튼으로 이번 주기의 입력을 정하고 "클럭 ↑"을 누르면 상태가 한 칸 움직인다. 지금 상태는 진하게, 방금 지난 전이는 굵은 화살표로 보인다. 아래쪽 파형에는 지난 클럭들의 입력·상태·레지스터 비트·출력이 쌓인다. 편집 줄에서 전이 하나를 바꿔 나만의 기계를 만들어 볼 수도 있다.

프리셋마다 생각해 볼 거리가 있다. 자판기는 무어 기계라 "배출" 상태에 한 클럭 머문 뒤 다음 동전을 받는다. 밀리로 만들면 상태가 줄지만 출력이 동전 입력 신호의 잡음에 노출된다. 신호등은 입력(차량 감지)을 보는 상태와 무조건 넘어가는 상태(황색)가 섞여 있다. 실제 신호등이라면 황색 상태에 머무는 시간을 세는 타이머 카운터가 하나 더 붙는다. 큰 FSM은 이렇게 작은 FSM(카운터)과 짝을 이루는 경우가 많다. 홀짝 검사기는 상태 2개, 플립플롭 하나, XOR 하나짜리 가장 작은 쓸모 있는 FSM이다.

상태 인코딩: 이진 · 원핫 · 그레이

상태도에는 이름만 있고 비트가 없다. 상태 \(N\)개에 어떤 코드를 줄지가 상태 인코딩(State encoding / assignment)이고, 이 선택이 플립플롭 수와 다음 상태 논리의 크기, 속도, 전력을 함께 바꾼다.

• 이진(Binary): 상태 번호를 그대로 2진수로. 플립플롭이 \(\lceil\log_2 N\rceil\)개로 가장 적다. 대신 다음 상태 식이 모든 상태 비트를 봐야 해서 식이 크고 깊어지기 쉽다.
• 원핫(One-hot): 상태마다 플립플롭 하나, 늘 정확히 하나만 1. 플립플롭이 \(N\)개로 많지만, "지금 S2인가?"가 플립플롭 하나를 보면 끝나므로 다음 상태 식이 "들어오는 화살표의 OR"로 짧고 얕다.
• 그레이(Gray): 이웃한 번호끼리 한 비트만 다른 코드. 상태가 주로 순서대로 흘러가는 기계(카운터, 순차 제어)에서 전이마다 한 비트만 바뀌어 스위칭 전력이 줄고, 비동기로 읽어도 중간값이 튀지 않는다. 클럭 도메인을 건너는 FIFO 포인터가 대표적인 예다(10장).

결과는 생각보다 미묘하다. 상태가 2~4개인 작은 기계에서는 이진(또는 그레이)이 플립플롭도 리터럴도 적다. 원핫은 식의 개수가 상태 수만큼 늘어 리터럴 합계가 커진다. 그런데 원핫 식 하나의 크기는 그 상태로 들어오는 화살표 수에만 달려 있고 상태 수 \(N\)과 무관하다. 모듈로-8 카운터를 보면 이진 식은 상태 비트 셋과 입력을 모두 보지만(팬인 4), 원핫 식은 "이전 상태 비트 · en + 지금 상태 비트 · en′" 꼴로 늘 변수 셋이다. 상태가 수십 개로 늘면 이진의 다음 상태 식은 \(\log_2 N\)개 상태 비트와 입력을 모두 엮은 깊은 논리가 되고, 원핫은 여전히 얕다.

이것이 FPGA에서 원핫을 선호하는 이유다. FPGA의 논리 칸은 "4~6입력 LUT 하나 + 플립플롭 하나"로 짝지어져 있어 플립플롭은 사실상 공짜이고, 비용은 LUT 개수보다 LUT를 몇 단 거치느냐(속도)로 정해지는 경우가 많다. 팬인이 LUT 입력 수 안에 들면 식 하나가 LUT 한 단으로 끝난다. 덤으로 출력 해독도 "q_S3 하나 보기"로 끝난다. 반대로 ASIC에서는 플립플롭이 NAND2 대여섯 개 면적이고 클럭 전력도 먹으므로, 상태가 많으면 이진(또는 그 변형)이 유리한 경우가 많다.

상태 최소화와 불법 상태 복구

요구 사항을 따라 상태도를 그리다 보면 하는 일이 똑같은 상태가 둘 생기기 쉽다. 두 상태가 모든 입력 열에 대해 같은 출력 열을 낸다면 바깥에서는 구별할 수 없으므로 하나로 합쳐도 된다. 이런 상태를 동치 상태(Equivalent states)라 한다. 찾는 방법은 분할 정제(Partition refinement)다. 처음에는 출력이 같은 상태끼리 한 묶음으로 두고, 같은 묶음 안에서 어떤 입력에 대해 "다음 상태가 다른 묶음으로 가는" 상태를 떼어 낸다. 더는 쪼개지지 않을 때 남은 묶음 하나하나가 최소 기계의 상태가 된다.

상태를 합치면 플립플롭이 줄 수도 있고(6개 → 3개면 3비트 → 2비트), 줄지 않더라도 다음 상태 논리가 단순해진다. 다만 상태 수가 \(\lceil\log_2 N\rceil\)의 경계를 넘지 않으면 플립플롭 수는 그대로라는 점도 기억하자.

상태를 \(k\)비트로 인코딩하면 \(2^k\)개 코드 중 \(N\)개만 쓰이고 나머지는 불법 상태(Illegal / unreachable state)다. 정상 동작에서는 절대 들어가지 않지만, 전원 투입 직후의 무작위 초기값, 우주선·알파 입자가 일으키는 소프트 에러(16장), setup 위반으로 생긴 준안정이 레지스터를 불법 코드에 떨어뜨릴 수 있다. 그때 기계가 스스로 빠져나오지 못하면 시스템이 멈춘다.

• 리셋은 반드시: 모든 상태 레지스터에 리셋을 달아 알려진 상태(보통 IDLE)에서 출발한다. 비동기 리셋은 클럭 없이도 즉시 걸리지만, 풀릴 때는 클럭에 동기화해서 풀어야 플립플롭마다 다른 클럭에서 출발하는 사고를 막는다(리셋 동기화기).
• default 가지: Verilog의 case에 default: next = IDLE;를 두면 쓰지 않는 코드에서 IDLE로 돌아오는 논리가 생긴다. 단, 합성 도구가 "도달 불가능"을 이유로 이 논리를 지울 수 있으므로 안전이 중요하면 "safe FSM" 옵션을 켠다.
• 원핫의 함정: 원핫은 불법 코드가 \(2^N - N\)개로 압도적으로 많다. 위 그림처럼 복구 항을 넣거나, "1의 개수가 1이 아니면 리셋"하는 검사기를 단다. 우주·차량용 칩은 상태 레지스터를 세 벌 두고 다수결로 고치는 TMR까지 쓴다.

Verilog로 쓰는 FSM 맛보기

실제 설계에서는 상태도를 손으로 게이트까지 옮기지 않고 하드웨어 기술 언어로 적는다. 합성 도구가 ③~⑤단계(인코딩, 식 최소화, 게이트 매핑)를 대신한다. 코드 구조는 그림 9-1의 세 덩어리를 그대로 따르는 것이 정석이다. 상태 레지스터는 always @(posedge clk) 블록 하나, 다음 상태 논리는 always @(*) 조합 블록 하나, 출력 논리는 assign이나 또 하나의 조합 블록이다. 자세한 코딩 패턴과 합성 과정은 17장에서 다룬다.

module det101 (
  input  wire clk, rst_n, x,
  output wire y,       // 무어 출력
  output wire z        // 밀리 출력 (비교용)
);
  // 상태 이름. 숫자에 의미를 싣지 않는다 → 도구가 인코딩을 바꿔도 안전
  localparam [1:0] S0 = 2'b00, S1 = 2'b01, S2 = 2'b10, S3 = 2'b11;
  reg [1:0] state, next;

  // ① 상태 레지스터: 비동기 리셋(풀림은 바깥의 리셋 동기화기가 맞춘다)
  always @(posedge clk or negedge rst_n)
    if (!rst_n) state <= S0;
    else        state <= next;

  // ② 다음 상태 논리: 순수 조합 회로
  always @(*) begin
    next = S0;                  // 기본값: 래치 추론 방지
    case (state)
      S0: next = x ? S1 : S0;
      S1: next = x ? S1 : S2;
      S2: next = x ? S3 : S0;
      S3: next = x ? S1 : S2;   // 겹침 허용: "101" 뒤의 0은 "10"
      default: next = S0;       // 불법 상태 → 복구
    endcase
  end

  // ③ 출력 논리
  assign y = (state == S3);         // 무어: 상태만 본다
  assign z = (state == S2) & x;     // 밀리: 입력도 본다 (S3 없이도 검출)
endmodule

몇 가지 습관이 버그를 크게 줄인다. 상태 레지스터 블록에서만 논블로킹 대입(<=)을 쓰고, 조합 블록은 블로킹 대입(=)과 맨 앞의 기본값으로 시작한다. 기본값을 빼먹고 어떤 가지에서 next를 대입하지 않으면, 합성 도구는 "이전 값을 기억하라"는 뜻으로 읽어 원치 않는 래치를 만든다. 출력도 조합 블록에서 만든다면 같은 규칙을 따른다.