1 Podstawy Techniki CyfrowejWykład 8: Projektowanie synchronicznych układów sekwencyjnych Dr inż. Marek Mika Państwowa Wyższa Szkoła Zawodowa im. Jana Amosa Komeńskiego W Lesznie

2 Plan Minimalizacja automatu zasady przykłady

3 Minimalizacja automatuMinimalizacja automatu to minimalizacja liczby stanów, czyli transformacja automatu o danej tablicy przejść-wyjść na równoważny mu (pod względem przetwarzania sygnałów cyfrowych automat o mniejszej liczbie stanów wewnętrznych. Jest to często możliwe, ponieważ w pierwotnej specyfikacji często wprowadzane są stany nadmiarowe lub równoważne

4 Przykładowa minimalizacja automatuPierwotna specyfikacja definiowała 6 stanów i wymagała 3 przerzutników, a po minimalizacji liczba stanów zmalała do 3, a liczba wymaganych przerzutników do 2 Pytanie: Jak to zrobić? Przed minimalizacją Po minimalizacji

5 Proces minimalizacji liczby stanów

6 Zgodność stanów

7 Relacja zgodności Ze względu na zgodność warunkową (para zgodna warunkowo w dalszych obliczeniach może okazać się parą zgodną lub sprzeczną) w obliczeniach par zgodnych posługujemy się tzw. tablicą trójkątną Tablica trójkątna składa się z tylu komórek, ile jest wszystkich możliwych par stanów Na przykład dla automatu o 5 stanach …

8 Przykładowa tablica trójkątnaWypełnienie v – para zgodna x – para sprzeczna (i,j) – para (pary) stanów następnych, jeżeli para jest zgodna warunkowo

9 Wypełnianie tablicy trójkątnej – przykład

10 Wykreślanie stanów sprzecznychPo wypełnieniu tablicy trójkątnej sprawdza się, czy pary stanów sprzecznych nie występują jako pary stanów następnych. Jeśli tak, to te pary należy skreślić Proces ten powtarzany jest do momentu sprawdzenia wszystkich par sprzecznych Pozostałe (niewykreślone) komórki (bez względu na zawartość) odpowiadają parom zgodnym

11 Wyznaczanie MKZ Po wyznaczeniu zbioru par stanów zgodnych można przystąpić do obliczenia maksymalnych zbiorów stanów zgodnych, czyli Maksymalnych Klas Zgodności

12 Wyznaczanie MKZ - przykładStosując metodę bezpośrednią otrzymujemy

13 Algorytm minimalizacjiOkreślenie par stanów zgodnych Wyznaczenie maksymalnych zbiorów stanów zgodnych (MKZ) Selekcja zbiorów spełniających: warunek pokrycia – każdy stan musi wchodzić co najmniej do jednej klasy warunek zamknięcia – dla każdej litery wejściowej wszystkie następniki (stany następne) danej klasy muszą wchodzić do jednej klasy

14 Warunek pokrycia - przykład

15 Warunek zamknięcia - przykład

16 Warunek pokrycia i zamknięcia – druga próba

17 Przykład 2

18 Przykład 2 – cd. Wyznaczenie metodą bezpośrednią MKZ

19 Przykład 2 – cd.

20 Przykład 2 – cd.

21 Przykład 3 – synteza detektora sekwencji

22 Przykład 3 cd. – synteza detektora sekwencjiCelem etapu syntezy abstrakcyjnej jest zapisanie działania automatu w formie tablicy lub grafu przejść wyjść. Zazwyczaj konstruowanie grafu jest wygodniejsze.

23 Przykład 3 cd. – synteza detektora sekwencjiNa podstawie uzyskanego w ten sposób grafu automatu łatwo utworzyć odpowiednią tablicę przejść wyjść. Łatwo spostrzec, że w utworzonej tablicy stany i (zacienione na czerwono) są sobie równoważne i w takim razie można je zredukować do jednego stanu. W tej sytuacji upraszcza się zarówno tablica przejść wyjść automatu jak też jego graf.

24 Przykład 3 cd. – minimalizacja detektora sekwencji

25 Przykład 3 cd. – minimalizacja detektora sekwencji

26 Przykład 3 cd. – minimalizacja detektora sekwencji

27 Przykład 3 cd. – dalsze krokiDla tak uzyskanego automatu należy dokonać kodowania stanów a następnie wykonać syntezę kombinacyjną.

28 DziękujĘ ZA UWAGĘ