HW: Automaty Mealy a Moore

Sekvencny obvod je taky obvod, ktoreho vystup je zavisly na vstupe a zaroven na sucasnom stave (alebo predchadzajucom vstupe). Z toho vyplyva, ze takyto obvod obsahuje pamatove cleny. Rozdiel od kombinacneho je snad nad slnko jasny. Pre popis sekvencneho obvodu sa s vyhodou vyuzivaju automaty a to bude aj tema toho prispevku. Dalej popisovane automaty su zakladnymi typmi sekvencnych aut. spolocne s autonomnym, Medvedovym a kombinacnym automatom. Automaty rozoznavame podla zavislosti vystupnych stavov na vstupnych a vnutornych symboloch.

Automaty Mealy a Moore su konecne automaty, tvorene sesticou
mnozinou vstupnych premennych X
mnozinou vystupnych premennych Y 
mnozinou vnutornych stavov Q
pociatocny stavom Q0 
prechodovou funkciou δ
vystupnou funkciou λ

Ak si uz z automatov nepamatate nic, tak sa mrknite na kapitolu konecne automaty (TBD).

Mealyho automat
Qt = δ(Xt, Qt-1)        Novy stav je zavisly na vstupnom symbole a predoslom stave 
Yt = λ(Xt, Qt-1)        Vystupny symbol je zavisly na vstupnom symbole a predoslom stave

Vystup je vygenerovany pri kazdom prechode a zavisi na vstupnom symbole a predoslom stave Yt = λ(Xt, Qt-1). Teda, aby sme boli presny, jedna sa vlastne o prechod a teda stav Qt-1 je stav z ktoreho vychadzame. 

Cervene cisla na obrazku oznacuju vstup citaca, modre cisla vystup citaca. Reakcia na vstup je v Mealyho automate viditelna okamzite.


















Tabulka prechodov a vystupov


        0     1    |    0   1
Si    S0  S1        0   0
S0   S0  S1        0   1
S1   S1  S0        1   0


Aby sme sa z automatu dostali az k navrhu obvodu a funkciam, tak si tabulku prechodov a vystupov zakodujeme. Zakodovanu tabulku potom vyuzijeme k navrhu map.

Zakodovanie
        a    b
Si     0    0
S0    0    1
S1    1    0


zakodovana tabulka bude vyzerat nasledovne:

        0     1    |    0   1

00   01  10        0   0

01   01  10        0   1

10   10  01        1   0

a z tabulky vyrobime mapu

pre A:

                ----- b

             -----    a

       1   1   X  0 

 |     0   0   X  1

x


pre B:

                ----- b

             -----    a

       0   0   X  1 

 |     1   1   X  0

x

pre X:

                ----- b

             -----    a

       0   0   X  1 

 |     0   1   X  0

x

Teraz uz staci len z map vyrobit fcie a schemu mozme navrhnut. 

Moorov automat 

Qt = δ(Xt, Qt-1)        Novy stav je zavisly na vstupnom symbole a predoslom stave 

Yt = λ(Qt-1)              Vystupny symbol na predoslom stave

Ak ste pozorni, tak Vam neuniklo, ze vystup Mooreovho automatu nezavisi na vstupnom symbole, ale len a len na jeho predchadzajucom stave. 

Cervene cisla na obrazku oznacuju vstup citaca, modre cisla vystup citaca. Reakcia na vstup je v tomto pripade viditelna az po prechode do nasledujuceho stavu. 

Tabulka prechodov tohto automatu bude trosku odlisna, ako u Mealyho a to preto, ze vystup zavisi od stavu, v ktorom sa nachadzame. 


                 0          1         |       Y
Si             S0        S1               0               #je jasne vidno, ze vystup zalezi na stave 
S0           S00      S01              0 
S1           S10      S11              0
S00         S00      S01              0
S11         S10      S11              0
S01         S10      S11              1
S10         S00      S01              1


tuto tabulku si zase zakodujeme
                 c         b       a
Si              0         0       0
S0             0         0       1
S1             0         1       0
S00           0         1       1
S11           1         0       0
S01           1         0       1
S10           1         1       0

a zakodovana tabulka prechodov bude vyzerat nasledovne:

                cba      cba       |      Y

Si            000      010              0               

S0           011      101              0 

S1           110      100              0

S00         011      101              0

S11         110      100              0

S01         101      100              1

S10         110      101              1

a z tejto tabulky vyrobime mapy obdobnym sposobom ako u Mealyho automatu.