Abstract
狀態編碼可視為一種對應過程––把有限狀態機(finite state machine)內的狀態對應到超立方體(hypercube) 上的節點，使得每個節點擁有相異的二位元碼(binary c-ode)。這篇論文提出一個分兩階段的編碼方式，它是植基於最大邊重配對法(maximum qdgeweight matching)。第一個步驟是建立一個帶有邊重的完全圖形(complete graph)；圖形上的每個節點代表一個狀態，每個邊上的計重是代表當邊上的兩個狀態被編成具有相互毗鄰的二位元碼時，在邏輯最小化(logic minimization)後所能獲得的利益，換句話說，所能減少的面積。接下來藉著最大邊重配對法，所有節點被兩兩配對，然後每一組配對的節點被收縮成一個新的節點，同時每一組狀態按照其出現於狀態轉換表(state transition table)中的次數高低，分別編上 0和 1碼。將圖形重覆的收縮直到節點數目變成二 (每次的收縮過程會將被配對的節點合併成一個新的節點，所以圖形的節點數目會減半，圖形上所含有的資料也須重新計算) 。假設這些狀態是以 n個二位元進行編碼。則在第一次收縮時被合併的兩個狀態，將會有相同的前n-1 個二位元碼；在第二次收縮時被合併的兩個節點所代表的四個狀態，將會有相同的前n-2 個二位元碼，依此類推。這種方法不僅符合編碼的基本要求，同時還能儘可能地滿足兩個估算邏輯電路大小的目標函數：讓所有相鄰狀態碼的邊重總和變大，讓出現次數高的狀態含有較多的0 碼。這種編碼法的優越性可由實驗結果獲得證明。