An Algorithm of the Test Pairs Minimization by means of the Incompatibility Graph

• Autorzy: Czerwiński R. , Rudnicki T.

Warianty tytułu

PL

Algorytm minimalizacji par testowych z użyciem grafu niezgodności

• Języki publikacji: EN

Abstrakty

EN

A heuristic method of the test pairs minimization in Two-Pattern testing is presented. The method is designed for test pattern generators including ROM and MISR, while the goal of the minimization is reduction of the ROM size. The method is based on the coloring the incompatibility graph. Authors present original application of the coloring the incompatibility graph. Introduced in the paper algorithm is very compact and can be implemented as a quick computer program. Primary experiments prove the high effectiveness of the method.

PL

W niniejszej pracy przedstawiono heurystyczną metodę minimalizacji liczby par testowych potrzebnych do testowania uszkodzeń opóźnieniowych. Metoda ta polega na tworzeniu w kolejnych etapach minimalizacji grafu niezgodności par testowych. Minimalizacja opiera się na kolorowaniu takiego grafu. Ostateczna liczba par testowych jest równa liczbie chromatycznej grafu. Naturalnie, kolory przyporządkowane poszczególnym wierzchołkom grafu zawierają informację, które pary testowe mają być ze sobą sklejane. O końcowej liczbie par testowych po procesie sklejania decyduje liczba stanów nieokreślonych występujących w parach testowych przed procesem sklejania. Jeżeli liczba tych stanów jest duża, wówczas istnieje wiele możliwości sklejania par testowych. Jednak tylko kilka rozwiązań sklejania daje minimalną końcową liczbę par testowych po procesie sklejania. Metoda nie wymaga rozwiązania problemu pokrycia znanego z klasycznych metod minimalizacji. Kilka sklejonych par testowych (rys. 3) w jedną parę testową (rys. 4) oznacza, że w jednym takcie zegarowym zostanie przetestowanych kilka ścieżek układu ze względu na występowanie w nich uszkodzeń opóźnieniowych. Mniejsza liczba par testowych oznacza mniejszą liczbę słów programujących, a także mniejsze wykorzystanie pamięci ROM generatora par testowych z pamięcią ROM (rys. 1) przy jednoczesnym wysokim współczynniku pokrycia par testowych. Dodatkową zaletą mniejszej liczby par testowych jest mniejsza liczba potrzebnych taktów zegarowych do ich generacji. Poszczególne kroki metody minimalizacji liczby par testowych (rys. 6) zostały przedstawione na prostym przykładzie (rys. 5). Wstępne wyniki eksperymentów dają bardzo dobre wyniki.

Słowa kluczowe

EN

two-pattern testing; delay faults; MISR

PL

testowanie; pary testowe; uszkodzenia opóźnieniowe; MISR

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 6
• Strony: 573--575
• Opis fizyczny: Bibliogr. 6 poz., rys., schem.

Twórcy

autor

Czerwiński R.

autor

Rudnicki T.

• Silesian University of Technology, Faculty of Automatics, Electronics and Computer Science,

Bibliografia

• [1] Furuya K., McCluskey E. J.: Two-Pattern Test Capabilities of Autonomous TPG Circuits. Proc. IEEE Int. Test Conference, October 1991, pp. 704-711.
• [2] Kania D.: Synteza logiczna przeznaczona dla matrycowych struktur programowalnych typu PAL. Zeszyty Naukowe Politechniki Śląskiej, Gliwice, 2004.
• [3] Polian I., Becker B.: Configuring MISR-Based Two-Pattern BIST Using Boolean Satisfiability. Proc. Int. Workshop on Design and Diagnostics of Electronic Circuits and Systems, April 2003, pp. 73-80.
• [4] Qiang X., Nicolici N.: DFT infrastructure for broadside two-pattern test of core-based SOCs. IEEE Transactions on Computers, April 2006, Volume 55, Issue 4, pp. 470-485.
• [5] Rudnicki T., Hławiczka A.: Test Pattern Generator for Delay Faults. Proc. of IEEE Int. Workshop on Design & Diagnostic of Electronics Circuits & Systems, DDECS’07, Kraków 2007, pp. 255-258.
• [6] Wan W., Perkowski M. A.: A new Approach to the Decomposition of Incompletely Specified Multi-Output Functions Based on Graph Coloring and Local Transformations and Its Applications to FPGA Mapping. Proc. of the Conf. on European Design Automation, 1992, pp. 230-235.