1

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

2

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

3

I

T
P

W

ZPT

KODOWANIE

Jedyną rozsądną z punktu widzenia dzisiejszych
technologii i realną do omówienia w
ograniczonym

1)

czasie wykładu jest metoda

wykorzystująca podział
z własnością podstawienia.

Jedyną rozsądną z punktu widzenia dzisiejszych
technologii i realną do omówienia w
ograniczonym

1)

czasie wykładu jest metoda

wykorzystująca podział
z własnością podstawienia.

1)

A wszystkich wytrwałych w tym procesie
specjalnie nagradzam na egzaminie.

1)

A wszystkich wytrwałych w tym procesie
specjalnie nagradzam na egzaminie.

4

I

T
P

W

ZPT

Elementy rachunku podziałów c.d.

Iloczyn podziałów, iloraz podziałów oraz relacja 

Sumą podziałów



a

+



b

nazywamy najmniejszy

(względem relacji ) podział, który jest nie mniejszy od



a

oraz



b

.

Suma podziałów

5

I

T
P

W

ZPT

Przykładzik





9

,

8

,

7

6

,

5

;

4

,

3

;

2

,

1

;







9

8

,

7

5

,

4

;

3

,

2

;

6

,

1

;

;





a



b





;...

6

,

2

,

1





a

+ 

b





;...

6

,

3

,

2

,

1





a

+ 

b





;...

6

,

4

,

3

,

2

,

1





a

+ 

b





9

,

8

,

7

;

6

,

5

,

4

,

3

,

2

,

1





a

+ 

b





;...

6

,

5

,

4

,

3

,

2

,

1





a

+ 

b

6

I

T
P

W

ZPT

Własność podstawienia

Podział  na zbiorze stanów automatu M=<S, I ,

δ> ma własność podstawienia (closed partition),
gdy dla każdej pary stanów S

i

, S

j

należącej do

tego samego bloku  i każdego wejścia I

k

stany

I

k

S

i

oraz I

k

S

j

należą do wspólnego bloku .

Podział  na zbiorze stanów automatu M=<S, I ,

δ> ma własność podstawienia (closed partition),
gdy dla każdej pary stanów S

i

, S

j

należącej do

tego samego bloku  i każdego wejścia I

k

stany

I

k

S

i

oraz I

k

S

j

należą do wspólnego bloku .

x

s

0

1

0

1

A

A

F

0

0

B

E

C

0

1

C

C

E

0

1

D

F

A

1

0

E

B

F

1

1

F

D E

0

0





F

D

C

E

B

A

,

,

;

,

,

1





Podziały z własnością podstawienia:

Podziały z własnością podstawienia:





F

E

D

B

C

A

,

;

,

;

,

2





7

I

T
P

W

ZPT

Twierdzenie

Dany jest automat M o zbiorze stanów S, |S| = n.

Do zakodowania stanów potrzeba Q

1

, ..., Q

k

elementów pamięci.



() – liczba bloków podziału 

Jeżeli istnieje podział  z własnością podstawienia i

jeżeli r spośród k zmiennych kodujących Q

1

, ..., Q

k

, gdzie

r = log

2



(), jest przyporządkowanych blokom podziału  tak,

że wszystkie stany zawarte w jednym bloku są oznaczone tymi
samymi kodami Q

1

, ..., Q

r

, to funkcje Q’

1

, ..., Q’

r

, są niezależne

od pozostałych (k – r) zmiennych.

Dany jest automat M o zbiorze stanów S, |S| = n.

Do zakodowania stanów potrzeba Q

1

, ..., Q

k

elementów pamięci.



() – liczba bloków podziału 

Jeżeli istnieje podział  z własnością podstawienia i

jeżeli r spośród k zmiennych kodujących Q

1

, ..., Q

k

, gdzie

r = log

2



(), jest przyporządkowanych blokom podziału  tak,

że wszystkie stany zawarte w jednym bloku są oznaczone tymi
samymi kodami Q

1

, ..., Q

r

, to funkcje Q’

1

, ..., Q’

r

, są niezależne

od pozostałych (k – r) zmiennych.

8

I

T
P

W

ZPT

Przykład 1- interpretacja w.p.

x

s

0

1

0

1

A

A

F

0

0

B

E

C

0

1

C

C

E

0

1

D

F

A

1

0

E

B

F

1

1

F

D E

0

0





F

D

C

E

B

A

,

,

;

,

,

1





0 0

0 1
0 1
0 0
1 0
1 0

Kodowanie wg 

1

Kodowanie wg 

1





A
B
C

D

E

F

0
0
1
1
0
1





F

E

C

B

D

A

τ

,

;

,

;

,



Nie wystarcza to do

zakodowania



1

•



=

(0)

Warunek jednoznaczności kodowania!

Warunek jednoznaczności kodowania!

9

I

T
P

W

ZPT

Przykład 1…

x

s

0 1 0 1

A

A F 0 0

B

E C 0 1

C

C E 0 1

D

F A 1 0

E

B F 1 1

F

D E 0 0

Q

1

Q

2

Q

3

A 0 0 0
B 0 0 1
C 1 0 1
D 1 0 0
E 0 1 0
F 1 1 0

Co to znaczy, że zastosujemy
kodowanie wg podziału
zamkniętego:

Co to znaczy, że zastosujemy
kodowanie wg podziału
zamkniętego:

Q

1

’ = D

1

= f(x,Q

1

)

Q

1

’ = D

1

= f(x,Q

1

)

Nie musimy obliczać funkcji

wzbudzeń, aby stwierdzić, że

pierwsza z nich, czyli D

1

będzie…

Niestety tylko jedną zmienną
zakodowaliśmy wg podziału zamkniętego,
zatem:

Niestety tylko jedną zmienną
zakodowaliśmy wg podziału zamkniętego,
zatem:

a co z
pozostałymi?

Q

2

’ = D

2

=

f(x,Q

1

,Q

2

,Q

3

)

Q

3

’ = D

3

=

f(x,Q

1

,Q

2

,Q

3

)

Q

2

’ = D

2

=

f(x,Q

1

,Q

2

,Q

3

)

Q

3

’ = D

3

=

f(x,Q

1

,Q

2

,Q

3

)

10

I

T
P

W

ZPT

Przykład 1…

x

s

0

1

0

1

A

A

F

0

0

B

E

C

0

1

C

C

E

0

1

D

F

A

1

0

E

B

F

1

1

F

D

E

0

0





F

E

D

B

C

A

,

;

,

;

,

2



π





F

D

C

E

B

A

,

,

;

,

,

1



π

Kodowanie wg 

1

Kodowanie wg 

1

0 0

0 1
0 0
0 1
1 0
1 0

A
B
C

D

E

F

0
0
1
1
0
1



2



2

)

(0











2

1

Jest to kodowanie jednoznaczne

A może jest więcej podziałów zamkniętych:

A może jest więcej podziałów zamkniętych:

Później wykażemy, że oprócz 

1

Później wykażemy, że oprócz 

1

jest 

2

jest 

2

11

I

T
P

W

ZPT

PRZYKŁAD 1 c.d.

Przy tak dobranym kodowaniu pierwsza funkcja
wzbudzeń Q

1

’

tego automatu będzie zależna od

jednej zmiennej wewnętrznej, a druga i trzecia
łącznie (Q

2

’, Q

3

’) od dwóch zmiennych

wewnętrznych, czyli

Q

1

’ = f(x,Q

1

)

Q

2

’ = f(x,Q

2

,Q

3

)

Q

3

’ = f(x,Q

2

,Q

3

)

Przy tak dobranym kodowaniu pierwsza funkcja
wzbudzeń Q

1

’

tego automatu będzie zależna od

jednej zmiennej wewnętrznej, a druga i trzecia
łącznie (Q

2

’, Q

3

’) od dwóch zmiennych

wewnętrznych, czyli

Q

1

’ = f(x,Q

1

)

Q

2

’ = f(x,Q

2

,Q

3

)

Q

3

’ = f(x,Q

2

,Q

3

)

Kto nie wierzy, niech zakoduje, obliczy funkcje
Q

1

’, Q

2

’, Q

3

’ i sprawdzi.

Kto nie wierzy, niech zakoduje, obliczy funkcje
Q

1

’, Q

2

’, Q

3

’ i sprawdzi.

Dla całego roku!

Dla całego roku!

12

I

T
P

W

ZPT

Obliczanie podziału zamkniętego

x

s

0 1

A

A F

B

E C

C

C E

D

F A

E

B F

F

D E

A,B

A,B

A,E

A,E

C,F

C,F

C,D

C,D

F

F

E

E

B,D

B,D

A,C

A,C

E,F

E,F

A,D

A,D

A,F

A,F

A,B

A,B

A,C

A,C

A,D

A,D





F

D,

C,

;

E

B,

A,

1









F

E,

;

D

B,

;

C

A,

2





 

1



Tworzymy graf par następników

dla różnych wierzchołków

początkowych

13

I

T
P

W

ZPT

PRZYKŁAD 2

x

s

0

1

Z

A

H

B

0

B

F

A

0

C

G

D

0

D

E

C

1

E

A

C

0

F

C

D

0

G

B

A

0

H

D

B

0

Generujemy podziały zamknięte

Generujemy podziały zamknięte

Do zakodowania stanów
automatu M potrzebne są 3
podziały 2-blokowe, takie że:

Do zakodowania stanów
automatu M potrzebne są 3
podziały 2-blokowe, takie że:

(0)















c

b

a

14

I

T
P

W

ZPT

PRZYKŁAD 2 c.d.

x

s

0

1

Z

A

H

B

0

B

F

A

0

C

G

D

0

D

E

C

1

E

A

C

0

F

C

D

0

G

B

A

0

H

D

B

0

Graf par następników :

Graf par następników :





H

G,

F,

E,

;

D

C,

B,

A,

1





A,B

A,B

F,H

F,H

C,D

C,D

E,F

E,F

A,C

A,C

G,E

G,E

G,H

G,H

B,D

15

I

T
P

W

ZPT

PRZYKŁAD 2 c.d.

x

s

0

1

Z

A

H

B

0

B

F

A

0

C

G

D

0

D

E

C

1

E

A

C

0

F

C

D

0

G

B

A

0

H

D

B

0





G

F,

C,

B,

;

H

E,

D,

A,



G

F,

;

H

E,

C

B,

;

D

A,

;

G

F,

C

B,

;

H

E,

D,

A,

;

H

E,

D

A,

;

G

F,

C,

B,

;

A,D

A,D

D,H

D,H

B,F

B,F

+

=



2

+

=



2

16

I

T
P

W

ZPT

PRZYKŁAD 2 c.d.





H

G,

F,

E,

;

D

C,

B,

A,

1









G

F,

C,

B,

;

H

E,

D,

A,

2





Niestety:

Niestety:

Potrzebny jest więc jeszcze jeden podział :

Potrzebny jest więc jeszcze jeden podział :





)

0

(













G

F,

;

H

E,

;

C

B,

;

D

A,

2

1

)

(0

τ 











2

1





F

E,

D,

C,

;

H

G,

B,

A,



τ

17

I

T
P

W

ZPT

PRZYKŁAD 2 c.d.





H

G,

F,

E,

;

D

C,

B,

A,

1









G

F,

C,

B,

;

H

E,

D,

A,

2





0
0
0
0
1
1
1
1

0
1
1
0
0
1
1
0

Kodowanie wg 

1

Kodowanie wg 

1



2



2

A
B
C

D

E

F

G
H





F

E,

D,

C,

;

H

G,

B,

A,



τ





0
0
1
1
1
1
0
0

18

I

T
P

W

ZPT

PRZYKŁAD 2 c.d.

Przy tak dobranym kodowaniu dwie funkcje
wzbudzeń Q

1

’

i Q

2

’ tego automatu będą zależne od

jednej zmiennej wewnętrznej, a trzecia Q

3

’ (w

najgorszym przypadku) od trzech zmiennych, czyli

Q

1

’ = f(x,Q

1

)

Q

2

’ = f(x,Q

2

)

Q

3

’ = f(x,Q

1

,Q

2

,Q

3

)

Przy tak dobranym kodowaniu dwie funkcje
wzbudzeń Q

1

’

i Q

2

’ tego automatu będą zależne od

jednej zmiennej wewnętrznej, a trzecia Q

3

’ (w

najgorszym przypadku) od trzech zmiennych, czyli

Q

1

’ = f(x,Q

1

)

Q

2

’ = f(x,Q

2

)

Q

3

’ = f(x,Q

1

,Q

2

,Q

3

)

Warto zakodować, obliczyć funkcje wzbudzeń
Q

1

’, Q

2

’, Q

3

’ i sprawdzić, czy rzeczywiście tak

jest.

Warto zakodować, obliczyć funkcje wzbudzeń
Q

1

’, Q

2

’, Q

3

’ i sprawdzić, czy rzeczywiście tak

jest.

19

I

T
P

W

ZPT

Komentarz

Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.

Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.

Q

1

’ = f(x,Q

1

)

Q

2

’ = f(x,Q

1

,Q

2

,Q

3

)

Q

3

’ = f(x,Q

1

,Q

2

,Q

3

)

Q

1

’ = f(x,Q

1

)

Q

2

’ = f(x,Q

1

,Q

2

,Q

3

)

Q

3

’ = f(x,Q

1

,Q

2

,Q

3

)

0 0

0

0 0

1

0 1

0

0 1

1

1 0

0

1 0

1

1 1

0

1 1

1

A
B
C
D
E
F
G
H

Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.

Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.

W szczególności dla kodowania wg naturalnego
kodu binarnego

1)

:

W szczególności dla kodowania wg naturalnego
kodu binarnego

1)

:

1)

Naturalny kod binarny jest przyjmowany domyślnie do kodowania

automatów w komercyjnych systemach projektowania układów
cyfrowych

1)

Naturalny kod binarny jest przyjmowany domyślnie do kodowania

automatów w komercyjnych systemach projektowania układów
cyfrowych

20

I

T
P

W

ZPT

Nie martwmy się…

W najnowszych

systemach istnieje

opcjonalna

możliwość

wprowadzenia

kodowania

obliczonego

zewnętrznie przez

użytkownika

21

I

T
P

W

ZPT

21

Zadanie treningowe – licznik

mod. 8

Zaprojektować licznik mod 8 z wejściem zezwalającym E (Enable).
Przerzutniki do realizacji dobrać tak

1)

, aby uzyskać najprostszy

schemat logiczny licznika.

Zaprojektować licznik mod 8 z wejściem zezwalającym E (Enable).
Przerzutniki do realizacji dobrać tak

1)

, aby uzyskać najprostszy

schemat logiczny licznika.

Licznik

E

clock

Q

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

1)

W tym sensie jest to

zadanie z metod kodowania

1)

W tym sensie jest to

zadanie z metod kodowania

22

I

T
P

W

ZPT

22

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’

Zakodowana tablica przejść

licznika

Tablica przejść

Tablica przejść

Zakodowana tablica przejść
kod binarny

Zakodowana tablica przejść
kod binarny

23

I

T
P

W

ZPT

23

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 transformowana do tablicy
Karnaugha

24

I

T
P

W

ZPT

24

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

Funkcje wzbudzeń dla

przerzutników D

D2 =

D2 =

1

Q

Q2

0

Q

Q2



D1 =

D1 =

E

Q1

D0 =

D0 =

E

Q0

Q2E



E

2Q1Q0

Q



1Q0E

Q



0

Q

Q1



0E

Q



QQ’

D

00

0

01

1

10

0

11

1

25

I

T
P

W

ZPT

25

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

T2 =

T2 =

EQ1Q0

T1 =

T1 =

T0 =

T0 =

EQ0

E

Funkcje wzbudzeń dla

przerzutników T

QQ’

T

00

0

01

1

10

1

11

0

26

I

T
P

W

ZPT

26

Schemat logiczny
licznika

1)

T

0

Q

Q

Clock

T

1

Q

Q

Enable

T

2

Q

Q

1

1

Q

T



1

0

2

0

1

0

Q

EQ

T

EQ

T

E

T







1)

Najprostszy na

świecie

E

Q

E

Q

D

0

0

0





E

Q

Q

Q

Q

E

Q

D

0

1

0

1

1

1







E

Q

Q

Q

Q

Q

E

Q

Q

Q

D

0

1

2

0

2

2

1

2

2









27

I

T
P

W

ZPT

27

E

A

0

1

A

0

A

0

A

1

A

1

A

1

A

2

A

2

A

2

A

3

A

3

A

3

A

4

A

4

A

A

5







A

14

A

14

A

15

A

15

A

15

A

0

Schemat ten można uogólniać…

Gdybyśmy chcieli zaprojektować licznik
mod 16

2

2

Q

T



2

1

0

3

Q

Q

EQ

T 

1

1

1

0

2

0

1

0

Q

T

Q

EQ

T

EQ

T

E

T









28

I

T
P

W

ZPT

28

Schemat logiczny licznika…

T Q

Q

Clock

T Q

Q

Enable

Rst

T Q

Q

T Q

Q