nfdsksdja fnkjfdsa lkfds dfns jfdsa lkj fdn lkfdsaj PDF

Preview

Summary

nfdsksdja fnkjfdsa lkfd sns jfdsa lkj fdn lkfdsajsns jfdsa lkj fdn lkfdsajsns jfdsa lkj fdn lkfdsajsns jfdsa lkj fdn lkfdsfdsa lkj fdn lkfdsajsns jfdsa lkj fdn lkfdsajsns jfdsa lkj fdn lkfdsajsns jfdsa lkj fdn lkfdsaj...

Description

Logika Układów Cyfrowych Ćwiczenie 207

R

Termin: wtorek 16:15 Prowadzący: mgr inż. Antoni Sterna

Spis treści 1 Zadania

2

2 Przebieg ćwiczenia 3 2.1 Automat sprawdzający, czy w ciągu symboli 0/1 ostatni symbol jest taki sam jak pierwszy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Na wejście automatu wprowadzane są ciągi zawierające symbole 0/1. Po wykryciu jednej jedynki zmiana wyjścia automatu 0 → 1, po wykryciu sekwencji 000 zmiana wyjścia 1 → 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Wnioski

15

1

1

Zadania 1. Automat sprawdzający, czy w ciągu symboli 0/1 ostatni symbol jest taki sam jak pierwszy. 2. Na wejście automatu wprowadzane są ciągi zawierające symbole 0/1. Po wykryciu jednej jedynki zmiana wyjścia automatu 0 → 1, po wykryciu sekwencji 000 zmiana wyjścia 1 → 0.

Dla obu zadań przygotować automaty w wariantach: Mealy i Moore’a (grafy, funkcje przejść i wyjść). Dla zadania pierwszego wykonać również syntezę strukturalną obu wersji (schematy do sprawdzenia w symulacji).

2

2 2.1

Przebieg ćwiczenia Automat sprawdzający, czy w ciągu symboli 0/1 ostatni symbol jest taki sam jak pierwszy

Automat sprawdzający, czy w ciągu symboli 0/1 ostatni symbol jest taki sam jak pierwszy może zostać przedstawiony jako automat Moore’a lub Mealy’ego o pięciu stanach (Rys. 1, Rys. 2). y0 q0 z0

z1

z1 y1

q2

z0

z1

y0

q1

z0

z0

z1

q4

q3

z0

z1

Rysunek 1: Graf automatu Moore’a

3

y1

y0

q0 z1/y1

z0 /y1

z1/y1 q2

z 0/y0

z0/y1

z 1/y1

q1

z0/y0

z1/y0

q4

q3

z0/y0

z1/y0

Rysunek 2: Graf automatu Mealy’ego W przedstawionych automatach występują dwa sygnały wejściowe i wyjściowe, dlatego do zakodowania ich wystarczy jeden bit. Kodowanie sygnałów wejściowych i wyjściowych zostało przedstawione odpowiednio w Tabelach 1 oraz 2.

z0 z1

Z 0 1

y0 y1

Tablica 1: Zakodowane sygnały wejściowe

Y 0 1

Tablica 2: Zakodowane sygnały wyjściowe

Do zakodowania czterech stanów potrzebne są trzy przerzutniki Q2 , Q1 i Q0 . Kodowanie stanów przedstawiono w Tabeli 3.

q0 q1 q2 q3 q4

Q2 0 0 0 0 1

Q1 0 0 1 1 0

Q0 0 1 0 1 0

Tablica 3: Zakodowane stany

4

Q2 0 0 0 0 0 0 0 0 1 1

t Q1 0 0 0 0 1 1 1 1 0 0

Q0 0 0 1 1 0 0 1 1 0 0

Z 0 1 0 1 0 1 0 1 0 1

Q2 0 0 0 0 1 0 0 0 1 0

t+1 Q1 Q0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0

D2

D1

D0

0 0 0 0 1 0 0 0 1 0

0 1 0 1 0 1 0 1 0 1

1 0 1 1 0 0 1 1 0 0

Tablica 4: Pobudzenia dla wejść przerzutników typu D Następnie wykonana została minimalizacja funkcji dla D2 , D1 i D0 za pomocą siatek Karnaugha (Rys. 3, Rys. 4, Rys. 5). Q0 Z 00

01

11

10

00

0

0

0

0

01

1

0

0

0

11

X

X

X

X

10

1

0

X

X

Q2 Q1

Q0 Z 00

01

11

10

00

0

1

1

0

01

0

1

1

0

11

X

X

X

X

10

0

1

X

X

Q2 Q1

Rysunek 3: D2 D2 = Z · Q0 · Q1 + Z · Q2 =

Rysunek 4: D1

= Z(Q0 · Q1 · Q2 ) = D1 = Z

= Z + Q0 · Q1 · Q2 = = Z + Q0 · Q1 + Q2 = = Z + Q0 + Q1 + Q2

5

Q0 Z 00

01

11

10

00

1

0

1

1

01

0

0

1

1

11

X

X

X

X

10

0

0

X

X

Q2 Q1

Rysunek 5: D0

D0 = Z · Q1 · Q2 + Q0 = = Z · Q1 · Q2 + Q0 = = D0 = Z · Q1 · Q2 · Q0 Przedstawione automaty różnią się sposobem generacji liter alfabetu wyjściowego. W automacie Moore’a litera generowana na wyjściu zależy wyłącznie od aktualnego stanu, natomiast w automacie Mealy’ego wyjście uzależnione jest zarówno od stanu, w jakim została podana litera alfabetu wejściowego, jak i samej tej litery. Ze względu na te różnice dla obu automatów należy przeprowadzić osobną syntezę funkcji wyjść.

Q2 0 0 0 0 1

Q1 0 0 1 1 0

Q0 0 1 0 1 0

Q2 0 0 0 0 0 0 0 0 1 1

Y 0 1 1 0 0

Tablica 5: Tabela wyjść dla automatu Moore’a

Q1 0 0 0 0 1 1 1 1 0 0

Q0 0 0 1 1 0 0 1 1 0 0

Z 0 1 0 1 0 1 0 1 0 1

Y 1 1 1 0 0 1 1 0 0 1

Tablica 6: Tabela wyjść dla automatu Mealy’ego

6

Q0 Z 00

01

11

10

00

1

1

0

1

Q2 Q1 Q1 Q0 00

01

11

10

01

0

1

0

1

0

0

1

0

1

11

X

X

X

X

1

0

X

X

X

10

0

1

X

X

Q2

Rysunek 6: Y dla automatu Moore’a

Rysunek 7: Y dla automatu Mealy’ego

Y = Q0 · Q1 + Q0 · Q1 =

Y = Q0 · Q1 · Q2 + Z · Q0 + Z · Q0 =

= Q0 ⊕ Q1

= Q0 · Q1 · Q2 + Z ⊕ Q0 = = Q0 · Q1 · Q2 + Z ⊕ Q0 = = Q0 · Q1 · Q2 · Z ⊕ Q0

7

Rysunek 8: Schemat układu dla automatu Moore’a

8

Rysunek 9: Schemat układu dla automatu Mealy’ego Rysunki 8 i 9 przedstawiają wykonane w programie Logisim schematy układów, które zaprojektowano z użyciem przerzutników typu D. Działanie obu układów zostało sprawdzone w trakcie zajęć i nie wykryto błędów, zwrócono natomiast uwagę na możliwość zminimalizowania grafu automatu Mealy’ego (Rys. 2). Proces ten przedstawiono w Tabelach 7, 8 oraz 9. z q 0 1 2 3 4

0

1

1,1 1,1 4,0 1,1 4,0

2,1 3,0 2,1 3,0 2,1

Tablica 7

z q (1,3)

0 1 2 4

0 1,1 1,1 4,0 4,0

1

z q

2,1 1,0 2,1 2,1

(1,3) (2,4)

0 1 2

0

1

1,1 1,1 2,0

2,1 1,0 2,1

Tablica 9

Tablica 8

9

Powstały w ten sposób automat można przedstawić za pomocą tylko trzech stanów (Rys. 10), dzięki czemu liczba przerzutników potrzebnych do zakodowania ich zmniejszyła się do dwóch. Dalsza synteza automatu została wykonana analogicznie do poprzednio opisanego przykładu. q0

z1 /y1

z0 /y1

z1 /y1 q2

q1

z0 /y1

z1 /y0

z0 /y0

Rysunek 10: Graf automatu Mealy’ego z minimalną liczbą stanów

t Q1 0 0 0 0 1 1

Q0 0 0 1 1 0 0

Z 0 1 0 1 0 1

t+1 Q1 Q0 0 1 1 0 0 1 0 1 1 0 1 0

D1

D0

0 1 0 0 1 1

1 0 1 1 0 0

Tablica 10: Pobudzenia wejść dla przerzutników typu D

10

Z

Z

0

1

00

1

0

0

01

1

1

X

X

11

X

X

1

1

10

0

0

0

1

00

0

1

01

0

11 10

Q1 Q0

Q1 Q0

Rysunek 11: D1

Rysunek 12: D0

D1 = Z · Q0 + Q1 =

D0 = Z · Q1 + Q0 = = (Z · Q1 ) · Q0

= (Z · Q0 ) · Q1

Q1 0 0 0 0 1 1

Q0 0 0 1 1 0 0

Z 0 1 0 1 0 1

Y 1 1 1 0 0 1

Tablica 11: Tabela wyjść Obszar zielony na rys. 13 jest zbędny. Z 0

1

00

1

1

01

1

0

11

X

X

10

0

1

Q1 Q0

Rysunek 13: Y

11

Y = Z · neQ1 + Q0 · Q1 · +Z · Q0 = = Z · Q1 + Q0 · (Q1 + Z) = = Z · Q1 + (Q0 · (Q1 · Z)) = = (Z · Q1 ) + (Q0 + (Q1 · Z)) = = (Z · Q1 ) · (Q0 + (Q1 + Z)) = = (Z · Q1 ) · (Q0 · (Q1 + Z)) = = (Z · Q1 ) · (Q0 · (Q1 · Z ))

Rysunek 14: Schematu układu Projekt zminimalizowanego automatu Mealy’ego został zrealizowany poza zajęciami, jednak sprawdzany w symulatorze działał poprawnie.

12

2.2

Na wejście automatu wprowadzane są ciągi zawierające symbole 0/1. Po wykryciu jednej jedynki zmiana wyjścia automatu 0 → 1, po wykryciu sekwencji 000 zmiana wyjścia 1 → 0

Zadany automat można przedstawić za pomocą automatu Moore’a lub Mealy’ego o czterech stanach (Rys. 15, Rys. 16). y1

z1

z0

q1

y0

y1

z1

q0

q2 z0

z1 z0 z1

q3

y1

z0 Rysunek 15: Graf automatu Moore’a

z1 /y1 z0 /y1

q1 z0 /y0 q0

z1 /y1

z1 /y1 q2

z1 /y1

z0 /y1

z0 /y0 q3 Rysunek 16: Graf automatu Mealy’ego W Tabeli 12 przedstawione zostały funkcje przejść dla obu automatów. Ze względu na różnice w ich działaniu, podobnie jak w poprzednim zadaniu, funkcje wyjść zostały rozpatrzone osobno (Tab. 13, Tab. 14).

13

t qi q0 q0 q1 q1 q2 q2 q3 q3

zi z0 z1 z0 z1 z0 z1 z0 z1

t+1 qi q0 q1 q2 q1 q3 q1 q0 q1

Tablica 12: Funkcje przejść dla automatów Moore’a i Mealy’ego

q q0 q1 q2 q3

qi q0 q0 q1 q1 q2 q2 q3 q3

y y0 y1 y1 y1

Tablica 13: Funkcje wyjść dla automatu Moore’a

zi z0 z1 z0 z1 z0 z1 z0 z1

yi y0 y1 y1 y1 y1 y1 y0 y1

Tablica 14: Funkcje wyjść dla automatu Mealy’ego

14

3

Wnioski

Ze względu na specyfikę działania, automat Mealy’ego jest w stanie zrealizować to samo zadanie przy użyciu mniejszej ilości przerzutników, co pokazuje pierwszy z przerobionych przykładów. Warto zatem rozpocząć pracę od minimalizacji automatu w celu uzyskania możliwie najprostszego automatu.

15...