存儲器測試算法及診斷覆蓋率研究

摘 要：隨著微電子技術的快速進步，半導體集成電路高速發展，新的存儲器測試技術也不斷更新。文章描述了存儲器的經典測試算法運算過程，并分析了其原理。在研究經典測試算法的基礎上，吸收經典算法的思想，比較各種不同算法的優缺點，改進測試算法，以便在實際檢測中能夠減少測試所需要的時間，提高故障診斷覆蓋率，達到比較滿意的測試效果。

關鍵詞：存儲器；測試算法；診斷覆蓋率

中圖分類號：TP333.8 文獻標識碼：A 文章編號：1006-8937（2014）12-0009-02

存儲器測試技術是一直不斷更新的技術，隨著存儲器在市場上的需求日益增加，每一種新存儲器技術的出現都會引起廣泛的關注，往往新技術的出現都對實際測試工作造成巨大的改變。而面對越來越大的存儲器市場，生產商對于存儲器功能安全越來越重視，尋找高效的測試算法一直是存儲器測試過程中需要解決的問題。

1 存儲器測試算法

對于存儲器的測試，目前有許多種測試算法，有使用時間長久的經典算法，也有近些年運用廣泛的新型算法，它們都各有特點。

現主要的算法有MSCAN算法（全“0”全“1”算法）、Checkerboard算法（棋盤法）、Gallop算法（奔跳法）、March算法等。一種實用有效的測試算法，能夠花費較少的時間和操作程序，更全面的檢測出存儲器故障。

1.1 MSCAN算法（全“0”全“1”算法）

對所有單元寫“1”，再讀取所有單元，進行對比。對所有單元寫“0”，再讀取所有單元，進行對比。算法表達式：{■（w0）；■（r0）；■（w1）；■（r1）}。算法的執行方式可以如下：

①從檢測起始點，沿著地址遞增的方向將所有存儲單元寫“0”；②從檢測起始點，沿著地址遞增的方向讀出所有存儲單元的值“0”；③從檢測起始點，沿著地址遞增的方向將所有存儲單元寫“1”；④從檢測起始點，按照地址遞增的方向讀出所有儲存單元的值“1”。

可編程為：

For I=1 to n；Do

Write O to cell I

Read cell I for 0

Write 1 to cell I

Read cell I for 1

Continue

End

在運用該算法過程中，若存儲單元無法寫入或讀出的（能夠讀出但是讀出錯誤值），則表示此單元出現了故障。這個算法測試時間是T=4n，時間復雜度O（n）?？蓹z測固定故障SAF。

1.2 Checkerboard算法（棋盤法）

checkerboard算法的測試過程：對存儲器所以存儲單元賦值，賦值完后存儲器就像國際象棋棋盤的形式。即把整個存儲單元分成a、b兩塊（a為黑色，b為白色），然后用如下方式對a、b讀寫，如圖1所示。

①對分塊a（b）中的單元寫0（1）；②讀所有單元；③對分塊a （b）中的單元寫1 （0）；④讀所有單元。

一種改進型checkerboard算法：

①對分塊a（b）中的單元寫0（1）；②對分塊a（b）中的單元寫1（0）；③讀所有單元；④對分塊a（b）中的單元寫1 （0）；⑤讀所有單元。

運用第二種checkerboard算法，存儲器在檢測過程中比未改進型的checkerboard算法多經歷一次狀態變化。此算法則可以測試出TF故障。

checkerboard算法測試時間T=4n（5n），時間復雜度為0（n）?？蓹z測出固定故障SAF等故障，診斷覆蓋率不高。

1.3 Gallop（算法）

Gallop測試算法過程如下：

①所有單元寫0（1）；②A0寫1（0），然后A1讀0（1）；A0讀1（0），A1讀0（1），然后A2讀0（1）；A0讀1（0），接著A2讀0（1），A3讀0（1）；A0讀1（0），…直到全部單元。③將A0改寫為0（1），讀A1位1（0），重復上述步驟。

可編程為：

For I=1 to n；Do

write 0 to cell I

Continue

White I=1 to n；Do

Write 1 to cell I

Read all cell verify I

Write 0 to Cell I

Continue

End

整個算法過程類似于1（0）一直在漫游，漫游情況如圖2所示。

Gallop算法測試時間，時間復雜度為O（n2）。此算法具有較高的診斷覆蓋率，但由于其復雜度比較高，檢測過程中花費的時間較為漫長，故在實際中使用頻率比較低。

1.4 March算法

March算法是近多年在存儲器測試算法中使用較廣的算法之一。March算法根據算法的自由度分為很多種不同算法，March 5n是其中最基本的一種，描述如下：

①全部單元中寫0；②讀A0單元的0，然后再改寫為1，然后讀A1的0，再改寫A1為1，直到An-1。這樣所有單元均為1；③然后從An-1到AO作讀1寫0的操作。

可編程為：

For I=1 to n；Do

Write 0 to cell I

Continue

While I=1 to n；Do

Read cell I verify 0

Write 1 to cell I

Continue

For I=n to 1；Do

Read cell I verify 1

Write 0 to cell I

Read cell I verify 0

Continue

End

這種最一般的March 5n算法的表達式{■（w0）；？堊（r0，w1）；？墼（r1，w0）}。

March 5n算法的測試時間相對較短，操作程度也簡單，它的測試時間長為T=5n，時間復雜度0（n）。

March算法根據算法的自由度可以分為很多不同算法，下面就是一些March算法以及表達式：

March 6n

{■（w0）；？堊（r0，w1）；？墼（r1，w0，r0）}。

March 9n

{■（w0）；？堊（r0，w1）；？堊（r1，w0）；？墼（r0，w1）；？墼（r1，w0）}

march 13n

{■（w0）；？堊（r0，w1，r1）；？堊（r1，w0，r0）；？墼（r0，w1，w1）；？墼（r1，w0，w0）}

存儲器測試算法還有很多，不同種算法各有優勢，但也有不同的缺點。如何在實際測試中發揮各種算法的優點，避除其缺點，提高檢測效率是算法研究的重點。測試時長和存儲大小的關系見表1。各種測試算法診斷覆蓋率的情況見表2。

2 改進型的測試算法

從以上兩張表中可以看出Checkerboard算法和March算法的時間復雜度低，一個為T=4（n），一個為T=5（n），從公式中可知，。測試中操作時間和存儲器容量n成正比利關系。Gallop算法雖然比前兩種測試算法的診斷覆蓋率高很多，但是測試時需要進行的操作太復雜，花費的時間太長，在實際中不具有大量使用的可能性。所以可以嘗試把March算法和Checkerboard算法結合使用，在March算法的基礎上應用checkerboard算法，時間復雜度不變，但是提升了診斷覆蓋率。

改進型算法的測試過程如下：

①所有單元寫0；②讀A0單元的0，再改寫為0；讀A1單元的0，再改寫為1；讀A2單元的0，再改寫為0；讀A3單元的0，再改寫為1...直到An-1。（即存儲器中存儲單元排列次數為奇數的單元讀0寫0，存儲單元排列次數為偶數的單元讀0寫1）這個步驟結果之后，存儲器就像被劃分為棋盤一樣，類似與進行checkerboard測試算法操作得到的結果一樣；③讀An-1單元的1，再改寫為0；讀An-2單元的0，再改寫為1；…直到A0（即讀取每個存儲單元中的值再寫入相反值）。這一步完成后，存儲器的形式還是棋盤格式，只是其中數值都相反。

3 結 語

通過本文分析可知，每一種測試算法都有各自的優點和缺點，沒有完美的測試算法。改進的算法都是在已有的算法的基礎上進行改良或者創新。通過理論分析和數據方面對比，改進的算法在測試速度快速的基礎上，診斷覆蓋率有所提高。在日常存儲器測試工作中，測試算法需要不斷的完善和更新，人們同時必須不斷的嘗試和創新，這樣才能根據測試的實際需要尋找到合適的測試算法以便解決測試過程中遇到的問題。

參考文獻：

[1] 張衛國.RAM檢測的算法分析及軟件實現[J].西安科技學院學報，2003，（3）.

[3] 楊士元.數字系統的故障診斷與可靠性設計[M].北京：清華大學出版社，2000.

[4] 蔣登峰，周娟.隨機存取存儲器故障分析及測試方案實現[J].中國計量學院學報，2010，（3）.

[5] 李璇君，辛季齡，張天宏，等.RAM的故障模型及自測試算法[J].南京航空航天大學學報，1999，（1）.