Sekwencyjne układy cyfrowe
Układ sekwencyjny  to układ cyfrowy, w którym zależność między wartościami sygnałów
wejściowych (tzw. stan wejść) i wyjściowych (tzw. stan wyjść) nie jest jednoznaczna.
Stan wyjść układu sekwencyjnego zależy nie tylko od aktualnego stanu wejść ale również od
poprzednich stanów wejść tzn. od kolejności (sekwencji) zmian stanów wejść. Układy te
zapamiętują historię oddziaływań sygnałów wejściowych  dlatego też nazywane są układami z
pamięcią. Pamięć układu, tzw. blok pamięci, tworzy minimalna liczba wielkości niezbędnych do
opisania wszystkich skutków przeszłych oddziaływań. Wielkości te nazywane są stanem pamięci
wewnętrznej (stanem pamięci lub stanem wewnętrznym) układu.
Temu samemu stanowi wejść mogą więc w układzie sekwencyjnym odpowiadać różne stany
wyjść, zależność pomiędzy stanem wejść i wyjść układu nie jest jednoznaczna.
W zależności od sposobu oddziaływania sygnałów wejściowych na układ (a właściwie na blok
pamięci) układy sekwencyjne dzielone są na:
układy asynchroniczne
zmiana stanu pamięci następuje bezpośrednio (w dowolnej chwili czasu) pod wpływem
zmiany stanu wejść,
układy synchroniczne
zmiana stanu pamięci następuje tylko w ściśle określonych chwilach czasu wyznaczanych
przez dodatkowy sygnał wejściowy układu tzw. sygnał taktujący (zegarowy,
synchronizujący).
Układy cyfrowe f.2/1
Sekwencyjne układy cyfrowe  oznaczenia
xi  i-ty sygnał wejściowy; m  ilość sygnałów wejściowych;
yi  i-ty sygnał wejściowy; n  ilość sygnałów wejściowych;
Qi  i-ty element pamięci; p  ilość elementów pamięci;
qi  aktualny stan i-tego elementu pamięci Qi:
X = (x1, x2, & , xm)  stan wejść;
Y = (y1, y2, & , yn)  stan wyjść ;
A = (q1, q2, & , qp)  stan pamięci wewnętrznej (stan pamięci lub stan wewnętrzny);
X  zbiór wszystkich stanów wejść (zawiera maksymalnie 2m stanów);
Y  zbiór wszystkich stanów wyjść (zawiera maksymalnie 2n stanów);
A  zbiór wszystkich stanów wewnętrznych (zawiera maksymalnie 2p stanów);
W realizacji stykowej element pamięci Qi realizowany jest jako przekaz
nik. Po zmianie sygnału
wejściowego przekaz
nika stan jego cewki Qi może różnić się od stanu jego zestyków qi. W
praktyce na przełączenie potrzebny jest czas (kilkanaście milisekund). Jeżeli stan zestyków qi
różni się od stanu cewki Qi to elementy bloku pamięci będą zmieniały swój stan aż do zrównania
stanów Qi i qi. Podobne opóz
nienie (kilka nanosekund) wprowadzają elementy bezstykowe  po
zmianie stanu wejść sygnały wyjściowe bloku pamięci qi będą miały przez pewien czas wartości
wynikające ze stanu poprzedniego.
Układy cyfrowe f.2/2
Sekwencyjne układy cyfrowe  struktura
Przyjmuje się następujący opis funkcjonowania układu sekwencyjnego:
sygnały wejściowe xi (i = 1 : m) przekazywane są do elementów pamięci Qj (j = 1 : p) które
tworzą tzw. blok pamięci, sygnały wyjściowe bloku pamięci qj zależą od wartości sygnałów
wejściowych xi oraz od stanu samej pamięci qj (tzn. od poprzednich sygnałów wyjściowych
bloku pamięci), oddziaływanie sygnałów wyjściowych bloku na jego wejścia stanowi
sprzężenie zwrotne,
sygnały z wyjść bloku pamięci qj wysyłane są również do elementów wyjściowych układu,
które na ich podstawie (i ewentualnie sygnałów wejściowych układu) generują sygnały
wyjściowe yk (k = 1 : n).
q1
BP  blok pamięci; qj q1
BW  blok elementów wyjściowych;
qp qj
S  sygnał taktujący (tylko w układach synchronicznych)
qp
S
y1(t)
Sygnały wejściowe przesyłane są na wejście
BP
x1
yj(t)
bloku wyjściowego tylko w tzw. układach Mealy ego,
BW
xi
Jeżeli blok wyjściowy otrzymuje wyłącznie sygnały
yn(t)
xm
z bloku pamięci to układ taki jest nazywany
układem Moore a.
Rys. 1. Schemat blokowy układu sekwencyjnego
Układy cyfrowe f.2/3
Sekwencyjne układy cyfrowe  opis
Działanie układów sekwencyjnych opisuje się za pomocą funkcji przejść:
�: A�X A,
oraz funkcji wyjść:
: A�X Y (dla układu Mealy ego) lub : A Y (dla układu Moore a)
Funkcja przejść określa stan wewnętrzny układu w chwili (t + 1) na podstawie stanu
wewnętrznego i stanu wejść w chwili poprzedniej t:
At +1 = �(At, Xt).
Funkcja przejść � odpowiada za pamięć układu, na schemacie blokowym układu była
reprezentowana przez blok pamięci.
Funkcja wyjść określa stan wyjściowy układu w zależności od stanu wewnętrznego,
i ewentualnie stanu wejściowego, w tej samej chwili:
Yt = (At, Xt) (dla układu Mealy ego),
Yt = (At) (dla układu Moore a).
Każdy układ sekwencyjny może być zaprojektowany jako układ Moore a lub Mealy ego. Układy
Mealy ego mają zwykle prostszą strukturę.
Układy cyfrowe f.2/4
Sekwencyjne układy cyfrowe  uwagi
Funkcja wyjść  wyznacza wartości sygnałów wyjściowych  na schemacie blokowym układu
sekwencyjnego była reprezentowana przez blok wyjściowy;
 jest funkcją przyporządkowującą każdemu argumentowi (At, Xt) czy (At) dokładnie jeden
stan wyjść Yt; stąd blok wyjściowy układu sekwencyjnego jest układem kombinacyjnym.
Stany wejść, stany wewnętrzne i stany wyjść układów sekwencyjnych określone są w
dyskretnych chwilach czasu:
t1, t2, t3, & .
W układach asynchronicznych odstęp pomiędzy kolejnymi chwilami czasu jest różny,
t2 = t1 + "t1, t3 = t2 + "t2, & ,
zależy od czasu reakcji elementów układu "tk,
w układach synchronicznych odstępy są równe, zależne od sygnału taktującego:
t2 = t1 + "t, t3 = t2 + "t, & , ("t > "tk).
Układy asynchroniczne pracują na ogół szybciej od układów synchronicznych. Różnice w
prędkościach działania elementów układu asynchronicznego przyczyniają się do powstawania
niekorzystnych zjawisk (hazard, wyścig krytyczny), zjawiska te nie występują w układach
synchronicznych.
Układy cyfrowe f.2/5
Metody opisu układów sekwencyjnych
Opis słowny  opisowo przedstawia funkcjonowanie układu, z opisu powinny wynikać wszystkie
stany wejściowe (a właściwie wszystkie możliwe sekwencje tych stanów) i odpowiadające im
stany wyjściowe (lub ich sekwencje). Z opisu słownego nie wynika np. ilość niezbędnych do
realizacji układu elementów pamięci.
Przykład 1.
Przycisk P steruje pracą lampy. Jeśli lampa nie świeci, wciśnięcie przycisku powoduje jej
zaświecenie, jeśli lampa świeci, wciśnięcie przycisku powoduje jej zgaszenie. Zwolnienie
przycisku nie powoduje zmian jej stanu.
Układ jest układem sekwencyjnym (z pamięcią)  dla tego samego stanu wejściowego (wciskanie przycisku)
możliwe są dwa stany wyjściowe (lampa świeci i lampa nie świeci).
Przykład 2.
Przyciski Z (załącz) i W (wyłącz) sterują pracą urządzenia. Naciśnięcie przycisku Z załącza
urządzenie, urządzenie pracuje również po zwolnieniu tego przycisku. Naciśnięcie przycisku W
wyłącza urządzenie. Urządzenie nie pracuje gdy wciśnięte są obydwa przyciski. Dodatkowo, nie
jest możliwa jednoczesna zmiana stanu obydwu przycisków.
Układ jest układem sekwencyjnym  dla tego samego stanu wejściowego (obydwa przyciski zwolnione)
możliwe są dwa stany wyjściowe (urządzenie pracuje i urządzenie nie pracuje).
Układy cyfrowe f.2/6
Metody opisu układów sekwencyjnych
Wykres czasowy  przedstawia przebieg w czasie zmian stanów wejściowych i odpowiadających
im stanów wyjściowych  przy czym nie są uwzględniane opóz
nienia wynikające z czasu reakcji
elementów układu. Do jednoznacznego opisu działania układu niezbędne jest zaznaczenie na
wykresie wszystkich możliwych sekwencji stanów wejść i wyjść. Przy dużej liczbie sygnałów
wejściowych lub wejściowych czy skomplikowanym sposobie przetwarzanie sygnałów wykres
ten może być jednak mało czytelny.
a) P
W taktach:
t
nieparzystych: P=0 a Y=0 lub Y=1
Y
t parzystych: P=1 a Y=0 lub Y=1
1 2 3 4 5 6 7 8 9 10 11 12 13
Z
t
b)
W
W taktach 2.,4.,8.,12.
t
stan wejściowy Z=0, W=0 a
Y
stan wyjściowy Y=0 lub Y=1
t
1 2 3 4 5 6 7 8 9 10 11 12 13
Rys. 2. Wykresy czasowe układów a) z przykładu 1. i b) z przykładu 2.
Układy cyfrowe f.2/7
Metody opisu układów sekwencyjnych
Opis słowny czy wykresy czasowe przedstawiają jedynie zależności pomiędzy zewnętrznymi
sygnałami układu (tzn. sygnałami wejściowymi i wyjściowymi). Do syntezy układu potrzebna
jest wiedza o stanach wewnętrznych układu oraz funkcjach przejść i wyjść. Informacje takie
zawarte są w opisach typu graf przejść czy tablice przejść i wyjść.
Graf przejść  graf, którego wierzchołki odpowiadają stanom wewnętrznym układu A, a gałęzie
oznaczają przejścia pomiędzy stanami wymuszane określonymi stanami wejściowymi X. Dla
układów Moore a stan wyjść Y zależy wyłącznie od stanu wewnętrznego A więc jest
przyporządkowywany odpowiedniemu wierzchołkowi grafu. Dla układów Mealye go stan wyjść
Y zależy od stanu wewnętrznego A i od stanu wejść X i jest przyporządkowany podobnie jak
stan wejść odpowiedniej gałęzi grafu.
stan wejść
stan wyjść
0 1
1
stan
A1 A2
wewnętrzny
A1  lampa nie świeci (przycisk P zwolniony),
0 0
A2  lampa świeci (przycisk P wciśnięty),
1
A3  lampa świeci (przycisk P zwolniony),
A4 A3
A4  lampa nie świeci (przycisk P wciśnięty)
0 1
Rys. 3. Graf przyjść układu z przykładu 1.
Układy cyfrowe f.2/8
Metody opisu układów sekwencyjnych
Konstrukcja grafu przejść nie zawsze jest zadaniem łatwym. Wymaga po pierwsze znajomości
stanów wewnętrznych układu. Stany wewnętrzne można zidentyfikować np. uważnie analizując
opis słowny układu lub wykres czasowy układu.
Wykres czasowy należy podzielić na odcinki czasu w których sygnały wejściowe nie ulegają
zmianie. Kolejne kombinacje wartości stanów wejściowych i wyjściowych odpowiadają stanom
wewnętrznym układu. Każdą nową kombinację wartości stanu wejściowego i wyjściowego
można oznaczyć jako nowy stan wewnętrzny. Stany w których wejścia i wyjścia są takie same
mogą być stanami równoważnymi lub nie.
Poniżej przedstawiony został wykres czasowy układu z przykładu 2. Założono, że wszystkie
stany o tych samych wejściach i wyjściach są stanami równoważnymi.
1
A1 A2 A3 A4 A1 A5 A3 A4 A3 A5 A1 A2 A1 A3
Z
00
10
t
10 11
W
10
0 1
0
t
Y
A2 A5 A4
t
01
11 01
1 2 3 4 5 6 7 8 9 10 11 12 13
01
00
Rys. 4. Wykres czasowy i graf przejść układu z przykładu 2.
A1
(A1  urz. wył. Z=0, W=1, A2  urz. wył. Z=0, W=0,, A3  urz. wł. Z=1, W=0,
0
A4  urz. wł. Z=0, W=0, A5  urz. wył. Z=1, W=1).
Układy cyfrowe f.2/9
Metody opisu układów sekwencyjnych
Tablica przejść  podobnie jak graf przejść zawiera wszystkie stany wewnętrzne układu i
przejścia pomiędzy tymi stanami wymuszane stanami wejściowymi. Tablica ta ma tyle wierszy
ile jest stanów wewnętrznych układu i tyle kolumn ile różnych stanów wejściowych może
wystąpić podczas pracy układu (z tego powodu może być stosowana dla układów o maksymalnie
5, 6 wejściach). Do kratek tablicy wpisywane są stany wewnętrzne, do których przechodzi układ
który był poprzednio w stanie określonym przez wiersz tablicy pod wpływem stanu wejściowego
określonego przez kolumnę tablicy (w każdym z wierszy tablicy jedna z kratek opisana jest tak
samo jak wiersz  odpowiada to sytuacji kiedy stan wejść nie ulega zmianie, nie ulega więc
zmianie również stan wewnętrzny). Tablica przejść odpowiada funkcji przejść � układu.
Tablica wyjść  odpowiada funkcji wyjść  układu;
dla układu Mealye go podobnie jak tablica przejść ma tyle wierszy ile jest stanów wewnętrznych
układu i tyle kolumn ile jest różnych stanów wejściowych, w kratkach tablicy wpisywane są
stany wyjściowe odpowiadające stanom wewnętrznym wskazywanym przez wiersze tablicy i
stanom wejściowym wskazywanym przez kolumny tablicy;
dla układu Moore a stan wyjść jest funkcją tylko stanu wewnętrznego, tablica wyjść ma więc tyle
wierszy ile jest stanów wewnętrznych i jedną kolumnę w której wpisywane są wartości stanów
wyjściowych, dla układów tego typu tablicę przejść uzupełnia się dodatkową kolumną
zawierającą wartości stanów wyjściowych  otrzymuje się w ten sposób tablicę przejść 
wyjść).
Układy cyfrowe f.2/10
Tablice przejść i wyjść
0 1
X=P X=P
1
A Y
A 0 1 A 0 1 Y
A1 A2
A1 0
A1 A1 A2 A1 A1 A2 0
0 0
A2 1
A2 A3 A2 A2 A3 A2 1
A3 1
1 A3 A3 A4 A3 A3 A4 1
A4 A3
A4 0
A4 A1 A4 A4 A1 A4 0
0 1
1
A3
X=(Z,W) X=(Z,W)
00
10
A 00 01 11 10 A Y A 00 01 11 10 Y
10 11
10
0 1
0
A1 A2 A1 A5  A1 0 A1 A2 A1 A5  0
A2 A5 A4 A2 A2 A1  A3 A2 0 A2 A2 A1  A3 0
01
A3 A4  A5 A3 A3 1 A3 A4  A5 A3 1
11 01
01
00
A4 1
A4 A4 A1  A3 A4 A4 A1  A3 1
A1
A5  A1 A5 A3 A5 0 A5  A1 A5 A3 0
0
Rys. 5. Grafy przejść, tablice przejść, tablice wyjść i tablice przejść-wyjść układów z przykładu 1. i 2.
(na czerwono zaznaczono komórki których stan wewnętrzny nie zmienił się ponieważ nie zmienił się stan wejść)
Układy cyfrowe f.2/11
Analiza i synteza układów sekwencyjnych
Analiza  głównym celem analizy jest zrozumienie zasad działania układu, w przypadku gdy
znana jest jego struktura; celem analizy może być również chęć wykrycia z
ródeł niewłaściwego
zachowania układu (hazard, wyścig, zamknięty cykl drgań).
Synteza  to proces odwrotny do analizy, prowadzi od założeń definiujących sposób działania
układu do jego projektu.
b) opis układu
(wykres czasowy,
a)
graf przejść)
schemat
układu
pierwotna
tablica
tablice
programu
stanów
zredukowana
tablice
tablica
tablice schemat
przejść i wyjść
programu
stanów układu
ew. graf przejść
(tablice przejść
i wyjść)
Rys. 6. Algorytmy a) analizy i b) syntezy układu sekwencyjnego.
Układy cyfrowe f.2/12
Synteza układów sekwencyjnych
Podczas syntezy układu sekwencyjnego należy kolejno ustalić:
liczbę elementów wejściowych i wejściowych (ilości te wynikają wprost ze sformułowania
zadania, które ma realizować układ),
liczbę elementów pamięci,
funkcje przejść � i wyjść  układu,
zaproponować schemat układu (budując blok pamięci:
z wykorzystaniem pętli sprzężeń zwrotnych  rozwiązanie takie wynika wprost z
postaci funkcji �,
z wykorzystaniem przerzutników  w tym przypadku należy wybrać typ przerzutnika i
na podstawie funkcji � określić funkcje wzbudzeń wszystkich przerzutników użytych do
budowy pamięci, wykorzystanie przerzutników eliminuje pętle sprzężeń zwrotnych).
Do syntezy układów sekwencyjnych stosowane są metody:
tablic kolejności łączeń (zwana metodą Siwińskiego)  może być stosowana dla niezbyt
złożonych algorytmów przetwarzania sygnałów ale niezależnie od ilości elementów
wejściowych i wyjściowych układu,
tablic przejść i wyjść (zwana metodą Huffmana)  może być stosowana dla złożonych
algorytmów przetwarzania ale przy niedużej liczbie sygnałów wejściowych (2, 3).
Układy cyfrowe f.2/13
Synteza asynchronicznych układów sekwencyjnych
W układach asynchronicznych zmiana stanu pamięci At następuje bezpośrednio (w dowolnej
chwili czasu) pod wpływem zmiany stanu wejść Xt. Nowy stan wewnętrzny At+1 ustala się w
układzie po czasie "tk zależnym od czasu reakcji elementów układu.
Układ może znajdować się w stanach wewnętrznych: stabilnym lub niestabilnym. Jeżeli nie
zmienia się stan wejść X i stan wewnętrzny
At+1 `" At,
to stan At jest niestabilnym stanem wewnętrznym. Jeżeli stan wejść się nie zmienia oraz
At+1 = At,
to stan At jest stabilnym stanem wewnętrznym. Stan taki ustala się po ustaniu procesów
przejściowych po czasie "tk (wynikającym z opóz
nień wnoszonych przez elementy tworzące
blok pamięci układu) od zmiany stanu wejść układu.
Jeżeli układ znajduje się w stanie stabilnym to zmiana tego stanu może nastąpić jedynie pod
wpływem zmiany stanu wejść. Po zmianie stanu wejść układ znajdzie się w stanie niestabilnym a
po upływie czasu "tk w nowym stanie stabilnym. Przyjmuje się (dla zapewnienia poprawnej
pracy układów asynchronicznych), że:
zmiana stanu wejść może być spowodowana zmianą tylko jednego sygnału wejściowego,
zmiana stanu wejść może nastąpić tylko wtedy gdy układ znajduje się w stanie stabilnym.
Układy cyfrowe f.2/14
Synteza asynchronicznych układów sekwencyjnych metodą Huffmana
Metoda polega na:
sporządzeniu opisu działania układu w postaci tablicy przejść  wyjść nazywanej także
pierwotną tablicą programu,
wykonaniu redukcji (minimalizacji) stanów wewnętrznych,
pierwotna liczba stanów wewnętrznych układu przyjęta na podstawie pierwotnej tablicy
programu może być większa od liczby stanów niezbędnych do realizacji określonego
zadania, na tym etapie powstaje z pomocą wykresu redukcyjnego tzw. zredukowana tablica
programu (tabela ta powstaje w wyniku połączenia wybranych wierszy pierwotnej tablicy
programu),
określeniu liczby elementów pamięci i przypisaniu im odpowiednich kodów,
kodowanie elementów pamięci przeprowadza się z pomocą tzw. wykresu przejść,
zestawieniu tablic stanów elementów pamięci i elementów wyjściowych.
Przy pomocy tablic stanów można już zbudować schematy logiczne dla bloku pamięci i bloku
wyjściowego.
Konstrukcja bloku pamięci z przerzutników wymaga jeszcze dodatkowo określenia typu
wykorzystywanych przerzutników i i ich funkcji wzbudzeń.
Układy cyfrowe f.2/15
Pierwotna tablica programu
W pierwotnej tablicy programu:
stany wewnętrzne układu oznaczane są zwykle kolejnymi liczbami naturalnymi,
stabilny stan wewnętrzny zaznacza się obwodząc kółkiem liczbę odpowiadającą temu
stanowi.
X=(Z,W)
X=(Z,W)
a) b)
A 00 01 11 10 Y
A 00 01 11 10 Y
Oznaczenia stanów:
1  A1 (urz. wył. Z=0, W=1),
1
2 5  0
A1 A2 A1 A5  0
2  A2 (urz. wył. Z=0, W=0),
2
1  3 0
A2 A2 A1  A3 0
3  A3 (urz. wł. Z=1, W=0),
3
4  5 1
A3 A4  A5 A3 1 4  A4 (urz. wł. Z=0, W=0),
5  A5 (urz. wył. Z=1, W=1).
4
1  3 1
A4 A4 A1  A3 1
5
 1 3 0
A5  A1 A5 A3 0
Rys. 7. Tablica przejść-wyjść układu z przykładu 2.
a) przed i b) po wprowadzeniu nowych oznaczeń dla stanów wewnętrznych,
W tablicy a) na czerwono zaznaczone zostały komórki których stan wewnętrzny nie zmienił się z powodu
braku zmian stanu wejściowego  stany te są stanami stabilnymi układu.
Układy cyfrowe f.2/16
Redukcja stanów wewnętrznych
A
ączenie odpowiadających sobie wierszy pierwotnej tablicy programu pozwala na zmniejszenie
liczby niezbędnych elementów pamięci potrzebnych do realizacji określonego programu.
A
ączyć można ze sobą wiersze tabeli:
zawierające w opowiadających sobie kolumnach stany niesprzeczne,
stany są niesprzeczne jeżeli jeden z nich jest opisany liczbą a drugi    ,
jeżeli stan sygnałów wyjściowych w łączonych wierszach jest takim sam lub niesprzeczny to układ
odpowiadający nowej tabeli jest w dalszym ciągu układem Moore a,
jeżeli łączone są wiersze o różnych stanach wyjść, układ odpowiadający nowej tabeli będzie już układem
Mealye go i konieczne będzie zapisanie stanu jego wyjść w tablicy wyjść,
zawierające równoważne stany stabilne,
dwa stany stabilne są równoważne jeżeli znajdują się w tej samej kolumnie (są reakcją na te same stany
wejściowe), mają jednakowe lub niesprzeczne stany wyjściowe oraz wszystkie możliwe przejścia z tych
stanów prowadzą do takich samych stanów lub stanów równoważnych.
W wynikowym, połączonym wierszu wpisuje się:
liczbę  którą zawierały obydwie łączone komórki, lub liczbę z jednej z komórek w
przypadku gdy druga zawierała    ,
kreskę  jeżeli obydwie łączone komórki zawierały    ,
kółko  jeżeli obydwie łączone komórki zawierały tą samą liczbę i dodatkowo w jednej z
nich liczba ta oznaczała stabilny stan wewnętrzny.
Układy cyfrowe f.2/17
Redukcja stanów wewnętrznych
Podczas łączenia wierszy pierwotnej tablicy programu pomocny jest tzw. wykres redukcyjny:
na obwodzie koła umieszcza się liczby odpowiadające stanom wewnętrznym układu 
odpowiadają one jednocześnie numerom wierszy pierwotnej tablicy programu,
numery wierszy, które mogą zostać połączone, łączone są odcinkami (jeżeli stan wyjść jest
niesprzeczny odcinek powinien być narysowany linią ciągłą, w przeciwnym przypadku linią
przerywaną).
X=(Z,W)
A 00 01 11 10 Y
1
X=(Z,W)
1
2 5  0
A 00 01 11 10 Y
2
1  3 0
5 2
1,2,5
3 0
3
4  5 1
3,4
1 5 1
4
1  3 1
4 3
5
 1 3 0
Rys. 8. Pierwotna tablica programu, wykres redukcyjny, zredukowana tablica programu układu z przykł. 2.
Układy cyfrowe f.2/18
Kodowanie wierszy zredukowanej tablicy programu
Jeżeli liczba wierszy zredukowanej tablicy programu mieści się w zakresie 2p 1 a 2p to blok
pamięci można zrealizować wykorzystując p elementów pamięci. Wierszom zredukowanej
tablicy programu należy przypisać kody w postaci ciągów zerojedynkowych o długości p (ciągi
te odpowiadają stanom elementów pamięci Q1, Q2, & , Qp). Kody należy przypisać w taki sposób
aby niezbędne przejścia pomiędzy wierszami tabeli można było zrealizować przy zmianie stanu
tylko jednego elementu pamięci. Proces kodowania ułatwia tzw. wykres przejść:
na wykresie każdy wiersz zredukowanej tablicy programu jest reprezentowany przez
odpowiadający mu wierzchołek,
wierzchołki odpowiadające wierszom pomiędzy którymi w tablicy są przejścia (w wierszach
występuje ten sam numer stanu wewnętrznego  raz w postaci stanu stabilnego drugi raz w
postaci stanu niestabilnego) należy łączyć odcinkami,
na koniec, wierzchołkom należy przypisać ciągi zerojedynkowe (o długości p) w taki sposób
aby wierzchołki połączone były opisane ciągami różniącymi się tylko na jednej pozycji.
X=(Z,W)
Do realizacji pamięci wystarczy jeden
A 00 01 11 10 Y element pamięci Q1 (dwa wiersze = 21).
Wiersz pierwszy tabeli można zakodować
1,2,5
3 0
1,2,5 3,4
jako  0 , a drugi jako  1 .
3,4
1 5 1
Rys. 9. Kodowanie zredukowanej tablicy programu układu z przykładu 2.
Układy cyfrowe f.2/19
Tablice stanów
Końcowy etap syntezy układu polega na przygotowaniu tablic stanów elementów pamięci i elementów
wyjściowych. Tablice stanów odpowiadają funkcjom przejść � i wyjść  budowanego układu. Tablica stanów
elementów pamięci ma tyle wierszy ile jest stanów elementów pamięci i tyle kolumn ile jest stanów wejść.
Tak samo wygląda tablica stanów elementów wyjściowych dla układu Mealy ego. W przypadku układu
Moore a tablica ta ma tylko jedną kolumnę.
Tablicę stanów elementów pamięci otrzymuje się wprost ze zredukowanej tablicy programu uwzględniając
przyjętą metodę kodowania. Stany stabilne opisuje się kodem wiersza w którym stany te występują, a stany
niestabilne kodem wiersza docelowego.
Podobnie otrzymuje się tablicę stanów elementów wyjściowych dla układów Moore a. Dla układów
Mealy ego tablicę tą otrzymuje się wykorzystując zredukowaną i pierwotną tablicę programu. W kratkach, w
których w tablicy zredukowanej występują stany stabilne wpisuje się wartości stanów wyjściowych na
podstawie tablicy pierwotnej. W kratkach w których występują stany niestabilne wpisuje się wartość stanu
wyjściowego jeżeli przy przejściu przez stan niestabilny stan wyjść układu się nie zmienia lub    jeżeli stan
wyjść się zmienia.
Q1 = w(q1 + z)
X=(Z,W)
Y =Q1 z w
z,w
A 00 01 11 10 Y
Y=Q1
q1 Y
q1 00 01 11 10
q1
1,2,5
3 0
0 0 0 0 1
0 0
3,4
1 5 1
1 1 0 0 1
1 1
Rys. 10. Zredukowana tablica programu, tablice stanów i ostateczny schemat układu z przykładu 2.
Układy cyfrowe f.2/20
Synteza asynchronicznych układów sekwencyjnych - przykład
Przykład 3.
Zaprojektować układ sterujący pracą dwóch zaworów Z1 i Z2 przy pomocy których napełniany jest zbiornik.
Ze zbiornika w sposób przypadkowy może wypływać woda. Poziom wody w zbiorniku jest kontrolowany
przez czujniki A i B (a = 0  poziom wody poniżej A; a = 1  poziom wody powyżej A; b = 0  poziom wody
poniżej B; b = 1  poziom wody powyżej B; stan a = 0 i b = 1 nie może wystąpić).
Praca zaworów powinna przebiegać według następującego programu:
jeżeli jest niski poziom wody (a = 0, b = 0)  zawory powinny być otwarte (Z1= 1, Z2= 1) ,
jeżeli jest wysoki poziom wody (a = 1, b = 1)  zawory powinny być zamknięte (Z1= 0, Z2= 0)
jeżeli jest średni poziom wody (a = 1, b = 1)  otwarty jest zawór, który poprzednio był zamknięty.
Z1 Z2
B
A
Rys. 11. Ilustracja przykładowego zadania.
Układy cyfrowe f.2/21
Synteza przykładowego układu  stabilne stany wewnętrzne
Z analizy opisu programu pracy zaworów wynika, że układ może znajdować się w stanach:
A1: niski poziom wody, zawory otwarte (a = 0, b = 0, Z1 = 1, Z2 = 1),
A2: wysoki poziom wody, zawory zamknięte (a = 1, b = 1, Z1 = 0, Z2 = 0),
A3: średni poziom wody, otwarty zawór Z1 (a = 1, b = 0, Z1 = 1, Z2 = 0),
A4: średni poziom wody, otwarty zawór Z2 (a = 1, b = 0, Z1 = 0, Z2 = 1).
W oparciu o powyższe cztery stany nie można jeszcze zbudować tablicy czy grafu przejść.
Załóżmy, że układ znajduje się w stanie A1. Jeżeli poziom wody wzrośnie to układ może znalez
ć się albo w
stanie A3 albo w A4. Taka sytuacja jest niedopuszczalna. Zmiana stanu musi jednoznacznie zależeć od jego
stanu poprzedniego i od stanu wejść. Rozwiązanie powyższego problemu polega na wprowadzeniu dwóch
stanów opisujących zachowanie układu przy niskim stanie wody:
A1': niski poziom wody, zawory otwarte, poprzednio otwarty był zawór Z2,
A1": niski poziom wody, zawory otwarte, poprzednio otwarty był zawór Z1.
Układ w stanie A1', przy wzroście poziomu wody, zmienia stan na stanie A3, a układ w stanie A1", w tej
samej sytuacji, zmienia stan na A4  zmiana stanu układu jest jednoznacznie określona.
Podobna sytuacja ma miejsce gdy układ znajduje się w stanie A4. Przy spadku poziomu wody układ może
znalez
ć się albo w stanie A3 albo w A4. Problem można rozwiązać, podobnie jak poprzednio, wprowadzając
dwa stany opisujące zachowanie układu przy wysokim stanie wody:
A2': wysoki poziom wody, zawory zamknięte, poprzednio otwarty był zawór Z2,
A2": wysoki poziom wody, zawory zamknięte, poprzednio otwarty był zawór Z1.
Układy cyfrowe f.2/22
Synteza przykładowego układu  pierwotna tablica programu
Ostatecznie wyróżnionych zostało sześć stabilnych stanów wewnętrznych układu:
1: niski poziom wody, zawory otwarte, poprzednio otwarty był zawór Z2 (poprzednio stan A1'),
2: niski poziom wody, zawory otwarte, poprzednio otwarty był zawór Z1 (poprzednio stan A1"),
3: średni poziom wody, otwarty zawór Z1 (poprzednio stan A3),
4: średni poziom wody, otwarty zawór Z2 (poprzednio stan A4),
5: wysoki poziom wody, zawory zamknięte, poprzednio otwarty był zawór Z2 (poprzednio stan A2'),
6: wysoki poziom wody, zawory zamknięte, poprzednio otwarty był zawór Z1 (poprzednio stan A2").
X=(a,b)
10
10 00
3
00 01 11 10 Z1 Z2
A
10 11   3 1 1
1
11 00 00 11
  4 1 1
2
1 5 6 2
2  6 1 0
3
11 10
1  5
4 0 1
00 10
4
 
3 0 0
5
01
 
4 0 0
6
Rys. 12. Graf przejść i tablica przejść-wyjść układu z przykładu 3.
(przy założeniu, że zmiana stanu wejść może być spowodowana zmianą tylko jednego sygnału wejściowego
 założenie takie przyjmowane jest dla zapewnienia poprawnej pracy każdego układu asynchronicznego).
Układy cyfrowe f.2/23
Synteza przykładowego układu  redukcja stanów wewnętrznych
Redukcję stanów wewnętrznych ułatwia wykres redukcyjny.
a)
X=(a,b)
b) c)
00 01 11 10 Z1 Z2 X=(a,b)
A
1 2
  3 1 1
1
00 01 11 10
A
  4 1 1
2

3
1,5
2  6
3 1 0

4
2,6
6 3
1  5
4 0 1
2  6
3
 
3 0 0
5
1  5
4
 
4 0 0
6 5 4
Rys. 13. a) Tablica przejść  wyjść przykładowego układu, b) wykres redukcyjny układu  ze względu na
różnice w stanach wyjść odcinki łączące redukowane stany zostały narysowane linią przerywaną,
c) tablica przejść po połączeniu wierszy 1 i 5 oraz 2 i 6  tzw. zredukowana tablica programu
Z analizy wykresu redukcyjnego wynika, że łączenie stanów 1 i 5 oraz 2 i 6 prowadzi do projektu układu w
postaci układu Mealy ego. Jeżeli układ miałby być zaprojektowany jako układ Moore a to redukcja stanów
wewnętrznych byłaby niedopuszczalna.
Przykładowy układ zostanie najpierw zaprojektowany jako układ Mealy ego a następnie jako układ Moore a.
Układy cyfrowe f.2/24
Synteza przykładowego układu  układ Mealy ego
Zredukowana tablica programu układu Mealy ego ma 4 wiersze (są cztery stany wewnętrzne). Dwa
elementy pamięci dają możliwość zakodowania czterech stanów: q1 q2 = 00, q1 q2 = 01, q1 q2 = 10 oraz q1 q2 =
11. Załóżmy, że do realizacji bloku pamięci wystarczą elementy Q1 i Q2 (dwa elementy mogą nie wystarczyć
do realizacji układu o czterech stanach).
Po utworzeniu wykresu ilustrującego przejścia występujące w zredukowanej tablica programu (tzw. wykres
przejść) okazuje się, że kody 00, 01, 10 i 11 pozwalają opisać wierzchołki wykresu w taki sposób aby
wierzchołki połączone były opisane ciągami różniącymi się tylko na jednej pozycji  liczba elementów
pamięci jest więc wystarczająca.
a) X=(a,b) b) c) d)
X=(a,b) X=(a,b)
00 11
00 01 11 10
A
00 01 11 10 00 01 11 10
A q1q2
1,5 2,6

3
1,5
00  00 01 00  00 01
00 00

4
2,6
11  11 10 11  11 01
11 01
2  6
3
11  11 01 11  11 10
01 11
4 3
1  5
4
00  00 10 00  00 10
10 10
10 01
00 11
e)
Rys. 14. a) zredukowana tablica programu, b) wykres przejść,
1,5 2,6
c) tablica programu po zakodowaniu  wiersze są nieprawidłowo ułożone,
d) tablica programu po zakodowaniu i uporządkowaniu wierszy
 tablica stanów elementów pamięci,
4 3
e) alternatywny wykres przejść.
01 10
Układy cyfrowe f.2/25
Synteza przykładowego układu  układ Mealy ego
Tablicę stanów elementów wyjściowych otrzymuje się wykorzystując zredukowaną i pierwotną tablicę
programu. W kratkach, w których w tablicy zredukowanej występują stany stabilne wpisuje się wartości
stanów wyjściowych na podstawie tablicy pierwotnej. W kratkach w których występują stany niestabilne
wpisuje się wartość stanu wyjściowego jeżeli przy przejściu przez stan niestabilny stan wyjść układu się nie
zmienia lub    jeżeli stan wyjść się zmienia.
Y=(Z1Z2)
X=(a,b) X=(a,b) Y=(Z1Z2)
00 01 11 10
q1q2
00 01 11 10
00 01 11 10 Z1 Z2 00 01 11 10 A
A A
11  00 10
00
11  00
 1,5
  3 1 1 3
1 1,5
1   0 10
01
3  10
  4 1 1 2  6
2 3
11  00 01
11
11  00
2,6

2  6 4
3 1 0 2,6
10  1  0 01
4  01
1  5 1  5
4 0 1 4
 
3 0 0
5
: 1110 czyli 1
: 1011 czyli: 1
10
  : 0010 czyli  0
4 0 0
6
: 1000 czyli:  0
: 0111 czyli:  1
: 1101 czyli  1
01
: 0001 czyli 0 : 0100 czyli: 0
Kratka opisuje stan niestabilny, który pozwala przejść ze stanu do albo ze stanu do .
Przy przejściu stan wyjść zmienia się z  11 na  10 (stan pierwszego wyjścia się nie zmienia  więc
dla tego wyjścia należy przyjąć stan  1 , stan drugiego wyjścia się zmienia  więc można przyjąć dowolną
wartość stanu) stan wyjść można przyjąć jako  1  . Przy przejściu , stan wyjść można przyjąć jako  
0 (zmiana z  00 na  10 ). Ostatecznie stan wyjść w kratce trzeba przyjąć jako  10 .
Układy cyfrowe f.2/26
Synteza przykładowego układu  układ Mealy ego
Korzystając z tablic stanów elementów pamięci i elementów wyjściowych można zapisać wyrażenia logiczne
opisujące wartości sygnałów wyjściowych bloku pamięci i sygnałów wyjściowych całego układu.
ab ab ab
q1q2 00 01 11 10 q1q2 00 01 11 10 q1q2 00 01 11 10
00  00 01 0  0 0 0  0 1
00 00 00
11  11 01 1  1 0 1  1 1
01 01 01
11  11 10 1  1 1 1  1 0
11 11 11
00  00 10 0  0 1 0  0 0
10 10 10
Q1Q2 Q1 Q2
Q1 = a q2 + bq2 + q1q2 + abq1 Q2 = a q2 + bq2 + q1q2 + abq1
ab ab ab
q1q2 00 01 11 10 q1q2 00 01 11 10 q1q2 00 01 11 10
11  00 10 1  0 1 1  0 0
00 00 00
1   0 10 1   1
01 01 01   0 0
11  00 01 1  0 0 1  0 1
11 11 11
10  1  0 01 1   1
10   0 0
10
Y1Y2 Y1 Y2
Y1 = b �"(a + q1) Y2 = b �"(a + q1)
Układy cyfrowe f.2/27
Synteza przykładowego układu  układ Moore a
Z wykresy redukcyjnego (slajd 24) wynika, że projektując układ jako układ Moore a nie można zredukować
liczby stanów wewnętrznych układu. Tablica programu ma 6 wierszy (jest sześć stanów wewnętrznych).
Sześć stanów można zakodować przy pomocy trzech elementów Q1, Q2 i Q3. Wykres przejść pozwala na
ustalenie sposobu kodowania.
X=(a,b)
a) b) c)
X=(a,b)
010 011
00 01 11 10 Z1 Z2
A
00 01 11 10 Z1 Z2
A
000   001 1 1
1) 000
  3 1 1
1 110 111
011   010 1 1
2) 011
2   4 1 1
011  101 001 1 0
3) 001
2  6
3 1 0
000  110 010 0 1
4) 010
1  5 0 1
4
100 101
5) 100   100 101 0 0
 
3 0 0
5
000 001
6) 111   111 110 0 0
 
6 4 0 0
111 001  0
101
: 1000 czyli  0
 0
100 010 0 
110
: 0010 czyli  0
Rys. 15. a) tablica programu, b) wykres przejść,
c) tablica programu po zakodowaniu (niektóre z przejść nie mogą być wykonane bezpośrednio 
wymagałoby to zmiany stanu więcej niż jednego elementu pamięci  przejścia takie dzieli się na dwa etapy
wprowadzając się stany pośrednie np.: przejście z tzn. z 001 do 111 należy zamienić na przejścia z
001 do 101 i z 101 do 111, dodatkowo należy określić wartości wyjść w stanach przejściowych).
Układy cyfrowe f.2/28
Synteza przykładowego układu  układ Moore a
Po uporządkowaniu wierszy zakodowanej tablicy programu (rys. 15 c) zgodnie z kodem Graya można
utworzyć tablice stanów elementów pamięci i elementów wyjściowych a na ich podstawie zapisać wyrażenia
logiczne opisujące wartości sygnałów wyjściowych bloku pamięci i sygnałów wyjściowych całego układu.
ab ab ab ab
Z1 Z2 q
q q
q q q
Z1 Z2
00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10
000   001 1 1 0
000 000   0 0 0 1 1
000   0
000   1
000 000
011  101 001 1 0 0
001 001  1 0 1 1 1 0
001  0 0
001  1 1
001 001
011   010 1 1 0
011 011   0 1 1 1 1
011   1
011   0
011 011
000  110 010 0 1 0
010 010  1 0 0 0 0 1
010  1 1
010  0 0
010 010
100 010 0  110   1 0
110 110   0 1 0
110   0 0
110 110 
111   111 110 0 0 0 0
111   1 1
111   1 1
111   1 0
111 111
111 001  0
101 101   1 0 0
101   1 0
101   1 1
101  101
100   100 101 0 0 0 0
100   1 1
100   0 0
100   0 1
100 100
Q1 Q2 Q3
Q1 = b + q1 q2 q3 + q1 q2 q3 Q2 =q2 q3 + a q3 + abq2 + a q1 q2 + b q1 q3 Q3 =q2 q3 + bq3 + abq2 + a q3
Z1 =q1 q2 + q1 q3 Z2 =q1 q2 + q1 q3
Rys. 16. Tablice stanów elementów pamięci i elementów wyjściowych układu z przykładu 3.
Układy cyfrowe f.2/29
Analiza i synteza przykładowego układu sekwencyjnego
Przykład 4. Zbadać działanie układu przedstawionego na poniższym schemacie.
a
Na podstawie schematu można zapisać
wyrażenia logiczne elementów pamięci tego
q1
układu tzn.:
Q1
Q1 = a q1 + q1 q2 + a q2
q2
Q2 = a q2 + a q1 + q1 q2
Sygnał na wyjściu układu jest równy
Y=Q2
sygnałowi wyjściowemu drugiego elementu
pamięci:
Y = Q2
Na podstawie powyższych wyrażeń można
zapisać osobne tablice stanów dla elementów
Q1, Q2 i Y lub jedną zbiorczą.
Rys. 17. Schemat logiczny przykładowego układu.
a a
a a
q1q2 Y q1q2 0 1 Y
q1q2 0 1 q1q2 0 1
0 00 01 0
0 0 0 1 00 00
00 00
1 11 01 1
1 0 1 1 01 01
01 01
1 11 10 1
1 1 1 0 11 11
11 11
0 00 10 0
0 1 0 0 10 10
10 10
Q1 Q2
Q1 Q2
Układy cyfrowe f.2/30
Analiza i synteza przykładowego układu sekwencyjnego
Analiza tablicy stanów elementów Q1 i Q2 pozwala zidentyfikować wewnętrzne stany stabilne (Q1Q2 = q1q2)
i niestabilne (Q1Q2 `" q1q2) układu. Stany niestabilne ulegają automatycznym zmianom  bez zmian stanu
wejść. Stan niestabilny może prowadzić do stanu stabilnego lub niestabilnego  wartości Q1Q2 wyznaczają
kolejny stan q1q2 układu.
W tablicy b) oznaczone zostały stany:
a) b)
stabilne (symbol �%) i niestabilne (symbol " ).
a a
Na podstawie wartości Q1Q2, zaznaczone zostały przejścia ze
q1q2 0 1 q1q2 0 1
stanów niestabilnych.
00 01 �% "
00 00
Jeśli układ znajduje się w stanie wewnętrznym 00, a wejście a = 0
11 01 " �%
01 01
to stan ten można zmienić zmieniając stan wejścia na a = 1.
Zmiana ta powoduje przejście układu do niestabilnego stanu 01 z
11 10 �% "
11 11
którego automatycznie układ przechodzi do stabilnego stanu 01.
00 10 " �%
10 10
Zmiana wejścia na a = 0 przenosi układ do niestabilnego stanu 11
Q1 Q2 Q1 Q2
a następnie do stabilnego stanu 11 itd.
0 1
a
1
Oznaczając stany wewnętrzne kolejnymi liczbami q1q2 0 1 Y
1 2
naturalnymi:
2 0
1
 stan 00,  stan 01,  stan 11,  stan 10
0 0
3
2 1
można tablice stanów zapisać w postaci tablicy
4 1
3
1
przejść  wyjść, a następnie na jej podstawie
4 3
1
4 0
utworzyć graf przejść.
0 1
Układy cyfrowe f.2/31
Analiza i synteza przykładowego układu sekwencyjnego
Otrzymany graf odpowiada grafowi układu z przykładu 1 (lampa włączana i wyłączana jednym przyciskiem)
o ile przyjąć, że stany od A1 do A4, zostały zakodowane przy pomocy kolejnych liczb.
Spróbujmy teraz wykonać zadanie odwrotne  syntezę takiego samego układu  tylko z inaczej
zakodowanymi stanami. Nowy sposób kodowania przedstawiony został na wykresie przejść układu
(kodowanie jest nieprawidłowe  wierzchołki które na wykresie są połączone opisane są ciągami różniącymi
się więcej niż jedną pozycją  wierzchołek 1 i 4 oraz 2 i 3).
a) b) c) d)
a a a
00 01
q1q2 0 1 Y q1q2 0 1 Y q1q2 0 1 Y
1 2
00 01 0 00 01 0
1 2 0 00 00
3 1 10 01 1 10 01 1
2 01 01
4 1 10 11 1 00 11 0
3 10 11
4 3
1 0 00 11 0 10 11 1
4 11 10
11 10
Q1 Q2
Rys. 18. a) tablica przejść  wyjść, b) wykres przejść c) tablica po zakodowaniu  wiersze są nieprawidłowo
ułożone, d) tablica po zakodowaniu i uporządkowaniu wierszy  tablica stanów elementów pamięci i
elementu wyjściowego układu.
Układy cyfrowe f.2/32
Wyścigi i zamknięty cykl drgań
Błędne kodowanie stanów prowadzi do powstawania niekorzystnych zjawisk w układach
sekwencyjnych. Zjawiskami tymi są wyścigi i tzw. zamknięty cykl drgań.
Wyścig występuje wtedy, gdy zmiana stanu wewnętrznego układu wymaga równoczesnej zmiany
więcej niż jednego elementu pamięci. Równoczesna zmiana jest w praktyce niemożliwa. W
przypadku dwóch elementów może się np. zdarzyć, że
pierwszy element zmieni swój stan wcześniej,
drugi element zmieni swój stan wcześniej,
obywa zmienią stan jednocześnie.
Układ będzie mógł przejść ze stanu niestabilnego do stabilnego na kilka sposobów. Jeżeli w
każdym z możliwych przypadków osiągnie on ten sam stan stabilny to wyścig taki nazywany jest
wyścigiem niekrytycznym. Jeżeli przejście może nastąpić do różnych stanów stabilnych to
wyścig jest wyścigiem krytycznym.
Zamknięty cykl drgań występuje gdy układ ze stanu niestabilnego nie może przejść do żadnego
ze swoich stanów stabilnych. Jedyną możliwością przerwania drgań jest zmiana stanu wejść
układu.
Układy cyfrowe f.2/33
Analiza i synteza przykładowego układu sekwencyjnego
Nieprawidłowe kodowanie stanów przykładowego układu doprowadziło do możliwości powstania wyścigu
krytycznego i nawet zamkniętego cyklu drgań.
a
0 1
a) b)
q1q2
a
q1q2 0 1 Y
�% "
00
00 01 0
00
" �%
01
10 01 1
01
00 11 0
11
" �%
11
10 11 1
10
Q1 Q2
�% "
10
Q1 Q2
Rys. 19. a) tablica stanów, b) tablica stanów z zaznaczonymi stanami stabilnymi, niestabilnymi oraz
możliwymi przejściami pomiędzy nimi.
Po zmianie stanu wejść z a = 1 na a = 0 powinno nastąpić przejście ze stanu stabilnego 01 do stanu
niestabilnego 10. Przejście takie wymaga zmiana stan dwóch elementów pamięci. Mogą więc wystąpić
przypadki zmiany stanu na stan 11, 00 albo 10 (zaznaczone przerywanymi czerwonymi strzałkami). Stany 00
i 10 są stanami stabilnymi (ale różnymi)  więc w tym przypadku wystąpi wyścig krytyczny. Zmiana stanu na
stan 11 prowadzi do wyścigu (zaznaczony przerywanymi niebieskimi strzałkami), który może zakończyć
stanami stabilnymi 00 i 10. Może jednak nastąpić powrót do stanu 01 i dalej znowu może wystąpić stan 11
itd.  czyli układ może wpaść w drgania.
Układy cyfrowe f.2/34