Wykonanie: Krakowian Konrad 140059 Rakowski Bartosz 140116 |
mgr inż. A. Sterna Poniedziałek, godz. 15.15 27.03.2006r. |
Sprawozdanie nr 5
AUTOMATY MOORE'A I MEALY
Cel ćwiczenia
Celem ćwiczenia jest zapoznanie z dwoma podstawowymi kategoriami automatów oraz metodami transformacji automatu Moore'a w automat Mealy i odwrotnie.
Program ćwiczenia:
Zaprojektować detektor sekwencji 1111
A) Sekwencje mogą zachodzić na siebie:
a) Realizacja automatu Moore'a:
z1 z1 z1 z1
y1 y0 y0 y0
z0 z0
z1 z0
z0
y0
z0
z0=0
z1=1
Tablica przejść automatu Moore`a:
WY |
y0 |
y0 |
y0 |
y0 |
y1 |
WE\stany |
q0 |
q1 |
q2 |
q3 |
q4 |
z0 |
q0 |
q0 |
q0 |
q0 |
q0 |
z1 |
q1 |
q2 |
q3 |
q4 |
q4 |
b) Realizacja automatu Mealy'ego:
Tablica przejść: Tablica wyjść:
|
q0 |
q1 |
q2 |
q3 |
q4 |
z0 |
q0 |
q0 |
q0 |
q0 |
q0 |
z1 |
q1 |
q2 |
q3 |
q4 |
q4 |
|
q0 |
q1 |
q2 |
q3 |
q4 |
z0 |
y0 |
y0 |
y0 |
y0 |
y0 |
z1 |
y0 |
y0 |
y0 |
Y1 |
y1 |
Po minimalizacji:
Tablica przejść: Tablica wyjść:
|
q0 |
q1 |
q2 |
q3 |
z0 |
q0 |
q0 |
q0 |
q0 |
z1 |
q1 |
q2 |
q3 |
q3 |
|
q0 |
q1 |
q2 |
q3 |
z0 |
y0 |
y0 |
y0 |
y0 |
z1 |
y0 |
y0 |
y0 |
y1 |
Graf automatu Mealy'ego:
z1,y0 z1,y0 z1,y0 z1,y1
z0,y0 z0,y0
z0,y0
z0,y0
B) Sekwencje nie mogą zachodzić na siebie:
a) Realizacja automatu Moore'a:
z1
z1 z1 z1
y1 y0 y0 y0
z0 z0
z1 z0
z0
y0
z0
z0=0
z1=1
Tablica przejść automatu Moore`a:
WY |
y0 |
y0 |
y0 |
y0 |
y1 |
WE\stany |
q0 |
q1 |
q2 |
q3 |
q4 |
z0 |
q0 |
q0 |
q0 |
q0 |
q0 |
z1 |
q1 |
q2 |
q3 |
q4 |
q1 |
b) Realizacja automatu Mealy'ego:
Tablica przejść: Tablica wyjść:
|
q0 |
q1 |
q2 |
q3 |
q4 |
z0 |
q0 |
q0 |
q0 |
q0 |
q0 |
z1 |
q1 |
q2 |
q3 |
q4 |
q1 |
|
q0 |
q1 |
q2 |
q3 |
q4 |
z0 |
y0 |
y0 |
y0 |
y0 |
y0 |
z1 |
y0 |
y0 |
y0 |
y1 |
y0 |
Po minimalizacji:
Tablica przejść: Tablica wyjść:
|
q0 |
q1 |
q2 |
q3 |
z0 |
q0 |
q0 |
q0 |
q0 |
z1 |
q1 |
q2 |
q3 |
q0 |
|
q0 |
q1 |
q2 |
q3 |
z0 |
y0 |
y0 |
y0 |
y0 |
z1 |
y0 |
y0 |
y0 |
y1 |
Graf automatu Mealy'ego:
z1,y0 z1,y0 z1,y0
z0,y0 z0,y0
z0,y0
z0,y0
z1,y1
a) Synteza strukturalna detektora w wersji Moore'a:
Kodowanie sygnałów:
z0 |
0 |
z1 |
1 |
y0 |
0 |
y1 |
1 |
|
Q1 |
Q2 |
Q3 |
Y |
q0 |
0 |
0 |
0 |
0 |
q1 |
0 |
0 |
1 |
0 |
q2 |
0 |
1 |
0 |
0 |
q3 |
0 |
1 |
1 |
0 |
q4 |
1 |
0 |
0 |
1 |
Q2 Q3 |
|
|
|
|
Q1 |
00 |
01 |
11 |
10 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
- |
- |
- |
Y = Q1
Zakodowana tablica automatu:
|
Q1 |
Q2 |
Q3 |
Q1 |
Q2 |
Q3 |
|
z0
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
z1
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
Minimalizacja siatkami Karnaugh'a:
Q2Q3 |
|
|
|
|
zQ1 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
- |
- |
- |
- |
11 |
- |
- |
- |
- |
10 |
- |
0 |
1 |
0 |
Q2Q3 |
|
|
|
|
zQ1 |
00 |
01 |
11 |
10 |
00 |
- |
- |
- |
- |
01 |
1 |
- |
- |
- |
11 |
0 |
- |
- |
- |
10 |
- |
- |
- |
- |
J = z*Q2*Q3 K = z'
Q2Q3 |
|
|
|
|
zQ1 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
- |
- |
01 |
0 |
- |
- |
- |
11 |
0 |
- |
- |
- |
10 |
0 |
1 |
- |
- |
Q2Q3 |
|
|
|
|
zQ1 |
00 |
01 |
11 |
10 |
00 |
- |
- |
1 |
1 |
01 |
- |
- |
- |
- |
11 |
- |
- |
- |
- |
10 |
- |
- |
1 |
0 |
J = z'*Q3 K = z + Q3
Q2Q3 |
|
|
|
|
zQ1 |
00 |
01 |
11 |
10 |
00 |
0 |
- |
- |
0 |
01 |
0 |
- |
- |
- |
11 |
0 |
- |
- |
- |
10 |
1 |
- |
- |
1 |
Q2Q3 |
|
|
|
|
zQ1 |
00 |
01 |
11 |
10 |
00 |
- |
1 |
1 |
- |
01 |
- |
- |
- |
- |
11 |
- |
- |
- |
- |
10 |
- |
1 |
1 |
- |
J = z1*Q1' K = 1
Schemat układu:
b) Synteza strukturalna detektora w wersji Mealy'ego:
Kodowanie sygnałów:
z0 |
0 |
z1 |
1 |
y0 |
0 |
y1 |
1 |
|
Q1 |
Q2 |
q0 |
0 |
0 |
q1 |
0 |
1 |
q2 |
1 |
0 |
q3 |
1 |
1 |
Zakodowana tablica automatu:
|
Q1 |
Q2 |
Q1 |
Q2 |
|
z0
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
z1
|
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
Minimalizacja siatkami Karnaugh'a:
Q1Q2 |
|
|
|
|
z |
00 |
01 |
11 |
10 |
0 |
0 |
0 |
- |
- |
1 |
0 |
1 |
- |
- |
Q1Q2 |
|
|
|
|
z |
00 |
01 |
11 |
10 |
0 |
- |
- |
1 |
1 |
1 |
- |
- |
0 |
0 |
J = z*Q2 K = z'
Q1Q2 |
|
|
|
|
z |
00 |
01 |
11 |
10 |
0 |
0 |
- |
- |
0 |
1 |
1 |
- |
- |
1 |
Q1Q2 |
|
|
|
|
z |
00 |
01 |
11 |
10 |
0 |
- |
1 |
1 |
- |
1 |
- |
1 |
0 |
- |
J = z K = z' + Q1'
Schemat układu:
Zaprojektować automat pokazujący resztę z dzielenia przez 4
Realizacja automatu Moore'a:
Alfabet wejściowy:
z= {z0, z1} z0 = 0, z1 = 1
Alfabet wyjściowy:
Y = {y0, y1, y2, y3}
y0 - reszta „0”, y1 - reszta „1”, y2 - reszta „2”, y3 - reszta „3”,
y0 y1 y3
z1 z1 z1
z0
z0
z0 z1 z0
y2
Uwagi i wnioski:
W pierwszym punkcie zaprojektowaliśmy detektor sekwencji „1111”. Do zrealizowania detektora podanej sekwencji niezbędny jest graf jego przejść, po zaprojektowaniu takiego odczytujemy z grafu jego tabelę przejść. Kolejnym punktem do zrealizowania była synteza strukturalna. Naszym zadaniem było zrealizowanie automatu za pomocą bramek i przerzutników, wybraliśmy przerzutniki typu JK. Zakodowaliśmy sygnały, stany i wyjścia automatu, następnie przy pomocy zakodowanych sygnałów powstała tabela, w której stany Q1,Q2,Q3 (Q1,Q2 - Mealy) oznaczają wyjścia przerzutników po podaniu zakodowanych sygnałów. Następnie w wyniku przeprowadzonej minimalizacji funkcji otrzymaliśmy pewien układ kombinacyjny złożony z bramek i trzech (dwoch - Mealy) przerzutników.
Ostatnim podpunktem była realizacja automatu pokazującego resztę z dzielenia przez 4. Zrealizowaliśmy graf przejść jednak nie udało nam się zrealizować tego ćwiczenia.
7
q0
q1
q2
q3
q4
q0
q1
q3
q2
q4
q3
q2
q1
q0
q3
q2
q1
q0
q0
q1
q2
q3