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

)