Piotr Kawalec

Wykład IX - 1

Wykład IX

Tworzenie i minimalizacja

tablic przejść- wyjść

Technika cyfrowa

Piotr Kawalec

Wykład IX - 2

Technika cyfrowa

Przykłady tworzenia tablic przejść -

wyjść



Przykład 2 -

zbudować tablicę przejść - wyjść

układu

wykrywającego w dowolnie długim ciągu

binarnym

sekwencje

1100



Przykład 3 -

Na wejście układu podawane są

kolejno

bit po bicie trzybitowe ciągi o wartościach od

0 do 5.

Na wyjściu ma się pojawić 1 gdy kolejny ciąg

zawiera

nieparzystą liczbę jedynek

Piotr Kawalec

Wykład IX - 3

Technika cyfrowa

Zamiana tablic przejść - wyjść
automatu Mealy’ego w tablice
automatu Moore’a



Każdej parze stanów

(s

i

, y

k

)

wpisanych w

klatki
tablicy Mealy’ego przyporządkowujemy stan

z

j

automatu Moore’a, przy czym jednakowym

parom
stanów powinny odpowiadać te same stany

z

j

.



Tworzymy tablicę przejść - wyjść automatu

Moore’a,
przypisując każdemu stanowi

z

j

sygnał

y

k

z

pary

(s

i

, y

k

)

. Stany następne dla każdego

x

przypisujemy

stanowi

z

j

takie, jakie miał stan

s

i

z tejże pary.

Piotr Kawalec

Wykład IX - 4

Technika cyfrowa

Zamiana tablic przejść - wyjść
automatu Moore’a w tablice
automatu Mealy’ego



Zapisujemy w klatce tablicy przejść automatu

Moore’a, w której występował stan następny

s

i

,

wartości wyjścia

y

k

odpowiadające temu

stanowi.



Po utworzeniu tablicy przejść - wyjść

automatu

Mealy’ego usuwamy kolumnę wyjść.

Piotr Kawalec

Wykład IX - 5

Technika cyfrowa

Minimalizacja tablic przejść - wyjść



zbudowane tablice przejść - wyjść zwykle nie

mają
minimalnej liczby wierszy (stanów)



ponieważ od liczby stanów zależy wymagana

wielkość pamięci, to układy zawierające
minimalną
liczbę stanów wewnętrznych będą prostsze i
tańsze



Proces minimalizacji liczby stanów

wewnętrznych
polega na zastępowaniu dwóch lub więcej
wierszy
w tablicy przejść - wyjść jednym wierszem,
bez
zmiany sposobu działania układu

Piotr Kawalec

Wykład IX - 6

Technika cyfrowa

Podstawowe pojęcia



Dwa stany następne

stanów s

i

, s

j

są

niesprzeczne

jeśli są one jednakowe lub co najmniej jeden

z nich jest nieokreślony (np.

s

k

i

s

k

;

s

k

i

--

;

--

i

--

)



Dwa stany wyjścia y i y’ są

niesprzeczne

,gdy

odpowiadające im sygnały są parami

identyczne

lub co najmniej jeden z nich jest

nieokreślony

(

0

i

0

;

1

i

1

;

0

i

--

;

1

i

--

;

--

i

--

)

Piotr Kawalec

Wykład IX - 7

Technika cyfrowa

Podstawowe pojęcia cd



Stany s

i

i s

j

są

zgodne

, jeżeli dla każdego

ciągu

liter wejściowych

x

stosowalnego zarówno

dla s

i

jak i

s

j

,

stany końcowe wygenerowanych

ciągów

wyjściowych są niesprzeczne



Dwa stany wewnętrzne

s

i

i

s

j

są

zgodne

,

jeżeli



sygnały wyjściowe odpowiadające tym

stanom

są niesprzeczne



stany następne są niesprzeczne lub

zgodne

Piotr Kawalec

Wykład IX - 8

Technika cyfrowa

Przykład minimalizacji tablic przejść-

wyjść



zminimalizować tablicę automatu

x

s

x

1

x

2

x

3

x

4

y

1

y

2

1

5

5

–

1

0 1

2

–

2

2

–

0 –

3

5

–

–

4

1 –

4

5

–

–

4

– 1

5

1

2

3

4

1 1

stany 1 i 4 są zgodne

;

stany 2 i 4 zgodne

;

stany

3 i 4 zgodne

Piotr Kawalec

Wykład IX - 9

Technika cyfrowa

Minimalizacja liczby stanów
wewnętrznych metodą par (trójkątną
tablicą zgodności)



buduje się tablicę trójkątną



klatkę o współrzędnych (i, j) wykreśla się

jeżeli stany

s

i

i s

j

mają sprzeczne wyjścia

 gdy zgodność pary stanów

s

i

i

s

j

jest

warunkowana

zgodnością

innej pary

s

k

i

s

l

to indeksy

k,l

wpisujemy

do klatki o współrzędnych

(i,j)

. Nie wpisuje się

indeksów pary stanów warunkujących

zgodność

samej siebie

Piotr Kawalec

Wykład IX - 10

Technika cyfrowa

Minimalizacja liczby stanów
wewnętrznych metodą par (trójkątną
tablicą zgodności) cd



wpisuje się warunki i wykreśla wszystkie

klatki

o sprzecznych wyjściach



następnie wykreśla się te wszystkie klatki, w

których

jako jeden z warunków występuje para

indeksów

odpowiadająca klatce wykreślonej na

poprzednim

etapie

 klatki niewykreślone, bez względu na

zawartość,

odpowiadają parom stanów zgodnych

Piotr Kawalec

Wykład IX - 11

Technika cyfrowa

Wyznaczanie maksymalnych grup
stanów zgodnych



dla automatu zupełnego wszystkie stany

parami

zgodne można zastąpić jednym stanem



dla automatu niezupełnego na podstawie

tablicy

trójkątnej tworzony jest zbiór (klasa)

maksymalnych

grup stanów zgodnych (grup w których

wszystkie

stany są parami zgodne)

 zbiór maksymalnych grup stanów zgodnych

oznaczamy



Piotr Kawalec

Wykład IX - 12

Technika cyfrowa

Wyznaczanie zbioru maksymalnych
grup stanów zgodnych





z grafu relacji zgodności



tworzymy graf relacji zgodności łącząc ze

sobą

stany odpowiadające parom indeksów

opisujących

niewykreślone klatki tablicy trójkątnej



wychodząc z każdego

stanu tworzymy

maksymalne grupy stanów zgodnych

zawierające

wszystkie stany połączone każdy z każdym



tworzymy zbiór



Piotr Kawalec

Wykład IX - 13

Technika cyfrowa



z tablicy trójkątnej



wybieramy kolumnę o najwyższym

numerze w

której nie wszystkie klatki są wykreślone i

dla niej

wypisujemy zbiory par indeksów

niewykreślonych klatek



jeśli dla kolejnej kolumny w zbiorze wierszy

o niewykreślonych klatkach mieszczą się

utworzone poprzednio zbiory, to

rozszerzamy

je o numer rozpatrywanej kolumny

Piotr Kawalec

Wykład IX - 14

Technika cyfrowa



z tablicy trójkątnej cd



pozostałe niewykreślone klatki kolumny

opisuje

się zbiorami par indeksów



czynności te powtarza się dla wszystkich

dalszych kolumn, analizując możliwość

rozszerzenia dowolnego z wcześniej

wypisanych zbiorów lub ich podzbiorów


postępowanie to kończymy wypisaniem

zbioru

maksymalnych grup stanów zgodnych

zawierającego wszystkie stany automatu

Piotr Kawalec

Wykład IX - 15

Technika cyfrowa

Wyznaczanie optymalnego zbioru
maksymalnych grup stanów zgodnych



opt



dla automatów zupełnych automat

wyznaczony na
podstawie maksymalnych grup stanów
zgodnych jest
minimalny



dla automatów niezupełnych można

wyznaczyć

optymalny zbiór grup zgodnych



opt

zawierający
mniejszą liczbę grup

Piotr Kawalec

Wykład IX - 16

Technika cyfrowa

Wyznaczanie optymalnego zbioru
maksymalnych grup stanów
zgodnych



opt



szukany zbiór grup zgodnych musi spełniać

warunki:

 każdy stan musi wchodzić co najmniej do

jednej grupy

(warunek pełności zbioru)



dla każdej pary każdego zbioru muszą być

spełnione wymogi zgodności warunkowej

Piotr Kawalec

Wykład IX - 17

Technika cyfrowa

Przykłady minimalizacji liczby
stanów wewnętrznych (trójkątną
tablicą zgodności)



Przykład 1 zminimalizować tablicę automatu

x

s

x

1

x

2

x

3

x

4

y

1

y

2

1

5

5

–

1

0 1

2

–

2

2

–

0 –

3

5

–

–

4

1 –

4

5

–

–

4

– 1

5

1

2

3

4

1 1

Piotr Kawalec

Wykład IX - 18

Technika cyfrowa



tablica trójkątna

Piotr Kawalec

Wykład IX - 19

Technika cyfrowa



graf zgodności

1

2

3

4

5



wyznaczanie zbioru

 i 

opt



= {{1,4}; {2,4}; {3,4}; {5}}



opt

= {{1,4}; {2}; {3};{5}}

Piotr Kawalec

Wykład IX - 20

Technika cyfrowa



minimalna tablica przejść - wyjść

x

s

x

1

x

2

x

3

x

4

y

1

y

2

{1,4}

1

4

4

–

1

0 1

{2}

2

–

2

2

–

0 –

{3}

3

4

–

–

1

1 –

{5}

4

1

2

3

1

1 1