Abstract
通訊協定的設計,實現和使用已經越來越普遍.通訊協定的實現所需要的步驟大致上有:規格書的閱讀,將要實現的部份詳細描述,驗證描述有無矛盾或漏洞,程式碼的撰寫,程式碼與規格的一致性測試製作成產品等步驟.當我們在測試一系統之正確性時, 其測試成本的考量, 是相當重要的. 減少測試序列的長度及重新啟動系統的次數, 是最有效的方法, 先前有許多相關的論文, 其理論基礎都是UIO/RCP (UIO: UniqueInput Outputsequence, RCP: Rural Chinese Postman problem), 這些論文確實都有減少測試序列的長度及重新啟動系統的次數, 但是卻都沒有保證其偵錯之能力.而有另一些理論基礎為錯誤模型 (Fault Model)的論文, 其有保證其有單錯偵測能力, 但其重新啟動系統之次數又過多. 在測試超大型積體電路時, 因其製作過程皆為電腦自動化, 所以如一測試序列擁有單錯偵測之能力時, 其已相當足夠. 有介於以上幾點, 所以本篇論文將提出一擁有單錯偵測能力序列之生成演算法, 並且減少重新啟動系統的次數, 甚至在測試過程中沒有重新啟動該系統. 在本篇論文中, 我們首先介紹一些相關的基本理論, 如圖形理論, 有限機理論, 及有限機可能發生錯誤的種類.錯誤的種類有下列四種:1.輸出錯誤. 2.輸入錯誤. 3.目的節點錯誤. 4.起始節點錯誤. 本篇論文所論述之演算法, 引用UIO 及RCP 等相關理論,並且主要針對第三種錯誤來生成其測試序列, 而且會證明此測試序列, 可以偵測出其他三種錯誤. 在本篇之第四章, 並有針對MCNC之有限機基準,所作之實驗, 並與其他相關論文之比較, 藉以佐證本篇論文之優點.