Podręcznik

1. Pojęcia podstawowe

W omawianych do tej pory układach kombinacyjnych wektor wyjściowy Y_t w chwili t jest bezpośrednio zależny od wektora wejściowego X_t w chwili t. Zajmiemy się teraz układami sekwencyjnymi, dla których wektor wyjściowy Y_t  w chwili t zależy od sekwencji wektorów wejściowych X_t, X_t–1, X_t–2,…, w chwilach t, t –1, t – 2,… .

Modelem matematycznym układu sekwencyjnego jest automat. Automat jest definiowany przez określenie:

1. zbioru liter wejściowych X (lub V) i wyjściowych Y,
2. zbioru stanów wewnętrznych S,
3. funkcji przejść (oznaczanej d),
4. funkcji wyjść (oznaczanej l).

W formalnym zapisie automat A określa się jako piątkę áS, X, Y, d, lñ, gdzie funkcja przejść jest definiowana jako odwzorowanie d: S ´ X ® S, natomiast funkcja wyjść l jest odwzorowaniem l: S ´ X ® Y (tzw. automat Mealy’ego) lub jako l: S ® Y (tzw. automat Moore’a).

Ważnym pojęciem w układach cyfrowych jest pojęcie automatu zupełnego i niezu­pełnego. Automat, określony funkcjami przejść d i wyjść l nazywamy automatem zupełnym, jeśli dziedziny tych funkcji są równe zbiorom S ´ X oraz S (w przypadku funkcji wyjść automatu Moore’a). Jeśli natomiast dziedziną którejkolwiek funkcji jest podzbiór wymienionych zbiorów, to jest: D_d Ì S ´ X, D_l Ì S ´ X lub D_l Ì S, to taki automat nazywamy niezupełnym.

Funkcje przejść-wyjść jest najwygodniej przedstawiać za pomocą tablicy przejść-wyjść. Tablice przejść-wyjść przykładowych automatów podane w tabeli 4.1 reprezentują automat Moore’a (a) oraz automat Mealy’ego (b). Tablicom tym odpowiadają grafy automatów pokazane na rys. 4.1.

 

Tablica 4.1

 

 

Techniczną realizacją automatu jest układ sekwencyjny zbudowany z układu kombinacyjnego i pamięci (rys. 4.2). Układ kombinacyjny automatu jest układem wielowyjściowym, wytwarzają­cym sygnały wyjściowe automatu y₁, …, y_m oraz syg­nały wzbudzające układ pamięciowy q₁, …, q_k. Wejścia­mi układu kombi­nacyjnego są sygnały wejściowe automatu x₁, …, x_n oraz sygnały wyjściowe Q₁, …, Q_p układu pamięciowego.

 

Rys. 4.1. Graf automatu a) Moore’a, b) Mealy’ego

 

 

Rys. 4.2. Układ sekwencyjny

 

Układ kombinacyjny jest opisany tablicami wyjść i wzbudzeń (sposób tworzenia tablic wzbudzeń poznamy w dalszej części rozdziału). W układach synchronicznych pamięć automatu jest zbudowana z tzw. przerzutników – automatów elementarnych synchronizowanych specjalnym sygnałem zegarowym oznaczonym clk. W układach asynchronicznych pamięć jest realizowana bezpośrednio przez sprzężenia zwrotne z wyjść na wejścia układu kombinacyjnego.

Synteza układów sekwencyjnych jest złożo­nym i obszernym zadaniem składającym się z kilku etapów. Zwyczajowo wyróżnia się następujące etapy:

• synteza abstrakcyjna (utworzenie tablicy przejść-wyjść),
•  redukcja (minimalizacja) liczby stanów,
•  kodowanie stanów, liter wejściowych i wyjściowych,
•  synteza kombinacyjna (obliczanie funkcji wzbudzeń przerzutników i funkcji wyjściowych).

Omawianie procesu syntezy układów sekwencyjnych rozpoczynamy od etapu syntezy abstrakcyjnej, której celem jest utworzenie tablicy przejść-wyjść. Tablicę taką najczęściej tworzy się za pośrednictwem grafu automatu. Jest to najważniejszy a zarazem najobszerniejszy etap całego procesu syntezy.

Tworzenie grafu automatu, a tym samym odpowiedniej tablicy przejść-wyjść, jest istotną czynnością w syntezie układów sekwencyjnych. Rozważmy tablicę przejść-wyjść układu sekwencyjnego spełniającego funkcję tzw. detektora sekwencji

Układ ma badać kolejne „trójki” symboli wejściowych. Sygnał wyjściowy pojawiający się podczas trzeciego skoku układu ma wynosić 1, gdy „trójka” ma postać 001, a 0, gdy „trójka” jest innej postaci – stąd nazwa „detektor sekwencji”. Graf tego automatu jest pokazany na rys. 4.3. Odpowiadająca mu tablica przejść-wyjść jest pokazana w tablicy 4.2.

Rys. 4.3. Graf detektora sekwencji

 

Tablica 4.2

 

 

 

Łatwo sprawdzić, że każda sekwencja 001 na wejściu układu spowoduje powstanie na jego wyjściu sygnału y = 1.

Równie prosta jest konstrukcja grafu automatu wykrywającego ciąg dokładnie trzech albo dokładnie czterech następujących bezpośrednio po sobie jedynek w dowolnie długim słowie wejściowym.

 

Syntezę abstrakcyjną bardziej złożonego automatu omawiamy w przykładzie 4.2.