Podręcznik

W tym punkcie zajmiemy się analitycznym opisem dekompozycji funkcji boolowskich. Do tego celu posłużymy się omówionym w rozdz. 1 rachunkiem podziałów. W szczególności wyprowadzimy warunki dekompozycji dla funkcji boolowskich opisanych podziałami P₁, P₂,..., P_n, P_f określonymi na zbiorze K ponumerowanych wektorów tablicy prawdy funkcji f.

Na początek zajmiemy się poszukiwaniem realizacji f = h(U,g(V,W)), gdzie:

$U=\left\{x_{i_1},\ldots,x_{i_r}\right\},\ \ V=\left\{x_{i_{r+1}},\ldots,x_{i_t}\right\},\ \ w=\left\{x_{j_1},\ldots,x_{j_t}\right\}\ $

a ponadto

$W\subseteq\ U,\ U\cup\ V\subseteq\ X,\ U\cap\ V=\Phi$  oraz $\ \ P\left(x_{i_1}\right)\cdot\ P\left(x_{i_2}\right)\cdot\cdot\cdot\ P\left(x_{i_t}\right)\le\ P_f$

Sens powyższych ustaleń wynika z faktu, że dla danego U zbiór V może być wyznaczony bezpośrednio z reprezentacji argumentowej RA_f ograniczonej do par p, q: {p,q} $\subseteq$BLOK(P_U), gdzie $P_U=P_{i_1}\ldots\ P_{i_r}$

Oznaczając tak zdefiniowaną reprezentację przez RA_g, łatwo stwierdzić, że V jest rozwiązaniem równania RA_g = 1. Ponadto przez P_V, P_W będziemy oznaczać podziały na K określone zbiorami V  i W, tzn.:

W szczególności f = h(U, g (V)) wtedy i tylko wtedy, gdy istnieje P_g ³ P_V, dla którego P_U · P_g $\le$  P_f (jest to tzw. dekompozycja rozłączna [3.15].

Uzasadnienie jest natychmiastowe, jeżeli zauważymy, że dwublokowy podział P_g ³ P_V,W jednoznacznie reprezentuje funkcję g, natomiast P_U · P_g funkcję h. Otóż każdy blok H  podziału P_V,W jest wzajemnie jednoznaczną reprezentacją wektora o składowych $\left(x_{j_1},\ldots,x_{j_p},x_{i_{r+1}},\ldots,x_{i_t}\right)$, gdyż skoro  H $\in$ P_V · P_W, to dla każdego P_a spośród $P_{j_1}\ldots\ P_{j_p},P_{i_{r+1}}\ldots\ P_{i_t}$ blok H należy do ustalonego bloku  podziału P_a. Zapisując ten fakt w formie przyporządkowania:

H ® wektor o składowych binarnych c $\in$ {0,1}

i uwzględniając, że blokom tym są w podziale P_g przyporządkowane:

$0,\ gdy\ H\in\Pi_g^0$

$1,\ gdy\ H\in\Pi_g^1$

uzyskujemy naturalną reprezentację g: B ^t-r+p ® {0,1}. Z kolei, skoro P_U · P_g $\le$ P_f, to $P_{i_1}\ldots\ P_{i_r}\cdot\ P\left(g\right)\le\ P\left(f\right)$ i tym samym $f=h\left(x_{i_1},\ldots,x_{i_r},g\right)\ \ $
Natomiast wartości h wynikają (analogicznie jak poprzednio) z przynależności bloków P_U · P_g do bloków podziału P_f.

Jak wynika z twierdzenia 3.2 najistotniejsze w obliczeniu dekompozycji funkcji boolowskiej jest obliczenie podziału P_G.  Algorytm obliczania P_G można sprowadzić do algorytmu obliczania MKZ. Oznaczmy bloki podziału P_V: P_V =(B₁,…,B_i,…,B_j,…,B_N) i przyjmijmy przez poddział g_ij rozumieć podział uzyskany z P_V przez sklejenie B_i oraz B_j w jeden blok i pozostawienie pozostałych bloków bez zmiany, tzn.: g_ij =(B₁,…,B_iB_j,…,B_N).

Dwa bloki B_i i B_j podziału P_V są zgodne, jeśli podział  g_ij spełnia warunek twierdzenia o dekompozycji: P_U · g_ij £ P_F. W przeciwnym przypadku B_i oraz B_j  są niezgodne.

W ten sposób obliczanie Π_G można sprowadzić do algorytmu obliczania MKZ. Wystarczy w tym celu dla obliczonych par zgodnych B_i, B_j (albo sprzecznych) obliczyć rodzinę maksymalnych zbiorów zgodnych bloków B, a następnie stosując algorytm wyznaczania minimalnego pokrycia skojarzyć zbiory bloków minimalnego pokrycia z blokami podziału Π_G.

Ale do wyznaczenia zgodnych (lub sprzecznych) par (B_i, B_j) niekoniecznie musimy się posługiwać skomplikowaną  nierównością P_U · g_ij £ P_F. Wystarczy w tym celu obliczyć iloczyn zbioru B_i È B_j  z blokami podziału P_U i sprawdzić, czy każdy „niepusty iloczyn” jest zawarty w jakimś bloku P_F.

Do obliczenia P_G zastosujemy algorytm wyznaczania klas zgodnych wg par niezgodności: (B₁, B₇), (B₂, B₅), (B₂, B₆), (B₃, B₇), (B₄, B₅), (B₄, B₆), i (B₅, B₇).  Utworzona według par niezgodnych formuła typu iloczyn sum i jej kolejne przekształcenia są następujące:

(B₁ + B₇) (B₂ + B₅) (B₂ + B₆) (B₃ + B₇) (B₄ + B₅) (B₄ + B₆) (B₅ +  B₇) =

= (B₇ + B₁B₃B₅) (B₂B₄ + B₅B₆) = B₂B₄B₇ + B₅B₆B₇ + B₁B₂B₃B₄ B₅ +  B₁B₃B₅B₆

Klasy zgodne uzyskamy odejmując od zbioru {<i>B</i>₁,...,<i>B</i>₇}, zbiory tych B_i, które występują w jednym składniku obliczonego wyżej wyrażenia typu „suma  iloczynów”. Stąd:

B₁B₃B₅B₆ + B₁B₂B₃B₄ + B₆B₇ + B₂B₄B₇.

{<i>B</i>₁,..., <i>B</i>₇} - {<i>B</i>₂, <i>B</i>₄, <i>B</i>₇} = { <i>B</i>₁, <i>B</i>₃, <i>B</i>₅, <i>B</i>₆}

{<i>B</i>₁,...,<i>B</i>₇} - {<i>B</i>₅, <i>B</i>₆, <i>B</i>₇ } = {<i> B</i>₁, <i>B</i>₂, <i>B</i>₃, <i>B</i>₄}

{<i>B</i>₁,...,<i>B</i>₇} -  {<i>B</i>₁, <i>B</i>₂, <i>B</i>₃, <i>B</i>₄, <i>B</i>₅}  = {<i>B</i>₆, <i>B</i>₇}

{<i>B</i>₁,...,<i>B</i>₇} - {<i> B</i>₁, <i>B</i>₃, <i>B</i>₅, <i>B</i>₆} = {<i>B</i>₂, <i>B</i>₄, <i>B</i>₇}

Z powyższych klas bloków zgodnych można wyselekcjonować dwie: { <i>B</i>₁, <i>B</i>₃, <i>B</i>₅, <i>B</i>₆} oraz{<i>B</i>₂, <i>B</i>₄, <i>B</i>₇}, pokrywające zbiór {<i>B</i>₁,..., <i>B</i>₇}, czyli: 

$\Pi_g=\left\{\overline{B_1,B_3,B_5,B_6};\overline{B_2,B_4,B_7}\right\}$.

W tym przypadku rozwiązanie jest trywialne. Wracając do pierwotnych kostek tworzących poszczególne bloki B_i otrzymujemy:

$\Pi_g=\left\{\overline{1,3,5,6,8,10,11};\overline{2,4,7}\right\}$

w którym od razu określamy kodowanie bloków.

Obliczanie podziału P_G można uprościć rezygnując z możliwości uzyskania rozwiązania optymalnego tj. podziału P_G z najmniejszą liczbą bloków, co w realizacji odpowiada najmniejszej liczbie wyjść z komponentu G. Metoda prowadząca do takiego rozwiązania polega na zastosowaniu podziału ilorazowego P_U |P_U·P_F. Podział ilorazowy podaje informację, które bloki podziału P_V należy umieścić w różnych blokach tworzonego podziału P_G. Dwa bloki B_i, B_j, podziału P_V należy umieścić w różnych blokach P_G wtedy, gdy ich przecięcia ze zbiorem B_u podziału  P_U należą do różnych elementów C_s, C_t, odpowiedniego bloku podziału P_U |P_U·P_F. Taką metodę konstruowania podziału P_G nazywać będziemy metodą rozdziału elementów podziału ilorazowego P_U |P_U·P_F. Na przykład dla podziałów  P_U, P_f,  P_V z przykładu 3.1:

$P_U=P_1•P2=(\overline{1,3,5,7};\overline{2,4,6,8};\overline{9,11};\overline{10})$

$P_f=\left\{\overline{1,2,3,4,5};\overline{6,7,8,9,10,11}\right\}$

$P_V=P_3•P4•P5=(B1,B2,B3,B4,B5,B6,B7)=(\overline{1};\overline{2};\overline{3,9};\overline{4};\overline{5,8};\overline{6,10,11};\overline{7})$

podział ilorazowy jest następujący: $P_U|P_U•PF=(\overline{(1,3,5)(7)};\overline{(2,4)(6,8)};\overline{(9,11)};\overline{(10)})$

Rozważmy bloki B₁ i B₇ podziału P_V. Ich przecięcia z blokiem $B_U=\overline{1,3,5,7}$ , czyli 1 i 7 należą odpowiednio do C_s =  (1,3,5) oraz  C_t = (7), czyli dwóch różnych elementów P_U |P_U·P_f. Zatem konstruując podział P_G należy B₁ i B₇ umieścić w różnych blokach P_G.

Metodę rozdziału przy tworzeniu podziału P_G dla funkcji z przykładu 3.1 wyjaśnimy posługując się interpretacją graficzną przedstawioną na rys. 3.4.

Rys.  3.4. Konstrukcja podziału P_g

Z po­działu ilorazowego wnioskujemy, że P_G może być dwublokowy i musi rozdzielać elementy (1,3,5) od (7), (2,4) od (6,8) itd.  Dlatego (zaczynając od pierwszego bloku podziału ilorazowego) bloki P_V zawierające elementy 1; 3,9 oraz 5,8 umieszczamy w pierwszym bloku P_G – na rys 3.3 z lewej strony pionowej kreski, natomiast blok zawierający 7 musimy umieścić w drugim –  po prawej stronie pionowej kreski. W drugim bloku podziału ilorazowego należy rozdzielić (2,4) od (6,8). Ale element 8 został już wpisany do pierwszego bloku, zatem również do pierwszego bloku należy wpisać blok P_V = (6,10,11), natomiast do drugiego należy wpisać (2) i (4). W rezultacie uzyskujemy identyczny jak poprzednio.

$\Pi_g=\left\{\overline{1,3,5,6,8,10,11};\overline{2,4,7}\right\}$

Zastosowanie omówionych wyżej algorytmów dekompozycji do syntezy logicznej modułów wielowyjściowych (np. matryce PLA, moduły PLD, pamięci ROM) wymaga przede wszystkim uogólnienia podstawowego twierdzenia o dekompo­zycji na przypadek układów wielowyjściowych. Łączna (jednoczesna) dekompozy­cja wszystkich funkcji wchodzących w skład układu realizo­wanego z zastosowaniem modułu wielo­wyjściowego poz­wala na wyodrębnienie wielowyjściowych podukładów H, G, których tablice prawdy stanowią bądź bezpośrednią informację, określającą na przy­kład zawartość pamięci ROM lub komórki typu LUT, bądź też są punktem wyjścia do dal­szych etapów syntezy (np. minimalizacja układów wielowyjściowych) w przypadku matryc PLA.

Łatwo sprawdzić, że P_V × P_g £ P_f. Zatem dekompozycja istnieje. Dalej, ko­rzystając z podziałów P_V  i  P_g oblicza­my tablicę funkcji g (tab. 3.7). Obliczenia interpretujemy następująco. Dla przykładu: blok $\overline {1}$ jest zawarty w drugim bloku podziałów P₁, P₅, P₆, natomiast w pierwszym bloku podziału P₁₀ oraz w pierwszym bloku podziału P_g. Dlatego odpowiadający mu wektor jest 1110, ma wartość funkcji g = 0 (patrz tab. 3.6).

Podobnie postępujemy dla funkcji h (tab. 3.7), ale tu korzystamy z bloków ilo­czynu podziałów P_U × P_g oraz ich przynależności do podziałów  P₇, P₈, P₉, P_g oraz P_f .

Tablica  3.6	Tablica  3.7