070 071

70

Przykład. 3.3

Narysować graf układu sekwencyjnego Moore'a, obliczającego prędkość na podstawia podawanych w Jednostkowych odstępach czasu na Jego wejście w\r-LoAcl przyśpiąazeó Jakiegoś układu fizycznśgo. Przyśpieszenia należą do zbioru -2, -1, 0, +1, +2 przy czym wiadomo, że wartość bezwzględna, prędkości nigdy nie przekroczy 3 oraz, te przyśpieszenia zwiększające bezwzględną wartość prędkości nie mogą być, co do modułu, większe od Jedno-

	.1	-1	1	•(	♦t
-ł	-	—	-s	*2	-1
-t	-	-3	-I	-1	0
-1	-	-1	-1	t	M
1	—		0	♦1	. -
*1	-1	0	♦1	♦2	—
♦1	0	♦1	♦1	♦3	-
	♦1	♦t	♦3	-	-

Rys. 3.3. Graf 1 tablica przejść układu z przykładu 3.3

Oznaczając stany wartościami prędkości otrzymujemy graf i tablicę jrzeJSć Jak na ry^; 3.3* Zwróćmy uwagę, że z wprowadzonych ograniczeń wynikają przejścia nieokreślone. •    ’    14 3.2. MINIMALIZACJA LICZBY STANÓW WEWNęTRZNYCH

Minimalizacja liczby stanów polega na zastąpieniu danego układu sekwencyjnego innym, działającym w określonym sensie identycznie, a posiadającym mniejszą ilość stanów. Zmniejszenie ilości stanów Jest korzystne,bo prowadzi najczęściej do uproszczenia realizowanego układu.

Przez układ sekwencyjny działający identycznie z zadanym, będziemy tu rozumieli układ sekwencyjny pokrywający układ zadany. Relacja pokrywania Jest zdefiniowana następującymi definicjami, £17 str. 9CQ:

Stan s₁ układu sekwencyjnego Jest pokrywany przez Oan Sg - układu sekwencyjnego Mg, co oznaczamy przez £ Sg, wtedy 1 tylko wtedy,gdy dla dowolnego ciągu wejściowego x^, i = 1,2,..., Jeżeli y^ jest określone to y₂i = y_1i( gdzie y,^ i y_2i są sygnałami .wyjściowymi układów 1#^ i Mg w chwili i.

Układ sekwencyjny jest pokrywany przez układ sekwencyjny Mg, wtedy i tylko wtedy, gdy dla każdego stanu układu istnieje taki stan s₂ układu Mg, ża s^ 4 Sg. .    ■ ■

W świetle wprowadzonych definicji zagadnienie minimalizacji liczby stanów układu sekwencyjnego sprowadza się do wyznaczenia spośród układów sekwencyjnych pokrywających układ zadany, układu o minimalnej liczbie stanów. Wyznaczenia takiego układu sekwencyjnego można dokonać poszukując takich stanów zadanego układu, które można połączyć w jeden nowy stan bez zmiany sposobu działania układu, tzn. otrzymując układ pokrywający układ zadany. Takie stany, które można połączyć, nazywamy niesprzecznymi.

Stany s^ i Sg są stanami niesprzecznymi, co oznaczamy s^ ~Sg, wtedy 1 tylko wtedy, gdy dla dowolnego ciągu wejściowego x^, i = 1,2,..., jeżeli są określone y_/]i i y_2i, to y_2i =    gdzie y_1i, y_2i są sygnałami wyjścio

wymi tego samego układu sekwencyjnego*J .

W procesie minimalizacji wyznaczamy zbiory stanów niesprzeoznych, pamiętając przy tym, że dla układów nie w pełni określonych relacja nie-sprzeczności nie jest przechodnia tzn. z tego, że s^ ~ Sg i Sg ~ s^ nie wynika, że s^ s^.

Przykład 5,4

Weźmy następujące trzy ciągi wyjściowe otrzymane ze stanów s^.Sg.Sjdla pewnego ciągu wejściowego, przy czym wiadomo, że s^~Sg i Sg ~ s^

s, 0-1-100

SgO-111--

Bj 0 1-1110

Z przedstawionych ciągów widać, że s^ s^ (na pozycji 6 0 11). ht

Dla utworzenia zbioru stanów niesprzeoznych należy więc wykazać nie-sprzecznośó każdego stanu z każdym innym w obrębie tego zbioru. Zauważmy tu także, że z nleprzeohodniości relacji niesprzeczności wynika, że zbiory stanów niesprzeoznych mogą nie być rozłączne.

Zbiór stanów niesprzeoznych odpowiada jednemu nowemu stanowi układu minimalnego, pokrywającego układ zadany.

Zbiory Ti stanów niesprzeoznych tworzą rodziny R^. Ra to, aby rodzina Rj stanowiła podstawę konstrukcji minimalnego układu sekwencyjnego, potrzeba i wystarcza, aby

1) pokrywała wszystkie stany układu zadanego,

Zwróćay uwagę, że definicja niesprzeczności odnosi się do dwóch etanów tego eaae-go układu sekwencyjnego, podczas gdy definicje pokrywania odnosi się do etanów dwóch różnych układów sekwencyjnych.