頁籤選單縮合
題 名 | Graph-Based Method for Computing Interconnect Complexity |
---|---|
作 者 | 楊文霖; | 書刊名 | 國立屏東商專學報 |
卷 期 | 5 1997.05[民86.05] |
頁 次 | 頁189-201 |
分類號 | 319.9 |
關鍵詞 | Finite state machine; FSM; VLSI; Communication complexity; |
語 文 | 英文(English) |
英文摘要 | In an earlier paper we presented a multi-way FSM general decomposition method based on a cost function whose goal is to minimize the interconnect complexity. Unfortunately, the running time to compute the interconnect complexity of a given input partition using this method is Ω (2 �� ), where n is the number of primary inputs. Hence, this approach is practical only for FSMs with a small number of inputs. In this paper, we present a new method for computing the interconnect complexity of a given input partition based on a graph representation we call the transition tree diagram (TTD). The running time of this method takes only O(p �� *q �� *n �� ) bit operations, where p is the number of trees in the TTD representation and q is the largest number of edges owned by any one of the trees. The decomposition procedure based on this new method is several order of magnitude faster than the previous version. |
本系統中英文摘要資訊取自各篇刊載內容。