Piotr Kawalec

Wykład II - 1

Wykład II

Kodowanie automatów

synchronicznych z

zastosowaniem rachunku

podziałów

Technika cyfrowa

Piotr Kawalec

Wykład II - 2

Technika cyfrowa

Twierdzenie o złożoności funkcji
przejść



Przy kodowaniu dąży się do znalezienia takich

podziałów, aby funkcje przejść automatu

zakodowanego zgodnie z tymi

podziałami zależały

od jak najmniejszej ilości zmiennych

Q

i

.

Twierdzenie

Zakładamy że wartości sygnałów

Q

1

,...,

Q

k

przyjmowane są

według podziałów



1

,...,



k

Jeżeli







i

jest parą podziałów i







1



2



...





l

to

Q

i

’

jest funkcją

jedynie

sygnałów

wejściowych

oraz sygnałów

Q

1

,...,

Q

l.

Q

i

’

=  (x

1

,..., x

n

,

Q

1

,...,

Q

l

)

Piotr Kawalec

Wykład II - 3

Technika cyfrowa

Wniosek z twierdzenia



Aby funkcje przejść zależały od jak

najmniejszej

liczby argumentów, należy

szukać podziałów dla

których spełnione są

kolejno następujące warunki:



1 



i





i





i





r





i









i







1





2









i







1





2

...



l

Piotr Kawalec

Wykład II - 4

Technika cyfrowa

Cena podziału wewnętrznego



Ceną podziału wewnętrznego

c(



i

)

nazywamy

szacunkową ilość zmiennych od których

zależy

funkcja wzbudzeń przerzutnika

Q

i

zakodowanego

zgodnie z



i

zmniejszoną o 1.



Cenę podziału wewnętrznego wyznacza się z

zależności

c(



i

) = n +

l

- 1

gdzie
n - liczba zmiennych wejściowych
l - liczba sygnałów

Q

l

od których zależy

funkcja

wzbudzeń przerzutnika

Q

i

Piotr Kawalec

Wykład II - 5

Technika cyfrowa

Wyznaczanie liczby sygnałów

Q

l



Dla par podziałów wyszczególnionych we

wnioskach z twierdzenia można wyznaczyć
wartość

l

.



1 



i

l = 0





i





i

l = 1





r





i

l = 1









i







1





2

l = 2

•

•

•









i







1





2

...



k

l = k

Piotr Kawalec

Wykład II - 6

Technika cyfrowa

Minimalna złożoność funkcji przejść



Aby uzyskać funkcję przejść o minimalnej

złożoności należy dążyć do wyboru takich
podziałów



1

,



2

,...,



k

aby:

 iloczyn tych podziałów był podziałem
zerowym



1

•



2

• • •



k

= 0



wartość sumy cen wszystkich podziałów

wewnętrznych była minimalna

i=k



c(



i

)

i=1

Piotr Kawalec

Wykład II - 7

Technika cyfrowa

Podziały zewnętrzne



Podziałem zewnętrznym



x

j

(y

i

)

dla automatu

Mealy’ego nazywamy podział, którego

bloki

zawierają tylko takie stany

którym przy sygnale

wejściowym

x

j

odpowiadają jednakowe sygnały
wyjściowe.



Podziałem zewnętrznym



(y

i

)

dla automatu

Moore’a nazywamy podział, którego bloki
zawierają stany

którym odpowiadają

jednakowe sygnały wyjściowe

Piotr Kawalec

Wykład II - 8

Technika cyfrowa

Twierdzenia o złożoności funkcji wyjść



Przy kodowaniu dążymy do znalezienia takich

podziałów, aby funkcje wyjść automatu



zakodowanego zgodnie z tymi

podziałami zależały

od jak najmniejszej ilości zmiennych

Q

i

.

Twierdzenie dotyczące automatów Moore’a

Zakładamy że



1

,...,



k

są podziałami

dwublokowymi według których koduje się
sygnały

Q

1

,...,

Q

k

, natomiast

(y

j

)

jest

podziałem zewnętrznym ze względu na

y

j

.

Jeżeli



(y

j

)





1





2

...



l

to

y

j

jest funkcją

jedynie

sygnałów

Q

1

,...,

Q

l

czyli

y

j

= (

Q

1

,...,

Q

l

)

Piotr Kawalec

Wykład II - 9

Technika cyfrowa

Twierdzenie o złożoności funkcji wyjść

Twierdzenie dotyczące automatów Mealy’ego

Zakładamy że



1

,...,



k

są podziałami

dwublokowymi według których koduje się
sygnały

Q

1

,...,

Q

k

,

natomiast

(y

j

)

jest podziałem zewnętrznym ze

względu na

y

j

, gdzie



(y

j

)

=



x

1

(y

i

)





x

2

(y

i

)

  



x

n

(y

i

)

Jeżeli



(y

j

)





1





2

...



l

to

y

j

jest funkcją

jedynie

sygnałów wejściowych oraz sygnałów

Q

1

,...,

Q

l.

y

j

= (x

1

,..., x

n

,

Q

1

,...,

Q

l

)

Piotr Kawalec

Wykład II - 10

Technika cyfrowa

Cena sygnału wyjściowego



Dla automatu Moore’a jako cenę sygnału Ł

wyjściowego przyjmuje się

c(y

i

) = l - 1

gdy

y

j

= (

Q

1

,...,

Q

l

)



Dla automatu Mealy’ego cena sygnału

wyjściowego wzrasta o liczbę zmiennych
wejściowych n

c(y

i

) = n + l - 1



Łączna cena układu uwzględniająca zarówno

cenę podziałów jak i cenę wyjść wyraża

się wzorem

c =



c(



i

) +



c(y

i

)

Piotr Kawalec

Wykład II - 11

Technika cyfrowa

Metoda kodowania z wykorzystaniem
par podziałów



Dana metoda jest przydatna do kodowania

automatów o małej liczbie stanów

wewnętrznych
(do 8 stanów)



Pozwala ona wyznaczyć kod o najniższej cenie

pod warunkiem dokonania przeglądu
odpowiednio dużej liczby wariantów



Dla automatów o małej liczbie stanów należy

rozpatrywać jako



i

wszystkie podziały

dwublokowe

Piotr Kawalec

Wykład II - 12

Technika cyfrowa

Etapy metody



Wyznaczyć zbiór par podziałów







,

gdzie



jest pewnym podziałem dwublokowym

lub w

szczególności prawidłowym



Narysować graf par podziałów



Zaznaczyć na grafie podziały dogodne ze

względu na wyjście



Wybrać rodzinę T

k opt.

o minimalnej cenie

Piotr Kawalec

Wykład II - 13

Technika cyfrowa

Przykłady kodowania z
zastosowaniem rachunku podziałów

Przykład 1



Zakodować automat zadany tablicą przejść-

wyjść

x x

1

x

2

x

1

x

2

s
1 1 3 0 1
2 4 2 1 --
3 3 1 1 0
4 1 4 -- 1

Piotr Kawalec

Wykład II - 14

Technika cyfrowa

Przykłady kodowania z
zastosowaniem rachunku podziałów

Przykład 2



Zakodować automat zadany tablicą przejść-

wyjść

x

s x

1

x

2

y

1

y

2

1 1 2 0 0
2 1 3 0 0
3 4 3 -- 0
4 5 3 1 1
5 1 3 0 1