Technika cyfrowa
Wykład II
Kodowanie automatów
synchronicznych z
zastosowaniem rachunku
podziałów
Piotr Kawalec Wykład II - 1
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 Qi.
Twierdzenie
Zakładamy że wartości sygnałów Q1,..., Qk
przyjmowane są według podziałów �1,..., �k
Jeżeli Ą �i jest parą podziałów i Ą e" �1" �2" ..." �l
to Qi jest funkcją jedynie sygnałów wejściowych
oraz sygnałów Q1,..., Ql.
Qi = � (x1,..., xn , Q1,..., Ql)
Piotr Kawalec Wykład II - 2
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 Ą e" �1" �2
Ą �i Ą e" �1" �2" ..." �l
Piotr Kawalec Wykład II - 3
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 Qi 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 Ql od których zależy funkcja
wzbudzeń przerzutnika Qi
Piotr Kawalec Wykład II - 4
Technika cyfrowa
Wyznaczanie liczby sygnałów Ql
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 Ą e" �1" �2 l = 2
"
"
"
Ą �i Ą e" �1" �2" ..." �k l = k
Piotr Kawalec Wykład II - 5
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 - 6
Technika cyfrowa
Podziały zewnętrzne
Podziałem zewnętrznym Ąx (yi) dla automatu
j
Mealy ego nazywamy podział, którego bloki
zawierają tylko takie stany którym przy sygnale
wejściowym xj odpowiadają jednakowe sygnały
wyjściowe.
Podziałem zewnętrznym Ą(yi) dla automatu Moore a
nazywamy podział, którego bloki zawierają stany
którym odpowiadają jednakowe sygnały wyjściowe
Piotr Kawalec Wykład II - 7
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 Qi.
Twierdzenie dotyczące automatów Moore a
Zakładamy że �1,..., �k są podziałami dwublokowymi
według których koduje się sygnały Q1,..., Qk, natomiast
Ą(yj) jest podziałem zewnętrznym ze względu na yj.
Jeżeli Ą(yj) e" �1" �2" ..." �l to yj jest funkcją jedynie
sygnałów Q1,..., Ql czyli
yj = (Q1,..., Ql)
Piotr Kawalec Wykład II - 8
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 Q1,..., Qk,
natomiast Ą(yj) jest podziałem zewnętrznym ze
względu na yj, gdzie
Ą(yj) = Ąx (yi) " Ąx (yi) " " " Ąx (yi)
1 2 n
Jeżeli Ą(yj) e" �1" �2" ..." �l to yj jest funkcją jedynie
sygnałów wejściowych oraz sygnałów Q1,..., Ql.
yj = (x1,..., xn, Q1,..., Ql)
Piotr Kawalec Wykład II - 9
Technika cyfrowa
Cena sygnału wyjściowego
Dla automatu Moore a jako cenę sygnału A

wyjściowego przyjmuje się
c(yi) = l - 1
gdy yj = (Q1,..., Ql)
Dla automatu Mealy ego cena sygnału wyjściowego
wzrasta o liczbę zmiennych wejściowych n
c(yi) = n + l - 1
A
ączna cena układu uwzględniająca zarówno
cenę podziałów jak i cenę wyjść wyraża się wzorem
c = Ł c(�i) + Ł c(yi)
Piotr Kawalec Wykład II - 10
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 - 11
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ę Tk opt. o minimalnej cenie
Piotr Kawalec Wykład II - 12
Technika cyfrowa
Przykłady kodowania z zastosowaniem
rachunku podziałów
Przykład 1
Zakodować automat zadany tablicą przejść-wyjść
x x1 x2 x1 x2
s
1 1 3 0 1
2 4 2 1 --
3 3 1 1 0
4 1 4 -- 1
Piotr Kawalec Wykład II - 13
Technika cyfrowa
Przykłady kodowania z zastosowaniem
rachunku podziałów
Przykład 2
Zakodować automat zadany tablicą przejść-wyjść
x
s x1 x2 y1 y2
1 1 2 0 0
2 1 3 0 0
3 4 3 -- 0
4 5 3 1 1
5 1 3 0 1
Piotr Kawalec Wykład II - 14