簡述儲存器測試圖形演算法論文
簡述儲存器測試圖形演算法論文
1 介紹
隨著積體電路製造工藝的不斷進步，半導體晶片的發展趨於高密度、高速度、高複雜度，給測試帶來了極大的挑戰。儲存器是積體電路產品中的一個主要門類，主要用來存放資料、指令、程式等資訊。儲存器的測試一方面可用於判斷產品質量是否合格，另一方面透過測試獲得一些資料用於改進工藝。
目前儲存器的基本測試方法已經比較成熟，主要有儲存器直接存取測試、儲存器的宏測試、儲存器內建自測試三種，各有利弊。儲存器直接存取測試是利用自動測試裝置來進行測試，自動測試裝置的效能和測試成本使得直接存取測試方式對大容量的儲存器並不合適。儲存器的宏測試將儲存器作為一個宏模組，利用電路內部的掃描路徑生成宏模組的測試向量，再透過自動測試裝置在電路外部施加測試向量，對於較大的儲存器，宏測試向量的資料量較大，測試需要較長時間。儲存器內建自測試是在儲存器外圍產生一整套控制電路，實現晶片內建儲存器測試模式的自動產生及測試結果的自動判別，這種方法增加晶片的面積，但是具有自動化程度高、測試質量高、測試成本低、測試時間短等優勢。
對於儲存器來說，最主要的測試是讀寫邏輯功能測試，以檢測儲存單元的故障，包括由於壞的金屬連線、壞的元件、晶片邏輯錯誤等原因引起的功能故障。這些故障通常被簡化為幾個較為成熟的故障模型，透過不同的測試圖形演算法來檢測故障。本文以儲存器的測試圖形為切入點，先簡單介紹儲存器簡化的故障模型，然後介紹常用的儲存器測試圖形演算法以及一些新近提出的改進儲存器測試圖形演算法，對其進行比較，並對將來儲存器測試圖形的發展進行預期。
2 常用的儲存器測試圖形演算法
對於儲存器的功能測試，演算法有很多種，分別針對不同的儲存器故障模型，包括固定故障、轉換故障、耦合故障、圖形敏感故障、定址故障、資料保留故障等。一個高效率的測試演算法，需要用盡可能少的測試圖形和儘可能短的測試時間檢測到儘可能多的故障。從理論上說，存在覆蓋所有故障的測試演算法，但是實際上由於時間複雜度的原因無法實現。假設用N 表示一個儲存器的地址數，那麼測試圖形的複雜度可以用N來表示。
對於較大容量的儲存器來說，N3/2圖形和N2圖形的測試時間在實際測試中是無法承受的。在實際測試中最常用的演算法主要有全“0”/全“1”圖形，奇偶校驗板圖形和齊步“1”/“0”圖形。這三種圖形均為N圖形。
1、全“0”/全“1”圖形
將全部儲存單元按順序寫0、讀0、寫1、讀1，測試圖形序列長度為4 N，可用於檢測儲存器的固定故障。
2、奇偶校驗板圖形
奇偶校驗板圖形也稱棋盤圖形，向儲存單元矩陣寫入的資料圖形是根據儲存單元選址地址碼的奇偶性而定的，如果儲存單元的行地址碼和列地址碼中有偶數個1，其奇偶性為0，則在該儲存單元中寫“0”，反之寫“1”。根據演算法寫入背景圖形，然後逐位讀出並檢測結果的正確性，再以反碼圖形重複上述測試過程，測試圖形序列長度為4 N。奇偶校驗板圖形可用於檢測儲存器的固定故障、地址譯碼故障，以及相鄰位的短路故障。
3、齊步圖形
齊步圖形演算法也稱March演算法，是對儲存器的每個單元依次進行檢驗的一種方法，從第一個儲存單元開始，逐一對每個單元進行取反和檢驗，直到最後一個單元檢測結束才完成一遍掃描。齊步演算法的流程如圖2所示，W0、W1、R0、R1分別表示寫“0”、寫“1”、讀“0”、讀“1”。具體流程為：首先背景圖形寫全“0”，從低地址開始沿增址方向順序讀“0”、寫“1”(R0W1)，一直到最高地址。然後從最高地址開始沿減地址方向順序讀“1”、寫“0”(R1W0)，測試圖形序列長度為5 N。齊步圖形可用於檢測全部的固定故障、地址譯碼故障和轉換故障。
4、其他測試圖形
以上三種測試圖形均為N 型測試圖形，其共同特點是測試時間短，但覆蓋的故障比較有限。相較而言，齊步演算法的效率最高。除此之外，還有很多複雜度更高的圖形，比如乒乓演算法、蝶形演算法等。乒乓演算法的`故障覆蓋率很高，能夠有效地檢測出固定故障、轉換故障、耦合故障和部分圖形敏感故障，其測試圖形序列長度為4 N2+2 N，屬於N2型測試圖形。蝶形演算法同樣具有很高的故障覆蓋率，能夠有效地檢測出固定故障、地址解碼故障和圖形敏感故障，屬於N3/2型測試圖形。
這些高複雜度的測試圖形都具有一個共同的弊端，時間複雜度太高，測試時間過長，雖然在理論中有很高的故障覆蓋率，但在實際生產中很少使用。
因此，在近期關於儲存器測試圖形演算法的研究中，提出了一些改進的N圖形演算法，跟經典的測試演算法相比，在不大量增加測試時間的前提下，能夠有效地提高故障覆蓋率，在下一部分將詳細進行介紹。
3 改進的儲存器測試圖形演算法
目前，國內外經典的March演算法有MATS、MATS+、March A、March B、March C、March C-、March C+、March LR、March SR等。1979年Nairt提出的MATS演算法對固定故障提供了最短的齊步測試;由MATS改進的MATS+演算法能夠檢測地址解碼故障及固定故障;1980年提出的March A、March B演算法可用於測試部分連線故障;1991年，Van de Goor對Match C演算法進行改進，提出了March C-演算法，在獲得同樣的故障覆蓋率的前提下降低了March C 演算法的複雜度;March C+在March C的基礎上增加了3 N 的複雜度，但同時提高了故障覆蓋率。March C演算法及其衍生演算法現成為儲存器測試的主流演算法。本文將介紹三種較為新穎巧妙的改進演算法。
1、棋盤型齊步演算法
這種演算法的基本構想是在齊步演算法中使用棋盤格式，棋盤演算法可以檢測出固定故障和相鄰單元的橋接故障，齊步圖形演算法可以覆蓋全部的固定故障、地址譯碼故障和轉換故障。將兩種演算法相結合，不僅可以實現兩種演算法本來的功能，由於讀寫特殊性，還可以檢測一部分相鄰圖形敏感故障。
(1)所有儲存單元寫0。
(2)讀A0單元(表示地址為0的單元)的“0”，再改寫為“0”;讀A1單元的“0”，再改寫為“1”;讀A2單元的“0”，再改寫為“0”;讀A3單元的“0”，再改寫為“1”…直到An-1。此步執行完後，儲存器被寫為棋盤格式。
(3)讀An-1單元的“l”，再改寫為“0”;讀An-2單元的“0”，再改寫為“l”…直到A0。此步完成後，儲存器被寫為一個與步驟(2)結束後相反的棋盤格式。
經過改進的棋盤格齊步演算法測試圖形序列長度為5 N，跟齊步圖形演算法相比，測試時長沒有增加，而故障覆蓋率明顯提高。
2、基於棋盤演算法的改進
棋盤格圖形演算法中，對於每一個儲存單元來說，只經過了從“0”到“1”的轉換或者從“1”到“0”的轉換，不能覆蓋全部的轉換故障。於是對棋盤演算法進行了巧妙的改進，具體流程如下：
(1)寫入反棋盤格圖形;
(2)寫入棋盤格圖形;
(3)讀棋盤格圖形;
(4)寫入反棋盤格圖形;
(5)讀反棋盤格圖形。
該改進演算法與棋盤格演算法相比，測試圖形序列長度增加了N，能夠檢測出全部的轉換故障、地址解碼故障、固定故障以及相鄰單元的橋接故障，故障覆蓋率有所提高。
3、March SSE演算法
(1)所有儲存單元寫“0”;
(2)從低地址位遞增到高地址位，對每個儲存單元依次進行讀“0”、寫“0”、讀“0”、寫“1”、讀“1”操作;
(3)從低地址位遞增到高地址位，對每個儲存單元依次進行讀“1”、寫“1”、讀“1”、寫“0”、讀“0”操作;
(4)從高地址位遞減到低地址位，對每個儲存單元依次進行讀“0”、寫“0”、讀“0”、寫“1”、讀“1”操作;
(5)從高地址遞位減到低地址位，對每個儲存單元依次進行讀“1”、寫“1”、讀“1”、寫“0”、讀“0”操作;
(6)所有的儲存單元讀“0”。其測試圖形序列長度為22N，透過改進，除了能夠覆蓋固定故障、地址解碼故障等靜態故障意外，還能夠覆蓋全部的動態讀破壞故障、動態讀錯誤故障、動態干擾耦合故障和部分動態偽讀破壞故障、動態偽讀破壞耦合故障。在檢測儲存器動態故障的演算法中，以較低的測試時間複雜度，獲得了較高的故障覆蓋率。
4 儲存器測試圖形演算法的應用
在目前的實際測試生產中，採用的都是儲存器直接存取測試的方法，考慮到裝置能力和測試效率的問題，通常使用的都是經典的O(N)型測試圖形，僅包括全“0”/全“1”測試圖形和奇偶校驗板圖形，對於大容量的儲存器，由於裝置測試圖形儲存容量的限制，僅採用奇偶校驗板圖形進行測試。這兩種演算法時間複雜度低，演算法編寫簡單，且覆蓋了出現頻率較高的基本故障。結合測試圖形自動發生器(Automatic Pattern Generator，APG)能夠生成複雜度更高的測試圖形，但又帶來了可讀性差、測試時間長、除錯不便等問題，因而一些針對某些特殊故障的複雜測試圖形更多地還停留在科研階段。簡單、高效、高故障覆蓋率的測試圖形演算法是實際工業生產中追求的最終目標。
上一節提到的基於棋盤演算法的改進方法，跟棋盤格演算法比較，測試圖形序列長度僅增加了N，覆蓋了全部轉換故障，測試圖形的編寫難度未增加。因此，在裝置能力能夠滿足需求的條件下，在實際測試中採用該改進演算法替換傳統的棋盤格演算法是很有價值的。
齊步法較目前使用的方法具有更高的故障覆蓋率，測試圖形的複雜度極少量的提高，測試圖形編寫難度也有所增加。棋盤型齊步演算法結合了齊步法和棋盤法的特點，較齊步法有更高的故障覆蓋率而未增加時間複雜度，在實際的測試生產中值得去嘗試。
5 結語
儲存器的測試圖形演算法始終存在測試時間複雜度和故障覆蓋率的矛盾，故障覆蓋率高的演算法必然時間複雜度大。在目前的工業生產應用中，只能使用時間複雜度為O(N)的測試圖形，因而根據實際需要，國內外研究人員基於經典N 型測試圖形演算法進行了改進研究，在不大量增加時間複雜度的前提下，提高故障覆蓋率。但大多數研究還停留在理論分析層面，未透過實驗驗證，更沒有投入到生產應用中。將來測試演算法有可能將測試時間複雜度和故障覆蓋率的矛盾調和到更低，也可能出現解決時間複雜度的方法，總之，儲存器測試圖形演算法的研究還有待進一步的研究和發展。