Espresso
(1984)
Synteza
wielopoziomowa
Minimalizacja
Dekompozycja
symboliczna
funkcjonalna
(1990)
(1995)
I
T
P
W
ZPT
1
R
oz
w
ó
j
t
e
c
h
n
o
l
o
g
ii
Dekompozycja funkcjonalna
Niestety metoda dekompozycji polegajÄ…ca na
zastosowaniu twierdzenia Curtisa jest
absolutnie nieprzydatna w automatycznych
obliczeniach komputerowych
Znacznie skuteczniejsza jest metoda dekompozycji, w której
obliczenia sÄ… wykonywane przy pomocy tzw. rachunku
podziałów
I
T
P
W
ZPT
2
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
I
Y
T
P
W
ZPT
3
Twierdzenie o dekompozycji
& w ujęciu rachunku podziałów
U
U, V są rozłącznymi podzbiorami X
G
oraz W ‚" U
‚"
‚"
‚"
G
H
PF
Funkcję F: Bn {0,1}m można zrealizować w strukturze:
F = H(U,G(V,W))
wtedy i tylko wtedy, gdy istnieje podział G e" PV*"W taki, że:
I
PU · G d" PF
T
P
W
ZPT
4
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.
Dla S = {1,2,3,4,5,6}, P = {{1,2}, {3,5}, {4,6} } jest podziałem na S.
P =
(1,2; 3,5;4,6)
I
Iloczyn podziałów oraz relacja d".
T
P
W
ZPT
5
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.
Iloczynem podziałów Pa " Pb nazywamy największy (względem
relacji d") podział, który jest nie większy od Pa oraz Pb.
Pa = Pb = !. =
(1,2,4;3,5,6) (1,4; 2,6;3,5) (1,2; 4;6;3,5)
Pc d" Pa Tak
<
Pc / Pb NIE!
I
T
Pa " Pb =
(1,4; 2;6;3,5)
P
W
ZPT
6
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
Pa|Pb =(1)(6,7) ; (3)(2,8) ; (4,5)
I
T
P
W
ZPT
7
Przykład
.type fr
.i 10
.o 1
Synteza układów logicznych str. 65
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
Można wykazać, że funkcja ta
1110100110 0
0100110000 0 jest zależna od
0101000010 0
0111111011 1
0000010100 1
1101110011 1
7 argumentów!
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
X = {x3, x5, x6, x7, x8, x9, x10}
1111111111 1
0010000000 1
1101100111 1
I
0010001111 1
T
1111100010 1
P
1010111101 1
W
0110000110 1
0100111000 1
ZPT
.e
8
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}
{,4,5,8,9,10,12,13,16,17,19,22,25; 2,3,6,7,11,14,15,18,20,21,23,24}
1
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 =
{,2,3,6,7,8,9,11,13,15,19,22,24,25; 4,5,10,12,14,16,17,18,20,21,23}
1
P10 =
I
T
P
W
Pf = {,2,...,9;
1
10,...,25}
ZPT
9
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
Ile wyjść z bloku G???
H
I
T
P
W
ZPT f
10
Obliczenie podziałów PU, PV
Nie ma sprawy:
PU=P7" P8" P9
To 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=
I
T
P
W
ZPT
11
Jak wyznaczyć G
Podział ilorazowy:
Pu|PF
I
Względem poprzedniej definicji: Pu|Pu " PF
T
P
W
ZPT
12
Podział ilorazowy
(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}
; (5,9)(12,22)
; (3)(14,18,21)
((1,4)(10) ; (2)(11)
Pu|PF =
(6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23))
I
T
P
W
ZPT
13
Jak wyznaczyć G ???



Przypomnijmy twierdzenie o dekompozycji:
F = H(U,G(V)) wtedy i tylko wtedy, gdy istnieje podział G e" PV
 e"
 e"
 e"
taki, że:
PU · G d" PF
 d"
 d"
 d"
Podział G tworzymy z bloków
PV zgodnie z podziałem ilorazowym
Pu|PF
Po prostu sklejamy bloki PV
I
T
P
W
ZPT
14
Obliczenie G
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
I
T
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)
P
W
ZPT
15
Jak było &
x3 x5 x6 x10
x3 x5 x6 x10
G
x7 x8 x9
G
x7 x8 x9
Ile wyjść z bloku G???
H
H
f
f
Teraz wiemy, skoro G jest dwublokowy
I
T
P
W
ZPT
16
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
I
T
P
W
ZPT
17
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
1 1 1 0
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}
I
T
1
P10 ={,2,3,6,7,8,9,11,13,15,19,22,24,25; 4,5,10,12,14,16,17,18,20,21,23}
P
W
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
18
Funkcja H
PU " G < PF
= (1,4;10 ; 2 ;11; 3 ;14,18,21...)
x7 x8 x9 g h
1 0 1 0
0
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}
{,4,5,8,9,10,12,13,16,17,19,22,25; 2,3,6,7,11,14,15,18,20,21,23,24}
1
P8 =
I
T
{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 =
P
W
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
19
Praktyczny wynik dekompozycji funkcji z
przykładu
.type fr
.i 10
.o 1
.p 25
x3 x5 x6 x10
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
G
1110100110 0
x7 x8 x9
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
H
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
Tylko 2 komórki
f
1101100111 1
0010001111 1
1111100010 1
1010111101 1
I 0110000110 1
0100111000 1
T
.e
P
W
ZPT
20
Zagadka
Na ilu komórkach zrealizuje tę funkcję
amerykański system QUARTUS?
25 kom. (FLEX)
QUARTUS
lub 27 kom. (Stratix)!!!
I
T
P
W
ZPT
21
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
F
H
Y
Y = {y1, y2,& , ym}
I
T
P
W
ZPT
22
Przykład dekompozycji zespołu funkcji (SUL Tabl. 8.3)
P1 = (1,2,3,4,5,6,7;8,9,10,11,12,13,14,15)
x1 x2 x3 x4 x5 y1 y2 y3
1 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 1 0
P2 = (1,2,3,13,14,15;4,5,6,7,8,9,10,11,12)
3 0 0 0 1 0 1 0 0
4 0 1 1 0 0 0 1 1 P3 = (1,2,3,7,8,9,13,14,15;4,5,6,10,11,12)
5 0 1 1 0 1 0 0 1
P4 = (1,4,5,7,8,10,13;2,3,6,9,11,12,14,15)
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
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
10 1 1 1 0 0 1 0 0
11 1 1 1 1 1 0 1 1
PF = (1,9,14;5,7,8,13;2,6,12;4,11;3,10,15 )
12 1 1 1 1 0 0 1 0
13 1 0 0 0 1 0 0 1
I
14 1 0 0 1 1 0 0 0
T
P
15 1 0 0 1 0 1 0 0
W
ZPT
23
Przykład&
x3 x4 x1 x2 x5
Szukamy dekompozycji
g
" " "
U={x3,x4} V = {x1,x2,x5}
h
PU =P3" P4
PV=P1" P2" P5
PU|PF
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|PF =
I
T
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
P
W
ZPT
24
Przykład c.d.
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)
(2) (9,14) (3,15)
1,3
8 , 9 ,10 ,12
2
15
13 ,14
5
4 , 6 , 7
I
T
P
11
W
ZPT G = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
25
Przykład c.d.
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
PU = 1,7,8,13; 2,3,9,14,15;4,5,10;6,11,12
I
T
PU " G < PF
P
W
ZPT
26
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
I
T
P
W
ZPT
27
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
&
(
I
1; 7;
8 ,13 ; 3 ,15 ;
PU " G =
T
P
W
ZPT
28
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
I
T
jest niepotrzebny!!!
P
W
ZPT
29
Obliczanie podziału G metodą
przenoszenia bloków PV na podstawie
podziału ilorazowego PU% G jest
trudne do zalgorytmizowania.
Szczęśliwie jednak algorytm obliczania
G można sprowadzić do algorytmu
obliczania MKZ.
I
T
P
W
ZPT
30
Systematyczny algorytm dekompozycji
G e"PV :PU " G d"PF
Sklejanie bloków z PV. Tak wielu jak to tylko możliwe.
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 spełnia warunek Twierdzenia,
tzn., jeśli PU " łij d" PF.
W przeciwnym przypadku Bi oraz Bj sÄ… niezgodne.
Podzbiór ´ bloków podziaÅ‚u wejÅ›ciowego PV nazywamy zgodnÄ… klasÄ…
bloków jeÅ›li bloki w ´ sÄ… parami zgodne.
Zgodna klasa bloków jest nazywana maksymalną, jeśli nie jest
zawarta w żadnej innej klasie zgodnej.
I
T
P
W
ZPT
31
Przykład (ten sam co poprzednio)
x1x2x3x4x5 y1y2y3
U={x3,x4} oraz V = {x1,x2,x5}.
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
PF = 1,9,14; 5,7,8,13;2,6,12;4,11;3,10,15
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
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
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
I
T
P
W
ZPT
32
Przykład &
U={x3,x4} oraz V = {x1,x2,x5}.
PF = 1,9,14; 5,7,8,13;2,6,12;4,11;3,10,15
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
I wyznaczamy wszystkie pary zgodne (Bi, Bj)
I
T
P
W
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
PU|PF=(1)(7,8,13); (2)(9,14)(3,15); (4)(5)(10); (11)(6,12)
Niezgodna!
B1, B2
PU " (1,2,3; 4,6,7; 5;...)d"PF
/
Zgodna!
B1, B4
PU " (1,3,5; 2; 4,6,7; ...)d"PF
I
T
P
W
ZPT
34
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}
I
T
P
{B5, B7}
W
ZPT
35
Przykład c.d.
B1 B2 B3 B4 B5 B6 B7 B8
Klasy maksymalne:
PV = 1,3; 2; 4,6,7; 5; 8,9,10,12; 11; 13,14; 15
{B1,B4, B6, B8}
{B4, B6, B7}
{B2, B3} {B5, B7} {B1,B4, B6, B8}
{B2, B4, B6}
G = 2,4,6,7; 8,9,10,12, 13,14; 1,3,5,11,15
{B3, B8}
{B3, B7}
{B2, B3}
I
T
Ten sam rezultat co poprzednio
P
{B5, B7}
W
ZPT
36