Pomocí synchronního sekvenčního obvodu realizujte konečný automat se dvěma vstupy a, b a jedním výstupem z, zadaný následující tabulkou přechodů a tabulkou výstupů. Použijte vhodnou metodu pro minimalizaci a zakódování vnitřních stavů. Správnost návrhu ověřte pomocí simulace tak, aby se v časovém diagramu prošlo všemi vnitřními stavy minimalizovaného automatu.
\ba| tabulka přechodů tabulka výstupů Qi\ | 00 01 10 00 01 10 -------------------- -------------- Q0| Q10 Q4 Q9 0 1 0 Q1| Q8 Q2 Q6 1 0 1 Q2| Q1 Q4 Q9 0 1 0 Q3| Q8 Q0 Q1 1 0 1 Q4| Q8 Q8 Q9 0 0 1 Q5| Q0 Q7 Q6 0 1 1 Q6| Q8 Q0 Q1 1 0 1 Q7| Q8 Q8 Q5 0 0 1 Q8| Q1 Q7 Q10 1 0 1 Q9| Q2 Q4 Q3 0 1 1 Q10| Q8 Q2 Q1 1 0 1 Použijte klopné obvody typu 7472.
Stanovte maximální možnou hodinovou frekvenci za předpokladů: Vstupní stavy obvodu se mění pouze v intervalu < T , T + 50ns >, kde T jsou okamžiky příchodu záporné hrany hodinových pulzů. Správný výstupní stav musí trvat po dobu nejméně 50 ns.
Písemná zpráva musí obsahovat:
Poznámka: Součástí hodnocení bude i ocenění formální úrovně zprávy.
Minimalizaci vnitřních stavů provedeme pomocí implikační tabulky:
1 | x | ||||||||||
2 | 1,10 | x | |||||||||
3 | x | 0,2 1,6 | x | ||||||||
4 | x | x | x | x | |||||||
5 | x | x | x | x | x | ||||||
6 | x | 0,2 1,5 | x | T | x | x | |||||
7 | x | x | x | x | 9,5 | x | x | ||||
8 | x | 1,8 6,10 2,7 | x | 1,8 0,7 1,10 | x | x | 1,8 0,7 1,10 | x | |||
9 | x | x | x | x | x | 0,2 4,7 3,6 | x | x | x | ||
10 | x | 1,6 | x | 0,2 | x | x | 0,2 | x | 1,8 2,7 1,10 | x | |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Z tabulky vyplývají následující třídy ekvivalence:
A = {0,2}, B = {1,3,6,10}, C = {4,7}, D = {5,9}, E = {8}
ba\Qi | 00 | 01 | 10 | 00 | 01 | 10 | |
A | B | C | D | 0 | 1 | 0 | |
B | E | A | B | 1 | 0 | 1 | |
C | E | E | D | 0 | 0 | 1 | |
D | A | C | B | 0 | 1 | 1 | |
E | B | C | B | 1 | 0 | 1 |
Zminimalizovaná tabulka přechodů a výstupů
Vnitřní stavy zakódujeme pomocí metody Dolotta-McCluskey. Automat má 5 vnitřních stavů, jsou tedy potřeba 3 proměné na jejich zakódování. Dle literatury ([1], str. 87) bude kódotvorných sloupců 15 a matice výchozích stavů bude mít následující tvar:
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Matice výchozích stavů
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Matice následujících stavů pro ba = 00
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Matice následujících stavů pro ba = 01
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Matice následujících stavů pro ba = 10
Sloupce těchto matic zapíšeme dekadicky v inverzním kódu do výběrové tabulky, ve které provedem ohodnocení jednotlivých řádků dle následujících kriterií:
Po tomto vyhodnocení vyberem sloupec s největším skóre a ve druhém a třetím kole hodnotíme podle těchto dvou pravidel:
V obou kolech vybereme sloupec s nejvyšším skóre, který splňuje podmínky ([1] str. 92) pro platný kód. Celý postup hodnocení je uveden v následující tabulce, vybrané sloupce jsou tučně zvýrazněny.
Q | 00 | 01 | 10 | a+b | c | d+e | s1 | f | g | s2 | f | g | s3 |
1 | 12 | 4 | 0 | 8 | - | - | 8 | - | 16 | 24 | x | x | x |
2 | 0 | 0 | -11 | 16 | 16 | - | 32 | x | x | x | x | x | x |
3 | 12 | 4 | -11 | - | - | - | 0 | - | 16 | 16 | x | x | x |
4 | 0 | -12 | 0 | 16 | - | - | 16 | - | 32 | 48 | x | x | x |
5 | 12 | -8 | 0 | 8 | - | - | 8 | - | 16 | 24 | x | x | x |
6 | 0 | -12 | -11 | 8 | - | - | 8 | - | 32 | 40 | x | x | x |
7 | 12 | -8 | -11 | - | - | - | 0 | - | 16 | 16 | x | x | x |
8 | -14 | 0 | 11 | 8 | - | - | 8 | - | 16 | 24 | x | x | x |
9 | -2 | 4 | 11 | - | - | - | 0 | 4 | - | 4 | - | - | 4 |
10 | -14 | 0 | -0 | 16 | - | - | 16 | - | 16 | 32 | x | x | x |
11 | -2 | 4 | -0 | 8 | - | - | 8 | 4 | - | 12 | - | - | 12 |
12 | -14 | -12 | 11 | - | - | 8 | 8 | - | - | 8 | - | - | 8 |
13 | -2 | -8 | 11 | - | - | - | 0 | 4 | - | 4 | - | 16 | 20 |
14 | -14 | -12 | -0 | 8 | - | 8 | 16 | - | - | 16 | - | - | 16 |
15 | -2 | -8 | -0 | 8 | - | - | 8 | 4 | - | 12 | - | 16 | 28 |
Tabulka přechodů pro metodu Dolotta-McCluskey
Poznámka: V některé literatuře (např. [1]) je pro 3. kolo ještě uváděna podmínka h: výskyt hodnot shodných s hodnotami, které získáme operacemi logického součtu nebo součinu vybraných sloupců nebo s jejich komplementy - 1 bod. Tuto podmínku jsem nebral v úvahu proto, že například v [2] není uváděna a lze se tedy (i díky jejímu nízkému bodovému ohodnocení) domívat, že na konečnou složitost funkcí nemá příliš vliv. Kromě toho v tomto případě by stejně nemohla výsledek ovlivnit.
vnitřní stav | kód |
---|---|
A | 000 |
B | 001 |
C | 011 |
D | 111 |
E | 010 |
Zakódování vnitřních stavů
Q | ba=00 | ba=01 | ba=10 | výstup | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
q2 | q1 | q0 | q2 | q1 | q0 | q2 | q1 | q0 | q2 | q1 | q0 | 00 | 01 | 10 | |
A | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
B | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
C | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
D | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
E | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
Výpočet minimální periody Tmin provedem dle následujícího vzorce ([2], str. 129):
kde:
V našem případě je tedy Tmin:
Funkce automatu byla otestována pomocí ohodnocení vodičů pro dva různé stavy a porovnáním výsledků s tabulkou přechodů. Obě dvě ohodnocení proběhly v pořádku, je tedy pravděpodobné, že automat funguje korektně.
Pro kontrolu metody Dolotta-McCluskey jsem použil program KVS. Výsledné kódování vnitřních stavů určené tímto stavem se mírně lišilo od mého "ručního" zakódování, nicméně složitost funkcí byla prakticky stejná.