Redukcja argumentów
x1 x2 x3 x4 x5 x6 x7 f
1 1 0 0 0 1 0 1 0
2 1 0 1 1 1 1 0 0
Przecież są tu tylko 4
3 1 1 0 1 1 1 0 0
argumenty?
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
f = x4x7 + x2x6
I
& czyli ta funkcja nie zależy od: x1,x3,x5
T
P
W
ZPT
1
...ale gdybyYmy wiedzieli o tym wczeYniej •!e
le gdybyYmy wiedzieli o tym wczeYniej •!e
le gdybyYmy wiedzieli o tym wczeYniej, •!e
le gdybyYmy wiedzieli o tym wczeYniej •!e
n j z l l 4 7
n j z l l 4 7
n j z l l 4 7
n j z l l 4 7
x2 x4 x6 x7 f
x1 x2 x3 x4 x5 x6 x7 f
1 0 0 0 1 0
1 1 0 0 0 1 0 1 0
2 0 1 1 0 0
2 1 0 1 1 1 1 0 0
3 1 1 1 0 0
3 1 1 0 1 1 1 0 0
4 1 0 1 1 0
4 1 1 1 0 1 1 1 0
5 1 0 0 1 1
5 0 1 0 0 1 0 1 1
6 0 0 1 0 1
6 1 0 0 0 1 1 0 1
7 0 0 0 0 1
7 1 0 1 0 0 0 0 1
8 0 0 1 0 1
8 1 0 1 0 1 1 0 1
9 1 0 0 1 1
9 1 1 1 0 1 0 1 1
I
T Czy mo n j n Å‚
na przewidzie od n j n Å‚
n j n Å‚Å‚
n j n
P
W
z ini liz n
z ini liz n
z ini liz n
jakich argumentów z ini liz n
ZPT
n li 3n
n li 3n
n li 3n
funkcja istotnie zależy ??? n li 3n
2
Przykład z Synteza układów logicznych str 65
.type fr
.i 10 Funkcja
.o 1
10 argumentów
.p 25
0010111010 0
.i 10
1010010100 0
.o 1
0100011110 0
1011101011 0
.p 6
1100010011 0
----00-1-- 1
0100010110 0
Espresso
1110100110 0
00--0----- 1
0100110000 0
----10-0-0 1
0101000010 0
0111111011 1
---1--0--1 1
0000010100 1
------1-0- 1
1101110011 1
0100100000 1
-----11--1 1
0100011111 1
.e
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
I
f = x5x6x8 + x1x2x5 + x5x6x8x10 + x4x7x10 + x7x9 + x6x7x10
1111100010 1
T
1010111101 1
P
0110000110 1
W
Brak x3 - 9 argumentów
0100111000 1
.e
ZPT
3
Zagadka...
.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
Od ilu argumentów
0100011110 0
zależy ta funkcja
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1 Można wykazać, że funkcja
1101110011 1
ta jest zależna od&
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
& zaledwie 7 argumentów!
1111111111 1
0010000000 1
1101100111 1
0010001111 1
Espresso redukuje składniki iloczynowe
1111100010 1
I
T 1010111101 1
P
0110000110 1
W
0100111000 1
Nie redukuje argumentów!!!
.e
ZPT
4
PROBLEM:
Obliczania minimalnej liczby argumentów
od których funkcja istotnie zależy
...jest bardzo istotny w redukowaniu złożoności
obliczeniowej procedur minimalizacji funkcji
boolowskich, a w konsekwencji może się
przyczynić do uzyskiwania lepszych rezultatów.
I
T
P
W
ZPT
5
Pojęcie zmiennej niezbędnej
Jeżeli wektory Xa oraz Xb: f (Xa) `" f (Xb), różnią się dokładnie
`"
`"
`"
dla jednej zmiennej to zmienną taką nazywamy niezbędną
Funkcja f
x4 x6 zmienne niezbędne
x1 x2 x3 x4 x5 x6 x7 f
x4 x6
1 1 0 0 0 1 0 1 0
2 1 0 1 1 1 1 0 0
różnią
ponieważ wiersze 2 i 8
x4
siÄ™ na pozycji
3 1 1 0 1 1 1 0 0
4 1 1 1 0 1 1 1 0
x6
a wiersze 4 i 9 na pozycji
5 0 1 0 0 1 0 1 1
6 1 0 0 0 1 1 0 1
I
7 1 0 1 0 0 0 0 1
T
P
8 1 0 1 0 1 1 0 1
W
9 1 1 1 0 1 0 1 1
ZPT
6
Wyjaśnienie&
x1 x2 x3 x4 x5 x6 x7 f x1 x2 x3 x5 x6 x7 f
1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0
2 1 0 1 1 1 1 0 0 2 1 0 1 1 1 0 0
3 1 1 0 1 1 1 0 0 3 1 1 0 1 1 0 0
4 1 1 1 0 1 1 1 0 4 1 1 1 1 1 1 0
5 0 1 0 0 1 0 1 1 5 0 1 0 1 0 1 1
6 1 0 0 0 1 1 0 1 6 1 0 0 1 1 0 1
7 1 0 1 0 0 0 0 1 7 1 0 1 0 0 0 1
8 1 0 1 0 1 1 0 1 8 1 0 1 1 1 0 1
9 1 1 1 0 1 0 1 1 9 1 1 1 1 0 1 1
Tablica specyfikacji jest sprzeczna, ponieważ
f(101110) = 0 (wektor 2)
I
T
P f(101110) = 1 (wektor 8)
W
Bez zmiennej niezbędnej funkcji nie można zrealizować!
ZPT
7
Zmienne niezbędne - przykład
Zmienne niezbędne występują w każdym wyrażeniu funkcji!!!
x4 x6
x1 x2 x3 x4 x5 x6 x7 f
1 1 0 0 0 1 0 1 0
f = x4x7 + x2x6
2 1 0 1 1 1 1 0 0
Ale do zmiennych nzb należy dołączyć
3 1 1 0 1 1 1 0 0
jeszcze inne zmienne, aby uzyskany zbiór
4 1 1 1 0 1 1 1 0
był wystarczający do realizacji funkcji.
5 0 1 0 0 1 0 1 1
6 1 0 0 0 1 1 0 1
Oczywiście chcemy, aby był to zbiór o
7 1 0 1 0 0 0 0 1
minimalnej liczności.
8 1 0 1 0 1 1 0 1
9 1 1 1 0 1 0 1 1
I
T
P
W
Jak taki zbiór (zbiory) obliczyć?
ZPT
8
Redukcja argumentów przykład&
Należy obliczyć iloczyn podziałów wyznaczonych
przez zmienne niezbędne (ozn. PN):
P6 =
{1,5,7,9; 2,3,4,6,8}
{1,4,5,6,7,8,9; 2,3}
P4 =
(1,5,7,9 ; 4,6,8 ; 2,3 )
PN = P4" P6 =
{1,2,3,4; 5,6,7,8,9}
Pf =
A następnie należy obliczyć podział ilorazowy:
PN|PN" Pf = ( (1),(5,7,9); (4),(6,8);(2,3))
aby wiedzieć jakie wektory należy rozdzielić,
I
T
1, 5, 7, 9
4, 6, 8
P
W
aby uzyskać zbiór minimalno-argumentowy.
ZPT
9
Rozdzielanie wektorów
Co należy rozumieć przez rozdzielanie wektorów?
Jakie zmienne oddzielajÄ… wektor 1 od wektora 7?
x1 x2 x3 x4 x5 x6 x7 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
x3 x5 x7
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
I
T 8 1 0 1 0 1 1 0 1
P
W
9 1 1 1 0 1 0 1 1
ZPT
10
Redukcja argumentów przykład c.d.
x1 x2 x3 x4 x5 x6 x7 f
1 1 0 0 0 1 0 1 0
2 1 0 1 1 1 1 0 0
1, 5, 7, 9
3 1 1 0 1 1 1 0 0
4 1 1 1 0 1 1 1 0
4, 6, 8 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
x1 x2
1, 5
9 1 1 1 0 1 0 1 1
1, 7
x3 x5 x7
1, 9
x2 x3
x1 x2
Tu obliczamy minimalne
x3 x5 x7 pokrycie kolumnowe
4, 6
x2 x3 x7
x2 x3
I
T 4, 8
x2 x7
x2 x7
P
W
ZPT
...obliczamy systematycznie...
11
Redukcja argumentów przykład c.d.
x1 x2
x3 x5 x7
x2 x3
x2 x7
(x1 + x2) (x3 + x5 + x7) (x2 + x3)
(x2 + x7) =
= (x2 +x1)(x2 + x3)(x2 + x7)(x3 + x5 + x7) =
(x3 + x5 + x7) =
=(x2 +x1x3x7)
Tylko to
było
znalezione
przez
= x2x3 + x2x5 +x2x7 + x1x3x7 + . . .
Espresso
I
*" {x4,x6}
*"
*"
*"
T
P
W
{x2,x3,x4,x6} {x2,x4,x5,x6} {x2,x4,x6,x7}
ZPT
12
...ale gdybyYmy wiedzieli o tym wczeYniej •!e
le gdybyYmy wiedzieli o tym wczeYniej •!e
le gdybyYmy wiedzieli o tym wczeYniej, •!e
le gdybyYmy wiedzieli o tym wczeYniej •!e
n j z l l 4 7
n j z l l 4 7
n j z l l 4 7
n j z l l 4 7
x2 x4 x6 x7 f
x1 x2 x3 x4 x5 x6 x7 f
1 0 0 0 1 0
1 1 0 0 0 1 0 1 0
2 0 1 1 0 0
2 1 0 1 1 1 1 0 0
3 1 1 1 0 0
3 1 1 0 1 1 1 0 0
4 1 0 1 1 0
4 1 1 1 0 1 1 1 0
5 1 0 0 1 1
5 0 1 0 0 1 0 1 1
6 0 0 1 0 1
6 1 0 0 0 1 1 0 1
7 0 0 0 0 1
7 1 0 1 0 0 0 0 1
8 0 0 1 0 1
8 1 0 1 0 1 1 0 1
9 1 0 0 1 1
9 1 1 1 0 1 0 1 1
I
n j n Å‚
n j n Å‚Å‚
n j n Å‚
n j n
T
P
z ini liz n
z ini liz n
z ini liz n
z ini liz n
W
n li 3n
n li 3n
n li 3n
n li 3n
ZPT
13
Znaczenie praktyczne i skuteczność redukcji
argumentów
Program PANDOR (Eksperymenty do W04 i W05)
Ekspansja
Redukcja argumentów
I
T
P
W
ZPT
zpt2.tele.pw.edu.pl Projekty/Oprogramowanie
14
Przykład:
.type fr
.i 10
& z Synteza układów logicznych str 65
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
.i 10
1100010011 0
Funkcja TL27
.o 1
0100010110 0
1110100110 0 10 argumentów
.p 6
0100110000 0
----00-1-- 1
0101000010 0
0111111011 1
00--0----- 1
0000010100 1
Espresso
----10-0-01
1101110011 1
0100100000 1
---1--0--1 1
0100011111 1
------1-0- 1
0010000110 1
1111010001 1
-----11--1 1
1111101001 1
.e
1111111111 1
0010000000 1
1101100111 1
I
0010001111 1
T
9 argumentów
P 1111100010 1
W 6 termów
1010111101 1
0110000110 1
0100111000 1
ZPT
.e
15
Funkcja TL27
Funkcja TL27 przed redukcjÄ…
Funkcja TL27 po redukcji
.type fr
.i 10
Realizacja funkcji
.o 1 f1
Ilość zmiennych = 7
.p 25
Ilość wektorów = 25
0010111010 0
R3 =
1010010100 0 {1,2,4,6,7,9,10}
0100011110 0
0001110 0
1011101011 0
1001000 0
1100010011 0 0101110 0
1010111 0
0100010110 0
1101011 0
1110100110 0
0101010 0
Pandor
0100110000 0 1100010 0
0101000 0
0101000010 0
0110010 0
Jeżeli zredukowaną
0111111011 1
0111111 1
0000010100 1 0001000 1
funkcjÄ™ zminimalizujemy
1111011 1
1101110011 1
0100000 1
0100100000 1
ekspansjÄ…, to&
0101111 1
0000010 1
0100011111 1
1111001 1
0010000110 1
1110101 1
1111010001 1
1111111 1
0000000 1
1111101001 1
1110011 1
1111111111 1
0000111 1
0010000000 1
1110010 1
I
1001101 1
1101100111 1
T
0100010 1
0010001111 1
P 0101100 1
1111100010 1
W
1010111101 1
Jedno z 10 rozwiązań po
0110000110 1
ZPT
0100111000 1
redukcji argumentów
16
.e
Przykład TL27
Wynik Pandora po RedArg i Ekspansji:
f = x1x2x7 + x1x2x4 + x1x10 + x1x4x6 + x7x9
7 argumentów, 5 termów
Wynik Espresso:
f = x5x6x8 + x1x2x5 + x5x6x8x10 + x4x7x10 + x7x9 + x6x7x10
I
T
P
9 argumentów, 6 termów
W
ZPT
17
Funkcja KAZ
Przed redukcjÂ
Przed redukcjÂ
Przed redukcjÂ
Przed redukcjÂ
Po redukcji
Po redukcji
Po redukcji
Po redukcji
.type fr
.i 21
.o 1
.p 31
100110010110011111101 1
01010 1
111011111011110111100 1
10110 1
001010101000111100000 1
00100 1
001001101100110110001 1
Pandor
01001 1
100110010011011001101 1
01000 1
100101100100110110011 1
11010 1
001100100111010011011 1
10011 0
001101100011011011001 1
01110 0
110110010011001001101 1
10100 0
100110110011010010011 1
11000 0
110011011011010001100 1
11011 0
010001010000001100111 0
10000 0
100110101011111110100 0
00010 0
111001111011110011000 0
01111 0
101101011100010111100 0
00011 0
110110000001010100000 0
11111 0
110110110111100010111 0
00000 0
110000100011110010001 0
Ile jest takich
01101 0
001001000101111101101 0
00110 0
100100011111100110110 0
rozwiązań
100011000110011011110 0
110101000110101100001 0
110110001101101100111 0
010000111001000000001 0
001001100101111110000 0
I
100100111111001110010 0
000010001110001101101 0
T
Jedno z wielu rozwiÂzaÄ…
Jedno z wielu rozwiÂzaÄ…
Jedno z wielu rozwiÂzaÄ…
Jedno z wielu rozwiÂzaÄ…
101000010100001110000 0
P
101000110101010011111 0
o redukcji
W po redukcji argumentów
o redukcji
o redukcji
101010000001100011001 0
011100111110111101111 0
.end
ZPT
18
Przykład KAZ
Silnie nieokreślona funkcja 21 argumentów,
31 wektorów w TP
Wynik Pandora 5 argumentów, 3 termy
f = x2x4x9x19 + x2x4x9 + x2x19x20
Wynik Espresso 9 argumentów, 3 termy
f = x2x14x19x21 + x7x8x12 + x5x8x20
I
T
P
W
ZPT
19
Zadanie nieco trudniejsze&
X1 X2 X3 X4 X5 X6 X7 X8 X9 y1 y2
1 0 0 0 1 0 0 1 1 0 0 1
2 0 1 1 0 0 0 0 1 0 0 1
3 1 1 1 0 1 1 0 0 0 1 0
4 0 1 0 0 0 1 1 0 1 0 0
5 0 0 1 0 1 1 1 0 0 0 1
6 0 1 1 0 0 0 1 1 0 0 0
7 0 1 1 0 1 1 0 1 1 1 1
8 0 0 0 1 0 0 1 0 1 1 1
9 1 1 1 0 0 0 1 1 0 1 0
10 0 0 1 1 0 0 1 0 1 1 0
P =1,2,5; 3,9,10; 4,6; 7,8
F
Jeżeli wektory Xa oraz Xb: f (Xa) `" f (Xb), różnią się dokładnie
`"
`"
`"
I
T
P dla jednej zmiennej to zmienną taką nazywamy niezbędną
W
ZPT
20
Zadanie&
Zmienne niezbędne N = {x1,x3,x7}
Na kolosach i egzaminach
PN=P1" P3" P7
sÄ… zawsze podawane
PN
= (1,4,8 ; 2,7 ; 3; 5, 6, 10; 9)
P =1,2,5; 3,9,10; 4,6; 7,8
F
Podział ilorazowy:
PN|PN" PF
I
T
P
W
(3); (5)(6)(10); (9)
(1)(4)(8); (2)(7);
PN|PN" PF=
ZPT
21
Zadanie&
(3); (5)(6)(10); (9)
(1)(4)(8); (2)(7);
PN|PF =
X1 X2 X3 X4 X5 X6 X7 X8 X9 y1 y2
1 0 0 0 1 0 0 1 1 0 0 1
2 0 1 1 0 0 0 0 1 0 0 1
3 1 1 1 0 1 1 0 0 0 1 0
2,4,6,8,9 v
1,4
4 0 1 0 0 0 1 1 0 1 0 0
1,8
8,9 5 0 0 1 0 1 1 1 0 0 0 1
6 0 1 1 0 0 0 1 1 0 0 0
4,8
2,4,6
7 0 1 1 0 1 1 0 1 1 1 1
2,7
8 0 0 0 1 0 0 1 0 1 1 1
5,6,9
9 1 1 1 0 0 0 1 1 0 1 0
5,6
2,5,6,8
10 0 0 1 1 0 0 1 0 1 1 0
I
5,10
T
4,5,6,9
P
W
6,10 v
2,4,8,9
ZPT
22
Zadanie&
Wyrażenie boolowskie według indeksów zmiennych X :
i
(8+9)(2+ 4+6)(5+6+9)(2+5+6+8)=
= (9 + 8)(9 + 5 + 6)(2 + 6 + 4)(2 + 6 + 5 + 8)=
îÅ‚
= 9+8(5+6)Å‚Å‚îÅ‚2+6+4(5+8)Å‚Å‚ =
ïÅ‚ śłïÅ‚ śł
ðÅ‚ ûÅ‚ðÅ‚ ûÅ‚
= (9 + 5Å"8 + 6Å"8)(2 + 6 + 4Å"5 + 4Å"8)=
I
T
P
W
ZPT
23
Zadanie&
Wyrażenie boolowskie według indeksów zmiennych X :
i
(8+9)(2+ 4+6)(5+6+9)(2+5+6+8)=
= (9 + 8)(9 + 5 + 6)(2 + 6 + 4)(2 + 6 + 5 + 8)=
îÅ‚
= 9+8(5+6)Å‚Å‚îÅ‚2+6+4(5+8)Å‚Å‚ =
ïÅ‚ śłïÅ‚ śł
ðÅ‚ ûÅ‚ðÅ‚ ûÅ‚
= (9 + 5Å"8 + 6Å"8)(2 + 6 + 4Å"5 + 4Å"8)=
=2Å"9+6Å"9+4Å"5Å"9+4Å"8Å"9+2Å"5Å"8+
I
+5Å"6Å"8+4Å"5Å"8+4Å"5Å"8+2Å"6Å"8+6Å"8+
T
P
W
+4Å"5Å"6Å"8+4Å"6Å"8
ZPT
24
Zadanie&
Ostatecznie:
=2Å"9+6Å"9+4Å"5Å"9+4Å"8Å"9+2Å"5Å"8+4Å"5Å"8+6Å"8
= 2Å"9+6Å"9+6Å"8+4Å"5Å"9+4Å"8Å"9+2Å"5Å"8+4Å"5Å"8
Pami c, dne były:
taj e zmienne niezb
I
T
P
W
{x1,x3,x7}
ZPT
25
Zadanie. . .
{x1,x3,x7}
= 2Å"9+ 6Å"9+6Å"8+ 4Å"5Å"9+ 4Å"8Å"9+ 2Å"5Å"8+ 4Å"5Å"8
Aatwo wypisać wszystkie
minimalne rozwiÄ…zania:
x1, x2, x3, x7, x9
x1, x3, x6, x7, x9
x1, x3, x6, x7, x8
x1, x3, x4, x5, x7, x9
x1, x3, x4, x7, x8, x9
I x1, x2, x3, x5, x7, x8
T
P
x1, x3, x4, x5, x7, x8
W
ZPT
26
Inne zastosowania redukcji argumentów
Dekompozycja równoległa&
X Xh Ä…" X
X Ä…" X
g
X
Xg
Xh
F
G
H
Y
Yg Yh
Y = Yg *" Yh
I
T
P
W Taki sposób syntezy jest istotny dla
nowoczesnych struktur FPGA!
ZPT
27
Dekompozycja równoległa - przykład
y1: {x1, x2, x6}
x1 x2 x3 x4 x5 x6 x7 x8 y1 y2 y3 y4 y5 y6
y2: {x3, x4}
1 0 0 0 1 1 1 0 0 0 0 0 0 0
2 1 0 1 0 0 0 0 0 0 0 1 0 1
y3: {x1, x2, x4, x5, x8}
3 1 0 1 1 1 0 0 0 0 1 1 0 1 1
4 1 1 1 1 0 1 0 0 0 1 1 1 1 0
{x1, x2, x4, x6, x8}
5 1 0 1 0 1 0 0 0 0 0 0 0 1
6 0 0 1 1 1 0 0 0 1 1 0 1 0 0
y4: {x1, x2, x3, x4, x7}
7 1 1 1 0 0 0 0 0 1 0 0 1 0
8 1 0 1 1 0 1 0 0 1 1 0 0 1
9 1 0 1 1 0 1 1 0 1 0 1 1
y5: {x1, x2, x4}
10 0 0 0 1 1 1 0 1 0 0 1 0 1
11 0 0 0 1 1 0 0 1 1 0 0 0
y6: {x1, x2, x6, x8}
I
T
P
W
ZPT
28
Dekompozycja równoległa - przykład
y1: {x1, x2, x6}
y2: {x3, x4}
y3: {x1, x2, x4, x5, x8}
{x1, x2, x4, x6, x8}
y4: {x1, x2, x3, x4, x7}
y5: {x1, x2, x4}
y6: {x1, x2, x6, x8}
I
G= {y1, y3, y6 } H= {y2, y4,y5}
T
P
W
Xg = {x1, x2, x4, x6, x8}Xh = {x1, x2, x3, x4, x7}
ZPT
29
Dekompozycja równoległa - przykład
x1 x2 x4 x6 x9 y1 y3 y6
x1 x2 x3 x4 x7 y2 y4 y5
1 0 0 1 1 0 0 0 0
1 0 0 0 1 0 0 0 0
2 1 0 0 0 0 0 0 1
2 1 0 1 0 0 0 1 0
3 1 0 1 0 0 0 1 1
3 1 0 1 1 0 1 0 1
4 1 1 1 1 0 0 1 0
4 1 1 1 1 0 1 1 1
5 0 0 1 0 0 1 0 0
5 0 0 1 1 0 1 1 0
6 1 1 0 0 0 1 1 0
x1 x2 x3 x4 x5 x6 x7 x8 6 1 1 1 0 0 0 0 1
7 1 0 1 1 0 1 0 1
7 1 0 1 1 1 1 1
8 0 0 1 1 1 0 1 1
9 0 0 1 0 1 1 0
G H
I
T
P
W
y1 y3 y6
y2 y4 y5
ZPT
30
Wyszukiwarka
Podobne podstrony:
Wielka czerwona jedynka (The Big Red One) cz 2Pure RedCin Acr CNC TC [12] L273 85 1IPV6 TC04 red shoehart zhecmcpzzksiwibpsqyd5z6eplngcp34sgeypriREDUL&TC 202 Red ShoehartCoC The Horror at Red HookMartial arts NINJA Red BookTrzy Królestwa Red Cliff [2008] CD2więcej podobnych podstron