Piotr Kawalec
Wykład I - 1
Wykład I
Elementy rachunku
podziałów
Technika cyfrowa
Piotr Kawalec
Wykład I - 1
Wykład I
Elementy rachunku
podziałów
Technika cyfrowa
Piotr Kawalec
Wykład I - 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
= { B
1
, B
2
, . . ., B
n
}
B
1
B
2
. . . B
n
=
S
Piotr Kawalec
Wykład I - 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
= { B
1
, B
2
, . . .,B
n
}
B
i
B
j
=
dla i j
B
1
B
2
. . . B
n
=
S
Piotr Kawalec
Wykład I - 4
Technika cyfrowa
Podstawowe pojęcia rachunku
podziałów
Podzbiory B
i
nazywamy
blokami
i
oznaczamy
kreskami nad elementami zbioru
S
np. podział
= {B
1
, B
2
, B
3
} = {
13
,
4
,
25
} dzieli
zbiór S = {1,2,3,4,5} na trzy bloki
B
1
= {1,3};
B
2
={4};
B
3
={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 I - 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 I - 6
Technika cyfrowa
Podstawowe pojęcia rachunku
podziałów
Podział
1
jest
nie większy
od podziału
2
,
czyli
1
2
gdy każdy blok z
1
jest zawarty w pewnym
bloku
2
{1, 2, 3, 45, 67}
{ 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 I - 7
Technika cyfrowa
Zastosowanie podziałów do
kodowania
Podstawowe pojęcia
Zakodowaniu zbioru stanów wewnętrznych
S
przy
pomocy
k
sygnałów
Q
1
, . . ., Q
k
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
2
k - 1
Piotr Kawalec
Wykład I - 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
T
k
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ą
T
k opt
nazywamy
rodzinę końcową
T
k
wyznaczającą kod
dający
najprostsze funkcje przejść i
wyjść (najprostszy
układ)
Piotr Kawalec
Wykład I - 9
Technika cyfrowa
Podstawowe pojęcia
Ponieważ
najprostszy układ będzie miał
minimalną ilość elementów pamięci to przy
poszukiwaniu
T
k opt
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 I - 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
T
k1
= {
12
,
13
}; T
k2
= {
12
,
14
}; T
k3
= {
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 I - 11
Technika cyfrowa
Mechanizm kodowania stanów
Np. rodzinie końcowej
T
k1
= {
12
,
13
}
mogą
odpowiadać warianty kodowania:
Q
S
Q
1
Q
2
Q
1
Q
2
Q
1
Q
2
Q
1
Q
2
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 I - 12
Technika cyfrowa
Para podziałów
Stan wewnętrzny s’ = (s,x
i
) nazywamy
x
i
- 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
x
i
X,
x
i
- następniki
tych stanów zawarte są w
pewnym bloku podziału
2
Piotr Kawalec
Wykład I - 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 I - 14
Technika cyfrowa
Przykład znajdowania par podziałów
Dla zadanej tablicy przejść wyznaczyć podział
poprzedzający dla podziału
13
= {13, 245}
x x
1
x
2
x x
1
x
2
x x
1
x
2
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 I - 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 x
1
x
2
x
1
x
2
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 I - 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
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 I - 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
1
2
i
1
2
...
l