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