Wykład XII Rachunek podziałów

background image

Piotr Kawalec

Wykład XII - 1

Wykład XII

Zastosowanie rachunku

podziałów do kodowania

automatów synchronicznych

Technika cyfrowa

background image

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

= { B

1

, B

2

, . . ., B

n

}

B

1

 B

2

. . .  B

n

=

S

background image

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

= { B

1

, B

2

, . . .,B

n

}

B

i

 B

j

=

dla i  j

B

1

 B

2

. . .  B

n

=

S

background image

Piotr Kawalec

Wykład XII - 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

background image

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}

background image

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

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

background image

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

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

background image

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

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)

background image

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

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

background image

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

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

background image

Piotr Kawalec

Wykład XII -
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 !!!

background image

Piotr Kawalec

Wykład XII -
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

background image

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

background image

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 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

background image

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 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}

background image

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

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

)

background image

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

1

2

i

1

2

...

l


Document Outline


Wyszukiwarka

Podobne podstrony:
Wykład II Kodowanie z rachunkiem podziałów
Wykład I Rachunek podziałów
Wykład XII
12i13Prawo Cywilne Wykład XII i XIII 7 i! styczeń
Wyklad II -psychopatologia i podzial w ICD 10, Psychopatologia
Wyklad XII- Przedstrunowce Strunowce- Ryby, Biologia, zoologia
IKONOGRAFIA ŚWIĘTYCH, WYKŁAD XII, 01 11
Mikrobiologia wykład XII, XIII
Wykład 2, Mapy, skale i podziałk
wykład 1 wstęp domikrobiologii, podział organizmow
Rachunkowość wykład 14, Rachunkowość - Jacek Jaworski
Ubezpieczenia gospodarcze wyklady(1), FINANSE I RACHUNKOWOŚĆ, System Ubezpieczeń
Modele rachunku kosztów Wykład 3, UEK, Rachunek Kosztów
Wykład XII  01 01 Splot lędźwiowy
WYKŁAD XII (4)

więcej podobnych podstron