Rotation of�

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 ^{+ x}i^x3 ^{+ x}l^x4 ^{+ x}i^x2^x3^x4

Faktoryzacja daje następujące rezultaty:

(3.77)

f(Xj.X2.X3.X4) « Xj(Xg + x₃ + x₄)    ♦ XjX2X3X₄ =

^Cl(

X,| x₂ x₃ x₄ + x₁x₂x₃x₄

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) - x₂x₃ + XjX₂ ♦ x₂x₄ ♦ x₂x₃x₄

Faktoryzacja przebiega następująco:

f(Xj.	X2.X3.X4) =		^X2^X3	^+ xl^x2	^+ x2=
^X2^X3	^+ xl^x2	^+ X2^X4 ^+		^X2^X3^X4 *	• ^xi^x;
^x2 (^x J	^+ X3 '	- V	^+ X3	x4(x2 *	XjX2
^x2^xjX	3^X4) +	^X3^X4	[^x2	+ Xj(x2	^+x2
^X2^X1^X	3^X4) ^+	^X3^X4	(Xj	^+ x2^5 =

^X2^X1^X3^X4 * ^X3^X4^X1^X2

+ x₂x₃x₄

(3.79)

(na podst. prawa (3.75c))

^X2^X1^X2^X3^X4 ^{+ X}3^X4 ^X1^X2^X3^X4