tc 05, Studia infa, Technika Cyfrowa TC, wyk (staszek2708)
[ Pobierz całość w formacie PDF ]
Sławomir Kulesza
Technika cyfrowa
Minimalizacja form
boolowskich
Wykład dla studentów III roku Informatyki
Wersja 1.0, 05/10/2010
Minimalizacja form boolowskich
Minimalizacja – proces przekształcania form
boolowskich w celu otrzymania możliwie naj-
prostszych form równoważnych.
Kryterium minimalizacji – obniżenie kosztu
układu cyfrowego, skrócenie ścieżek propagacji
sygnałów, ograniczenie liczby sygnałów w ukła-
dzie.
Drogi minimalizacji – (1) zmniejszanie liczby
bramek, (2) zmniejszanie liczby wejść bramek.
Sens minimalizacji
Wskaźnik złożoności
Zwykle nie wiadomo, czy dana forma boolowska jest
poszukiwaną formą minimalną.
W celu oszacowania złożoności form boolowskich sto-
suje się tzw. wskaźnik złożoności (kosztu):
Z = LT + LL
LT – liczba termów formy boolowskiej
LL – liczba literałów w formie boolowskiej
Wskaźnik Z powinien przyjmować wartość możliwie
małą.
Przykład oszacowania wskaźnika Z
x
1
x
2
f(x
1
,x
2
)
0
0
0
0
1
1
1
0
0
1
1
1
Kanoniczna forma iloczynowa:
(
fX
) = (
x
1
+
x
2
)⋅(
x
1
+
'x
2
) ⇨ = + =
Z235
Kanoniczna forma sumacyjna:
fXx
1
⋅
'x
2
+
x
1
⋅
x
2
⇨ = + =
Z235
() =
Formaminimalna
() =
:
fXx
2
⇨ = + =
Z112
[ Pobierz całość w formacie PDF ]