1.    Minimalizace množiny vnitřních stavů

Minimalizaci množiny vnitřních stavů provedeme rozkladem vnitřních stavů do jednotlivých tříd k-ekvivalentních stavů.

V první tabulce jsou uvedeny vnitřní stavy, které mají shodné výstupní stavy – jsou označeny stejnou barvou.

 

 

Tabulka přechodů

Tabulka výstupů

Qi/ba

00

01

10

00

01

10

Q1

Q7

Q9

Q4

0

0

1

Q2

Q11

Q1

Q6

0

1

0

Q8

Q3

Q1

Q6

0

1

0

Q0

Q0

Q7

Q9

1

0

0

Q10

Q12

Q3

Q13

1

0

0

Q12

Q10

Q7

Q9

1

0

0

Q4

Q11

Q5

Q12

1

0

1

Q6

Q7

Q9

Q12

1

0

1

Q5

Q10

Q1

Q8

1

1

0

Q9

Q12

Q1

Q8

1

1

0

Q13

Q0

Q1

Q2

1

1

0

Q3

Q8

Q10

Q12

1

1

1

Q7

Q2

Q0

Q0

1

1

1

Q11

Q2

Q10

Q10

1

1

1

 

V další tabulce je uveden první rozklad do tříd A až F.

 

Třída 

Qi/ba

00

01

10

00

01

10

A

Q1

Q7F

Q9E

Q4D

0

0

1

B

Q2

Q11F

Q1A

Q6D

0

1

0

Q8

Q3F

Q1A

Q6D

0

1

0

C

Q0

Q0C

Q7F

Q9E

1

0

0

Q10

Q12C

Q3F

Q13E

1

0

0

Q12

Q10C

Q7F

Q9E

1

0

0

D

Q4

Q11F

Q5E

Q12C

1

0

1

Q6

Q7F

Q9E

Q12C

1

0

1

E

Q5

Q10C

Q1A

Q8B

1

1

0

Q9

Q12C

Q1A

Q8B

1

1

0

Q13

Q0C

Q1A

Q2B

1

1

0

F

Q3

Q8B

Q10C

Q12C

1

1

1

Q7

Q2B

Q0C

Q0C

1

1

1

Q11

Q2B

Q10C

Q10C

1

1

1

 


Je jasně vidět, že množina vnitřních stavů jednotlivých skupin je ekvivalentní, lze tedy přepsat tabulku do minimalizované tabulky vnitřních stavů.

 

 

Tab. přechodů

Tab. výstupů

Qi/ba

00

01

10

00

01

10

QA

QF

QE

QD

0

0

1

QB

QF

QA

QD

0

1

0

QC

QC

QF

QE

1

0

0

QD

QF

QE

QC

1

0

1

QE

QC

QA

QB

1

1

0

QF

QB

QC

QC

1

1

1

 

2.    Kódování vnitřních stavů

Kódování vnitřních stavů provedeme pomocí metody Dolotta-McCluskey.

Automat má 6 vnitřních stavů, k jejich zakódování potřebujeme 3 proměnné. Kódotvorné sloupce budou mít 6 řádků a je jich 25.

Matice výchozích stavů:

 

0

0

0

0

0

0

0

0

0

0

0

0

0

0

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

1

1

1

1

1

1

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

1

1

1

0

0

0

1

1

1

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

1

1

0

1

1

0

0

1

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

0

1

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

 

Matice následných stavů pro vstupní písmeno 00:

1

1

0

1

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

1

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

0

1

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

 

Matice následných stavů pro vstupní písmeno 01:

1

0

1

1

0

1

1

0

0

1

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

1

1

0

0

1

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

0

0

0

0

0

0

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

0

0

0

0

0

0

0

1

1

1

1

1

1

1

 

Matice následných stavů pro vstupní písmeno 10:

0

1

1

1

0

0

0

1

1

1

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

0

1

1

1

0

0

0

1

1

1

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

1

1

0

1

1

0

0

1

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

 


Tabulka ohodnocení jednotlivých kódotvorných sloupců:

 

Q(t+1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Q(t)

00

01

10

a

b

c

d

e

S1

f

g

S2

f

g

h

S3

 

1

-11

-19

8

x

x

x

x

x

0

x

x

0

x

x

x

0

 

2

-11

8

-15

x

x

x

x

x

0

x

x

0

x

x

1

1

 

3

0

-27

-7

8

x

x

x

x

8*

x

x

0

x

x

x

x

 

4

-11

-19

-7

x

x

x

x

8

8

4

16

28

N

N

N

N

 

5

-1

9

5

x

x

x

8

x

8

x

x

8*

x

x

x

x

 

6

10

-26

13

x

x

x

8

x

8

x

x

8

x

x

x

8

 

7

-1

-18

13

x

x

x

x

x

0

x

x

0

4

16

x

20

N

8

10

1

-10

x

x

x

x

x

0

x

x

0

x

x

x

0

 

9

-1

9

-10

x

x

x

x

x

0

x

x

0

8

32

x

40

N

10

10

-26

-2

x

x

x

x

x

0

x

x

0

x

x

x

0

 

11

-1

-18

-2

x

x

x

x

x

0

x

x

0

4

16

x

20

N

12

-10

8

2

x

x

x

x

x

0

x

x

0

x

x

x

0

 

13

1

-27

10

x

x

x

x

x

0

4

16

20

N

N

N

N

 

14

-10

-19

10

x

x

x

x

8

8

x

x

8

x

x

x

8

 

15

1

0

-13

8

x

x

x

x

8

4

x

12

N

N

N

N

 

16

-10

8

-13

x

x

x

x

x

0

x

x

0

x

x

x

0

 

17

1

-27

-5

x

x

x

x

x

0

4

16

20

N

N

N

N

 

18

-10

-19

-5

x

x

x

x

x

0

x

x

0

x

x

x

0

 

19

11

1

7

x

x

x

x

x

0

x

x

0

x

x

x

0

 

20

-0

9

7

x

8

x

x

x

8

x

x

8

4

16

1

29

N

21

11

-26

15

x

x

x

x

8

8

x

x

8

x

x

1

9*

 

22

-0

-18

15

x

8

x

x

x

8

x

x

8

x

x

2

10

N

23

11

1

-8

x

x

x

x

x

0

x

x

0

x

x

x

0

 

24

-0

9

-8

x

8

x

x

x

8

x

x

8

4

16

1

29

N

25

11

-26

-0

x

8

x

x

x

8

x

x

8

x

x

1

9

 

 

Pravidla pro ohodnocení jednotlivých kódotvorných sloupců:

a)        výskyt samých nul v řádce pro vstupní písmeno (8 bodů)

b)        výskyt samých jedniček v řádce pro vstupní písmeno (8)

c)        výskyt stejné hodnoty ve sloupcích pro sousední vstupní písmeno (16)

d)        stejná hodnota s výchozím stavem (8)

e)        stejná hodnota s komplementem výchozího stavu (8)

f)          výskyt stejné hodnoty v řádku jako vybraný sloupec nebo jeho komplement(4)

g)        výskyt stejné hodnoty v řádku jako v řádku vybraného sloupce (16)

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)

 

V tabulce jsou tučně označeny kódotvorné sloupce s nejvyšším skóre, tučně s hvězdičkou * jsou označeny vybrané sloupce a N značí sloupce, které netvoří platný kód s již vybranými sloupci.

Po prvním ohodnocení jsem z možných sloupců vybral sloupec 3 (000110). Po druhém ohodnocení dostaly vyšší ohodnocení než vybraný sloupec 5 (001001) sloupce 4, 13, 15, 17, ale ani jeden z nich netvořil s již vybraným sloupcem 3 platný kód. Po posledním ohodnocení získaly sloupce 7, 9, 11, 20, 22, 24, 25 vyšší ohodnocení než vybraný sloupec 21 (011010), ale netvořili s již vybranými sloupci platný kód.


Zakódujeme vnitřní stavy takto:

 

Vnitřní stav

Kód

QA

0

0

0

QB

0

0

1

QC

0

1

1

QD

1

0

0

QE

1

0

1

QF

0

1

0

 

Zakódovaný tabulka přechodů a výstupů tedy vypadá takto:

 

 

Zakódovaná tabulka přechodů

Tab. výstupů

 

Q

00

01

10

 

 

 

 

q2

q1

q0

q2

q1

q0

q2

q1

q0

q2

q1

q0

00

01

10

QA

0

0

0

0

1

0

1

0

1

1

0

0

0

0

1

QB

0

0

1

0

1

0

0

0

0

1

0

0

0

1

0

QC

0

1

1

0

1

1

0

1

0

1

0

1

1

0

0

QD

1

0

0

0

1

0

1

0

1

0

1

1

1

0

1

QE

1

0

1

0

1

1

0

0

0

0

0

1

1

1

0

QF

0

1

0

0

0

1

0

1

1

0

1

1

1

1

1

 

3.    Mapy budících funkcí klopných obvodů a výstupní funkce

Výrazy jsou přímo upraveny pro realizaci pomocí členů NAND.

 

KO 0 (vnitřní proměnná q0):

 


 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

0

1

x

0

 

 

q0

0

0

x

0

 

q1

q0

1

0

x

1

 

q1

 

1

1

x

1

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

1

0

x

1

q2

 

 

0

1

x

1

 

 

 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

0

1

x

0

 

 

q0

0

0

x

0

 

q1

q0

1

0

x

1

 

q1

 

1

1

x

1

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

1

0

x

1

q2

 

 

0

1

x

1

 



KO 1 (vnitřní proměnná q1):

 


 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

1

0

x

0

 

 

q0

1

0

x

0

 

q1

q0

1

1

x

0

 

q1

 

0

1

x

1

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

1

0

x

0

q2

 

 

1

0

x

1

 

 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

1

0

x

0

 

 

q0

1

0

x

0

 

q1

q0

1

1

x

0

 

q1

 

0

1

x

1

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

1

0

x

0

q2

 

 

1

0

x

1

 


 

KO 2 (vnitřní proměnná q2):


 

 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

0

1

x

1

 

 

q0

0

0

x

1

 

q1

q0

0

0

x

1

 

q1

 

0

0

x

0

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

0

0

x

0

q2

 

 

0

1

x

0

 

 

 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

0

1

x

1

 

 

q0

0

0

x

1

 

q1

q0

0

0

x

1

 

q1

 

0

0

x

0

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

0

0

x

0

q2

 

 

0

1

x

0

 


 

Výstupní funkce:

 

 

 

 

 

b

b

 

 

 

 

a

a

 

 

 

 

0

0

x

1

 

 

q0

0

1

x

0

 

q1

q0

1

0

x

0

 

q1

 

1

1

x

1

q2

q1

 

x

x

x

x

q2

q1

q0

x

x

x

x

q2

 

q0

1

1

x

0

q2

 

 

1

0

x

1


4.    Schéma automatu a schémata pro dvě různá ohodnocení vodičů

Viz. přílohy 1, 2 a 3

 

5.    Výpočet maximální možné frekvence hodinových pulsů

Vycházíme z těchto parametrů hranového klopného obvodu 7473:

t1 = 20 ns (minimální délka úrovně H hodinového signálu)

ZKO = 30 ns (zpoždění klopného obvodu)

ZHR = 20 ns (zpoždění hradel)

Dst.Yi = 50 ns (potřebná doba stabilního výstupního písmena Yi)

tsetup = 10 ns (předstih klopných obvodů)

Dust.Xi = 50 ns (doba potřebná pro ustálení vstupního písmena Xi)

 

Hodnoty závislé na konkrétním zapojení:

NZK1 = 60 ns (nejdelší zpoždění v cestě K1 kombinační části)

NZK2 = 40 ns (nejdelší zpoždění v cestě K2 kombinační části)

NZK3 = 60 ns (nejdelší zpoždění v cestě K3 kombinační části)

NZK4 = 80 ns (nejdelší zpoždění v cestě K4 kombinační části)

 

Kde K1 až K4 jsou:

Minimální délku úrovně L spočítáme podle [1] tímto vztahem:

Minimální délka periody hodinových impulsů tedy je:

 

A maximální frekvence hodinových pulsů:

 

6.    Použitá literatura

[1] V. Jáneš, J. Douša: Logické systémy, skriptum ČVUT 1998.

 

7.    Přílohy

vše ke stažení i tento dokument ve wordu
přílohy nakresleny v PROFICADu
příloha 1
příloha 2
příloha 3