Juhtautomaadi süntees - näidislahendus #2

Tegemist on uue näitega, mis proovib katta ka need küsimused, mis esimesest välja jäid - kaks tingimuslikku plokki järjest ja realisatsioon Moore automaadina (vt. allpool). Mealy automaat. Kasutatav elementbaas - 2-AND, 3-AND, 2-OR, 3-OR, 2-XOR, NOT, JK-triger. Algoritmi realiseerimiseks Mealy automaadina 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 -> S1: !x1 / y1, y3 S1 -> S2: x1 & x2 / y2, y3 S1 -> S3: x1 & !x2 / y1, y4 S2 -> S2: !x3 / y2, y4 S2 -> S1: x3 / y1, y3 S3 -> S1: 1 / y1, y3 Siirete loetelu alusel on väga mugav välja kirjutada automaadi tabel.

Automaadi tabel (kodeerimata) ja olekudiagramm

sisendid	jooksev olek	järgmine olek	väljundid
it	st	st+1	ot
!x1 x1 & x2 x1 & !x2	S1	S1 S2 S3	y1, y3 y2, y3 y1, y4
!x3 x3	S2	S2 S1	y2, y4 y1, y3
1	S3	S1	y1, y3

Olekute kodeerimine

Kuna kasutusedl on JK-trigerid, siis oleks hea kasutada naaberkodeeringut (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 on naaberkodeerimine võimalik, sest olekuid on ainult kolm ja siirded toimuvad olekust S1 ja tagasi (vt. ka olekudiagrammi). Vaja läheb kahte bitti (q1, q2). Valin koodid järgmiselt: S1 "00", S2 "01" ja S3 "10" (kood "11" jääb kasutamata). Muuseas, kui valida koodid nii, et S2 "10" ja S3 "01", ei muutuks sisuliselt mitte midagi, ainult q1 ja q2 oleksid vahetuses.

Kodeeritud automaadi tabel:

it	st	K(st)	st+1	K(st+1)	ot
0-- 11- 10-	S1	00	S1 S2 S3	00 01 10	1010 0110 1001
--0 --1	S2	01	S2 S1	01 00	0101 1010
---	S3	10	S1	00	1010

Siirde- ja väljundfunktsioonide süntees ja minimeerimine

Qt	Qt+1	Jt	Kt
0 0 1 1	0 1 0 1	0 1 - -	- - 1 0

JK-trigerite puhul peab sisendi väärtuse leidmisel arvestama nii jooksva kui ka järgmise olekuga. Nii peab siirdel "0" -> "1" olema J-sisend "1" ja K-sisendi väärtus pole oluline (vt. ka tabelit paremal). Alljärgnevas tabelis on sisse toodud nii trigerite ergutus-sisendid (j1, k1, j2, k2) kui ka sisend- ja väljundsignaalide nimed.

Automaadi tabel ja signaalide nimed:

xxx 123	st	qq 12	st+1	qq 12	jk jk 11 22	yyyy 1234
0-- 11- 10-	S1	00	S1 S2 S3	00 01 10	0- 0- 0- 1- 1- 0-	1010 0110 1001
--0 --1	S2	01	S2 S1	01 00	0- -0 0- -1	0101 1010
---	S3	10	S1	00	-1 0-	1010

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 - "-Dopoall" ja valitud kolm väiksemate kuupide/implikantide arvuga tulemust.

funktsioonid	espresso sisend	tulemus #1	#2	#3	#4
xxx qq | jkjk yyyy 123 12 | 1122 1234 ================== 0-- 00 | 0-0- 1010 11- 00 | 0-1- 0110 10- 00 | 1-0- 1001 --0 01 | 0--0 0101 --1 01 | 0--1 1010 --- 10 | -10- 1010 --- 11 | ---- ----	.i 5 .o 8 0--00 0-0-1010 11-00 0-1-0110 10-00 1-0-1001 --001 0--00101 --101 0--11010 ---10 -10-1010 ---11 -------- .e	.i 5 .o 8 11-00 00100110 10-00 10001001 --0-1 00000101 0---0 00001010 --1-1 00011010 ---1- 01001010 .e	.i 5 .o 8 #faas 10110101 --1-- 00010000 11-00 00101100 10-00 10000011 --0-1 00001111 .e	.i 5 .o 8 #faas 11100101 11-00 00101100 10-00 10000011 ----- 01000000 --0-1 00011111 .e	.i 5 .o 8 #faas 10100101 11-00 00101100 10-00 10000011 --0-1 00011111 .e

Tulemus #1:
[ j1 = x1 x2'q1'q2' ]     [ k1 = q1 ]     [ j2 = x1 x2 q1'q2' ]     [ k2 = x3 q2 ]
[ y1 = q1 + x1 x2'q1'q2' + x3 q2 + x1'q2' ]     [ y2 = x1 x2 q1'q2' + x3'q2 ]
[ y3 = q1 + x1 x2 q1'q2' + x3 q2 + x1'q2' ]     [ y4 = x1 x2'q1'q2' + x3'q2 ]

Tulemus #2:
[ j1 = x1 x2'q1'q2' ]     [ k1'= 0 ]     [ j2 = x1 x2 q1'q2' ]     [ k2 = x3 ]
[ y1'= x1 x2 q1'q2' + x3'q2 ]     [ y2 = x1 x2 q1'q2' + x3'q2 ]
[ y3'= x1 x2'q1'q2' + x3'q2 ]     [ y4 = x1 x2'q1'q2' + x3'q2 ]

Tulemus #3:
[ j1 = x1 x2'q1'q2' ]     [ k1 = 1 ]     [ j2 = x1 x2 q1'q2' ]     [ k2'= x3'q2 ]
[ y1'= x1 x2 q1'q2' + x3'q2 ]     [ y2 = x1 x2 q1'q2' + x3'q2 ]
[ y3'= x1 x2'q1'q2' + x3'q2 ]     [ y4 = x1 x2'q1'q2' + x3'q2 ]

Tulemus #4:
[ j1 = x1 x2'q1'q2' ]     [ k1'= 0 ]     [ j2 = x1 x2 q1'q2' ]     [ k2'= x3'q2 ]
[ y1'= x1 x2 q1'q2' + x3'q2 ]     [ y2 = x1 x2 q1'q2' + x3'q2 ]
[ y3'= x1 x2'q1'q2' + x3'q2 ]     [ y4 = x1 x2'q1'q2' + x3'q2 ]

Esimene variant on selgelt kehvem, kui on ülejäänud. Sealjuures on #3 ja #4 sisuliselt samad (k1'=0 & k1=1) ning on #2-st ainult natuke kehvemad, sest k2 vajab täiendavat invertorit.

Variant #5 - Karnaugh kaardi abil (sisuliselt praktikumis tehtu):
Automaadi tabelit analüüsides on näha, et k1=1 (ainult '-' ka '1'). Samuti sõltub k2 x3-st ainult olekus S2, muidu võib olla suvalise väärtusega. Seega k2=x3 (vrdl. #2). Ka on näha, et y2 on '1', kui y1 on '0', ja vastupidi. Sama kehtib ka y3 ja y4 suhtes. Seega võib kirja panna, et y2=y1' ja y4=y3'. Ülejäänud neli funktsiooni - j1, j2, y1 ja y3 - tuleb siiski minimeerida.

[ j1 = x1 x2'q2' ]     [ j2 = x1 x2 q1' ]     [ y1 = q1 + x3 q2 + x1'q2' + x2'q2' ]     [ y3 = q1 + x3 q2 + x1'q2' + x2 q2' ] - y1 ja y3 pole just parimad.
Kui minimeerida y1 ja y3 0-de järgi (punased kontuurid), st. sisuliselt y2 ja y4, on tulemuseks variantides #2-#4 saadud funktsioonid -
[ y1'= x3'q2 + x1 x2 q1'q2' ]     [ y3'= x3'q2 + x1 x2'q1'q2' ] .

Siirde- ja väljundfunktsioonide realiseerimine

Variante omavahel võorreldes on osade funktsioonidega asi selge:   [ k1 = 1 ]   ,   [ k2 = x3 ]   ,   [ y1 = y2' ]   ja   [ y3 = y4' ]   (y1 ja y3 vajaksid rohkem implikante). Ülejäänutel on kattuvusi, mis aitavad leevendada piirangut, et AND/OR elementidel on kuni kolm sisendit.

[ j1 = x1 x2'q2' ]   või   [ j1 = x1 x2'q1'q2' ]   ja   [ y4 = x1 x2'q1'q2' + x3'q2 ]   -->   [ j1 = x1 x2'q2' ]   [ y4 = j1 q1' + x3'q2 ] ;
[ j2 = x1 x2 q1' ]   või   [ j2 = x1 x2 q1'q2' ]   ja   [ y2 = x1 x2 q1'q2' + x3'q2 ]   -->   [ j2 = x1 x2 q1' ]   [ y2 = j2 q2' + x3'q2 ] .

Lõoplik skeem oleks siis järgmine:
[ j1 = x1 x2'q2' ] - 3-AND, NOT;
[ k1 = 1 ] ;
[ j2 = x1 x2 q1' ] - 3-AND;
[ k2 = x3 ] ;
[ t1 = x3'q2 ] - 2-AND, NOT;
[ y2 = j2 q2' + t1 ] - 2-AND, 2-OR;
[ y4 = j1 q1' + t1 ] - 2-AND, 2-OR;
[ y1 = y2' ] - NOT;
[ y3 = y4' ] - NOT.

Kokku seega kaks 3-AND, kolm 2-AND, kaks 2-OR ja neli NOT-elementi. Põhimõtteliselt võiks ju proovida ka DeMorgani seaduse abil invertorite arvu vähendamist, kuid selline peenhäälestus pole selles töös enam oluline.

Simuleerimine (e. valideerimine)

Ü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. y2 ja y2b). 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 kõigepealt tagasi S1-le (x1=0). Seejärel S2-le (x1=1 & x2=1), siis tsüklis tagasi S2-le (x3=0) ja uuesti tagasi S1 (x3=1). Olekusse S3 saab S1-st (x1=1 & S2=0), kust tullakse tagasi algusesse, st S1 (alati tõene).

Sisuliselt tekib eespool toodud siirete loetelu, mis võib olla osaliselt teises järjestuses ja kus mõned siirded võivad korduda:
S1 -> S1: !x1 / y1, y3
S1 -> S2: x1 & x2 / y2, y3
S2 -> S2: !x3 / y2, y4
S2 -> S1: x3 / y1, y3
S1 -> S3: x1 & !x2 / y1, y4
S3 -> S1: 1 / y1, y3

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. Ka tuleks vastavalt vajadusele samme lisada või eemaldada. Biti-vektorid x ja y on kasutuse tulemuse paremaks vaatamiseks. Simuleerimise kestuseks peaks piisama 1-st mikrosekundist (10 sammu): "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.

Sarnaselt 1. kodutööga on ka siin võimalik simuleerida korraga mõlemat automaadi mudelit. Vajalik on muudetud testpink, et tulemusel oleks näha m&otulde;lema automaadi välajundid (y1-y4 ja y1s-y4s) ning nende võrdlus (y1x-y4x).

Moore automaat. Kasutatav elementbaas - 2-NOR, 3-NOR, 4-NOR, NOT, D-triger. Algoritmi realiseerimiseks Moore automaadina on vaja neli olekut - S1, S2, S3, S4 (iga väljundplokk on olek). Siirete kontroll näitab, et tsüklid sisaldavad (vähemalt ühte) olekut. Samuti pole konflikte tingimuslike plokkide läbimisel. Olekud ja väljundid:   S1 (y1, y3);   S2 (y2, y3);   S3 (y2, y4);   S4 (y1, y4). Siirded (kokku 8): S1 -> S1: !x1 S1 -> S2: x1 & x2 S1 -> S4: x1 & !x2 S2 -> S3: !x3 S2 -> S1: x3 S3 -> S3: !x3 S3 -> S1: x3 S4 -> S1: 1 Siirete loetelu alusel on väga mugav välja kirjutada automaadi tabel.

Automaadi tabel (kodeerimata) ja olekudiagramm

sisendid	jooksev olek	järgmine olek	väljundid
it	st	st+1	ot
!x1 x1 & x2 x1 & !x2	S1	S1 S2 S4	y1, y3
!x3 x3	S2	S3 S1	y2, y3
!x3 x3	S3	S3 S1	y2, y4
1	S4	S1	y1, y4

Olekute kodeerimine

Kuna kasutusedl on D-trigerid, siis on oluline, mitu siiret mingisse olekusse toimub - mida rohkem siirdeid, seda rohkem nulle võiks oleku kood sisaldada, sest siis on vastavas siirdefunktsioonis vähem implikante ja funktsioon võiks lihtsam tulla. Siirdeid on on olekutesse järgmiselt: S1 - 4; S2 - 1; S3 - 2; S4 - 1. Selle alusel saaks S1 koodiks "00" (kahest bitist piisab) ja S3 "01". Oleku S2 koodi puhul saab arvestada sellega, et siirded on samad, mis olekus S3 (väaljundid erinevad). Kui anda S2-le naaberkood S3-ga, on alust eeldada, et siiretele vastavad implikandid võivad kleepuda. Seega oleksid olekute koodid järgmised: S1 "00", S2 "11", S3 "01" ja S4 "10".

Kodeeritud automaadi tabel:

it	st	K(st)	st+1	K(st+1)	ot
0-- 11- 10-	S1	00	S1 S2 S4	00 11 10	1010
--0 --1	S2	11	S3 S1	01 00	0110
--0 --1	S3	01	S3 S1	01 00	0101
---	S4	10	S1	00	1001

Siirde- ja väljundfunktsioonide süntees ja minimeerimine

Automaadi tabel ja signaalide nimed:

xxx 123	st	qq 12	st+1	qq 12	dd 12	yyyy 1234
0-- 11- 10-	S1	00	S1 S2 S4	00 11 10	00 11 10	1010
--0 --1	S2	11	S3 S1	01 00	01 00	0110
--0 --1	S3	01	S3 S1	01 00	01 00	0101
---	S4	10	S1	00	00	1001

Selle tabeli põhjal on võimalik välja kirjutada siirde- ja väljundfunktsioonid. Kuna Moore automaadil ei sõltu väljundid sisenditest, on siirde- ja väljund-funktsioonid minimeeritud eraldi. Minimeerimisel on kasutatud espresso erinevaid võtmeid, et võimalusel realiseerida mõni funktsioonidest inverteeritult, sest NOR-elementide kasutamisel on mõnel juhul parem lähtuda minimeerimisest 0-de järgi (vrdl. KNK).

väljundid	espr. sis.	#1: faas 0101	#2: faas 1010	siirded	espr. sis.	#1: faas 11	#2: faas 10
qq | yyyy 12 | 1234 ========= 00 | 1010 11 | 0110 01 | 0101 10 | 1001	.i 2 .o 4 00 1010 11 0110 01 0101 10 1001 .e	.i 2 .o 4 #faas 0101 10 0011 -1 1100 01 0011 .e	.i 2 .o 4 #faas 1010 11 0011 -0 1100 00 0011 .e	xxx qq | dd 123 12 | 12 =========== 0-- 00 | 00 11- 00 | 11 10- 00 | 10 --0 11 | 01 --1 11 | 00 --0 01 | 01 --1 01 | 00 --- 10 | 00	.i 5 .o 2 0--00 00 11-00 11 10-00 10 --011 01 --111 00 --001 01 --101 00 ---10 00 .e	.i 5 .o 2 #faas 11 11-00 01 1--00 10 --0-1 01 .e	.i 5 .o 2 #faas 10 -0--0 01 1--00 10 --1-1 01 ---10 01 0---0 01 .e

Väljundid #1: [ y1 = q2' ]     [ y2 = q2 ]     [ y3 = y4' ]     [ y4 = q1 q2'+ q1'q2 ]
või y3 ja y4 0-de järgi kui   [ y3'= q1 q2'+ q1'q2 ]     [ y4 = y3' ]

Väljundid #2: [ y1 = q2' ]     [ y2 = q2 ]     [ y3 = q1 q2 + q1'q2' ]     [ y4 = y3' ]
või y3 ja y4 0-de järgi kui   [ y3 = y4' ]     [ y4'= q1 q2 + q1'q2' ]

Siirded #1: [ d1 = x1 q1'q2' ]     [ d2 = x1 x2 q1'q2'+ x3'q2 ]

Siirded #2: [ d1 = x1 q1'q2' ]     [ d2'= x2'q2'+ x3 q2 + q1 q2' + x1'q2' ]

Siirde- ja väljundfunktsioonide realiseerimine

Skeemi loomiseks tuleks võrrelda erinevaid variante korduvkasutatavuse seisukohalt - nt. "Siirded #2"-s sisaldab d2 sama implikanti, mis on ka "Väljundid #1" y3/y4-s. Selle tõttu on väljundite realiseerimise aluseks #1, kuid siirete puhul on võrreldud mõlema variandi realiseeritavust (pluss täiendav teisendus).

Skeem #1 - aluseks "Väljundid #1" ja "Siirded #1":
[ y1 = q2' ] ;
[ y2 = q2 ] ;
[ y3 = ((q1'+q2)' + (q1+q2')')' ] - 3x2-NOR;
[ y4 = y3' ] - NOT;
[ d1 = (x1'+q1+q2)' ] - NOT, 3-NOR;
[ d2 = ( ( (x1'+x2'+q1+q2)' + (x3+q2')' )' )' ] - 2xNOT, 4-NOR, 2x2-NOR.
Kokku 4xNOT, 5x2-NOR, 3-NOR, 4-NOR - 11 elementi / 21 sisendit.

Skeem #2 - aluseks "Väljundid #1" ja "Siirded #2":
[ y1 = q2' ] ;
[ y2 = q2 ] ;
[ y3 = ((q1'+q2)' + (q1+q2')')' ] - 3x2-NOR;
[ y4 = y3' ] - NOT;
[ d1 = (x1'+q1+q2)' ] - NOT, 3-NOR;
[ d2 = ( (x2+q2)' + (x3'+q2')' + (q1'+q2)' + (x1+q2)' )' ] - NOT, 4-NOR, 3x2-NOR (pluss üks y3-st).
Kokku 3xNOT, 6x2-NOR, 3-NOR, 4-NOR - 11 elementi / 22 sisendit.

Skeem #3 - aluseks "Väljundid #1" ja "Siirded #2" (q2 sulguse ette toodud):
[ y1 = q2' ] ;
[ y2 = q2 ] ;
[ y3 = ((q1'+q2)' + (q1+q2')')' ] - 3x2-NOR;
[ y4 = y3' ] - NOT;
[ d1 = (x1'+q1+q2)' ] - NOT, 3-NOR;
[ d2 = ( (x3'+q2')' + (q2 + (x2'+ q1 + x1')' )' )' ] - 2xNOT, 3-NOR, 3x2-NOR.
Kokku 4xNOT, 6x2-NOR, 2x3-NOR - 12 elementi / 22 sisendit.

Elementide ja sisendite koguarvu arvestades osutub parimaks "Skeem #1" (mis ei olegi 0-de järgi minimeeritud, juhtub vahel :-)
Valideeritud on siiski kõiki kolme skeemi, et veenduda nende korrektsuses.

Simuleerimine (e. valideerimine)

Valideerimine on põhimõtteliselt sarnane Mealy automaadi puhul tehtuga. Selleks on vaja nii nii käitumuslikku kui ka struktuurset mudelit (aluseks "Skeem #1").

Testpingi jaoks on kõigepealt vaja määrata, mis järjekorras siirded läbitakse:
S1 -> S1: !x1
S1 -> S2: x1 & x2
S2 -> S3: !x3
S3 -> S3: !x3
S3 -> S1: x3
S1 -> S2: x1 & x2
S2 -> S1: x3
S1 -> S4: x1 & !x2
S4 -> S1: 1

Olekud ja väljundid läbimise järjekorras:   S1 (y1, y3);   S1 (y1, y3);   S2 (y2, y3);   S3 (y2, y4);   S3 (y2, y4);   S1 (y1, y3);   S2 (y2, y3);   S1 (y1, y3);   S4 (y1, y4).   Kokku 9 takti (sammu) ja simuleerida võiks nüüd ca 1,2 us (run 1.2 us).

Käitumuslikku kirjeldust simuleerides on tulemusel näha, kuidas muutuvad olekud ja signaalid. Erinevalt Mealy automaadist muutuvad väljundid ainult takti tõusva frondi korral. Struktuurse kirjelduse (Skeem #1) simuleerimise tulemusel on näha, et nii x-de kui ka y-te muutumised langevad kokku.

Sarnaselt Mealy automaadile on ka siin võimalik simuleerida korraga mõlemat automaadi mudelit. Testpinki on muudetud selliselt et tulemusel oleks näha mõlema automaadi välajundid (y1-y4 ja y1s-y4s) ning nende võrdlus (y1x-y4x).

Samuti on olemas VHDL-kood kahele ülejäänud skeemi-variandile "Skeem #2" ja "Skeem #3". Mõlema korrektsust on kontrollitud samade testpinkidega.