2. DIGITÁLIS ÁRAMKÖRÖK TESZTJEINEK SZÁMÍTÁSA (Dr. Sziray József, 2001.)

2. DIGITÁLIS ÁRAMKÖRÖK TESZTJEINEK SZÁMÍTÁSA (Dr. Sziray József, 2001.) 2.1 A digitális tesztelés alapjai A következőkben a digitális áramköröket elvont formában, vagyis digitális vagy logikai hálózatokként kezeljük. Ez azt jelenti, hogy a fizikailag létező áramköröket az őket egyegyértelműen reprezentáló hálózati modellel helyettesítjük. Definíciók: Hálózati pont: A hálózatban szereplő logikai elemek bemenő, ill. kimenő pontjai, melyekhez logikai érték rendelhető. Elsődleges bemenet: Olyan hálózati pont, mely a hálózat egyik logikai elemétől sem kap vezérlő jelet. Elsődleges kimenet: Olyan hálózati pont, melyet a hibavizsgálat teljes végrehajtása alatt méréssel ellenőrizni tudunk és szándékozunk. Megjegyzés: A tárgyalásban elsődleges be/kimenet helyett hálózati be/kimenet is elő fog fordulni. Hálózati csomópont: elsődleges bemenet, vagy a hálózat logikai elemének kimenő pontja. Hálózati út: Csomópontoknak olyan rendezett sorozata, amelyben bármely két egymást követő csomópont egyazon logikai elem bemeneti, ill. kimeneti pontja, ahol a bemeneti pont megelőzi a kimenetit, és a sorozatban mindegyik elem csak egyszer fordul elő. Az i, j, k,…, p sorszámú pontok által képezett utat P(i-j-k-…-p) fogja jelölni (az angol path szó alapján). Ha egy útra csak i kezdő- és j végpontjával hivatkozunk, akkor a P(i-j) jelölést alkalmazzuk. Teljes út: Elsődleges bementtől elsődleges kimenetig terjedő út. Hálózati út hossza: Az út mentén előforduló csomópontok száma. Rekonvergens utak: Két vagy több hálózati út rekonvergens, ha legalább két közös pontjuk van. A jelenséget rekonvergenciának nevezzük. Tesztelés: A hálózat elsődleges bemeneteire történő sorozatos jelküldés és az elsődleges kimenetek jeleinek megfigyelése. Megjegyzés: A tesztelés végrehajtása célszerűen automatizáltan történik. Ilyenkor egy áramköri egységen (pl. integrált áramköri elem, szerelt áramköri kártya, stb.) a hozzáférési érintkezőket tekintjük elsődleges be/kimeneti pontoknak: a tesztelő automata a bemeneti érintkezőkre küldi a vizsgálójeleket, és a kimeneti érintkezőkön méri a válaszjeleket.

Egy hiba tesztje: Elsődleges bemeneti jelkombinációk olyan rendezett sorozata, melynek hatására az adott hibát tartalmazó hálózat a legutolsó kombinációra a helyestől eltérő (hibás) elsődleges kimeneti kombinációval válaszol. Ebben az esetben azt mondjuk, hogy a teszt kimutatja, felfedi, vagy detektálja a hibát. Itt használatban van még az a kifejezés is, hogy a teszt lefedi az adott hibát. Detektálható hiba: Egy hibáról akkor mondjuk, hogy detektálható, ha legalább egy tesztje létezik. (Tervezési redundancia folytán létezhetnek olyan áramköri hibák, amelyek semmilyen körülmények között nem éreztetik hatásukat az áramkör egészének működésében. Az ilyen hibák nem detektálhatók a teszt definíciója értelmében.) Egy adott ponton detektálható hiba: Egy hiba az i hálózati ponton detektálható, ha a hiba jelenléte miatt az i ponton az elvárt helyes logikai értéktől eltérő érték jelentkezik. Ennek megfelelően egy hiba tesztje a hibát legalább egy elsődleges kimeneten detektálja. Hibajel: Az i hálózati ponton jelentkező hibás logikai érték. Eszerint egy hiba tesztje legalább egy elsődleges kimeneten képes hibajelet eredményezni. Teljes tesztkészlet/teszthalmaz: Teszteknek olyan összessége, amely a hálózat mindegyik előre feltételezett és detektálható hibájának tesztjét magában foglalja. Az ilyen teszthalmazról azt mondjuk, hogy teljes hibalefedést eredményez. A hibalefedés mértékét szokás még százalékban is kifejezni: ekkor egy teszthalmazhoz azt az értéket rendeljük, ami az általa lefedett hibáknak az összes hibához viszonyított százalékát adja. A teljes teszthalmaz 100 %os hibalefedésű. Ha a teszteket annak eldöntésére használjuk fel, hogy a hálózat egyáltalán hibás-e vagy sem, akkor hibadetektáló vagy jó-nem jó (angolban „go-no go”) tesztelésről beszélünk. Ha a hibák helyének és mivoltának megállapítása a célunk, akkor hibadiagnosztizáló tesztelésről van szó. Ez nyilván magában foglalja a hibadetektáló tesztelés végrehajtását is. Teszttervezés: Az a tervezési folyamat, amelyben egymás után meghatározzuk az egyes előre feltételezett hálózati hibák tesztjét. Ezt a folyamatot mindenképpen célszerű számítógépen végezni: ekkor számítógépes teszttervezésről vagy számítógépes tesztgenerálásról beszélünk. A teszttervezés mindenkori célja a teljes tesztkészlet előállítása, vagyis a 100 %-os hibalefedés elérése. Megjegyzés: A mai félvezetős technológia már olyan bonyolult áramkörök előállítását teszi lehetővé (egy IC-be milliós számban tudnak tranzisztorokat integrálni), hogy a teljes hibalefedés elérése gyakorlatilag nem valósítható meg. Általában a 90 %-on felüli minél jobb lefedés a reális és elfogadható cél. Tesztszámítás vagy determinisztikus tesztgenerálás: Egy adott hiba tesztjének szisztematikus számításokkal történő meghatározása. Véletlenszerű/random tesztgenerálás: Bemenő jelkombinációk sorozatának véletlenszerű képzése a hálózati hibák tesztjeként történő felhasználásra. (Angolban: random test generation.)

2

Logikai hibaszimuláció: A hibátlan és a hibát tartalmazó hálózat logikai működésének végigkövetése adott bemenőjel-sorozat hatására, a hibátlan hálózat működésével való összehasonlítás céljából. A hibaszimuláció számítógépen hajtandó végre: elsődleges célja az, hogy meghatározzuk a bemenő jelek által felfedhető hibák halmazát. Elkerülhetetlen szerepe van a random tesztgenerálásban, ahol a véletlenül képzett tesztekről határozhatjuk meg a segítségével, hogy azok mely hibákat képesek detektálni. Ugyancsak fontos szerepet kap a determinisztikus tesztgenerálásban is: ekkor egy kiszámított tesztre végrehajtva meg tudjuk határozni a kapott teszt által felfedett többi hibát is. Ezekre a hibákra már nem kell elvégezni a tesztszámítást. Teljes hibaszimuláció: Hibaszimuláció végrehajtása az összes előre feltételezett hibát különkülön tartalmazó hálózatra. Ezáltal a bemenőjel-kombinációk sorozata által felfedni képes összes hibát meghatározzuk. Egy adott tesztkészletre végrehajtott teljes hibaszimuláció eredménye egy ún. hibamátrixban foglalható össze. A mátrix soraihoz a tesztek, oszlopaihoz a hibák tartoznak. Egy sor és egy oszlop találkozásánál 1-es szerepel, ha a sor tesztje felfedi az oszlop hibáját, 0 szerepel, ha nem fedi fel. Megjegyzés: A hibamátrixban foglalt információ alapján nyílik mód a diagnosztizáló tesztelés végrehajtására. Erre akkor kerül sor, amikor a fizikailag tesztelt áramkörről kiderült, hogy hibás. A mérési eredményekből tudni lehet, hogy melyik tesztre érkezett helyes válasz, ill. melyikre hibás. A helyes választ adó tesztek által felfedett hibák nem lehetnek az áramkörben, míg a hibás választ adó tesztek hibái elvileg igen. Mindezek alapján a méréssel kapott információ és a hibamátrix együttes felhasználása lehetővé teszi az elvileg lehetséges hibák körének a leszűkítését egy minimálisan lehetséges konkrét hibahalmazra. A hibamátrix alapján előre meg lehet határozni az adott tesztkészlet ún. diagnosztikai felbontóképességét: ez az a szám, amely megadja, hogy a tesztkészlet végrehajtásának összes lehetséges kimenetele átlagosan hány eleműre teszi lehetővé az áramkörben lehetséges konkrét hibák körét. Kombinációs hálózatok modellje: Kombinációs hálózatokra a következő algebrai modellt fogjuk használni: Legyen a hálózat elsődleges bemeneti változóinak vektora x = (x1, x2,…, xn), az elsődleges kimeneti változók vektora z = (z1, z2,…, zm), ahol zi az x változóinak Boole-függvénye:

zi = zi(x)

i = 1,2,…, m-re.

A továbbiakban a kombinációs hálózatokat késleltetés nélkülinek tekintjük, vagyis feltételezzük, hogy a zi kimeneti függvény értékét bármely időpillanatban meghatározza a bemeneti értékek kombinációja. Az elsődleges bemeneti, ill. kimeneti értékkombinációt olyan vektornak tekintjük, amelynek i-edik komponense xi, ill. zi logikai értéke. A hálózat általános rajza a 2.1. ábrán szerepel.

3

x1 Kombinációs

x2

z1 z2

hálózat zn

xn

2.1. ábra: Kombinációs hálózatok modellje Az i-edik hálózati pont logikai változója legyen gi, melynek viselkedését a gi(x1, x2,…, xn) = gi(x) Boole-függvény írja le. A logikai inverzió jelölésére az aposztróf (felülvessző) jelet fogjuk használni: Például x1 inverze x1’. Legyen továbbá a hálózat pontjainak száma w, és a pontokat számozzuk 1-től w-ig a következő konvenció szerint: Egy logikai elem bemeneti pontjának sorszáma legyen mindig kisebb, mint bármelyik kimenetének sorszáma. Belátható, hogy ez a számozási előírás minden esetben teljesíthető. Ezen kívül még kikötjük, hogy gi = xi legyen.

i = 1, 2, …, n-re Sorrendi hálózatok modellje:

A továbbiakban kizárólag szinkron, vagyis órajellel ütemezett sorrendi hálózatokkal foglalkozunk. Ezekre nézve a 2.2. ábra szerinti modellt fogjuk alkalmazni, ami nem más mint az ún. Mealy-modell. A modell jelöléseinek értelmezése, vektorok felhasználásával: x = (x1, x2,…, xn)

az elsődleges bemeneti változók vektora.

z = (z1, z2,…, zn)

az elsődleges kimeneti változók vektora.

y = (y1, y2,…, yn)

a másodlagos (visszacsatolási) bemeneti változók vektora, amely a hálózat jelenlegi tároló állapotát fejezi ki.

Y = (Y1, Y2,…, Yn) a másodlagos (visszacsatolási) kimeneti változók vektora, amely a hálózat következő tároló állapotát fejezi ki.

4

z1

x1 Kombinációs

xn

zn

hálózat y1

Y1

yp

Yp D1

Dp Órajel

2.2. ábra: Szinkron szekvenciális hálózatok modellje A szinkronitás következményeként az órajelek által megszabott t-edik ütem Y vektorának és a (t+1)-edik ütem y vektorának értékkombinációi megegyeznek. Emiatt szokás még y bitértékeit a hálózat jelenlegi állapotának, Y-éit pedig következő állapotának, y-t és Y-t pedig állapotvektoroknak nevezni. Eszerint tehát az időpontok t = 0, 1, 2,… diszkrét értékeivel yj[t + 1] = Yj[t],

j = 1, 2,…, p-re.

A kombinációs részhálózathoz tartozó alábbi Boole-függvények teljessé teszik a hálózat algebrai leírását: zj = zj(x1, x2,…, xn, y1, y2,…, yp)

j = 1, 2,…, m-re.

Yj = Yj(x1, x2,…, xn, y1, y2,…, yp)

j = 1, 2,…, p-re.

Ebben a modellben a kombinációs hálózatot továbbra is késleltetés nélkülinek tekintjük, vagyis feltételezzük, hogy a fenti két összefüggésben nem játszik szerepet az idő.

5

2.1.1 Hibamodellek és érvényességi körük Hibamodellnek nevezzük azoknak az előre feltételezett hibáknak a konkrét halmazát, amelyekre vonatkozóan a teszttervezést végre kívánjuk hajtani. Több fajta hibamodell létezik a gyakorlatban. Egy hibamodell meghatározásakor a következő főbb szempontokat érdemes tekintetbe kell venni: • • •

A teszttervezés kivitelezhetőségi lehetőségei és a ráfordítandó költségek. Az adott gyártási technológiához kapcsolódó hibajelenségek előzetes ismerete. A tesztelés végrehajtásához szükséges hardver és szoftver eszközök által nyújtott szolgáltatások köre.

Megjegyzés: A publikált gyakorlati tapasztalatok alapján általában megállapítható, hogy a digitális áramkörök, ill. berendezések fejlesztési és előállítási költségében a tesztelési folyamatok megtervezésére és végrehajtására fordítandó költség több mint 50 %-ot tesz ki. A gyártási technológiák fejlődésével folyamatosan növekszik az integráltsági fok, az áramkörök bonyolultsága és mérete, ami végső soron a tesztköltségek arányának növekedését vonja maga után. Mindebből az következik, hogy folyamatosan szükség van újabb és hatékonyabb módszerek, eszközök kidolgozására mind a teszttervezés, mind pedig a tesztvégrehajtás területén. A következőkben a használatban levő fontosabb hibamodelleket tekintjük át. Ehhez előbb a különböző lehetséges hibákat ún. hibaosztályokba soroljuk, a fellépésük és hatásuk sajátságaitól függően. Általános hibaosztályok: a) A hiba jelentkezésének időtartamától függően: • Állandó vagy permanens: a hiba az üzemelés teljes időtartama alatt változatlanul fennáll. • Átmeneti vagy intermittens: a hiba az üzemelés során időnként megjelenik, majd megszűnik. • Ideiglenes: a hiba csak egyszer jelenik meg, majd megszűnik. b) A működésben kifejtett hatástól függően: • Statikus: a hiba az állandósult állapotbeli működésben nyilvánul meg. • Dinamikus: a hiba hatása az időbeli viselkedésben jelentkezik. (Példák: Egy logikai elem késleltetése nagyobb a megengedettnél, aminek hatására a hálózat egésze lassabban hajtja végre a műveleteit a kelleténél. A hálózat belső jelterjedési idői a tárolók beírási és vezérlési viszonyait megzavarják, amitől hibás beírás történik meg.) c) A működési szemlélettől függően: • Logikai: a hálózat logikai működését változtatja meg a hiba. • Parametrikus: az áramköri működésben jelentkező hiba, amely a jelek feszültségszintjében, áramértékében, ill. az elemek terhelhetőségében nyilvánul meg. d) Az előfordulási számosságtól függően: • Egyszeres: az adott hiba csak egyedül, önmagában fordul elő. • Többszörös: az adott hiba egynél több helyen, egyidejűleg külön-külön lép fel.

6

A hibák érvényességi köre: A hardver-technológia fejlődésével a versenyben fennmaradt vezető nyugati és japán cégek olyan magas szintre tudták már emelni a fejlesztési és gyártási minőségbiztosítást, hogy ezzel lényegesen javult az általuk kibocsátott termékek megbízhatósága és időtállósága. A mai korszerű digitális rendszerek körében a meghibásodás szempontjából előtérbe kerültek az ún. biztonságkritikus rendszerek, amelyeknél a hibás működés jelentős károkat okozhat emberéletben, környezeti hatásban, vagy gazdasági, pénzügyi téren. Az USA-beli Bell Laboratories (jelenlegi nevén: Lucent Technologies), az általa üzemeltetett ilyen kategóriájú telefonvezérlési rendszerében 1997-ben statisztikai felmérést végzett a leállási idők okaira vonatkozóan. Eszerint az egy évre terjedő eredmények azt mutatták, hogy 70 %-ban szoftverhiba, 20 %-ban intermittens és dinamikus hiba, és állandósult statikus hardver-hiba csak 10 %-ban volt a leállások előidézője. A hardver tekintetében jelentkező fenti megfigyelés a gyakorlatban világszerte megerősítést nyert. Ez azt jelenti, hogy megnövekedett a jelentősége az időszakos, átmeneti, ill. dinamikus hibák tesztelésére alkalmas megoldások kidolgozásának. Az ezen a téren elért eddigi elméleti eredmények ugyanakkor arra utalnak, hogy a tesztszámításban nincsen szükség arra, hogy alapjában eltérő számítási megközelítést kelljen alkalmazni az ilyen hibákra nézve, mint amilyeneket a permanens, statikus hibáknál alkalmazhatunk. Ennek két fő oka van: •

•

Az időszakosan jelentkező hibák nagy része olyan hardver-hiba, amely nem különbözik az állandósult hibától, így az utóbbi tesztje az előbbi kimutatására is alkalmas. Ilyenkor tehát nem a tesztek tervezésében, hanem a tesztek végrehajtási módjában kell különbséget tenni. Ez azt jelenti, hogy az időszakos hibák kimutatása érdekében rendszeresen ismétlődő, üzem közbeni tesztelésre van szükség. A dinamikus hibák kimutatására szolgáló tesztszámítási eljárások visszavezethetőek a statikus hibák tesztjeinek számítására.

Mindezek alapján a továbbiakban kizárólag olyan hibamodellel fogunk foglalkozni, amelyre a következő hibaosztályok érvényesek: • • •

Permanens. Statikus. Logikai.

Megjegyzés: A számosság tekintetében elsősorban egyszeres hibákkal foglakozunk, de egyes módszereknél a többszörös hibákat is figyelembe vesszük. Az alkalmazott hibamodellek: Elakadási hiba: Egy hálózati pont hibája, ami abban nyilvánul meg, hogy az adott pont logikai értéke állandó szinten marad, és vezérléssel nem változtatható meg. (Angol elnevezése: stuck-at fault. Ebből származik a másik, széles körben elterjedt magyar elnevezése: leragadási hiba.)

7

Az α logikai szinten törtnő elakadást α-s elakadásnak (angolul stuck-at α) nevezzük. Például: 0-s vagy 1-es elakadás (stuck-at 0 vagy stuck-at 1). Az i-edik pont α szinten történő elakadási hibáját a továbbiakban i(α)-val jelöljük. Mint ismeretes, a sínen (buszon) keresztül történő adatátvitel az ún. nagyimpedanciás logikai értéket is megköveteli. Ez az érték valójában a sínre való jelkapcsolódás megszűntét fejezi ki, ezért valójában csak egy fiktív logikai érték, amit jelöljünk Z-vel. A nagyimpedanciás érték az elakadási hibák körébe a következő módon vonható be: Az i-edik pont nagyimpedanciás elakadása az i(Z) hiba, ami abban nyilvánul meg, hogy az i pont nem vezérelhető sem 1-be, sem 0-ba, vagyis a pont „nem tud rábeszélni a sínre”. Ennek a hibának létezik az inverze is, amit kisimpedanciás elakadásnak nevezhetünk, és i(Z’)-vel jelölünk. Ez a hiba abban nyilvánul meg, hogy az i pont nem vezérelhető Z-be, csak 0-ba vagy 1-be, vagyis a pont „mindig a sínre beszél”. Jelvezetékek galvanikus hibái: Kétféle hiba léphet fel a logikai elemek galvanikus összeköttetésében, nevezetesen rövidzár, ill. szakadás. A rövidzárral két különböző jelvezeték kerül galvanikus kapcsolatba. Az áramköri technológiától függően ilyenkor ÉS-zárlatról, ill. VAGY-zárlatról beszélhetünk. ÉS-zárlat esetén a két jelvezeték egymástól eltérő logikai értéke mellett a zárlatban a 0 érték jelenik meg, vagyis a 0 szint dominál, VAGY-zárlat esetén pedig ugyanekkor az 1-es érték jelenik meg, vagyis az 1 szint dominál. Megjegyzés: Tesztszámítás szempontjából a zárlati hibák kezelése lényegében véve visszavezethető az elakadási hibákéra. Az igazi nehézséget itt az okozhatja, amikor egy zárlat visszacsatolási hurkot hoz létre egy hálózatban. Ezzel egy kombinációs hálózat aszinkron szekvenciálissá változik, míg egy szinkron szekvenciális hálózat egy tárolóval bővülhet, ami aszinkron működést is okozhat. A szakadással egy vezeték jeltovábbítása szűnik meg. Az esetek többségében ez egy adott szintű logikai elakadási hibának felel meg: az áramköri technológiától függően a leszakadt bemeneti pontok 0-s vagy 1-es elakadáson vannak. CMOS-hibák: Tranzisztor-hibák: Az elterjedt CMOS technológiájú félvezetős logikai áramkörök NMOS vagy PMOS típusú kapcsoló üzemű tranzisztorokkal működnek. (Emiatt működésük tulajdonképpen hasonlít a régi relés hálózatok működéséhez.) A félvezetős tranzisztoroknak kétféle hibája állhat elő: •

•

A tranzisztor forrás (source) és nyelő (drain) pontjai között állandó rövidzár lép fel. Ez a tranzisztor ún. zárlati hibája, amikor a tranzisztor állandóan átereszt (angolul: stuck-at short hiba). NMOS esetén ez a hiba ekvivalens a tranzisztor vezérő pontjának (jelöljük g-vel az angol gate elnevezés után) 1-es elakadásával, vagyis g(1)-gyel, PMOS esetén pedig g(0)-val. A tranzisztor forrás és nyelő pontjai között állandó szakadás lép fel. Ez a tranzisztor ún. szakadási hibája, amikor a tranzisztor állandóan nyitva van

8

(angolul: stuck-at open hiba). NMOS esetén ez a hiba ekvivalens a tranzisztor vezérő pontjának 0-s elakadásával, vagyis g(0)-val, PMOS esetén pedig g(1)-gyel. Galvanikus hibák: A CMOS áramkörök galvanikus hibái a tranzisztorok közötti összeköttetésekben jelentkeznek, rövidzár vagy szakadás formájában. Ezek a hibák azzal a következménnyel járnak, hogy többnyire lényegesen módosítják az eredeti logikai működést, ami nagymértékben megnehezíti a tesztszámítási feladatot. (Kombinációs hálózatnál ilyenkor a transzformált hálózathoz kell olyan bemenő jelkombinációt keresni, ami eltérő választ eredményez az eredeti hálózathoz képest. Szekvenciális hálózatnál ugyanezt a célt a bemeneti kombinációk megfelelő sorozatával lehet elérni.) A felhasznált hibamodell: A továbbiakban a legelterjedtebben használatos hibamodellel, az elakadási hibák halmazával foglalkozunk csak. Mint látható volt, ezek a hibák sok esetben ekvivalensek voltak zárlati, ill. szakadási hibákkal. Kimutatható továbbá az is, hogy egy logikai kapu bemeneti pontjai közötti zárlat mindig ekvivalens a kapuhoz tartozó elakadási hibával, akár ÉS-zárlatról, akár VAGY-zárlatról is van szó. Az elakadási hibákat felfedő tesztekről megállapítható, hogy igen alapos, átfogó vizsgálatot hordoznak magukban az általános értelemben vett működésre nézve, ami a hibamodellhez tartozó tesztkészletek hatékonysága mellet szól. Az ilyen hibákat felfedő teljes tesztkészlet végrehajtása után a következő megállapítást tudjuk tenni a vizsgált áramkörről: Ha nem volt hibás válasza, akkor mindegyik hálózati pont 0-ból 1-be, valamint 1-ből 0-ba vezérelhető, miközben a hálózat egésze is helyes működést mutat. Mondhatjuk azt, hogy a hálózat „mindegyik ízülete megmozgatható”. Az egyszerűség kedvéért a továbbiakban csak a hálózati csomópontok elakadási hibáival foglalkozunk, a logikai elemek bemeneti pontjain nem tételezünk fel külön hibát. Ez azt jelenti, hogy a hibák az elsődleges bemeneteken, valamint az elemek kimeneti pontjain jelentkeznek. (Könnyen belátható, hogy ez nem jelent semmilyen elméleti megszorítást, csak a tárgyalást egyszerűsíti.) A következő öt alpontban olyan determinisztikus tesztszámító módszerek, algoritmusok bemutatásra kerítünk sort, amelyek kizárólag kombinációs hálózatokra vonatkoznak. Ebben a tárgyalásban kapu szintű hálózatokkal foglalkozunk. A szekvenciális hálózatok, továbbá a kapu szintnél magasabb rendű, modul szintű, ill. funkcionális szintű hálózatok tárgyalását a fejezet későbbi alpontjai tartalmazzák. 2.1.2 Kapu szintű tesztelés Mint ismeretes, a kombinációs hálózatok felépítésükben és működésükben jóval egyszerűbbek a sorrendi hálózatoknál. Ennek tulajdonítható, hogy a logikai tesztelés irodalma először ezt a hálózattípust tárgyalta. Jelenleg már számos kidolgozott hatékony módszer ismeretes, amely alkalmas a tesztszámítási feladatok megoldására. A hálózatokról feltételezzük, hogy kizárólag logikai kapukból vannak felépítve. Az ilyen felépítést kapu szintűnek nevezzük. A meghibásodható pontok az elsődleges bemenetek és a kapuk kimenetei. Ezek hibáiról elmondható, hogy kimutatásukra mindig elegendő egyetlen

9

bemeneti jelkombináció. Ha erre a hibás áramkör olyan kimeneti kombinációval válaszol, ami a helyestől eltér, az adott input a hiba tesztje lesz. A hibaterjesztés fogalma: Ahhoz, hogy egy hiba detektálható legyen a hálózat kimenetén, nyilván arra van szükség, hogy a hiba hatása eljusson a kimenetig. Ezt a feltételt egy olyan input kombináció teljesíti, amelynek a jelenléte esetén a hiba hatására egy vagy több elsődleges kimeneti változó megváltoztatja helyes logikai értékét. A teszt által eredményezett jelenséget hibaterjesztésnek nevezzük (angolban: fault propagation). Egy hiba hatása akkor és csak akkor terjed tovább, ha a terjedése mentén előforduló valamennyi kapu kimeneti értékét a helyes logikai érték ellenkezőjére változtatja. Ez más megfogalmazásban azt jelenti, hogy a hiba terjedése mentén mindenütt egy-egy hibajel áll elő, egészen az elsődleges kimenetig. Ha egy adott kapu egyik bemenete hibás, ennek hatása kizárólag akkor rontja el a kapu kimeneti értékét, ha egyedül a hibás érték szabja meg a kimeneti értéket. Ezt viszont a kapu hibátlan bemeneteire adott megfelelő értékekkel tudjuk biztosítani. Ha például egy ÉS-kapu hibátlan bemenetein logikai 1 van, akkor az itt kívánt feltételt értük el. VAGY-kapu esetén ilyenkor 0-ra van szükség a hibátlan bemeneteken. Az egybemenetű inverter ugyanakkor mindig átbocsátja a hibajelet. Ha egy hálózati út mentén levő kapuk azon bemenetein, amelyek nem tartoznak az úthoz, a kapuk egyenkénti hibaátbocsátását biztosító logikai értékek vannak, akkor az utat aktívnak, hangoltnak vagy érzékenynek nevezzük. Egy aktív út mindegyik kapuja ugyancsak aktív (hangolt vagy érzékeny). (Az angol elnevezés: sensitive path.) A logikai értékeknek az út aktivitását biztosító kijelölését az út aktivizálásának, hangolásának vagy érzékenyítésének nevezzük. (Angolul: path sensitization.) Nagyon lényeges még egy másik tény is: a továbbterjesztésnek szükséges feltétele, hogy maga a hiba is detektálható legyen a keletkezési helyén, vagyis az elakadási logikai érték eltérő legyen a hibás ponton várt helyes logikai értéktől. Tehát a hibajelnek a hiba keletkezési helyén is meg kell jelennie. Magától értetődik ugyanis, hogy ellenkező esetben a hiba sehol sem éreztetné hatását. Ezeken a meggondolásokon alapul az a módszer, amelyet D. B. Armstrong (USA) publikált 1966-ban. A következőkben ezt a módszert vázoljuk fel. Armstrong módszere: Az Armstrong-féle eljárás egyszeres hibákra vonatkozik, és két számítási fázisból áll: 1) Az első fázisban a hiba helyéhez az elakadási szinttel ellentétes logikai értéket rendeljük. Ezután a hiba helyétől valamelyik elsődleges kimenetig egy lehetséges jelterjedési utat választunk ki. Az út mentén található kapuk azon bemeneteihez, amelyek nem elemei az útnak, a kapuk hangolását biztosító logikai értékeket rendeljük: ÉS-kapu, NAND-kapu estén 1-eseket, VAGY-kapu, NOR-kapu esetén 0-kat. 2) Miután a kiválasztott utat hangoltuk, a második fázisban szisztematikus próbálgatásokkal olyan logikai értékeket keresünk a kapuk bemeneteihez, melyek az első fázisban kijelölt

10

értékeket eredményezik. Ha sikerül az elsődleges bemenetekhez visszajutva ellentmodásmentesen megvalósítani a sorozatos hozzárendelést, akkor ezzel az adott hiba tesztjét kapjuk meg. Sikertelenség esetén egy újabb lehetséges út kiválasztására kerül sor, az eljárás megismétlésével. Armstrong módszeréről megállapítható volt, hogy nem mindegyik detektálható hibához képes tesztet találni. Ezt legkönnyebben egy ellenpéldán tudjuk illusztrálni, amit E. C. Schneider (USA) publikált 1966-ban. A példa hálózata a 2.3. ábrán látható.

8

5 x1 x2 x3

9 6

12

(0) 10

x4 7

11 - Hálózati hiba: 6(0).-

2.3. ábra: A Schneider-féle példa kombinációs hálózata Tegyük fel, hogy a 6(0) hibához keresünk tesztet. A 6-os pontból a z1-nek megfelelő 12-es elsődleges kimenetig a P(6-9-12) és a P(6-10-12) utak léteznek. Ahhoz, hogy a hibamentes hálózatban a 6-os ponton logikai 1 legyen, x2 = 0

és

x3 = 0

szükséges. Az első út aktivizálási feltétele: x1 = 0,

g8 = 0,

g10 = 0,

g11 = 0.

Esetünkben g10 = 0-hoz x4 = 1 szükséges (g6 értéke a hiba miatt 0), g11 = 0-hoz viszont g7 = 1, ami x4 értéke miatt feloldhatatlan ellentmondás. Ez azt jelenti, hogy az első út önmagában véve nem aktivizálható. Ugyanez adódik a második út esetében is. Mindezek ellenére az adott hibának létezik tesztje, mégpedig a (0, 0, 0, 0) bemeneti vektor, amiről könnyen meggyőződhetünk.

11

z1

Vegyük észre, hogy a módszer eredménytelensége itt abból adódott, hogy egyszerre csak egy utat próbált meg aktivizálni, holott a 6(0) hiba tesztje mindkét lehetséges utat egyidejűleg aktivizálva tud érvényesülni. A két hibaterjesztési út azonban olyan, hogy egy pontban kétfelé ágazik, majd ismét találkozik a 12-es kapunál, vagyis a 2.1 alpontban szereplő definíció szerint rekonvergens. Általánosan is megállapítható, hogy az Armstrong-módszer a rekonvergencia miatt nem alkalmas mindegyik hiba tesztjének előállítására. Ennek a hiányosságnak a kiküszöböléséhez tehát olyan módszerre van szükség, amely képes arra, hogy egyidejűleg egynél több utat is aktivizálni, hangolni tudjon. Egy ilyen megoldást vázolunk fel a következő alpontban. 2.1.3 A D-algoritmus A többszörös úthangolás megvalósítására dolgozta ki J. P. Roth (USA) 1966-ban az általa Dalgoritmusnak nevezett tesztszámító eljárást. Roth bebizonyította, hogy a D-algoritmus felhasználásával bármelyik detektálható elakadási hiba összes létező tesztje előállítható. A Dalgoritmus ugyancsak alkalmas a többszörös hibák tesztjeinek kiszámítására is. Az algoritmus alapelve abban áll, hogy a hiba helyétől az elsődleges kimenetekig vezető különböző lehetséges útkombinációkat egyidejűleg kísérli meg aktivizálni. Ha egy aktivizálási procedúra tesztet eredményez, akkor célhoz értünk, ellenkező esetben egy újabb útkombináció kiválasztására kerül sor. A D-algoritmus úgy van szervezve, hogy mindegyik lehetséges útkombinációt végig tudja vizsgálni. A számítások ún. hálózati vektorok vagy kockák (Roth elnevezése: cube) között definiált műveletek elvégzésével hajtandók végre. A k csomópontból álló hálózathoz a k komponensből álló v = (v1, v2, …, vk) hálózati vektor tartozik, ahol vi az i-edik csomópont logikai értéke. A D-algoritmus 5-értékű logikai rendszert alkalmaz, a következő értékek halmazával: {0 1, d, D, D’} Ebben a halmazban d az ún. közömbös érték. Jelentése: vi = d esetén az aktuális számítások szempontjából mindegy, hogy milyen határozott érték szerepel az i-edik ponton. A D jelentése a következő: vi = D esetén az i-edik ponton a helyes logikai 1 helyett a hibás 0 érték van jelen. (Roth a discrepancy szóból vette a betűt.) Ha a hibajelet úgy definiáljuk, hogy egy törtvonal baloldalán a helyes, jobb oldalán a hibás érték szerepel, akkor írhatjuk, hogy D = 1/0. A D-algoritmusnak nevet adó D logikai érték tehát nem más mint egy konkrét hibajel. Ugyanígy értelmezhető a D hibajel inverze, a D’ is. Eszerint a D’ jelentése a következő: vi = D’ esetén az i-edik ponton a helyes logikai 0 helyett a hibás 1 érték van jelen, vagyis D’ = 0/1.

12

A fenti értelmezés már sugallja, de mégis fontosnak tartjuk itt kiemelni, hogy az értékhalmazban szereplő 0 és 1 önmagukban véve mindig a hálózati pontok helyes logikai értékét képviselik, még hiba jelenlétekor is. A logikai értékek között definiálva vannak a Boole-műveletek. A 0-ra és 1-re nézve a kétértékű logikára érvényes műveletek vonatkoznak. A többi esetben az értékek definíciója alapján tudjuk értelmezni a műveleteket. Például: az ÉS-művelettel D 1 = D,

D 0 = 0,

D D = D,

D D’ = 0,

D + 0 = D,

D + D = D,

D + D’ = 1.

a VAGY-művelettel D + 1 = 1,

Ami az invertálást illeti, ott egyedül d esetében teljesül az, hogy d’ = d, vagyis a közömbös érték inverze is közömbös marad. Egy i(α) egyszeres elakadási hibára vonatkozóan a D-algoritmus menete a következő: 1) Kiindulásként a hálózati vektor mindegyik komponense d értéket kap. A hiba keletkezési helyén α konkrét értékétől függően D-t vagy D’-et veszünk fel: Ha α = 0, akkor gi = D, ha pedig α = 1, akkor gi = D’. Ezután a hibátlan gi = α’ értéket biztosító bemeneti kombinációt vesszük fel a hibás kimenetű kapu bemenetein. A Schneider-példán ez a következő hálózati vektort jelenti: v = (d, 0, 0, d, d, D, d, d, d, d, d,d). 2) A kezdeti értékek beállítása után a hibaterjesztési fázisra kerül sor. Roth ezt a folyamatot D-terjesztésnek (D propagation) nevezte el. Ennek célja az, hogy a hibajel D vagy D’ alakban legalább egy elsődleges kimenetre jusson el úgy, hogy a még szükséges 0 és 1 értékek ellentmondásmentes hozzárendelése is megtörténjen a hálózati pontokhoz. A D-terjesztés végrehajtásához mindegyik kapuhoz ún. D-terjesztési vektorok állíthatók elő. (Roth elnevezése: propagation D cube.) E vektorokban egy kapu bemeneti pontjainak olyan értékkombinációi szerepelnek, amelyek valójában a kapu lehetséges aktivizálási feltételeit fejezik ki. Olyan logikai feltételeket, melyek szerint a kapu egy vagy több bemenetére érkező hibajel miként terjeszthető a kapu kimenetére. (Egy kapu bemenetei között lehet egynél több hibás értékű is, hiszen a kiválasztott hálózati hiba hatása egynél több úton is eljuthat a kapuhoz.) A 2.3. ábra 12-es kapujához többek között például a (d, d, d, d, d,d, d, D, 0, 0, 0, D’),

(d, d, d, d, d,d, d, 0, D, D, 0, D’),

(d, d, d, d, d,d, d, D’, 0, 0, 0, D),

(d, d, d, d, d,d, d, 0, D’, D’, 0, D)

D-terjesztési vektorok generálhatók.

13

Az algoritmus az először meghatározott hálózati vektorból kiindulva szisztematikusan, lépésenként kísérli meg olyan újabb vektorok kiszámítását, amelyek kifejezik, hogy milyen logikai értékek teszik lehetővé a hibának a különböző lehetséges utakon való terjesztését. Itt egy számítási lépés abból áll, hogy egy hibaterjesztési részeredményt tartalmazó vektornak képezzük az ún. D-interszekcióját egy olyan kapu D-terjesztési vektorával, amelyen át lehetőség van a hiba továbbjuttatására. Ezeket a műveleteket mindaddig végezzük, amíg az összes kapott eredményvektorban a D vagy D’ nem terjeszthető tovább. A Roth által definiált D interszekció valójában két vektor közötti művelet, amelyben az eredményvektor a két műveleti vektor azonos helyen levő komponenseinek „interszekciójával” áll elő”. Jelöljük ezt a műveletet hullámvonallal (∼). Példaként néhány eset: 0 ∼ 0 = 0, D ∼ D = D,

1 ∼ 1 = 1,

0 ∼ d = 0,

D’ ∼ D’ = D’, D ∼ d = D,

1 ∼ d = 1, D’ ∼ D’ = D’.

Az ellentétes logikai értékek, valamint a D, D’ és a határozott értékek között a művelet nincs megengedve, vagyis nem ad eredményt. Ilyenek például a 0 ∼ 1, D ∼ 0, D ∼ 1, D ∼ D’ műveletek. Belátható, hogy az értelmezett esetekben az adott logikai értékek nincsenek egymással ellentmondásban, a nem értelmezett esetekben viszont igen. Azok az eredményvektorok, amelyekben a D vagy D’ a hálózat egy vagy több kimenetén szerepel, kifejezik a hibaterjesztésben részt vevő utak együttes aktivizálási feltételeit. Ha a Schneider-példában a 6(0) hibához elvégezzük az összes lehetséges D-terjesztést, akkor a következő három eredményvektorhoz jutunk: v1 = (0, 0, 0, d, d, D, d, 0, D’, 0, 0, D), v2 = (d, 0, 0, 0, d, D, d, 0, 0, D’, 0, D), v3 = (0, 0, 0, 0, d, D, d, 0, D’, D’, 0, D). Az eredményekből látható, hogy v1 a P(6-9-12), v2 a P(6-10-12), míg v3 az előző két út együttes aktivizálási feltételét fejezi ki. Ebben a stádiumban a hátralevő feladat azoknak a hiányzó 0 és 1 értékeknek a kijelölése, amelyek ellentmondásmentesen biztosítják egy adott eredményvektorban levő 0 és 1 értékek teljesülését. Az erre szolgáló, szisztematikus próbálkozásokból álló műveletsorozatra a továbbiakban az összehangolási eljárás elnevezést használjuk. (Roth elnevezése: consistency operation. A másik, ennél jóval elterjedtebb angol elnevezés: line-value justification.)

14

3) Az összehangolás egy szisztematikus eljárás, amelynek során egymás után jelölünk ki határozott logikai értékeket a hálózati elemek kimenetein úgy, hogy azok logikailag összhangban legyenek az elemek kimeneti értékeivel, valamint a már korábban elhelyezett értékekkel. Ilyenkor kizárólag a kimenetek 0 és 1 értékeit kell a bemeneti oldalról biztosítani, d-t nem. A D és D’ már nem vesznek részt ebben a folyamatban. . Az eljárás mindaddig tart, amíg az elsődleges bemenetekig nem jutunk. Az összehangolás során fellépő ellentmondások feloldására az előző döntések szisztematikus megváltoztatását kíséreljük meg. Ezzel így egy ún. visszakövetéses döntéssorozatot hajtunk végre. (Ez angolul: backtracing vagy backtracking.) Egy régebbi döntés megváltoztatása után töröljük az akkori döntés összes következményeit, vagyis a döntés óta kiosztott logikai értékeket, és az új döntéstől folytatjuk tovább az összehangolást. Eben az eljárásban nagyon fontos, hogy egy kapu bemenetein mindig elég a minimálisan szükséges feltételt előírni a kimenet biztosításához. Más szóval ez azt jelenti, hogy minél kevesebb határozott értéket kell a bemenetekhez rendelni. A don’t care érték visszakövetésére ugyanis nincs szükség. Például: ÉS-kapunál, ha a kimenet 0, elég az egyik bemenetre 0-t tenni, a többi maradhat d. A példánkban szereplő hálózat D-terjesztési vektorait tekintve, az összehangolás eredményeként a v1 és v2 vektorokhoz nincs konzisztens megoldás, míg a v3-hoz van: v = (0, 0, 0, 0, 1, D, 1, 0, D’, D’, 0, D). A végeredményként kapott vektorból kiolvasható a 6(0) hiba tesztje, ami az ismert x = (0, 0, 0, 0) vektor. Többszörös hibák kezelése: A D-algoritmus kiterjeszthető többszörös hibákra is. Ekkor azonban a számítási mennyiség lényegesen megnövekszik. A következőkről van szó ugyanis: Ha egynél több szimultán hiba van, akkor nem biztos, hogy azok tesztje mindegyiket terjeszti. Hogy melyik hiba hatását kell elindítanunk és melyiket nem, azt előre nem lehet tudni. Ami biztos, az annyi, hogy legalább egy hibát mindig terjeszteni kell. Ha egy hibát terjeszteni akarunk, akkor a helyére D-t vagy D’-t kell írnunk. Ha kizárjuk a terjesztésből, akkor a hibátlan hálózatban a hiba helyére az elakadási szintet kell előírnunk. Ha az együttes hibák száma q, akkor az összes lehetséges q hibaindítási kombináció száma 2 – 1 lesz. Ez azt jelenti, hogy legrosszabb esetben ennyiszer kell a teljes D-algoritmust végrehajtanunk, amíg tesztet találunk, vagy kiderül, hogy nem létezik teszt. Végezetül még szükségesnek tartjuk megjegyezni, hogy a D-algoritmust igen sokan vizsgálták és további módosításokat, javításokat dolgoztak ki rá vonatkozóan. Ezek közül leginkább az a továbbfejlesztett változat érdemel említést, amelyet P. Muth (Németország) publikált 1976-ban. Ebben az eredeti 5-értékű logika helyett Muth egy 9-értékűt javasolt, ami a végigpróbálandó hibaterjesztési útkombinációk számának lényeges csökkenésére vezet, vagyis gyorsítja az eredeti D-algoritmust.

15

2.1.4 A Boole-differenciák módszere Az előző két alpontban ismertetett számítási elvek magukban hordozzák a sikertelen próbálkozások lehetőségét. A következőkben egy olyan megoldással foglalkozunk, amelyben ez a tulajdonság jóval kevesebb szerepet játszik. Ez abból adódik, hogy itt a hálózat viselkedését leíró Boole-függvényeket használjuk fel, és a megfelelő logikai kifejezések között kell előre megszabott logikai műveleteket elvégezni. Ezt, az ún. Boole-differenciákon alapuló megközelítést először F. F. Sellers és társai (USA) vetették fel 1968-ban. Azóta számtalan publikáció jelent meg, amely ezzel a megoldási móddal foglalkozik. A Boole-differencia definíciója: Egy n-változós zj(x1, x2,…, xn) = zj(x) logikai függvénynek az xk változójára vonatkozó Boole-differenciája dzj / dxk = dzj(x1, x2,…, xn) / dxk = = zj(x1,…, xk,…, xn) ⊕ zj(x1,…, x’k,…, xn),

(2.1)

ahol a ⊕ műveleti jel a KIZÁRÓ VAGY-ot (XOR) képviseli. Bizonyítható, hogy a (2.1) kifejezhető a dzj / dxk = zj(x1,…, xk-1, 1, xk+1,…, xn) ⊕ ⊕ zj(x1,…, xk-1, 0, xk+1,…, xn)

(2.2)

összefüggéssel is. Ez azt jelenti, hogy az xk-ra vonatkozó Boole-differencia csak az xk-tól különböző n-1 darab változó függvénye. Az XOR művelet definíciója alapján könnyen igazolható, hogy ha dzj / dxk = 1,

akkor

zj(x1,…, xk-1, 1, xk+1,…, xn) ≠ ≠ zj (x1,…, xk-1, 0, xk+1,…, xn). Másrészt, ha dzj / dxk = 0,

akkor

zj(x1,…, xk-1, 1, xk+1,…, xn) = = zj (x1,…, xk-1, 0, xk+1,…, xn). Mindebből következik, hogy annak szükséges és elégséges feltétele, hogy az xk változó logikai értéke befolyásolja zj értékét, dzj / dxk = 1. 16

A (2.1)-hez hasonlóan, általánosan a következő formában definiálhatjuk egy kombinációs hálózat zj(x1, x2,…, xn) = zj(x) kimeneti függvényének egy gi(x1, x2,…,xn) = gi(x) függvényre vonatkozó Boole-differenciáját: dzj / dgi = zj(x, gi(x)) ⊕ zj(x, gi’(x)) = = zj(x, gi = 1) ⊕ zj(x, gi = 0).

(2.3)

Az általánosítás szerint gi(x) = xk esetén (2.3) a (2.1) és (2.2) képletekbe megy át. Az i(α) hibát a zj kimeneten detektáló tesztnek biztosítania kell, hogy zj értékét befolyásolja a gi. Ennek viszont szükséges és elégséges feltétele, hogy dzj / dgi = 1

(2.4)

teljesüljön. A tesztnek emellett a hibamentes hálózatban a gi(x1, x2,…, xn) = α’

(2.5)

értéket kell eredményeznie. Ugyanis a (2.4) feltétel teljesülése garantálja, hogy az egymással ellentétes gi értékekre a zj is ellentétes értékpárral válaszol. Ugyanakkor a (2.5) feltétel az iedik pont helyes logikai értékét írja elő, ami hiba esetén ellentétesre változik, s így a hiba hatása megfigyelhető lesz a zj kimeneten: a zj értéke különbözni fog a hibamentes esethez tartozó logikai értékétől. Mindet tehát azt jelenti, hogy egy bemeneti kombináció akkor és csak akkor lehet i(α) tesztje, ha megoldása a (2.4) – (2.5) logikai egyenletpárnak. Az egyenletpárt tehát az elsődleges bemeneti változókra mint ismeretlenekre nézve kell megoldani. A megoldásokat a következő úton kapjuk meg: A Boole-differenciát a (2.3) szerint gi = 1, gi’ = 0 helyettesítéssel állítjuk elő. Először képezzük a két egyenlet logikai szorzatát. Esetünkben ez azt jelenti, hogy α = 0-ra (2.4) baloldala a gi tényezővel, α = 1-re pedig gi’-vel bővül, míg a jobboldal marad logikai 1. Az így előállt egyenletet a logikai függvények közti műveletek elvégzésével olyan alakra hozzuk, ami a negált és nem negált bemeneti változók logikai szorzatainak összegéből áll, vagyis az ún. diszjunkt forma alakul ki. Mivel a teljes kifejezés logikai értéke 1, ezért sorban mindegyik tagját 1-gyel téve egyenlővé, az így kapott egyenletekből azonnal kiolvasható az őket kielégítő egyetlen bemeneti kombináció. Eszerint az egyenletnek annyi különböző megoldása van, ahány különböző tagból áll a végső alak. Például: x1’ x2 x3 x4’ = 1

megoldása

(0, 1, 1, 0).

Példaként tekintsük a 2.1. ábrán szereplő hálózatot, a 6(0) hibával. A hálózat kimeneti függvénye a g6 bevonásával: z1(x, g6) = x1 x2 x3 x4 + x2 x3 x4 g6 + x1 x2 x3 g6 + x2 x3 g6 + x1’ x2’ x3’ x4’ g6. A számítások elvégzésével 17

dz1 / dg6 = x1’ x2 x3 x4 + x1 x2 x3 x4’ + x1’ x2 x3 + x2 x3 x4’ + x1’ x2’ x3’ x4’. Mivel g6(x) = (x2 + x3)’ = x2’ x3’, ezzel a 6(0) hiba tesztje (dz1 / dg6) g6(x) = x1’ x2’ x3’ x4’ = 1 alapján a már ismert (0, 0, 0, 0) bemeneti vektor lesz. A gyakorlatban a logikai hálózatoknak általában 1-nél jóval több elsődleges kimenete van. Számunkra viszont egy hibához elegendő egyetlen teszt előállítása, ezért elegendő egyetlen kimenetre elvégezni a fenti számításokat. Ha viszont egy adott kimenethez nem találunk tesztet, akkor egy újabb kimenet kiválasztására kerül sor. Legrosszabb esetben tehát mindegyik kimenetre végre kell hajtani az algoritmust. Többszörös hibák kezelése: A Boole-differenciák módszere ugyancsak kiterjeszthető többszörös hibák tesztjeinek számítására is. A számítások elve követi a D-algoritmusnál bemutatott elvet. Ebben az esetben is azt kell figyelembe vennünk, hogy az egyidejűleg fennálló hibák különböző terjesztési-nem terjesztési kombinációkban kapcsolandók be a számításokba. Egy ilyen kombinációt egy Boole-egyenlet tud kifejezni, amit meg kell oldani. Ha a hibák multiplicitása q q, akkor a legrosszabb esetben most is 2 – 1 alkalommal kell végrehajtani a Booledifferenciák módszerét, mégpedig egyetlen kimenetre vonatkozóan. Ahhoz, hogy egy hiba ne terjedjen, arra van szükség, hogy az előfordulási pontjára az elakadási szinttel megegyező logikai érték kerüljön. Ekkor az i hibás pont logikai függvénye a hibaszinttől függően a következő formában vesz részt a megoldandó Boole-egyenletben: Ha i(α)-ban α = 0, akkor gi = 0 kell, vagyis gi’ lesz az egyenletben szereplő szorzótényező,

míg α = 1 esetén gi = 1 kell, és a gi vesz részt a szorzatban. A terjedés-nem terjedés aktuális esetét a Boole-differenciában is figyelembe kell venni. Ekkor az a függvény, amelyhez tartozó hiba nem terjesztendő, nem kerül bele a Boole-differencia egyik tagjába sem, mivel a két tag nem térhet el egymástól az adott függvény miatt. Például, ha az i(0) és a k(1) hibapár tesztjét úgy akarjuk meghatározni, hogy i(0)-at terjesztjük, k(1)-et pedig legátoljuk a terjesztésben, akkor a megoldandó Boole-egyenletünk a következő alakot veszi fel: gi gk [ zj (x, gi = 1) ⊕ zj(x, gi = 0)] = 1. Abban az esetben, amikor mind a két hibát terjeszteni akarjuk, a következő egyenlet megoldására lesz szükség: gi gk’ [ zj (x, gi = 1, gk = 0) ⊕ zj(x, gi = 0, gk = 1)] = 1. Az utóbbi egyenletben szereplő szögletes zárójeles tényezőt kettős Boole-differenciának nevezzük. Az elnevezés onnan ered, hogy két belső változó egymástól való eltérését, differenciáját fejezi ki. Ezen az alapon természetesen létezik az n-szeres Boole-differencia fogalma is, amelyben n számú változó eltérése van leírva.

18

2.1.5 A PODEM és a FAN algoritmus A P. Goel (USA) által 1981-ben publikált PODEM (Path-Oriented DEcision Making) algoritmus öt logikai értékkel dolgozik. Kapu szintű kombinációs hálózatok egyszeres elakadási hibáit képes kezelni. A gyakorlati tapasztalatok szerint jóval hatékonyabb a Dalgoritmus 5-értékű változatánál. Kifejlesztésekor a szerző a következő gondolatmenetet követte: A D-algoritmus működése során a vizsgált hálózat belső csomópontjaira rögzít logikai értékeket, holott az elsődleges bemenetek logikai értékei egyértelműen meghatározzák bármely belső csomópont logikai értékét. Így, mivel egy hálózatnak általában jóval több belső csomópontja van, mint elsődleges bemenete, a D-algoritmusnak sokkal több döntési lehetőséggel kell számolnia mint egy olyan algoritmusnak, amely csak az elsődleges bemenetekre köt le értékeket. Ezáltal a helytelen, vagyis fölösleges döntések esélye is jóval nagyobb a D-algoritmusban. A PODEM ezért nem végez összehangolást, hanem olyan kombinációt keres az elsődleges bemenetekre, amely az elérni kívánt cél felé vezet. A cél, mint minden módszernél, ebben az esetben is kétféle lehet: A hiba aktivizálása és hatásának kiterjesztése egy elsődleges kimenetre. Ezzel a megoldással a PODEM jelentősen szűkíti a döntési teret, hiszen az csak az elsődleges bemenetekhez tartozó csomópontokból áll. Ráadásul látszólag megtakarítottuk az összehangolást is a D-algoritmushoz képest. A fentiek alapján a PODEM a következő fő lépésekre bontható: 1. A hiba kiválasztása 2. Olyan elsődleges bemeneti kombináció keresése, amely aktivizálja a hibát. Ha nem sikerül megfelelőt találni, akkor a kiválasztott hiba tesztelhetetlen. 3. Ha a hiba hatása elért egy elsődleges kimenetet, akkor az elsődleges bemeneteken egy tesztvektor van. Ebben az esetben itt befejeződik a számítás az adott hibára. 4. Egy célcsomópont kijelölése, ahová a hiba hatását tovább szeretnénk terjeszteni. Amennyiben az összes lehetséges aktivizált úttal megpróbálkoztunk már, a célcsomópontok különböző kijelölésén keresztül, akkor a kiválasztott hiba tesztelhetetlen. 5. Olyan elsődleges bemeneti kombináció keresése, amely a hiba hatását a kiválasztott csomópontra terjeszti. 6. Ugrás a 3. pontra. A döntési tér szűkülése és az összehangolás elhagyása magyarázatul szolgálhatna a jelentős hatékonyságnövekedésre a D-algoritmussal szemben. Mindazonáltal az összehangolás megtakarítása látszólagos, a hatásfok növekedése nem ezekben az okokban keresendő. A PODEM, az elsődleges bemenetek megfelelő logikai értékeit egy adott cél elérése érdekében, egy heurisztika segítségével választja meg. Most vizsgáljuk meg, hogyan is történhet ez a választás: • •

Lehet véletlenszerű a választás az összes elsődleges bemenetre, de ez a megoldás gyakorlatilag a random tesztgenerálással lenne egyenértékű. A véletlen értékek generálását korlátozhatjuk a célcsomópontot meghajtó elsődleges bemenetekre és kizárhatjuk a már kipróbált kombinációkat. Ez a megoldás már valószínűleg hatékonyabb az előzőnél, de várhatóan még mindig rosszabb, mint a topológiai információkat is figyelembe vevő összehangolás a D-algoritmusban.

19

•

Végül egy elsődleges bemenet értékére tehetünk javaslatot, a célcsomópont kívánt logikai értékét az áramkörben az adott elsődleges bemenethez vezető úton visszakövetve. Egy ilyen módszer viszont minél pontosabb becslést ad, bonyolultságában annál közelebb áll a D-algoritmusban használt összehangoláshoz, hiszen a visszakövetés egy-egy lépésében is adminisztrálnunk kell a visszakövetett értéket, az pedig, hogy ezt az adminisztrációt érték lekötésnek tekintjük-e már csak értelmezés kérdése. Sőt, ha a visszakövetés köztes eredményeit értéklekötésként kezeljük és ezek alapján implikációt is végzünk, a döntési tér gyorsabban szűkülhet illetve a konfliktusok előbb kiderülhetnek. (Implikáció: az 1 és 0 logikai értékek további biztos értékhatásának meghatározása a hálózatban.)

Miben áll tehát a hatékonyságnövekedés? Mivel a PODEM elsőnek publikált változatában az összehasonlítás alapja az 5-értékű D-algoritmus volt. Ennek pedig épp az volt a gyengéje, hogy a visszakövetés során a szűk értékkészlet miatt egyes belső csomópontokra gyakran pontatlan vagy hibás megkötéseket tett. A szintén öt logikai értéket használó PODEM-nél ez a probléma nem jelentkezhetett, hiszen a belső csomópontok egy elsődleges bemenet, az 5értékű logikában szereplő, 1 vagy 0 értékre történő lekötését követő implikáció során kaptak értéket. Így tehát, a PODEM esetében az 5-értékű logika nem okozott pontatlanságokat vagy hibákat. Összefoglalva tehát az eddigieket, úgy tűnik, hogy csak a D-algoritmus túl nagy információveszteséggel dolgozó 5-értékű változatához képest jelentett egyértelmű haladást a PODEM. Az állítást alátámasztja, hogy a D-algoritmus 9-értékű változata nem marad el hatékonyságban a PODEM mögött. A PODEM-nek is számos módosított változatát publikálták. Ezek közül a legjelentősebb, a heurisztikák alkalmazására épülő, 5-értékű, kapu szintű FAN (FANout-oriented test pattern generation algorithm) algoritmus. (H. Fujiwara és T. Shimono, Japán, 1983.) A PODEM-hez képest további, a döntési visszalépések számának csökkentését célzó megoldásokat foglal magában • •

•

•

Minden értéklekötés után előre- és hátrafelé implikációt hajt végre. Megfelelő aktivizált értéket vesz fel azokra a csomópontokra, amelyeken biztosan áthalad az adott hibahelyről kiinduló aktivizált út, azaz ahol a D-terjesztési front egyetlen kapura szűkül, továbbá az ilyen csomópontok hibaterjesztésben részt nem vevő kapubemeneteire nemvezérlő kombinációt allokál. Az előző pont alapján lekötött csomópontok összehangolása :Így tehát a PODEM-mel ellentétben a FAN-ben több célcsomópont létezhet egyszerre, ezért az ezek biztosítását végző procedúrát többszörös visszakövetésnek (Multiple Backtrace) hívják. Emellett a FAN többszörös visszakövetése, -a PODEM egyszeres út mentén végzett visszakövetésével szemben-, a D-algoritmushoz hasonlóan többszörös utat is képes kezelni. Ez a megoldás viszont elvében és így bonyolultságában megegyezik a Dalgoritmusban használt összehangolással. A több ágon történő visszakövetést azonban a FAN szélességi jelleggel végzi, ami kevésbé hatékony, mint a mélységi jellegű megoldás. A különbség abból adódik, hogy a kapuk inverz működését leíró függvény általában nem egyértelmű, így előrefelé gyakrabban végezhető implikáció, mint hátra. Ha pedig mélységében végezzük az összehangolást, akkor növeljük az előrefelé ható implikációk lehetőségének az esélyét és így gyorsabban szűkül a döntési tér. Azok az áramköri csomópontok (ún. bead-line-ok), amelyeknek hátrafelé vetülő árnyéka független az áramkör többi részétől, fa struktúrájú és nem tartalmazza a hibahelyet, biztosan visszalépés nélkül leköthető akár 1 akár 0 értékre, ezért a FAN-ben az összehangolás csak ezekig a pontokig folyik első lépésben. Ennek oka az, hogy mivel ezen csomópontok esetében biztos sikerre számíthatunk, összehangolásukat

20

elhalaszthatjuk akkorra, amikor már minden egyéb, egy teszt előállításához szükséges munkát elvégeztünk. Így ha a tesztszámítás során vissza kell vonnunk egy döntést, nem végeztünk felesleges munkát a bead-line-ok összehangolásával. A FAN algoritmust közlő publikáció a PODEM-mel végzett összehasonlításokat. A kísérlet során minden elakadási hibát figyelembe vettek, és minden teszt előállítása után végeztek hibaszimulációt. A számításokat 10 és 1000 nagyságú visszalépési korláttal végezték. Megítélésem szerint a két eredménysorozat közül csak az elsőnek van gyakorlati jelentősége, az ezres korlát esetében észlelhető rohamos számításiidő-növekedés miatt. Emellett megállapítható, hogy a FAN algoritmus jelentősen hatékonyabb a PODEM hasonló körülmények között implementált változatánál. Egyedüli hátránya a sok KIZÁRÓ VAGYkaput (XOR-kaput) tartalmazó hálózatok kezelésében mutatkozik meg. Ennek oka valószínűleg az, hogy a FAN elemkészlete nem tartalmazza a KIZÁRÓ VAGY-kaput. Azokat a hálózatmodell előállítása során ekvivalens, három kapuból álló kapcsolással helyettesíti. Ez a megoldás a kapuszám növekedésén túl, újabb rekonvergens utakat is behoz a hálózatba. Áttekintve az ismertetett módszerekre vonatkozó publikált futási eredményeket, arra a véleményre juthatunk, hogy a D-algoritmus és a PODEM fejlettebb változatai között nincs lényeges hatásfokbeli eltérés. Az apróbb különbségek nagyrészt az alkalmazott heurisztikus megoldásoknak és az algoritmusok hálózatfüggőségének tudhatók be. 2.1.6 A kettős összehangolás A kettős összehangolás algoritmusa szintén a logikai értékek szisztematikus próbálgatással történő elhelyezésével képes tesztet számítani akár egyszeres, akár többszörös hibához. Az algoritmus végrehajtási módjából következően gyakorlatilag nincs különbség az egyszeres és többszörös hibák kezelésére fordítandó számítási mennyiségben, ami szembetűnő különbség az eddig ismertetett módszerekhez képest. A kettős összehangolást (angol elnevezése: composite justification) Sziray J. publikálta 1979-ben (USA, Stanford Egyetem). A módszer a következő meggondolásokon alapul: Tegyük fel, hogy q ≥ 1 számú hibához keresünk tesztet úgy, hogy a hibadetektálási kimenetünk zj. Ezen tesztvektor meghatározásának feladata a következő módon is megfogalmazható: Előállítandó egy olyan bemenő kombináció, amelyre nézve a hibátlan és a hibát tartalmazó hálózati változatok legalább egy elsődleges kimeneti értékben különböznek. Legyen ez a zj értéke. E cél elérése érdekében zj-hez egy β értéket rendelünk, ahol β önkényesen 0 vagy 1, és megkíséreljük egy olyan bemeneti kombináció előállítását, amely egyrészt összhangban van a) zj helyes β értékével a hibátlan hálózatban, és b) zj hibás β’ értékével a hibás hálózatban. A kitűzött feladat megoldásához egyidejűleg két tartományban fogjuk számításainkat végezni: az ún. normális, ill. a hibás tartományban. Ez azt jelenti, hogy mindegyik hálózati pontnál két logikai értéket veszünk figyelembe, mégpedig a hibátlan és a hibás hálózatban számított értéket. Egy ilyen értékpárt kettős értéknek (composite value) nevezünk. Egy i pont kettős

21

értékét gi = vn / vh alakban adjuk meg, ahol a vn az i pont helyes értéke, vh pedig az i pontnak a feltételezett hibát tartalmazó hálózatban felvett értéke. Számításainkban egy tartományban három logikai értékkel dolgozunk. Ezek: a logikai 0, a logikai 1 és a közömbös érték, amit most is d-vel jelölünk. A d érték szemantikus interpretációja: a számítások adott fázisában d helyett tetszőlegesen 0–t vagy 1-et írhatunk elő a d-t hordozó pontra, anélkül, hogy az ellentmondásra vezetne. A kettős értékek halmazát úgy is megkaphatjuk, hogy képezzük a {0, 1, d} halmaznak önmagával vett Descartes-szorzatát, ami a következő eredményt adja: {0/0, 0/1, 0/d, 1/0, 1/1, 1/d, d/0, d/1, d/d}. Ez azt jelenti, hogy a számításokat 9-értékű logikai rendszerben végezzük, ahol a kilenc kettős érték első komponensei a normál, második komponensei a hibás tartományba esnek. Ebben a logikai rendszerben két érték közötti művelet eredményének első, ill. második komponense az operandusok első, ill. második komponensei között végzett ugyanazon művelet eredménye lesz. A kiindulási értékeink a következők lesznek: zj = β/β’, míg egy α szintű elakadási hibát tartalmazó ponton felveendő kettős érték d/α. Belátható, hogy ez a kiindulási értékhalmaz a minimálisan szükséges és elégséges értékeket írja elő ahhoz, hogy azok az adott q-szoros hiba tesztjének feltételét adják. Az így adódó kiindulási értékekhez a D-algoritmusban felhasznált összehangolási eljárást használjuk fel a teszt kiszámítására. A kettős értékekkel végzett összehangolást kettős összehangolásnak nevezzük. Ez ugyanolyan módon végzendő, mint az egyszeres értékekkel, azzal a két további kikötéssel, hogy a) két kettős érték akkor és csak akkor konzisztens, ha mind a normális, mind a hibás komponensük konzisztens; b) a hibás tartományban az elakadási értékeket nem szabad összehangolni a jelfolyamban őket megelőző értékekkel. (A hibás érték ugyanis önmagából adódik.) Az összehangolás során természetesen csak a határozott logikai értékeket kell „visszakövetni”, a d-komponenseket nem. Ha a folyamatban ellentmondás lép fel, akkor az utoljára megtett változtatható értékkijelölésen (döntésen) módosítunk, majd töröljük az összes ez után kijelölt értéket, és tovább folytatjuk a számítást. A fentiekben leírt folyamat lépéseinek száma lényegesen csökkenthető az alábbi két megfontolással: Magától értetődik, hogy azokon a hálózati pontokon, amelyeken nem halad át jel egy hibás ponttól az elsődleges kimenetek felé, nem különbözhet a kettős értékek két komponense. 22

Ezeket a pontokat inaktívnak nevezzük. Az inaktív pontok ismeretében lényegesen kevesebb lesz az esetenként választható kettős értékek száma, másrészt egy ilyen pontnál kettő helyett csak egyetlen logikai értéket kell a továbbiakban összehangolni. Vegyük észre, hogy számunkra elegendő azoknak a pontoknak a meghatározása, amelyeken át a hibás pontokból zj-hez terjed a jel. Az ilyen pontokat potenciálisan aktívnak nevezzük. Ez azért van így, mert az összes többi pont vagy inaktív, vagy pedig nem vesz részt a zj-re elindított számítási folyamatban. A potenciálisan aktív pontok halmazának meghatározásához elegendő a hálózatot egyszer a jelterjedési irányban a hibás pontokból kiindulva, egyszer pedig a jelterjedéssel ellentétesen, zj-ből kiindulva bejárni. A két bejárással kapott pontok halmazainak közös része adja az eredményt. Itt jegyezzük meg, hogy a továbbiakban egy zj kimenetet csak akkor veszünk figyelembe, ha az legalább egy hibás pontból elérhető valamely jelterjedési úton keresztül. A másik megfontolás a zj kezdeti értékeire vonatkozik. A gondot itt az okozza, hogy nem tudjuk előzetesen, mit válasszunk helyes, ill. hibás értéknek, ezért élünk önkényes választással. Egyszeres hiba esetén azonban nincs szükség arra, hogy megismételjük az összehangolást zj felcserélt értékeivel, ha a kezdeti választás nem vezetett volna eredményre. Ha ugyanis zj kezdeti értékpárja olyan 0/1 vagy 1/0 értékpárt (nevezzük ezt aktív értéknek) implikál a hiba helyén, ami ellentmond az elakadási szintnek, akkor az összes addig kiosztott kettős érték komponenseit felcserélhetjük, amivel az ellentmondás megszűnik, és innentől a számítás tovább folytatható. A hiba helyén mindig fogunk aktív kettős értéket kapni, mivel a zj-n levő aktív kettős érték összehangolásához legalább egy hibaterjesztési út mentén kizárólag aktív értékeknek kell szerepelniük. Másrészt azonban ha a hibák száma egynél több, a felcserélési folyamat nem mindig hajtható végre ugyanabban az összehangolási menetben. Az előbbiek alapján q ≥ 1 egyidejűleg fennálló hiba tesztjének előállítására a következő algoritmus szolgál: Egy megfelelő zj kezdeti értéknek 0/1-et választunk, míg a hibás pontokat a hibás tartományban ellátjuk elakadási értékükkel. Ezután kettős összehangolást végzünk, a hálózati elemeket kimeneteik azonosítójának csökkenő sorrendjében véve. Ha q = 1, és az aktív értékek láncolata a hibás i pont és a zj közötti út mentén ellentmondásba kerül i-nél, akkor az i-n kívül sorravett pontok kettős értékét felcseréljük, és tovább folytatjuk az összehangolást. Ha q > 1, akkor zj = 0/1-re végrehajtjuk a kettős összehangolást. Ha ez sikertelen lenne, akkor az eljárást teljes egészében megismételjük zj = 1/0-val is. Egy konzisztens megoldás esetén a teszt az elsődleges bemeneteknek a normális tartományba eső értékeiből áll. Ha zjvel nem sikerült megoldást kapnunk, vesszük a következő elsődleges kimenetet, és arra hajtjuk végre a kettős összehangolást. Példaként ismét a Schneider-hálózatot véve a 6(0) hibával, a számítások menete a következő lesz: 1) A kiindulási értékek:

z1 = 0/1,

2) A potenciálisan aktív pontok halmaza:

{6, 9, 10, 12}.

4) Az összehangolási folyamat lépései sorban: 23

g6 = d/0.

g11 = d/0,

g10 = 1/0, g9 = d/0,

g8 = d/0,

g7 = d/1,

és végül g6 = 0/1, ami ellentmondás (ütközés) a hibás tartomány elakadási helyén. Az ellentmondás feloldására felcseréljük az eddig kijelölt összes értéket, és tovább folytatjuk a számításokat. Ennek ellentmondásmentes végeredménye a következő lesz: z1 = 1/0,

g10 = 0/1,

g9 = 0/d,

x1 = 0/d,

g8 = 0/d,

x2 = 0/d,

g7 = 1/d,

x3 = 0/d,

g6 = 1/0, g5 = 1/d,

x4 = 0/d.

A keresett tesztet a végeredményként kapott bementi vektornak a normál tartományba eső értékei adják. A számítások jól mutatják, hogy a két hibaterjesztési út szimultán aktivizálására úgy került sor, hogy csak az egyik úton kellett visszakövetni az aktív értéket. Ez a tény a kettős összehangolás egyik alapvető sajátosságát tükrözi, nevezetesen azt, hogy a végső hibaterjesztési útkombináció a homogén számítási folyamat eredményeként valójában „magától” alakul ki. 2.2

A módszerek kiterjesztése szekvenciális hálózatokra

Mint ismeretes, a sorrendi, vagy szekvenciális hálózatok elsődleges kimeneti változóinak értéke egy adott időpontban nemcsak az elsődleges bemeneti változók értékeitől függ, hanem a hálózat tárolóinak állapotaitól is. A tárolási funkciót a logikai visszacsatolások valósítják meg, a 2.1. ábrán bemutatott Mealy-modellnek megfelelően. A szinkron hálózatok órajele az állapotváltozások ütemét határozza meg. Az aszinkron hálózatokban nincs órajel: ezekben az állapotváltozások a hálózat belső késleltetéseitől függő sebességgel mennek végbe. A továbbiakban kizárólag a szinkron változattal foglalkozunk. A gyakorlati elterjedtségét tekintve ez a típus ma már csaknem teljesen kiszorította az órajel nélküli típust. A sorrendi hálózatok tesztjeinek kiszámítása jóval bonyolultabb problémákat vet fel, mint a kombinációs hálózatoké. A bonyolultságot a jelen levő tárolók okozzák. Ugyanis az elsődleges kimenetre nem kötődő tárolók állapotát nehéz közvetett mérésekkel megfigyelni. Ugyanilyen nehézséget jelent a tárolók állapotának az elsődleges bemenetekről történő vezérlése, amire ugyancsak szükség van a teszteléskor. Egy ehhez kapcsolódó fontos fogalom a következő: A szekvenciális hálózatot a tárolók tetszőleges, vagy adott állapotkombinációjából egy előírt kombinációjába vivő bemenő vektorok rendezett sorozatát beállító sorozatnak nevezzük. (Az automataelméletben ezzel lényegében megegyező fogalom a szinkronizáló sorozat – angolul: synchronizing sequence.) A beállító sorozatok megtervezése esetenként igen hosszadalmas számításokat igényel. A feladatot nehezíti a különböző hibákat tartalmazó hálózat hibánként eltérő viselkedése is. Megállapítható még, hogy míg a kombinációs hálózatok minden tesztje egyetlen bemenő vektor, addig a sorrendieké általában egynél több vektor sorozata, ahol természetesen számít a bemenő jelek időbeni sorrendje is.

24

A szekvenciális hálózatok tesztszámítási módszereit minden tekintetben a kombinációs hálózatokéra lehet visszavezetni. Az utóbbiakra vonatkozó módszerek felhasználása azon alapszik, hogy a hibaterjesztést végső soron a szekvenciális hálózati modell kombinációs blokkjára kell elvégezni. Ezt a blokkot tekintve az a lényeges újdonság a tiszta kombinációs modellhez képest, hogy az elsődleges kimeneti változók nemcsak az x vektortól, hanem az y vektortól is függenek, a már korábban definiált z = z(x1, x2, …xn, y1, y2, , yp) = z(x, y) összefüggés értelmében. Ennek a helyzetnek megfelelően egy tetszőleges h hibára vonatkozó tesztszámítási feladat végső soron két megközelítésben oldható meg: 1) Adott állapothoz való illesztés: Tegyük fel, hogy a hálózat egy ismert yt állapotban van. Ekkor az z = z(x, yt) függvényhez keresünk egy olyan xt vektort, ami a h hibát a z vektor valamelyik bitjére juttatja. Ezt az esetet tehát úgy lehet elképzelni, mintha a kombinációs hálózati blokk bemeneteinek egy részén, tudniillik a másodlagos bemeneteken, már előírt logikai érték lenne. Jelöljük az s darab bemenő vektorból álló rendezett sorozatot x(s)-sel, ahol s-et a sorozat hosszának nevezzük. Eszerint x(s) = x1, x2,…,xs. Tegyük fel, hogy az yt állapotot az x(t-1) = x1, x2, …, xt-1 bemenő sorozat hozta létre. Ekkor a h hiba tesztje az x(t) = x1, x2,…, xt-1, xt bemenő sorozat lesz. A kapu szinten kezelt kombinációs hálózati blokkra az eddig ismertetett tesztszámító módszerek mindegyike alkalmazható. Ehhez még két fontos kiegészítést kell fűznünk: a) Az x(t-1) sorozat hatására bekövetkező yt állapot meghatározása a hálózat működésének végigkövetésével, vagyis szimulációval történhet meg. A tesztszámítás érdekében ilyenkor a hibás hálózati verziók működését is végig kell követnünk, vagyis hibaszimuláció végrehajtására van szükség. b) A feltételezett h hiba hatása yt egy vagy több komponensében is megjelenhet hibajelként. Az ilyen hibát virtuális hálózati hibának nevezzük. A kombinációs hálózati blokk virtuális hibái a számítások szempontjából ugyanúgy kezelendők, mint az eredeti h hiba, vagyis további elakadási hibáknak tekintendők, amelyek vagy belekerülnek a

25

terjesztésbe, vagy sem. Ez a helyzet tehát a többszörös hibák számítására alkalmas változatok felhasználását követeli meg akkor is, ha a h hiba csak egyszeres. A tesztszámítás általános folyamata: A következőkben az állapotvektorhoz való illesztés egy célszerű és hasznos megoldásának általános folyamatát ismertetjük algoritmikus lépésekben. Legyen a kiindulási állapot ys, amelybe az x(s-1) = x1, x2,…, xs-1 sorozat juttatta a hálózatot. A tesztet egy adott h hibához keressük. 1. lépés: Hibaterjesztés végrehajtásának megkísérlése a kombinációs blokk z vektorának egy lehetséges bitjére. 2. lépés: Ha a hibaterjesztés sikerült, akkor hibaszimuláció végrehajtása következik a talált tesztvektorra, az ys állapotból kiindulva. A h hiba tesztje ekkor az x(s) = x1, x2,…, xs-1, xs sorozat lesz, és a h-ra vonatkozó számítások véget érnek. Ha a terjesztés nem sikerült, akkor a 3. lépés következik. 3. lépés: Hibaterjesztés végrehajtásának megkísérlése a kombinációs blokk Y vektorának egy lehetséges bitjére. (A másodlagos kimenetre, vagyis tárolóra történő hibaterjesztésnek az a célja, hogy egy újabb állapotba víve a hálózatot, ebből a helyzetből lehessen újra megkísérelni az elsődleges kimenetre történő terjesztést.) Ha a hibaterjesztés sikerült, akkor hibaszimuláció végrehajtása következik a talált tesztvektorra, az ys állapotból kiindulva. Ezután legyen s := s + 1, majd újra kezdjük az 1. lépéstől. Ha a terjesztés nem sikerült, akkor a h-ra vonatkozó számítási folyamat sikertelenül véget ér. A fenti, számítógépre szervezett folyamatról látható, hogy általánosan nem garantálja egy hiba létező tesztjének megtalálását. A módszer eredményessége ugyanis függ a kiindulási állapottól. Emiatt sikertelenség esetén érdemes lehet ugyanara a h hibára egy később elért újabb állapotban megismételni a számításokat. Az új állapot ilyenkor másik hibák tesztjeinek kiszámítása és szimulációja után jön létre. 2) Tesztszámítás beállító sorozattal: A másik megközelítésben a hibaterjesztési számítást szabadon végezzük el a kombinációs blokk z = z(x, y)

26

vektorfüggvényére, szabadon meghatározható bemeneti változónak tekintve x-et és y-t. Az így kapott teszt egy (xt, yt) vektorpárból fog összetevődni. Ebben a párosban az xt mint elsődleges bemeneti vektor szabadon ellátható a kapott bitértékekkel. Ezzel szemben a másodlagos bemeneteket nem tudjuk kívülről közvetlenül vezérelni, ezért az yt beállításáról külön kell még gondoskodni. Az előírt állapotkombinációt egy külön bemenő sorozatnak, beállító sorozatnak a hálózatra küldésével lehet elérni. A beállító sorozat tehát közvetlenül megelőzi az xt vektort. A számítások szempontjából nem mindegy, hogy ismeretlen, vagy ismert kiindulási állapotból kell elérni a kitűzött állapotot. Az ismeretlen kiindulás ugyanis másképpen azt jelenti, hogy tetszőleges állapotból kell elérni célt, ami sokkal nehezebb, mint egy ismertből. Az ismeretlenből való kiindulást teljesítő sorozatot szokás még inicializáló sorozatnak, míg az ismertből kiindulót transzfer sorozatnak is nevezni. Az igényelt beállító sorozatok meghatározása rendkívül számításigényes feladat. A számítások elvégzéséhez az elérendő állapotot tételezzük fel az Y vektorban, és a jelterjedésben mindig visszafelé haladva olyan elsődleges és másodlagos bemeneti kombinációt határozunk meg, amely összhangban van az elérendő állapottal. A talált másodlagos bemeneti kombinációt ismét a másodlagos kimenetekre tételezzük fel, és újra keresünk egy ezzel konzisztens x-y bementi párt, és így tovább. Inicializáló sorozat esetén a vázolt folyamat akkor ér véget sikeresen, ha az utoljára talált y-kombináció mindegyik bitje don’t care értékű lesz. Transzfer sorozat esetén a végeredményt annak az állapotnak a bitenkénti pontos elérése jelenti, amiből kiindulva a hálózatot a célállapotba kellett vinni. A leírt visszafelé haladó keresés a Mealy-modell kombinációs blokkján hajtandó végre. Ezt elvileg meg lehet oldani a Boole-függvények alkalmazásával, valamint a logikai értékek összehangolási procedúrájával is. A feladat megoldását lényegesen nehezíti, hogy a tesztszámításhoz a h hibát tartalmazó hálózatot kell figyelembe venni. Ehhez a D-algoritmus, a Bole-differenciák, valamint a kettős összehangolás számítási apparátusa elméletileg egyaránt felhasználható, néhány kiegészítő meggondolással. Mindazonáltal a beállító sorozatok meghatározásáról mindenképpen le kell mondani a gyakorlatban, mivel ez a megközelítés beláthatatlan mennyiségű, és ugyanakkor kevés sikerre vezető számításokat vonna maga után. Végezetül fontosnak tarjuk megemlíteni, hogy a szekvenciális hálózatok kezelése még egy általánosan figyelembe veendő szempontot vet fel. A számítások végzésekor szükség lehet arra, hogy az ismeretlen logikai értéket is kezelnünk kell. Ezt az értéket szokásos u-val jelölni (az angol unknown szó alapján). Az u értékre azért lehet szükség, mert a hálózatoknál nem mindig tételezhetjük fel, hogy mindegyik tárolójuk állapotértéke ismert. Az ismeretlen tárolóértékek megkövetelik az u érték kezelését. A kettős összehangolás esetében ez például azt jelenti, hogy a {0, 1 , d, u} halmaznak az önmagával képzett Descartes-szorzata 16-elemű halmazt ad, vagyis az algoritmus sorrendi hálózatokra 16-értékű logikai rendszerben hajtódik végre. Elvileg tehát 16 lehetséges kettős értéket vehet fel egy hálózati pont. Ehhez még azt érdemes hozzátenni, hogy az u érték használatára egyedül csak az ismeretlen értékű tárolóállapotoknál van szükség, mégpedig a tárolók kimeneti pontjain. Az összehangolási folyamatban tehát csak a másodlagos 27

bemeneteken szereplő u értékek jöhetnek számításba, a többi hálózati ponton nincs szükség az ismeretlen érték kezelésére. Ott tehát elegendő 9 kettős érték használata. Könnyen belátható, hogy az u érték nem lehet konzisztens semmilyen határozott logikai értékkel, így sem a 0-val, sem az 1-gyel. Egyedül csak a don’t care (d) érték konzisztens az u-val. Ekkor u ∼ d = u. 2.3

Funkcionális szintű tesztelés

Az integráltsági fok növekedésével egyre inkább szükségessé válik a logikai elemeknek a klasszikus kapu szintnél magasabb hierarchikus szinten történő kezelése. Ezt a követelményt főként az a tény motiválja, hogy az IC-k ekvivalens kapuszáma olyan mértékben megnövekedett, hogy az már egyre inkább kivihetetlenné teszi a kapu szintű gépi feldolgozást. A VLSI szint ma már nemcsak százezres, hanem milliós nagyságrendű számú kaput is hordozhat magában. A hálózatokat a kapuknál tetszőleges mértékben bonyolultabb építőelemekkel is modellezhetjük. Az ilyen összetett építőelemet általában egynél jóval több kaput tartalmazó hálózattal lehet helyettesíteni. Egy-egy építőelemről, amit logikai modulnak nevezünk, azt tételezzük fel, hogy a külsőleg definiált működését, vagyis az elem funkcionális viselkedését ismerjük, miközben eltekintünk belső struktúrájától. Eszerint tehát a modulok a bemeneti és kimeneti pontjaik közötti logikai-funkcionális összefüggésekkel vannak definiálva. Az ilyen megközelítést funkcionális szintű vagy modul szintű modellezésnek nevezzük. A modellek különféle specifikálása, leírása létezik. Egyszerűbb esetben igazságtáblák, ill. Boolefüggvények szolgálnak erre a célra. Az összetettebb elemek megadása ma már magas szintű hardver-leíró nyelvek (hardware-description language, HDL) felhasználásával történik. Ezekhez a nyelvekhez saját fordítóprogram tartozik, ahol a modellezésre a fordítás után előálló tárgykód alapján kerül sor. A legelterjedtebben használt ilyen eszköz az USA-ban kifejlesztett és szabványosított VHDL nevű nyelv. A funkcionális szintű modellezés magától értetődően azt eredményezi, hogy egy digitális modul feldolgozása jóval kevesebb adat felhasználásával, kevesebb számítási lépés végrehajtásával megy végbe, mint ha a modul ekvivalens kapuhálózatát dolgoznánk fel, egyenként foglalkozva az összetevő kapuk jeleivel. Az ilyen szintű modellezés a számítógépes megvalósításkor a kisebb tárolóigényben és a rövidebb feldolgozási időben nyilvánul meg. Természetesen ennek ára is van: a kapu szintről való lemondás azzal jár, hogy a modulok finomstruktúráját kevésbé hűen tudjuk kifejezni, ami elsősorban az időbeni jelterjedési viszonyok, valamint a belső modulhibák feldolgozásában érezteti hatását. Jellegzetes modulok közé tartoznak például a dekódolók, multiplexerek, összeadók, aritmetikai-logikai egységek (ALU-k), léptetőregiszterek, számlálók, stb. Ez persze nem jelent merev határokat: a bonyolultság alsó határán építőelem lehet egy tetszőleges kapu is, míg a felső határt a pontos funkcionális leírás nehézsége, az adott leírás szükségessége, valamint a gépi úton még kifizetődő feldolgozhatóság egymás közötti viszonya (trade-off-ja) szabja meg. Ebbe természetesen döntő mértékben beleszámít a teszttervezés megoldhatósága, ill. kivitelezhetősége is. Mint a korábbi fejezetekben láttuk, az alacsony hierarchikus szinten történő tesztszámítás elméleti alapjai már ki vannak dolgozva. A kapu szintű módszerek életképes gyakorlati eszköznek bizonyultak a számítógéppel végzett teszttervezésben. Ezzel szemben a magasabb

28

szintű hálózatkezelés területén, így a funkcionális szintűn is, az eddig elért eredmények már kevésbé kielégítőek. A helyzet az, hogy a felmerülő feladatok eleve rendkívül számításigényesek, és emellett még számos kombinatorikai természetű probléma vár megoldásra. A teszttervező programrendszerek hatékonyságát döntő mértékben befolyásolják a logikai elemek működését specifikáló gépi modellek. A modellezés az igazságtáblázatokra, valamint az ún. funkcionális algoritmusokra épül. Utóbbi esetben olyan algoritmusokról van szó, amelyek felhasználásával a logikai modulok bemenő jeleinek és tárolóállapotainak ismeretében a kimenő jelek és az új tárolóállapotok számíthatók ki. Igazságtáblázatokat vehetünk számításba a programozott elemeknél (pl. PROM, FPGA), és általában ott, ahol az áramköri katalógus is ebben a formában írja le működésüket. Tipikus elemek például a dekódolók, multiplexerek, összeadók. A tárolóigény és a gépi feldolgozás-kiértékelés szempontjából a nagybonyolultságú elemek működését a legcélszerűbb funkcionális algoritmusokkal definiálni. Az algoritmusok alapján elkészíthető az adott modul magas szintű hardver-leíró nyelven történő specifikálása. A 2.1.1 pontban leírt hibamodellek funkcionális szinten is alkalmazhatóak. Mindazonáltal ez a modellezési mód újabb hibafajták kezelését is lehetővé teszi. Ezek a következők: • •

Funkcionális hibák: Egy modul egy adott bemenőkombináció vagy bemenősorozat hatására egy ugyancsak definiált, de a helyestől eltérő válaszjelkombinációt ad ki. Jelváltozó hibája: A hardver-leíró nyelven definiált hálózat egy vagy több jelváltozója állandó logikai értéken van elakadva.

A fenti két hibafajta számítási kezelése nem igényel eltérő megközelítést az elakadási hibákétól, ezért a továbbiakban külön nem foglakozunk velük. A következőkben egy-egy példán keresztül mutatjuk be, hogy a kapu szinten alkalmazott algoritmusok hogyan használhatóak fel modul szinten leírt hálózatok tesztjeinek számítására. Példa kombinációs modulra: A kiválasztott kombinációs modul egy négybites multiplexer (adatszelektor). Jelölések: Címbitek: a1, a2. Adatbemenetek: d0, d1, d2, d3. Engedélyező jel: s. Kimenet: z. Az engedélyezés s = 0 esetén van érvényben, s = 1-re z = 0 lesz, függetlenül a többi bemenet értékétől. Normál üzemben a címbitek által kijelölt adatbemenet aktuális értéke jut el a kimenetre. A D-algoritmus felhasználásakor először is arra van szükség, hogy rendelkezésünkre álljanak a hálózati modulok D-terjesztési vektorai. Ezek ismeretében lehet a hibaterjesztési fázisban a hibát az egyes modulokon keresztül a kimenetek felé terjeszteni. A kapukhoz képest ez jóval nagyobb vektorkészletet jelent, még kombinációs blokkok esetén is. Az alábbiakban

29

megadjuk a multiplexer néhány D-terjesztési vektorát, ahol a vektor elemei a fenti bitfelsorolás sorrendjét követik: (0, 0, 1, d, d, d, D, D’),

(0, 0, D, d, d, d, 0, D)

(0, 0, D’, d, d, d, 0, D’),

(0, 1, d, D, d, d, 0, D)

(0, 1, d, D’, d, d, 0, D’),

(1, 1, d, d, d, D, 0, D)

(D, D, 0, d, d, 1, 0, D),

(D, D, 1, d, d, 0, 0, D’)

Az összes lehetséges D-terjesztési vektor az igazságtábla alapján állítható elő. ugyancsak Az összehangolási eljáráshoz ugyancsak az igazságtábla használandó fel, a z kimenet értékéből kiindulva. Például, a z = 1-hez a lehetséges bemeneti kombinációk a következők: (0, 0, 1, d, d, d, 0),

(0, 1, d, 1, d, d, 0),

(1, 0, d, d, 1, d, 0),

(1, 1, d, d, d, 1, 0).

A kettős összehangolás nem igényli a D-terjesztési vektorokat, mivel nem tartalmaz hibaterjesztési fázist. A fenti multiplexerre vett összehangolási példa legyen a következő: Tegyük fel, hogy z = 0/1, és a2-n 0-s elakadási hiba van, d0-n 1-es elakadási hiba van. Ekkor a kettős összehangolás eredménye: (a1, a2, d0, d1, d2, d3, s) = (0/0, 0/0, 0/1, d/d, d/d, d/d, 0/0). Példa szekvenciális modulra: Legyen a kiválasztott modul egy 6-bites bináris számláló. A számláló blokksémája a 2.4. ábrán látható.

Y1 Y2 Y3

Cp

U

G

L

A1

Y4 Y5

A2 A3 A4

A5 A6

2.4. ábra: A bináris számláló blokksémája

30

Y6

A számláló működésének modellezésére funkcionális algoritmusokat fogunk felhasználni. A működési módok vezérlőkódjai, valamint az egyes működési módokat megvalósító algoritmusok felsorolása a 2.1. táblázatban szerepel.

Cp d d 1 0 0

U d d d 1 0

G d 1 0 0 0

L 0 1 1 1 1

Működési mód Algoritmus Párhuzamos beírás P Értéktartás H Értéktartás H Inkrementálás U Dekrementálás D

2.1. táblázat: A működési módok vezérlőkódjai

Jelölje xc = (Cp, U, G, L). a vezérlőbitek vektorát, az adatbemeneti bitek vektora pedig legyen A = (A1, A2, A3, A4, A5, A6). Legyenek továbbá a regiszter elemeinek jelenlegi, ill. következő állapotát kifejező vektorok y = (y1, y2, y3, y4, y5, y6), ill. Y = (Y1, Y2, Y3, Y4, Y5, Y6). A négy alapalgoritmus a következő módon definiálható: 1) P (párhuzamos beírás):

Yi = Ai, ahol i = 1, 2, …,6.

2) H (értéktartás): yi = yi, ahol i = 1, 2,…,6. 3) U (inkrementálás, számlálás felfelé): • • • •

A legkisebb helyértékű 0-tól balra mindegyik bit változatlan marad. A legkisebb helyértékű 0, valamint a tőle jobbra levő bitek, amelyek ugyanakkor balra vannak a legkisebb helyértékű u-tól, mind u értéket kapnak, és a legkisebb helyértékű u értéke marad u-nak. A legkisebb helyértékű 0-ból 1 lesz, ha az jobbra van a legkisebb helyértékű u-tól. Ha a szélső jobboldalon vannak összefüggő 1-esek, akkor azok mindegyike 0 lesz.

4) D (dekrementálás, számlálás lefelé): Ugyanaz, mint az U algoritmus, azzal az eltéréssel, hogy az 1-eseket és 0-kat mindenütt fel kell cserélni egymással. A D-algoritmushoz használandó D-terjesztési vektorokból a következő táblázatban sorolunk fel néhányat, a bináris számlálóra vonatkozóan:

31

Cp, U, G, L, Ai, yi, Yi _____________________ d d 1 D 1 0 D’ d d 1 D 0 1 D 1 d d D 1 0 D’ 1 d d D 0 1 D d d d 0 D d D d d 1 1 d D D 1 d d 1 d D D 2.2. táblázat: D-terjesztési vektorok a bináris számlálóhoz A táblázatban látható vektorok azt fejezik ki, hogy a számláló egy adott állapotában a bemenetére érkező hibajel (D) milyen feltételekkel terjeszthető ki a kimenetre, anélkül, hogy állapotváltozásra lenne szükség. A D-terjesztéshez azonban egyetlen vektor nem mindig elegendő. Adott esetben szükség lehet egynél több vektorból álló bemenő sorozatok felhasználására is. Mindebből jól kitűnik az, hogy a D-terjesztés megoldása szekvenciális modulokra lényegesen megnehezíti a számításokat. Mindezen felül a vektorok halmazának előállítása külön problémákat vet fel. Jelenleg még nem ismeretes olyan módszer, amely a vektorkészlet automatizált generálását tenné lehetővé. A kettős összehangolás alkalmazására vegyünk egy olyan példát, amely a bináris számlálóra vonatkozik. Legyen B1 azoknak az algoritmusoknak a halmaza, amelyek konzisztensek egy adott xc vektorral. Például, ha xc = (0, d, d, 1), akkor a 2.1. táblázat szerint a B1 = {U, D, H} B

halmazt kapjuk. Legyen továbbá B2 azoknak az algoritmusoknak a halmaza, amelyek egyidejűleg konzisztensek az y, Y, valamint az A vektorok aktuális komponenseivel. Tételezzük fel, hogy a számláló a következő kezdeti értékekkel rendelkezik a normál tartományban: xc = (0, d, d, d),

A = (1, d, 0, d, 1, 1),

y = (0, 0, 1, 0, 0, 1),

Y = (d, 0, d, d, 1, 0).

Ehhez azt jegyezzük meg, hogy egy modul bemeneti értéke egy előző összehangolási lépésből adódik, amelyet egy másik modulra hajtottunk volt végre. Az xc-vel összhangban B1 = {U, D, H, P}. B

Az egyetlen algoritmus, ami konzisztens az y, Y, valamint A komponens-értékeivel, az U, vagyis B2 = {U}. B

Ezek után azoknak az algoritmusoknak a halmaza, amelyek egyaránt konzisztensek a modul kezdeti értékeivel, a következő módon kapható meg: B = B1 ∩ B2 = {U}. B

32

Itt a B halmazból egyértelműen arra következtethetünk, hogy xc = (0, 1, 0, 1), másrészt pedig hogy az A vektor nem változott meg. Ami a hibás tartományt illeti, legyen a normál értéktől való eltérés az Y vektor utolsó bitjében, vagyis Y = (d, 0, d, d, 1, 1) Az adott feltételeket kielégítő halmazok a következők lesznek: B1 = {U, D, H, P},

B2 = {P},

B

és végül

B = B1 ∩ B2 = {P}. B

Mindebből az alábbi eredmény adódik: xc = (0, d, d, 0),

A = (1, 0, 0, d, 1, 1).

A két tartományban kapott eredményeket összegezve azt láthatjuk, hogy egy hibajel adódott az L vezérlőbemeneten (vagyis L = 1/0), ami az Y6 kimenetre terjedt ki, a kapott bemeneti értékek révén. Ugyancsak meg kell még említenünk, hogy A2 = 0 az Y2 = 0 értékből adódott, a párhuzamos beírás feltételeivel összhangban. A végeredményül kapott értékeloszlást a 2.5. ábrán foglaltuk össze.

Y = d/d 0/0 d/d d/d 1/1 0/1

y= Cp U

x c = 0/0

1/d

G

0/0 0/0 1/1 0/0 0/0 1/1

L

0/d 1/0 A=1/1 d/0 0/0 d/d

1/1 1/1

2.5. ábra: Kettős összehangolás a bináris számlálóra

33

2.5 Összehasonlító áttekintés Ebben az alpontban röviden áttekintjük az ismertetett tesztszámító módszereket, és összehasonlítást teszünk közöttük a számítógépes megvalósíthatóság és felhasználhatóság szempontjából. A számítási teljesítmény folyamatos és erőteljes növekedésével továbbra is megmarad a jelentősége a kapu szintű modellezésnek. Ehhez járul még az a tény is, hogy ez a megközelítés strukturálisan jóval finomabb felbontást nyújt, mint a magasabb szintű megoldások. Mindez a fizikai hibák jóval tágabb körének felfedését teszi lehetővé. Az összehasonlításhoz számítási szempontból elegendő egyetlen hibadetektálási kimenetet figyelembe venni. Először egyszeres hibával foglalkozunk. Gyakorlati téren egyaránt számításba jöhetnek azok a módszerek, amelyek a logikai értékek algoritmikus kezelésén alapulnak: a D-algoritmus és az arra épülő módszerek, továbbá a PODEM, FAN, valamint a kettős összehangolás. A PODEM és a kettős összehangolás azzal a lényeges előnnyel rendelkeznek a többi módszerhez képest, hogy nem tartalmaznak hibaterjesztési fázist. A hibaterjesztés mindig külön összehangolási folyamatot igényel a teljes hálózatra nézve. A D-algoritmusnál legrosszabb esetben sor kerül az összes lehetséges útkombináció feldolgozására, és az ezeket követő összehangolásra. E megközelítéssel szemben a kettős összehangolási algoritmus a hibaterjesztési próbálgatást teljes mértékben mellőzi, és csak egyetlen összehangolási folyamatot hajt végre, aminek végén automatikusan kiadódik az az útkombináció, amelyen a hiba terjed. Ezáltal a rekonvergens utak jelenléte ezt a megoldást sokkal kisebb mértékben befolyásolja, mint a D-algoritmust. A Boole-differenciák módszere vagy annak bármely módosítása nagyméretű hálózatoknál óriási számú Boole-függvény előállítását és invertálását igényli. Másrészt pedig hatalmas mennyiségű algebrai műveletre van szükség a különböző Boole-egyenletek megoldásához. A másik gond az, hogy túlzottan nagy lehet a memóriaigény is, amit egyébként igen nehéz előre megbecsülni. Ez ellentétben áll a logikai értékek kezelésén alapuló módszerekkel, amelyek memóriaigénye minimális. Például a kettős összehangolási algoritmus 16 logikai értékének tárolására elegendő mindegyik hálózati ponthoz 4 bitet kijelölni. A jól programozható és algoritmizálható számítások ezt a megoldást számítógépre jóval alkalmasabbá teszik. Többszörös hibák esetén a kettős összehangolás előnyei jobban megnyilvánulnak. Mint ismeretes, q-szoros hiba esetén az összes többi módszert, beleértve a Boole-differenciákat is, q legrosszabb esetben 2 - 1-szer kell megismételni. Ezzel szemben a kettős összehangolási algoritmusban, a többszörös hibák számától függetlenül, legfeljebb csak kétszer kellhet végrehajtani a számítási folyamatot. Ami a funkcionális szintű modellezést illeti, ott a kapu szinten hatékony módszerek kiterjesztései számos modellezési és algoritmizálási problémát vetnek fel. A legfőbb gond a hibaterjesztési fázis megvalósításában jelentkezik. Eben ugyanis ismernünk kell az egyes hálózati modulok D-terjesztési vektorainak halmazát. Az ilyen halmazok meghatározására viszont még nem áll rendelkezésre általános és hatékony eljárás. Azok a gyorsítási eredmények, amelyek a PODEM és a FAN algoritmusokban mutatkoznak, végső soron a kapu szintű hálózati struktúra használatán alapulnak. Funkcionális szintű modellezésnél azok a strukturális és logikai elemzések, amelyeket e két algoritmus alkalmaz, 34

rendkívül bonyolulttá és nehezen kivitelezhetővé válnak. Itt is elmondható, hogy még nincsen kidolgozva e módszerek magasabb szintű modellezésre vonatkozó kiterjesztése. Az előbbiekkel ellentétben, a kettős összehangoláson alapuló megközelítéseket nem korlátozza minőségileg a hálózatok modellezési módja. Ugyanez vonatkozik a hálózati típusokra, vagyis kombinációsra, ill. szekvenciálisra, továbbá a hibák típusára és multiplicitására is. Ami a számítógépes megvalósítást illeti, egyedül csak az összehangolást kell gépre vinni, ami egy lényeges előny. Ennek végrehajtásához a hálózatban levő építőelemek inverz modelljére van szükség. Egy inverz modell a lehetséges bemeneti kombinációkat definiálja, amelyek egy-egy adott állapotkombinációt vagy kimeneti kombinációt eredményeznek. A modellezés céljára magas szintű hardver-leíró nyelveket lehet alkalmazni, ideértve a VHDL nyelvet is. A számítógépes megvalósítás olyan többértékű logikát kezelhet, amelyben a logikai értékek megegyeznek a hardver-leíró nyelven alkalmazott modellezés jelértékeivel. Ezen értékek száma tetszőleges lehet.

35