臺灣博碩士論文加值系統

在許多的電腦輔助設計的工具上，訊號傳遞方向(signal flow
direction)已被廣泛地運用來增加這些工具的準確性與效率。因此，發展
一個正確及有效率的系統來獲得此訊號傳遞方向之資訊，將是一件重要且
值得的工作。在本論文中，我們提出了一個整合系統來完成此項工作，此
一整合系統包含了兩個子系統，分別為：結構式子系統(structure-
based subsystem)與規則式子系統(rule-based subsystem)。在結構式子
系統中，我們將訊號傳遞方向指派之問題轉換到一個雙路徑問題(two-
paths problem)，並為此方法，亦將原本的電路轉換為一個所謂的GST-
graph的圖形上來解決，且利用圖形理論中之一線性演算法將此GST-graph
分解為分離元件(split components)，且我們亦已發展出另一個線性演算
法來決定分離元件中大部分之訊號傳遞方向。當電路中所有的電晶體都是
單向時，則此電路之所有電晶體訊號傳遞方向將可在此子系統中完全被解
決。然而，對於無法在結構式子系統中被決定方向的電晶體，將在規則式
子系統中重新考慮處理。在規則式子系統中，主要是提出一組基於邏輯原
理的規則來決定電晶體訊號傳遞方向。對於以往一些較為困難的電路，如
桶狀移位器(barrel shifter)，已可利用我們新提出的邏輯推演的規則予
以解決。最後，實驗結果亦證實此整合系統的正確性與效率。

In many CAD tools, signal flow direction information has been
used to improve their accuracy and performance. Hence deriving
this information correctly and efficiently is an important and
rewarding task. In this thesis an integrated system for
deriving signal flow direction information is presented. This
system consists of two subsystems: structure-based and rule-
based. In the structure-based subsystem, a new graph-theoretic
algorithm is developed. The direction assignment problem is
modeled as a two-paths problem on an undirected graph called
GST-graph. The GST-graph is decomposed into split components by
a linear algorithm and the direction information of most edges
in each split component can be derived by another linear
algorithm. If all transistors in a circuit are unidirectional
then all of them will be determined in this system. For those
transistors that cannot be determined by this subsystem, if
any, they will be dealt with in the rule-based subsystem. A new
set of rules including a logic implication rule have been
implemented. By considering the circuit semantics, some
difficult circuit such as a barrel shifter can be solved.
Experimental results show that accuracy and efficiency of this
integrated system.