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

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie z dwoma podstawowymi kategoriami automatów oraz metodami transformacji automatu Moore'a w automat Mealy i odwrotnie.

2. Program ćwiczenia:

1. Zaprojektować detektor sekwencji 1111

A) Sekwencje mogą zachodzić na siebie:

a) Realizacja automatu Moore'a:

z₁ z₁ z₁ z₁

y₁ y₀ y₀ y₀

z₀ z₀

z₁ z₀

z₀

y₀

z₀

z₀=0

z₁=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:

z₁,y₀ z₁,y₀ z₁,y₀ z₁,y₁

z₀,y₀ z₀,y₀

z₀,y₀

z₀,y₀

B) Sekwencje nie mogą zachodzić na siebie:

a) Realizacja automatu Moore'a:

z₁

z₁ z₁ z₁

y₁ y₀ y₀ y₀

z₀ z₀

z₁ z₀

z₀

y₀

z₀

z₀=0

z₁=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:

z₁,y₀ z₁,y₀ z₁,y₀

z₀,y₀ z₀,y₀

z₀,y₀

z₀,y₀

z₁,y₁

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 = Q₁

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_*Q_2*Q₃ 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'_*Q₃ K = z + Q₃

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 = z_1*Q₁' 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_*Q₂ 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' + Q₁'

Schemat układu:

2. Zaprojektować automat pokazujący resztę z dzielenia przez 4

Realizacja automatu Moore'a:

Alfabet wejściowy:

z= {z₀, z₁} z₀ = 0, z₁ = 1

Alfabet wyjściowy:

Y = {y₀, y₁, y₂, y₃}

y₀ - reszta „0”, y₁ - reszta „1”, y₂ - reszta „2”, y₃ - reszta „3”,

y₀ y₁ y₃

z₁ z₁ z₁

z₀

z₀

z₀ z₁ z₀

y₂

3. 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 Q₁,Q₂,Q₃ (Q₁,Q₂ - 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

q₀

q₁

q₂

q₃

q₄

q₀

q₁

q₃

q₂

q₄

q₃

q₂

q₁

q₀

q₃

q₂

q₁

q₀

q₀

q₁

q₂

q₃

---