Piotr Kawalec
Wykład III - 1
Wykład III
Przykłady kodowania
automatów
synchronicznych
z zastosowaniem rachunku
podziałów
Technika cyfrowa
Piotr Kawalec
Wykład III - 1
Wykład III
Przykłady kodowania
automatów
synchronicznych
z zastosowaniem rachunku
podziałów
Technika cyfrowa
Piotr Kawalec
Wykład III - 2
Technika cyfrowa
Etapy metody
Wyznaczyć zbiór par podziałów
,
gdzie
jest pewnym podziałem dwublokowym
lub w
szczególności prawidłowym
Narysować graf par podziałów
Zaznaczyć na grafie podziały dogodne ze
względu na wyjście
Wybrać rodzinę T
k opt.
o minimalnej cenie
Piotr Kawalec
Wykład III - 3
Technika cyfrowa
Przykłady kodowania z
zastosowaniem rachunku podziałów
Przykład 1
Zakodować automat zadany tablicą przejść-
wyjść
x x
1
x
2
x
1
x
2
s
1 1 3 0 1
2 4 2 1 --
3 3 1 1 0
4 1 4 -- 1
Piotr Kawalec
Wykład III - 4
Technika cyfrowa
Podziały zewnętrzne i grafy podziałów
(y)
=
x1
(y)
•
x2
(y)
={1, 23, (4)} • {14, 3,
(2)} =
14
x x
1
x
2
1
2
3
4
12
13
14
s
1 1 3 1
2 4 2 2
3 3 1 3
4 1 4 4
2
14
2
{12, 3, 4}
14
12
Piotr Kawalec
Wykład III - 5
Technika cyfrowa
Wyznaczenie rodzin końcowych i cen
Z grafu podziałów można wyznaczyć rodzinę
końcową
T
k
={
12
,
14
}, która jest
równocześnie
rodziną optymalną
T
k opt
Ceny podziałów
c(
12
)
= 1+1-1=1; c(
14
)
=1+2-1=2;
c(y)=1+1-1=1; c = 4
Kodowanie
s
12
14
1 0 1
2 0 0
3 1 0
4 1 1
Q
1
Q
2
Piotr Kawalec
Wykład III - 6
Technika cyfrowa
Zakodowana tablica przejść-wyjść
x
0 1
0 1
(s)
Q
1
Q
2
(2)
00
11 00
1 --
(1)
01
01 10
0 1
(4)
11
01 11
-- 1
(3)
10
10 01
1 0
Q
1
Q
2
y
Funkcja wyjść
y = x
Q
2
+ x
Q
2
Piotr Kawalec
Wykład III - 7
Technika cyfrowa
Tablice wzbudzeń przy realizacji na
przerzutnikach D
x
0 1
0 1
(s)
Q
1
Q
2
(2)
00
1 0
1 0
(1)
01
0 1
1 0
(4)
11
0 1
1 1
(3)
10
1 0
0 0
D
1
D
2
Funkcje wzbudzeń
D
1
= x
Q
2
+ x
Q
2
;
D
2
= x
Q
1
+
Q
1
Q
2
Piotr Kawalec
Wykład III - 8
Technika cyfrowa
Przykłady kodowania z
zastosowaniem rachunku podziałów
Przykład 2
Zakodować automat zadany tablicą przejść-
wyjść
x
s x
1
x
2
y
1
y
2
1 1 2 0 0
2 1 3 0 0
3 4 3 -- 0
4 5 3 1 1
5 1 3 0 1