´ Uvod Jak na to Pˇr´ıklad
Hardwarov´a realizace koneˇcn´ych automat˚ u BI-AAG - Automaty a gramatiky Martin Plicka Katedra teoretick´ e informatiky ˇ CVUT FIT
11.10.2010
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Co potˇrebujeme
Potˇrebujeme: zak´odovat vstupn´ı abecedu, zak´odovat stavy automatu, pamatovat si souˇcasn´y stav, realizovat pˇrechodovou funkci automatu pomoc´ı zak´odovan´ych stav˚ u a vstupn´ıch symbol˚ u, rozpoznat koncov´e stavy.
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
K´odov´an´ı vstupn´ı abecedy Vstupn´ı abecedu zak´odujeme v bin´arn´ım k´odu Pro text m˚ uˇzeme pouˇz´ıt 8 bit˚ u (rozˇs´ıˇren´a ASCII). Pro menˇs´ı abecedu m˚ uˇzeme pouˇz´ıt menˇs´ı poˇcet bit˚ u. Uˇsetˇr´ıme souˇc´astky, ale mus´ıme prov´adˇet konverzi.
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
K´odov´an´ı vstupn´ı abecedy Vstupn´ı abecedu zak´odujeme v bin´arn´ım k´odu Pro text m˚ uˇzeme pouˇz´ıt 8 bit˚ u (rozˇs´ıˇren´a ASCII). Pro menˇs´ı abecedu m˚ uˇzeme pouˇz´ıt menˇs´ı poˇcet bit˚ u. Uˇsetˇr´ıme souˇc´astky, ale mus´ıme prov´adˇet konverzi. Pˇr´ıklad - A = {a, b, c, d} Symbol a b c d
K´od 00 01 10 11
Pro reprezentaci v bin´arn´ım k´odu n´am staˇc´ı ⌈log2 (|A|)⌉ bit˚ u. Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
Reprezentace stav˚ u Stavy nejˇcastˇeji k´odujeme bin´arn´ım nebo Grayov´ym k´odem. Aktu´aln´ı stav je uloˇzen v datov´em registru. Pˇrechodov´a funkce kaˇzd´e kombinaci k´ odu star´eho stavu a vstupn´ıho symbolu pˇriˇrazuje k´ od nov´eho stavu. Inicializace - vynulov´an´ım datov´eho registru (pokud pro poˇc´ateˇcn´ı stav zvol´ıme k´ od 0).
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
Reprezentace stav˚ u Stavy nejˇcastˇeji k´odujeme bin´arn´ım nebo Grayov´ym k´odem. Aktu´aln´ı stav je uloˇzen v datov´em registru. Pˇrechodov´a funkce kaˇzd´e kombinaci k´ odu star´eho stavu a vstupn´ıho symbolu pˇriˇrazuje k´ od nov´eho stavu. Inicializace - vynulov´an´ım datov´eho registru (pokud pro poˇc´ateˇcn´ı stav zvol´ıme k´ od 0).
Alternativnˇe lze pouˇz´ıt k´od 1 z N. Kaˇzd´y stav je pˇredstavov´an jedn´ım 1bitov´ym klopn´ym obvodem. Pokud je nastaven na log1, stav je aktivn´ı. Kaˇzd´y pˇrechod je realizov´an funkc´ı zdrojov´eho stavu a k´ odu vstupn´ıho symbolu. Inicializace - nastaven´ım registru poˇc´ateˇcn´ıho stavu na log1, ostatn´ıch na log0.
V obou pˇr´ıpadech se jedn´a o synchronn´ı sekvenˇcn´ı obvody. Pˇrechod do nov´eho stavu je ˇr´ızen hodinov´ym sign´alem. Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
K´odov´an´ı stav˚ u v bin´arn´ım nebo Grayovˇe k´odu Aktu´aln´ı stav je uloˇzen v datov´em registru Pˇri kaˇzd´em taktu se do registru uloˇz´ı nov´y k´od stavu, kter´y je funkc´ı stavu pˇredchoz´ıho a k´odu vstupn´ıho symbolu. hodiny vstup
CLK m
implementace přechodové funkce
n
n D registr
Indikace konc. stavu
n
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
Implementace pˇrechodov´e funkce Kombinaˇcn´ı logikou. Jednotliv´e k´ ody n´asleduj´ıc´ıho stavu jsou urˇceny kombinaˇcn´ı funkc´ı bit˚ u k´ odu p˚ uvodn´ıho stavu a vstupn´ıho symbolu. Koncov´y stav je indikov´an kombinaˇcn´ı funkc´ı bit˚ u k´ odu aktu´aln´ıho stavu.
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
K´ odov´ an´ı Implementace
Implementace pˇrechodov´e funkce Kombinaˇcn´ı logikou. Jednotliv´e k´ ody n´asleduj´ıc´ıho stavu jsou urˇceny kombinaˇcn´ı funkc´ı bit˚ u k´ odu p˚ uvodn´ıho stavu a vstupn´ıho symbolu. Koncov´y stav je indikov´an kombinaˇcn´ı funkc´ı bit˚ u k´ odu aktu´aln´ıho stavu.
Programovatelnou pamˇet´ı. K´od n´asleduj´ıc´ıho stavu je uloˇzen na pamˇet’ov´em m´ıstˇe, jehoˇz adresa je sloˇzena z k´ odu p˚ uvodn´ıho stavu a k´ odu vstupn´ıho symbolu. Indikace koncov´eho stavu m˚ uˇze b´yt souˇc´ast´ı pˇrechodov´e funkce. Hodnota t´eto funkce je pak invariantn´ı ke vstupu (pro vˇsechny vstupy je v dan´em stavu stejn´a).
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad Sestroj´ıme koneˇcn´y automat nad abecedou A = {a, b, c, d}, kter´y bude pˇrij´ımat vˇsechna slova, kter´a konˇc´ı na ”aa” nebo ”c”.
Automat mus´ı b´yt deterministick´y a s plnˇe definovanou pˇrechodovou funkc´ı.
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad Sestroj´ıme koneˇcn´y automat nad abecedou A = {a, b, c, d}, kter´y bude pˇrij´ımat vˇsechna slova, kter´a konˇc´ı na ”aa” nebo ”c”.
a,b,c,d a START
0
a
1
2
c
3
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad Sestroj´ıme koneˇcn´y automat nad abecedou A = {a, b, c, d}, kter´y bude pˇrij´ımat vˇsechna slova, kter´a konˇc´ı na ”aa” nebo ”c”.
b,d
a
b,d b,d
START
a
0
c
c
a
b,d
3
Martin Plicka
a
1
2
c c
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad Sestroj´ıme koneˇcn´y automat nad abecedou A = {a, b, c, d}, kter´y bude pˇrij´ımat vˇsechna slova, kter´a konˇc´ı na ”aa” nebo ”c”.
Q/X →0 1 ←2 ←3
a 1 2 2 1
b 0 0 0 0
c 3 3 3 3
d 0 0 0 0
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad Sestroj´ıme koneˇcn´y automat nad abecedou A = {a, b, c, d}, kter´y bude pˇrij´ımat vˇsechna slova, kter´a konˇc´ı na ”aa” nebo ”c”.
Q/X →0 1 ←2 ←3
a 1 2 2 1
b 0 0 0 0
c 3 3 3 3
d 0 0 0 0
Q/X q1 q0 → 00 01 ← 11 ← 10
00 q1′ q0′ 01 11 11 01
01 q1′ q0′ 00 00 00 00
10 q1′ q0′ 10 10 10 10
11 q1′ q0′ 00 00 00 00
Pro k´odov´an´ı stav˚ u je v tomto pˇr´ıpadˇe v´yhodnˇejˇs´ı pouˇz´ıt Grayova k´odu. Vstupn´ı abecedu k´odujeme bin´arnˇe. V naˇsem pˇr´ıpadˇe uˇsetˇr´ıme nˇekolik bit˚ u, ale byla by potˇreba konverze na vstupu. Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad - implementace pˇrechodov´e funkce
x0
q0
x1
x1
x0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
q1
q0 q1
q0′ = x0 x1
q1′ = x0 x1 + x0 q0
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇr´ıklad - implementace pˇrechodov´e funkce q1 q0 x1 x0
q1’ q0’
q0′
= x0 x1 Martin Plicka
q1′
= x0 x1 + x0 q0
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Koncov´e stavy Koncov´e stavy indikujeme v´ystupn´ı funkc´ı z´avislou pouze na aktu´aln´ım stavu (automat typu Moore). Q 0 1 2 3
Y 0 0 1 1
Q 00 01 11 10
Martin Plicka
Y 0 0 1 1
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Koncov´e stavy Koncov´e stavy indikujeme v´ystupn´ı funkc´ı z´avislou pouze na aktu´aln´ım stavu (automat typu Moore). Q 0 1 2 3
Y 0 0 1 1
Q 00 01 11 10
Y 0 0 1 1
Y = q1 q1 q0
Y
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Pˇrechodov´a funkce pomoc´ı programovateln´e pamˇeti qn
q0 x m
...
...
Adresa
Data
... q’n
q’0
x0
Adresa q1 q0 x1 x0 00 00 00 01 00 10 00 11 01 00 01 01 01 10 01 11
Obsah q1′ q0′ Y 01 0 00 0 10 0 00 0 11 0 00 0 10 0 00 0
Adresa q1 q0 x1 x0 10 00 10 01 10 10 10 11 11 00 11 01 11 10 11 11
Y
Indikaci koncov´eho stavu Y zaˇclen´ıme do pˇrechodov´e funkce (hodnota je invariantn´ı ke vstupu). Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
Obsah q1′ q0′ Y 01 1 00 1 10 1 00 1 01 1 00 1 10 1 00 1
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Fragment implementace pomoc´ı k´odu 1 z N Mˇejme automat, jehoˇz fragment vypad´a nasledovnˇe . . .
0
1
b
c
2
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Fragment implementace pomoc´ı k´odu 1 z N Kaˇzd´y stav je pˇredstavov´an jedn´ım 1bitov´ym registrem. Kaˇzd´y pˇrechod je realizov´an vlastn´ı logickou funkc´ı (vstupy b=01, c=10). 0
1
0
1 CLK
CLK
X1 X0
b
c
c
b Hodiny
2
2 CLK
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
´ Uvod Jak na to Pˇr´ıklad
Pˇrechodov´ a funkce kombinaˇ cn´ı logikou Pˇrechodov´ a funkce programovatelnou pamˇ et´ı Reprezentace k´ odem 1 z N
Fragment implementace pomoc´ı k´odu 1 z N
0
Oproti pˇredchoz´ımu ˇreˇs´ıme kaˇzd´y pˇrechod zvl´aˇst’.
1 CLK
CLK
Zˇrejmˇe n´as to bude st´at v´ıc souˇc´astek.
X1 X0
Lze jednoduˇse simulovat nedeterminismus – aktivuje se v´ıce stav˚ u najednou.
c
b Hodiny
Automat pˇrij´ım´a, pokud je nˇekter´y koncov´y stav aktivn´ı – Velk´e OR hradlo na vˇcech koncov´ych stavech.
2 CLK
Martin Plicka
Hardwarov´ a realizace koneˇ cn´ ych automat˚ u
