本論文是關於HDL-based有限狀態機內建自我測試電路之設計與驗證，相關研究工作包含下列四大部分：
第一部份介紹有限狀態機電路的測試方式，包含傳統測試方法、使用LSSD之可測性設計以及內建自我測試電路。
第二部份為探討HDL-based有限狀態機內建自我測試電路之結構設計與實現，在分析待測電路及故障偵測電路後，發展出一個HDL-based有限狀態機內建自我測試電路系統。
第三部份為研究HDL-based有限狀態機內建自我測試電路之故障植入方法，講述如何在HDL-based有限狀態機之behavioral model中植入故障點，並設計其相關硬體，以Altera FPGA開發板實現之。
第四部份是設計與實現一驗證系統來計算內建自我測試電路之故障涵蓋率，其由軟、韌、硬體所整合而成，整個流程包含撰寫Nios- II相關軟韌體與使用Nios-II IDE來驗證其功能。
整體而言，本論文係以研究與設計HDL-based有限狀態機內建自我測試電路為目標，並研究如何在behavioral level植入故障以計算其故障涵蓋率。

This thesis is related to the design and verification of BIST (Built-In Self-Test) circuits for HDL-based FSMs (Finite State Machines). The related research work consists of the following four parts:
The first part is to introduce the test methods for FSM circuits, such as the traditional methods, the LSSD-based testable design methods, and the BIST-based methods.
The second part is to explore the architecture design and implementation of the BIST circuits for HDL-based FSMs. After analyzing both the circuit under test and the fault detection circuit a BIST-based system for the HDL-based FSM circuit has been developed.
The third part is to study the fault injection methods for the BIST circuits of HDL-based FSMs and to describe how to inject faults into HDL-based FSM circuits at the behavioral level. Meanwhile, the related hardware are designed and implemented on an Altera FPGA development board.
The fourth part is about the design and implementation of a verification system for computing the fault coverage of BIST circuits. This system is an integration of software, firmware, and hardware. The whole design process consists of work, such as writing Nios-II-related firmware and using the Nios-II IDE (Integrated Development Environment) to verify the function of the system.
On the whole, the goal of this thesis is to do the researches on designing the BIST circuits for HDL-based FSMs and to study how to inject faults at the behavioral level for computing the fault coverage.

第一章 緒論 ........................................................................................... 1
1 .2研究內容相關架構 .................................................................... 3
1.3論文組織及概觀 ......................................................................... 4
第二章 有限狀態機內建自我測試電路驗證系統之發展環境與流程
................................................................................................................... 5
2.1 SOPC-based軟/硬體整合設計簡介 .......................................... 5
2.2 Altera SOPC-based軟體發展環境 ............................................. 7
2.3 Altera SOPC-based硬體發展環境 ............................................. 8
2.3.1 NIOS II嵌入式系統 ......................................................... 8
2.3.1.1 NIOS II處理器架構[2] ........................................... 9
2.3.1.2 Avalon Bus架構[3] ................................................ 10
2.3.2 Quartus II SOPC發展系統 ............................................. 12
2.3.3 Altera Stratix II FPGA開發板 ........................................ 14
2.4有限狀態機內建自我測試電路架構與開發流程 ................... 15
2.4.1有限狀態機內建自我測試電路架構介紹 …................. 15
2.4.2有限狀態機內建自我測試電路開發流程 ..................... 16
第三章 有限狀態機電路之測試方法 ................................................. 18
3.1 有限狀態機電路之傳統測試方法 ......................................... 18
3.2 可測性設計（Design for Testability）..................................... 20
3.2.1 LSSD方法[6] .................................................................. 22
3.3 內建自我測試電路 ................................................................. 24
3.3.1 測試向量產生器（Test Vector Generator） .................... 26
3.3.2 簽章產生器（Signature Generator） ............................... 26
3.3.2.1 線性回授移位暫存器（LFSR）[6][8]..................... 27
3.3.2.2多輸入簽章暫存器（MISR）[6][8].......................... 28
3.4 有限狀態機電路之故障模式 ................................................. 29
3.4.1 Gate-level故障 ............................................................... 29
3.4.2 Wire-level 故障 ............................................................. 29
3.4.3 Flip-flop 故障 ................................................................ 30
3.5 有限狀態機電路之故障涵蓋率 ............................................. 31
3.5.1 故障植入（Fault Injection）.............................................. 32
3.5.2 故障涵蓋率（Fault Coverage）....................................... 33
第四章 HDL-based有限狀態機內建自我測試電路之設計與實現
................................................................................................................. 34
4.1 HDL-based 有限狀態機內建自我測試電路之架構 .............. 34
4.1.1 單一有限狀態機內建自我測試電路之架構 ............... 34
4.1.2 多重有限狀態機內建自我測試電路之架構 ............... 36
4.2 HDL-based有限狀態機內建自我測試電路之設計 ............... 38
4.2.1 單一有限狀態機內建自我測試電路之設計 ............... 38
4.2.2 多重有限狀態機內建自我測試電路之設計 ............... 40
4.3 HDL-based 有限狀態機內建自我測試電路之韌體控制 ..... 41
第五章 HDL-based有限狀態機內建自我測試電路故障涵蓋率 ..... 45
5.1 HDL-based有限狀態機電路之邏輯合成................................. 45
5.1.1無輸入有限狀態機電路之邏輯合成 ............................. 46
5.1.2單位元輸入有限狀態機電路之邏輯合成 ..................... 50
5.1.3多位元輸入有限狀態機電路之邏輯合成 ..................... 54
5.2 HDL-based有限狀態機電路故障植入..................................... 57
5.2. 1 有限狀態機外部故障點之故障植入 ........................... 59
5.2.2 有限狀態機內部故障點之故障植入 ........................... 60
5.2.3 真值表表示之有限狀態機內部故障植入 ................... 64
5.2.3.1 內部故障植入規則 .............................................. 71
5.2.3.2 外部故障相關點 .................................................. 73
5.2.3.3 無效之故障點 ..................................................... 73
5.3 HDL-based有限狀態機電路故障涵蓋率之計算 ................... 75
5.3.1 故障涵蓋率計算系統之架構 ....................................... 75
5.3.2故障涵蓋率計算系統之流程 ......................................... 77
第六章 HDL-based有限狀態機內建自我測試電路之模擬與驗證
................................................................................................................. 78
6.1 HDL-based 有限狀態機內建自我測試電路之驗證 .............. 79
6.2故障涵蓋率之計算及驗證 ....................................................... 82
第七章 結論 ......................................................................................... 83
參考文獻 ............................................................................................... 84

[1]Altera Corporation, Quartus II Handbook, 2005.
[2]Altera Corporation, NIOS II Processor Reference Handbook, 2004.
[3]Altera Corporation, Avalon Bus Specification Reference Manual, 2005.
[4]M. B. Lin, Digital System Designs and Practices Using Verilog HDL
and FPGAs, John Wiley & Sons, 2008.
[5]M. D. Ciletti, Advanced Digital Design with the Verilog HDL,
Prentice-Hall, 2003.
[6]L. T. Wang, C. W. Wu, and X. Wen, VLSI Test Principles and Architectures Design for Testability, Elsevier Morgan Kaufmann
Publishers, Boston, 2006.
[7]M. S. Shirazi and S. G. Miremadi, “FPGA-based Fault Injection into synthesizable Verilog HDL models,” The Second International Conference on Secure System Integration and Reliability Improvement, pp. 143-149, Jul. 2008.
[8]V. D. Agrawal, C. R. Kime, and K. K. Saluja, “A Tutorial on Built-In Self-Test, Part 1: Principles,” IEEE DESIGN & TEST OF
COMPUTERS, pp. 73-82, Mar. 1993.
[9]P. Ellervee, J. Raik, K. Tammemae, and R. Ubar, “Enviroment for FPGA-based fault emulation,” Proc. Estonian Acad. Sci. Eng., pp.
323-335, 2006.
[10] A. Miczo, Digital Logic Testing and Simulation, 2nd ed., John Wiley & Sons, 2003.
[11] M.-L. Sheu and C. L. Lee, “Simplifying Sequential Circuit Test
Generation,” IEEE Design & Test of Computers, pp. 28-38, 1994.
[12]高弘穎, 雙埠SRAM內建自我測試演算法驗證系統之設計與實
現, 國立台灣科技大學碩士學位論文, 民國一百零二年.
[13]彭健桓, FPGA-based 邏輯陣列內建自我測試電路驗證系統之設
計與實現, 國立台灣科技大學碩士學位論文, 民國一百零二年.