Dekompozycja metodą rachunku podziałów
X
U, V są rozłącznymi podzbiorami X,
U
W
V
ale U *" V niekoniecznie = X
G
czyli U *" V Ä…" X
H
W jest podzbiorem właściwym U
W ‚" U
Y = F(X)
Ponadto dopuszczamy powiększenie zbioru
argumentów bloku G
ZPT
1
Elementy rachunku podziałów
Podziałem na zbiorze S jest system zbiorów P = {Bi }, którego bloki
są rozłączne, czyli
Bi )" Bj =Ć, jeśli tylko i `" j
a ponadto S = Bi

i
Dla S = {1,2,3,4,5,6}, P = {{1,2}, {3,5}, {4,6} } jest podziałem na S.
 =
(1,2; 3,5;4,6)
Podzbiory nazywamy
blokami
Podstawowe pojęcia:
Iloczyn podziałów oraz relacja d".
ZPT
Elementy rachunku podziałów&
Powiemy, że podział Pa jest nie większy od Pb (co oznaczamy: Pa d" Pb ),
jeśli każdy blok z Pa jest zawarty w pewnym bloku z Pb.
a = b = . =
(1,2,4;3,5,6) (1,4; 2,6;3,5) (1,2; 4;6;3,5)
a =
(1,2,4;3,5,6)
c d" a Tak
. =
(1,2; 4;6;3,5)
c  NIE!
<
/ b
(0)  podział najmniejszy
b =
(1,4; 2,6;3,5)
(1)  podział największy
. =
(1,2; 4;6;3,5)
ZPT
Elementy rachunku podziałów&
Iloczynem podziałów a " b nazywamy największy (względem
relacji d") podział, który jest nie większy od a oraz b.
a = b =
(1,2,4;3,5,6) (1,4; 2,6;3,5)
a " b =
(1,4; 2;6; 3,5)
ZPT
Elementy rachunku podziałów&
Podział ilorazowy
Niech Pa i Pb są podziałami na S oraz Pa e" Pb. Podział Pa | Pb jest
podziałem ilorazowym Pa i Pb , jeżeli jego elementy są blokami Pb,
a bloki sÄ… blokami Pa.
Na przykład:
Pa =1,6,7; 2,3,8;4,5
Pb = 1; 2,8; 3; 4,5; 6,7
(1)(6,7) ; (3)(2,8) ; (4,5)
Pa|Pb =
ZPT
Nowy sposób opisu funkcji - podziały
x1 x2 x3 x4 x5 x6 x7 f
Funkcja f
1 1 0 0 0 1 0 1 0
2 1 0 1 1 1 1 0 0
P1 = {5; 3 1 1 0 1 1 1 0 0
1,2,3,4,6,7,8,9}
4 1 1 1 0 1 1 1 0
{1,2,6,7,8; 3,4,5,9}
P2 =
5 0 1 0 0 1 0 1 1
{1,3,5,6; 2,4,7,8,9}
P3 =
6 1 0 0 0 1 1 0 1
{1,4,5,6,7,8,9; 2,3}
P4 =
7 1 0 1 0 0 0 0 1
8 1 0 1 0 1 1 0 1
1,2,3,4,5,6,8,9}
{7;
P5 =
9 1 1 1 0 1 0 1 1
{1,5,7,9; 2,3,4,6,8}
P6 =
1,4,5,9}
{2,3,6,7,8;
P7 =
Pf = {1,2,3,4;
5,6,7,8,9}
ZPT
Twierdzenie o dekompozycji
& w ujęciu rachunku podziałów
Funkcję F: Bn {0,1}m można zrealizować w strukturze:
U
F = H(U,G(V,W))
G

G
H
PF
wtedy i tylko wtedy, gdy istnieje podział G e" PV*"W taki, że:
PU · G d" PF
ZPT
7
Twierdzenie o dekompozycji - interpretacja
X
X
U
G
F

G
H
Y = F(X)
Y = H(U,G(V,W))
G e" PV*"W taki, że: PU · G d" PF
PU PV*"W (PV)
to podziały indukowane przez
argumenty zbiorów U, V *" W, (V)
PF
Podział wyjściowy funkcji F
G



Trzeba obliczyć!!!
ZPT
8
Przykład (TL27) ilustrujący skuteczność
dekompozycji
.type fr
Książka Programowalne układy& str. 52
.i 10
.o 1
.p 25
Można wykazać, że funkcja ta
0010111010 0
1010010100 0
jest zależna od 7 argumentów
0100011110 0
1011101011 0
1100010011 0
0100010110 0
X = {x3, x5, x6, x7, x8, x9, x10}
1110100110 0
0100110000 0
0101000010 0
Celem przykładu jest pokazanie, że cały proces
0111111011 1
dekompozycji (Å‚Ä…cznie z obliczeniem tablic prawdy)
0000010100 1
1101110011 1
można wykonać wyłącznie na podziałach
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
Dalej wszystkie obliczenia będą wykonywane na podziałach
0010000000 1
1101100111 1
P3, P5, P6, P7, P8, P9, P10
0010001111 1
1111100010 1
1010111101 1
0110000110 1
Są to podziały na zbiorze ponumerowanych
0100111000 1
wektorów 1,& ,25
.e
ZPT
9
Specyfikacja funkcji  podziałami
{3,5,6,8,9,11,12,13,14,20,25; 1,2,4,7,10,15,16,17,18,19,21,22,23,24}
P3 =
P5 =
{2,3,5,6,9,11,14,15,16,19,21,24; 1,4,7,8,10,12,13,17,18,20,22,23,25}
P6 =
{4,7,9,13,15,17,19,20,21,22,24; 1,2,3,5,6,8,10,11,12,14,16,18,23,25}
P7 =
{2,5,6,7,8,9,11,12,13,15,16,19,20,22,24; 1,3,4,10,14,17,18,21,23,25}
{1,4,5,8,9,10,12,13,16,17,19,22,25; 2,3,6,7,11,14,15,18,20,21,23,24}
P8 =
{2,8,11,13,16,17,19,23,25; 1,3,4,5,6,7,9,10,12,14,15,18,20,21,22,24}
P9 =
{1,2,3,6,7,8,9,11,13,15,19,22,24,25; 4,5,10,12,14,16,17,18,20,21,23}
P10 =
Pf = {1,2,...,9;
10,...,25}
ZPT
10
Ustalenie zbiorów U i V
X = {x3, x5, x6, x7, x8, x9, x10}
Przyjmujemy arbitralnie&
V = {x3, x5, x6, x10}
U = {x7, x8, x9}
x3 x5 x6 x10
G
x7 x8 x9
Nie wiemy ile jest
wyjść z bloku G
H
f
ZPT
11
Obliczenie podziałów PU, PV
Można je wyznaczyć bezpośrednio z tablicy funkcji, ale
tym razem przy zastosowaniu rachunku podziałów:
U = {x7, x8, x9} V = {x3, x5, x6, x10}
PU=P7" P8" P9
& obliczenia sążmudne, ale proste
PV=P3" P5" P6" P10
(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)
PU =
(1 ; 2 ; 3,6,11 ;4,17;5,14;7,22 ;8,25 ;9; 10,18,23 ;12; 13; 15,19,24 ; 16 ; 20 ; 21)
PV=
ZPT
12
Podział ilorazowy Pu|Pu" PF
(1,4,10 ; 2,11 ; 3,14,18,21 ;5,9,12,22 ; 6,7,15,20,24 ;
PU =
8,13,16,19 ; 17,25 ; 23)
Pf = {1,2,...,9 ; 10,...,25}
Przy liczeniu podziału ilorazowego po prostu rozdzielamy
elementy bloków PU między różne bloki podziału Pf
; (5,9)(12,22)
; (3)(14,18,21)
((1,4)(10) ; (2)(11)
Pu|Pu" Pf =
(6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23))
W każdym bloku Pu|Pu" Pf są co najwyżej dwa elementy (nawiasy),
zatem liczba bloków podziału G musi być co najmniej dwa.
ZPT
13
Obliczenie G
Pu|Pu · Pf = ((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))
PV=
(1 ; 2 ; 3,6,11 ;4,17;5,14;7,22 ;8,25 ;9; 10,18,23 ;12; 13; 15,19,24 ; 16 ; 20 ; 21)
1 4,17 10,18,23
3,6,11 2 5,14 21
12 7,22 9 15,19,24 20
8,25 13 16
g = (1,3,4,6, 7,8, 11,12,17, 22, 25 ; 2,5,9,10, 13,14,15,16,18, 19, 20, 21, 23, 24)
ZPT
14
Liczba wyjść bloku G
Skoro G jest dwublokowy
x3 x5 x6 x10
x3 x5 x6 x10
G
G
x7 x8 x9
x7 x8 x9
Liczba wyjść z bloku G = 1
H
H
f
f
ZPT
15
Co dalej &
x3 x5 x6 x10
G
x7 x8 x9
H
f
Zawartość bloków G i H, czyli tablice prawdy
funkcji G i H
ZPT
16
Funkcja G
PV=
(1 ; 2 ; 3,6,11 ;4,17;5,14;7,22 ;8,25 ;9; 10,18,23 ;12; 13; 15,19,24 ; 16 ; 20 ; 21)
x3 x5 x6 x10 g
Wektory (wiersze) tablicy funkcji g
sÄ… wyznaczane przez bloki PV,
1 1 1 0
a wartości tej funkcji przez bloki G
0
1
1 0 1 0
0 0 1 0
0
{3,5,6,8,9,11,12,13,14,20,25; 1,2,4,7,10.15,16,17,18,19,21,22,23,24}
P3 =
P5 =
{2,3,5,6,9,11,14,15,16,19,21,24; 1,4,7,8,10,12,13,17,18,20,22,23,25}
P6 =
{4,7,9,13,15,17,19,20,21,22,24; 1,2,3,5,6,8,10,11,12,14,16,18,23,25}
P10 ={1,2,3,6,7,8,9,11,13,15,19,22,24,25; 4,5,10,12,14,16,17,18,20,21,23}
g = (1,3,4,6, 7,8, 11,12,17, 22, 25 ; 2,5,9,10, 13,14,15,16,18, 19, 20, 21, 23, 24)
ZPT
17
Funkcja H
PU " G < PF
= (1,4;10 ; 2 ;11; 3 ;14,18,21...)
x7 x8 x9 g hWektory (wiersze) tablicy
funkcji h sÄ… wyznaczane
przez bloki PU " G , a wartości
1 0 1 0
0
tej funkcji przez bloki PF
1 0 1 11
0 1 0 1
0
P7 =
{2,5,6,7,8,9,11,12,13,15,16,19,20,22,24; 1,3,4,10,14,17,18,21,23,25}
{1,4,5,8,9,10,12,13,16,17,19,22,25; 2,3,6,7,11,14,15,18,20,21,23,24}
P8 =
{2,8,11,13,16,17,19,23,25; 1,3,4,5,6,7,9,10,12,14,15,18,20,21,22,24}
P9 =
g = (1,3,4, 6, 7,8, 11,12, 17, 22, 25 ; 2,5,9, 10, 13,1 4,15,16, 18, 19, 20, 21, 23, 24)
ZPT
18
Co uzyskaliśmy&
x3 x5 x6 x10
Tylko 2 komórki typowej
G
x7 x8 x9
struktury FPGA
H
f
QUARTUS
23 kom.
Uzyskaliśmy wynik dziesięciokrotnie razy lepszy od
wyniku systemu Quartus amerykańskiej firmy
ZPT
19
Altera
Dekompozycja zespołu funkcji
Twierdzenie w ujęciu rachunku podziałów jest ogólne,
obliczenia są niezależne od liczby wyjść funkcji F.
X X
V
G
U
Dekompozycja
F
H
Y
Y = y1, y2,& , ym
ZPT
20
Przykład dekompozycji zespołu funkcji (SUL Przykład 8.4)
P1 = (1,2,3,4,5,6,7;8,9,10,11,12,13,14,15)
x1 x2 x3 x4 x5 y1 y2 y3
v
1 0 0 0 0 0 0 0 0
20 0 0 1 1 0 1 0 v
P2 = (1,2,3,13,14,15;4,5,6,7,8,9,10,11,12)
30 0 0 1 0 1 0 0
P3 = (1,2,3,7,8,9,13,14,15;4,5,6,10,11,12)
40 1 1 0 0 0 1 1
50 1 1 0 1 0 0 1
v P4 = (1,4,5,7,8,10,13;2,3,6,9,11,12,14,15)
60 1 1 1 00 1 0
70 1 0 0 0 0 0 1
8 1 1 0 0 0 0 0 1
P5 = (1,3,4,6,7,8,9,10,12,15;2,5,11,13,14)
9 1 1 0 1 0 0 0 0 v
PF =
(1,9,14; 2,6,12;3,10,15; 5,7,8,13;4,11)
10 1 1 1 0 0 1 0 0
11 1 1 1 1 1 0 1 1
v
12 1 1 1 1 00 1 0
13 1 0 0 0 1 0 0 1
Niezależnie od liczby
v
14 1 0 0 1 1 0 0 0
funkcji wszystkie
15 1 0 0 1 0 1 0 0
wyjścia opisujemy
jednym! podziałem
ZPT
21
Przykład& wyznaczanie podziałów PU, PV
x3 x4 x1 x2 x5
Szukamy dekompozycji
g
" " "
U={x3,x4} V = {x1,x2,x5}
h
PU =P3" P4
PV=P1" P2" P5
PU = 1,7,8,13; 2,3,9,14,15;4,5,10;6,11,12
PF = 1,9,14; 5,7,8,13;2,6,12;4,11;3,10,15
(1)(7,8,13);
(4)(5)(10); (11)(6,12)
(2)(9,14)(3,15);
PU|PUPF =
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
ZPT
22
Przykład& obliczanie G



Jak wyznaczyć G ???



PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
PU|PF=(1)(7,8,13); (2)(9,14)(3,15); (4)(5)(10); (11)(6,12)
TrochÄ™
(2) (9,14) (3,15)
inny
zapis
1,3
8 ,9 ,10 ,12
2
15
13 ,14
5
4 , 6 ,7
11
G = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
ZPT
23
Przykład& kodowanie G
W przypadku zespołu funkcji liczba bloków podziału G jest większa.
Należy zakodować bloki G Kodowanie jest dowolne
01
1000
G = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
Aktualna teoria nie podaje rozwiÄ…zania
problemu kodowania
Kodowanie jest potrzebne do wyznaczenia tablic prawdy funkcji G i H
ZPT
24
Tablica prawdy G
x1 x2 x5 g1 g2
P1 = (1,2,3,4,5,6,7;8,9,10,11,12,13,14,15)
1,3 0 0 0 0 0
P2 = (1,2,3,13,14,15;4,5,6,7,8,9,10,11,12)
0 1
0 0 1
2
4 , 6 ,7
P5 = (1,3,4,6,7,8,9,10,12,15;2,5,11,13,14)
0 1 0 0 1
5 0 1 1
0 0
011000
. . . . . .
G = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
ZPT
25
Tablica prawdy H
x3 x4 g1 g2 y1 y2 y3
0 0 0
1 0 0 0 0
P3 = (1,2,3,7,8,9,13,14,15;4,5,6,10,11,12)
0 0 1
7
0 0 0 1
P4 = (1,4,5,7,8,10,13;2,3,6,9,11,12,14,15)
0 0 1 0 0 0 1
8 ,13
3 ,15
0 1 0 0 1 0 0
00
0110
. . . . . .
G = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
PU = 1,7,8,13; 2,3,9,14,15;4,5,10;6,11,12
PU " G < PF
&
(
1; 7;
8 ,13 ; 3 ,15 ;
PU " G =
ZPT
26
Co uzyskaliśmy&
Funkcje g i h można obliczyć jawnie& z tablic prawdy
można uzyskać realizacje na bramkach.
x3 x4 x1 x2 x5
Ale dla struktur FPGA
wystarczy schemat
dekompozycji i tablice
g
prawdy.
h
Proces minimalizacji
jest niepotrzebny!!!
ZPT
27
Systematyczny algorytm dekompozycji
Obliczanie podziału G metodą
przenoszenia bloków PV na podstawie
podziału ilorazowego PU%PU" G jest
trudne do zalgorytmizowania.
Szczęśliwie jednak algorytm obliczania
G można sprowadzić do algorytmu
obliczania MKZ.
ZPT
28
Systematyczny algorytm dekompozycji
PV =( B1,& ,Bi,& ,Bj,& ,BN) Å‚ij =( B1,& ,BiBj,& ,BN)
Dwa bloki Bi i Bj podziału PV są zgodne, jeśli podział łij
uzyskany z PV przez sklejenie Bi oraz Bj w jeden blok i
pozostawienie pozostałych bloków bez zmiany
spełnia warunek Twierdzenia o dekompozycji: PU " łij d" PF.
W przeciwnym przypadku Bi oraz Bj sÄ… niezgodne.
ZPT
29
Przykład (ten sam co poprzednio)
U={x3,x4} oraz V = {x1,x2,x5}
PU = 1,7,8,13; 2,3,9,14,15;4,5,10;6,11,12
PF = 1,9,14; 5,7,8,13;2,6,12;4,11;3,10,15
PU|PUPF=(1)(7,8,13); (2)(9,14)(3,15); (4)(5)(10); (11)(6,12)
Numerujemy bloki PV
B1 B2 B3 B4 B5 B6 B7 B8
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
Å‚12 =
1,2,3; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
Å‚57 =
1,3; 2; 4,6,7; 5;
8,9,10,12,13,14; 11; 15
ZPT
30
Przykład &
Można sprawdzić, że
PU " Å‚12 / PF,
<
(B1, B2) jest sprzeczna
PU " Å‚57 d" PF (B5, B7) jest zgodna
Ale do wyznaczenia zgodnych (lub sprzecznych) par (Bi, Bj)
niekoniecznie musimy się posługiwać skomplikowaną
nierównością PU " łij d" PF
Wystarczy w tym celu obliczyć iloczyn zbioru Bi *" Bj
z blokami podziałuPU i sprawdzić, czy każdy  niepusty
iloczyn jest zawarty w jakimÅ› bloku PF
ZPT
31
Przykład &
B1 B2 B3 B4 B5 B6 B7 B8
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
B1 *" B2 =
1,2,3
(B1,B2) jest sprzeczna
<
/
" PU
= (1; 2,3) PF
1,2,3
(B5, B7) jest zgodna
B5 *" B7 =
8,9,10,12,13,14
d" PF
" PU
= 8,13; 9,14;10;12
8,9,10,12,13,14
PU = 1,7,8,13; 2,3,9,14,15;4,5,10;6,11,12
PF = 1,9,14; 5,7,8,13;2,6,12;4,11;3,10,15
ZPT
32
Przykład c.d.
Pary zgodne: (B1,B4), (B1,B6), (B1,B8), (B2,B3), (B2,B4), (B2,B6), (B3,B7),
(B3,B8), (B4,B6), (B4,B7), (B4,B8), (B5,B7), (B6,B7), (B6,B8).
Doskonale wiemy jak obliczać
Klasy maksymalne:
Maksymalne Klasy Zgodne
{B1,B4, B6, B8}
MKZ
{B4, B6, B7}
B1 B2 B3 B4 B5 B6 B7 B8
{B2, B4, B6}
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
{B3, B8}
{B3, B7}
G =
{B2, B3} ; {B5, B7} ;{B1,B4, B6, B8} {B2, B3}
{B5, B7}
ZPT
33
Przykład c.d.
B1 B2 B3 B4 B5 B6 B7 B8
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
G =
{B2, B3} ; {B5, B7} ;
{B1,B4, B6, B8}
 = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
G
Ten sam rezultat co poprzednio
ZPT
34
Komentarz: algorytmy dekompozycji
Dekompozycję funkcjonalną nazywać będziemy szeregową, dla
odróżnienia od równoległej
Szeregowa Równoległa
X
X
A B
G
H
G
H
Yg
Yh
Y
ZPT
35