Wykonanie: Krakowian Konrad 140059 Rakowski Bartosz 140116

mgr inż. A. Sterna Poniedziałek, godz. 15.15 03.04.2006r.

Sprawozdanie nr 6

KOMPUTEROWA REALIZACJA AUTOMATÓW SKOŃCZONYCH

1. Cel ćwiczenia

Celem ćwiczenia jest praktyczne zapoznanie się ze sposobem programowej realizacji na komputerze lub mikrokomputerze automatów skończonych (na przykładzie automatów typu Moore'a).

2. Program ćwiczenia:

1. Zaprojektować zamek szyfrowy otwierający się na kombinację 1001

1. Przypadek, w którym nie wolno popełnić żadnego błędu aby otworzyć zamek szyfrowy:

y₀ y₀ y₀ y₀ y₁

z₁ z₀ z₀ z₁

z₀ z₁ z₁ z₀ z_0, z₁

y₀

z_0, z₁

Alfabet wejściowy:

Z = {z₀,z₁}

z₀ = 0

z₁ = 1

Alfabet wyjściowy:

Y = {y₀,y₁}

y₀ - zamknięte

y₁ - otwarte

Stany wewnętrzne:

Q = {q₀,q₁,q₂,q₃,q₄,q₅}

q₀ - stan początkowy

q₄ - stan zatrzymania automatu (po wprowadzeniu błędnego kodu)

Funkcja przejść:

G_i⁺ = ⁰(q₀¹(z₂q₁²(z₁q₂³(z₁q₃⁴(z₂q₅⁵(z₁q₄⁶(z₁q₄,z₂q₄)⁶,z₂q₄)⁵,z₁q₄)⁴,z₂q₄)³,

z₂q₄)²,z₁q₄)¹)⁰

Funkcja wyjść:

Q[t]	Y[t+1]
q0	y0
q1	y0
q2	y0
q3	y0
q4	y0
q5	y1

Symulacja komputerowa:

a) dla poprawnego słowa wejściowego:

x = 1001

x = {z₁,z₀,z₀,z₁}

Q[t]	x[t]	Q[t+1]	Y[t+1]
q0	z1	q1	y0
q1	z0	q2	y0
q2	z0	q3	y0
q3	z1	q4	y1

b) dla przykładowego błędnego słowa wejściowego

x = 1011

x = {z₁,z₀,z₁,z₁}

Q[t]	x[t]	Q[t+1]	Y[t+1]
q0	z1	q1	y0
q1	z0	q2	y0
q2	z1	q4	y0
q4	z1	q4	y0

2. Przypadek, w którym dopuszczalne jest popełnienie jednego błędu:

z₁

y₀ y₀ y₀ y₀ y₀ y₀ y₀ y₀ y₁

z₁ z₀ z₀ z₀ z₁ z₀ z₀ z₁

z₁

z₀ z₁ z₁ z₀ z_0,z₁

z₁

z₀

y₀

z₀ z₁

2. Zaprojektować generator U2:

z₀ z₀ z₁

z₀ z₀

y₀ y₁ y₀

z₀

Alfabet wejściowy:

Z = {z₀,z₁}

z₀ - 0 w NKB

z₁ - 1 w NKB

Alfabet wyjściowy:

Y = {y₀,y₁}

y₀ - 0 w U2

y₁ - 1 w U2

Stany wewnętrzne:

Q = {q₀,q₁,q₂}

q₀ - stan początkowy

Funkcja przejść:

G_i⁺ = ⁰(q₀¹(z₁q₁²(z₁q₂³(z_oq₁,z₁q₂)³,z₀q₁)²,z₀q₀)¹)⁰

Funkcja wyjść:

Q[t]	Y[t+1]
q0	Y0
q1	y1
q2	y0

Symulacja komputerowa:

x = 1001

x = {z₁,z₀,z₀,z₁}

Q[t]	x[t]	Q[t+1]	Y[t+1]
q0	z1	q1	y0
q1	z0	q1	y1
q1	z0	q1	y1
q1	z1	q2	y1

3. Zaprojektować subtraktor szeregowy:

Graf automatu Mealy'ego:

z₂,y₁ z₀,y₀

z₃,y₀

z₁,y₁ z₂,y₀

z₃,y₁

z₁,y₀ z₀,y₁

Przejście z automatu Mealy'ego na automat Moore'a:

Tablica przejść: Tablica wyjść:

	b0	b1
z0	b0	b1
z1	b1	b1
z2	b0	b0
z3	b0	b1

	b0	b1
z0	y0	y1
z1	y1	y0
z2	y1	y0
z3	y0	y1

	b0/q0	b1
z0	b0y0/q01	b1y1/q11
z1	b1y1/q02	b1y0/q12
z2	b0y1/q03	b0y0/q13
z3	b0y0/q04	b1y1/q14

Tablica przejść automatu Moore'a:

sygn. wyjść.	y1	y0	y1	y1	y0	y1	y0	y0	y1
	q0	q01	q02	q03	q04	q11	q12	q13	q14
z0	q01	q01	q11	q01	q01	q11	q11	q01	q11
z1	q02	q02	q12	q02	q02	q12	q12	q02	q12
z2	q03	q03	q13	q03	q03	q13	q13	q03	q13
z3	q04	q04	q14	q04	q04	q14	q14	q04	q14

q₀₃ = q₀

q₀₁ = q₀₄ = q₁₃ = q₁

q₀₂ = q₁₁ = q₁₄ = q₂

q₁₂ = q₃

Zminimalizowana tablica przejść automatu Moore'a:

sygn. wyjść.	y1	y0	y1	y0
	q0	q1	q2	q3
z0	q1	q1	q2	q2
z1	q2	q2	q3	q3
z2	q0	q0	q1	q1
z3	q1	q1	q2	q2

Graf automatu Moore'a:

z₂

y₁

z₀,z₃

z₁ z₁ z₂

z₀,z₃

y₀ z₂

y₀

z₀,z₃ z₂

z₁ z₁

y₁

z₀,z₃

Alfabet wejściowy:

Z = {z₀,z₁,z₂,z₃}

z₀ = 00

z₁ = 01

z₂ = 10

z₃ = 11

Alfabet wyjściowy:

Y = {y₀,y₁}

y₀ = 0

y₁ = 1

Stany wewnętrzne:

Q = {q₀,q₁,q₂,q₃}

q₀ - stan początkowy

Funkcja przejść:

G_i⁺ = ⁰(q₀¹(z₀q₁²(z₁q₂³(z₁q₃⁴(z₂q₁,z₀q₂,z₃q₂,z₁q₃)⁴,z₂q₁,z₀q₂,z₃q₂)³,z₂q₀, z₀q_1,

z₃q₁)²,z₃q₁,z₁q₂,z₂q₀)¹)⁰

Funkcja wyjść:

Q[t]	Y[t+1]
q0	y1
q1	y0
q2	y1
q3	y0

Symulacja komputerowa:

x = 111110 - 100101

x = {z₁,z₂,z₃,z₂,z₂,z₃}

Q[t]	x[t]	Q[t+1]	Y[t+1]
q0	z1	q2	y1
q2	z2	q1	y0
q1	z3	q1	y0
q1	z2	q0	y1
q0	z2	q0	y1
q0	z3	q1	y0

3. Uwagi i wnioski:

Symulacja komputerowa jest bardzo dobrym sposobem na testowanie poprawności układu na poziomie grafu. Dzięki niej możemy zauważyć i poprawić ewentualne błędy jeszcze w trakcie projektowania danego układu.

1

q₅

q₃

q₂

q₁

q₀

b₁

b₀

q₂

q₄

q₄

q₅

q₆

q₇

q₉

q₈

q₀

q₁

q₂

q₃

q₁

q₀

q₃

q₂

q₁

q₀

---