8941511026

3.5.2. Minimalizacja stanów

Cel:

Redukcja liczby stanów automatu (uproszczenie grafu), w konsekwencji uproszczenie późniejszej implementacji w postaci układu cyfrowego. Zaawansowany matematycznie fragment teorii automatów, tutaj przywoływany w wersji „inżynierskiej" tylko na przykładach:

■    Dwa stany automatu nazywamy zgodnymi, jeśli automat znajdując się w nich zachowuje się identycznie, tzn. pod wpływem dowolnego ciągu pobudzeń Y/ generuje identyczne sekwencje odpowiedzi F,.

■    Stany zgodne można łączyć zastępuj ąc j e poj edynczym nowym stanem.

■    Stany identyczne - te same sygnały WY oraz te same stany następne.

Stany równoważne - te same sygnały WY oraz stany następne te same lub równoważne.

■    Niezgodność WY implikuje natychmiast nierównoważność, zgodność stanów następnych może być rozpatrywana warunkowo.

Przykład 5: Selektor triad

Na wejście x podawane są triady (sekwencje 3b). Układ ma wykrywać dwie wyróżnione: „010” i „110”:

x 0010100110001    10100101

y,    0    0    1    0    0    1    0    0    1    0    0    1    0    0    li 0 0 1 0 0 1

_yi    -    -    o    -    -    1    -    -    0    -    -    0    -    -    1--0--0

X = {0,1}

yi = 1 - zakończono wczytywanie triady, yi= 1 - wykryto wyróżnione „010” i „110”;

F = <yi, yj>, Y = { 0-, 10, 11 } - trwa wprowadzanie triady, triada inna niż „010”/„110”, wykryto „010”/,, 110”.