Espresso
I
T
. . . mankamenty
P
W
ZPT
1
Funkcja 7 argumentów
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
f = x4 x7 + x2x6
Pamiętamy . . . z ekspansji
I
T
P Czy mo ć
na przewidzieć od jakich argumentów
ć
ć
W
funkcja istotnie zależy ???
ZPT
2
Przykład z Synteza układów cyfrowych str 32
.type fr
Funkcja
.i 10
.o 1
10 argumentów
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
.i 10
1100010011 0
0100010110 0 .o 1
1110100110 0
.p 6
0100110000 0
0101000010 0 Espresso
----00-1-- 1
0111111011 1
00--0----- 1
0000010100 1
1101110011 1 ----10-0-01
0100100000 1
---1--0--1 1
0100011111 1
0010000110 1 ------1-0- 1
1111010001 1
-----11--1 1
1111101001 1
1111111111 1
.e
0010000000 1
1101100111 1
0010001111 1
I
1111100010 1
T
9 argumentów
P 1010111101 1
W
0110000110 1
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
1101110011 1
Można wykazać, że
0100100000 1
funkcja ta jest zależna od
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
7 argumentów!
0010001111 1
I 1111100010 1
T
1010111101 1
P
0110000110 1
W
0100111000 1
.e
ZPT
4
Wniosek
Espresso redukuje składniki iloczynowe
Nie redukuje argumentów!!!
I
Co to znaczy w praktyce?
T
P
W
ZPT
5
Realizacja w PLA
1
x1
PLA o 8 wejściach
2
x2
3
x3
4
x4
5
x5
AND
.i 10
6
x6
.o 1
.p 6
7
x7
----00-1-- 1
8
x8
00--0----- 1
x9
----10-0-01
?
---1--0--1 1
1 2 p
------1-0- 1
-----11--1 1
f1
.e
f2
I
OR
T
f3
P
W
ZPT
6
Realizacja w PLA po redukcji argumentów
1
x1
2
x2
3
x3
4
x4
O.K. Funkcja ma
5
x5
AND
7 argumentów,
6
jest realizowalna x6
7
x7
8
1 2 p
f1
f2
I
OR
T
f3
P
W
ZPT
7
PROBLEM:
Jak obliczyć minimalną liczbę argumentów
od których funkcja istotnie zależy ???
Nowy sposób opisu funkcji: rachunek podziałów
I
Elementy rachunku podziałów w skryptach &
T
P
W
ZPT
8
I
T
P
W
ZPT
9
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
{,2,6,7,8; 3,4,5,9}
1
P2 =
5 0 1 0 0 1 0 1 1
{,3,5,6; 2,4,7,8,9}
1
P3 =
6 1 0 0 0 1 1 0 1
{,4,5,6,7,8,9; 2,3}
1
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
{,5,7,9; 2,3,4,6,8}
1
P6 =
1,4,5,9}
{2,3,6,7,8;
P7 =
I
T
P Pf = {,2,3,4;
1 5,6,7,8,9}
W
ZPT
10
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ą
Wyjaśnienie i interpretacja w książce:
Synteza układów cyfrowych
I
T
P
W
ZPT
11
Redukcja argumentów  przykład
Funkcja f
x4 x6  zmienne niezbędne
różnią
ponieważ wiersze 2 i 8
x1 x2 x3 x4 x5 x6 x7 f
x4 x6
x4
się na pozycji
1 1 0 0 0 1 0 1 0
x6
a wiersze 4 i 9 na pozycji
2 1 0 1 1 1 1 0 0
3 1 1 0 1 1 1 0 0
P4 =
{1,4,5,6,7,8,9; 2,3}
4 1 1 1 0 1 1 1 0
{1,5,7,9; 2,3,4,6,8}
P6 =
5 0 1 0 0 1 0 1 1
6 1 0 0 0 1 1 0 1
Dalej liczymy iloczyn P4 P6
7 1 0 1 0 0 0 0 1
8 1 0 1 0 1 1 0 1
(1,5,7,9 ; 4,6,8 ;2,3)
P4" P6 =
9 1 1 1 0 1 0 1 1
I
T
{1,2,3,4; 5,6,7,8,9}
P Pf =
W
ZPT
12
Redukcja argumentów  przykład
Iloczyn podziałów wyznaczonych przez zmienne
niezbędne ma bardzo ważną interpretację
(1,5,7,9 ; 4,6,8 ;2,3)
P4" P6 =
{1,2,3,4; 5,6,7,8,9}
Pf =
I
T
P
W
ZPT
13
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
5 0 1 0 0 1 0 1 1
4, 6, 8
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
1, 5 x1 x2
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
...ale teraz systematycznie...
14
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) = 1
(x2 +x1)(x2 + x3)(x2 + x7)(x3 + x5 + x7) =
(x2 +x1x3x7)(x3 + x5 + x7) =
= x2x3 + x2x5 +x2x7 + x1x3x7 + . . .
*" {x4,x6}
*"
*"
*"
I
T
P {x2,x3,x4,x6} {x2,x4,x5,x6} {x2,x4,x6,x7}
W
ZPT
15
Redukcja argumentów  przykład c.d.
x1 x2 x3 x4 x5 x6 x7 f x2 x4 x6 x7 f
1 1 0 0 0 1 0 1 0 1 0 0 0 1 0
2 1 0 1 1 1 1 0 0 2 0 1 1 0 0
3 1 1 0 1 1 1 0 0 3 1 1 1 0 0
4 1 1 1 0 1 1 1 0 4 1 0 1 1 0
5 0 1 0 0 1 0 1 1 5 1 0 0 1 1
6 1 0 0 0 1 1 0 1 6 0 0 1 0 1
7 1 0 1 0 0 0 0 1 7 0 0 0 0 1
8 1 0 1 0 1 1 0 1 8 0 0 1 0 1
9 1 1 1 0 1 0 1 1 9 1 0 0 1 1
{x2,x4,x6,x7}
I
T
P
W
ZPT
16
& skutecznie wspomaga proces minimalizacji
funkcji boolowskich
Wprowadzenie redukcji argumentów do
procedury ekspansji daje  w rozsądnym czasie 
wyniki lepsze niż słynne Espresso
17
Przykład z Synteza układów cyfrowych str 32
.type fr
Funkcja TL27
.i 10
.o 1
10 argumentów
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
.i 10
1100010011 0
.o 1
0100010110 0
1110100110 0
.p 6
0100110000 0
----00-1-- 1
0101000010 0 Espresso
0111111011 1
00--0----- 1
0000010100 1
----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 9 argumentów
0010001111 1
I
6 termów
1111100010 1
T
P 1010111101 1
W
0110000110 1
0100111000 1
.e
ZPT
18
Funkcja TL27
Funkcja TL27 przed redukcją
Realizacja funkcji f1
Ilość zmiennych = 7
.type fr
Ilość wektorów = 25
.i 10
R3 = {1,2,4,6,7,9,10}
.o 1
0001110 0
.p 25
1001000 0
0010111010 0
0101110 0
1010010100 0 1010111 0
1101011 0
0100011110 0
0101010 0
1011101011 0
1100010 0
1100010011 0 0101000 0
0110010 0
0100010110 0
0111111 1
1110100110 0
0001000 1
Pandor
0100110000 0 1111011 1
0100000 1
0101000010 0
0101111 1
0111111011 1
0000010 1
0000010100 1 1111001 1
1110101 1
1101110011 1
1111111 1
0100100000 1
0000000 1
1110011 1
0100011111 1
0000111 1
0010000110 1
1110010 1
1111010001 1
1001101 1
0100010 1
1111101001 1
0101100 1
1111111111 1
0010000000 1
I
1101100111 1
T
0010001111 1
Jedno z 10 rozwiązań po
P
1111100010 1
W
redukcji argumentów
1010111101 1
0110000110 1
ZPT
0100111000 1
19
.e
Przykład TL27
Funkcja 10 argumentów, 25 wektorów w TP
Wynik Pandora  7 argumentów
f = x1x2x7 + x1x2x4 + x1x10 + x1x4x6 + x7x9
Wynik Espresso  9 argumentów
f = x5x6x8 + x1x2x5 + x5x6x8x10 + x4x7x10 + x7x9 + x6x7x10
Powierzchnia PLA S = (2n+m)P
I
T
P
SEsp= 114 SPan= 75
W
ZPT
20
Funkcja KAZ
Przed redukcj
Jedno z wielu rozwi
za
Przed redukcj
Jedno z wielu rozwi
za
Przed redukcj
Jedno z wielu rozwi
za
Przed redukcj
Jedno z wielu rozwi
za
po redukcji argumentów
o redukcji
o redukcji
o 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
T 000010001110001101101 0
101000010100001110000 0
P
101000110101010011111 0
W
101010000001100011001 0
011100111110111101111 0
.end
ZPT
21
Przykład KAZ
Silnie nieokreślona funkcja 21 argumentów,
31 wektorów w TP
Wynik Espresso  9 argumentów, 3 termy
f = x2x14x19x21 + x7x8x12 + x5x8x20
Wynik Pandora  5 argumentów, 3 termy
f = x2x4x9x19 + x2x4x9 + x2x19x20
Powierzchnia PLA S = (2n+m)P
I
T
SEsp= 57 SPan= 33
P
W
ZPT
22