簡述存儲器測試圖形算法論文
1 介紹
隨著集成電路制造工藝的不斷進步，半導體芯片的發(fā)展趨于高密度、高速度、高復雜度，給測試帶來了極大的挑戰(zhàn)。存儲器是集成電路產(chǎn)品中的一個主要門類，主要用來存放數(shù)據(jù)、指令、程序等信息。存儲器的測試一方面可用于判斷產(chǎn)品質(zhì)量是否合格，另一方面通過測試獲得一些數(shù)據(jù)用于改進工藝。
目前存儲器的基本測試方法已經(jīng)比較成熟，主要有存儲器直接存取測試、存儲器的宏測試、存儲器內(nèi)建自測試三種，各有利弊。存儲器直接存取測試是利用自動測試設備來進行測試，自動測試設備的性能和測試成本使得直接存取測試方式對大容量的存儲器并不合適。存儲器的宏測試將存儲器作為一個宏模塊，利用電路內(nèi)部的掃描路徑生成宏模塊的測試向量，再通過自動測試設備在電路外部施加測試矢量，對于較大的存儲器，宏測試向量的數(shù)據(jù)量較大，測試需要較長時間。存儲器內(nèi)建自測試是在存儲器外圍產(chǎn)生一整套控制電路，實現(xiàn)芯片內(nèi)置存儲器測試模式的自動產(chǎn)生及測試結(jié)果的自動判別，這種方法增加芯片的面積，但是具有自動化程度高、測試質(zhì)量高、測試成本低、測試時間短等優(yōu)勢。
對于存儲器來說，最主要的測試是讀寫邏輯功能測試，以檢測存儲單元的故障，包括由于壞的金屬連接、壞的元件、芯片邏輯錯誤等原因引起的功能故障。這些故障通常被簡化為幾個較為成熟的故障模型，通過不同的測試圖形算法來檢測故障。本文以存儲器的測試圖形為切入點，先簡單介紹存儲器簡化的故障模型，然后介紹常用的存儲器測試圖形算法以及一些新近提出的改進存儲器測試圖形算法，對其進行比較，并對將來存儲器測試圖形的發(fā)展進行預期。
2 常用的存儲器測試圖形算法
對于存儲器的功能測試，算法有很多種，分別針對不同的存儲器故障模型，包括固定故障、轉(zhuǎn)換故障、耦合故障、圖形敏感故障、尋址故障、數(shù)據(jù)保留故障等。一個高效率的測試算法，需要用盡可能少的測試圖形和盡可能短的測試時間檢測到盡可能多的故障。從理論上說，存在覆蓋所有故障的測試算法，但是實際上由于時間復雜度的原因無法實現(xiàn)。假設用N 表示一個存儲器的地址數(shù)，那么測試圖形的復雜度可以用N來表示。
對于較大容量的存儲器來說，N3/2圖形和N2圖形的測試時間在實際測試中是無法承受的。在實際測試中最常用的算法主要有全“0”/全“1”圖形，奇偶校驗板圖形和齊步“1”/“0”圖形。這三種圖形均為N圖形。
1、全“0”/全“1”圖形
將全部存儲單元按順序?qū)?、讀0、寫1、讀1，測試圖形序列長度為4 N，可用于檢測存儲器的固定故障。
2、奇偶校驗板圖形
奇偶校驗板圖形也稱棋盤圖形，向存儲單元矩陣寫入的數(shù)據(jù)圖形是根據(jù)存儲單元選址地址碼的奇偶性而定的，如果存儲單元的行地址碼和列地址碼中有偶數(shù)個1，其奇偶性為0，則在該存儲單元中寫“0”，反之寫“1”。根據(jù)算法寫入背景圖形，然后逐位讀出并檢測結(jié)果的正確性，再以反碼圖形重復上述測試過程，測試圖形序列長度為4 N。奇偶校驗板圖形可用于檢測存儲器的固定故障、地址譯碼故障，以及相鄰位的短路故障。
3、齊步圖形
齊步圖形算法也稱March算法，是對存儲器的每個單元依次進行檢驗的一種方法，從第一個存儲單元開始，逐一對每個單元進行取反和檢驗，直到最后一個單元檢測結(jié)束才完成一遍掃描。齊步算法的流程如圖2所示，W0、W1、R0、R1分別表示寫“0”、寫“1”、讀“0”、讀“1”。具體流程為：首先背景圖形寫全“0”，從低地址開始沿增址方向順序讀“0”、寫“1”(R0W1)，一直到最高地址。然后從最高地址開始沿減地址方向順序讀“1”、寫“0”(R1W0)，測試圖形序列長度為5 N。齊步圖形可用于檢測全部的固定故障、地址譯碼故障和轉(zhuǎn)換故障。
4、其他測試圖形
以上三種測試圖形均為N 型測試圖形，其共同特點是測試時間短，但覆蓋的故障比較有限。相較而言，齊步算法的效率最高。除此之外，還有很多復雜度更高的圖形，比如乒乓算法、蝶形算法等。乒乓算法的`故障覆蓋率很高，能夠有效地檢測出固定故障、轉(zhuǎn)換故障、耦合故障和部分圖形敏感故障，其測試圖形序列長度為4 N2+2 N，屬于N2型測試圖形。蝶形算法同樣具有很高的故障覆蓋率，能夠有效地檢測出固定故障、地址解碼故障和圖形敏感故障，屬于N3/2型測試圖形。
這些高復雜度的測試圖形都具有一個共同的弊端，時間復雜度太高，測試時間過長，雖然在理論中有很高的故障覆蓋率，但在實際生產(chǎn)中很少使用。
因此，在近期關(guān)于存儲器測試圖形算法的研究中，提出了一些改進的N圖形算法，跟經(jīng)典的測試算法相比，在不大量增加測試時間的前提下，能夠有效地提高故障覆蓋率，在下一部分將詳細進行介紹。
3 改進的存儲器測試圖形算法
目前，國內(nèi)外經(jīng)典的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算法及其衍生算法現(xiàn)成為存儲器測試的主流算法。本文將介紹三種較為新穎巧妙的改進算法。
1、棋盤型齊步算法
這種算法的基本構(gòu)想是在齊步算法中使用棋盤格式，棋盤算法可以檢測出固定故障和相鄰單元的橋接故障，齊步圖形算法可以覆蓋全部的固定故障、地址譯碼故障和轉(zhuǎn)換故障。將兩種算法相結(jié)合，不僅可以實現(xiàn)兩種算法本來的功能，由于讀寫特殊性，還可以檢測一部分相鄰圖形敏感故障。
(1)所有存儲單元寫0。
(2)讀A0單元(表示地址為0的單元)的“0”，再改寫為“0”;讀A1單元的“0”，再改寫為“1”;讀A2單元的“0”，再改寫為“0”;讀A3單元的“0”，再改寫為“1”…直到An-1。此步執(zhí)行完后，存儲器被寫為棋盤格式。
(3)讀An-1單元的“l(fā)”，再改寫為“0”;讀An-2單元的“0”，再改寫為“l(fā)”…直到A0。此步完成后，存儲器被寫為一個與步驟(2)結(jié)束后相反的棋盤格式。
經(jīng)過改進的棋盤格齊步算法測試圖形序列長度為5 N，跟齊步圖形算法相比，測試時長沒有增加，而故障覆蓋率明顯提高。
2、基于棋盤算法的改進
棋盤格圖形算法中，對于每一個存儲單元來說，只經(jīng)過了從“0”到“1”的轉(zhuǎn)換或者從“1”到“0”的轉(zhuǎn)換，不能覆蓋全部的轉(zhuǎn)換故障。于是對棋盤算法進行了巧妙的改進，具體流程如下：
(1)寫入反棋盤格圖形;
(2)寫入棋盤格圖形;
(3)讀棋盤格圖形;
(4)寫入反棋盤格圖形;
(5)讀反棋盤格圖形。
該改進算法與棋盤格算法相比，測試圖形序列長度增加了N，能夠檢測出全部的轉(zhuǎ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，通過改進，除了能夠覆蓋固定故障、地址解碼故障等靜態(tài)故障意外，還能夠覆蓋全部的動態(tài)讀破壞故障、動態(tài)讀錯誤故障、動態(tài)干擾耦合故障和部分動態(tài)偽讀破壞故障、動態(tài)偽讀破壞耦合故障。在檢測存儲器動態(tài)故障的算法中，以較低的測試時間復雜度，獲得了較高的故障覆蓋率。
4 存儲器測試圖形算法的應用
在目前的實際測試生產(chǎn)中，采用的都是存儲器直接存取測試的方法，考慮到設備能力和測試效率的問題，通常使用的都是經(jīng)典的O(N)型測試圖形，僅包括全“0”/全“1”測試圖形和奇偶校驗板圖形，對于大容量的存儲器，由于設備測試圖形存儲容量的限制，僅采用奇偶校驗板圖形進行測試。這兩種算法時間復雜度低，算法編寫簡單，且覆蓋了出現(xiàn)頻率較高的基本故障。結(jié)合測試圖形自動發(fā)生器(Automatic Pattern Generator，APG)能夠生成復雜度更高的測試圖形，但又帶來了可讀性差、測試時間長、調(diào)試不便等問題，因而一些針對某些特殊故障的復雜測試圖形更多地還停留在科研階段。簡單、高效、高故障覆蓋率的測試圖形算法是實際工業(yè)生產(chǎn)中追求的最終目標。
上一節(jié)提到的基于棋盤算法的改進方法，跟棋盤格算法比較，測試圖形序列長度僅增加了N，覆蓋了全部轉(zhuǎn)換故障，測試圖形的編寫難度未增加。因此，在設備能力能夠滿足需求的條件下，在實際測試中采用該改進算法替換傳統(tǒng)的棋盤格算法是很有價值的。
齊步法較目前使用的方法具有更高的故障覆蓋率，測試圖形的復雜度極少量的提高，測試圖形編寫難度也有所增加。棋盤型齊步算法結(jié)合了齊步法和棋盤法的特點，較齊步法有更高的故障覆蓋率而未增加時間復雜度，在實際的測試生產(chǎn)中值得去嘗試。
5 結(jié)語
存儲器的測試圖形算法始終存在測試時間復雜度和故障覆蓋率的矛盾，故障覆蓋率高的算法必然時間復雜度大。在目前的工業(yè)生產(chǎn)應用中，只能使用時間復雜度為O(N)的測試圖形，因而根據(jù)實際需要，國內(nèi)外研究人員基于經(jīng)典N 型測試圖形算法進行了改進研究，在不大量增加時間復雜度的前提下，提高故障覆蓋率。但大多數(shù)研究還停留在理論分析層面，未通過實驗驗證，更沒有投入到生產(chǎn)應用中。將來測試算法有可能將測試時間復雜度和故障覆蓋率的矛盾調(diào)和到更低，也可能出現(xiàn)解決時間復雜度的方法，總之，存儲器測試圖形算法的研究還有待進一步的研究和發(fā)展。
【簡述存儲器測試圖形算法論文】相關(guān)文章：
豐富的圖形世界測試及答案01-21
小羊軍團發(fā)展論文簡述04-06
關(guān)于議論文的簡述06-26
數(shù)學算法初步測試題03-19
算法案例測試題練習05-22
負數(shù)的加減算法測試題06-29
有關(guān)算法案例測試題05-02
算法設計與分析課程論文11-18