TC Moduł 7

From Studia Informatyczne

Grafika:TC_M7_Slajd1.png Układy synchroniczne

Grafika:TC_M7_Slajd2.png Modelem matematycznym układu sekwencyjnego jest automat. Automat jest definiowany przez określenie:
  • zbioru liter wejściowych X (lub V) i wyjściowych Y,
  • zbioru stanów wewnętrznych S,
  • funkcji przejść (oznaczanej \delta),
  • funkcji wyjść (oznaczanej \lambda).

Grafika:TC_M7_Slajd3.png W formalnym zapisie automat A określa się jako piątkę <S, X, Y, \delta , \lambda>, gdzie funkcja przejść jest definiowana jako odwzorowanie \delta : S \times X \rightarrow S, natomiast funkcja wyjść \lambda jest odwzorowaniem \lambda : S \times X \rightarrow Y (tzw. automat Mealy’ego) lub jako \lambda : S \rightarrow Y (tzw. automat Moore’a).

Ważnym pojęciem w układach logicznych jest pojęcie automatu zupełnego i niezupełnego. Automat, określony funkcjami przejść \delta i wyjść \lambda nazywamy automatem zupełnym, jeśli dziedziny tych funkcji są równe zbiorom S \times 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_\delta \subset S \times X, D_\lambda \subset S \times X lub D_\lambda \subset S, to taki automat nazywamy niezupełnym.


Grafika:TC_M7_Slajd4.png Funkcje przejść-wyjść jest najwygodniej przedstawiać za pomocą tablicy. Tablice przejść-wyjść przykładowych automatów podane na planszy reprezentują automat Mealy’ego oraz automat Moore’a. Tablicom tym odpowiadają grafy automatów.

Grafika:TC_M7_Slajd5.png Techniczną realizacją automatu jest synchroniczny układ sekwencyjny zbudowany z układu kombinacyjnego i pamięci. Układ kombinacyjny automatu jest układem wielowyjściowym, wytwarzającym sygnały wyjściowe automatu y_1,..., y_m oraz sygnały wzbudzające układ pamięciowy q_1,..., q_k. Wejściami układu kombinacyjnego są sygnały wejściowe automatu x_1,..., x_n oraz sygnały wyjściowe Q_1,..., Q_p układu pamięciowego. Układ kombinacyjny jest opisany tablicami wyjść i wzbudzeń (sposób tworzenia tablic wzbudzeń poznamy w dalszej części wykładu).

Grafika:TC_M7_Slajd6.png Pamięć automatu jest zbudowana z tzw. przerzutników – automatów elementarnych synchronizowanych specjalnym sygnałem zegarowym oznaczonym clk.

Grafika:TC_M7_Slajd7.png Stosowane przerzutniki mają jedno lub dwa wejścia (poza wejściem zegarowym i wejściami ustawiającymi statycznie). Wejścia te w zależności od typu przerzutnika są oznaczane: D, T, SR i JK. Ich tablice przejść są przedstawione kolejno w tablicach na planszy .

Grafika:TC_M7_Slajd8.png Przerzutnik jest określony:
  • tablicą przejść,
  • równaniem charakterystycznym,
  • tablicą wzbudzeń.

Grafika:TC_M7_Slajd9.png Podane na planszy tablice przejść przerzutników interpretujemy następująco.

Przerzutnik typu D jest to element opóźniający sygnał wejściowy o takt. Przerzutnik typu T przy podaniu jedynki na wejście T zmienia w kolejnym takcie swój stan na przeciwny. Przerzutnik typu SR jest to przerzutnik z dwoma wejściami: ustawiającym (Set) i zerującym (Reset), czyli przy S = 1, R = 0 przerzutnik przechodzi do stanu Q = 1, przy S = 0, R = 1 przerzutnik przechodzi do stanu Q = 0, przy czym podawanie jedynek na oba wejścia jednocześnie jest zabronione. Przerzutnik JK działa jak SR, gdy jedynka jest podana na co najwyżej jedno wejście i jak typu T, gdy jedynka jest podana na oba wejścia. Zatem na wejścia przerzutnika JK może być podana dowolna kombinacja wartości sygnałów J i K, przy czym zawsze przy sygnałach J = 1, K = 0 przerzutnik ten „zapala się”, to znaczy przechodzi do stanu 1, zaś przy sygnałach J = 0, K = 1 przerzutnik „gaśnie”, to znaczy przechodzi do stanu 0. Przy sygnałach J = K =1 przerzutnik zmienia stan na przeciwny.


Grafika:TC_M7_Slajd10.png Przy projektowaniu układów synchronicznych posługujemy się tzw. tablicami wzbudzeń przerzutników. Określają one jakie muszą być sygnały wejściowe przerzutnika, aby uzyskać określoną zmianę stanu (przejście ze stanu bieżącego Q do następnego Q’).

Grafika:TC_M7_Slajd11.png Tablice przejść i tablice wzbudzeń przerzutników nie określają bezpośrednio roli sygnału zegarowego. Dlatego na kolejnych planszach omówimy pracę przerzutnika z uwzględnieniem sygnału zegarowego.

Na planszy pokazane są przebiegi sygnałów wejściowych przerzutnika typu D oraz sygnał na jego wyjściu Q.


Grafika:TC_M7_Slajd12.png Te same przebiegi: tzn. informacyjny oraz zegarowy podajemy na wejścia przerzutnika typu T. ale w tym przypadku na wyjściu Q tego przerzutnika powstaje inny przebieg.

Grafika:TC_M7_Slajd13.png W celu lepszego porównania obie sytuacje podane są na jednej planszy.

Grafika:TC_M7_Slajd14.png Synteza układów sekwencyjnych jest złożonym 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)

Grafika:TC_M7_Slajd15.png Omawianie procesu syntezy układów sekwencyjnych rozpoczynamy od etapu syntezy kombinacyjnej. Jest to najważniejszy a zarazem najobszerniejszy etap całego procesu syntezy. Polega on (jak to pokazano na rysunku na planszy) na obliczaniu funkcji sterujących wejściami przerzutników (funkcje wzbudzeń) oraz na obliczaniu funkcji wyjściowych. Warto podkreślić różnicę w obliczaniu funkcji wyjściowych dla automatów typu Moore’a a i typu Mealy’ego. Otóż w pierwszym przypadku funkcje te są zależne tylko od wyjść Q przerzutników, natomiast w drugim, są zależne zarówno od wyjść Q jak i od wejść zewnętrznych X.

Grafika:TC_M7_Slajd16.png Syntezę kombinacyjną omówimy na przykładzie automatu, który dla ustalenia uwagi nazywać będziemy detektorem sekwencji. Jest to automat typu Mealy’ego, o trzech stanach wewnętrznych oznaczonych A, B, C, jednym sygnale wejściowym x oraz jednym sygnale wyjściowym. Pierwszą czynnością jaką należy wykonać jest zatem kodowanie stanów wewnętrznych. Kodowanie stanów polega na przyporządkowaniu abstrakcyjnym symbolom stanów A, B, C ciągów binarnych o możliwie najmniejszej liczbie bitów. Dla trzech stanów do jednoznacznego zakodowania wystarczą dwa bity. Dlatego przyjmiemy, że A = 00, B = 01, C = 11. Przyjęcie kodowania determinuje jednocześnie liczbę przerzutników układu sekwencyjnego. Oznaczając przerzutniki Q1, Q0 uzyskujemy zakodowaną tablicę przejść wyjść jak na planszy. Tablicę tę podajemy łącznie z nadmiarowym stanem wewnętrznym. Tak uzyskana tablica posłuży do obliczania funkcji wzbudzeń dla różnych przerzutników. Naszym zadaniem będzie realizacja tego automatu w trzech różnych strukturach: z zastosowaniem przerzutników typu D, T oraz JK.

Grafika:TC_M7_Slajd17.png Najpierw przerzutniki typu D. Zgodnie z tym co powiedzieliśmy zakodowana tablica reprezentuje dwa przerzutniki. Zatem w celu obliczenia funkcji wzbudzeń tablicę tę należy „rozpisać” na dwie tabelki odpowiadające poszczególnym przerzutnikom Q1 i Q0. Uzyskuje się w ten sposób oddzielne tablice wzbudzeń dla każdego przerzutnika. Są one zapisane w formie tabelek Karnaugha, a więc można na nich zakreślać pętelki w celu uzyskania minimalnych wyrażeń boolowskich dla funkcji wzbudzeń D1 i D0. W przypadku przerzutników typu D funkcje wzbudzeń są tożsame z funkcjami stanu następnego oznaczonym Q1’ oraz Q0’.

Również bezpośrednio z podanej tabelki obliczamy funkcję wyjściową Y.


Grafika:TC_M7_Slajd18.png Jak widać schemat logiczny tak zaprojektowanego układu jest zbudowany z dwóch przerzutników, do których wejść sterujących D1 i D0 dołączone są wyjścia układów kombinacyjnych realizujących funkcje wzbudzeń oraz funkcję wyjściową jakie obliczyliśmy na poprzedniej planszy.

Grafika:TC_M7_Slajd19.png Przystępujemy do realizacji z przerzutnikami typu T. W tym przypadku uzyskane poprzednio tabelki dla funkcji stanu następnego Q1’ i Q0’ należy dodatkowo przekształcić w celu uzyskania tablic wzbudzeń dla przerzutników T1 i T0. Transformacji takiej dokonujemy na podstawie tablicy wzbudzeń przerzutnika T. W rezultacie uzyskujemy tablice dla funkcji wzbudzeń T1 i T0. Są one w formie tabelek Karnaugha, zatem po zakreśleniu pętelek bezpośrednio obliczamy wyrażenia boolowskie dla T1 i T0.

Grafika:TC_M7_Slajd20.png Podobnie jak poprzednio schemat logiczny tak zaprojektowanego układu jest zbudowany z dwóch przerzutników, do których wejść sterujących T1 i T0 dołączone są wyjścia układów kombinacyjnych realizujących funkcje wzbudzeń oraz funkcję wyjściową jakie obliczyliśmy na poprzedniej planszy. Funkcja wyjściowa nie uległa zmianie.

Grafika:TC_M7_Slajd21.png Nieco bardziej skomplikowane jest obliczanie funkcji wzbudzeń dla przerzutników JK. W tym przypadku każdą tabelkę funkcji stanu następnego tj,. Q1’ oraz Q0’ należy przekształcić na dwie tabelki: jedną dla wejścia J, a drugą dla wejścia K. Oczywiście podobnie jak poprzednio odpowiednie wartości sygnałów binarnych jakie należy wpisywać do poszczególnych kratek tabelek wzbudzeń uzyskujemy z tablicy wzbudzeń dla JK. W rezultacie powstają cztery tabelki wzbudzeń: dla J1, K1 oraz dla J0, K0. Obliczone na ich podstawie funkcje wzbudzeń posłużą do narysowania schematu logicznego.

Grafika:TC_M7_Slajd22.png I w ten sposób powstaje schemat logiczny automatu zwanego detektorem sekwencji. Tym razem w realizacji na przerzutnikach typu JK.

Grafika:TC_M7_Slajd23.png Omówiony przykład syntezy układu dla detektora sekwencji jest zbyt prosty. Dla bardziej skomplikowanego treningu w projektowaniu sekwencyjnych układów cyfrowych omówimy syntezę licznika mod 5 ze sterowaniem. Naszym zadaniem jest zaprojektowanie licznika pracującego w trzech różnych trybach, a mianowicie: liczenie do przodu, liczenie do tyłu oraz zerowanie. Wybór tych trybów będzie dokonywany sygnałami sterującymi x_1 i x_2.

Pierwszą czynnością jest formalne zapisanie działania układu w postaci tablicy przejść wyjść. Jest to czynność, którą zgodnie z klasyfikacją etapów syntezy automatów zaliczamy do etapu syntezy abstrakcyjnej. Oznaczając dla licznika mod 5 (czyli zliczającego do 5) stany wewnętrzne wg naturalnego kodu binarnego: S0, S1,..., S4 wymienione trzy tryby pracy możemy zapisać w formie tabelki jak na planszy. Kolejny etap syntezy to kodowanie. Do zakodowania mamy zarówno stany wewnętrzne s0 do S4, jak też litery wejściowe a, b, c. Sposób kodowania podany jest w tabelce z prawej strony planszy.


Grafika:TC_M7_Slajd24.png Uzyskaną tabelkę należy zapisać w formie dogodnej do dalszych obliczeń. W tym celu dla oznaczenia poszczególnych wierszy i kolumn tej tablicy przyjmujemy kod Gray’a. Oczywiście chcąc, aby tablica taka jak najwierniej odpowiadała tablicy Karnaugha, niektóre wiersze będą miały nieokreślone stany następne. Uzyskana tablica reprezentuje (łącznie) trzy funkcje stanu następnego Q2’, Q1’, Q0’.

Grafika:TC_M7_Slajd25.png W celu obliczenia funkcji wzbudzeń należy uzyskaną tablicę rozpisać na trzy tabelki. Reprezentują one poszczególne przerzutniki tj. ich stany następne, a w przypadku przerzutników typu D są to jednocześnie funkcje wzbudzeń.

Grafika:TC_M7_Slajd26.png Mając zatem tabelki wzbudzeń poszczególnych przerzutników podane w formie tabelek Karnaugha możemy bezpośrednio z tych tabelek wyznaczyć odpowiednie wyrażenia boolowskie na funkcje wzbudzeń D2, D1, D0. W celu łatwiejszej interpretacji pętelek zakreślanych na tabelkach, pętelki i odpowiadające im iloczyny zmiennych zakreślono takimi samymi kolorami.

Grafika:TC_M7_Slajd27.png Proces projektowania licznika jest jeszcze bardziej skomplikowany dla realizacji na przerzutnikach typu JK. W tym przypadku każdą uzyskaną poprzednio tabelkę stanu następnego należy rozpisać na dwie oddzielne dla sterowania J oraz K.

Grafika:TC_M7_Slajd28.png Trzy kolejne plansze przedstawiają: z lewej strony tabelkę stanu następnego danego przerzutnika, a kolejne dwie z prawej strony reprezentują funkcje wzbudzeń wejścia J oraz K tego przerzutnika. Na tabelkach tych zaznaczono również pętelki według których obliczono funkcje wzbudzeń: kolejno: J2, K2, J1, K1 oraz J0, K0.

Grafika:TC_M7_Slajd29.png

Grafika:TC_M7_Slajd30.png

Grafika:TC_M7_Slajd31.png Z powyższego przykładu wynika niezbyt pocieszający wniosek:

Synteza kombinacyjna układów sekwencyjnych może być (i zazwyczaj jest) procesem żmudnym, w którym trzeba przetwarzać ogromne tablice wypełnione zerami i jedynkami. W postępowaniu takim nietrudno o pomyłkę. Na szczęście w komputerowych systemach projektowania proces ten jest całkowicie zautomatyzowany, a jedynym zadaniem projektanta jest wprowadzenie do systemu odpowiedniego pliku wejściowego z zapisaną specyfikacją tablicy przejść-wyjść.