1
I
T
P
W
ZPT
Espresso
. . . mankamenty
2
I
T
P
W
ZPT
Funkcja 7 argumentów
x
1
x
2
x
3
x
4
x
5
x
6
x
7
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
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
x
2
x
4
x
6
x
7
f
1 0 0 0 1 0
2 0 1 1 0 0
3 1 1 1 0 0
4 1 0 1 1 0
5 1 0 0 1 1
6 0 0 1 0 1
7 0 0 0 0 1
8 0 0 1 0 1
9 1 0 0 1 1
Pamiętamy . . . z ekspansji
6
2
7
4
x
x
x
x
f
Czy można przewidzieć od jakich argumentów
funkcja istotnie zależy ???
3
I
T
P
W
ZPT
Przykład z Synteza układów
cyfrowych str 32
Funkcja
10 argumentów
9 argumentów
.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e
.i 10
.o 1
.p 6
----00-1-- 1
00--0----- 1
----10-0-01
---1--0--1 1
------1-0- 1
-----11--1 1
.e
Espresso
4
I
T
P
W
ZPT
.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e
Zagadka...
Można wykazać, że
funkcja ta jest
zależna od
7 argumentów!
Od ilu
argumentów
zależy ta
funkcja
5
I
T
P
W
ZPT
Wniosek
Espresso redukuje składniki iloczynowe
Co to znaczy w praktyce?
Nie redukuje
argumentów!!!
6
I
T
P
W
ZPT
Realizacja w PLA
PLA o 8 wejściach
f
f
f
1
2
3
1 2 p
A N D
O R
1
2
3
4
5
6
7
8
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
?
.i 10
.o 1
.p 6
----00-1-- 1
00--0----- 1
----10-0-01
---1--0--1 1
------1-0- 1
-----11--1 1
.e
7
I
T
P
W
ZPT
Realizacja w PLA po redukcji
argumentów
O.K. Funkcja ma
7 argumentów,
jest realizowalna
f
f
f
1
2
3
1 2 p
A N D
O R
1
2
3
4
5
6
7
8
x
1
x
2
x
3
x
4
x
5
x
6
x
7
8
I
T
P
W
ZPT
PROBLEM:
Jak obliczyć minimalną liczbę argumentów
od których funkcja istotnie zależy ???
Nowy sposób opisu funkcji: rachunek podziałów
Elementy rachunku podziałów w skryptach …
9
I
T
P
W
ZPT
10
I
T
P
W
ZPT
Nowy sposób opisu funkcji -
podziały
x
1
x
2
x
3
x
4
x
5
x
6
x
7
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
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
P
1
=
P
2
=
P
f
=
;
5
{
;
8
,
7
,
6
,
2
,
1
{
;
4
,
3
,
2
,
1
{
}
9
,
8
,
7
,
6
,
4
,
3
,
2
,
1
}
9
,
5
,
4
,
3
P
3
=
;
6
,
5
,
3
,
1
{
}
9
,
8
,
7
,
4
,
2
P
4
=
;
9
,
8
,
7
,
6
,
5
,
4
,
1
{
}
3
,
2
P
5
=
;
7
{
}
9
,
8
,
6
,
5
,
4
,
3
,
2
,
1
P
6
=
;
9
,
7
,
5
,
1
{
}
8
,
6
,
4
,
3
,
2
P
7
=
;
8
,
7
,
6
,
3
,
2
{
}
9
,
5
,
4
,
1
}
9
,
8
,
7
,
6
,
5
Funkcja f
11
I
T
P
W
ZPT
Pojęcie zmiennej niezbędnej
Wyjaśnienie i interpretacja w książce:
Synteza układów cyfrowych
Jeżeli wektory
X
a
oraz X
b
: f (X
a
) f (X
b
), różnią się dokładnie
dla jednej zmiennej to zmienną taką nazywamy niezbędną
12
I
T
P
W
ZPT
Redukcja argumentów – przykład
x
1
x
2
x
3
x
4
x
5
x
6
x
7
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
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
Funkcja f
– zmienne
niezbędne
ponieważ wiersze
2 i 8
P
6
=
}
3
,
2
;
9
,
8
,
7
,
6
,
5
,
4
,
1
{
}
8
,
6
,
4
,
3
,
2
;
9
,
7
,
5
,
1
{
Dalej liczymy iloczyn P
4
P
6
x
4
x
6
x
4
x
4
a wiersze 4 i
9
x
6
x
6
różnią się na pozycji
na
pozycji
P
4
=
P
4
•P
6
=
)
4,6,8
1,5,7,9
(
2,3
;
;
P
f
=
}
9
,
8
,
7
,
6
,
5
;
4
,
3
,
2
,
1
{
13
I
T
P
W
ZPT
Redukcja argumentów – przykład
Iloczyn podziałów wyznaczonych przez zmienne
niezbędne ma bardzo ważną interpretację
P
4
•P
6
=
)
4,6,8
1,5,7,9
(
2,3
;
;
P
f
=
}
9
,
8
,
7
,
6
,
5
;
4
,
3
,
2
,
1
{
14
I
T
P
W
ZPT
Redukcja argumentów – przykład
c.d.
1, 5, 7, 9
4, 6, 8
Tu obliczamy minimalne
pokrycie kolumnowe
1, 5
x
1
x
2
1, 7
x
3
x
5
x
7
1, 9
x
2
x
3
4, 6
x
2
x
3
x
7
4, 8
x
2
x
7
x
1
x
2
x
3
x
5
x
7
x
2
x
3
x
2
x
7
...ale teraz systematycznie...
x
1
x
2
x
3
x
4
x
5
x
6
x
7
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
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
15
I
T
P
W
ZPT
Redukcja argumentów – przykład
c.d.
(x
1
+ x
2
)(x
3
+ x
5
+ x
7
)(x
2
+ x
3
)(x
2
+ x
7
) = 1
(x
2
+x
1
)(x
2
+ x
3
)(x
2
+ x
7
)(x
3
+ x
5
+
x
7
) =
(x
2
+x
1
x
3
x
7
)(x
3
+ x
5
+ x
7
) =
= x
2
x
3
+ x
2
x
5
+x
2
x
7
+ x
1
x
3
x
7
+ . . .
{x
2
,x
3
,x
4
,x
6
}
x
1
x
2
x
3
x
5
x
7
x
2
x
3
x
2
x
7
{x
2
,x
4
,x
5
,x
6
}
{x
2
,x
4
,x
6
,x
7
}
{x
4
,x
6
}
16
I
T
P
W
ZPT
Redukcja argumentów – przykład
c.d.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
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
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
x
2
x
4
x
6
x
7
f
1
0
0
0
1
0
2
0
1
1
0
0
3
1
1
1
0
0
4
1
0
1
1
0
5
1
0
0
1
1
6
0
0
1
0
1
7
0
0
0
0
1
8
0
0
1
0
1
9
1
0
0
1
1
{x
2
,x
4
,x
6
,x
7
}
17
…skutecznie wspomaga proces
minimalizacji funkcji boolowskich
Wprowadzenie redukcji argumentów do
procedury ekspansji daje – w rozsądnym
czasie – wyniki lepsze niż słynne Espresso
18
I
T
P
W
ZPT
Przykład z Synteza układów
cyfrowych str 32
Funkcja TL27
10 argumentów
.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e
.i 10
.o 1
.p 6
----00-1-- 1
00--0----- 1
----10-0-01
---1--0--1 1
------1-0- 1
-----11--1 1
.e
Espresso
9 argumentów
6 termów
19
I
T
P
W
ZPT
Funkcja TL27
Funkcja TL27 przed
redukcją
.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e
Realizacja funkcji f1
Ilość zmiennych = 7
Ilość wektorów = 25
R3 = {1,2,4,6,7,9,10}
0001110 0
1001000 0
0101110 0
1010111 0
1101011 0
0101010 0
1100010 0
0101000 0
0110010 0
0111111 1
0001000 1
1111011 1
0100000 1
0101111 1
0000010 1
1111001 1
1110101 1
1111111 1
0000000 1
1110011 1
0000111 1
1110010 1
1001101 1
0100010 1
0101100 1
Jedno z 10
rozwiązań po
redukcji
argumentów
Pandor
20
I
T
P
W
ZPT
Przykład TL27
Funkcja 10 argumentów, 25 wektorów w TP
10
7
6
9
7
10
7
4
10
8
6
5
5
2
1
8
6
5
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
Wynik Pandora – 7 argumentów
9
7
6
4
1
10
1
4
2
1
7
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
f
Powierzchnia PLA
S = (2n+m)P
S
Esp
= 114
S
Pan
= 75
Wynik Espresso – 9 argumentów
21
I
T
P
W
ZPT
Funkcja KAZ
.type fr
.i 21
.o 1
.p 31
100110010110011111101 1
111011111011110111100 1
001010101000111100000 1
001001101100110110001 1
100110010011011001101 1
100101100100110110011 1
001100100111010011011 1
001101100011011011001 1
110110010011001001101 1
100110110011010010011 1
110011011011010001100 1
010001010000001100111 0
100110101011111110100 0
111001111011110011000 0
101101011100010111100 0
110110000001010100000 0
110110110111100010111 0
110000100011110010001 0
001001000101111101101 0
100100011111100110110 0
100011000110011011110 0
110101000110101100001 0
110110001101101100111 0
010000111001000000001 0
001001100101111110000 0
100100111111001110010 0
000010001110001101101 0
101000010100001110000 0
101000110101010011111 0
101010000001100011001 0
011100111110111101111 0
.end
01010 1
10110 1
00100 1
01001 1
01000 1
11010 1
10011 0
01110 0
10100 0
11000 0
11011 0
10000 0
00010 0
01111 0
00011 0
11111 0
00000 0
01101 0
00110 0
Przed redukcją
Jedno z wielu rozwiązań
po redukcji argumentów
Ile jest
takich
rozwiązań
Pandor
22
I
T
P
W
ZPT
Przykład KAZ
Silnie nieokreślona funkcja 21 argumentów,
31 wektorów w TP
Wynik Espresso – 9 argumentów, 3 termy
20
8
5
12
8
7
21
19
14
2
x
x
x
x
x
x
x
x
x
x
f
Wynik Pandora – 5 argumentów, 3 termy
20
19
2
9
4
2
19
9
4
2
x
x
x
x
x
x
x
x
x
x
f
Powierzchnia PLA
S = (2n+m)P
S
Esp
= 57
S
Pan
= 33
Document Outline
- Slide 1
- Slide 2
- Slide 3
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Slide 8
- Slide 9
- Slide 10
- Slide 11
- Slide 12
- Slide 13
- Slide 14
- Slide 15
- Slide 16
- Slide 17
- Slide 18
- Slide 19
- Slide 20
- Slide 21
- Slide 22
Wyszukiwarka
Podobne podstrony:
ulog w4b
ulog w8b T
ulog w2
ulog w6 E
Automatyka ulog w8 id 629066 Nieznany (2)
w4a Zatrucie sola kuchenna
ulog demain
ulog w8a T
ulog w9b
ulog w8a e
ulog w6b
ulog w7a
ulog w9 e
ulog w1
ulog t pr 06
Zad 03-2, WEiTI - Makro, SEMESTR I, ULOG
więcej podobnych podstron