Technika cyfrowa
Wykład X
Zamiana i minimalizacja
tablic przejść- wyjść
Piotr Kawalec Wykład X - 1
Technika cyfrowa
Plan wykładu
Zamiana tablic przejść-wyjść
automatu jednego rodzaju w tablice
automatu drugiego rodzaju
Minimalizacja tablic przejść-wyjść
podstawowe pojęcia
minimalizacja metodą zgodności par
przykład minimalizacji
Piotr Kawalec Wykład X - 2
Technika cyfrowa
Zamiana tablic przejść - wyjść automatu
Mealy ego w tablice automatu Moore a
Każdej parze stanów (si, yk) wpisanych w klatki
tablicy Mealy ego przyporządkowujemy stan zj
automatu Moore a, przy czym jednakowym parom
stanów powinny odpowiadać te same stany zj.
Tworzymy tablicę przejść - wyjść automatu Moore a,
przypisując każdemu stanowi zj sygnał yk z pary
(si, yk). Stany następne dla każdego x przypisujemy
stanowi zj takie, jakie miał stan si z tejże pary.
Piotr Kawalec Wykład X - 3
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 si,
wartości wyjścia yk odpowiadające temu stanowi.
Po utworzeniu tablicy przejść - wyjść automatu
Mealy ego usuwamy kolumnę wyjść.
Piotr Kawalec Wykład X - 4
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 X - 5
Technika cyfrowa
Podstawowe pojęcia
Dwa stany następne stanów si , sj są niesprzeczne
jeśli są one jednakowe lub co najmniej jeden
z nich jest nieokreślony (np. sk i sk; sk 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 X - 6
Technika cyfrowa
Podstawowe pojęcia cd
Stany si i sj są zgodne, jeżeli dla każdego ciągu
liter wejściowych x stosowalnego zarówno dla si
jak i sj, stany końcowe wygenerowanych ciągów
wyjściowych są niesprzeczne
Dwa stany wewnętrzne si i sj 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 X - 7
Technika cyfrowa
Przykład minimalizacji tablic przejść-wyjść
zminimalizować tablicę automatu
x
x1 x2 x3 x4 y1 y2
s
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 X - 8
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
si i sj mają sprzeczne wyjścia
gdy zgodność pary stanów si i sj jest warunkowana
zgodnością innej pary sk i sl 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 X - 9
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 X - 10
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 X - 11
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 X - 12
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 X - 13
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 X - 14
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 X - 15
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 X - 16
Technika cyfrowa
Przykłady minimalizacji liczby stanów
wewnętrznych (trójkątną tablicą zgodności)
Przykład 1 zminimalizować tablicę automatu
x
x1 x2 x3 x4 y1 y2
s
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 X - 17
Technika cyfrowa
tablica trójkątna
22,5
3
4
51,5 1,5
1234
Piotr Kawalec Wykład X - 18
Technika cyfrowa
graf zgodności
1
2
3
5
4
wyznaczanie zbioru Ś i Śopt
Ś = {{1,4}; {2,4}; {3,4}; {5}}
Śopt = {{1,4}; {2}; {3};{5}}
Piotr Kawalec Wykład X - 19
Technika cyfrowa
minimalna tablica przejść - wyjść
x
x1 x2 x3 x4 y1 y2
s
{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
Piotr Kawalec Wykład X - 20
Technika cyfrowa
Przykłady minimalizacji liczby stanów
wewnętrznych (trójkątną tablicą zgodności)
Przykład 2 zminimalizować tablicę automatu
x
x1 x2 x3 x4 x1 x2 x3 x4
s
1 5 5   0 1  
2  5 3 6  0 0 1
3  1 2 4  1 1 1
4 2    0   
5 1  4 1 0  0 0
6   4    1 
s y
Piotr Kawalec Wykład X - 21
Technika cyfrowa
tablica trójkątna
2
1,5
3
2,5
4
1,2
5
2,4
6
12345
Piotr Kawalec Wykład X - 22
Technika cyfrowa
wyznaczanie zbioru Ś z tablicy trójkątnej
4 {4,6}
3 {3,4,6}
2 {2,4}
1 {1,3,6}; {1,5}
Ś = {{1,3,6}; {2, 4}; {3,4,6}; {1, 5}}
wyznaczanie zbioru Śopt
Śopt = {{3, 6}; {2, 4}; {1, 5}}
Piotr Kawalec Wykład X - 23
Technika cyfrowa
minimalna tablica przejść - wyjść
x
x1 x2 x3 x4 x1 x2 x3 x4
s
{1,5} 1 1 1 2 1 0 1 0 0
{2,4} 2 2 1 3 3 0 0 0 1
{3,6} 3  1 2 2  1 1 1
Piotr Kawalec Wykład X - 24