(zwana również dekompozycją funkcjonalną)
Rewelacyjna i rewolucyjna metoda syntezy
logicznej
Przegapiona przez twórców oprogramowania
komercyjnego
Dostępna wyłącznie w oprogramowaniu
uniwersyteckim
1
Dekompozycja funkcjonalna
TablicÄ… dekompozycji funkcji f nazywamy macierz
dwuwymiarową o kolumnach etykietowanych wartościami
zmiennych funkcji f ze zbioru B oraz o wierszach etykietowanych
wartościami zmiennych funkcji f ze zbioru A. Liczbę istotnie
różnych kolumn tej macierzy ze względu na ich zawartość
nazywamy ich krotnoÅ›ciÄ… i oznaczamy symbolem ½(A|B).
B
x1x2x3
" " "
" " "
" " "
" " "
x4x5 000 001
Elementami macierzy
0 1
00
M są wartości jakie
1 0 przyjmuje funkcja f na
01
wektorach złożonych z
A
I
odpowiednich etykiet
"
"
"
"
T
"
"
"
"
P
i-tego wiersza i j-tej
"
W "
"
"
kolumny.
ZPT
2
Klasyczne twierdzenie o dekompozycji
Niech będzie dana funkcja boolowska f oraz podział
zbioru zmiennych wejściowych funkcji f na dwa
rozłączne zbiory A i B, to wówczas:
f(A,B) = h(g1(B),.., gj(B),A) Ô! ½(A|B) d" 2j.
A
f
h
g
B
I
T
P
W
B (bound set), A (free set)
ZPT
3
Przykład
B
x1x2x3
000 001 010 100 110 101 011 111
x4x5
00 1 1 1 1 0 0 0 0
01 0 1 1 1 0 0 0 0
10 0 0 0 0 0 0 0 0
A
11 0 0 0 0 1 1 1 0
g1g2 00 01 10 11
x1 x2 x3 g1 g2
x4x5
0 0 0 0 0
0 0 1 1 0 0
0 0 1 0 1
0 1 0 1 0 0
0 1 0 0 1
1 0 0 0 0 0
1 0 0 0 1
1 1 0 0 1 0
1 1 0 1 0
I
1 0 1 1 0
T
Istnieje dekompozycja !
P
0 1 1 1 0
W
1 1 1 1 1
f = h(x4, x5, g1(x1, x2, x3), g2(x1, x2, x3))
ZPT
4
Praktyczne znaczenie dekompozycji
x4 x5 x1 x2 x3
x1 x2 x3 x4 x5
g
f
h
FPGA
I
T
P
W
ZPT
5
Przykład trochę trudniejszy
cde
000 001 010 011 100 101 110 111
a b
00 1  0 1  0 1 0
01     1 1  
10  0 1 0 0  0 1
11 0 1      
K0 K1 K2 K3 K4 K5 K6 K7
a b c d e
Istnieje dekompozycja !
g
I
f = h(a,b,g1(c,d,e), g2(c,d,e))
T
h
P
W
ZPT
6
Przykład trochę trudniejszy
B
cde
000 001 010 011 100 101 110 111
a b
00 1  0 1  0 1 0
01     1 1  
10  0 1 0 0  0 1
A
11 0 1      
K0 K1 K2 K3 K4 K5 K6 K7
c d e g1 g2
0 0 0 0 0
g1g2
00 01 11 10
a b
0 1 1 0 0
0 0 1 0 0 
1 0 0 0 0
0 1 1 1  
1 1 0 0 0
I
0 0 1 0 1
1 0 0 0 1 
T
1 0 1 0 1
P
1 1 0 1  
W
0 1 0 1 1
1 1 1 1 1
ZPT
7
Relacja zgodnoÅ›
ści kolumn
Å›
Å›
Jak obliczać dekompozycję
I
T
P
W
ZPT
8
Relacja zgodności kolumn
Kolumny {kr, ks} są zgodne, jeśli nie istnieje wiersz i,
dla którego elementy Kir, Kis są określone i różne,
tzn. odpowiednio: 0, 1 albo 1, 0.
K1 K2 K3 K4 K5 K6 K7
1 - 0 1 - 0 1
- - - - 1 1 -
- 0 1 0 0 - 0
I
T
0 1 - - - - 0
P
W
ZPT
9
Relacja zgodności kolumn
K1 K2 K3 K4 K5 K6 K7
1 - 0 1 - 0 1
- - - - 1 1 -
- 0 1 0 0 - 0
0 1 - - - - 0
Kolumny zgodne można  sklejać
{K1,K4,K7}
1 0
{K5,K6}
- 1
I
T
0 0
P
W
0 -
ZPT
10
Relacja zgodności
Relacja zgodności jest zwrotna, symetryczna,
ale nie jest przechodnia.
Pary zgodne umożliwiają wyznaczenie maksymalnych
zbiorów kolumn zgodnych.
Zbiór K = {k1,...,kp} nazywamy maksymalnym zbiorem
kolumn zgodnych (maksymalną klasą zgodności),
jeżeli każda para ki, kj wzięta z tego zbioru jest zgodna
oraz nie istnieje żaden inny zbiór kolumn zgodnych K2 ,
zawierajÄ…cy K.
I
T
P
W
ZPT
11
Obliczanie MKZ-ów
Problem obliczania maksymalnych klas zgodnych można
sprowadzić do znanego problemu obliczania maksymalnych
klik w grafie lub do problemu kolorowania grafu.
Najprostsza metoda polega na Å‚Ä…czeniu par kolumn
zgodnych w trójki, trójek w czwórki itd.
Redukując zbiory mniejsze zawarte w większych oblicza
Maksymalne Klasy Zgodności
I
T
P
W
ZPT
12
Metoda  na chłopski rozum
Pary zgodne
a, b
b, c
{a, b, c}
a, c
a, b, c
a, b, d
{a, b, c, d}
b, c, d
a, c, d
i.t.d.
I
T
P
W
ZPT
13
Przykład - obliczanie klas zgodności
0,3
Pary zgodne:
0,4
0,6
cde
000 001 010 011 100 101 110 111
a b
1,3
00 1  0 1  0 1 0
1,4
01     1 1  
1,5
10  0 1 0 0  0 1
1,6
11 0 1      
K0 K1 K2 K3 K4 K5 K6 K7
2,5
2,7
3,4
K0, K1 sprzeczna
3,6
K0, K2 sprzeczna
4,5
I
T
K0, K3 zgodna
4,6
P
W
K0, K4 zgodna
5,7
ZPT
14
Przykład  obliczanie klas zgodności
0,3
0,4
Maksymalne klasy
0,6
0,3,4
zgodności:
0,3,6
1,3
0,4,6
1,4
1,5
0,3,4,6
1,3,4
1,6
1,3,6
1,3,4,6
2,5
1,4,5
2,7
1,4,5
1,4,6
3,4
2,5,7
3,6
2,5,7
4,5
3,4,6
4,6
I
T
P
W
5,7
ZPT
15
Przykład  obliczanie klas zgodności
Z rodziny MKZ wybieramy minimalnÄ… liczbÄ™ klas (lub
podklas) pokrywającą zbiór wszystkich kolumn.
0,3,4,6
Wybieramy: Ostatecznie:
1,3,4,6
0,3,4,6 0,3,4,6
1,4,5
1,5
1,4,5
2,5,7
2,7
2,5,7
I
T
P
W
ZPT
16
Sklejanie kolumn  funkcja h
cde
000 001 010 011 100 101 110 111
ab
00 1 - 0 1 - 0 1 0
01 - - - - 1 1 - -
10 - 0 1 0 0 - 0 1
11 0 1 - - - - - -
K0 K1 K2 K3 K4 K5 K6 K7
{K0,K3,K4,K6} {K1,K5} {K2,K7}
g1g2 00 01 11 10
ab
00 1 0 0 -
I
01 1 1 - -
T
P
10 0 0 1 -
W
11 0 1 - -
ZPT
17
Nowe kodowanie kolumn  funkcja g
cde
000 001 010 011 100 101 110 111
ab
00 1 - 0 1 - 0 1 0
01 - - - - 1 1 - -
11 - 0 1 0 0 - 0 1
10 0 1 - - - - - -
K0 K1 K2 K3 K4 K5 K6 K7
c d e g1 g2
g1g2 00 01 11 10
0 0 0 0 0
ab
0 1 1 0 0
00 1 0 0 -
1 0 0 0 0
1 1 0 0 0
01 1 1 - -
0 0 1 0 1
I
T
11 0 0 1 -
1 0 1 0 1
P
W
0 1 0 1 1
10 0 1 - -
1 1 1 1 1
ZPT
18
Co uzyskaliśmy
a b c d e
g
Wystarczy dla realizacji w
h
strukturach FPGA
Ale funkcje g i h można obliczyć jawnie&
I
T
P
W
ZPT
19
Przykład  funkcje g1 i g2
c d e g1 g2
e e
0 1 0 1
0 0 0 0 0
cd cd
0 1 1 0 0
00 0 0 00 0 1
1 0 0 0 0
1 1 0 0 0
01 1 0 01 1 0
0 0 1 0 1
11 0 1 11 0 1
1 0 1 0 1
10 0 0 10 0 1
0 1 0 1 1
1 1 1 1 1
+cde +ce
+ de
g =cde g =cde
1 2
I
T
P
W
ZPT
20
Przykład  funkcja h
g1g2 00 01 11 10
ab
00 1 0 0 -
01 1 1 - -
11 0 1 - -
10 0 0 1 -
h = ag2 + bg2 + ag1
I
T
P
W
ZPT
21
Jak usprawnić obliczanie MKZ?
W metodzie dekompozycji jednym z
najważniejszych algorytmów jest
algorytm obliczania maksymalnych
klas zgodności
Czy nie można stosowanej do tej
pory  metody na chłopski rozum
zastąpić czymś skuteczniejszym?
I
T
P
W
ZPT
22
Jak usprawnić obliczanie MKZ?
W celu sprawniejszego obliczania MKZ
wprowadzimy dwie nowe metody:
a) metodÄ™ wg par zgodnych
b) metodÄ™ wg par sprzecznych
I
T
P
W
ZPT
23
Algorytm MKZ wg par zgodnych
E  relacja zgodności (ei,ej) " E
Rj = { ei | i < j oraz (ei,ej) " E}
RKZk RKZk+1 KZ " RKZk
a) Rk+1 = Ć, RKZk+1 jest powiększana o klasę KZ = {k+1}
b) KZ )" Rk+1 = Ć, KZ bez zmian
c) KZ )" Rk+1 `"Ć, KZ = KZ )" Rk+1*" {k+1}
I
T
P
W
ZPT
24
Przykład
Rj = { ei | i < j oraz (ei,ej) " E}
E:
1,2
Ć
R1 =
1,3
R2 = 1
1,5
1,2
R3 =
2,3
2,4
R4 = 2
2,5
3,5
R5 = 1,2,3
3,6
R6 = 3,4
4,6
I
T
P
W
ZPT
25
Przykład c.d.
a) Rk+1 = Ć, RKZk+1 jest powiększana o klasę KZ = {k+1}
b) KZ )" Rk+1 = Ć, KZ bez zmian
c) KZ )" Rk+1 `" Ć, KZ = KZ )" Rk+1*" {k+1}
R1 = Ć
{1}
R2 = 1
{1,2}
R3 = 1,2
{1,2,3}
R4 = 2
{2,4}, {1,2,3}
R5 = 1,2,3
{2,5}, {1,2,3,5}, {2,4}
Rodzina MKZ
I
T
P
{3,6},
R6 =3,4
W {4,6}, {1,2,3,5}, {2,4}
ZPT
26
Algorytm MKZ wg par sprzecznych
Zapisać pary sprzeczne w postaci koniunkcji dwuskładnikowych sum
Koniunkcję dwuskładnikowych sum przekształcić do minimalnego
wyrażenia boolowskiego typu suma iloczynów
Wtedy MKZ są uzupełnieniami zbiorów reprezentowanych przez
składniki iloczynowe tego wyrażenia
I
T
P
W
ZPT
27
Ten sam przykład
Pary zgodne
Pary sprzeczne
E:
1,2 1,4
1,3 1,6
1,5 2,6
2,3 3,4
2,4 4,5
2,5 5,6
3,5
3,6
4,6
I
T
P
W
ZPT
28
Przykład...
Pary sprzeczne:
(k1, k4), (k1, k6), (k2, k6), (k3, k4), (k4, k5), (k5, k6)
Obliczamy wyrażenie boolowskie typu  koniunkcja sum :
(k1 + k4) (k1 + k6 ) (k2 + k6) (k3 + k4) (k4 + k5) (k5+ k6) =
PorzÄ…dkujemy:
(k4 + k1) (k4 + k3 ) (k4 + k5) (k6 + k1) (k6 + k2) (k6 + k5) =
Przekształcamy
wyrażenie do postaci
 suma iloczynów :
k1k3k5)
= (k4 + (k6 + k1k2k5) =
I
T
k4k6 + k1k2k4k5 + k1k3k5k6 + k1k2k3k5
P
W
ZPT
29
Przykład...
Klasy zgodne uzyskamy odejmujÄ…c od zbioru {k1,...,k6}, zbiory tych ki,
które występują w jednym składniku wyrażenia typu  suma
iloczynów
{k1,..., k6} - {k4, k6} = {k1, k2, k3, k5 }
{k1,...,k6} - {k1, k2 , k4 , k5 } = {k3, k6}
{k1,...,k6} - {k1, k3, k5 , k6} = {k2 , k4}
{k1,...,k6} - {k1, k2, k3, k5 } = {k4, k6}
I
T
P
W
ZPT
30
Warto umiejÄ™ Ä™...
ętnie dobierać metodę
Ä™ Ä™
Ä™ Ä™
Pary zgodne:
(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,3), (2,5), (2,6), (2,7),
(3,4), (3,5), (3,6), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8),
(6,7), (6,8), (7,8),
Pary sprzeczne:
(1,8) (2,4) (2,8) (3,7) (4,5)
Wybór metody jest oczywisty!
I
T
P
W
ZPT
31
Klasy zgodności - przykład
S1
MKZ1 = {S1, S2, S5, S6, S7}
MKZ2 = {S1, S4, S6, S7}
S2
S8
MKZ3 = {S5, S6, S7 ,S8}
MKZ4 = {S4, S6, S7 ,S8}
MKZ5 = {S3, S5, S6, S8}
S7 S3
MKZ6 = {S3, S4, S6, S8}
MKZ7 = {S1, S2, S3, S5, S6}
MKZ8 = {S1, S3, S4, S6}
S4
I
S6
T
P
W
S5
ZPT
32
W poszukiwaniu innych metod&
Pary zgodne: Pary sprzeczne:
0,3 0,1
0,4 0,2
0,6 0,5
1,3 0,7
1,4 1,2
1,5 1,7
1,6 2,3
2,5 2,4
2,7 2,6
3,4 3,5
3,6 3,7
I
4,5 4,7
T
P
4,6 5,6
W
5,7 6,7
ZPT
33
Graf niezgodnoÅ›
ści
Å›
Å›
(0,1), (0,2), (0,5), (0,7), (1,2), (1,7), (2,3),
(2,4), (2,6), (3,5), (3,7), (4,7), (5,6), (6,7)
0
7 1
i jego kolorowanie
6 2
I
T
3
5
P
W
4
ZPT
34