Tworzenie automatów
4. Przy użyciu przerzutnika T wykryj sekwencję: 10001.
Na początek rysujemy graf dla wartości, które chcemy uzyskać. W przypadku tego
zadania jest to ciąg znaków: „10001”.
A. „Punkt zerowy” – w tym punkcie rozpoczynamy badanie wprowadzanego ciągu
znaków. (A = 0000…)
B. Z punktu A do punktu B przechodzimy, gdy wykryta zostanie „1”, która jest
pierwszym znakiem w poszukiwanym ciągu. (B = 1)
C. Z punktu B do punktu C przechodzimy, gdy wykryte zostanie „0”, które jest drugim
znakiem w poszukiwanym ciągu. (C = 10)
D. Z punktu C do punktu D przechodzimy, gdy wykryte zostanie „0”, które jest trzecim
znakiem w poszukiwanym ciągu. (D = 100)
E.Z punktu D do punktu E przechodzimy, gdy wykryte zostanie „0”, które jest czwartym
znakiem w poszukiwanym ciągu. (E = 1000)
F. Z punktu E do punktu F przechodzimy, gdy wykryta zostanie „1”, która jest ostatnim
znakiem w poszukiwanym ciągu. (F = 10001)
Teraz, by uzupełnić graf (rozpatrzyć wszystkie możliwe przypadki dla każdego punktu)
musimy dorysować brakujące „ścieżki”.
Punkt A – brakującą ścieżką jest ścieżka, gdy X (wartość nad linią) jest równa „0”.
Ponieważ punkt A jest punktem zerowym, odwołuje się do samego siebie.
Punkt B – brakująca ścieżka z wartością 1. Dla tej ścieżki punkt B również odwołuje się
do samego siebie, ponieważ niezależnie od tego, ile 1 się wyświetli (powiedzmy, że ciąg
wygląda następująco: „1111”), to ciągle ostatnim bitem będzie „1”.
Punkt C – brakująca ścieżka z wartością 1. W przypadku, gdy w punkcie C otrzymamy
„1”, musimy wrócić do punktu B (w ciągu „101” ostatnim bitem jest „1”).
Punkt D – brakująca ścieżka z wartością 1. Podobnie jak w przypadku punktu D, ciąg
„1001” będzie nieodpowiedni, by kontynuować. Wracamy do punktu B.
Punkt E – brakująca ścieżka z wartością 0. Po otrzymaniu takiego wyniku musimy
wrócić do punktu A (ciąg otrzymany będzie wyglądał: „10000”).
Punkt F – brakuje nam obu ścieżek. Ścieżka z wartością „1” będzie biegła do punktu B
(ponieważ ciąg będzie miał w tym przypadku wartość „100011”, czyli jedynka na końcu).
Natomiast ścieżka z wartością „0” kieruje się ku punktowi C (ciąg znaków „100010” –
w treści zadania nie było podane, że ciągi nie mogą się zazębiać).
Graf jest już kompletny
Teraz należy rozpisać punkty A-F jako liczby binarne. Wg. mgr inż. M. Rubanowicza
dla automatów najlepiej to zrobić używając liczb w kodzie Graya, a więc z tego względu, że
jest tylko 6 punktów, wystarcza nam użycie kodu 3-bitowego. Wartości dla tych punktów:
A – 000
B – 001
C – 011
D – 010
E – 110
F – 111
Można się teraz zabrać za tworzenie tabelki. W jaki sposób?
Q
2
,Q
1
,Q
0
X=0
X=1
Y
X
0
(T/D/JK)
2
,
1
,
0
X
1
(T/D/JK)
2
,
1
,
0
A
A -> ?
A -> ?
A==10001
A -> X
0
=
(T/D/JK)
2
,
1
,
0
A -> X
1
=
(T/D/JK)
2
,
1
,
0
B
B -> ?
B -> ?
B==10001
B -> X
0
=
(T/D/JK)
2
,
1
,
0
B -> X
1
=
(T/D/JK)
2
,
1
,
0
C
C -> ?
C -> ?
C==10001
C -> X
0
=
(T/D/JK)
2
,
1
,
0
C -> X
1
=
(T/D/JK)
2
,
1
,
0
D
D -> ?
D -> ?
D==10001
D -> X
0
=
(T/D/JK)
2
,
1
,
0
D -> X
1
=
(T/D/JK)
2
,
1
,
0
E
E -> ?
E -> ?
E==10001
E -> X
0
=
(T/D/JK)
2
,
1
,
0
E -> X
1
=
(T/D/JK)
2
,
1
,
0
F
F -> ?
F -> ?
F==10001
F -> X
0
=
(T/D/JK)
2
,
1
,
0
F -> X
1
=
(T/D/JK)
2
,
1
,
0
Kolumna Q
2
, Q
1
, Q
0
– w miejsca A-F wpisujemy przyjęte wcześniej liczby zapisane
w kodzie Graya.
Kolumna X = 0 – kolumnę tę uzupełniamy wpisując wartość w kodzie Graya dla punktu,
do którego przechodzimy, gdy X = 0 (czyli gdy jesteśmy w punkcie F, po otrzymaniu
X = 0 przechodzimy do punktu A – odczytać to można z wykonanego grafu).
Kolumna X = 1 – Analogiczna do poprzedniej (czyli gdy jesteśmy w punkcie D, po
otrzymaniu X = 1 przechodzimy do punktu B – odczytać to można z wykonanego
grafu).
Kolumna Y – określa, w którym punkcie wprowadzany ciąg 0 i 1 przyjmie wartość
„10001” (lub inną żądaną).
Kolumna X
0
(T/D/JK)
2
,
1
,
0
– porównanie kolumny Q
2-0
z kolumną X = 0, biorąc pod
uwagę tablicę przejść używanego typu przerzutnika (w przypadku tego zadania –
przerzutnika T). Do znalezienia na Wiki .
Kolumna X
1
(T/D/JK)
2
,
1
,
0
– analogiczna do poprzedniej, z tym wyjątkiem, że
porównujemy kolumnę X = 1.
Prawidłowo wypełniona tabela:
Q
2
,Q
1
,Q
0
X=0
X=1
Y
X
0
(T
2
, T
1
, T
0
)
X
1
(T
2
, T
1
, T
0
)
000
000
001
0
000
001
001
011
001
0
010
000
011
010
001
0
001
010
010
110
001
0
100
011
110
000
111
0
110
110
111
011
001
1
100
100
Funkcje dla T2, T1, T0 (przyjmujących wartość 1) wypisujemy w oparciu o kolumnę Q
2
,
Q
1
, Q
0
(„|X” -> „X = 0”).
T
0
= |X|Q
2
Q
1
Q
0
+ X|Q
2
|Q
1
|Q
0
+ X|Q
2
Q
1
|Q
0
T
1
= |X|Q
2
|Q
1
Q
0
+ |XQ
2
Q
1
|Q
0
+ X|Q
2
Q
1
Q
0
+ X|Q
2
Q
1
|Q
0
+ XQ
2
Q
1
|Q
0
T
2
= |X|Q
2
Q
1
|Q
0
+ |XQ
2
Q
1
|Q
0
+ |XQ
2
Q
1
Q
0
+ XQ
2
Q
1
|Q
0
+ XQ
2
Q
1
Q
0
Po zminimalizowaniu tych funkcji zostaje nam:
T
0
= |Q
2
Q
1
(XOR X, Q
0
) + X|Q
2
|Q
1
|Q
0
T
1
= |XQ
2
Q
1
|Q
0
+ XQ
1
|Q
0
+ |Q
2
Q
0
(XNOR X, Q
1
)
T
2
= |X|Q
2
Q
1
|Q
0
+ Q
2
Q
1
Q
0
+ Q
2
Q
1
|Q
0
Zostaje nam jeszcze rozpisanie funkcji Y, wykrywającej nasz ciąg znaków „10001”.
Y = Q
2
Q
1
Q
0
Schemat licznika dla tego grafu.
Układ wykrywający ciąg znaków „10001”.
Made by B. Rzozi (19.01.2011)
W oparciu o notatki udostępnione przez:
shenlon (
http://shenlon.eu
)