1

I

T
P

W

ZPT

Minimalizacja liczby stanów

a

b

c

d

a

b

c

d

A

C B

C

A

0

1

1

1

B

C C

A

–

0

1

1

–

C

B C

A

B

0

0

0

1

x

S

a

b

c

d

a

b

c

d

S1

–

S3 S4 S2 –

1

1

1

S2

S4

–

–

–

0

–

–

–

S3

S6 S6

–

–

0

1

–

–

S4

–

S6 S1 S5 –

0

0

1

S5

–

–

S2

–

–

–

1

–

S6

S3

–

S2 S3 0

–

0

1

Minimalizacja stanów to transformacja automatu o danej tablicy
przejść-wyjść na równoważny mu (pod względem przetwarzania
sygnałów cyfrowych) automat o mniejszej liczbie stanów
wewnętrznych. Jest to prawie zawsze możliwe, gdyż w procesie
pierwotnej specyfikacji często wprowadzane są stany nadmiarowe lub
równoważne.

Minimalizacja stanów to transformacja automatu o danej tablicy
przejść-wyjść na równoważny mu (pod względem przetwarzania
sygnałów cyfrowych) automat o mniejszej liczbie stanów
wewnętrznych. Jest to prawie zawsze możliwe, gdyż w procesie
pierwotnej specyfikacji często wprowadzane są stany nadmiarowe lub
równoważne.

Minimalizacja liczby
stanów

Czysty zysk – zamiast trzech przerzutników tylko dwa!

Czysty zysk – zamiast trzech przerzutników tylko dwa!

2

I

T
P

W

ZPT

Minimalizacja liczby stanów

x

S

a b c d a b c d

1

– 3 4 2 – 1 1 1

2

4 –

–

– 0 –

–

–

3

6 6 –

– 0 1 – –

4

– 6 1 5 – 0 0 1

5

–

– 2 –

–

– 1 –

6

3 – 2 3 0 – 0 1

Dwa stany wewnętrzne Si, Sj są zgodne, jeżeli dla
każdego wejścia v mają one niesprzeczne stany wyjść, a
ich stany następne są takie same lub niesprzeczne.

Dwa stany wewnętrzne Si, Sj są

zgodne

, jeżeli dla

każdego wejścia v mają one niesprzeczne stany wyjść, a
ich stany następne są takie same lub niesprzeczne.

Dwa stany wewnętrzne S

i

, S

j

są zgodne warunkowo,
jeżeli ich stany wyjść są
niesprzeczne oraz dla
pewnego v  V para stanów

następnych do S

i

, S

j

(ozn. S

k

,

S

l

):

(S

i

, S

j

)  (S

k

, S

l

)

Dwa stany wewnętrzne S

i

, S

j

są

zgodne warunkowo

,

jeżeli ich stany wyjść są
niesprzeczne oraz dla
pewnego v  V para stanów

następnych do S

i

, S

j

(ozn. S

k

,

S

l

):

(S

i

, S

j

)  (S

k

, S

l

)

Stany Si, Sj są sprzeczne,
jeżeli dla pewnego v  V

ich stany wyjść są
sprzeczne.

Stany Si, Sj są

sprzeczne,

jeżeli dla pewnego v  V

ich stany wyjść są
sprzeczne.

Stany zgodne
warunkowo

Stany zgodne

Stany
sprzeczne

3

I

T
P

W

ZPT

Relacja zgodności

Ze względu na zgodność warunkową w
obliczeniach (wszystkich!) par zgodnych
posługujemy się tzw. tablicą trójkątną.

Ze względu na zgodność warunkową w
obliczeniach (wszystkich!) par zgodnych
posługujemy się tzw. tablicą trójkątną.

Tablica trójkątna zawiera tyle kratek, ile jest
wszystkich możliwych par stanów. Na przykład
dla automatu o 5 stanach:

Tablica trójkątna zawiera tyle kratek, ile jest
wszystkich możliwych par stanów. Na przykład
dla automatu o 5 stanach:

4

I

T
P

W

ZPT

Tablica trójkątna

2
3
4
5

1

2

3

4

Kratki tablicy wypełniamy symbolami:

v – jeżeli para stanów jest zgodna,

x – jeżeli para stanów jest sprzeczna, lub

parą (parami stanów następnych), jeżeli jest
to para zgodna warunkowo.

Kratki tablicy wypełniamy symbolami:

v

– jeżeli para stanów jest zgodna,

x

– jeżeli para stanów jest sprzeczna, lub

parą

(parami stanów następnych), jeżeli jest

to para zgodna warunkowo.

5

I

T
P

W

ZPT

Tablica trójkątna - przykład

a b c d a b c d

1 – 3 4 2 – 1 1 1
2 4 – – – 0 – – –
3 6 6 – – 0 1 – –
4 – 6 1 5 – 0 0 1
5 – – 2 – – – 1 –
6 3 – 2 3 0 – 0 1

2

3

4

5

6

1

2

3

4

5

1,2; 3,5

v

v

v

v

v

v

36

36

46

24

24

34

6

I

T
P

W

ZPT

Tablica trójkątna - przykład

2



3 3,6

4,6

4







5 2,4







6



3,4



1,2; 3,5



1

2

3

4

5

Po wypełnieniu tablicy sprawdzamy, czy pary stanów
sprzecznych (zaznaczone ) nie występują przypadkiem

jako pary stanów następnych.

Po wypełnieniu tablicy sprawdzamy, czy pary stanów

sprzecznych

(zaznaczone ) nie występują przypadkiem

jako pary stanów następnych.

Wszystkie kratki
niewykreślone
odpowiadają parom
zgodnym:

Wszystkie kratki
niewykreślone
odpowiadają

parom

zgodnym

:

Jeśli są takie pary, to należy je

skreślić (czyli zaznaczyć ). Proces ten trzeba

powtarzać tak długo, aż sprawdzone zostaną wszystkie
krzyżyki.

Jeśli są takie pary, to należy je

skreślić (czyli zaznaczyć ). Proces ten trzeba

powtarzać tak długo, aż sprawdzone zostaną wszystkie
krzyżyki.

(1,2); (1,3); (1,5); (2,3);
(2,4); (2,5); (3,5); (3,6);
(4,6).

(1,2); (1,3); (1,5); (2,3);
(2,4); (2,5); (3,5); (3,6);
(4,6).

7

I

T
P

W

ZPT

Obliczanie MKZ

1,2 v
1,3 v
1,5 v
2,3 v
2,4
2,5 v
3,5 v
3,6
4,6

1,2,3 v

MKZ:

1,2,3,5

MKZ = {{1,2,3,5}, {2,4}, {3,6}, {4,6}}

MKZ = {{1,2,3,5}, {2,4}, {3,6}, {4,6}}

1,2,5 v
1,3,5 v
2,3,5 v

2,4
3,6
4,6

8

I

T
P

W

ZPT

Algorytm minimalizacji

1) Wyznaczenie par stanów zgodnych,

1) Wyznaczenie par stanów zgodnych,

2) Obliczenie maksymalnych

zbiorów stanów zgodnych
(MKZ),

2) Obliczenie maksymalnych

zbiorów stanów zgodnych
(MKZ),

3) Selekcja zbiorów spełniających tzw.

warunek pokrycia (a) i
zamknięcia (b):

3) Selekcja zbiorów spełniających tzw.

warunek pokrycia (a) i
zamknięcia (b):

a) każdy stan musi wchodzić co najmniej

do jednej klasy;

a) każdy stan musi wchodzić co najmniej

do jednej klasy;

b) dla każdej litery wejściowej wszystkie

następniki (stany następne) danej klasy
muszą wchodzić do jednej klasy.

b) dla każdej litery wejściowej wszystkie

następniki (stany następne) danej klasy
muszą wchodzić do jednej klasy.

9

I

T
P

W

ZPT

Warunek pokrycia - przykład

a b c d a b c d

1 – 3 4 2 – 1 1 1
2 4 – – – 0 – – –
3 6 6 – – 0 1 – –
4 – 6 1 5 – 0 0 1
5 – – 2 – – – 1 –
6 3 – 2 3 0 – 0 1

MKZ = {{1,2,3,5}, {3,6},
{ 2,4}, 4,6}}

Aby spełnić warunek pokrycia wystarczy wybrać klasy:

Aby spełnić warunek pokrycia wystarczy wybrać klasy:

{1,2,3,5}, {4,6}

10

I

T
P

W

ZPT

Warunek zamknięcia - przykład

a b c d a b c d

1 – 3 4 2 – 1 1 1
2 4 – – – 0 – – –
3 6 6 – – 0 1 – –
4 – 6 1 5 – 0 0 1
5 – – 2 – – – 1 –
6 3 – 2 3 0 – 0 1

Dla wybranych klas {1,2,3,5},
{4,6}}
obliczamy ich następniki:

a

b

c

d

1,2,3,

5

4,6

Nie jest spełniony warunek zamknięcia !

Nie jest spełniony warunek zamknięcia !

4,6

4,6

3,6

3,6

2,4

2,4

2

2

3

3

6

6

1,2

1,2

3,5

3,5

3,6!

3,6!

2,4!

2,4!

11

I

T
P

W

ZPT

Warunek pokrycia i zamknięcia –

druga próba

a b c d a b c d

1 – 3 4 2 – 1 1 1
2 4 – – – 0 – – –
3 6 6 – – 0 1 – –
4 – 6 1 5 – 0 0 1
5 – – 2 – – – 1 –
6 3 – 2 3 0 – 0 1

a b

c

d

a

b

c

d

A

1,2

B

3,5

C

4,6

MKZ = {{1,2,3,5}, {3,6},
{ 2,4}, {4,6}}

Wybór:

a b

c

d

a

b

c

d

A C B

C

A

0

1

1

1

B C C

A

–

0

1

1

–

C B C

A

B

0

0

0

1

{1,2}, {3,5},
{4,6}

3 6 1,

2

3,

5

6 6

2

–

4 3

4

2

0

1

1

1

0

1

1

–

0

0

0

1

O.K.

O.K.

12

I

T
P

W

ZPT

Jeszcze jeden przykład

0

1

0

1

1

2

6

0

0

2

3

1

1

1

3

–

4

–

0

4

–

5

–

0

5

3

–

1

–

6

7

–

1

–

7

–

8

–

0

8

–

–

–

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

37

37

46

46

56

56

68

68

45

45

48

48

58

58

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

37

37

13

I

T
P

W

ZPT

Jeszcze jeden przykład c.d.

2

3

4

5

6

7

8

1

2

3

4

5

6

7

37

37

46

46

56

56

68

68

45

45

48

48

58

58

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

37

37

1,3
1,7
2,5
2,8
3,4
3,5
3,6
4,5
4,6
4,7
5,7
5,8
6,7
6,8

1,3
1,7
2,5
2,8
3,4
3,5
3,6
4,5
4,6
4,7
5,7
5,8
6,7
6,8

Pary zgodne:

Pary zgodne:

3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8

3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8

MKZ:

MKZ:

3,4,
5

3,4,
5

2,5,
8

2,5,
8

14

I

T
P

W

ZPT

Jeszcze jeden przykład c.d.

0

1

0

1

1

2

6

0

0

2

3

1

1

1

3

–

4

–

0

4

–

5

–

0

5

3

–

1

–

6

7

–

1

–

7

–

8

–

0

8

–

–

–

1

2,5,8 3,4,

5

3,4,6 4,5,7 4,6,7

1,3

1,7

6,8

(0,S

i

)

(1,S

i

)

2,5,
8
3,4,
5
3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8

2,5,
8
3,4,
5
3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8

MKZ:

MKZ:

33–

33–

1– –

1– –

– –3

– –3

45–

45–

– –7

– –7

45–

45–

5–8

5–8

5–8

5–8

64

64

68

68

7–

7–

– –

– –

2–

2–

–3–

–3–

–7–

–7–

2–

2–

Tablica następników

Tablica następników

15

I

T
P

W

ZPT

Jeszcze jeden przykład c.d.

0

1

0

1

1

2

6

0

0

2

3

1

1

1

3

–

4

–

0

4

–

5

–

0

5

3

–

1

–

6

7

–

1

–

7

–

8

–

0

8

–

–

–

1

2,5,8 3,4,

5

3,4,6 4,5,7 4,6,7

1,3

1,7

6,8

(0,S

i

)

3

3

7

3

7

2

2

7

(1,S

i

)

1

45

45

58

58

46

68

–

X

S

0

1

0

1

A

C

C

1

1

B

B

A

1

0

C

A

B

0

0

A

A

B

B

C

C

16

I

T
P

W

ZPT

Detektor sekwencji

Zaprojektować układ sekwencyjny
Mealy’ego o jednym wejściu
binarnym i jednym wyjściu binarnym.
Układ ma badać kolejne „trójki”
symboli wejściowych. Sygnał
wyjściowy pojawiający się podczas
trzeciego skoku układu ma wynosić
1, gdy „trójka” ma postać 001, a 0,
gdy „trójka” jest innej postaci.
Sygnał pojawiający się podczas
pierwszego i drugiego skoku układu
może być nieokreślony.

Zaprojektować układ sekwencyjny
Mealy’ego o jednym wejściu
binarnym i jednym wyjściu binarnym.
Układ ma badać kolejne

„trójki”

symboli wejściowych. Sygnał
wyjściowy pojawiający się podczas
trzeciego skoku układu ma wynosić

1

, gdy

„trójka”

ma postać

001

, a

0

,

gdy

„trójka”

jest

innej postaci

.

Sygnał pojawiający się podczas
pierwszego i drugiego skoku układu
może być nieokreślony.

1

2

3

4

5

6

7

0/-

1/-

0/-

0/0

0/0

0/0

0/0

1/0

1/0

1/0

1/1

0/-

1/-

1/-

01100100110101001

01100100110101001

- -

0

- -

0

- -

1

- -

1

- -

1

- -

1

- -

0

- -

0

- -

0

- -

0

17

I

T
P

W

ZPT

Detektor sekwencji

0/-

1/-

0/0

1

2

3

4

5

6

7

0/-

1/-

0/-

0/0

0/0

0/0

1/0

1/0

1/0

1/1

0/-

1/-

1/-

0/0

0/-

1/-

1

2

3

4

5

0/-

1/-

0/-

0/0

1/0

1/1

1/-

S 0 1 0 1
1 2 3 -

-

2 4 5 -

-

3 5 5 -

-

4 1 1 0 1
5 1 1 0 0

S

0

1

0 1

1

2

3

-

-

2

4

5

-

-

3

6

7

-

-

4

1

1

0 1

5

1

1

0 0

6

1

1

0 0

7

1

1

0 0

18

I

T
P

W

ZPT

Minimalizacja detektora

sekwencji

X

S

0

1

0

1

1 2

3

–

–

2 4

5

–

–

3 5

5

–

–

4 1

1

0

1

5 1

1

0

0

2 2 4, 3 5

3 2 5, 3 5

45

4 1 2, 1 3 1 4, 1 5

1 5

5 1 2, 1 3 1 4, 1 5

1 5



1

2

3

4

Bardzo dużo par zgodnych!

Bardzo dużo par zgodnych!

Do wyznaczenia MKZ wykorzystamy pary

sprzeczne, których jest znacznie mniej

(dwie).

Do wyznaczenia MKZ wykorzystamy pary

sprzeczne, których jest znacznie mniej

(dwie).

19

I

T
P

W

ZPT

Minimalizacja detektora

sekwencji

Pary sprzeczne zapisujemy w postaci wyrażenia
boolowskiego typu iloczyn (koniunkcja) dwu-
składnikowych sum.

Pary sprzeczne zapisujemy w postaci wyrażenia
boolowskiego typu iloczyn (koniunkcja) dwu-
składnikowych sum.

Na tej podstawie zapisujemy wyrażenie: (2  3) (4 

5),
które po wymnożeniu uzyskuje postać:

(2  3) (4  5) = 2 4  2 5  3 4  3 5

Na tej podstawie zapisujemy wyrażenie: (2  3) (4 

5),
które po wymnożeniu uzyskuje postać:

(2  3) (4  5) = 2 4  2 5  3 4  3 5

W detektorze sekwencji pary sprzeczne są: (2, 3); (4, 5).

W detektorze sekwencji pary sprzeczne są: (2, 3); (4, 5).

Odejmując od zbioru S = {1, 2, 3, 4, 5} wszystkich

stanów zbiory zapisane w poszczególnych

składnikach uzyskujemy rodzinę wszystkich MKZ.

Odejmując od zbioru S = {1, 2, 3, 4, 5} wszystkich

stanów zbiory zapisane w poszczególnych

składnikach uzyskujemy rodzinę wszystkich MKZ.

{1, 2, 3, 4, 5} – {2, 4} = {1, 3, 5}
{1, 2, 3, 4, 5} – {2, 5} = {1, 3, 4}

{1, 2, 3, 4, 5} – {3, 4} = {1, 2, 5}

{1, 2, 3, 4, 5} – {3, 5} = {1, 2, 4}

20

I

T
P

W

ZPT

Minimalizacja detektora

sekwencji

X

S

0 1 0 1

1

2 3 - -

2

4 5 - -

3

5 5 - -

4

1 1 0 1

5

1 1 0 0

X

S

0

1

135 125 135
134 125 135
125 124 135
124 124 135

MKZ: {1, 3, 5}, {1, 3, 4}, {1, 2, 5},
{1, 2, 4}

Funkcja przejść dla wszystkich MKZ

Funkcja przejść dla wszystkich MKZ

Dokładamy klasę {1,2,5}

Dokładamy klasę

{1,2,5}

X

S

0

1

0

1

A 135 125 135

0

0

B 125 124 135

0

0

C 124 124 135

0

1

X

S

0

1

0

1

A

B

A

0

0

B

C

A

0

0

C

C

A

0

1

Klasy: {1,3,5}, {1, 2, 4}, {1, 2, 5} spełniają

warunek pokrycia i zamkniętości

Klasy:

{

1,3,5}, {1, 2, 4},

{1, 2, 5}

spełniają

warunek pokrycia i zamkniętości

ale nie spełniają
warunku zamkniętości
– stany następne:
{1,2,5} !

ale nie spełniają
warunku zamkniętości
– stany następne:

{1,2,5} !

Klasy {1, 3, 5}, {1, 2, 4} spełniają warunek

pokrycia,

Klasy

{1, 3, 5}, {1, 2, 4}

spełniają warunek

pokrycia,

21

I

T
P

W

ZPT

...a to już było

X

S

0

1

0

1

A

B

A

0

0

B

C

A

0

0

C

C

A

0

1

Uzyskany automat był już realizowany na
przerzutnikach i bramkach – wykład cz5, plansze
13 do 20.

22

I

T
P

W

ZPT

E

S

0

1

S

0

S

0

S

1

S

1

S

1

S

2

S

2

S

2

S

3

S

3

S

3

S

4





S

7

S

7

S

0

Synteza licznika

Licznik

E

clock

Q

Przykład licznika z wejściem

Enable

23

I

T
P

W

ZPT

E

S

0

1

E

Q2Q1Q0

0

1

S

0

S

0

S

1

000

000

001

S

1

S

1

S

2

001

001

010

S

2

S

2

S

3

010

010

011

S

3

S

3

S

4

011

011

100

S

4

S

4

S

5

100

100

101

S

5

S

5

S

6

101

101

110

S

6

S

6

S

7

110

110

111

S

7

S

7

s

0

111

111

000

S’

Q2Q1Q0

Q2’Q1’Q0’

Licznik modulo 8

Tablica przejść

Tablica przejść

Zakodowana tablica przejść

kod binarny

Zakodowana tablica przejść

kod binarny

24

I

T
P

W

ZPT

E

Q2Q1Q0

0

1

E

Q2Q1Q

0

0

1

000

000

001

000

000

001

001

001

010

001

001

010

010

010

011

011

011

100

011

011

100

010

010

011

100

100

101

110

110

111

101

101

110

111

111

000

110

110

111

101

101

110

111

111

000

100

100

101

Q2Q1Q0

Q2’Q1’Q0’

Q2Q1Q

0

Q2’Q1’Q0’

Zakodowana tablica p-w

25

I

T
P

W

ZPT

E

Q2Q1Q0

0

1

E

Q2Q1Q0

0

1

0

1

0

1

000

000

001

000

0

0

0

0

0

1

001

001

010

001

0

0

0

1

1

0

011

011

100

011

0

1

1

0

1

0

010

010

011

010

0

0

1

1

0

1

110

110

111

110

1

1

1

1

0

1

111

111

000

111

1

0

1

0

1

0

101

101

110

101

1

1

0

1

1

0

100

100

101

100

1

1

0

0

0

1

Q2Q1Q0

Q2’Q1’Q0’

Q2Q1Q0

D2

D1

D0

Zakodowana tablica p-w (D)

D2 =

D2 =

1

Q

Q2

0

Q

Q2



D1 =

D1 =

E

Q1

D0 =

D0 =

E

Q0

E

Q2



2Q1Q0E

Q



1Q0E

Q



0

Q

Q1



0E

Q

26

I

T
P

W

ZPT

E

Q2Q1Q0

0

1

E

Q2Q1Q0

0

1

0

1

0

1

000

000

001

000

0

0

0

0

0

1

001

001

010

001

0

0

0

1

0

1

011

011

100

011

0

1

0

1

0

1

010

010

011

010

0

0

0

0

0

1

110

110

111

110

0

0

0

0

0

1

111

111

000

111

0

1

0

1

0

1

101

101

110

101

0

0

0

1

0

1

100

100

101

100

0

0

0

0

0

1

Q2Q1Q0

Q2’Q1’Q0’

Q2Q1Q0

T2

T1

T0

Zakodowana tablica p-w (T)

T2 =

T2 =

EQ1Q0

T1 =

T1 =

T0 =

T0 =

EQ0

E

27

I

T
P

W

ZPT

Schemat licznika

T Q

Q

Clock

T Q

Q

Enable

T Q

Q

1

1

1

0

2

0

1

0

Q

T

Q

EQ

T

EQ

T

E

T









28

I

T
P

W

ZPT

Problem kodowania

x

s

0 1 0 1

A

A B 0 0

B

A C 0 0

C

D C 0 0

D

A B 0 1

Wariant I

A = 00
B = 01
C = 10

D = 11

Wariant I

A = 00
B = 01
C = 10

D = 11

Wariant II

A = 00
B = 11
C = 01

D = 10

Wariant II

A = 00
B = 11
C = 01

D = 10

2

1

2

1

1

Q

Q

x

Q

Q

D





2

1

2

1

2

1

2

Q

Q

x

Q

xQ

Q

Q

x

D







2

1

Q

xQ

y 

2

1

2

1

Q

Q

x

Q

x

D





x

D

2



2

1

Q

xQ

y 

Wariant II

Wariant II

Wariant I

Wariant I

29

I

T
P

W

ZPT

Kodowanie

3 stany - 3 różne kodowania

3 stany - 3 różne kodowania

4 stany - 3 różne kodowania

4 stany - 3 różne kodowania

5 stanów
-

5 stanów
-

140
kodowań

140
kodowań

7 stanów
-

7 stanów
-

840
kodowań

840
kodowań

9 stanów
-

9 stanów
-

ponad 10 milionów
kodowań

ponad 10 milionów
kodowań

Jak przewidzieć (obliczyć)
najlepsze kodowanie stanów?

Jak przewidzieć (obliczyć)
najlepsze kodowanie stanów?

Czy realne jest sprawdzenie wszystkich
możliwości

Czy realne jest sprawdzenie wszystkich
możliwości

30

I

T
P

W

ZPT

KODOWANIE

Klasyczne procedury kodowania są bardzo
skomplikowane i omówienie ich w ograniczonym
czasie wykładu jest niemożliwe.

Klasyczne procedury kodowania są bardzo
skomplikowane i omówienie ich w ograniczonym
czasie wykładu jest niemożliwe.

Można korzystać z oprogramowania
akademickiego: JEDI, NOVA (uniwersytet
kalifornijski: Berkeley).

Można korzystać z oprogramowania
akademickiego: JEDI, NOVA (uniwersytet
kalifornijski: Berkeley).