ELC dek r p

background image

ZPT

1

V

U

G

H

Y = F(X)

W

czyli U

V X

Dekompozycja metodą rachunku podziałów

X

Ponadto dopuszczamy powiększenie zbioru
argumentów bloku G

U, V są rozłącznymi podzbiorami X,

ale U

V niekoniecznie = X

W jest podzbiorem właściwym U

W

U

background image

ZPT

Elementy rachunku podziałów

Podziałem na zbiorze S jest system zbiorów P = {

B

i

}, którego bloki

są rozłączne, czyli

B

i

B

j

=

φ

, jeśli tylko i

j

Π =

)

4,6

;

3,5

;

1,2

(

Podstawowe pojęcia:

Iloczyn podziałów oraz relacja

≤.

Podzbiory nazywamy

blokami

Dla S = {1,2,3,4,5,6}, P = {{1,2}, {3,5}, {4,6} } jest podziałem na S.



i

i

B

S

=

a ponadto

background image

ZPT

Elementy rachunku podziałów…

Powiemy, że podział P

a

jest nie większy od P

b

(co oznaczamy: P

a

P

b

),

jeśli każdy blok z P

a

jest zawarty w pewnym bloku z P

b

.

Π

b

=

)

3,5

;

2,6

;

1,4

(

)

3,5,6

;

1,2,4

(

)

3,5

;

6

;

4

;

1,2

(

Π

a

=

Π

.

=

Π

c

Π

a

Tak

Π

c

Π

b



</

Π(0) – podział najmniejszy

Π(1) – podział największy

)

3,5

;

6

;

4

;

1,2

(

Π

.

=

)

3,5,6

;

1,2,4

(

Π

a

=

)

3,5

;

6

;

4

;

1,2

(

Π

.

=

Π

b

=

)

3,5

;

2,6

;

1,4

(

background image

ZPT

Elementy rachunku podziałów…

Π

b

=

Iloczynem podziałów

Π

a

Π

b

nazywamy największy (względem

relacji

≤) podział, który jest nie większy od

Π

a

oraz

Π

b

.

)

3,5

;

2,6

;

1,4

(

)

3,5,6

;

1,2,4

(

Π

a

=

Π

a

Π

b

=

;

1,4

(

;

2

)

3,5

;

6

background image

ZPT

Niech P

a

i P

b

są podziałami na S oraz P

a

P

b

. Podział P

a

| P

b

jest

podziałem ilorazowym P

a

i P

b

, jeżeli jego elementy są blokami P

b

,

a bloki są blokami P

a

.

4,5

;

2,3,8

;

1,6,7

P

a

=

6,7

;

4,5

;

3

;

2,8

;

1

P

b

=

Elementy rachunku podziałów…

(4,5)

P

|

P

b

a

=

;

(1)(6,7)

;

(3)(2,8)

Podział ilorazowy

Na przykład:

background image

ZPT

Nowy sposób opisu funkcji - podziały

x

1

x

2

x

3

x

4

x

5

x

6

x

7

f

1

1

0

0

0

1

0

1

0

2

1

0

1

1

1

1

0

0

3

1

1

0

1

1

1

0

0

4

1

1

1

0

1

1

1

0

5

0

1

0

0

1

0

1

1

6

1

0

0

0

1

1

0

1

7

1

0

1

0

0

0

0

1

8

1

0

1

0

1

1

0

1

9

1

1

1

0

1

0

1

1

P

1

=

P

2

=

P

f

=

;

5

{

;

8

,

7

,

6

,

2

,

1

{

;

4

,

3

,

2

,

1

{

}

9

,

8

,

7

,

6

,

4

,

3

,

2

,

1

}

9

,

5

,

4

,

3

P

3

=

;

6

,

5

,

3

,

1

{

}

9

,

8

,

7

,

4

,

2

P

4

=

;

9

,

8

,

7

,

6

,

5

,

4

,

1

{

}

3

,

2

P

5

=

;

7

{

}

9

,

8

,

6

,

5

,

4

,

3

,

2

,

1

P

6

=

;

9

,

7

,

5

,

1

{

}

8

,

6

,

4

,

3

,

2

P

7

=

;

8

,

7

,

6

,

3

,

2

{

}

9

,

5

,

4

,

1

}

9

,

8

,

7

,

6

,

5

Funkcja f

background image

ZPT

7

… w ujęciu rachunku podziałów

Funkcję F: B

n

 {0,1}

m

można zrealizować w strukturze:

F = H(U,G(V,W))

Twierdzenie o dekompozycji

U

G

H

Π

G

P

F

wtedy i tylko wtedy, gdy istnieje podział

Π

G

P

V

W

taki, że:

P

U

·

Π

G

P

F

background image

ZPT

8

Twierdzenie o dekompozycji - interpretacja

Π

G

P

V

W

taki, że: P

U

·

Π

G

P

F

F

Y = F(X)

X

Y = H(U,G(V,W))

U

G

H

Π

G

X

Π

Π

Π

Π

G

P

U

P

V

W

(P

V

)

P

F

to podziały indukowane przez
argumenty zbiorów U, V

∪ W, (V)

Podział wyjściowy funkcji F

Trzeba obliczyć!!!

background image

ZPT

9

Przykład (TL27) ilustrujący skuteczność

dekompozycji

.type fr

.i 10

.o 1

.p 25

0010111010 0

1010010100 0

0100011110 0

1011101011 0

1100010011 0

0100010110 0

1110100110 0

0100110000 0

0101000010 0

0111111011 1

0000010100 1

1101110011 1

0100100000 1

0100011111 1

0010000110 1

1111010001 1

1111101001 1

1111111111 1

0010000000 1

1101100111 1

0010001111 1

1111100010 1

1010111101 1

0110000110 1

0100111000 1

.e

Można wykazać, że funkcja ta

jest zależna od

7 argumentów

X = {x

3

, x

5

, x

6

, x

7

, x

8

, x

9

, x

10

}

Książka Programowalne układy… str. 52

Dalej wszystkie obliczenia będą wykonywane na podziałach

P

3

, P

5

, P

6

, P

7

, P

8

, P

9

, P

10

Celem przykładu jest pokazanie, że cały proces

dekompozycji (łącznie z obliczeniem tablic prawdy)

można wykonać wyłącznie na podziałach

Są to podziały na zbiorze ponumerowanych

wektorów 1,…,25

background image

ZPT

10

Specyfikacja funkcji – podziałami

P

3

=

;

25

,

20

,

14

,

13

,

12

,

11

,

9

,

8

,

6

,

5

,

3

{

}

24

,

23

,

22

,

21

,

19

,

18

,

17

,

16

,

15

,

10

,

7

,

4

,

2

,

1

P

5

=

;

24

,

21

,

19

,

16

,

15

,

14

,

11

,

9

,

6

,

5

,

3

,

2

{

}

25

,

23

,

22

,

20

,

18

,

17

,

13

,

12

,

10

,

8

,

7

,

4

,

1

P

6

=

;

24

,

22

,

21

,

20

,

19

,

17

,

15

,

13

,

9

,

7

,

4

{

}

25

,

23

,

18

,

16

,

14

,

12

,

11

,

10

,

8

,

6

,

5

,

3

,

2

,

1

P

f

=

;

9

,...,

2

,

1

{

}

25

,...,

10

P

7

=

;

24

,

22

,

20

,

19

,

16

,

15

,

13

,

12

,

11

,

9

,

8

,

7

,

6

,

5

,

2

{

}

25

,

23

,

21

,

18

,

17

,

14

,

10

,

4

,

3

,

1

P

8

=

;

25

,

22

,

19

,

17

,

16

,

13

,

12

,

10

,

9

,

8

,

5

,

4

,

1

{

}

24

,

23

,

21

,

20

,

18

,

15

,

14

,

11

,

7

,

6

,

3

,

2

P

9

=

;

25

,

23

,

19

,

17

,

16

,

13

,

11

,

8

,

2

{

}

24

,

22

,

21

,

20

,

18

,

15

,

14

,

12

,

10

,

9

,

7

,

6

,

5

,

4

,

3

,

1

P

10

=

;

25

,

24

,

22

,

19

,

15

,

13

,

11

,

9

,

8

,

7

,

6

,

3

,

2

,

1

{

}

23

,

21

,

20

,

18

,

17

,

16

,

14

,

12

,

10

,

5

,

4

background image

ZPT

11

Ustalenie zbiorów U i V

X = {x

3

, x

5

, x

6

, x

7

, x

8

, x

9

, x

10

}

U = {x

7

, x

8

, x

9

}

V = {x

3

, x

5

, x

6

, x

10

}

f

G

H

x

7

x

8

x

9

x

3

x

5

x

6

x

10

Przyjmujemy arbitralnie…

Nie wiemy ile jest

wyjść z bloku G

background image

ZPT

12

Obliczenie podziałów P

U

, P

V

)

23

;

17,25

;

8,13,16,19

;

24

6,7,15,20,

;

5,9,12,22

;

3,14,18,21

;

2,11

;

1,4,10

(

P

V

=

)

21

;

20

;

16

;

15,19,24

;

13

;

12

;

10,18,23

;

9

;

8,25

;

7,22

;

5,14

;

4,17

;

3,6,11

;

2

;

1

(

P

U

=

P

U

=P

7

•P

8

•P

9

P

V

=P

3

•P

5

•P

6

•P

10

Można je wyznaczyć bezpośrednio z tablicy funkcji, ale
tym razem przy zastosowaniu rachunku podziałów:

…obliczenia są żmudne, ale proste

U = {x

7

, x

8

, x

9

} V = {x

3

, x

5

, x

6

, x

10

}

background image

ZPT

13

)

23

;

17,25

;

8,13,16,19

;

24

6,7,15,20,

;

5,9,12,22

;

3,14,18,21

;

2,11

;

1,4,10

(

((1,4)(10)

P

U

=

P

f

=

;

1,2,...,9

{

10,...,25}

Podział ilorazowy P

u

|P

u

P

F

; (2)(11)

(6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23))

; (3)(14,18,21) ; (5,9)(12,22)

P

u

|P

u

P

f

=

Przy liczeniu podziału ilorazowego po prostu rozdzielamy
elementy bloków P

U

między różne bloki podziału P

f

W każdym bloku P

u

|P

u

• P

f

są co najwyżej dwa elementy (nawiasy),

zatem liczba bloków podziału Π

G

musi być co najmniej dwa.

background image

ZPT

14

Obliczenie Π

G

)

24

23,

21,

20,

19,

18,

4,15,16,

13,1

10,

2,5,9,

;

25

22,

17,

11,12,

7,8,

6,

1,3,4,

(

Π

g

=

P

u

|P

u

· P

f

= ((1,4)(10) ; (2)(11) ; (3)(14,18,21) ; (5,9)(12,22) ;

(6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23))

P

V

=

)

21

;

20

;

16

;

15,19,24

;

13

;

12

;

10,18,23

;

9

;

8,25

;

7,22

;

5,14

;

4,17

;

3,6,11

;

2

;

1

(

4,17

1

10,18,23

3,6,11

2

5,14

12

7,22

8,25

9

15,19,24

20

13

16

21

background image

ZPT

15

Liczba wyjść bloku G

f

G

H

x

7

x

8

x

9

x

3

x

5

x

6

x

10

Liczba wyjść z bloku G = 1

Skoro Π

G

jest dwublokowy

f

G

H

x

7

x

8

x

9

x

3

x

5

x

6

x

10

background image

ZPT

16

Co dalej …

Zawartość bloków G i H, czyli tablice prawdy
funkcji G i H

f

G

H

x

7

x

8

x

9

x

3

x

5

x

6

x

10

background image

ZPT

17

Funkcja G

x

3

x

5

x

6

x

10

g

P

V

=

)

21

;

20

;

16

;

15,19,24

;

13

;

12

;

10,18,23

;

9

;

8,25

;

7,22

;

5,14

;

4,17

;

3,6,11

;

2

;

1

(

1 1 1 0

0

1 0 1 0

1

0 0 1 0

0

)

24

23,

21,

20,

19,

18,

4,15,16,

13,1

10,

2,5,9,

;

25

22,

17,

11,12,

7,8,

6,

1,3,4,

(

Π

g

=

P

3

=

;

25

,

20

,

14

,

13

,

12

,

11

,

9

,

8

,

6

,

5

,

3

{

}

24

,

23

,

22

,

21

,

19

,

18

,

17

,

16

,

15

.

10

,

7

,

4

,

2

,

1

P

5

=

;

24

,

21

,

19

,

16

,

15

,

14

,

11

,

9

,

6

,

5

,

3

,

2

{

}

25

,

23

,

22

,

20

,

18

,

17

,

13

,

12

,

10

,

8

,

7

,

4

,

1

P

6

=

;

24

,

22

,

21

,

20

,

19

,

17

,

15

,

13

,

9

,

7

,

4

{

}

25

,

23

,

18

,

16

,

14

,

12

,

11

,

10

,

8

,

6

,

5

,

3

,

2

,

1

P

10

=

;

25

,

24

,

22

,

19

,

15

,

13

,

11

,

9

,

8

,

7

,

6

,

3

,

2

,

1

{

}

23

,

21

,

20

,

18

,

17

,

16

,

14

,

12

,

10

,

5

,

4

Wektory (wiersze) tablicy funkcji g
są wyznaczane przez bloki P

V

,

a wartości tej funkcji przez bloki Π

G

background image

ZPT

18

Funkcja H

x

7

x

8

x

9

g

h

...)

14,18,21

;

3

;

11

;

2

;

10

;

1,4

(

=

P

U

• Π

G

< P

F

1 0 1 0

0

1 0 1 1

1

0 1 0 1

0

P

7

=

;

24

,

22

,

20

,

19

,

16

,

15

,

13

,

12

,

11

,

9

,

8

,

7

,

6

,

5

,

2

{

}

25

,

23

,

21

,

18

,

17

,

14

,

10

,

4

,

3

,

1

P

8

=

;

25

,

22

,

19

,

17

,

16

,

13

,

12

,

10

,

9

,

8

,

5

,

4

,

1

{

}

24

,

23

,

21

,

20

,

18

,

15

,

14

,

11

,

7

,

6

,

3

,

2

P

9

=

;

25

,

23

,

19

,

17

,

16

,

13

,

11

,

8

,

2

{

}

24

,

22

,

21

,

20

,

18

,

15

,

14

,

12

,

10

,

9

,

7

,

6

,

5

,

4

,

3

,

1

)

24

23,

21,

20,

19,

18,

4,15,16,

13,1

10,

2,5,9,

;

25

22,

17,

11,12,

7,8,

6,

1,3,4,

(

Π

g

=

Wektory (wiersze) tablicy
funkcji h są wyznaczane
przez bloki P

U

• Π

G

, a wartości

tej funkcji przez bloki P

F

background image

ZPT

19

Co uzyskaliśmy…

f

G

H

x

7

x

8

x

9

x

3

x

5

x

6

x

10

Tylko 2 komórki typowej

struktury FPGA

QUARTUS

Uzyskaliśmy wynik dziesięciokrotnie razy lepszy od

wyniku systemu Quartus amerykańskiej firmy

Altera

23 kom.

background image

ZPT

20

Dekompozycja zespołu funkcji

X

F

X

G

H

Y

U

V

Y = y

1

, y

2

,…, y

m

Twierdzenie w ujęciu rachunku podziałów jest ogólne,
obliczenia są niezależne od liczby wyjść funkcji F.

Dekompozycja

background image

ZPT

21

x

1

x

2

x

3

x

4

x

5

y

1

y

2

y

3

1

0 0 0 0 0

0 0 0

2

0 0 0 1 1

0 1 0

3

0 0 0 1 0

1 0 0

4

0 1 1 0 0

0 1 1

5

0 1 1 0 1

0 0 1

6

0 1 1 1 0

0 1 0

7

0 1 0 0 0

0 0 1

8

1 1 0 0 0

0 0 1

9

1 1 0 1 0

0 0 0

10

1 1 1 0 0

1 0 0

11

1 1 1 1 1

0 1 1

12

1 1 1 1 0

0 1 0

13

1 0 0 0 1

0 0 1

14

1 0 0 1 1

0 0 0

15

1 0 0 1 0

1 0 0

)

15

,

14

,

13

,

12

,

11

,

10

,

9

,

8

;

7

,

6

,

5

,

4

,

3

,

2

,

1

(

1

=

P

;

14

,

9

,

1

(

Przykład dekompozycji zespołu funkcji (SUL Przykład 8.4)

)

12

,

11

,

10

,

9

,

8

,

7

,

6

,

5

,

4

;

15

,

14

,

13

,

3

,

2

,

1

(

2

=

P

)

12

,

11

,

10

,

6

,

5

,

4

;

15

,

14

,

13

,

9

,

8

,

7

,

3

,

2

,

1

(

3

=

P

)

15

,

14

,

12

,

11

,

9

,

6

,

3

,

2

;

13

,

10

,

8

,

7

,

5

,

4

,

1

(

4

=

P

)

14

,

13

,

11

,

5

,

2

;

15

,

12

,

10

,

9

,

8

,

7

,

6

,

4

,

3

,

1

(

5

=

P

Niezależnie od liczby
funkcji wszystkie
wyjścia opisujemy

jednym!

podziałem

;

15

,

10

,

3

)

11

,

4

;

13

,

8

,

7

,

5

;

12

,

6

,

2

v

v

v

v

v

v

=

F

P

background image

ZPT

22

Przykład…wyznaczanie podziałów

P

U

, P

V

U = {x

3

,x

4

} V = {x

1

,x

2

,x

5

}

6,11,12

;

4,5,10

;

5

2,3,9,14,1

;

1,7,8,13

P

U

=

3,10,15

;

4,11

;

2,6,12

;

5,7,8,13

;

1,9,14

P

F

=

;

)

(1)(7,8,13

P

U

= P

3

P

4

P

V

=P

1

P

2

P

5

=

F

U

U

P

P

|

P

;

3,15)

(2)(9,14)(

(11)(6,12)

;

(4)(5)(10)

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

x

3

x

4

x

1

x

2

x

5

g

h

• • •

Szukamy dekompozycji

background image

ZPT

23

Przykład…obliczanie

Π

Π

Π

Π

G

(2)

(9,14)

(3,15)

2

12

,

10

,

9

,

8

14

,

13

3

,

1

15

7

,

6

,

4

5

11

5

1,3,5,11,1

;

13,14

8,9,10,12,

;

2,4,6,7

Π

G

=

(11)(6,12)

;

(4)(5)(10)

;

3,15)

(2)(9,14)(

;

)

(1)(7,8,13

P

|

P

F

U

=

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

Jak wyznaczyć

Π

Π

Π

Π

G

???

Trochę
inny
zapis

background image

ZPT

24

Przykład…kodowanie

Π

G

5

1,3,5,11,1

;

;

13,14

8,9,10,12,

2,4,6,7

=

Π

G

Należy zakodować bloki Π

G

01

10

00

Kodowanie jest dowolne

Aktualna teoria nie podaje rozwiązania

problemu kodowania

W przypadku zespołu funkcji liczba bloków podziału Π

G

jest większa.

Kodowanie jest potrzebne do wyznaczenia tablic prawdy funkcji G i H

background image

ZPT

25

Tablica prawdy G

)

14

,

13

,

11

,

5

,

2

;

15

,

12

,

10

,

9

,

8

,

7

,

6

,

4

,

3

,

1

(

)

12

,

11

,

10

,

9

,

8

,

7

,

6

,

5

,

4

;

15

,

14

,

13

,

3

,

2

,

1

(

)

15

,

14

,

13

,

12

,

11

,

10

,

9

,

8

;

7

,

6

,

5

,

4

,

3

,

2

,

1

(

5

2

1

=

=

=

P

P

P

x

1

x

2

x

5

g

1

g

2

. . .

. . .

3

,

1

2

7

,

6

,

4

5

1,3,5,11,1

;

;

13,14

8,9,10,12,

2,4,6,7

=

Π

G

01

10

00

0 0 0

0 0 1

0 1 0

0 0

0 1

0 1

5

0 1 1

0 0

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

background image

ZPT

26

Tablica prawdy H

x

3

x

4

g

1

g

2

y

1

y

2

y

3

. . .

. . .

1

7

13

,

8

15

,

3

)

15

,

14

,

12

,

11

,

9

,

6

,

3

,

2

;

13

,

10

,

8

,

7

,

5

,

4

,

1

(

)

12

,

11

,

10

,

6

,

5

,

4

;

15

,

14

,

13

,

9

,

8

,

7

,

3

,

2

,

1

(

4

3

=

=

P

P

P

U

• Π

G

=

5

1,3,5,11,1

;

;

13,14

8,9,10,12,

2,4,6,7

=

Π

G

01

10

00

0 0 0 0
0 0 0 1
0 0 1 0

0 1 0 0

0 0 0

1 0 0

0 0 1

0 0 1

;

7

;

13

,

8

;

15

,

3

;

1

(

P

U

• Π

G

< P

F

6,11,12

;

4,5,10

;

5

2,3,9,14,1

;

1,7,8,13

P

U

=

background image

ZPT

27

Co uzyskaliśmy…

Ale dla struktur FPGA
wystarczy schemat
dekompozycji i tablice
prawdy.

Funkcje g i h można obliczyć jawnie…z tablic prawdy
można uzyskać realizacje na bramkach.

x

3

x

4

x

1

x

2

x

5

g

h

Proces minimalizacji
jest niepotrzebny!!!

background image

ZPT

28

Obliczanie podziału Π

G

metodą

przenoszenia bloków P

V

na podstawie

podziału ilorazowego P

U

│P

U

Π

G

jest

trudne do zalgorytmizowania.

Szczęśliwie jednak algorytm obliczania
Π

G

można sprowadzić do algorytmu

obliczania MKZ.

Systematyczny algorytm dekompozycji

background image

ZPT

29

Systematyczny algorytm dekompozycji

Dwa bloki B

i

i B

j

podziału P

V

są zgodne, jeśli podział

γ

ij

uzyskany z P

V

przez sklejenie B

i

oraz B

j

w jeden blok i

pozostawienie pozostałych bloków bez zmiany

W przeciwnym przypadku B

i

oraz B

j

są niezgodne.

P

V

=( B

1

,…,B

i

,…,B

j

,…,B

N

)

γ

ij

=( B

1

,…,B

i

B

j

,…,B

N

)

spełnia warunek Twierdzenia o dekompozycji: P

U

• γ

ij

≤ P

F

.

background image

ZPT

30

Przykład (ten sam co poprzednio)

6,11,12

;

4,5,10

;

5

2,3,9,14,1

;

1,7,8,13

P

U

=

3,10,15

;

4,11

;

2,6,12

;

5,7,8,13

;

1,9,14

P

F

=

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

B

1

B

2

B

3

B

4

B

5

B

6

B

7

B

8

(11)(6,12)

;

(4)(5)(10)

;

3,15)

(2)(9,14)(

;

)

(1)(7,8,13

P

P

|

P

F

U

U

=

γ

57

=

γ

12

=

;

1,2,3

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

13,14

8,9,10,12,

;

5

;

4,6,7

;

2

;

1,3

15

;

11

U = {x

3

,x

4

} oraz V = {x

1

,x

2

,x

5

}

Numerujemy bloki P

V

background image

ZPT

31

Przykład …

Ale do wyznaczenia zgodnych (lub sprzecznych) par (B

i

, B

j

)

niekoniecznie musimy się posługiwać skomplikowaną
nierównością P

U

γ

ij

P

F

Można sprawdzić, że

P

U

• γ

12

P

F

,

P

U

• γ

57

P

F

</

(B

1

, B

2

) jest sprzeczna

(B

5

, B

7

) jest zgodna

Wystarczy w tym celu obliczyć iloczyn zbioru B

i

∪ B

j

z blokami podziału P

U

i sprawdzić, czy każdy „niepusty

iloczyn” jest zawarty w jakimś bloku P

F

background image

ZPT

32

Przykład …

6,11,12

;

4,5,10

;

5

2,3,9,14,1

;

1,7,8,13

P

U

=

3,10,15

;

4,11

;

2,6,12

;

5,7,8,13

;

1,9,14

P

F

=

B

1

B

2

B

3

B

4

B

5

B

6

B

7

B

8

(B

1

,B

2

) jest sprzeczna

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

B

1

B

2

=

1,2,3

1,2,3

P

U

)

( 2,3

;

1

=

</

P

F

B

5

B

7

=

13,14

8,9,10,12,

13,14

8,9,10,12,

P

U

12

;

10

;

9,14

;

8,13

=

≤ P

F

(B

5

, B

7

) jest zgodna

background image

ZPT

33

Przykład c.d.

Pary zgodne: (B

1

,B

4

), (B

1

,B

6

), (B

1

,B

8

), (B

2

,B

3

), (B

2

,B

4

), (B

2

,B

6

), (B

3

,B

7

),

(B

3,

B

8

), (B

4

,B

6

), (B

4

,B

7

), (B

4

,B

8

), (B

5

,B

7

), (B

6

,B

7

), (B

6

,B

8

).

Doskonale wiemy jak obliczać

Maksymalne Klasy Zgodne

MKZ

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

B

1

B

2

B

3

B

4

B

5

B

6

B

7

B

8

=

Π

G

;

{B

1

,B

4

, B

6

, B

8

}

;

{B

2

, B

3

}

{B

5

, B

7

}

Klasy maksymalne:

{B

1

,B

4

, B

6

, B

8

}

{B

4

, B

6

, B

7

}

{B

2

, B

4

, B

6

}

{B

3

, B

7

}

{B

3

, B

8

}

{B

2

, B

3

}

{B

5

, B

7

}

background image

ZPT

34

Przykład c.d.

5

1,3,5,11,1

;

13,14

8,9,10,12,

;

2,4,6,7

=

Π

G

15

;

13,14

;

11

;

8,9,10,12

;

5

;

4,6,7

;

2

;

1,3

P

V

=

B

1

B

2

B

3

B

4

B

5

B

6

B

7

B

8

Ten sam rezultat co poprzednio

=

Π

G

;

{B

1

,B

4

, B

6

, B

8

}

;

{B

2

, B

3

}

{B

5

, B

7

}

background image

ZPT

35

Komentarz: algorytmy dekompozycji

Y

A

B

X

G

H

Szeregowa

X

Yg

Yh

G

H

Równoległa

Dekompozycję funkcjonalną nazywać będziemy szeregową, dla

odróżnienia od równoległej


Wyszukiwarka

Podobne podstrony:
ELC dek klas
ELC dek klas
DEK I 0
ELC met synt
porzÄ dek koryncki
retencja moja, Dek
Dek praw człowieka,karta narodów zjednoczonych,konwencja o prawach dziecka
PORZ DEK PRAWNY WSPOLNOT EUROPEJSKICH, SWPS SOCJOLOGIA, INSTYTUCJE UNII EUROPEJSKIEJ I JEJ EWOLUCJA
ELC VHDL
TC dek roz
ELC VHDL cz 1
Eo Loira, Augusto J Cent dek tri humorajxoj
024a rozp min bud zmien rozp w spr spos dek zgod wyr bud oraz spos zna ich zn bud
ELC Bin2BCD
DEK-I-0

więcej podobnych podstron