Przedstawione podejście do syntezy układów sekwencyjnych składa się z następujących czynności:
w zależności od możliwości architektury PLD, miejsca podsystemu w systemie cyfrowym, warunków realizacji ze względu na koszt i szybkość działania, cech układu sekwencyjnego dla każdego podsystemu wybierane są najbardziej pasujące modele automatów skończonych;
na podstawie cech wewnętrznych automatu skończonego i wybranych modeli określa się najbardziej pasującą metodę syntezy;
wykonuje się syntezę klas automatów skończonych odpowiednich modeli;
tworzy się zbiór funkcji Boolowskich części kombinacyjnej automatów skończonych wraz z jej minimalizacją (w razie konieczności);
wykonuje się syntezę zbioru funkcji Boolowskich jedną z metod syntezy układów kombinacyjnych na PLD;
w razie konieczności wykonuje się odwzorowanie układu logicznego na strukturę docelowego układu PLD.
Przedstawione niżej metody syntezy automatów skończonych na PLD posiadają następujące cechy:
szerokie wykorzystywanie możliwości architektur PLD:
wyjściowych przerzutników w charakterze elementów pamięci (automat klasy C);
przerzutników w pętlach sprzężeń zwrotnych w charakterze elementów pamięci (automat klasy D);
buforów wejściowych w charakterze elementów pamięci (automaty klas E i F);
makrokomórek z dwoma sprzężeniami zwrotnymi (automaty klas A i B na uniwersalnych układach PAL);
różna liczba linii iloczynu (termów) podłączonych do każdej makrokomórki (automaty klas A i B na uniwersalnych układach PAL).
szerokie zastosowanie operacji rozszczepienia stanów wewnętrznych automatu skończonego (dana operacja odnosi się do równoważnościowego przekształcenia automatu skończonego i nie zmienia algorytmu jego funkcjonowania):
do zbudowania automatu skończonego o najwyższej szybkości działania (automaty klas A i B);
do przekształcenia automatów skończonych Mealy’ego w automaty klasy D (rozszczepienie ze względu na wektory zmiennych wyjściowych);
do przekształcenia automatów skończonych Mealy’ego i Moore’a w automaty odpowiednio klas E i F (rozszczepienie ze względu na wektory zmiennych wejściowych);
wprowadzenie minimalnej ilości dodatkowych zmiennych wewnętrznych do odróżnienia kodów stanów wewnętrznych automatów skończonych różnych klas;
w zależności od możliwości architektury PLD jednoczesne umieszczenie różnych klas automatów skończonych w jednej strukturze automatu.
<w przygotowaniu>
Metoda A1 syntezy szybkich automatów skończonych klasy A (tradycyjny automat Mealy’ego) i klasy B (tradycyjny automat Moore’a) pozwala budować automaty o największej szybkości, gdzie częstotliwość przełączania elementów pamięci równa jest maksymalnej częstotliwości funkcjonowania układu PLD. Osiąga się to w ten sposób, że każda funkcja wzbudzenia elementów pamięci (funkcja przejścia) jest realizowana na jednej makrokomórce PLD. Do ograniczenia złożoności funkcji przejść stosuje się operację rozszczepienia stanów wewnętrznych w taki sposób, aby liczba przejść do każdego stanu nie przewyższała liczby termów, podłączonych do jednej makrokomórki PLD. W procesie kodowania stanów wewnętrznych kontroluje się złożoność funkcji przejść i w wypadku braku możliwości realizacji jakiejś funkcji przejścia na jednej makrokomórce PLD zwiększa się liczbę R bitów kodu stanów wewnętrznych.
Metoda A1 pozwala także efektywnie wykorzystać makrokomórki PLD z dwoma sprzężeniami zwrotnymi: jednocześnie do realizacji funkcji przejść i wprowadzania wartości funkcji wejściowych.
W obu metodach A1 i A2 syntezy automatów skończonych A i B przewiduje się możliwość programowania poziomu logicznego sygnałów wyjściowych PLD dla obniżenia kosztu realizacji.
Główną wadą metody A1 jest wąski obszar zastosowania z powodu rozchodzenia się ( dążenia do nieskończoności) algorytmu rozszczepienia stanów wewnętrznych.
Metoda A2 syntezy złożonych automatów skończonych klas A i B pozwala budować na PLD automaty praktycznie o nieograniczonej złożoności, jednak nie gwarantuje najwyższej szybkości działania automatu. Dla zwiększenia szybkości działania automatu skończonego w metodzie A2 rozszczepienie stanów wykonuje się dla ograniczenia liczby przejść tylko w „złe” stany, przy czym algorytm rozszczepienia nigdy nie rozchodzi się. W celu zmniejszenia złożoności realizacji (mierzonej liczbą wykorzystanych makrokomórek PLD) liczba R bitów kodu zmienia się od wartości intlog2M do М, gdzie M – liczba stanów wewnętrznych automatu skończonego. Następnie z otrzymanych rezultatów syntezy wybiera się najlepsze rozwiązanie ze względu na koszt i szybkość działania. Przy ocenie kosztów realizacji uwzględnia się różne sposoby przyporządkowywania termów makrokomórkom wyjściowym PLD.
W obu metodach A1 i A2 syntezy automatów skończonych A i B przewiduje się możliwość programowania poziomu logicznego sygnałów wyjściowych PLD dla obniżenia kosztu realizacji.
Główną cechą wyróżniającą metod A3 i A4 syntezy automatów skończonych klas C i D jest wykorzystanie przerzutników makrokomórek wyjściowych PLD w charakterze elementów pamięci automatu skończonego w przypadku, gdy wektory zmiennych wyjściowych mają identyczne wartości z częścią kodu stanów wewnętrznych. Pozwala to obniżyć koszt realizacji i jednocześnie zwiększyć szybkość działania automatów w porównaniu z automatami klas A i B.
Obniżenie kosztu realizacji uzyskuje się poprzez zmniejszenie liczby wykorzystywanych makrokomórek wyjściowych PLD, gdyż funkcje wyjściowe oraz część elementów pamięci automatu realizuje się na tych samych makrokomórkach PLD. Oprócz tego, upraszcza się część kombinacyjna automatu, ponieważ odpada konieczność realizacji części funkcji wzbudzeń elementów pamięci, które są identyczne z funkcjami wyjściowymi. Obniżenie kosztu realizacji jest tez spowodowane tym, że w charakterze kodów stanów wewnętrznych automatów klas C i D wykorzystuje się elementarne koniunkcje, a nie pełne koniunkcje, jak w automatach klas A i B.
Zwiększenie szybkości działania automatów skończonych klas C i D, w porównaniu z tradycyjnym podejściem, jest spowodowane tym, że w automatach klas C i D realizuje się przeważnie funkcje wyjściowe, które są zwykle prostsze niż funkcje przejść, co powoduje zmniejszenie liczby poziomów logicznych przy syntezie części kombinacyjnej automatu skończonego.
Kodowanie stanów wewnętrznych automatu klasy C prowadzi do zadania ortogonalizacji wierszy macierzy, które wykorzystuje się w charakterze kodów stanów wewnętrznych automatu. Przedstawiony algorytm pozwala minimalizować liczbę wartości znaczących w macierzy, co prowadzi do zmniejszenia liczby argumentów realizowanych funkcji.
Wadą metody A3 syntezy automatów skończonych klasy C jest to, że jest to automat Moore’a. Dlatego też, do przekształcenia automatu skończonego w automat Mealy’ego wykorzystuje się rozszczepienie stanów wewnętrznych. W niektórych wypadkach może to znacznie zwiększyć liczbę stanów wewnętrznych i przejść automatu skończonego.
Różnica między automatem klasy D a automatem klasy C polega na tym, że automaty klasy D są automatami Mealy’ego i każdy formowany wektor zmiennych wyjściowych określa kod stanu następnego. Do przejścia od dowolnego automatu skończonego (klasy A) do automatu klasy D w metodzie A4 wykorzystuje się rozszczepienie stanów wewnętrznych. Oprócz tego, aby można było zbudować automat klasy D, układ PLD powinien dopuszczać konfigurację wyjściowych makrokomórek z przerzutnikami w pętlach sprzężeń zwrotnych. Metoda A4 syntezy automatów skończonych klasy D może być alternatywą dla metody syntezy automatów klasy C w wypadkach, kiedy realizowany automat powinien być automatem Mealy’ego.
Wadą metody A4 jest konieczność rozszczepiania stanów wewnętrznych dla przekształcenia automatu wejściowego w automat klasy D oraz konieczność konfiguracji makrokomórek wyjściowych PLD z przerzutnikami w pętlach sprzężeń zwrotnych.
Główną cechą wyróżniającą metod A5 i A6 syntezy automatów skończonych klas E i F jest wykorzystanie przerzutników buforów wejściowych PLD w charakterze elementów pamięci automatu skończonego w przypadku, gdy wektory zmiennych wyjściowych mają identyczne wartości z częścią kodu stanów wewnętrznych. Pozwala to obniżyć koszt realizacji i jednocześnie zwiększyć szybkość działania automatów w porównaniu z automatami klas A i B.
W metodach A5 i A6 rozszczepienie stanów wewnętrznych wykorzystuje się w celu przekształcenia wejściowych automatów klas A i B odpowiednio w automaty klas E i F. Kodowanie stanów wewnętrznych automatów klas E i F prowadzi do zadania pokrycia grafu ortogonalności wierszy macierzy kodów minimalną liczbą pełnych podgrafów. W ogólnym wypadku, aby możliwe było zbudowanie automatów skończonych klas E i F, każdy wejściowy bufor PLD powinien posiadać dwa sprzężenia z logiką wewnętrzną układu PLD: rejestrowe i kombinacyjne.
Z wad metod A5 i A6 należy wymienić konieczność rozszczepienia stanów wewnętrznych dla przekształcenia wejściowych automatów klas A i B w automaty klas E i F. Oprócz tego, przy syntezie automatów klasy F wykorzystuje się rozszczepienie stanów wewnętrznych do przekształcenia automatu typu Mealy’ego w automat Moore’a.
<w przygotowaniu>
Metoda A7 syntezy wspólnego modelu automatów skończonych klas ADE pozwala najbardziej efektywnie wykorzystać możliwości architektur PLD: przerzutniki buforów wejściowych i makrokomórek wyjściowych w charakterze elementów pamięci automatu skończonego. Cechą charakterystyczną metody A7 jest maksymalne wykorzystanie modeli automatów klas D i E, co pozwala zminimalizować liczbę R elementów pamięci. W metodzie A7 wykorzystuje się rozszczepienie stanów wewnętrznych względem wektorów zmiennych wejściowych i wyjściowych.
Wadą metody A7 są zwiększone wymagania co do możliwości architektury PLD: istnienie buforów wejściowych z dwoma typami sprzężeń z logiką wewnętrzną układu PLD oraz konieczność umożliwienia konfiguracji makrokomórek wyjściowych z przerzutnikami w pętlach sprzężeń zwrotnych.
Metody A8 i A9 syntezy wspólnych modeli automatów skończonych klas AD i AE są odpowiednio zgodne z metodą ADE, kiedy nie można wykorzystać wejściowych buforów PLD (metoda A8 syntezy automatów klasy AD) lub wyjściowych makrokomórek w charakterze elementów pamięci (metoda A9 syntezy automatów klasy AE).
Metoda A10 syntezy wspólnego modelu automatów klasy BF jest identyczna z metodą A9 dla automatów klasy AE w przypadku jego przekształcenia w automat typu Moore’a. Do przekształcenia wejściowego automatu skończonego w automat typu Moore’a w metodzie A10 stosuje się rozszczepienie stanów wewnętrznych automatu.
<w przygotowaniu>
Metoda A10 syntezy wspólnego modelu automatów klasy BF jest identyczna z metodą A9 dla automatów klasy AE w przypadku jego przekształcenia w automat typu Moore’a. Do przekształcenia wejściowego automatu skończonego w automat typu Moore’a w metodzie A10 stosuje się rozszczepienie stanów wewnętrznych automatu.
Za pomocą pakietu ZUBR możliwa jest synteza sześciu klas automatów skończonych A, B, C, D, E i F, które mogą być efektywnie realizowane na PLD, a także czterech wspólnych modeli klas ADE, AD, AE i BF. Ponieważ na wejściach wszystkich modeli strukturalnych automatów skończonych można ustawić rejestry lub zatrzaski a na wyjściach – rejestry, to ogólna liczba modeli automatów skończonych, których realizacja jest możliwa na PLD wynosi 50. Dlatego wybór najbardziej pasującego modelu automatu potrzebnego przy jego realizacji na PLD nie jest zadaniem trywialnym. Zadanie jest jeszcze bardziej złożone , kiedy należy wybrać grupę najbardziej efektywnych modeli dla jakiegoś zbioru automatów skończonych, np. spotykanych w projektowanym systemie cyfrowym.
Najważniejszymi czynnikami, wpływającymi na wybór modelu strukturalnego automatu skończonego przy jego realizacji na PLD są:
wymagania systemowe, określone typami wejść i wyjść;
możliwości architektury PLD, konieczne do realizacji wspólnych modeli;
klasa automatu skończonego, do której odnosi się lub jest bliski realizowany automat skończony;
parametry czasowe modelu strukturalnego, wpływające na zachowanie się systemu cyfrowego;
koszt realizacji modelu i inne.
Wymagania systemowe w stosunku do automatu skończonego, są najważniejsze przy wyborze modelu strukturalnego. Na przykład, jeżeli przewiduje się wykorzystanie automatu na pierwszym poziomie systemu cyfrowego, na którego wejście sygnały podawane są w dowolnych momentach, to należy zastosować modele strukturalne z rejestrami lub zatrzaskami na wejściach. Z drugiej strony, jeśli przewiduje się wykorzystanie automatu na ostatnim poziomie systemu, należy wybrać modele z rejestrami na wyjściach. Dla systemów cyfrowych z potokową obróbką danych ważne jest, aby w każdym takcie synchronizacji na każdym poziomie systemu zakończone były czynności związane z obróbką danych. Dlatego w systemach potokowych na wszystkich poziomach należałoby zastosować modele z rejestrami na wyjściach. Należy zwrócić uwagę na stosowanie modeli z wejściami i wyjściami kombinacyjnymi, kiedy funkcje wyjściowe automatu skończonego bezpośrednio zależą od zmiennych wejściowych. W takich modelach każda zmiana na wejściach będzie powodowała zmiany wartości zmiennych wyjściowych.
Do budowy modeli automatów skończonych wykorzystywane są następujące cechy architektur PLD:
(1) – możliwość konfiguracji wyjściowych makrokomórek PLD z przerzutnikiem w pętli sprzężenia zwrotnego;
(2) – istnienie dwóch typów sprzężenia (kombinacyjnego i rejestrowego) między buforem wejściowym i logiką wewnętrzną układu PLD;
(3) – istnienie jednego typu sprzężenia (rejestrowego) między buforem wejściowym a logiką wewnętrzną układu PLD;
(4) – możliwość konfiguracji makrokomórek wyjściowych z wejściem rejestrowym i kombinacyjnym sprzężeniem zwrotnym;
(5) – możliwość konfiguracji wejściowych makrokomórek z zatrzaskami w charakterze elementów pamiętających.
Do zbudowania niektórych modeli wymaga się jednoczesnego występowania kilku podanych cech układu PLD. Z cechami architektury PLD wiąże się też możliwość buforowania wejściowych i (lub) wyjściowych sygnałów, która jest uwzględniana przy określaniu kosztów realizacji modelu.
Celem wyboru modelu automatu skończonego w zależności od parametrów czasowych jest zapewnienie maksymalnej szybkości działania systemu cyfrowego. Przy tym należy uwzględnić typ systemu: szeregowy lub potokowy. W wypadku systemu szeregowego należy wyróżnić systemy z oddzielną i ogólną synchronizacją.
W końcowym etapie wyboru modelu automatu skończonego uwzględnia się koszt realizacji, który oblicza się na podstawie konkretnych parametrów automatu skończonego lub ich średnich wartości, w przypadku wyboru modelu dla grupy automatów skończonych.
Metoda A12 wyboru najbardziej pasującej metody syntezy automatu skończonego pozwala na podstawie własności automatu skończonego wybrać metodę syntezy, zapewniającą minimalny koszt realizacji. Własności automatu skończonego są określane na podstawie zbiorów AA, AB, AC, AD, AE i AF stanów wewnętrznych automatów, odpowiednio, klas A, B, C, D, E i F. Minimalny koszt realizacji zapewniony jest poprzez wybór metody syntezy, dla której występuje minimalna liczba stanów wewnętrznych, kodowanych z wykorzystaniem różnych bitów kodu.