1. GSA1 Mealy
2. O1="y1,y2"; O2="y2,y3"; O3="y3,y4"; O4="y1,y4"
3. C1="not x3"; C2="not x2"; C3="x1"
4. 2-and, 3-and, 2-or, 3-or, 2-xor, not, JK-triger
Vastav graafskeem on toodud paremal.
| Matriklinumber 999999: 1. GSA1 Mealy 2. O1="y1,y2"; O2="y2,y3"; O3="y3,y4"; O4="y1,y4" 3. C1="not x3"; C2="not x2"; C3="x1" 4. 2-and, 3-and, 2-or, 3-or, 2-xor, not, JK-triger Vastav graafskeem on toodud paremal. |
|
Liigse ettenäitamise vältimiseks on kasutatud siiski GSA5, sest seda Mealy automaadina ülesandes pole. Kõik muud parameetrid on samad.
|
Algoritmi realiseerimiseks piisab kolmest olekust - S1, S2, S3. Siirete
kontroll näitab, et ühest olekust teise minnes läbitakse
täpselt üks operatsioonide plokk. Samuti pole konflikte
tingimuslike plokkide läbimisel. Siirded on järgmised: S1 -> S2: !x3 / y2, y3 ja x3 / y3, y4 S2 -> S1: !x2 / y1, y2 S2 -> S3: x2 / y1, y4 S3 -> S1: !x1 / y1, y2 S3 -> S3: x1 / y1, y4 Siirete loetelu alusel on väga mugav välja kirjutada automaadi tabel. |
 |
| |
|
|
|
| |
|
|
|
| x3 |
|
S2 |
y3, y4 |
| x2 |
|
S3 |
y1, y4 |
| x1 |
|
S3 |
y1, y4 |
Kuna kasutusedl on JK-trigerid, siis oleks hea kasutada naaber- või sellele lähedast kodeeringut. Siis muutuks siirdel võimalikult vähe olekubitte ja selle tõttu peaks ka siirdefunktsioon lihtsam tulema. Antud juhul pole täielik naaberkodeerimine võimalik, sest olekuid on ainult kolm (vt. ka olekudiagrammi). Vaja läheb igal juhul kahte bitti (q1, q2). Esialgu valin koodid järgmised: S1 "00", S2 "01" ja S3 "10" (naaberkoodi pole S2 ja S3 vahel). Edaspidiseks uurimiseks jätan kodeeringud [S1 "11", S2 "01", S3 "10"] ja [S1 "00", S2 "01", S3 "11"].
Kodeeritud automaadi tabel (kodeering #1):
| |
|
|
|
|
|
--0 |
| 00 |
S2 | 01 |
0110 |
-0- |
| 01 |
S3 | 00 |
1100 |
0-- |
| 10 |
S3 | 00 |
1100 |
| |
|
|
|
| 0 1 1 |
1 0 1 |
1 - - |
- 1 0 |
Automaadi tabel ja signaalide nimed (kodeering #1):
xxx |
|
|
|
|
jk jk |
yyyy |
--0 |
| 00 |
S2 | 01 |
0- 1- |
0110 |
-0- |
| 01 |
S3 | 00 |
0- -1 |
1100 |
0-- |
| 10 |
S3 | 00 |
-1 0- |
1100 |
Selle tabeli põhjal on võimalik välja kirjutada siirde- ja väljundfunktsioonid. Unustada ei tohi, et kasutamata olekukoodi ("11") korral pole funktsioonide väljundite väärtused olulised. Minimeerimisel on kasutatud espresso erinevaid võtmeid, et võimalusel realiseerida mõni funktsioonidest inverteeritult.
| funktsioonid | espresso sisend | espresso väljund | espresso -Dopo |
xxx qq | jkjk yyyy 123 12 | 1122 1234 ================== --0 00 | 0-1- 0110 --1 00 | 0-1- 0011 -0- 01 | 0--1 1100 -1- 01 | 1--1 1001 0-- 10 | -10- 1100 1-- 10 | -00- 1001 --- 11 | ---- ---- |
.i 5 .o 8 --000 0-1-0110 --100 0-1-0011 -0-01 0--11100 -1-01 1--11001 0--10 -10-1100 1--10 -00-1001 ---11 -------- .e |
.i 5 .o 8 --000 00100110 --100 00100011 1--1- 00001001 0--1- 01001100 -0--1 00011100 -1--1 10011001 .e |
.i 5 .o 8 #faas 10100011 ---00 00101010 --100 00000101 -1--1 10000101 1--1- 01000101 .e |
Funktsioonid ilma inverteerimisvõimaluseta:
[ j1 = x2 q2 ] [ k1 = x1' q1 ]
[ j2 = x3' q1' q2' + x3 q1' q2' ] [ k2 = x2' q2 + x2 q2 ]
[ y1 = x1 q1 + x1' q1 + x2' q2 + x2 q2 ] [ y2 = x3' q1' q2' +
x1' q1 + x2' q2 ]
[ y3 = x3' q1' q2' + x3' q1' q2' ] [ y4 = x3 q1' q2' + x1 q1 +
x2 q2 ]
Funktsioonid inverteerimisvõimalusega:
[ j1 = x2 q2 ] [ k1' = x1 q1 ]
[ j2 = q1' q2' ] [ k2' = 0 ]
[ y1' = q1' q2' ] [ y2' = x3 q1' q2' + x2 q2 + x1 q1 ]
[ y3 = q1' q2' ] [ y4 = x3 q1' q2' + x2 q2 + x1 q1 ]
Kuna espresso ei minimeeri mitte loogikaelemente vaid implikantide arvu silmas pidades, siis on vajalik täiendav tulemuste analüüs. Selleks sobib näiteks ka minimeerimine Karnaugh kaartide abil. Antud juhul piisab siiski signaalide nimedega tabeli ja minimeerimise tulemuste võrdlemisest:
[ j1 = x2 q2 ] - nii ka jääb.
[ k1 = x1' q1 ] või [ k1 = (x1 q1)' ]. Tabelist on aga näha, et k1 on määratud ainult olekus S3 (x1 eitusega). Seega võiks sõltuvuse olekust välja minimeerida - [ k1 = x1' ]. Sisuliselt taandub asi sellele, kas vastavat implikanti teistes funktsioonides tarvitatakse või mitte. Esialgu arvestan kõigi kolme võimalusega.
[ j2 = x3' q1' q2' + x3 q1' q2' ] või [ j2 = q1' q2' ]. Ka siin on võimalus täiendavaks lihtsustamiseks, sest j2 väärtus pole oluline olekus S2. Täiendav lihtsustamine annaks - [ j2 = q1' ]. Nagu k1 puhul, tuleb ka siin arvestada, kuidas vastavaid implikante kasutatakse teistes funktsioonides.
[ k2 = x2' q2 + x2 q2 ] või [ k2 = (0)' ] - tundub esialgu imelik, kuid analüüsides ka tabelit, on näha, et k2 väärtused on tõepoolest '1' ja '-'. Seega [ k2 = 1 ].
[ y1 = x1 q1 + x1' q1 + x2' q2 + x2 q2 ] või [ y1 = (q1' q2')' ]. On selge, et teine variant on sobilikum. Samas näitab võrdlus juba leitud funktsioonidega, et [ y1 = j2' ] (kuid mitte [y1=q1']!). See seab ka piirangu j2-le - [ j2 = q1' q2' ] (või keerulisem variant). Arvestades aga DeMorgani seadust, võiks nii y1 kui ka j2 ümber kirjutada - [ y1 = q1 + q2 ] ja [ j2 = y1' ]
[ y2 = x3' q1' q2' + x1' q1 + x2' q2 ] või [ y2 = (x3 q1' q2' + x2 q2 + x1 q1)' ] - osutus kõige keerukamaks. Lihtsamaks teha pole praktiliselt võimalik, küll saaks aga kasutada juba leitud funktsioone - [ y2 = x3' j2 + k1 + x2' q2 ] või [ y2 = (x3 j2 + j1 + k1')' ]. Teine osutub ehk sobilikumaks (not and asemel, kuid seab piirangu k1-le - [ k1 = (x1 q1)' ].
[ y3 = x3' q1' q2' + x3' q1' q2' ] või [ y3 = q1' q2' ] - see pole aga midagi muud kui j2 (ehk y1'). Seega [ y3 = j2 ].
[ y4 = x3 q1' q2' + x1 q1 + x2 q2 ] - see pole aga midagi muud kui y2'. Arvestades kasutatavat elemenbaasi, saame [ y4 = x3 j2 + j1 + k1' ] ja [ y2 = y4' ].
Lõplik skeem oleks siis järgmine:
[ j1 = x2 q2 ] - 2-and-element;
[ k1i = x1 q1 ] - 2-and-element;
[ k1 = k1i' ] - not-element;
[ y1 = q1 + q2 ] - 2-or-element;
[ j2 = y1' ] - not-element;
[ k2 = 1 ]
[ t1 = x3 j2 ] - 2-and-element;
[ y4 = t1 + j1 + k1i ] - 3-or-element;
[ y2 = y4' ] - not-element;
[ y3 = j2 ]
Kokku seega kolm 2-and-elementi, üks 2-or-element, üks 3-or-element ja kolm not-elementi.
Üks kontrolli võimalus on simuleerimine VHDL abil (simulaatorite kohta vt. 1. kodutöö näidislahendusest). Praeguses näites on toodud automaadi nii käitumuslik kui ka struktuurne mudel. Võrrelge kirjeldusi automaadi tabeli ja skeemiga eespool. Selle võrdluse põhjal peaks olema lihtne oma tabelile vastav kirjeldus teha. Skeemi tegemisel peate arvestama, milliseid tegelikke signaale vaja läheb. Tähelepanu tuleks pöörata sellele, et osa signaale on justkui dubleeritud (nt. y4 ja y4b). Põhjuseks on VHDL iseärasus, mis ei luba väljundeid lugeda ja selle pärast tulebki kasutata nn. signaalide koopiaid. Vajalikud trigerite mudelid leiab vastavatest failidest (D-triger ja JK-triger).
Automaatide kontrollimisel osutub kõige keerumakas ülesandeks
vajadus katta kõik olekud ja siirded võimalikult
väheste sammudega. Läbimistee leidmiseks võib kasutada
nii graafskeemi kui ka olekudiagrammi. Antud näites alustatakse S1-st,
kust liigutakse "vasakpoolset haru" (x3=0) pidi S2, seejärel tagasi S1
(x2=0). Uuesti S2 minnakse "parempoolse haru" (x3=1) kaudu, kust siis edasi
S3 (x2=1). S3-st tagasi ise-endale (x1=1) ja seejärel algusesse, st. S1,
tagasi (x1=0). Sisuliselt tekib eespool toodud siirete loetelu pisut
teises järjestuses:
S1 -> S2: !x3 / y2, y3
S2 -> S1: !x2 / y1, y2
S1 -> S2: x3 / y3, y4
S2 -> S3: x2 / y1, y4
S3 -> S3: x1 / y1, y4
S3 -> S1: !x1 / y1, y2
Sellise jada genereerib testpink, mis on iga automaadi jaoks pisut erinev, kuigi põhiosad langevad kokku. Muuta tuleks ainult sisendsignaale muutvat protsessi, täpsemalt seda, millisel taktil millist x-i muudetakse. Biti-vektorid x ja y on kasutuse tulemuse paremaks vaatamiseks. Simuleerimise kestuseks peaks piisama 1-st mikrosekundist (run 1 us).
Käitumuslikku kirjeldust simuleerides on tulemusel näha, kuidas muutuvad olekud ja signaalid. Juhiks tähelepanu veel sellele, et kuna testpingis muudetakse sisend-signaale taktsignaali langeval frondil, kuid automaadi mälu-elemendid töötavad tõusva frondiga, ja et tegu on Mealy automaadiga, siis võivad väljundid takti jooksul muutuda. Moore automaadi korral sellist pilti ei tohi tekkida.
Struktuurse kirjelduse simuleerimise tulemusel on näha ainult üksikud signaalid, sest olekud on "peidetud" signaalide q1 ja q2 sisse. Mõlema tulemuse võrdlemisel on oluline saavutada seda, et kui x-de muutumine langeb kokku, siis peab seda tegema ka y-te muutumine. See aga tähendabki seda, et struktuurses kirjelduses esitatud skeem käitub just selliselt, kuidas on kirjeldatud käitumuslikus mudelis.
Skeem ja ülejäänud kodeerimisvariandid lisanduvad hiljem...
