Technika cyfrowa
Wykład XII
Kodowanie z zastosowaniem
rachunku podziałów
Piotr Kawalec Wykład XII - 1
Technika cyfrowa
Plan wykładu
Elementy rachunku podziałów
Zastosowanie rachunku podziałów
do kodowania synchronicznych
układów sekwencyjnych
Przykłady kodowania
Piotr Kawalec Wykład XII - 2
Technika cyfrowa
Podstawowe pojęcia rachunku podziałów
Def 1
Pokryciem C zbioru S nazywamy zbiór podzbiorów
tego zbioru, których suma równa jest S
C = { B1, B2, . . ., Bn }
B1 *" B2 *" . . . *" Bn = S
Piotr Kawalec Wykład XII - 3
Technika cyfrowa
Podstawowe pojęcia rachunku podziałów
Def 2
Podziałem Ą zbioru S nazywamy zbiór
rozłącznych podzbiorów tego zbioru,
których suma równa jest S
Ą = { B1, B2, . . .,Bn }
Bi )" Bj = Ś dla i `" j
B1 *" B2 *" . . . *" Bn = S
Piotr Kawalec Wykład XII - 4
Technika cyfrowa
Podstawowe pojęcia rachunku podziałów
Podzbiory Bi nazywamy blokami i oznaczamy
kreskami nad elementami zbioru S
np. podział Ą = {B1, B2, B3} = { 13, 4, 25 } dzieli
zbiór S = {1,2,3,4,5} na trzy bloki B1= {1,3}; B2={4}; B3={2,5}
W podziale może występować blok, elementy
którego mogą być dołączane do dowolnych innych
bloków podziału. Elementy tego bloku zapisuje się
w nawiasie
Piotr Kawalec Wykład XII - 5
Technika cyfrowa
Podstawowe pojęcia rachunku podziałów
Iloczynem Ą1 " Ą2 podziałów Ą1 i Ą2 nazywamy
podział, którego blokami są przecięcia bloków
podziału Ą1 z blokami podziału Ą2
{134, 256} " {135, 246} = { 13, 4, 5, 26}
Sumą Ą1 + Ą2 podziałów Ą1 i Ą2 nazywamy
najmniejszy podział Ą taki, że jeżeli stan S jest
elementem jakiegoś bloku z Ą1 lub Ą2 to cały ten
blok jest zawarty w jednym bloku podziału Ą
{123, 45} + { 1, 2345} = {12345}
Piotr Kawalec Wykład XII - 6
Technika cyfrowa
Podstawowe pojęcia rachunku podziałów
Podział Ą1 jest nie większy od podziału Ą2 , czyli
Ą1 d" Ą2
gdy każdy blok z Ą1 jest zawarty w pewnym bloku Ą2
{1, 2, 3, 45, 67} d" { 12, 345, 67}
Największym i najmniejszym podziałem zbioru
S = {1,2,3, ..., n}
są odpowiednio podziały
jedynkowy { 12...n } = 1
zerowy { 1, 2, ..., n } = 0
Piotr Kawalec Wykład XII - 7
Technika cyfrowa
Zastosowanie podziałów do kodowania
Podstawowe pojęcia
Zakodowaniu zbioru stanów wewnętrznych S przy
pomocy k sygnałów Q1, . . ., Qk odpowiada k
podziałów dwublokowych �1, �2, . . ., �k.
Jeśli do realizacji automatu chcemy użyć minimalnej
liczby elementów pamięci to należy rozpatrywać
podziały prawidłowe
Podziałami prawidłowymi nazywamy podziały
spełniające warunki:
są to podziały dwublokowe
liczba elementów każdego bloku d" 2k - 1
Piotr Kawalec Wykład XII - 8
Technika cyfrowa
Podstawowe pojęcia
Dla zapewnienia jednoznaczności kodowania
podziały dwublokowe wzięte do kodowania muszą
spełniać warunek
�1 " �2 " " " �k = 0
Rodziną końcową podziałów Tk nazywamy zbiór
podziałów który można przyjąć do kodowania, tzn.
zbiór spełniający warunek zerowego iloczynu
Rodziną końcową optymalną Tkopt nazywamy
rodzinę końcową Tk wyznaczającą kod dający
najprostsze funkcje przejść i wyjść (najprostszy
układ)
Piotr Kawalec Wykład XII - 9
Technika cyfrowa
Podstawowe pojęcia
Ponieważ najprostszy układ będzie miał minimalną
ilość elementów pamięci to przy poszukiwaniu Tkopt
należy rozpatrywać tylko podziały prawidłowe !!!
Sposób zapisu podziałów dwublokowych
indeks przy � odpowiada numerom elementów
tworzących mniej liczny blok podziału
przy jednakowej liczności bloków, indeks tworzą
elementy bloku zawierającego element pierwszy
Piotr Kawalec Wykład XII - 10
Technika cyfrowa
Mechanizm kodowania stanów
Dla automatu o czterech stanach wewnętrznych
istnieją tylko trzy podziały prawidłowe
�12 = {12, 34}; �13 ={13, 24}; �14 = {14, 23}
Podziały te pozwalają utworzyć trzy rodziny
końcowe
Tk1 = {�12 , �13 }; Tk2 = {�12 , �14 }; Tk3 = {�13 , �14 }
Każda z tych rodzin określa inny wariant kodowania
Zarówno sposób przypisania podziałów � do Q,jak
i przypisanie wartości Q =1, oraz Q =0 blokom
podziału nie wpływają na złożoność układu
Piotr Kawalec Wykład XII - 11
Technika cyfrowa
Mechanizm kodowania stanów
Np. rodzinie końcowej Tk1 = {�12 , �13 } mogą
odpowiadać warianty kodowania:
Q
S Q1 Q2 Q1 Q2 Q1 Q2 Q1 Q2
1 0 0 1 0 1 1 0 1
2 0 1 1 1 0 1 1 1
3 1 0 0 0 1 0 0 0
4 1 1 0 1 0 0 1 0
�12 , �13 �12 , �13 �13 , �12 �13 , �12
Zarówno sposób przypisania podziałów � do Q,jak
i przypisanie wartości Q =1, oraz Q =0 blokom
podziału nie wpływają na złożoność układu !!!
Piotr Kawalec Wykład XII - 12
Technika cyfrowa
Para podziałów
Stan wewnętrzny s = � (s,xi) nazywamy
xi - następnikiem stanu s
Para podziałów Ą1 i Ą2 stanów wewnętrznych to
uporządkowana dwójka podziałów Ą1 Ą2 taka, że
dla każdych dwóch stanów zawartych w pewnym
bloku z Ą1 i dla każdego xi �" X, xi - następniki tych
stanów zawarte są w pewnym bloku podziału Ą2
Piotr Kawalec Wykład XII - 13
Technika cyfrowa
Metody znajdowania par podziałów
Przy kodowaniu automatów poszukujemy par
podziałów typu Ąj �i gdzie �i jest danym
podziałem dwublokowym (poszukiwanie
poprzednika z pary podziałów)
Dla wyznaczenia poprzednika podziału �i należy:
zakodować stany w tabeli przejść zgodnie z �i
połączyć w bloki podziału Ąj stany którym
odpowiadają identyczne ciągi w wierszach tablicy
Piotr Kawalec Wykład XII - 14
Technika cyfrowa
Przykład znajdowania par podziałów
Dla zadanej tablicy przejść wyznaczyć podział
poprzedzający dla podziału �13 = {13, 245}
x x1 x2 x x1 x2 x x1 x2
s s s
1 2 3 1 0 1 1 1 0
2 4 5 2 0 0 2 1 1
3 5 4 3 0 0 3 1 1
4 1 1 4 1 1 4 0 0
5 1 -- 5 1 -- 5 0 --
Największy podział Ąj ={1, 23, 45} {13, 245} = �13
Piotr Kawalec Wykład XII - 15
Technika cyfrowa
Inny sposób znajdowania par podziałów
Buduje się kratę w której kreski pionowe
odpowiadają kolumnom, a poziome wierszom tablicy
przejść
Zaznacza się krzyżykami przecięcia kresek
odpowiadające klatkom tablicy w których występują
stany jednego z bloków podziału (przykład z �13 )
x x1 x2 x1 x2
s
1 2 3 1
2 4 5 2
3 5 4 3 {1, 23, 4, 5}
4 1 1 4
5 1 -- 5 {1, 23, 45}
Piotr Kawalec Wykład XII - 16
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 XII - 17
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 XII - 18
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 XII - 19
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 XII - 20
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 XII - 21
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 XII - 22
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 XII - 23
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 XII - 24
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 XII - 25
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 XII - 26
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 XII - 27
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 XII - 28
Technika cyfrowa
Podziały zewnętrzne i grafy podziałów
Ą(y) = Ąx1(y) " Ąx2(y) ={1, 23, (4)} " {14, 3, (2)} = �14
x x1 x2 �1 �2 �3 �4 �12 �13 �14
s
1 1 3 1
2 4 2 2
3 3 1 3
4 1 4 4
�2 �14
�2 {12, 3, 4} �14 �12
Piotr Kawalec Wykład XII - 29
Technika cyfrowa
Wyznaczenie rodzin końcowych i cen
Z grafu podziałów można wyznaczyć rodzinę
końcową Tk ={�12 , �14 }, która jest równocześnie
rodziną optymalną Tk opt
Ceny podziałów c(�12) = 1+1-1=1; c(�14) =1+2-1=2;
c(y)=1+1-1=1; Łc = 4
Kodowanie s �12 �14
1 0 1
2 0 0
3 1 0
4 1 1
Q1 Q2
Piotr Kawalec Wykład XII - 30
Technika cyfrowa
Zakodowana tablica przejść-wyjść
x 0 1 0 1
(s) Q1Q2
(2) 00 11 00 1 --
(1) 01 01 10 0 1
(4) 11 01 11 -- 1
(3) 10 10 01 1 0
Q1Q2 y
Funkcja wyjść
y = xQ2 + xQ2
Piotr Kawalec Wykład XII - 31
Technika cyfrowa
Tablice wzbudzeń przy realizacji na przerzutnikach D
x 0 1 0 1
(s) Q1Q2
(2) 00 1 0 1 0
(1) 01 0 1 1 0
(4) 11 0 1 1 1
(3) 10 1 0 0 0
D1 D2
Funkcje wzbudzeń
D1 = xQ2 + xQ2 ; D2 = xQ1 + Q1Q2
Piotr Kawalec Wykład XII - 32
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 XII - 33