UL&TC 3, Technika Cyfrowa

[ Pobierz całość w formacie PDF ]
pokój EA 540,
wpr@eti.pg.gda.pl
UkładyLogiczne
i
TechnikaCyfrowa
CzęśćIII–minimalizacjafunkcjilogicznych
Dr in
Ŝ
. Paweł Raczy
ń
ski
2008-03-07
P. R. KSA WETI PG
1
Reguły sklejania (1)
W poprzedniej części spotkaliśmy się z zagadnieniem upraszczania
algorytmicznych metod minimalizacji funkcji logicznych
.
stosowaniu do upraszczania funkcji
reguł sklejania
(19) i (20).
Ax +Ax = A
–
reguła dla postaci sumacyjnej
(A + x)*(A + x) = A
–
reguła dla postaci iloczynowej
ZauwaŜmy, Ŝe w wyniku sklejania
redukcji ulega jedna ze
postaci prostej i zanegowanej.
2008-03-07
P. R. KSA WETI PG
2
funkcji logicznych. Obecnie zaprezentujemy dwie, spośród wielu
Minimalizacja funkcji logicznych polega na wielokrotnym
zmiennych
, ta która występuje w obu składnikach/czynnikach w
Reguły sklejania (2)
Aby wyeliminowa
ć
dwie zmienne z postaci funkcji nale
Ŝ
y zastosowa
ć
Ax y +Axy + Axy + Axy = A
(A+x+y)*(A+x+y)*(A+x+y)*(A+x+y) = A
Jak wida
ć
, zmienne, które zamierzamy wyeliminowa
ć
na mocy
wszystkich mo
Ŝ
liwych wariacjach poło
Ŝ
enia negacji.
sklejaniu
ró
Ŝ
ni
ą
si
ę
poło
Ŝ
eniem negacji
nad jedn
ą
ze zmiennych, a
wi
ę
c
s
ą
s
ą
siednie w sensie Hamminga
.
2008-03-07
P. R. KSA WETI PG
3
reguły sklejania w poni
Ŝ
szej postaci:
reguły sklejania musz
ą
wyst
ę
powa
ć
w składnikach/czynnikach we
Istotnym spostrze
Ŝ
eniem jest,
Ŝ
e składniki/czynniki podlegaj
ą
ce
Reguły sklejania – przykład zastosowania
Zminimalizować funkcję:
f (x
1
,x
2
,x
3
) = x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
=
S
(2,3,4,5,7)
JeŜeli skleimy składniki o numerach 2 i 3 oraz 5 i 7 otrzymamy:
f (x
1
,x
2
,x
3
) = x
1
x
2
+ x
1
x
3
+ x
1
x
2
x
3
W której to postaci nie moŜna dokonać dalszych sklejeń. Nie naleŜy
numerach 2i 3, 3 i 7, 4 i 5 oraz 5 i 7 bo otrzymamy:
f (x
1
,x
2
,x
3
) = x
1
x
2
+ x
2
x
3
+ x
1
x
2
+ x
1
x
3
NaleŜy skleić składniki o numerach 2 i 3, 4 i 6 oraz 5 i 7 otrzymując:
f (x
1
,x
2
,x
3
) = x
1
x
2
+ x
1
x
2
+ x
1
x
3
Co jest postacią minimalną.
2008-03-07
P. R. KSA WETI PG
4
takŜe wykonywać wszystkich moŜliwych sklejeń tzn. składników o
Reguły sklejania – wnioski
Analiza powyŜszego przykładu prowadzi do następujących
wniosków:
• pierwszym problemem jest
znalezienie wszystkich
Hamminga
i mogą potencjalnie wziąć udział w operacji
sklejania;
• drugim problemem jest
wybór składników/czynników
Algorytmiczna metoda minimalizacji powinna określić
zapewnić gwarancję osiągnięcia postaci minimalnej w
określonym sensie.
2008-03-07
P. R. KSA WETI PG
5
składników/czynników, które są sąsiednie w sensie
sklejanych w celu osiągnięcia postaci minimalnej
.
efektywne metody rozwiązania obydwu problemów oraz
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • emaginacja.xlx.pl

    •