Abstract
測試一個Finite State Machine (FSM) 已經被證明是一個很難的問題?Hen 64][ic83] 。傳統使用的測試方法是設計一個checking experiment [Hen 64]。但此方法會產生太長的test sequence,并不實用。另一個廣為使用的方法是complete scan logic [Agr 84]。此方法將所有的memouy elements 串連起來，使得它們變成可以控制和觀察。這個方法成功的將測試循序電路問題轉換為較簡單的測試組合電路問題，但是它所造成的額外面積有時是難以忍受的。如何在不使用scan logic的情況下有效的測試循序電路是一個有趣的問題。一種方法是改進目前測試循序電路的演算法。最近的研究則是趨向另一種完全不同的方法，稱為synthesis for testability。Agrawal 和cheng [Agr 90 ]在 1990年提出一種可以實現Syhtheses for testablity的方法.他們將使用者給定的object machine 和一個設計好的test machine 合併 ，使最後得到的電路能執行兩者的功能而變得較為好測。一般來說，合併兩個圖形是很難的問題。在本論文中，我們只開心兩個state transition graph (STG)的合併問題。而且其中之一是經過特殊設計的test function。在本論文中，我們為了降低問題的難度而對Agrawal 所提出的test machine作了一些觀察并整理出四個特性。根據這些特性，我們提出一個圖形合併演算法。如果有需要的話，此演算法在合併的過程中會自動增加一個imput pin 以保證合併的成功。經由對MCNC 1989 Logic synthesis Workshop benchmark set的實驗數據可以看出，雖然大部分的合併都必須在增加一個input pin 的情況下才能完成，但我們所提出的演算法的確能夠快速完成上述的合併工作。