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 wejicle wartości przyśpieszeń Jakiegoś układu flzycznśgo. Przyśpieszenia naleśą do zbioru -2, -1, 0, 4-1, +2 przy czym wiadomo, te wartość bezwzględlna 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-

•( »t

-	-	-s	'I	-1
—	-i	-I	-1	0
-	-i	*1	0	*1
—	-\	0	♦i	-
-1	0	♦1	♦I	—
0	♦i	♦1	♦3	-
♦1	♦i	♦3	-	-

łX -i -ł -i

-1

-1

I

*1

♦1

♦ł

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ę jrzejk; Jak nary^; 3.3« Zwróćmy uwagę, te s wprowadzonych ograniczeń wynikają przejścia nieokreślone. •    ’ 3.2. MINIMALIZACJA LICZBY STANÓW WEWNĘTRZNYCH

Minimalizacja liczby atanć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, [/I7 str. 90^i

Stan 8^ układu sekwencyjnego U^ Jest pokrywany przez Oan Sg >■; układu sekwencyjnego lig, co oznaczany przez s₁ < s₂, wtedy 1 tylko wtedy,gdy dla dowolnego ciągu wejściowego x_Ł, 1 = 1,2,..., jeżeli y_1t jest określone to 721 ³ ^11’ Sdala 7-j^ l^^ sygnałami .wyjściowymi układów M. i Mg w chwili i.

Iflcład sekwencyjny M., jest pokrywany przez układ sekwencyjny Mg, wtedy 1 tylko wtedy, gdy dla każdego stanu s₁ układu M₁ Istnieje taki stan _Sg układu Mg, że 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 nlesprzecznymi.

Stany s₁ i Sg są stanami nlesprzecznymi, co oznaczamy 8^ ~Sg, wtedy i tylko wtedy, gdy dla dowolnego ciągu wejściowego x_i# i = 1,2,..., jeżeli są określone y_1Ł i    ^t0 721 ^{3 7}1i' S³²¹* 7-|i» ?2i sygnałami wyjścio

wymi tego samego układu sekwencyjnego .

W procesie minimalizacji wyznaczamy zbiory stanów niesprzecznych, 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^ ~ sj 1 Sg ~ Sj nie wynika, że s^ ~ Sj.

Przykład ć.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,j~Sg i s-g — s^

s, 0-1-100

SgO-111--

Sj 01-1110

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

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

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

Zbiory Ti stanów niesprzecznych tworzą rodziny Rj. Ka 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 uletprzeozaośel odnosi się do dwóch stanów tego nawago układu sekwencyjnego, podczas gdy definicja pokrywania odnosi się do stanów dwóch różnych układów sekwencyjnych.