• 作者： 王朝欽; 范揚麟
• 作者服務機構： 中山大學電機工程研究所
• 中文摘要： 如果將狀態指定(state assignment)做適當的安排使得在狀態遞移時狀態位元改變減少，則有限狀態機(FSM)的功率(power)消耗會減少。在這篇論文中，我們提出一個有限狀態機的貪婪式狀態配對成群(Greedy State Pair Grouping)演算法，並且分析此演算法所期望的效率。以狀態遞移機率矩陣和初始輸入訊號來計算狀態的發生機率。貪婪式配對成群演算法則是將各個狀態的終端機率(terminal probability)大小來配對成群在一起，而狀態位元表示的指定則以狀態配對成群的相反順序處理。從系統化的特性而言，貪婪式配對成群對於切換次數減少的期望值預測是相對於傳統的方法而言。因此，在我們的方法裡發現了期望切換次數減少的上界(upper bound)。使用貪婪式配對成群法的結果證明狀態遞移時，狀態位元切換次數減少的比例可以在電路以硬體實現之前被預估出來。
• 英文摘要： The power consumption of a finite state machine (FSM) can be reduced if the count of bit changeactivity during the state transition is decreased by appropriate arrangement of the states. In this work,we propose a greedy pair grouping of states for FSM and analyze the expected performance of this algorithm.The probability that a state will appear is computed by using the state transition probability matrix andthe initial input signal. A greedy pairwise grouping algorithm is then presented in which the states arepairwisely grouped together by the magnitude of their individual terminal probability. The bit representationof the state assignment is carried out in the reversed order of the sequence of the grouping. The systematiccharacteristics of the greedy grouping results in transition reduction compared to the classical method.Furthermore, an upper bound of the expected reduction ratio of our method is discovered. Results usingthis greedy pairwise state grouping method show that the performance of the reduction of transition activitycan be pre-estimated before circuits are implemented in hardware.
• 中文關鍵字： state assignment; greedy pair grouping; power estimation; transition density
• 英文關鍵字： --