TECHNIKA CYFROWA I MIKROKOMPUTERY

WYKŁAD 7

10.04.2003

UKŁADY SYNCHRONICZNE

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

UKŁAD SEKWENCYJNY jest to
urządzenie służące do
przetwarzania informacji
cyfrowej. Przedstawić go można
w postaci bloku posiadającego n-
sygnałów wejściowych x

1

, x

2

, ...

x

n

oraz m sygnałów wyjściowych

y

1

, y

2

, ... y

m

. Wektor wartości

binarnych sygnałów wejściowych
x

1

, x

2

,...,x

n

określa tzw. stan wejść

automatu
(a

1

, a

2

,...,a

n

)=X

i

gdzie a

i

- wartość zmiennej x

i

UKŁAD

SEKWENCYJNY

x

1

x

2

x

n

y

1

y

2

y

n

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zbiór stanów wejść automatu
X={x

1

, x

2

,...,x

n

}

nazywany jest alfabetem wejściowym, a poszczególne stany
-literami tego alfabetu.
Podobnie wartości sygnałów wyjściowych y

1

,...,y

n

określają stan

wyjść automatu
(b

1

,...,b

m

)=Y

j

,

gdzie b

i

- wartość zmiennej y

i

,

a zbiór stanów wyjść
Y={y

1

, y

2

,...,y

n

}

nazywany jest alfabetem wyjściowym. Ponieważ nie wszystkie
kombinacje sygnałów wejściowych i wyjściowych muszą
występować więc moc zbioru X jest nie większa niż 2

n

, zaś moc

zbioru Y nie większa niż 2

m

.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W układach kombinacyjnych aktualny stan wyjść Y

t

zależał

jedynie od aktualnego stanu wejść X

t

Y

t

=f(X

t

)

W układach sekwencyjnych aktualny stan wyjść zależy również
od poprzednich stanów wejść
Y

t

=f(X

t

, X

t-1

, X

t-2

, ...)

Mówimy zatem, że automat sekwencyjny ma pamięć. Dla
opisania automatu sekwencyjnego wprowadza się pojęcie
stanu wewnętrznego A, określonego przez stany Q

i

elementów

pamięciowych automatu
A=(Q

1

,...,Q

i

,...Q

k

)

Zbiór stanów wewnętrznych automatu oznaczamy:
A={A

1

, A

2

,...,A

k

}

Moc A jest nie większa niż 2

k

.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Związki pomiędzy stanem wyjść, stanem wewnętrznym i stanem
wyjść automatu opisane są funkcjami przejść i wyjść. Funkcja
przejść dla danego stanu wewnętrznego i stanu wejść automatu
określa jego następny stan wewnętrzny
A

t+1

=(A

t

, X

t

)

Funkcja wyjść określa stan wyjść automatu. Stan ten może zależeć
od stanu wewnętrznego i stanu wejść (tzw. Automat Mealy’ego)
Y

t

=

1

(A

t

, X

t

)

bądź też, jak często bywa w praktyce, tylko od stanu
wewnętrznego (tzw. Automat Moore’a)
Y

t

=

2

(A

t

)

Jak widać do scharakteryzowania działania automatu wystarczy
znać X, Y, A, , .
Automat skończony określa się jako uporządkowaną piątkę:
M=<X

M

, Y

M

, A

M

, 

M

, 

M

>

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MEALY’EGO

Stan wyjścia zależy od stanu
wewnętrznego i od stanu wejść





X

Y

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MOORE’A

Stan wyjścia zależy jedynie od
stanu wewnętrznego





X

Y

A

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W zależności od sposobu oddziaływania sygnałów wejściowych na
stan pamięci automatu dzielimy automaty sekwencyjne na
synchroniczne i asynchroniczne. W układach synchronicznych stan
wejść X może oddziaływać na układ pamięciowy (to znaczy zmieniać
stan) tylko w ściśle określonych momentach, wyznaczonych
sygnałem na specjalnym wejściu taktującym (zegarowym). Dowolny
układ sekwencyjny można traktować jak układ synchroniczny, jeżeli
jeden z sygnałów wejściowych g spełnia następujące warunki:
• zmiana stanu wewnętrznego układu następuje przy określonej
zmianie (np. z 1 na 0) sygnału g,
• pozostałe sygnały wejściowe zmieniają swą wartość gdy g=0
(warunek ten jest konieczny dla niektórych typów przerzutników)
Sygnał g uznajemy wówczas za sygnał taktujący. Sygnał ten, zwany
także taktem, narzuca rytm pracy układu i jest przyjmowany za
umowną jednostkę czasu. Symbole t, t+1 ... oznaczają więc kolejne
takty zegara.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W układach asynchronicznych nie wyróżnia się wejścia
taktującego, zmiana stanu wewnętrznego następuje
bezpośrednio pod wpływem zmiany stanu wejść. Nowy stan
wewnętrzny A

t+1

ustala się po czasie , wyznaczonym przez

opóźnienie elementów, z których zbudowany jest automat.
Funkcję przejść automatu asynchronicznego można więc

zapisać w postaci:
A(t+)= [A(t), X(t)]

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Funkcje przejść i wyjść automatu są zwykle przedstawiane w
postaci tablicy, zwanej tablicą przejść i wyjść. Z lewej strony
tablicy wypisane są wszystkie stany wewnętrzne automatu, a u
góry - wszystkie stany wejść. W klatkach tablicy dla każdego
stanu wewnętrznego A

it

i dla każdego stanu wejść X

jt

podany

jest następny stan wewnętrzny
A

pt+1

= (A

jt

, X

jt

). Stany wyjść automatu Mealy’ego wygodnie jest

wpisywać w klatkach tej samej tablicy.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MEALY’EGO

A

1

A

3

A

4

A

2

x

1

/y

3

x

2

/y

3

x

2

/y

4

x

2

/y

1

x

1

/y

1

x

2

/y

2

x

1

/y

3

x

1

/y

1

X

t

A

t

X

1

X

2

A

1

A

3

Y

1

A

4

Y

3

A

2

A

1

Y

3

A

2

Y

4

A

3

A

4

Y

1

A

4

Y

2

A

4

A

2

Y

3

A

3

Y

1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MOORE’A

A

1

A

3

A

4

A

2

x

1

x

2

x

1

x

1

x

2

x

2

x

1

(Y

1

)

(Y

2

)

(Y

3

)

(Y

4

)

X

t

A

t

X

1

X

2

A

1

A

2

A

4

Y

2

A

2

A

2

A

3

Y

1

A

3

A

3

A

1

Y

1

A

4

A

2

A

2

Y

3

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W przypadku automatu Moore’a stan wyjść jest jednakowy dla
wszystkich klatek znajdujących się w danym wierszu,
wypisujemy go więc z prawej strony tablicy.
Dokładnym odpowiednikiem tablicy przejść jest graf automatu.
Wierzchołkom grafu przypisuje się numery stanów
wewnętrznych A, natomiast łukom - stany wejść X. Symbole
odpowiadające stanom wyjść Y umieszcza się w przypadku
automatu Mealy’ego przy łukach, a w przypadkach automatu
Moore’a przy wierzchołkach.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 1

Licznik liczący sygnały taktowe
modulo 5 (to znaczy po pięciu
impulsach wracający do stanu
początkowego). Licznik taki ma
pięć stanów wewnętrznych
A

1

,...,A

5

, w każdym takcie układ

przechodzi do kolejnego stanu.

A

t

A

t+1

Y

A

1

A

2

Y

1

A

2

A

3

Y

2

A

3

A

4

Y

3

A

4

A

5

Y

4

A

5

A

1

Y

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 1

Y

1

A

1

A

1

A

1

A

1

A

1

Y

5

Y

2

Y

4

Y

3

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 2

Układ, który przy podaniu
sygnału 1 na wejście x wytwarza
na wyjściu y pojedynczy, nie
ucięty impuls o długości równej
okresowi generatora C.

A

t

A

t+1

Y

A

1

A

2

Y

1

A

2

A

3

Y

2

A

3

A

4

Y

3

A

4

A

5

Y

4

A

5

A

1

Y

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 3

Komparator szeregowy,
porównujący ze sobą dwie liczby
binarne C i D (podawane na wejścia
szeregowo, cyfra po cyfrze,
poczynając od najmniej znaczących)
będzie miał trzy stany wewnętrzne
odpowiadające trzem możliwym
przypadkom C>D, C=D,C<D. W
stanach tych zapamiętywane są
wyniki porównania dotychczas
podanych fragmentów liczb.
Kombinacje sygnałów wyjściowych
x

1

x

2

00, 01, 11, 10 odpowiadają

stanom wejścia x

00

, x

01

, x

11

, x

10.

Sygnały wyjściowe y

1

y

2

równe 10,

00 lub 01 będą odpowiadać
poszczególnym stanom
wewnętrznym (automat Moore’a)

X/A X

00

X

01

X

11

X

10

Y

1

Y

2

1

1

3

1

2

00

2

2

3

3

2

10

3

3

3

3

2

01

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 3

3

C<D

00
11

00
11
01

01

01

2

C>D

1

C=D

01

10

00
11
01

10

00

10

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 4

Sumator szeregowy, służący do
dodawania dwu liczb
podawanych kolejni cyfra po
cyfrze (poczynając od najmniej
znaczącej), powinien mieć dwa
stany wewnętrzne. Stany te
odpowiadają wartościom
przeniesienia (p=0 lub p=1) do
pozycji bardziej znaczącej.

X/A

X

1

00

X

2

01

X

3

11

X

4

10

A

1

A

1

0

A

1

1

A

2

0

A

1

1

A

2

A

1

1

A

2

0

A

2

1

A

2

0

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 4

A

1

p=0

11 (0)

A

1

p=1

00 (1)

00 (0)

01
10

(1)

10
01

(0)

11(1)

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Dla prostych układów synchronicznych graf lub tablicę przejść
można narysować bezpośrednio na podstawie słownego opisu
działania układu. W grafach i tablicach nie wyróżnia się wśród
sygnałów wejściowych stanu zegara a jedynie zaznacza się
stan wejść automatu (w momencie zmiany stanu sygnału
zegarowego). Momentem tym może być zmiana stanu zegara
z 1 na 0 (tylne zbocze zegara) lub z 0 na 1 (przednie zbocze
zegara). Moment zmian nie wpływa na sposób opisu i metodę
syntezy automatu, ale ma pewne znaczenie dopiero na eapie
syntezy logicznej.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W podanych przykładach zakładano dowolnie, że układ ma być
autoamtem Moore;a lub Mealy’ego. Na ogół trudno określić czy
prostszą realizację ma automat Mealy’ego, czy równoważny
mu automat Moore’a. Równoważność automatów rozumie się
tu w sensie ich takiego samego działania obserwowanego z
zewnątrz (to znaczy obserwacji jedynie stanów wejść i wyjść).

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zmianę tablicy przejść automatu Mealy’ego w tablicę przejść
równoważnego mu automatu Moore’a można przeprowadzić w
następujący sposób:
• każdej parze stanów (A

j

, Y

j

) wpisanych w klatki tablicy

automatu Mealy’ego przyporządkować stan B

j

automatu

Moore’a, przy czym jednakowym parom powinny odpowiadać
jednakowe stany B

j

• ułożyć tablice przejść automatu Moore’a, przypisując
każdemu stanowi B

j

sygnał wyjściowy Y

j

z odpowiadającej mu

pary (A

j

, Y

j

). Stany następne, dla każdego X

i

, przypisujemy

stanowi B

j

=(A

j

, Y

j

) takie jakie miał stan A

j

z tejże pary, to

znaczy (

1

(A

j

, X

i

), (A

j

, X

i

))=B

r

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

X

1

X

2

A

1

A

2

(B

1

)

0

A

3

(B

2

)

0

A

2

A

4

(B

3

)

0

A

5

(B

4

)

0

A

3

A

6

(B

5

)

0

A

7

(B

6

)

0

A

4

A

1

(B

7

)

0

A

1

(B

8

)

1

A

5

A

1

(B

8

)

1

-

A

6

A

1

(B

8

)

1

-

A

7

A

1

(B

7

)

0

-

X

1

X

2

Y

B

1

B

3

B

4

0

B

2

B

5

B

6

0

B

3

B

7

B

8

0

B

4

B

8

-

0

B

5

B

8

-

0

B

6

B

7

-

0

B

7

B

1

B

2

0

B

8

B

1

B

2

1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zmiana tablicy przejść automatu Moore’a w tablicę przejść
automatu Mealy’ego polega na wpisaniu w kratkę tablicy, w
któej występowa stan następny A

j

, wartości wyjścia automatu

Moore’a odpowiadającego temu stanowi, a następnie usunięcie
kolumny wyjść

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

X

00

X

01

X

10

X

11

Y

1

Y

2

A

1

A

1

A

3

A

1

A

2

00

A

2

A

2

A

3

A

2

A

2

10

A

3

A

3

A

3

A

3

A

2

01

X

00

X

01

X

10

X

11

A

1

A

1

00

A

3

00

A

1

00

A

2

00

A

2

A

2

10

A

3

10

A

2

10

A

2

10

A

3

A

3

01

A

3

01

A

3

01

A

2

01

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Dane są dwa automaty skończone zupełne
N=< X

N

, Y

N

, A

N

, 

N

, 

N

>

M=<X

M

, Y

M

, A

M

, 

M

, 

M

>

takie, że X

N

=X

M

, Y

N

=Y

M

.

Niech p=x

1

, x

2

,...,x

s

będzie pewnym ciągiem stanów wejść

automatu.
Można określić dla automatu funkcje (A

1

, p), (A

1

, p), ’(A

1

, p),

(A

1

, p). (A

1

, p)=A

2

, A

3

,...,A

s+1

, gdzie A

2

, A

3

,...,A

s+1

jest ciągiem

stanów wewnętrznych takich, że:
A

2

= (A

1

,X

1

),...,A

s+1

=(A

s

,X

s

)

Funkcja (A

1

,p) określa ciąg stanów, przez które przechodzi

automat znajdujący się początkowo w stanie wewnętrznym A

1

,

gdy na wejście podamy ciąg stanów wejść p=X

1

, X

2

,...,X

s

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

(A

1

, p)=Y

1

, Y

2

,...,Y

s

gdzie Y

1

, Y

2

,...,Y

s

, jest ciągiem stanów wyjścia takich, że:

Y

1

=(A

1

, X

1

)

Y

2

=(A

2

, X

2

)= ((A

1

, X

1

), X

2

)

...
Y

s

=(A

s

, X

s

)= (A

s

,X

s

)

Funkcja (A

1

, p) określa ciąg wyjść, którym automat znajdujący

się początkowo w stanie A

1

odpowiada na ciąg stanów do

wejścia p=X

1

, X

2

,...,X

s

. Wartością funkcji ’(A

1

, p) jest A

s+1

, to

znaczy stan, do którego przejdzie automat ze stanu A

1

pod

wpływem ciągu p=X

1

, X

2

,...,X

s

. Wartością funkcji (A

1

, p) jest

ostatni stan ciągu wyjściowego wygenerowanego przez
automat znajdujący się początkowo w stanie A

1

, po podaniu

ciągu wejściowego p.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

(3, X

1

X

2

)= 1 2

(3, X

1

X

1

X

1

)= 1 3 1

(4, X

2

X

1

X

1

)= 5 4 2

’(3, X

1

X

2

)= 2

’(3, X

1

X

1

X

1

)= 1

’(4, X

2

X

1

X

1

)= 2

(3, X

1

X

2

)=1 1

(3, X

1

X

1

X

1

)= 1 0 1

(4, X

2

X

1

X

1

)= 0 0 1

(3, X

1

X

2

)=1

(3, X

1

X

1

X

1

)= 1

(4, X

2

X

1

X

1

)= 1

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Powiemy, że automaty zupełne M i N o takich samych
alfabetach X i Y są równoważne (M N), gdy dla każdego

ciągu p podanego na wejścia automatów i dla każdego stanu
A

i

A

N

, istnieje taki stan A

j

A

M

, że odpowiednie ciągi wyjściowe

obu automatów są jednakowe.
Stany A

i

oraz A

j

automatu M są równoważne gdy dla każdego

ciągu wejściowego p odpowiednie ciągi wyjściowe są
jednakowe. Do wyszukiwania stanów równoważnych
wykorzystuje się następujące twierdzenie.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Dwa stany wewnętrzne A

i

, A

j

automatu w pełni określonego są

równoważne, jeżeli dla dowolnego stanu wejść X

r

spełnione są

następujące warunki:
• sygnały wyjściowe, odpowiadające obu tym stanom są
jednakowe
• stany następne są jednakowe lub równoważne

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Stany 1 i 2 są równoważne, gdyż
ich następniki (stany następne)
są jednakowe, to znaczy:

(1, X

1

)= (2, X

1

)= 3

(1, X

2

)= (2, X

2

)= 3

(1, X

1

)= (2, X

1

)= 0

(1, X

2

)= (2, X

2

)= 1

Stany 3 i 4 są równoważne, gdyż
ich następniki są jednakowe lub
równoważne

(3, X

1

)= 1 (4, X

1

)= 2 12

(3, X

2

)= (4, X

2

)= 5

(3, X

2

)= (4, X

2

)= 0

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Analizując równoważność stanów 5 i
6 można zauważyć, że
(5, X

1

)= (6, X

1

), (5, X

1

)= (6, X

1

)

(5, X

2

)= (6, X

2

)

czyli stany 5 i 6 są równoważne pod
warunkiem, że stany
(5, X

2

)= 6 i (6, X

2

)= 5 są

równoważne. Te stany są
równoważne, gdyż pod wpływem
stanu wejścia X

2

automat dla obu

tych stanów da wyjście 1 i przejdzie
do stanu 5 lub 6, a dla stanu wejścia
X

1

przejdzie do stany 4. Zatem dla

dowolnego ciągu wejściowego
automat znajdujący się w stanie 5 i
w stanie 6 wygeneruje taki sam ciąg
wyjściowy.

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Ponieważ automat zachowuje się
tak samo dla różnych stanów
równoważnych, każdą z par
stanów równoważnych można ze
sobą połączyć i otrzymany
automat będzie równoważny
automatowi początkowemu.
Połączone stany 1 i 2 oznaczono
przez A, stany 3 i 4 przez B, zaś
stany 5 i 6 przez C. Stany A i C
okazują się równoważne, zatem
automat można zminimalizować.

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

X

1

X

2

A

B

0

A

1

B

A

1

C

0

C

B

0

C

1

X

1

X

2

K

L

0

L

1

L

K

1

K

0

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zdefiniowana relacja równoważności stanów automatu jest
przechodnia (A

1

 A

2

 A

2

 A

3

A

1

 A

3

), zwrotna (A A) oraz

symetryczna
(A

1

 A

2

A

2

 A

1

), czyli jest znaną z teorii relacji relacją

równoważności, dzielącą zbiór A na rozłączne podzbiory,
których suma jest równa A.
Relacja równoważności stanów dzieli zbiór stanów automatu na
zbiory stanów wzajemnie równoważnych, które mogą być
zastąpione jednym stanem.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Ciąg p=X

1

X

2

...X

n

jest stosowalny do automatu niezupełnego

będącego w stanie A

1

, jeśli wszystkie elementy ciągu (A

1

, p)

są określone, to znaczy jeżeli stan ’(A

1

, p) jest określony dla

każdego podciągu początkowego p’ ciągu p.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Ciąg X

1

X

1

jest stosowalny do

automatu znajdującego się w
stanie 2, nie jest natomiast
stosowalny do tego automatu,
znajdującego się w stanie 4, gdyż
stan (4, x

1

) jest nieokreślony. Dwa

stany wewnętrzne automatu
niezupełnego A

i

,A

j

są niesprzeczne

jeśli są one jednakowe lub co
najmniej jeden z nich jest
nieokreslony. Dwa stany wyjśćia
y

1

,y

2

,...,y

m

i y

1

’,y

2

’,...,y

m

’ są

niesprzeczne, gdy każda para y

i

,y

i

zawiera dwa elementy jednakowe
(0 i 0 lub 1 i 1) lub co najmniej
jeden nieokreślony (0 i -, 1 i -, - i -)
Niesprzeczne są więc na przykład
stany wyjśc 10 i 10 1- i 10,-0- i 10-

X

1

X

2

X

3

X

4

Y

1

3

3

-

2

0-

2

3

-

-

1

-1

3

2

4

5

1

11

4

-

4

4

-

01

5

3

-

-

1

1-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Dla celów minimalizacji wprowadza się w automatach
niezupełnych pojęcie stanów zgodnych. Powiemy, że stany A

i

i

A

j

są zgodne, jeżeli dla każdego ciągu wejściowego

p=X

1

,X

2

,...,X

s

, który jest stosowalny zarówno do A

i

jak i do A

j

stany końcowe wygenerowanych przez p ciągów wyjściowych
są niesprzeczne. Relację zgodności stanów A

i

i A

j

oznaczymy

przez A

i

A

j

.

Do znajdowania stanów zgodnych wygodnie jest posłużyć się
następującym twierdzeniem:

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Dwa stany wewnętrzne A

i

, A

j

automatu niezupełnego są

zgodne, gdy spełnione są następujące warunki:
• sygnały wyjściowe odpowiadające obu tym stanom są
niesprzeczne,
• stany następne są niesprzeczne lub zgodne

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Stany 1 i 2 są zgodne, gdyż
(1, X

1

)= (2, X

1

)= 3

(1, X

2

)= 3 (2, X

2

)= -

(1, X

3

)= - (2, X

3

)= -

(1, X

4

)= 2 (2, X

4

)= 1

(1)= 0 -
(2)= - 1
Stany 1 i 2 odpowiadają na każdy
ciąg wejść, dla którego istnieje
określony ciąg stanów
wewnętrznych i wyjść, takim
samym ciągiem stanów wyjścia.
Podobnie można stwierdzić, że
stany 2 i 3 są zgodne ze sobą.
Relacja zgodności nie jest
przechodnia, gdyż stany 1 i3 nie są
zgodne, bo mają sprzeczne wyjścia.

X

1

X

2

X

3

X

4

Y

1

3

3

-

2

0-

2

3

-

-

1

-1

3

2

4

5

1

11

4

-

4

4

-

01

5

3

-

-

1

1-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Badając stany 3 i 5 zauważamy,
że mają niesprzeczne wyjścia (11
i 1-)
(3, X

4

)= (5, X

4

)= 1

(3, X

3

)= 5, (5, X

3

)= -

(3, X

2

)= 4, (2, X

2

)= -

(3, X

1

)= 2, (2, X

1

)= 3

(1)= 0 -
(2)= - 1
Stany 1 i 1,5 i - oraz 4 i - są
niesprzeczne. Natomiast ze
względu na kolumnę X

1

stany 3 i

5 są zgodne pod warunkiem, że
stany 2 i 3 są zgodne. Stany 2 i 3
są zgodne, więc 3 i 5 też są
zgodne.

X

1

X

2

X

3

X

4

Y

1

3

3

-

2

0-

2

3

-

-

1

-1

3

2

4

5

1

11

4

-

4

4

-

01

5

3

-

-

1

1-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

W pierwotnej tablicy przejść
zgodne są stany 5 i 6, gdyż
odpowiadają im jednakowe
wyjścia i jednakowe stany
następne. Podobnie zgodne są
stany 4 i 7. Po zastąpieniu
zgodnych par stanów przez inny
stan (piszemy 5 zamiast 5 i 6
oraz 4 zamiast 4 i 7, jeżeli w
danej kolumnie występuje
symbol i kreska - piszemy ten
symbol

X

1

X

2

A

1

2
0

3
0

A

2

4
0

5
0

A

3

6
0

7
0

A

4

1
0

1
1

A

5

1
1

-

A

6

1
1

-

A

7

1
0

-

X

1

X

2

A

1

2
0

3
0

A

2

4
0

5
0

A

3

5
0

4
0

A

4

1
0

1
1

A

5

1
1

-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

W wielu przypadkach nie da się zminimalizować tablicy przejść
w tak prosty sposób. Na następnym wykładzie zostanie podana
metoda minimalizacji liczby stanów wewnętrznych automatu,
tzw. metoda par. Metoda ta jest stosowana zarówno do
automatów zupełnych jak i niezupełnych.