Gallop算法 - 存儲器故障診斷算法實現(xiàn)

　　Gallop算法也稱為1(0)漫游或乒乓測試，測試過程如下：

　　(1)部分地址單元清0(1);

　　(2)A0寫1(0)，然后A1讀0(1)，A0讀1(0)，然后A2讀0(1)，A0讀1(0)，接著A3讀0(1)，A0讀1(0)，直到全部單元;

　　(3)將A0改寫為0(1)，寫A1為1(0)，重復以上步驟。

　　整個過程就像1(0)在整個陣列中漫游一樣，圖5表示1漫游的情況，該算法具有較高的故障覆蓋率，能檢測SAF故障、TF故障以及CF故障，單位該算法操作次數(shù)是O(N2)需要較長的測試時間。

?

　　4.3 March算法(進行法)[3，4]

　　(1)全部單元中寫0;

　　(2)讀A0單元的0，然后再改寫為1，然后讀A1的0，再改寫A1為1，直到An-1。這樣所有單元均為1;

　　(3)然后從An-1到A0作讀1寫0再讀0的操作。

　　該算法的操作次數(shù)為O(N)，能檢測全部的SAF故障、AF故障以及TF故障。

　　5 一種基于棋盤算法的改進及實現(xiàn)

　　通過研究和對比上述3個算法發(fā)現(xiàn)，Checkerboard(棋盤)算法和March算法以線性方式進行讀寫，因此存儲器操作次數(shù)與存儲器容量N成正比，Gallop算法雖然有較高的故障覆蓋率，但由于其對存儲器刺激次數(shù)過多，因此，在實際測試中不是一種很經(jīng)濟的測試算法，Checkerboad算法只實現(xiàn)了0→1或1→0的讀寫，所以不能測試變遷故障。而March算法恰恰實現(xiàn)了這兩個狀態(tài)的轉(zhuǎn)換，但March算法操作次數(shù)(6N)要多于Checkerboard算法的操作次數(shù)(4N)，對于大容量存儲器的測試，March算法將需要比Checkerboard算法更多的測試時間來完成整個測試過程，因此結(jié)合March算法的特點，對Checkerboard算法進行如下改進。

　　(1)對分塊a(b)中單元寫1(0);

　　(2)對分塊a(b)中的單元寫0(1);

　　(3)讀所有單元;

　　(4)對分塊a(b)中的單元寫1(0);

　　(5)讀所有單元。

　　這樣整個存儲器就同時經(jīng)歷了由0→1和1→0兩個讀寫狀態(tài)，就可以測試出變遷故障，寫改進后Checkboard算法對存儲器的操作次數(shù)為5N次，而March算法對存儲

　　器的操作次數(shù)則需要6N次，大大地節(jié)省了測試時間。

　　以一個X(行地址)、Y(列地址)地址復用的128×128的存儲器矩陣為例，按改進后的算法編寫的測試圖形片斷如圖6。

?

　　實際的算法圖形要配合讀寫的時序，因此圖形更為復雜，但對存儲器的操作次數(shù)與理論是一致的，改進的Checkerboard算法雖然使用了較少的存儲器操作次數(shù)，但其只能診斷出部分AF故障，與March算法相比，是以犧牲故障覆蓋率為代價來提高測試速度的。

　　在實際的生產(chǎn)型測試中，地址譯碼模塊由于結(jié)構(gòu)較存儲矩陣要簡單得多，因此出現(xiàn)故障的概率遠遠小于存儲矩陣，且改進的Checkerboard算法也能診斷部分的AF故障，是一種經(jīng)濟的測試算法。

　　6 結(jié)語

　　改進的算法雖然提高了測試速度，但這種改進犧牲了故障覆蓋率。但就實際的測試需要而言，是完全符合要求且行之有效的，在實際應(yīng)用中，要根據(jù)存儲器的故障類型和測試需求來選擇合適的診斷算法，才能達到滿意的效果。