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