TC Moduł 9

Układy asynchroniczne

Struktura sekwencyjnego układu asynchronicznego jest podobna do struktury układu synchronicznego (por. moduł 7 plansza 5). Istotną różnicą jest brak wejścia zegarowego clk. Z tego powodu pamięć układu mogą stanowić przerzutniki (automaty elementarne) nie synchronizowane lub elementy opóźniające. Powstaje zatem pytanie: co – wobec braku sygnału zegarowego – wyznacza kolejne takty pracy układu, powodując zmiany jego stanów wewnętrznych? Czynnikiem powodującym te zmiany może być tylko zmiana stanów wejść. Taka sytuacja jest pokazana na rysunku fragmentu grafu. Pod wpływem litery wejściowej

X_{i}\,

układ znalazł się w stanie

S_{a}\,

. Pozostaje w nim tak długo, aż na wejściu pojawi się inna litera –

X_{j}(j\in i)\,

. Wówczas układ może przejść do stanu

S_{b}\,

. Przykładowe stany

S_{a}\,

i

S_{b}\,

nazywa się stanami stabilnymi. Należy przyjąć, że w układzie asynchronicznym wszystkie stany są stanami stabilnymi, a zmiana stanu może nastąpić tylko w wyniku zmiany stanu wejść.

Najprostszym asynchronicznym układem sekwencyjnym jest przerzutnik asynchroniczny typu

SR\,

. Na planszy podana jest tablica przejść przerzutnika

SR\,

. Z tablicy tej wyznaczamy tzw. funkcję charakterystyczną przerzutnika. Funkcja ta podaje zależność stanu następnego

Q\,

od stanu bieżącego i sygnałów na wejściach

S\,

,

R\,

. Wyrażenie boolowskie tej funkcji przekształcamy (wg prawa De Morgana) do postaci zawierającej funktory

NAND\,

. Odpowiedni schemat logiczny przerzutnika

SR\,

podany jest na rysunku.

Zaprojektujemy układ asynchroniczny, którego działanie jest opisane na planszy. Najpierw wykażemy, że automat działa zgodnie z grafem pokazanym na rysunku. Załóżmy, że na wejściu jest wektor

00\,

; układ jest w stanie stabilnym

1\,

z wyjściem

0\,

(pętla z wektorem wejściowym

00\,

). W tym stanie (zgodnie z założeniem) może na wejściu pojawić się wektor

01\,

– przechodzimy do stanu

2\,

(wyjście

0\,

) lub wektor

10\,

– przechodzimy do stanu

3\,

(wyjście

0\,

). W stanie

2\,

na wejściu może się pojawić wektor

11\,

– przechodzimy do stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 4\,} , a na wyjściu jest stan Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1\,} , gdyż ta sytuacja oznacza, że na wejściu kolejno pojawiały się wektory Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 00, 01, 11\,} . Jeśli w stanie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 2\,} pojawi się Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 00\,} – wracamy do stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1\,} . Należy teraz rozpatrzyć sytuację w stanie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 3\,} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 4\,} . W stanie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 3\,} po przyjściu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 00\,} wracamy do stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1\,} , a po przyjściu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 11\,} przechodzimy do stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 5\,} (z wyjściem Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0\,} ). W stanie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 4\,} po przyjściu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 10\,} można przejść do już istniejącego stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 3\,} , zaś po przyjściu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 01\,} trzeba przejść do nowego stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 6\,} (nie można przejść do stanu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 2\,} , gdyż sekwencja wejściowa Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle ...01,11,01,11,...\,} powodowałaby by wygenerowanie na wyjściu sekwencji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0101...\,} ). Do zamknięcia grafu pozostaje tylko uzupełnienie przejść ze stanów Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 5\,} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 6\,} . Bezpośrednio z uzyskanego grafu tworzymy tablicę przejść-wyjść tego automatu. Kółka w tej tablicy oznaczają stany stabilne. Należy zwrócić uwagę, że w powyższym grafie wszystkie stany są stanami stabilnymi.

Następnym etapem syntezy układów asynchronicznych jest minimalizacja liczby stanów automatu, która przebiega tak samo, jak w przypadku układów synchronicznych. Łatwo sprawdzić, że na podstawie uzyskanej tablicy przejść wyjść można wyznaczyć zbiór par zgodnych: Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{1,2\}} ,

\{1,3\}

,

\{3,5\}

,

\{3,6\}

,

\{5,6\}

. Stąd maksymalne klasy zgodne są następujące: Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{1,2\}, \{1,3}, \{4\} \{3,5,6\}} . Warunek pokrycia i zamknięcia spełniają zbiory:

\{1,2\},\{4\}\{3,5,6\}

. Oznaczając stany wewnętrzne kolejno literami

A\,

,

B\,

i

C\,

, uzyskujemy tablicę przejść wyjść automatu minimalnego.

W realizacji automatu asynchronicznego, podobnie jak w realizacji automatu synchronicznego, występują dwa etapy: kodowanie stanów i synteza strukturalna, czyli wyznaczenie funkcji wzbudzeń przerzutników. Oba te procesy w odniesieniu do układów asynchronicznych mają swoją specyfikę spowodowaną brakiem zewnętrznej synchronizacji.

Aby przeanalizować zjawiska zachodzące w układzie asynchronicznym przeprowadzimy syntezę automatu minimalnego. Stanom $A\,$ , $B\,$ , $C\,$ tego automatu przyporządkujemy wektory kodowe odpowiednio $00,01,10\,$ . Otrzymujemy zakodowaną tablicę przejść-wyjść, uwzględniającą nie wykorzystany wektor stanu $11\,$ . Na planszy pokazano również graf stanów automatu minimalnego z odpowiednimi wektorami kodowymi dla poszczególnych stanów.

Zaprojektowany układ będzie działał poprawnie, jeżeli czasy działania elementów opóźniających

\Delta \,

są jednakowe, to znaczy

\Delta _{1}=\Delta _{2}

. W rzeczywistości funkcja opóźnienia

\Delta \,

jest realizowana w układzie kombinacyjnym przez opóźnienia (czas przenoszenia) bramek, realizujących ten układ. Dlatego sygnały

Q1,Q2\,

na wyjściach tego układu nie zmieniają swych wartości jednocześnie. Taka sytuacja może mieć wpływ na poprawność działania układu zwłaszcza w takim przypadku, w którym wektory kodowe sąsiednich stanów różnią się na więcej niż jednej pozycji. Właśnie tak jest w grafie automatu minimalnego przy przejściu ze stanu

B\,

(wektor kodowy

01\,

) do stanu

C(10)\,

) . Na planszy rozważono tę sytuację. Dla

\Delta _{1}<\Delta _{2}

(

\Delta _{1},\Delta _{2}

– czasy opóźnienia sygnałów

q_{1},q_{2}\,

) stan

01\,

pod wpływem wejść

01\,

zmieni się na stan niestabilny

11\,

, po czym (zgodnie z tablicą przejść) układ przejdzie do stanu stabilnego

10\,

, zgodnego z założeniem. Takie przejście nazywa się wyścigiem niekrytycznym. Jeżeli

\Delta _{1}>\Delta _{2}

, to dla wejść

01\,

układ przejdzie do stanu

00\,

, ale stan ten dla wejść

01\,

jest stabilny; układ nie przejdzie do stanu

10\,

. Takie przejście nazywa się wyścigiem krytycznym; powoduje ono nieprawidłową pracę układu. Aby zapobiec tej sytuacji, można odpowiednio skorygować graf stanów, zastępując bezpośrednie przejście ze stanu

01\,

do stanu

10\,

pod wpływem wejść

01\,

– przejściem przez stan niestabilny

11\,

.

Dla

\Delta _{1}<\Delta _{2}

stan

01\,

pod wpływem wejść

10\,

zmieni się na stan niestabilny

11\,

, po czym (zgodnie z tablicą przejść) układ przejdzie do stanu stabilnego

10\,

, zgodnego z założeniem. Jeżeli

\Delta _{1}>\Delta _{2}

, to dla wejść

10\,

układ przejdzie do stanu

00\,

, po czym do stanu

10\,

, też zgodnego z założeniem. W obu przypadkach – wyścig niekrytyczny.

Aby uniknąć analizy poprawności działania realizacji układu asynchronicznego po jego zaprojektowaniu, można automat (minimalny) odpowiednio zakodować w taki sposób, aby wektory kodowe sąsiednich stanów różniły się tylko na jednej pozycji.

Uwzględniając przeprowadzone rozważania łatwo stwierdzić, że graf automatu należy uzupełnić o stan niestabilny zakodowany

11\,

, co prowadzi do zmodyfikowanej tablicy przejść podanej na planszy.

Zmodyfikowaną tablicę rozpisujemy na poszczególne funkcje wzbudzeń

Q1'\,

oraz

Q2'\,

.

Wyznaczone na podstawie tych tablic funkcje

Q_{1}^{'}\,

i

Q_{2}^{'}\,

(również

y\,

), opisują realizację układu kombinacyjnego, nazywaną realizacją ze sprzężeniem zwrotnym:

${\begin{matrix}y=Q_{2}&Q_{1}^{'}=Q_{1}x_{1}+Q_{1}x_{2}+Q_{2}{\overline {x}}_{1}+x_{1}{\overline {x}}_{2}&Q_{2}^{'}={\overline {Q}}_{1}x_{1}x_{2}+{\overline {Q}}_{1}Q_{2}x_{2}\end{matrix}}$

gdzie składnik $Q_{1}x_{1}\,$ wprowadzono w celu uniknięcia szkodliwego zjawiska, zwanego hazardem. Wprowadzenie tego składnika zapobiegnie pojawieniu się na wyjściu $Q_{1}\,$ krótkiego impulsu o wartości logicznej $0\,$ , który może powstać przy zmianie sygnału $x_{2}\,$ z $1\,$ na $0\,$ .

Plansza wyjaśnia powstawanie zjawiska hazardu. W układach asynchronicznych funkcje wzbudzeń muszą być realizowane w taki sposób, aby nie występował hazard statyczny.

W celu likwidacji hazardu wyrażenia boolowskie funkcji wzbudzeń należy uzupełnić o składnik (nadmiarowy), odpowiadający pętli na tablicy Karnaugha, w taki sposób, aby każde dwie sąsiednie jedynki były objęte wspólną pętlą.

Mając świadomość, że w realizowanym automacie zlikwidowaliśmy przyczyny wszystkich szkodliwych zjawisk, możemy przystąpić do narysowania schematu logicznego tego automatu.

Z asynchronicznych przerzutników typu

SR\,

(

{\overline {S}}\,{\overline {R}}

) są budowane przerzutniki synchroniczne typu

D\,

,

T\,

i

JK\,

. Istnieją różne mechanizmy synchronizacji przerzutników: od najprostszej – szerokością impulsu (tzw. latch), przez synchronizację dwustopniową (master-slave), aż po synchronizację zboczem przebiegu zegarowego. Synchronizacja zboczem polega na tym, że stan wejść przerzutnika oddziałuje na jego stan wewnętrzny (i tym samym na stan wyjść) tylko w momencie wystąpienia zmiany, np. z

0\,

na

1\,

, w przebiegu zegarowym.

Przerzutniki tego typu mają prostą budowę, ale mogą służyć tylko do przechowywania (zatrzaskiwania) informacji. Nie mogą służyć do budowy układów sekwencyjnych.

Prawidłowa synchronizacja powinna działać tak, aby w czasie trwania okresu przebiegu zegarowego sygnał wejściowy przerzutnika był odczytywany jeden raz, a stan przerzutnika zmieniał się także jeden raz – niezależnie od zmiany sygnałów wejściowych. Mechanizm ten zostanie dokładnie omówiony na przykładzie, którego celem będzie zaprojektowanie asynchronicznego układu realizującego funkcje przerzutnika typu

D\,

synchronizowanego narastającym (dodatnim) zboczem przebiegu zegarowego.

Najczęściej do realizacji takiego przerzutnika przyjmuje się układ o schemacie blokowym zbudowanym z automatu sterującego i asynchronicznego przerzutnika

{\overline {S}}\,{\overline {R}}

. Automat sterujący o wejściach

D\,

i

clk\,(c)\,

steruje asynchronicznym przerzutnikiem

{\overline {S}}\,{\overline {R}}

, którego praca jest opisana w tablicy podanej na planszy. Przerzutnik ten może zmienić stan wyjścia

Q\,

z

0\,

na

1\,

, jeśli na wyjściu

Y_{1}\,

automatu sterującego pojawi się

0\,

, lub z

1\,

na

0\,

, jeśli

0\,

pojawi się na wyjściu

Y_{2}\,

(jednoczesne pojawienie się sygnału

0\,

na wyjściu

Y_{1}\,

i

Y_{2}\,

jest niedopuszczalne).

Graf stanów typu Moore’a automatu sterującego pokazano na niniejszej planszy. Stan

1\,

jest stanem oczekiwania. Jeśli w tym stanie na wejściu

D\,

jest

1\,

(wektor wejściowy

10\,

), to zmiana sygnału zegarowego

clk\,

z

0\,

na

1\,

powoduje przejście automatu do stanu

2\,

i pojawienie się na wyjściach

Y_{1}\,

,

Y_{2}\,

wektora

01\,

, co spowoduje włączenie przerzutnika

{\overline {S}}\,{\overline {R}}

(jeśli uprzednio był wyłączony). Jeśli w stanie

1\,

na wejściu

D\,

jest

0\,

(wektor wejściowy

00\,

), to zmiana sygnału zegarowego

clk\,

z

0\,

na

1\,

powoduje przejście automatu do stanu

3\,

i pojawienie się na wyjściach

Y_{1}\,

,

Y_{2}\,

wektora

10\,

, co spowoduje wyłączenie przerzutnika

{\overline {S}}\,{\overline {R}}

(jeśli uprzednio był włączony). Powrót do stanu

1\,

ze stanów

2\,

i

3\,

następuje po zmianie sygnału

clk\,

z

1\,

na

0\,

.

Na podstawie narysowanego grafu automatu tworzymy tablicę przejść-wyjść automatu sterującego, którą następnie kodujemy w sposób pokazany na planszy.

Zakodowaną tablicę rozpisujemy na dwie tabelki dla poszczególnych funkcji

Q_{1}^{'}\,

i

Q_{2}^{'}\,

.

Z tabelek tych można wyznaczyć wyrażenia boolowskie dla $Q_{1}^{'}\,$ i $Q_{2}^{'}\,$ .

Ostatecznie

${\begin{matrix}Y_{1}=Q_{1},&Y_{2}=Q_{2}\end{matrix}}$

${\begin{matrix}Q_{1}^{'}={\overline {c}}+q_{1}{\overline {D}}+{\overline {q}}_{2},&Q_{2}^{'}={\overline {c}}+q_{2}D+{\overline {q}}_{1}\end{matrix}}$

Na tej podstawie i po zastosowaniu prawa De Morgana uzyskujemy schemat logiczny układu zaprojektowanego na elementach typu $NAND\,$ .

Cały proces syntezy sekwencyjnego układu asynchronicznego prezentujemy raz jeszcze na innym przykładzie, ale tym razem z oszczędnymi komentarzami. Zadanie to słuchacz wykładu może potraktować jako zadanie treningowe. Plansze 24 do 28 prezentują kluczowe etapy syntezy.