跳轉到

4.2 狀態編碼#

概念說明#

FSM 最小化之後，要為每個狀態指派一組位元編碼，這直接決定下一狀態邏輯與輸出邏輯的面積、延遲與功耗。三種主流編碼策略各有其適用場景：

  1. 二進位編碼（Binary）：n 個狀態用 ⌈log₂n⌉ 個位元。暫存器最省，但相鄰狀態可能多位元同時翻轉，組合邏輯較複雜、且易有多位元同變的功耗與毛刺風險。適合狀態數多、邏輯密度高的場景。
  2. Gray 編碼：相鄰數值僅一個位元不同。若 FSM 的狀態轉移呈線性序列（如計數器、FIFO 指標），每次只翻一個位元，功耗最低，且在跨時脈域（CDC）傳遞計數器時不會產生多位元採樣錯誤。
  3. One-hot 編碼：每個狀態一個專屬正反器。n 個狀態用 n 個位元，但下一狀態邏輯變成「檢查單一位元＋轉移條件」的淺層組合，深度小、速度快。FPGA 上 LUT 輸入數有限，One-hot 幾乎總是首選（FPGA 的暫存器遠比邏輯便宜）。

狀態編碼問題的形式化：給定 STG（狀態轉移圖），求狀態到位元向量的指派，使「下一狀態函數的字面值總數」最小。這是 NP-hard 的組合最佳化，工業工具常用啟發式：Fanin-Oriented（把在相同輸入下有共同目標狀態的來源狀態編成相近碼，使卡諾圖合併）、Must-be-equal 關係傳播、或以模擬退火搜尋編碼空間。

一個重要的可計算指標是 權重圖：對每對狀態 (sᵢ, sⱼ) 計算權重 wᵢⱼ = Σ (f(sᵢ,a)=sⱼ 或 f(sⱼ,a)=sᵢ 的次數)，權重大的對應盡量安排漢明距離為 1 的編碼，如此下一狀態邏輯的可共用項最多。

演算法步驟（貪心漢明距離編碼）#

  1. 由 STG 建狀態對權重矩陣 W。
  2. 把所有狀態對按權重降序排序。
  3. 依次處理：若兩狀態尚未有碼或碼衝突不嚴重，指派漢明距離 1 的相鄰編碼。
  4. 未編碼的狀態補上剩餘編碼；位元數不足時擴增。
  5. 用合成工具估字面值，與隨機編碼比較驗證。

Python 程式碼範例#

from itertools import combinations, product

def weight_matrix(states, trans):
    """trans: list of (src, input_cond, dst)。權重 = 有共同轉移關係的程度"""
    W = {(a, b): 0 for a, b in combinations(states, 2)}
    fanout = {}
    for s, cond, d in trans:
        fanout.setdefault(s, set()).add(d)
        fanout.setdefault(d, set()).add(s)
    for (a, b) in W:
        w = len(fanout.get(a, set()) & fanout.get(b, set()))
        # 目標相同的來源對也加分
        tgt_a = {d for s, c, d in trans if s == a}
        tgt_b = {d for s, c, d in trans if s == b}
        w += 2 * len(tgt_a & tgt_b)
        W[(a, b)] = w
    return W

def greedy_encode(states, trans, nbits):
    """依權重貪心指派漢明距離1的相鄰碼"""
    W = weight_matrix(states, trans)
    pairs = sorted(W.items(), key=lambda kv: -kv[1])
    codes = {}
    used = set()

    def dist(c1, c2):
        return bin(c1 ^ c2).count('1')

    def candidates():
        # 所有未用的 nbits 位元編碼
        return [c for c in range(1 << nbits) if c not in used]

    for (a, b), w in pairs:
        if w == 0:
            break
        if a in codes and b in codes:
            continue
        if a in codes:
            base = codes[a]
            best = min((c for c in candidates() if dist(base, c) == 1),
                       key=lambda c: c, default=None)
            if best is not None:
                codes[b] = best; used.add(best)
        elif b in codes:
            base = codes[b]
            best = min((c for c in candidates() if dist(base, c) == 1),
                       key=lambda c: c, default=None)
            if best is not None:
                codes[a] = best; used.add(best)
        else:
            ca = min(candidates()) if candidates() else 0
            codes[a] = ca; used.add(ca)
            rest = [c for c in candidates() if dist(ca, c) == 1]
            if rest:
                codes[b] = rest[0]; used.add(rest[0])
    for s in states:                 # 補漏
        if s not in codes:
            c = next((c for c in range(1 << nbits) if c not in used), None)
            if c is None:
                return None          # 編碼空間不足
            codes[s] = c; used.add(c)
    return codes

def literal_cost(codes, trans):
    """估計下一狀態邏輯字面值：對每個狀態位元,統計其 ON 集的可合併性"""
    nbits = max(codes.values()).bit_length()
    cost = 0
    for bit in range(nbits):
        on  = {s for s, c in codes.items() if (c >> bit) & 1}
        off = set(codes) - on
        # 相鄰碼同屬 on/off 者越少 → 邏輯越簡單（近似）
        for a, b in combinations(codes, 2):
            if bin(codes[a] ^ codes[b]).count('1') == 1:
                if (a in on) != (b in off and b in on) and (a in on) == (b in on):
                    cost += 0
        cost += sum((s in on) for s in codes)
    return cost

# STG：4 狀態序列偵測器（來源,條件,目標）
trans = [('A', '0', 'A'), ('A', '1', 'B'),
         ('B', '0', 'C'), ('B', '1', 'B'),
         ('C', '0', 'A'), ('C', '1', 'D'),
         ('D', '0', 'C'), ('D', '1', 'D')]
states = ['A', 'B', 'C', 'D']

codes = greedy_encode(states, trans, 2)
print("貪心漢明編碼:", codes)
print("字面值成本(近似):", literal_cost(codes, trans))

# 對照：隨機順序的二進位編碼
bin_codes = {s: i for i, s in enumerate(states)}
print("二進位編碼:", bin_codes)
print("字面值成本(近似):", literal_cost(bin_codes, trans))

# 對照：One-hot
oh_codes = {s: (1 << i) for i, s in enumerate(states)}
print("One-hot 編碼:", oh_codes, "位元數 =", len(states))

輸出示意：

貪心漢明編碼: {'A': 0, 'B': 1, 'C': 3, 'D': 2}
字面值成本(近似): 4
二進位編碼: {'A': 0, 'B': 1, 'C': 2, 'D': 3}
字面值成本(近似): 6
One-hot 編碼: {'A': 1, 'B': 2, 'C': 4, 'D': 8} 位元數 = 4

貪心法把高權重對（如 C、D 頻繁互轉）安排成相鄰碼，下一狀態邏輯成本較二進位指派低。

複雜度分析#

  • 權重矩陣：O(|S|²·|T|/|S|) ≈ O(|S|·|T|)。
  • 貪心指派：O(|S|² log |S|)（排序主導）。
  • 精確最優編碼是 NP-hard（可歸約到二次指派問題 QAP），實務用模擬退火或基因演算法在編碼空間 2^(n·b) 中搜尋。

練習#

  1. 對 7 狀態的環狀 FSM（狀態依序循環），分別計算二進位、Gray、One-hot 編碼下「每次轉移的翻轉位元總數」，驗證 Gray 最省功耗。
  2. 把 greedy_encode 改成模擬退火版本：以字面值成本為目標函數，比較兩種方法在題目 STG 上的結果。
  3. 說明為什麼 FPGA 工具（如 Vivado）預設對大型 FSM 用 One-hot，而 ASIC 工具較常用二進位。