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