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

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:

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

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í stav	kód
A	000
B	001
C	011
D	111
E	010

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é

2.5 Schéma obvodů

• Automat
• Ohodnocení 1
• Ohodnocení 2

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

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

kde:

• t_klo = 30ns ... zpoždění JK KO
• t_su = 20ns ... doba předstihu JK KO
• t_ko-klo = 3.20ns = 60ns ... zpoždění nejdelší větve kombinační části pro KO
• t_ko-vys = 5.20ns = 100ns ... zpoždění nejdelší větve kombinační části pro výstup
• t_vst = 50ns ... doba ustálení vstupních signálů
• t_vys = 50ns ... doba stability výstupního signálu

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

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