Mikroszámítógépes program logikai függvények minimalizálására KÁLDI TIBOR Országos Mérésügyi Hivatal S Z E N T IDA Y K L Á R A K a n d ó K á l m á n Villamosipari Műszaki
Illil WKM
Főiskola
ÖSSZEFOGLALÁS A kombinációs h á l ó z a t o k tervezésének egyik a l a p v e t ő szempontja, hogy az előírt specifikációt a lehető leg g a z d a s á g o s a b b a n valósítsuk meg. A logikai szintézis nek a mikroelektronikai t e r v e z é s b e n is jelentős szerepe van. E g y - é s t ö b b k i m e n e t ű (max. 10) logikai függvé nyek minimalizálására alkalmas, Z X Speetrum szemé lyi s z á m í t ó g é p e n f u t t a t h a t ó , A S S E M B L Y nyelven írt programot k é s z í t e t t ü n k , ami az M . A . Breuer által bevezetett, irredundáns lefedési algoritmusra épül. E r e d m é n y e i n k e t dekóder áramkör tervezési példájával illusztráljuk.
Bevezetés A mikroelektronikai tervezés fontos elemét képezi a logikai szintézis. A hazánkban is ü z e m b e állított, elsősorban a berendezés-orientált áramkörök fej lesztésére alkalmas Hierarchikus Tervező Rend szer ( H T R ) a szintézis eljárásokkal megfelelően kiegészítve gyorsabb és hibamentesebb tervezést tenne l e h e t ő v é [ 1 ] , [2]. Munkánk a logikai (Boolefüggvények minimalizálásával foglalkozik, és az el készített program kezdeti lépését jelentheti egy önálló, de a H T R - h e z kapcsolódó Logikai Szintézis Alrendszer szoftvernek. A logikai függvények — mint ismeretes — al gebrai ú t o n , grafikus eljárással vagy számítógépes módszerekkel minimalizálhatók. Nagyobb v á l t o zószám esetén csakis ezen utóbbi megoldás jöhet szóba, mivel az elterjedten alkalmazott Karnaughtábla 8—10 v á l t o z ó felett már nehezen áttekinthe t ő és lassan kezelhető. A számítógépes módszerek k ö z ö t t figyelemre méltó a Melvin A . Breuer [3] által kidolgozott, ú n . irredundáns lefedési algorit mus-csoport, ami szemléletessége ós kis tárkapa citás-igénye folytán az egyszerűbb kategóriájú személyi számítógépekre is k ö n n y e n adaptálható. Az algoritmusok által definiált műveletek kizáró lag karakter füzéreken (string változókon) végre hajtott logikai műveletekre korlátozhatók, ame lyek jól illeszkednek az A S S E M B L Y nyelvhez. Az irredundáns lefedési eljárás egyik sajátossága, hogy az áramkörtervező által előírt logikai függ v é n y , az ú n . kezdeti lefedés, tetszőleges lehet olyan értelemben, hogy nem szükséges a f ü g g v é n y t a normál alakra visszavezetni, mint pl. a QuineMcCluskey numerikus eljárás esetében [4]. * K ö z l e m é n y ü n k Z X Speetrum (48 K ) személyi számítógépre kidolgozott minimalizálási progra mot ismertetet, ami Melvin A . Breuer módszerén alapul. A z eredményül kapott irredundáns lefedés kétszintű É S - V A G Y , ill. N E S - N E S kapus háló zattal valósítható meg.
KÁLDI
TIBOR
elődjénél dolgozott a tranzisztor gyártás szak ién. 1967-től az OMH Optikai osztályán radio metriai méréstechnikával és fotódetektor ok vizsgála taival foglalkozik.
A Jedlik Ányos Közle kedés gépészeti Techniku mot 1958-ban végezte el. 8 évig az EIVRT-ben, a TUNGSRAM RT jogSZENTIDA
Y
KLÁRA
Oki. fizikus, oki. elektro nika szakmérnök, egy. doktor. Korábban a Híra dástechnikai Ipari Kutató Intézet (a MEV jog elődje ) tud. főmunkatársajelenleg a KKVMF KATI docense, szak csoportvezető. Szakmai te vékenysége : tranzisztor strukturavizs gálatok, optoelektronikai félvezető eszközök méréstechnikája, minőségellenőrzés, Okta-
tási területe a félvezetők konstrukciós számításai, digitális áramkörök.
2. Az algebrai íormalizinus írjuk fel a logikai f ü g g v é n y kiindulást képező alakját szorzattagok (mintermek, P tagok) össze geként. H a a f ü g g v é n y t algebrai ú t o n egyszerűsít jük, olyan szorzattagok is előfordulhatnak, ame lyekből bizonyos változók kiestek. A z ilyen csonka P tagot az egyszerűbb algoritmizálhatóság érdeké ben J . P . R o t h [5] ú n . kocka (cube) alakjában fejezte ki. Legyen pl. a c = A A szorzattag egy háromváltozós f ü g g v é n y egyik tagja, amit a hiányzó A% változóval A A A + A A^A szerint egészíthetünk ki. A z A közömbös v á l t o z ó t cc-szel, a ponált v á l t o z ó t 1-gyel é s a negáltat 0-val jelölve, a c kocka x
1
Z
s
3
X
Z
2
c= 1X0
formában írható fel. A kocka-specifikáció lényege tehát, hogy az n változós B o o l e - f ü g g v é n y t n dimenziós vektorok (kockák) halmazával adjuk meg. A c vektor össze t e v ő i c = { 0 , 1, x} értékűek, és az / függvényt az f — { v 2> c
C
.}
B e é r k e z e t t : 1988. V I . 6. (H)
kockahalmazzal definiáljuk. A gépi algoritmusok s z á m o s operátort és műve letet értelmeznek a kockák és a kockahalmazok között. E z e k közül a metszet ós az éles szorzat is mertetésére térünk ki.
446
Híradástechnika
XXXIX,
évfolyam,
1988, 10. szám
1. láblázat
A metszet koordináta-táblája
.0 1 x
a,
0
Q
Q
1 1
0
E z u t ó b b i e r e d m é n y éppen a ü halmaz P tagos alakja. E l l e n t é t b e n a metszettel, az éles szorzat nem k o m m u t a t í v m ű v e l e t , a szorzótényezők sor rendje t e h á t nem cserélhető fel. Halmazműveletek. A metszet és az éles szorzat koc kahalmazokra is kiterjeszthető. Legyen C é s Gj k é t w-dimenziós halmaz. E k k o r
0 1 x
4
Gi^C =-
yj
}
2. táblázat
Az éles szorzat koordináta-táblája
[ y>
w
d*C = f
«'€ c*
(c'o )]és c
[c'#C]
ahol ' # ( ? / = ( . . .(c'#c )#c )#c . . .)#ön) itt Gj = (c c , . . . , c«) értékű. (c'ZCi jelentése: c' eleme a Gt halmaznak.) c
#
0 ai
1 x
0
1
x
z y 1
z
y
z 7, z
0
1
2
t
n
y
2
xy
l
2
{
n
xy
Éles szorzat. A P tagos alaknál maradva, a c^-nek a c„-nal való éles szorzata v
x
y
C=ip (üres halmaz), ha a #b = z minden i-re; c # C g , = c . ha bármely i-re y adódik. i
Az irredundáns lefedés algoritmusait t ö b b , egy m á s t k ö v e t ő lépésre bontva ismertetjük. A z algo ritmusok levezethetők a Boole-algebra alaptételei ből és szemléltethetők a Karnaugh táblán. 1. lépés: implikáció. N é z z ü k az 1. ábra példáját A ^ = 01x1 hurok benne foglaltatik a c = x l x l hurokban, vagyis q implikálja c -t ( q - ^ C g ) . Amennyiben c -*c fennáll, c^c^ip (üres hal maz) adódik és c e l h a g y h a t ó . 2. lépés: kockatörlés. A 2. ábra kezdeti lefedését tekintve, b e l á t h a t ó , hogy a C5 kocka felesleges, hiszen a többi n é g y rendre lefedi annak egy-egy celláját. Valamely c kocka akkor törölhető, ha k i emelve azt a G halmazból, a c#((7—c) m ű v e l e t eredménye f-vel lesz egyenlő. A példánál maradva b e l á t h a t ó , hogy 2
2
x
2
1
1
alapján értelmezhető, ahol a c =P(a) és a c =^P(b) megfeleltetéssel élünk. A 2. táblázat alapján nyer h e t ő G f ü g g v é n y kockahalmaz, ami a k ö v e t k e z ő k é p p e n definiálható:
x
3
(((C5#C )#C )#C )#C4=
#c =P(a).P(b)
Cx
2
2
3. Az irredundáns lefedés alforitmusai
Metszet. A c^Cy m ű v e l e t az 1. táblázat segítségé vel v é g e z h e t ő el. c = (a a . . .a .. .a ), c = = (bjb . . . & { . . . & „ ) é s az eredményül kapott ú j kocka c = (d d .. .d . . .d ). Legyen pl. 0^ = 10x1 és C;c = x 0 1 1 . Az azonos pozícióban l é v ő elemek k ö z ö t t e l v é g e z v e a kijelölt m ű v e l e t e t , 0 ^ = 1 0 1 1 lesz az eredmény. Legyen most 0^ = 10x0, ekkor a negyedik elemnél Q o l v a s h a t ó k i a táblázatból. H a bármely pozícióban Q adódik, az eredményül kapott c kocka üres halmaz lesz, amit ^-vel jelölünk. Nem nehéz felismerni, hogy a metszet nem m á s , mint a k o c k á k n a k megfelelő, csonka P tagok szorzata. x
1
1;
i
2
3
f.
Megjegyezzük, hogy a vizsgált c k o c k á t k ö v e t ő (C-c) halmaz kockáinak sorrendje az éles szorzatok végzésekor tetszőleges lehet. 3. lépés: elemtörlés. A 3. ábrán l á t h a t ó p é l d a alap ján ezt a lépést inkább a „ h u r o k b ő v í t é s " n é v v e l il lethetnénk. A z elemtörlósnél t e h á t azt a folyama tot algoritmizáljuk, amikor a kezdeti lefedést na gyobb, t ö b b cellát befogó hurokkal helyettesítjük
x
Egyébként:
Vb
^ ( a ^ . . .ai_ owai . . .a ) i ahol CCÍ = a # ö , ós h a i-edik elemet törölni kell. H a x 1-gyel, vagy 0-val e g y e n l ő , a kocka ezekkel az értékekkel szerepel az e r e d m é n y b e n . a halmazok egyesítésének m ű v e l e t e (unió). Az éles szorzat ez utóbbi v á l t o z a t á t világítsuk meg egy példával. Legyen c ^ l x O x és c ^ x l x l . A z eredmény a O = {100x, 1x00} halmaz lesz. E z t igazolhatjuk, ha szorzattag alakban írjuk fel a k o c k á k a t és a DeMorgan szabályt alkalmazva Cx^pCy—
t
1
+1
n
AjA$K
^ 00
01
11
10
4
t
w
elvégezzük a P ( a ) -P(b) m ű v e l e t e t . c =P(a) = A A és v =P(f>) — A AA, sel: c
x
X
Z
%
c% # c = A^^A^i)
3
2
1 1
; ;
J!
1
megfeleltetés
IH480-1I
= ^4j-4 (-<4 + A 4) = A A A
y
Oi
\(l
t
2
s
+
1. ábra. I m p l i k á c i ó : a c ^ O l x l k o c k á n a k megfelelő hurok benne foglaltatik a c = : x l x l k o c k á n a k meg felelő hur okban 2
+ Híradástechnika
XXXIX.
A^A Ai z
évfolyam,
1988. 10. szám
447.
1
a
á
oo
P \
n
01
10
00 01 ,
11
i
' 1 \
í /
1
' t
1 i
'
;
1
10
!
/
j
H480-2
Visszatérve a 3. ábra példájához, az elemnegálás azt jelenti, mintha a kiválasztott k o c k á t reprezen táló hurkot valamelyik irányba eltoltuk volna. H a a léptetett hurok által befogott cellákat a többi hurok (kocka) lefedi, a b ő v í t é s elvégezhető. 4. lépés: közös implikánsok keresése. A k kimenetű kombinációs hálózat k darab logikai függvényből álló függvényrendszerrel jellemezhető. A hálózat tervezésének egyik lehetősége, hogy az egyes k i menetekhez tartozó logikai f ü g g v é n y e k e t különkülön, egymástól függetlenül minimalizáljuk. Gaz daságosabb megoldást kaphatunk azonban, ha az e g y m á s t ó l független minimalizálást k ö v e t ő e n meg keressük azokat az implikánsokat, amelyek k é t vagy t ö b b f ü g g v é n y b e n közösek. Nézzünk egy példát a közös implikánsokra. Legyen f = A A$+A A és f =A A + A A. Az f'-hez t a r t o z ó kezdeti lefedést a 4a. ábra, míg / kezdeti lefedését a 46. ábra szemlélteti. Kockákkal kifejezve: 0 = { x l l , Olx}; C = { l x 0 , l l x } /!-et t e h á t a C és / - t a C halmaz reprezentálja. K é p e z zük e k é t halmaz m e t s z e t é t a C^C^ művelettel. Az 1. koordináta-táblázatot h a s z n á l v a : C nC =xll^llx = lll 1
2
2
L
2
1
s
X
2
2
2. áöra. K o c k a t ö r l ó s : A c = l l x x kockának megfelelő hurok teljesen fedve van a Ci = lxOO, c = x l 0 1 , c = l x l l és c = x l l 0 k o c k á k n a k megfelelő hurok egy-egy cellája által 5
2
3
4
1
2
2
l
a Karnaugh táblán. Ezáltal a kockákban a {0, 1} elemek x-re változnak. A z algoritmus lépései a következők. Vesszük az első c k o c k á t és annak {0, 1} elemeit sorszámmal látjuk el. A z i=l elemet negáljuk. A z í g y nyert c(i = l ) kockát kiemelve a C halmaz ból, éles szorzat-sorozatot végzünk. Amennyiben
adódik, a c kocka i — 1 elemét a;-re írjuk á t . A c koc k a ezután átírt formájában szerepel a G halmaz ban. A z eljárást valamennyi i-re (i?sn) elvégezzük, és a C halmaz valamennyi kockáját megvizsgáljuk a bemutatott m ó d o n .
1
A
2 \
0
0
0 1
77
,
1
1
x
é
2
2
2
±
2
1 0
<7 ={111, 0 1 x } é s C = { l l l , 1x0} 1
2
adódik, ami egyszerűsíti a realizálást, hiszen az 111 kocka mint közös kapu, m i n d k é t kimenethez csatlakoztatható.
A
1 i
2
adódik, a többi párosítás rp-t eredményez. A met szet eredménye, ami nem m á s , mint az f és f függvények szorzata, a 4. c. ábrán látható. Mind / - b e , mint / - b e beírható a közös implikáns, és cse rébe elhagyható f^hől / - b ő l az AA szorzattag, mivel ezek második celláját mind / \ m i n d / esetében a másik hurok lefedi. Végered ményben 2
c(i = l ) # ( C - c ) = y
A
2
1
A
2 \
0
0
0
1
7 7
00
i
01 11
7
1 0
7
j i ')
-\ i
i 7
i i i i
J
k
10
7
i
7
7
7
b., H 480-3 3. ábra. Elemtörlós: A c = x l 0 1 kocka i = 2 elemét negál' felelő hurok lefed. H a s o n l ó k é p p e n kö-*
c ( i = 2 ) = x l l l adódik, amit a c = x x l l kockának megh e t ő a c = 1100 kocka elemcseréje is.
448
Híradástechnika
2
2
3
1
XXXIX.
évfolyam,
1988. 10. szám
jA
A
A
Q.
i
2
77
7
0 f .
1
r
AjA
AA
2
3
01
n hi\
1
1
1 2
AjA
12 10
2
?
A-SJ±
00
00
01
7 7
1 0
\
A 1 ,2 A
\ A]A A 2
3
e-,
H48CK %,4. ábra. P é l d a k ö z ö s i m p l i k á n s keresésére: a) a z / f ü g g v é n y kezdeti lefedése b) a z / f ü g g v é n y kezdeti lefedése 1
3
Az algoritmizálás a k ö v e t k e z ő k é p p e n történik.^ Meg kell vizsgálni a kezdeti lefedést jelentő, k s z á m ú halmaz egymással való összes lehetséges metszetét. H a pl. a halmazban szereplő c kockának a G halmazban l é v ő c k o c k á v a l való metszete y>-től különböző, c ^c = c új kocka keletkezik. E z t k ö v e t ő e n meg kell vizsgálni, hogy a Gi halmazban Cj halmazban a c he lyettesíthető-e a c -nel. H a mindkét halmazra teljesülnek a lefedési feltételek, c és c törlendő és mind Cj-be, mind C -be c írandó. A halmazok egymással való metszetének m ű v e l e t é t mindaddig meg kell ismételni, amíg új kocka keletkezik. Valamely kocka elhagyásának vizsgálatához elő kell állítani a metszettől különböző összes variánst. Hogy azokat lefedi-e a halmaz többi eleme, arról a 2. lépésnek megfelelő éles szorzat műveletsor ad felvilágosítást. Költségfüggvények. A logikai függvények m e g v a l ó sításának költségeit korábban a szükséges kapuk s z á m a alapján határozták meg. A mikroelektroni k á b a n , ahol egyetlen félvezető lapkán helyezik el az egész áramkört, nagyobb jelentősége van a k a p u b e m e n e t s z á m és a F A N OUT csökkentésének. Általában többféle költségfüggvényt definiálnak, amelyek a fenti jellemzőket tartalmazzák. x
}
y
x
y
xv
y
xy
x
3
v
xy
4. Programszerkesztés Kiindulási
feltételek:
— a minimalizálandó logikai f ü g g v é n y t szorzatok összegeként kell megadni; — tetszőleges kezdeti lefedés választható a csonka P tagokat kockákkal kifejezve; — egyszerűsített lefedésből indulunk k i C - * C K J D C alapján, ahol C az igaz (care) é s D C a közöm bös (don't care) halmaz; — a program t ö b b k i m e n e t ű függvények minima lizálására készült, amely — értelemszerűen — ma g á b a n foglalja az e g y k i m e n e t ű kombinációs függ v é n y e k esetét is. A program bemenet, kimenet ós interaktív t ö m b j é t B A S I C nyelven írtuk meg, míg a feladat megoldó rész A S S E M B L Y nyelven készült. 0
0
Híradástechnika
XXXIX.
évfolyam,
1988. 10. szám
•* Bemeneti
jellemzők
Az egyes kockák elemeinek n száma maximálisan 20 lehet azzal a megkötéssel, hogy a k ö z ö m b ö s változók (az x-értékek) s z á m a nem lehet nagyobb 16-nál. A f ü g g v é n y k i m e n e t e k k s z á m a maximáli san 10 lehet. Egy-egy kimenethez max. 64 darab kocka tartozhat, azonban a kockák összes s z á m a nem lépheti t ú l a 255-öt. A z adatbevitel kockán k é n t történik a {0, 1, x } szimbólumok bevitelével, majd feltüntetjük, hogy a beírt kocka mely kimene tekhez tartozik, ül. nem tartozik: az a k t í v k i menetet 1-gyel, és az i n a k t í v kimenetet x-szel jelölve. Kimeneti adatok A program első lépésben a kimenetenkénti mini malizálást végzi el. Amennyiben e g y k i m e n e t ű logikai f ü g g v é n y t vizsgálunk, a feladatmegoldás véget is ért. T ö b b k i m e n e t ű f ü g g v é n y esetén a program második lépésben elvégzi a közös implikánsok megkeresésén alapuló minimalizálási el járást is. A program kiszámítja az alábbi költségfüggvé nyeket : Kapubemenetek száma Kapuk száma Max. F A N I N Max. F A N OUT É S - V A G Y realizáció esetében a Max. F A N I N megadja, hogy maximálisan h á n y b e m e n e t ű ÉS kapura van szükség. A Max. F A N OUT azt jelenti, hogy egy ÉS kapu kimenetre maximálisan h á n y darab V A G Y kapubemenet csatlakozik. Perifériák A program mind magnetofonkazettás, mind haj lékony mágnes lemezes változatban elkészült. E z azt jelenti, hogy mind a bevitt adatok, mind pedig a részeredményként és v é g e r e d m é n y k é n t kapott kockahalmazok és költségfüggvények hát tértárra kivihetők, ill. onnan betölthetők. A Z X Spectrum géphez Seikosha G P 50S (ill. 100S) printer illeszthető é s az eredmények oldalanként kinyomtathatók. 449
HA80-5I
/ / /_/ 0
i n n /i n i /"
N
I IL
I \l
I I I
I I _/ /
74
75
16
17
23
24
25
26
27
28
29
30
31
5. ábra. 9-szegmenses kijelző képe ós a megjeleníteni k í v á n t karakterkészlet
5. Tervezési példa Szintézisprogramunkat 9-szegmenses kijelző dekóder tervezési példájával illusztráljuk. A 9-szeg menses karaktermegjelenítő képe é s szegmenseinek jelölése az 5. ábrán l á t h a t ó . Az ábra feltünteti az általunk példaként választott karakterkészletet is, amelyet a kijelző megjelenít, ha a dekóder be menetére bináris alakban az egyes karaktereknél feltüntetett számnak megfelelő jelsorozatot adjuk. P l . a 7-es s z á m j e g y a 00111 jelsorozattal g y ú j t h a t ó k i , ahol a 0 a logikai L-szintet és az 1 a logikai H szintet jelöli. A 9-szegmenses kijelzővel már csak nem valamennyi b e t ű , és sokféle szimbólum is megjeleníthető, m í g az ismertebb 7-szegmenses v á l t o z a t o t inkább csak a számjegyek kiíratására 3. tahiázat
A dekóder logikai függvényének kezdeti lefedése Kimenetek
Bemenetek EN 0 1 1 1
450
LT E
D
C
B
A í
X
X
X
X
X
X
X
0 1 1
X
X
X
X
X
0 0
0 0
0 0
0 0
0 1
f
d
X
X
1
h x 1
X
X
X
X
X
1
1 1 X
b x 1 1 1
alkalmazzák [6]. A teljesség kedvéért a dekódert engedélyező bemenettel ( E N ) és lámpavizsgáló bemenettel ( L T ) is elláttuk. H a az E N bemenet L-szintet kap, a kijelzés letiltott, m í g H-szint 4. táblázat
Az irredundáns lefedés végső eredménye Bemenet 1x01111 1x10011 1x10110 lxxlOlO lxlllOx lOxxxxx 1x11100 1x01010 1x11x01 1x00x10 1x00011 lxOlOOx 1x0x110 1x10x00 lxllOlx lxOlxxl lxxOlOx lxxlOxl lxxOlOl 1x11011 1x0x1x0 lxlOxlx lxxxOOO
Kimenet lxxxxlxxx llxxlxxxx lxlxxxxll lxxxxxxxx 111111111 xllxxxxxx xlxxxxxxx xxlxxlxxl xxlxxlxxx xxlxxxxxx xxlxxxxxl xxlxxxxxx xxllxxxxx xxlxxxxxx xxxlxxxxl xxxlxlllx xxxlxxxxx xxxlxxxxx xxxllxxlx
Híradástechnika
XXXIX.
Bemenet 1x01x11 1x01lxx lxlOlxx lxxOxlO 1x10001 1x10100 1x0x000 1x0x101 lxxlOOO 1x1x010 1x11x10 lxOlxOx lxOOlxx lxOlOxx lxOxxll lxxOOOx 1x00x00 1x00x11 1x10x01 lxOxOxx 1x1x001 lxxxlll
évfolyam,
Kimenet xxxxlxxxx xxxxlxxxx xxxxlxxxx xxxxlxxxx xxxxxlxxx xxxxxllxx xxxxxlxxl xxxxxlxxx xxxxxllxx xxxxxlxxx xxxxxlxxx xxxxxlxxl xxxxxxlxx xxxxxxlxx xxxxxxlxl xxxxxxlxx xxxxxxxlx xxxxxxxlx xxxxxxxlx xxxxxxxlx xxxxxxxxl
1988. 10. szám
5. táblázat
Költségfüggvények
Kapubemenetszám Bemeneti kapuk sz. Kapuk száma Max. F A N I N Max. F A N OUT
Kezdeti lefedés
Kimenetenként! min.
371 33 42 7 9
321 63 62 6 9
290 45 54 6 9
esetén engedélyezett. H a az L T bemenet L-szintet kap, a kijelző valamennyi szegmense aktivizálódik. A logikai f ü g g v é n y kezdeti lefedésének n é h á n y sorát a 3. táblázat tartalmazza. A többi sor az 5. ábra alapján egyszerűen meghatározható. A minimalizálás végső eredményét a 4. táblázat t ü n t e t i fel. A dekóder működését egyszerű B A S I C n y e l v ű program segítségével szimuláltuk, ellenőriz ve a 4. táblázatban foglalt eredményeket. A z 5. táblázat a költségfüggvényeket adja meg a kezdeti lefedés, a kimenetenkónti minimalizálás ós a közös implikánsok megkeresése u t á n . Mint a 4. és 5. táblázatból látható, a végső eredményben lényegesen lecsökkent a kapubemenetek s z á m a a kezdeti lefedéshez képest, a k a p u s z á m azonban m e g n ő t t . A program teljes futási ideje kb. 15 s nagyságú volt. A programot s z á m o s példával teszteltük és ta pasztaltuk, hogy a futási i d ő az adatstruktúrától is
Híradástechnika
XXXIX.
évfolyam,
1988. 10. szám
lényegesen függ. Vizsgálataink és becsléseink arra utalnak, hogy maximális terjedelmű adatbevitellel a legkedvezőtlenebb esetben mintegy félórás futási időre lehet számítani. 6. Köszönetnyilvánítás Szerzők köszönetet mondanak Keresztes P é t e r főiskolai docensnek, amiért a probléma érdekessé gére felhívta figyelmüket.
IRODALOM [1] Automatikus s t r u k t ú r a szintézis a Hierarchikus • Tervező Rendszerhez. T a n u l m á n y . K é s z ü l t a Mik roelektronikai K o r m á n y b i z t o s ós a M E V m e g b í z á sából 1985-ben. Szerzők: Keresztes Péter, Ágotái István stb. [2] Design Automation of Digital Systems. Chapter One, R . J . Preiss. 1972 by Prentice-Hall, I n c . [3] Design Automation of Digital Systems. Chapter Two, Melvin A. Breuer. 1972 by Prentice-Hall, Inc. [4] Janovics-Tóth: A logikai t e r v e z é s módszerei 2., j a v í t o t t kiadás. Műszaki K ö n y v k i a d ó , B p . 1976. 4.fejezet. [5] J. P. Roth: „Algebraic Topological Methods for the Synthesis of Switching Systems. I . " Trans. Amer. Math. S o c , Vol. 88 (1958), pp. 301—326. [6] Kis Halas—Mészáros—Szentiday: Optoelektronikai kijelzők és megjelenítők. Műszaki K ö n y v k i a d ó ' B p . 1984. 1. fejezet.
451
