Semestrální práce z předmětu 36LS

Martin Tůma, 3/50, paralelka 110

1 Zadání

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.
  1. Použijte hradla typu 7400 a 7410; 7420 jen pokud používáte D-klopné obvody.
  2. Nejvyšší povolená logická zátěž IO je pět.
  3. Vnější vstupy máte k dispozici pouze v přímé formě.
  4. Zpoždění obvodů nechť je pro hradla 20ns a pro klopné obvody 30ns.

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:

  1. toto zadání,
  2. zakódování vnitřních stavů včetně zdůvodnění volby kódu,
  3. zakódovanou tabulku přechodů a výstupů,
  4. mapy pro vstupy klopných obvodů a mapy pro výstupní proměnné,
  5. výrazy pro budící proměnné klopných obvodů a vnější výstupy v MNDF,
  6. schéma obvodu ve dvou exemplářích pro dvě různá ohodnocení vodičů,
  7. výpočet maximální možné frekvence hodinových pulzů,
  8. časový diagram získaný ze simulátoru s označením vnitřních stavů.

Poznámka: Součástí hodnocení bude i ocenění formální úrovně zprávy.

2 Řešení

2.1 Minimalizace vnitřních stavů

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ů

2.2 Zakódování vnitřních stavů

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:

0000000 00000000
0000000 11111111
0001111 00001111
0110011 00110011
1010101 01010101

Matice výchozích stavů

0000000 11111111
1010101 01010101
1010101 01010101
0000000 00000000
0000000 11111111

Matice následujících stavů pro ba = 00

0001111 00001111
0000000 00000000
1010101 01010101
0001111 00001111
0001111 00001111

Matice následujících stavů pro ba = 01

0110011 00110011
0000000 11111111
0110011 00110011
0000000 11111111
0000000 11111111

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í:

  1. a) výskyt samých nul v řádce pro vstupní písmeno - 8b
  2. b) výskyt samých jedniček v řádce pro vstupní písmeno - 8b
  3. c) výskyt stejné hodnoty ve sloupcích pro sousední vstupní písmeno - 16b
  4. d) stejná hodnota s výchozím stavem - 8b
  5. e) stejná hodnota s komplementem výchozího stavu - 8b

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:

  1. f) výskyt stejné hodnoty v řádku jako vybraný sloupec, nebo jeho komplement - 4b
  2. g) výskyt stejné hodnoty v řádku jako v řádku vybraného sloupce - 16b

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í stavkód
A000
B001
C011
D111
E010

Zakódování vnitřních stavů

2.3 Zakódovaná tabulka 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

2.4 Mapy a funkce pro vnitřní a výstupní proměnné


mapa pro KO0 mapa pro KO1 f(a,b,q0,q1,q2) pro KO0 f(a,b,q0,q1,q2) pro KO1 mapa pro KO2 mapa pro Y f(a,b,q0,q1,q2) pro KO2 f(a,b,q0,q1,q2) pro Y

2.5 Schéma obvodů

2.6 Výpočet maximální možné frekvence hodinových pulzů

Výpočet minimální periody Tmin provedem dle následujícího vzorce ([2], str. 129):

Tmin = max(tklo, tvst) + max(tko-vys + tvys, tko-klo + tsu)

kde:

V našem případě je tedy Tmin:

Tmin = max(30, 50) + max(100 + 50, 60 + 20) = 200ns
fmax = 5MHz

3 Závěr

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á.

Reference

  1. [1] H. Kubátová, Z. Blažek: Logické systémy - cvičení ČVUT 1999
  2. [2] V. Jáneš, J. douša: Logické systémy - ČVUT 1994