190
3.4.4. Faktoryzacja
Przedstawione dotychczas metody minimalizacji funkcji (zarówno jej NPS jak i NPI) dawały w rezultacie wyrażenia o sztywnej strukturze. Na przykład minialna NPS funkcji to suma pewnej liczby iloczynów zmiennych, przy czym niektóre zmienne wchodzące do iloczynów mogą być zanegowane. Przenosząc te rozwaZania na płaszczyznę realizacji funkcji z wykorzystaniem elementów małej skali integracji SSI, tzn. bramek logicznych (patrz rozdz. 3.5), można stwierdzić, że struktura uzyskiwanych układów również jest sztywna i zawiera trzy poziomy elementów: poziom inwerterów i dwa poziomy bramek wielowejściowych, odpowiednio, bramek iloczynu i bramek sumy. Analogicznie w przypadku minimalnej NPI funkcji, jest to iloczyn pewnej liczby sum zmiennych
bądź negacji zmiennych. Struktura układu w tym przypadku zawiera poziom inwerterów, poziom bramek sumy oraz poziom bramek iloczynu.
Okazuje się że sztywna struktura schematów odpowiadających wyrażeniom NPS i NPI funkcji nie w każdym przypadku zapewnia
rozwiązanie wymagające rzeczywiście minimalnej liczby bramek. W związku z tym opracowane zostały metody, które lepiej minimalizują liczbę bramek i liczbę ich wejść. Jedną z nich jest faktoryzacja. Polega ona na przekształcaniu minimalnych wyrażeń NPS lub NPI do postaci, która zawiera mniej literałów, a tym samym daje się zrealizować z pomocą
mniejszej liczby bramek lub bramek o mniejszej liczbie wejść
Przekształcenia te to najczęściej prawa de Morgana, wyciąganie przed nawias wspólnego czynnika (w przypadku NPS) lub częściowe wymnażanie (w przypadku NPI). Opisują je m.in. poniższe wzory:
(3.75a) (3.75b)
(3.75c)
AB + AC = A(B+C),
(A+B) (A+C) = A + BC,
ABC = AB BC = AB ABC,
gdzie A, B, C są zmiennymi lub wyrażeniami logicznymi.
Przykład 3.18 (4)
(3.76)
Minimalna NPS funkcji czterech zmiennych jest następująca: f (Xj.X2.X2.X4) = y-^y-2 + xix3 + xlx4 + xix2x3x4
Faktoryzacja daje następujące rezultaty:
(3.77)
f(Xj.X2.X3.X4) « Xj(Xg + x3 + x4) ♦ XjX2X3X4 =
Cl(
X,| x2 x3 x4 + x1x2x3x4
Do realizacji postaci (3.7S) potrzebne są cztery inwertery, cztery bramki iloczynowe (trzy dwuwejściowe i jedna czterowejściowa) oraz jedna czterowejściowa bramka sumy - łącznie 9 bramek o sumarycznej liczbie 18 wejść. W skrócie, koszt realizacji można opisać parą liczb (9,18). Postać sfaktoryzowana (3.77) wymaga czterech inwerterów, jednej trzywejściowej bramki NAND, dwu bramek iloczynowych - jednej dwuwejściowej a drugiej czterowejściowej oraz jednej dwuwejściowej bramki sumy. Łącznie potrzeba 8 bramek o sumarycznej liczbie 15 wejść - koszt realizacji wynosi zatem (8,15). Jeszcze tańsza jest realizacja z wykorzystaniem bramki EXOR - pozostawiamy to Czytelnikowi.
Określanie kosztu realizacji układu jest najwygodniejsze na podstawie jego schematu; -asady tworzenia schematów w oparciu o analityczne postaci funkcji awiane są w rozdz. 3.5.
Przykład 3.19 (4]
Minimalna NPS funkcji jest następująca:
(3.78)
f (Xj.X2.X3.X4) - x2x3 + XjX2 ♦ x2x4 ♦ x2x3x4
Faktoryzacja przebiega następująco:
f(Xj. |
X2.X3.X4) = |
X2X3 |
+ xlx2 |
+ x2= | |
X2X3 |
+ xlx2 |
+ X2X4 + |
X2X3X4 * |
• xix; | |
x2 (x J |
+ X3 ' |
- V |
+ X3 |
x4(x2 * |
XjX2 |
x2xjX |
3X4) + |
X3X4 |
[x2 |
+ Xj(x2 |
+ x2 |
X2X1X |
3X4) + |
X3X4 |
(Xj |
+ x25 = |
X2X1X3X4 * X3X4X1X2
(3.79)
(na podst. prawa (3.75c))
X2X1X2X3X4 + X3X4 X1X2X3X4