BOHUS MIKLÓS-DR. GÉHER KÁROLY BME Híradástechnikai Elektronika Intézet
Logikai hálózatok számítógépes vizsgálata* ETO:
A digitális berendezések s z á m á r a k i a l a k í t o t t logikai h á l ó z a t o k m á r v i s z o n y l a g e g y s z e r ű b b esetben is o l y a n sok b á z i s e l e m e t t a r t a l m a z n a k , h o g y a t e r h e l é s i , k é s l e l t e t é s i t u l a j d o n s á g o k v i z s g á l a t a , a helyes l o g i k a i m ű k ö d é s e l l e n ő r z é s e , az esetleges t é v e s b e k ö t é s e k h e l y é n e k m e g k e r e s é s e , a meg nem engedett vezérlé sek k i m u t a t á s a r e n d k í v ü l f á r a d t s á g o s f e l a d a t . A f e n t i f e l a d a t o k j ó l a l g o r i t m i z á l h a t o k , ezekre l o g i k a i ana l í z i s t és e g y é b v i z s g á l a t o k a t v é g z ő p r o g r a m o k k é s z í t hetők. A z analízis programok különösen előnyösen h a s z n á l h a t ó k a logikai k a p c s o l á s i rajz m ó d o s í t á s u t á n i e l l e n ő r z é s r e . A k o n s t r u k c i ó s t e r v e z é s megkez d é s e e l ő t t — m i n d az i n t e g r á l t á r a m k ö r i t o k o k , m i n d a t o k o k b ó l f e l é p ü l t k á r t y á k e s e t é n — c é l s z e r ű a he lyes l o g i k a i m ű k ö d é s r ő l s z á m í t ó g é p e s s z i m u l á c i ó v a l előzőleg m e g g y ő z ő d n i . G y á r t á s k ö z b e n és a v é g e l l e n ő r z ő m é r é s e k n é l s z ü k s é g e s az egyes k á r t y á k e l l e n ő r z é s e . E b b e n az esetben a hiba k i m u t a t á s á n t ú l m e n ő e n a l a p v e t ő k ö v e t e l m é n y a h i b a t í p u s á n a k és h e l y é n e k m e g h a t á r o z á s a . A z o p timális vizsgáló jelek k i v á l a s z t á s á r a diagnosztikai teszteket g e n e r á l ó s z á m í t ó g é p - p r o g r a m o k k é s z í t h e tők. A t o v á b b i a k b a n az e l s ő f e l a d a t k ö r e l l á t á s r a a l k a l mas p r o g r a m o k a t a n a l í z i s p r o g r a m n a k , a m á s o d i k feladatcsoporthoz t a r t o z ó k a t pedig d i a g n o s z t i z á l ó p r o g r a m n a k n e v e z z ü k . Jelen d o l g o z a t c é l j a , h o g y rövid bevezetést nyújtson a logikai hálózatok vizsgá l a t á n a k fentiekben v á z o l t k é t f e l a d a t k ö r é b e . A logikai hálózatok vizsgálatáról publikált kül földi i r o d a l o m a r é s z l e t e k r e v o n a t k o z ó a n e l é g s z ű k s z a v ú . H a z á n k b a n t ö b b helyen folyik ilyen t e v é k e n y s é g — bizonyos f o k i g e l t é r ő i r á n y o k b a n — p l . B M E E l e k t r o n c s ö v e k és F é l v e z e t ő k T a n s z é k , M T A A K I , T á v k ö z l é s i K u t a t ó I n t é z e t . P u b l i k á c i ó k a t te k i n t v e ez csak a H í r a d á s t e c h n i k á b a n k ö z ö l t s z á m í t ó g é p p r o g r a m k a t a l ó g u s b a n t ü k r ö z ő d i k . A z [ 5 ] refe rencia r é s z l e t e s e n k i f e j t i a l o g i k a i h á l ó z a t o k a n a l í zisére szolgáló program t u l a j d o n s á g a i t , e z é r t a k ö v e t k e z ő k b e n a d i a g n o s z t i k á v a l kapcsolatos k é r d é seket f o g j u k b ő v e b b e n t á g y a l n i . B e m u t a t j u k , h o g y a diagnosztika h i b a - t á b l á z a t m ó d s z e r r e l , é r z é k e n y s é g i ú t m ó d s z e r r e l , h i b a - s z ó t á r m ó d s z e r r e l v é g e z h e t ő el és f e l h í v j u k a f i g y e l m e t a B o o l e differencia j e l e n t ő ségére a h i b á k k i m u t a t á s á n á l .
1. L o g i k a i a n a l í z i s A z elektronikus á r a m k ö r ö k analizálásánál k i t ü n tetett figyelmet kell fordítani (i) a modell alkotásra, (ii) a m e g e n g e d h e t ő összekapcsolási lehetőségekre, * A munka a Számítástechnikai Koordinációs Intézet meg bízásából készült. Beérkezett: 1972. I I I . 4.
164.1:681.325.85.001.4
( i i i ) a b e m e n e t é s k i m e n e t ( g e r j e s z t é s é s felelet) k a p c s o l a t á r a és ( i v ) a felhasználó o r i e n t á l t p r o g r a m rendszer s z e m p o n t j a i r a . T e k i n t s ü k á t ezeket a k é r déseket integrált á r a m k ö r i tokokból felépített logikai hálózatok esetén. A l o g i k a i h á l ó z a t m o d e l l e z é s é r e e l v i l e g t ö b b lehe tőség kínálkozik. Elképzelhető ellenállásokból, kapa citásokból, diódákból, t r a n z i s z t o r o k b ó l stb. felépített modell, amely n e m l i n e á r i s á r a m k ö r f o r m á j á b a n írja le a h á l ó z a t o t . E z a l e í r á s b á z i s e l e m e k ( l o g i k a i a l a p á r a m k ö r ö k ) e s e t é n szükséges, azonban b o n y o l u l t a b b hálózatok esetén egyrészt a számítási igény rohamo san n ő , m á s r é s z t a l o g i k a i h á l ó z a t m ű k ö d é s é n e k m e g ítélése s z e m p o n t j á b ó l t ú z o t t a n részletes e r e d m é n y e ket szolgáltat. Ismeretes, h o g y N A N D , i l l e t v e N O R m ű v e l e t se gítségével minden kombinációs logikai m ű v e l e t k i fejezhető, t e h á t egyetlen m ű v e l e t e l e g e n d ő a k o m b i nációs h á l ó z a t o k leírásához. Ennek megfelelően olyan m o d e l l is f e l é p í t h e t ő lenne, a m e l y c s u p á n p l . N A N D k a p u k a t és k é s l e l t e t é s e k e t r e p r e z e n t á l ó elemeket tartalmazna. Egy tényleges logikai hálózat ilyen h e l y e t t e s í t ő k é p é n e k k i a l a k í t á s a és a k a p o t t ered m é n y e k é r t e l m e z é s e és f e l h a s z n á l á s a a k o n k r é t h á l ó z a t r a a z o n b a n n a g y o n n e h é z k e s lenne. A z integrált á r a m k ö r i tokokból felépített logikai h á l ó z a t o k e s e t é n c é l s z e r ű az i n t e g r á l t á r a m k ö r i k é s z let által b i z t o s í t o t t logikai modellekre t á m a s z k o d n i , t e h á t A N D , OR, N A N D , N O R , N O T stb. k a p u k a t , D , J K t á r o l ó k a t , s ő t nagyobb f u n k c i o n á l i s elemeket ( A D D E R , D E C O D E R s t b . ) is m e g e n g e d n i . A z i d ő v i s z o n y o k a t a b á z i s e l e m e k bemenetei é s k i m e n e t e i k ö z ö t t értelmezhető maximális késleltetési időkkel lehet m o d e l l e z n i . A z á r a m v i s z o n y o k s z á m í t á s a a t e r h e l é s e k és t e r h e l h e t ő s é g e k ( F A N - I N , FAN-OUT) meghatározására egyszerűsíthatő. A logikai h á l ó z a t tényleges s z á m í t á s a előtt, össze kapcsolhatóság szempontjából, ellenőrzésre van szük ségünk. Ennek keretében meghatározandó a) az ö s s z e s b e k ö t é s i r e n d e l l e n e s s é g ( h i á n y z ó be k ö t é s , n e m é r t e l m e z h e t ő b e k ö t é s e k stb.), b) az ö s s z e s á r a m k ö r i s z e m p o n t b ó l t i l o s ö s s z e k ö t t e t é s , a m e l y b á z i s e l e m k á r o s o d á s r a vezet, c) az ö s s z e s l o g i k a i s z e m p o n t b ó l t i l o s ö s s z e k ö t t e t é s ( p l . b i z o n y o s k a p u k bemenete n e m lehet ö s s z e kötve saját kimenetével), d) t o v á b b á , h o g y az á r a m k ö r k o m b i n á c i ó s , s z i n k ron szekvenciális vagy aszinkron szekvenciális m ű k ö d é s ű - e . E v i z s g á l a t o k feleletet a d n a k o l y a n fontos k é r d é s e k r e , m i n t p l . van-e v i s s z a c s a t o l á s az á r a m k ö r b e n , van-e a s z i n k r o n m ű k ö d é s ű t á r o l ó az á r a m k ö r b e n , hogyan t ö r t é n i k a t á r o l ó k vezérlése stb. L o g i k a i h á l ó z a t o k n á l a bemenet és kimenet k a p csolata t ö b b m ó d s z e r r e l l e í r h a t ó :
199
HÍRADÁSTECHNIKA X X I I I . ÉVF. 7. SZ. a) M e g h a t á r o z h a t ó a l o g i k a i p o n t j á n a k l o g i k a i egyenlete,
hálózat
bármely
b) k i í r h a t ó a k i v á l a s z t o t t p o n t o n l e v ő l o g i k a i é r t é k a b e m e n ő j e l e k és a t á r o l ó k belső á l l a p o t á n a k minden értéke mellett, c) a h á l ó z a t b á r m e l y p o n t p á r j a k ö z ö t t , a k é t p o n tot összekötő valamennyi útra meghatározható a késleltetési idő. E f e l a d a t o k t é n y l e g e s m e g o l d á s a sok n e h é z s é g b e ü t k ö z i k . A l o g i k a i egyenletek n a g y o b b h á l ó z a t o k e s e t é n á t t e k i n t h e t e t l e n h o s s z ú s á g ú a k lehetnek, a t á r o l ó k f i g y e l m b e v é t e l e a l o g i k a i egyenletek f e l í r á s á n á l n e h é z k e s stb. A k é t pont k ö z ö t t i késleltetési i d ő értel m e z é s e az 1—0 é s 0 — 1 á t m e n e t e k i d e j é n e k e l t é r é s e k ö v e t k e z t é b e n , a nagyobb funkcionális egységek k ü l ö n b ö z ő bemenetei é s k i m e n e t e i k ö z ö t t i e l t é r ő k é s l e l t e t é s e k k ö v e t k e z t é b e n bizonyos m é r t é k b e n ö n k é nyes. A l o g i k a i h á l ó z a t a n a l í z i s é n e k legfontosabb fela d a t a , h o g y a d o t t b e m e n ő j e l e k h e z és b e l s ő á l l a p o t o k hoz e l ő á l l í t s a az ö s s z e s k i m e n e t l o g i k a i é r t é k é t . A h á l ó z a t b e m e n ő jelei a h á l ó z a t b e m e n ő v á l t o z ó i , a k ü l s ő v e z é r l ő j e l e k és a t á r o l ó k v e z é r l é s é t v é g z ő ó r a j e l e k . A h á l ó z a t belső á l l a p o t á t t á r o l ó k v a l ó s í t j á k meg. E z e k l e h e t n e k v a g y az ó r a j e l egy m e g h a t á r o z o t t szintváltozására billenő szinkron tárolók, vagy a ka pocslécről, ill. e g y m á s r ó l vezérelt aszinkron vezérlésű tárolók. A bemenőjelek minden adott tetszőleges k o m b i n á c i ó j a és a szinkron vezérlésű t á r o l ó k a d o t t b e l s ő á l l a p o t a e s e t é n m e g h a t á r o z h a t ó az a s z i n k r o n v e z é r l é s ű t á r o l ó k é s az ö s s z e s k i m e n e t l o g i k a i é r t é k e , t o v á b b á k i s z á m í t h a t ó a szinkron vezérlésű tárolók á l t a l a k ö v e t k e z ő órajel idején létrejövő belső állapot. I l y m ó d o n r e n d e l k e z é s ü n k r e á l l az a d o t t b e m e n e t i vezérlés h a t á s á r a keletkező kimeneti jel a logikai hálózat tetszőleges pontján, valamint — a tárolók állapotainak kiíratásával — a logikai hálózat kódolt állapot-táblázata. Ezáltal olyan e r e d m é n y e k e t ka p u n k , m e l y e k m é r é s s e g í t s é g é v e l is csak r e n d k í v ü l k ö r ü l m é n y e s e n h a t á r o z h a t ó k m e g , m i v e l a b e l s ő cso m ó p o n t o k nem állnak rendelkezésre. A f e l h a s z n á l ó o r i e n t á l t p r o g r a m r e n d s z e r szempont jából m a g á t ó l é r t h e t ő d ő m ó d o n b i z t o s í t a n u n k kell, hogy a p r o g r a m a l k a l m a z á s a e g y s z e r ű legyen, a fel h a s z n á l t g é p i d ő l e h e t ő legkevesebb l e g y e n , az a d o t t s z á m í t ó g é p k o n f i g u r á c i ó ( e l s ő s o r b a n az o p e r a t í v m e m ó r i a ) k i h a s z n á l á s a o p t i m á l i s legyen. A z a l k a l m a z á s a l a p v e t ő k ö v e t e l m é n y e , h o g y a b á z i s e l e m e k és i n t e g r á l t á r a m k ö r i t o k o k s z á m í t á s á h o z s z ü k s é g e s ada tai mágnesszalagon tárolva a tervező rendelkezésére álljanak. A felhasználó a k a t a l ó g u s b a n m á r megta l á l h a t ó elemekre a t í p u s m e g a d á s á v a l ( p l . S N 7472 N ) h i v a t k o z i k . A programrendszer k a r b a n t a r t ó j a k í v á n s á g r a az a d a t b a n k o t e l v i l e g t e t s z ő l e g e s e n , a k á r n a g y o b b f u n k c i o n á l i s e g y s é g e k k e l is b ő v í t h e t i . A z a t é n y , h o g y a m é r n ö k ö k á l t a l e d d i g is h a s z n á l t i n t e g r á l t á r a m k ö r i k a t a l ó g u s és a m á g n e s s z a l a g o n t á r o l t a d a t b a n k azonos h i v a t k o z á s t b i z t o s í t , a l o g i k a i ana lízis p r o g r a m h a s z n á l a t á t e l ő s e g í t i . A programrendszer h a s z n á l a t á t j á r u l é k o s szolgál t a t á s o k k a l is c é l s z e r ű e l ő s e g í t e n i . A l o g i k a i h á l ó z a t t e r v e z é s é n e k t ö b b rutin-feladata egyszerűen prog r a m o z h a t ó , p l . a megépítéshez szükséges integrált á r a m k ö r i t o k o k s z á m á n a k és t í p u s á n a k ö s s z e s í t é s e ,
200
a megengedett és t é n y l e g e s t e r h e l é s e k m e g h a t á r o z á sa s t b . M i n d e z e k s z ü k s é g e s e k ahhoz, h o g y a l o g i k a i analízis-program h a t é k o n y eszközzé váljék a tervező kezében.
2 . Diagnosztika A z e l m ú l t é v e k b e n t ö b b eljárást dolgoztak k i egyetlen előforduló hiba k i m u t a t á s á r a . A z e l j á r á s o k a t k é t nagy csoportra oszthatjuk: (i) f i x v i z s g á l a t i e l j á r á s o k , m e l y e k n é l a v i z s g á l ó j e l e k f ü g g e t l e n e k az előző v i z s g á l a t o k e r e d m é n y é t ő l - (ii) szekvenciális v i z s g á l a t i e l j á r á s o k , m e l y e k n é l a v i z s g á l ó j e l f ü g g az előző vizsgálat e r e d m é n y é t ő l . L o g i k a i r e n d s z e r e k n é l elsősorban a f i x vizsgálati eljárásokat alkalmazzák, e z é r t csak e z e k k e l f o g l a l k o z u n k . A fix vizsgálati eljárások közül a hiba-táblázat m ó d s z e r t , az é r z é k e n y s é g i ú t m ó d s z e r t é s a h i b a szótár módszert ismertetjük. 2.1 A hiba-táblázat módszernél v i z s g á l j u n k egy k o m binációs logikai á r a m k ö r t , melynek n b e m e n e t é t jelöl je X p X , . . . X , és h i b a m e n t e s k i m e n e t é t p e d i g F (az e g y s z e r ű s é g é r d e k é b e n c s u p á n egyetlen k i m e n e t e t t á r g y a l u n k ) . A k ü l ö n b ö z ő h i b á k h a t á s a az 1. t á b l á z a t szerint f o g l a l h a t ó ö s s z e . A t á b l á z a t b a l o l d a l a a bemeneti v á l t o z ó k 2" lehetséges v á l t o z a t á n a k listája. 2
n
A hibatáblázat kiindulási
x„.
. x, x
F
1
alakja F i F , . .
1. táblázat
.Ff...
0 . . 0 0 0 . . 0 1 0 . . 1 0
0 1 0
1 0 . .. 0 . . . 1 0 . .. 0 . . . 1 0 . .. 1 . . .
1 . .. 1 1
0
0 0 .
..
1
. . .
F, m i n t e m l í t e t t ü k a h i b a m e n t e s k i m e n e t e t , F , F, . . . Fj, . . . a k i m e n e t a b b a n az esetben, h a v a l a m e l y i k h i b a o k f e l l é p . A j o b b o l d a l r ó l egyes oszlopok e l h a g y h a t ó k , nevezetesen, ha v a l a m e l y i k Fj oszlop megegyezik F - e l ( v a g y i s a / - e d i k h i b á n a k nincs h a t á s a a k i m e n e t r e ) v a g y , h a F , é s F megegyezik ( v a gyis k é t k ü l ö n b ö z ő h i b á n a k azonos h a t á s a v a n ) . E z e n t ö r l é s e k u t á n m i n d e g y i k oszlop k ü l ö n b ö z ő lesz. m m e g k ü l ö n b ö z t e t h e t ő h i b a e s e t é n m+í oszlop á l l a j o b b o l d a l o n F, F , . . . F . A z m +1 oszlopot 2 " soros h i b a - t á b l á z a t b a , T-be f o g l a l h a t j u k . A p r o b l é m a ezek u t á n T a z o n s o r a i n a k m e g t a l á l á s a , a m e l y e k a l a p j á n az oszlopok m e g k ü l ö n b ö z t e t h e t ő k . A h i b a d e t e k t á l á s c é l j á b ó l a n n y i s o r t h a g y h a t u n k k i T-böl, h o g y az első oszlop k ü l ö n b ö z ő l e g y e n a t ö b b i oszlop tól. A h i b a - d e t e k t á l á s céljából szükséges vizsgálatok Na s z á m á r a az l^sN ?sm korlát érvényes. Kimutat t á k , hogy a hiba lokalizálására szükséges vizsgálatok N s z á m á r a az 1 + 1 Idm^sN^m korlát érvényes. x
2
k
x
m
d
t
A h i b a - t á b l á z a t sorainak m i n i m a l i z á l á s a a n a l ó g a logikai kapcsolástanból ismert p r i m implikánsok meghatározásával. A hiba-táblázat kombinációs áramkörökre megszorítás nélkül alkalmazható. H á t r á n y a , h o g y a sorok s z á m a e x p o n e n c i á l i s a n n ö v e k e d i k a bemenet n s z á m á v a l . G y a k o r l a t i l a g n s l O be-
BOHÜS M—t)R. GELLER K.: T.ÖGIKAI HÁLÓZATOK SZÁMÍTÓGÉPES VIZSGÁLATA m e n e t , n é h á n y k i m e n e t és mrslOO h i b a e s e t é n a l k a l mazható. 2.2 Az érzékenység út módszernél v i z s g á l j u n k egy b á zis e l e m e k b ő l álló l o g i k a i h á l ó z a t o t . A z o k a t a h i b á k a t t e k i n t j ü k , a m e l y e k a b b ó l a d ó d n a k , h o g y az a l a p á r a m k ö r a l o g i k a i egy v a g y a l o g i k a i n u l l a é r t é k e n m e g r e k e d t . E z e k j e l ö l é s e (s-a-1), i l l e t v e (s-a-0) az a n g o l s t u c k a t 1, és s t u c k a t 0 k i f e j e z é s e k b ő l a d ó d ó a n . A z érzékenységi ú t m e n t é n előforduló hiba esetén a kimenet megváltozik. A z érzékenységi ú t m e n t é n f e l l é p ő (s-a-í) é s (s-a-O) h i b á k n á l a k i m e n e t k ü l ö n b ö z n i fog a h i b a m e n t e s á r a m k ö r k i m e n e t é t ő l . P é l d á u l az 1. á b r á n l á t h a t ó k a p c s o l á s n á l a l k a l m a z z u k az a = 0, 6 = 1, c = 0 v i z s g á l ó j e l e t . E k k o r az 1 é s 2 k a p u k o n k e r e s z t ü l v e z e t ő ú t az / k i m e n e t h e z é r z é k e n y s é g i ú t , m i v e l a 4 k a p u k i m e n e t e 0. A 4 és 2 k a p u k o n v e z e t ő ú t is é r z é k e n y s é g i ú t , m i v e l a 3 k a p u k i m e n e t e 1 és c = 0. T e h á t az a — 0, b = í, c = 0 v i z s g á l ó j e l e k é t ú t m e n t é n fellépő h i b á k a t k i m u t a t j a . M á s vizsgáló jelekkel a kapcsolás t o v á b b i útjai ellenőrizhetők.
a-0 #y
f=aAbA (a Vb)Ac
H a valamely logikai hálózat b e m e n ő változói X , . . . X é s k i m e n ő v á l t o z ó j a F, a k k o r az 2
X
v
n
F=F(X ,
X ,
1
X )
2
n
l o g i k a i e g y e n l e t n e k az X , v á l t o z ó t ó l v a l ó f ü g g é s é t a ' D,F
= ^=F(X ,
X ,
Í
X„
2
®F(X
X ,
13
...
X„
2
X )® n
X) n
k i f e j e z é s e k k e l d e f i n i á l t Boole-differencia h a t á r o z z a meg ( A © s z i m b ó l u m a k i z á r ó V A G Y , illetve modulo 2 ö s s z e a d á s j e l e ) . A B o o l e - d i f f e r e n c i a v a l a m e l y X,( l s / s n ) változóban bekövetkező X , -*X, változás h a t á s á t v i z s g á l j a . DF a következőképpen értékel hető k i : t
dF = —— = 0, a k k o r a h á l ó z a t b a n e l ő dXf f o r d u l ó e g y e t l e n h i b a nincs h a t á s s a l a k i m e n e t r e , a h á l ó z a t X - v e l szemben i n v a r i á n s . dF b) H a DjF = —rr=l, akkor a h á l ó z a t kimenete CíX; m i n d i g h i b á s , ha X,-*-X,- hiba előfordul. F feltétel nélkül függ X t ő l . dF c) H a DjF = —— =
Ha
DÍF
r
i
\\c=0
[/oft-did
q>i(Xi,
A z érzékenységi ú t a lehetséges vizsgálójeleknek csak egy t ö r t r é s z é v e l s z á m o l . E v i z s g á l ó j e l e k a h i b a t á b l á z a t azon sorainak felelnek meg, m e l y e k h e z n a g y s z á m ú h i b a t a r t o z i k . A z e l j á r á s s a l m i n d e n (s-a-í) é s (s-a-0) h i b a k i m u t a t h a t ó é s a m ó d s z e r a l k a l m a z h a t ó n a g y á r a m k ö r ö k e s e t é n is. A z é r z é k e n y s é g i ú t m ó d szer t e t s z ő l e g e s egyszeri h i b a d e t e k t á l á s á r a k i t e r j e s z t h e t ő és s z á m í t ó g é p s e g í t s é g é v e l g a z d a s á g o s a n elvégezhető. A z eljárás nem minimalizálja a vizsgáló jelek s z á m á t . 2.3 A hiba-szótár módszerrel k o m b i n á c i ó s és szekven ciális á r a m k ö r ö k e g y a r á n t v i z s g á l h a t ó k . A hiba szó t á r i s m e r t h i b á k e s e t é n fellépő v i z s g á l a t i e r e d m é n y e k rendszerezett ö s s z e á l l í t á s a . A p r o g r a m a l o g i k a i á r a m k ö r l e í r á s á t t a r t a l m a z z a és a k ü l ö n b ö z ő h i b á k a t a program b e m e n ő adatainak v á l t o z t a t á s á v a l állítjuk e l ő . A h á l ó z a t r a v i z s g á l ó j e l e k e t k a p c s o l u n k és a h i b á s esetekhez t a r t o z ó k i m e n e t e k e t r e g i s z t r á l j u k . A z í g y k a p o t t h i b a - s z ó t á r segítségével a t é n y l e g e s e n fellépő h i b á k l o k a l i z á l h a t o k . N a g y h á l ó z a t o k v a g y rendsze r e k e s e t é n a h i b a - s z ó t á r igen terjedelmes, e z é r t a d a t redukáló lekéüzések alkalmazása válik szükségessé. A d i a g n o s z t i k á v a l f o g l a l k o z ó fejezet l e z á r á s a k é n t matematikai
m ó d s z e r é t , a Boole-differencia b e v e z e t é s é t juk.
Érdekességképpen
elöljáróban
tárgyal
megjegyezzük,
h o g y a l o g i k a i h á l ó z a t o k n á l é r t e l m e z e t t B o o l e diffe rencia a h á l ó z a t e l m é l e t b e n a l k a l m a z a t t zékenységgel a n a l ó g fogalom.
n
l ó z a t k i m e n e t e csak a k k o r f ü g g X , - t ő l , h a :
1. ábra. Az érzékenységi út értelmezése
a v i z s g á l ó j e l e k g e n e r á l á s á n a k fontos
l
S, = ^ - é r -
X)
= l.
n
E z az u t ó b b i l o g i k a i egyenlet h a t á r o z z a m e g a be m e n ő v á l t o z ó k azon k o m b i n á c i ó j á t , a m e l y m e l l e t t Xi-i-Xj hiba a kimeneten k i m u t a t h a t ó . Egyetlen hiba előfordulásának esetére D , F k ö n y nyen á l t a l á n o s í t h a t ó . A z eddigiekben k i z á r ó l a g vala mely bemenő változó h a t á s á t vizsgáltuk. Ez ö n m a g á b a n is fontos eset, hiszen egy l o g i k a i rendszer v a l a m e l y r é s z h á l ó z a t á n a k k i m e n ő jele egy v a g y t ö b b t o v á b b i h á l ó z a t r é s z b e m e n e t é ü l s z o l g á l az esetek n a g y r é s z é b e n . K ü l ö n ö s j e l e n t ő s é g e lehet e n n e k a v i z s g á l a t n a k a b b a n az esetben is, h a a l o g i k a i r e n d szer p á r h u z a m o s m ű k ö d é s ű , é s a b b a n egy v a g y t ö b b segédváltozó terjed. Erre tipikus példa a r e k u r z í v átvitelképzéssel m ű k ö d ő p á r h u z a m o s ü z e m ű össze a d ó e g y s é g , a m e l y b e n a h e l y é r t é k e k egy a d o t t cso p o r t j á r a k o m b i n á c i ó s h á l ó z a t — az ö s s z e a d á s e l v é g zése e l ő t t — h a t á r o z z a m e g az egyes h e l y é r t é k e k h e z t a r t o z ó átviteli impulzusokat. A z előre m e g h a t á r o z o t t á t v i t e l i i m p u l z u s o k az egyes h e l y é r t é k e k e n az az ö s s z e a d á s t e l v é g z ő r é s z h á l ó z a t b e m e n ő j e l e i . T o vábbi példák: átvitel-terjedésen alapuló információ feldolgozó h á l ó z a t o k ( s z á m l á n c , összeadó egység, p a r i t á s v i z s g á l ó stb.), r é s z e k r e o s z t o t t , k a s z k á d m ű k ö d é s ű k o m b i n á c i ó s h á l ó z a t o k stb. Egyetlen b e m e n ő v á l t o z ó b a n előforduló hiba k i t e r j e s z t h e t ő egyetlen k a p u á r a m k ö r b e n f e l l é p ő h i b a h a t á s á n a k a n a l í z i s é r e is. Pl. H á r o m b e m e n e t ű összeadó í-edik h e l y é r t é k é n k e l e t k e z ő S, ö s s z e g é s C, á t v i t e l , h a az operandusok í-edik h e l y é r t é k e n levő s z á m j e g y e A i l l e t v e B: i;
Si = A,®
B^Ct^;
C = AB+ i
i
i
(A,+
t
Bi)C
Ul
201
HÍRADÁSTECHNIKA X X I I I . ÉVF. 7. SZ. H a Gi = AjBj k a p u á l l í t j a e l ő az á t v i t e l k e l e t k e z é s é t a d ó j e l e t , T = Aj+-B,- k a p u p e d i g az á t v i t e l t e r j e d é s t , akkor: t
St = TtG ®C t
és
u
C^Gi
+
Tfi,^
A z a l á b b i B o o l e - d i f f e r e n c i á k h a t á r o z z á k m e g a G,> i l l e t v e Ti k a p u á r a m k ö r ö k e g y i k é b e n e l ő f o r d u l ó h i b a h a t á s á t a hálózat kimeneteire:
invariancia, a feltétel nélküli függés, illetve feltételes f ü g g é s esete f o r d u l - e e l ő . H a X , — X , , Xj^-Xj változás egymást kizáró V A G Y k a p c s o l a t b a n v a n , v a g y i s a k é t h i b a o k egy i d ő b e n nem léphet fel, a k k o r a d F 2
D F: l9]
d(X ®X ) i
dC,
= T,C .-i
dG,
(
A Boole-differencia algebrai e s z k ö z ö k k e l a definí ció a l a p j á n k ö z v e t l e n ü l m e g h a t á r o z h a t ó . S z á m í t ó g é p segítségével t ö r t é n ő m e g h a t á r o z á s logikai egyenletet megoldó programrészt kíván. Egyszerűsíthető a közvetlen meghatározás az a l á b b i összefüggés f e l h a s z n á l á s á v a l : D
i
F = ~ = F(X ,
X ,
1
®F(X
2
X ,
lt
. . . . 1,
X J 0
0,
2
X) n
minden X,-re, l r s / s n esetén. Számítógép segítsé g é v e l t ö r t é n ő k i s z á m í t á s e b b e n az esetben is l o g i k a i egyenletet m e g o l d ó p r o g r a m r é s z t k í v á n . I g a z o l h a t ó , h o g y az i s m e r t m i n i m a l i z á l á s i e l j á r á s o k f e l h a s z n á l á s á v a l is e l l ő á l l í t h a t ó a B o o l e - d i f f e r e n c i a . P l . V e i t c h - d i á g r a m a l a p j á n ez ú g y t ö r t é n h e t , h o g y egy-egy m i n t e r m t á b l á n á b r á z o l j u k F(X .. .X,, . . . X) i l l e t v e F(X , X . . . , X , . . . X) logikai f ü g g v é n y t , m a j d a k é t m i n t e r m t á b l á b ó l DF szá m á r a egy h a r m a d i k a t k é s z í t ü n k . A D , F - e t á b r á z o l ó m i n t e r m t á b l a l-es t e r m j e i o t t v a n n a k , a h o l az e l ő z ő k é t t á b l a t e r m j e i antivalensek. S z á m í t ó g é p e n t ö r t é n ő e l ő á l l í t á s ezen m ó d s z e r e a s z o k á s o s m i n i m a l i z á l á s i e l j á r á s o k k i s m é r v ű t o v á b b f e j l e s z t é s é t k í v á n j a , az antivalens termek előállítására. T i s z t á n algebrai síkon t ö r t é n ő előállítás é r d e k é b e n az F f ü g g v é n y r é s z e k r e is b o n t h a t ó , é s az egyes r é szek B o o l e - d i f f e r e n c i á j á n a k i s m e r e t é b e n h a t á r o z h a t ó m e g az e r e d ő B o o l e - d i f f e r e n c i a . K e t t ő s B o o l e - d i f f e r e n c i a s z o l g á l a l o g i k a i rendszer ben előforduló k e t t ő s hiba d e t e k t á l á s á r a . K e t t ő s h i ba e s e t é n a k ö v e t k e z ő eseteket k e l l m e g v i z s g á l n i : a) a k é t h i b a e g y ü t t e s e n f o r d u l e l ő ; b) a k é t h i b a v a g y az e g y i k , v a g y a m á s i k h i b a o k v a l a m e l y i k é b e n l é p fel, de e g y i d ő b e n csak az e g y i k h i b a o k l é t e z i k ; c ) a k é t h i b a v a g y az e g y i k , v a g y a m á s i k h i b a o k m i a t t f o r d u l e l ő , v a g y m i n d k e t t ő egyszerre f e l l é p . E g y s z e r ű s é g k e d v é é r t l o g i k a i h á l ó z a t X,-, i l l . Xj b e m e n ő v á l t o z ó j á b a n fellépő X/---X,-, i l l . XJ-*XJ v á l t o z á s l e g y e n a h i b a o k a . V i z s g á l j u k m e g ennek h a t á s á t F(X X , . . . , X , , . . . , X , . . . , X) logikai függvényre. l;
n
1
2 >
;
l é n y e g é b e n e g y v á l t o z ó s Boole differencia segítségével analizálható a hiba. r
K i m u t a t h a t ó , hogy a hiba-detekció visszavezethető a k é t hibaok külön-külön történő vizsgálatára a kö vetkezőképpen :
2
;
dF F=———- — F(X , d(X,Xj)
n
2
. . . ,X,-,
1
, X )&F(X , n
1
X,-,
Xj,
Xj, ...
X) n
kifejezéssel definiált k e t t ő s Boole-differencia segít ségével v i z s g á l h a t ó a hiba h a t á s a . A z előzőekhez ha s o n l ó a n DjjF k i é r t é k e l é s é v e l h a t á r o z h a t ó m e g , h o g y
202
dF
2
d(Xi@Xj)
dF
~~dX~ dX +
i
H a a k é t h i b a o k k ö z ü l v a g y az e g y i k , v a g y a m á s i k , v a g y m i n d k e t t ő egyszerre l é p h e t f e l , a k k o r a k é t hibaok vagy kapcsolatban van, h a t á s á n a k vizsgála tára dF 2
D
i
+
'
F
=
d(X
i
+
Xj)
k e t t ő s Boole-differencia a l k a l m a z h a t ó . K i m u t a t h a t ó , h o g y a h i b a - d e t e k c i ó e b b e n az esetben az e g y i d e j ű l e g f e l l é p ő é s az e g y m á s t k i z á r ó k e t t ő s h i b a a n a l í z i s é r e v e z e t h e t ő vissza az a l á b b i m ó d o n :
n
H a Xi^-Xi; Xj^-Xj v á l t o z á s e g y i d e j ű l e g l é p fel, vagyis a k é t hibaok É S kapcsolatban v a n : D
dF
,F -
D,-m
dF
dF
2
t
V
j
D F l+I
=
d(X
t
+ Xj)
d(X,
+ Xj)
dF 2
2
+-
d(X,Xj)
IRODALOM [1] £>. B. Armstrong: On Finding a Nearly Minimai Set of Fault Detectlon Tests for Combinational Logic Nets. I E E E Trans. on E l . Computere, Vol. EG—15, No. 1. pp. 66—73, 1966. [2] Bohus M.: Statikus és dinamikus hazárd vizsgálata aszinkron működésű logikai hálózatokban. Mérés és Automatika. X V I I I . és 4—5. szám 121—126. old. 1970. [3] Bohus M.: Digitális rendszerek tervezése. Tankönyvki adó Budapest 1969. [4] Bohus M.: Elektronikus számítógépek. Tankönyvkiadó, Budapest, 1966. [5] Bohus M.—Csopaki Gy.—Gefferth L.—Halász E.—Németh G.—Trón T.—Varró L.: A LOGAN logikai szimulációs program. Híradástechnika (ebben a számban). [6] H. Y. Chang—W. Thomis: Method of Interpreting Diagnostic Data for Locating Faults in Digital Machines. B S T J . Vol. 46. pp. 289—317. February 1964. [7] Hv Y. Chang: An Algorithm for Selecting an Optimum Set of Diagnostic Tests. I E E E Trans, on E l . Computers, Vol. EC—14, No. 5. pp. 706—711. October 1966. [8] Csurgay Á.—Géher K.—Házmán I.: Helyzetkép a háló zatelmélet fő fejlődési irányairól. MTA Műszaki Tudo mányok osztálya, Távközlési Rendszerek Bizottság. 24. old. 1971. [9] R. W. Downing—J. S. Nowak—L. S. Tuomenoksa: No. 1. ESS Malntanence Plan. BSTJ. Vol. 43. pp. 1961—2020. September 1964. [10] Drasny J.: Automatikus tervezés a Számítástechnikai Koordinációs Intézetben. Híradástechnika (ebben a számban). [111 P- C. Garton—S. P. O'Byrne: Applications of Logic Simulation in Large Real Time Systems. I E E Conference Publication No. 51. pp. 51—58. 1969. [12] Géher K.: Számítógép programok katalógusa 1969. Híra dástechnika, X X I . évf. 6. szám. 178—184. öld.
B O H U S M — D R . G É H E R K . : L O G I K A I HÁLÓZATOK SZÁMÍTÓGÉPES V I Z S G A L A T A
[13] K. Géher: Theory of Network Tolerances. Akadémiai Kiadó, Budapest, 1971. [14] Géher K.: Számítógép programok katalógusa 1970. Híra dástechnika, X X I I . évf. 8. szám. 246-255. oid. [15] G. G. Hays: Computer-Aided Desing: Simulation of Di gital Design Logic. I E E E Trans. on Computere, Vol. G—18, No. 1. pp. 1—10. January 1969. [16] G. Insinga: Simulazione de reti logiche mediante calcolatore numerieo, Alta Frequenza, Vol. X X X I X . No. 3—4. 1970. [17] A. A. Kaposi: Logic Testing by Simulation. I E E Conference Publication No. 51. pp. 31—40. 1969. [18] W. H. Kautz: Fault Testing and Diagnosis in Combinatiónal Digital Circuits. I E E E Trans. on Gomputers, Vol. C—16. pp. 353—366. April 1968. [19] J. B. Krushal—E. R. Hart: A Geometric Interpretation of Diagnostic Data from a Digital Machine, Based on a Study of the Morris Illinois Electronic Central Office. BSTJ Vol. 45. pp. 1299—1338. October 1966. [20] F. Lee: An Automatic Self-checking and Fault Locating Method. I R E Trans. on E l . Computere, Vol. EG—11, pp. 649—654. October 1964. [21] F. Leraillez—A. Sarre—B. Waterlot: CRISMASS: a Tool for Gonception, Realisation, Implementation and Simu lation of Sequential Synchronous Machines, I E E E Conference Publication 51. pp. 59—71. 1969.
[22] C. S. Lorens: Invertible Boolean Functions, I E E E Trans. on E l . Computere, Vol. EC—13, No.5. pp. 529—541. Oc tober 1964. [23] P. N. Marinos: Derivation of Minimai Complete Sets of Test-input Sequences Using Boolean Differences. I E E E Trans. on Computere. Vol. C—20. pp. 25—32. January 1971. [24] R A C A L Research Limited: R E D A P 22. Simulation of an Interconnected System of Logic Elemenst (SISLE). R E D A C User's Manuál, Vol. 2. 1969. [25] J. P. Roth: Diagnosis of Automatic Failures: A Caculus and a Method. I B M J . Res. and Dev. Vol. 10. pp. 278—291. July 1966. [26] J. P. Roth—W. G. Bouricius—P. R. Schneider: Programmed Algorithmus to Compute Test to Detect and Distinguish Between Failures in Logic Circuits. I E E E Trans. on. E l . Gomputers. Vol. EC—16. No. 5. pp. 567—580. October 1967. [27] F. F. Sellers—M. Y.Hsiao—L. W. Bearnson: Errordetecting Logic for Digital Computere, Mc Graw-Hill, New York 1968. [28] Sebestyén B.: Számítógép-bázisú automatikus ellenőrző rendszerek. Mérés és Automatika 172—176 és 270—274. old. 1970. [29] D. J. K. Wise: LIDO-An Integrated System for Com puter Layout and Documentation of Digital Electro-nics. I E E Conference Publication No. 51. pp. 72^—81. 1969.
