Podręcznik

5. Przykłady syntezy

Omówione w dalszej części przykłady pozwalają stwierdzić, że proces kodowania stanów wewnętrznych automatu dla realizacji na pamięciach znakomicie się upraszcza i głównie polega na wyznaczaniu kodowania wstępnego. Wyznaczanie kodowania wstępnego z reguły sprowadza się do odpowiedniego podziału tablicy przejść automatu. N przykład dla automatu z  tablicy 4.41a  kodowanie wstępne uzyskamy dzieląc tę tablica na 4 podtablice w sposób pokazany w tab. 4.41b.

 

Tablica  4.41

a)						b)
x1x2	00	01	11	10		x1x2	00	01	11	10
a	e	–	c	–		a	e	–	c	–
b	e	a	f	f		b	e	a	f	f
c	–	e	c	f		c	–	e	c	f
d	a	a	–	c		d	a	a	–	c
e	a	d	b	b		e	a	d	b	b
f	d	a	c	c		f	d	a	c	c

 

 

Zapewni to realizację tego automatu na pamięci o trzech wejściach adresowych,  ze zbiorem  wejść bezpośrednich U ={q_1,x₁} i zbiorem wejść do UMA, V={q₂,q₃,x₂}. Oczywiście nie można być pewnym, że możliwa będzie dekompozycja rozłączna i być może dla spełnienia warunku dekompozycji trzeba będzie powiększyć liczbę wejść do UMA.

Jeszcze inna sytuacja może się zdarzyć, gdy dla uzyskania właściwego podziału tablicy przejść na podtablice trzeba dokonać odpowiedniej permutacji wierszy tej tablicy.  Z sytuacją taką mamy do czynienia w automacie o tablicy przejść podanej w tab. 4.42a. W tym przypadku odpowiednia permutacja oraz podział na podtablice powinny być takie jak w tab. 4.42b.

Tablica  4.42

a)

b)

000

001

110

111

010

000

001

110

111

010

v1

v2

v3

v4

v5

v1

v2

v3

v4

v5

a

a

b

e

e

c

b

c

b

b

a

b

b

c

b

b

a

b

e

b

c

b

–

–

c

a

a

c

–

b

a

a

b

e

e

c

d

c

e

e

d

e

c

a

a

c

–

b

e

b

c

b

–

–

d

c

e

e

d

e

 

Mogą być również takie automaty, w których struktura układu sekwencyjnego jest niezależna od kodowania stanów wewnętrznych. Sytuację taką omawiamy w poniższych przykładach.