twuc_424.pdf

186 4. Synteza układów sekwencyjnych

2) uzyskaną w ten sposób tablicę Mealy'ego minimalizuje się łącząc

stany zgodne.

Przykład przekształcenia uzyskanej na rys. 4-18c tablicy Moore'a

(sumatora szeregowego) w tablicę Mealy'egp jest przedstawiony na rys.

4-19.

oo 01 u 10

00 01 11 10

0,0

2fl

2,0

',<

2,0

2fl

(oj)o

{2,3)1

0,0

0,1

! ,o

1,0

1,1

1,0

0,0

2,0

A',Y

Rys. 4-19. Zmiana układu Moort'a na układ Mealy'ego dla sumatora

gowego; a) tablica Moore'a; b) przeniesienie symboli wyjść; c) zminimali-

zowana tiiblica Mealy'ego

4.2.4. KODOWANIE STANÓW WEWNĘTRZNYCH

Po uzyskaniu minimalnej tablicy przejść Moore'a lub Mealy'ego

należy tę tablicę zakodować, tzn. opisać za pomocą sygnałów binarnych

x, y i Q. Zazwyczaj stany X \ Y od samego początku syntezy występują

w postaci ciągów sygnałów (x x , x 2 , ...,*») i (y t , y t , ..., y„), gdyż wstępne

binarnej,

czyli

każdemu A-, przypisać konkretny ciąg

Pierwszym problemem, który powstaje przy kodowaniu stanów

wewnętrznych, jest określenie liczby k sygnałów O potrzebnych dla

opisania K stanów wewnętrznych. Ponieważ można przypuszczać, że

im więcej przerzutników (elementów pamięci) z wyjściami Q zawiera

układ, tym jest droższy, bardziej skomplikowany i zawodny, należy więc

dążyć do możliwie najmniejszej liczby k dla danego K. Najmniejsza

możliwa liczba k wynika z zależności

2*" 1 < K *s 2"

założenia obejmują właśnie relacje między konkretnymi sygnałami « i _>'.

Natomiast stany A, wprowadzone w procesie syntezy, mają dowolną

postać umowną (zwykle kolejnych liczb naturalnych) i dlatego przed

dalszymi etapami projektowania układu należy je zapisać w standardowej

postaci

4.2, Układy synchroniczne 187

i oznacza po prostu minimalną liczbę bitów, potrzebnych do przedsta-

wienia w postaci dwójkowej liczby K. Niekiedy minimalizacja liczby ele-

mentów pamięci nie prowadzi do najprostszego układu, ale jest to problem

dalszy; na początku należy próbować zastosować minimalni} wartość k.

Gdy k jest już określone, pozostaje ustalenie relacji między konkret-

nymi stanami A i ciągami wartości (O,, 0 2 , ..., O*). Na poprawne dzia-

4anie układu synchronicznego nie ma to wprawdzie żadnego wpływu,

ale—jak się okazuje —ma bardzo duży wpływ na stopień złożoności

tego układu. Wynika to z faktu, że tablica przejść i wyjść jest po zakodo-

waniu doprowadzana do postaci tablicy Karnaugha, z której znanymi me-

todami są otrzymywane pewne funkcje kombi nacyjne. Na postać tych

funkcji istotny wpływ ma to, czy sąsiadujące ze sobą w tablicy stany

A\ i Aj są zapisane jako np. 011 i 111, czy jako 000 i 111, gdyż w pierw-

szym przypadku istnieją większe możliwości sklejeń, a więc uproszczenia

funkcji i układu. Podobnie nie jest obojętne czy stan 000 przechodzi pod

wpływem jakiegoś X w stan 001 czy w 111, gdyż w pierwszym przypadku

zmiana angażuje mniej sprzętu i można spodziewać się, że układ będzie

prostszy. Te i inne podobne przyczyny sprawiają, że kodowanie stanów

wewnętrznych powinno być przeprowadzane tak, by powstały w dalszych

etapach układ był możliwie najprostszy. Jest to jednak problem bardzo

trudny, gdyż już przy K = 5, możliwych, odmiennych sposobów r kodo-

wania jest 140 i liczba ta szybko rośnie ze wzrostem K, a więc porówna-

nie wszystkich wersji jest praktycznie nierealizowalne. Nawet za pomocą

maszyny cyfrowej trudno jest przekroczyć barierę K = 9 (10 milionów

wariantów kodowania), pozostaje więc poszukiwanie metody umożliwia-

jącej ocenę złożoności układu bez potrzeby jego syntezy już na podstawie

tablic przejść i wyjść (przed ich zakodowaniem). Niestety, metody umoż-

liwiającej odszukanie najlepszego wariantu kodowania dowolnego układu

dotychczas nie ma, a nawet, gdy powstanie, będzie zbyt złożona dla

syntezy niemaszynowej, gdyż musi uwzględnić wiele różnych czynników

mających wpływ na złożoność układu. Również najogólniejsza z istnieją-

cych metod (Hartmanisa i Stearnsa), chociaż nic obejmuje wszystkich

układów i czynników, w swej klasycznej postaci jest mało użyteczna, gdyż

wymaga licznych, pracochłonnych czynności, nawet w przypadku pro-

stych tablic o K = 5. W zastosowaniach praktycznych szybciej uzyskuje

się dobry wynik badając tablice pod kątem wypełnienia kilku różnych wa-

188

4. Synteza układom

runków mających wpływ na złożoność układu. Postępowanie takie nie

gwarantuje wprawdzie, że rezultat będzie najlepszy, ale uwzględnia wiele

czynników, daje pewną swobodę wyboru rozwiązania i zwykle prow r adzl

do rozwiązań najlepszych lub zbliżonych do najlepszych.

Gdy układ sekwencyjny ma dwa stany (np. 1,2), problem kodowania

nie istnieje, gdyż są tylko dwie możliwości:

A B

Ponieważ wersja A różni się od B tylko negacją, zamiana O na O i O na

O w A — daje B i odwrotnie. Przerzutniki mają zazwyczaj zarówno

wyjście Q jak i Q wiec złożoność obydwu wersji jest identyczna, a nawet

gdyby realizacja jednej wersji była mniej wygodna — przejście na drugą

wersję jest proste. Wynika stąd wniosek, który będzie wykorzystywany

dalej: kombinacje kodowe różniące się o negację są równoważne i wy-

starczy uwzględnić jedną z nich.

Tak więc — w przypadku dwóch stanów wewnętrznych istnieje w za-

sadzie tylko jeden sposób kodowania.

Gdy układ ma trzy stany (np. 1,2,3) — można wypisać wicie wa-

riantów kodowania, np.

A B C D E F

1 —

00 00 00 11 00 01

2—

01 01 11 10 11 11

3—

11 10 10 00 01 00

Jednakże dokładniejsza analiza wykazuje, że wersja D powstała z A

przez negowanie, E — to wersja C z miejscami zamienionymi, & F — to

wersja B z miejscami zamienionymi i negacją drugiej wartości. Oczywiście,

zamiana miejsc w kodzie nie może wpłynąć na złożoność układu, bo

wszystkie funkcje logiczne są przemienne, a więc wersje z wartościami

zamienionymi Q można uznać za równoważne i uwzględniać tylko jedną

z nich. Wynika stąd, że ze wszystkich podanych wyżej możliwości ko-

dowania trzech stanów, tylko wersje A, B i C różnią się od siebie w sposób

istotny dla realizacji układu. Okazuje się, że również inne, dowolne wersje,

4.2. Układy synchroniczne 189

są równoważne jednej z wersji A, B, C. Można się o tym przekonać za

pomocą wyprowadzonego przez Hartmanisa rachunku podziałów, bardzo

wygodnego narzędzia przy poszukiwaniu najlepszych metod kodowania.

Podział jest to pełny (tzn. zawierający wszystkie elementy rozpatry-

wanego zbioru) zbiór podzbiorów rozłącznych. Podzbiory są nazywane

blokami i wyodrębnione za pomocą kreski nad ich elementami, a podziały

są oznaczane małymi literami greckimi.

Na przykład m. — {1,2; 3,5; 4} jest trój blokowym podziałem zbioru

{1,2,3,4,5}, natomiast {1; 3,5; 4} i {1,2; 3,5; 2,4} nie są podziałami tego

zbioru.

Podział n t jest nie większy od określonego na tych samych elementach

{1,2; 3; 4} ^ (U; ^4}

gdyż {l,2}_s {1,2}, {3} s {3,4} i {4} E {3,4}.

Zgodnie z tą relacją, podziałem najmniejszym jest podział o blokach

jednoelementowych, oznaczany przez 0. Na przykład:

{T; 2; 3; 4; 5} = 0

Podziałem najwiekszym jest podział o jednym bloku, oznaczany

przez 1, np.

{1,2,3,4,5} =1

Dla dowolnego n jest n ^ 0 i n ^ 1.

Iloczyn podziałów ^ i TI 2 (tego samego zbioru) to podział, którego-

blokami są przekroje bloków JT, z blokami TI^. Na przykład:

{1,2,3; 4,5,6} • {1,2,6; 3,4,5} = {1,2; 3; 6; 4,5},

gdyż {lA3}_n {l&6}y= {1^2}, Jl,2,3} n {3,4,5} - {3} itd.

Podobnie: (1,2; 3; 4,5}- {1,3,4; 2,5} =0.

Suma podziałów jtj i .T 2 (tego samego zbioru) to najmniejszy po-

dział 71 taki, że jeśli a jest elementem jakiegoś bloku z Jt l lub jt 2 • t o

ten blok jest zawarty w jednym bloku 71. Na przykład:

{T^; 3^4; 5^}+ {U; 2A; 5fi] == {1,2,3,4, 5,6},

podziału JI 2 ( n i ^ ^2)1 j e ^i każdy blok z ?!, jest zawarty w jakimś bloku

z n 2 , np,

190

4. Synteza układów sekwencyjnych

gdyż, skoro {1,2} z (n^ jest zawarte w bloku m (z n), to i {1,3} u {2,4}

(z ?i 2 ) zawarte są w OT, a także {3,4} (z TE i) jest zawarte w «, czyli

W - {1,2} u {1,3} u {2,4} u {3,4} = {1,2,3,4}

Można zauważyć, że w wariancie A kodowania trzech stanów, pierw-

szy bit swą wartością 0 albo 1 wprowadza podział TC 1 = {1,2; 3}, a drugi

bit — n 2 = {T; 2,3}. Na rys. 4-20a pokazano to w sposób graficzny.

n 2

Rys. 4-20, Podbiały zbioru o trzech elementach; wersje podziałów przydat-

nych do kodowania

Każda para stanów jest tu przedzielona linią podziału, co oznacza, że nie

będzie dwóch stanów zakodowanych w taki sam sposób. Warunek ten

można też sprawdzić za pomocą iloczynu podziałów; gdy daje on w wy-

niku 0 — kodowanie zgodne z podziałami przypisze każdemu stanowi

inny kod.

Opisanie wartości Q za pomocą podziału n jest możliwe wtedy, gdy

podział 7i ma dwa bloki, przy czym nie jest istotne któremu z nich przy-

pisze się wartość 0, a któremu 1. W przypadku trzech stanów istnieją

tylko trzy podziały dwublokowe:

z tych trzech podziałów mogą być wykorzystane do kodowania. W ten

właśnie sposób powstały wersje A, BiC (rys. 4-20). Wszystkie pozostałe

wersje opisuje się również tymi samymi podziałami, a różnica polega

jedynie na zamianie miejsc (n 2 , jr t zamiast je l3 n 2 ) lub wartości (0 za-

miast 1 i przeciwnie), co nie zmienia stopnia przydatności kodu.

Podobnie: {T^; 3; 2^5}+ {1^"; 2A) 5} = 1

Dla dowolnych n t i 7r 2 jest TI L - n 2 =ś Wj oraz JI, -\-n 1 ^ ?t t ,

», ={Tć; 3}, x % = {I; 2^3} oraz w a = {T>, 2}

Ponieważ n y • n 2 = 0, % • TI 1 = 0 oraz TT 2 • JT 3 = 0, więc każde dwa

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: