隨著製程技術的進步，晶片上單位面積內可容許的電晶體數量也大幅提升，使得測試階段必需花費更大量的時間和成本去驗證電路的正確性，常見的測試方法中主要分二類，一類為外部測試( external testing )，如自動測試機台( Automatic Test Equipments，ATE )可以快速的自行產生測試式樣( Test pattern )且驗證，但是需要較高的硬體成本，第二類為內建自我測試( Build-In-Self-Test，BIST )，相較於外部測試，它不需要花費大量的硬體成本及可達到測試的目的。
線性反饋位移暫存( Linear Feedback Shift Registers，LFSR )是用來產生近隨機測試式樣( pseudo-random test pattern )，可以使 BIST 能以較低的硬體實現測試驗證。然而傳統的LFSR在做電路測試上還是沒有比較好的錯誤覆蓋率( fault coverage )，而且缺乏系統化設計產生測試式樣電路的方法，因此本論文擬提出一個新的線性反饋雙向移位暫存器( Bidirectional shift register )架構及系統化設計方法，從已知的測試式樣中分析且有系統化的設計出一個找出測試式樣序列的方法，可達到高錯誤覆蓋率，和找到最短的測試式樣序列以減少測試時間，而每一次位移都只有一個位元0或1的變化，進而能降低測試功率的消耗。
我們將CAD96[12]所提供的測試檔案進行測試且分析其結果，藉由分析單向位移和雙向位移的差異，我們可發現雙向所找到測試式樣序列比單向尋找的還要來的短，雖然所需要的邏輯閘數量比較多，可是能縮短測試的時間。

With the progress of IC manufacturing, the number of transistors on the chip is increased. Thereby, the IC designer will spend more time to verify the correctness of chip. There are two main ways for IC testing. The first one is external testing such as Automatic Test Equipments (ATE). It can auto generate the test pattern and have better fault coverage. However, the ATE is very expensive. The second method is Build-In-Self-Test (BIST). Different from ATE, the BIST can accomplish the testing without spending too much hardware overhead.
Linear Feedback Shift Registers (LFSR) is widely adopted as the pseudo-random test pattern generator for BIST, due to its low hardware overhead. However, there are many faults are hardly detected by the traditional LFSR. To achieve the better fault coverage and testing cycle, we want to propose a new test pattern generation LFSR architecture by using bidirectional shifter register.
By analyzing target test vectors, we can systematically design a test pattern generator which has better fault coverage and shortest generation sequence. Because each shifting only cost one bit change, we can also reduce the power consumption.
Our benchmark is provided by CAD96 [12]. By comparing the difference between one-way and two-way test pattern generator, we can observe that the generation sequence length of two-way test pattern generator is shorter than one way. Although the two-way test pattern generator expenses more gates to design the circuit, we can come to better testing time.

中文摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VI
表目錄 VIII

目錄
第一章 、前言 1
第二章 、相關研究背景介紹 3
2.1線性反饋位移暫存器 3
2.2 相關研究 5
第三章 、研究動機與問題定義 9
3.1 研究動機 9
3.2 問題定義 9
3.2.1 距離計算 12
3.2.2 距離簡化 14
第四章 、演算法與程式流程 15
4. 1 程式概要 15
4. 2 雙向線性反饋移位暫存器產生測試式樣演算法 17
4.2.1 Shift right 17
4.2.2 Shift lift 22
4.2.3 Bidirectional shift 25
第五章 、實驗結果 28
5.1 實驗平台 28
5.2 實驗數據 28
5.3 實驗結果 29
第六章 、結論與未來方向 33
參考文獻 33
作者簡介 35

圖目錄
圖 1-1：摩爾定律 1
圖 1-2：加入BIST的測試結構[12] 2
圖 1-3：X4＋X3＋1 的 LFSR 邏輯表示圖 2
圖 2-1：Type-I LFSR 3
圖 2-2：Type-II LFSR 3
圖 2-3：特徵多項式的通式與通試圖。 3
圖 2-4：4-bit的基本特徵多項式。 4
圖 2-5：4-Bit的雙向位移暫存器 4
圖 2-6：Type-I LFSR與Dual LFSR[1] 5
圖 2-7：LHCA 範例[2] 6
圖 2-8：LFSR用於CUT例子，和 XOR network[4] 8
圖 3-1：de Bruijn 圖 11
圖 3-2：The proposed LFSR architecture. 12
圖 3-3：兩測試式樣之間距離與計算方法 13
圖 3-4：兩點間之距離的取捨 14
圖 4-1：程式的流程圖 15
圖 4-2：所有測試的測試式樣 17
圖 4-3：兩測試式樣之間距離與計算方法 18
圖 4-4：以右移連接所有測試式樣 19
圖 4-5：以右移所有測試式樣之間的距離 19
圖 4-6：兩點間之距離的取捨 20
圖 4-7：去較長路徑後之間的距離 20
圖 4-8：以右移找到minimum weighted Hamiltonian path 21
圖 4-9：以右移找出最短的路徑與真值表 21
圖 4-10：建構BIST電路 22
圖 4-11：以左移所有測試式樣之間的距離與簡化 23
圖 4-12：以左移找到minimum weighted Hamiltonian path與真值表 24
圖 4-13：雙向找minimum weighted Hamiltonian path 25
圖 4-14：以雙向找出最短的路徑與真值表 26
圖 4-15：建構BIST電路 26
圖 5-1：單向範例 29
圖 5-2：單向與雙向測試式樣序列，建構BIST電路 30

表目錄
表 5-1：測試平台與環境 28
表 5-2：測試數據資訊 28
表 5 3：單向與雙向測試式樣比較 29
表 5 4：單向與雙向測試式樣使用邏輯閘比較 30

[1]J. Rajski, N. Tamarapalli and J. Tyszer, “Automated synthesis of phase shifters for built-in self-test applications” , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.19, Issue 10, pp.1175-1188, Oct. 2000.
[2]G. Mrugalski, J. Rajski, and J. Tyszer, “Cellular automata-based test pattern generators with phase shifters” , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.19, Issue 8, pp.878-893, Aug. 2000.
[3]L.J. Lipska and J. Sastoriza, “Boolean feedback functions for full-length nonlinear shift registers” , Journal of Telecommuncations and Informatiom, pp.28-30, Apr. 2004.
[4]T. Moriyasu and S. Ohtake, “A Method of LFSR Seed Generation for Scan-Based BIST Using Constrained ATPG” , Proceedings of Complex, Intelligent, and Software Intensive Systems, Jul. 2013.
[5]N. C. Lai and S. J. Wang “A reseeding technique for LFSR-based BIST application” , Proceedings of the 11th Asian Test Symposium, pp. 200-205, Nov. 2002.
[6]B. Koenemann, “LFSR-coded test patterns for scan designs” , Proceedings of European Test Conference , pp.237-242, 1991.
[7]S. Hellebrand, S. Tarnick, J. Rajski, and B. Courtois, “Generation of Vector Patterns Through Reseeding of Multiple-Polynomial Linear Feedback Shift Registers” , Proceedings of IEEE International Test Conference , pp.120-129, 1992.
[8]W. C. Lien, K. J. Lee, T. Y. Hsieh and K. Chakrabarty, “A New LFSR Reseeding Scheme via Internal Response Feedback”, Proceedings of Asian Test Symposium, 2013.
[9]S. Hellebrand, J. Rajski, S. Tarnick, S. Venkataraman and B. Courtois, “Built-in test for circuits with scan based on reseeding of multiple-polynomial linear feedback shift registers”, IEEE Transactions on Computer, Vol. 44, Issue. 2, pp. 223-233, Feb. 1995.
[10]W. C. Lien, T. Y. Hsieh and K. J. Lee, “A Test-Per-Clock LFSR Reseeding Algorithm for Concurrent Reduction on Test Sequence Length and Test Data Volume”, Proceedings of Asia Test Symposium , pp.278-283, 2012.
[11]E. Kalligeros, X. Kavousianos, D. Bakalis and D. Nikolos, “An efficient seeds selection method for LFSR-based test-per-clock BIST”, Proceedings of International Symposium on Quality Electronic Design, pp. 261-266, 2002.
[12]http://cad_contest.cs.nctu.edu.tw/cad11/Problems/96/index.htm
[13]http://www.eecs.berkeley.edu/~alanmi/abc/
[14]M. M. Mano, Digital design. 2001.
[15]D. B. West, Introduction to Graph Theory. 1996.