Podręcznik

1. Metoda klasyczna

Niech będzie dana funkcja boolowska f: {0, 1}ⁿ ® {0, 1} oraz pewien podział zmiennych X = {x1,..., xn} na dwa rozłączne zbiory B (bound set) i A (free set). Tablicą dekompozycji funkcji f (decomposition chart) nazywamy macierz dwuwymiarową o kolumnach etykietowanych wartościami zmiennych funkcji f ze zbioru B oraz o wierszach etykietowanych wartościami zmiennych funkcji f ze zbioru A. Elementami macierzy M są wartości, jakie przyjmuje funkcja f na wektorach złożonych z odpowiednich etykiet i-tego wiersza i j-tej kolumny. Liczbę istotnie różnych kolumn tej macierzy ze względu na ich zawartość oznaczamy symbolem n(A|B) (column multiplicity).

Niech będzie dana funkcja boolowska f oraz podział zbioru zmiennych wejściowych funkcji f na dwa rozłączne zbiory A i B, wówczas:

f(A,B) = h(A,g₁(B),..., g_j(B)) Û n(A|B) £ 2^j

Schemat takiej dekompozycji jest przedstawiony na rys. 3.1.

Uzupelnij opis obrazka

Rys. 3.1. Schemat blokowy dekompozycji funkcjonalnej

Twierdzenie powyższe można uogólnić na przypadek zespołów funkcji. Niech będzie dana rodzina funkcji boolowskich F, wówczas:

F(A,B) = H(A,G(B)) dla G(B) = (g₁(B),..., g_j(B)) Û n(A|B) £ 2^j

Dla funkcji z tablicy 3.1 kolumny są adresowane trzema zmiennymi {x1, x2, x3} względem których funkcja f jest symetryczna. Wiersze natomiast są adresowane zmiennymi {x4, x5}.

Tablica 3.1

Uzupelnij opis obrazka

Grupy kolumn o adresach {(001), (010), (100)} i {(110), (101), (011)} są odpowiednio równe. Zatem istnieje dekompozycja, w której zmienne {x1, x2, x3} są przeadresowywane na {g1, g2} (tablica 3.2a).

Wówczas funkcja f może być specyfikowana w tablicy, w której adresami kolumn są {g1, g2}, a wierszy odpowiednio wartości zmiennych {x4, x5} (patrz tablica 3.2b). Tablice te są jednocześnie tablicami prawdy funkcji reprezentujących składowe dekompozycji, tzn. bloki G i H.

Tablica 3.2

Uzupelnij opis obrazka

Niestety postępowanie takie w ogólnym przypadku funkcji nie w pełni określonych nie może być już tak bezpośrednie. Przykład takiej bardziej skomplikowanej sytuacji omówimy dokonując dekompozycji funkcji podanej w tabl. 3.4.

Tablica 3.3

Uzupelnij opis obrazka

Otóż w tym przypadku, ze względu na nieokreśloności funkcji, nie można bezpośrednio podjąć decyzji, które kolumny w tablicy dekompozycji są takie same. Wynika to z faktu, że kreskom reprezentującym punkty nieokreśloności funkcji można przypisać wartość albo 0 albo 1, w rezultacie zaliczając odpowiednią kolumnę do – być może – innego zbioru kolumn identycznych. Dlatego w tym przypadku wygodnie będzie wszystkie kolumny, dla których w poszczególnych wierszach tablicy dekompozycji nie występują sprzeczne wartości (0 i 1), nazywać kolumnami zgodnymi. Zgodne są na przykład kolumny K₀ i K₃, gdyż w ich poszczególnych wierszach, jako wartości funkcji, występują wyłącznie: 1 (w kolumnie K₀) i 1 (w kolumnie K₃), oraz odpowiednio, – i –; – i 0; wreszcie 0 i –. Natomiast kolumny K₀ i K₁ są niezgodne, gdyż w wierszu oznaczonym 11 mają wartości funkcji odpowiednio 0 i 1. Nietrudno zauważyć, że tak definiowane pary kolumn zgodnych tworzą relację zgodności, której własności: zwrotność, symetryczność i nieprzechodniość uprawniają do grupowania kolumn zgodnych w maksymalne klasy zgodności. Wypisując więc dla funkcji z tabl. 3.4 wszystkie pary zgodne: {K0, K3}, {K0, K4}, {K0, K6}, {K1, K3}, {K1, K4}, {K1, K5}, {K1, K6}, {K2, K5}, {K2, K7}, {K3, K4}, {K3, K6}, {K4, K5}, {K4, K6}, {K5, K7}, łatwo możemy obliczyć – stosując algorytm omówiony w rozdz. 1 – maksymalne klasy zgodności:

{K0, K3, K4, K6},

{K1, K3, K4, K6},

{K1, K4, K5},
{K2, K5, K7}.

Ze zrozumiałych względów niektóre kolumny występują w więcej niż jednej klasie zgodności. Musimy więc podjąć decyzję o wyborze rozłącznych klas zgodności (nie muszą być w tym przypadku maksymalne) pokrywających wszystkie kolumny tablicy dekompozycji, tzn. każda kolumna musi być reprezentowana w jednej klasie zgodności. Jedno z możliwych rozwiązań jest:{K0, K3, K4, K6}, {K2, K5}, {K2, K7}.

Po połączeniu kolumn należących do jednej klasy w jedną, uzyskuje się tablice funkcji G i H oraz wyrażenia boolowskie tych funkcji:

$g_1=\bar{c}d\bar{e}+cde$

$g_2=\bar{c}d\bar{e}+ce+\bar{d}e$

$h=\bar{a}{\bar{g}}_2+bg_2+ag_1$

Funkcjom G i H odpowiada schemat blokowy oraz logiczny przedstawiony odpowiednio na rys. 3.2a oraz 3.2b.

a)	b)

Rys. 3.2. Schemat blokowy (a) i logiczny (b) funkcji GiH

Przedstawiona wyżej metoda, jakkolwiek łatwa do interpretacji graficznej, w obliczeniach analitycznych bardziej skomplikowanych przykładów staje się zbyt pracochłonna. Na przykład dla funkcji TL27 (patrz tab. 2.28) odpowiednia tablica dekompozycji – uzyskana dla reduktu R₁₀ = {x3, x5, x6, x7, x8, x9, x10} – jest przedstawiona w tab. 3.4.

Tablicę tę skonstruowano przy założeniu, że zbiory zmiennych bezpośrednich oraz pośrednich są odpowiednio A = {x7, x8, x9}, B = {x3, x5, x6, x10}. Spostrzeżenie, że w tablicy tej – w celu obliczenia składowych G i H dekompozycji – należy „skleić” kolumny oznaczone wektorami: 0000, 0011, 0100, 0101, 1000, 1001, 1010, 1011, 1111 oraz 0010, 0110, 0111, 1100, 1101, 1110, nie jest zadaniem łatwym. Spostrzeżenie to prowadzi do wniosku, że funkcję TL27 można zrealizować, jak na rys. 3.3.

Rys. 3.3. Realizacja funkcji TL27	Tablica 3.4

2. Dekompozycja funkcjonalna metodą rachunku podziałów

Dekompozycja funkcjonalna metodą rachunku podziałów

2.1. Dekompozycja funkcjonalna – model podstawowy

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.:

$P_V=P\left(x_{i_{r+1}}\right)\cdot\ P\left(x_{i_{r+2}}\right)\cdot\ldots\cdot\ P\left(x_{i_t}\right)$

$P_W=P\left(x_{j_1}\right)\cdot\ P\left(x_{j_2}\right)\cdot\ldots\cdot\ P\left(x_{i_t}\right)$

Jeżeli f : Bⁿ ®{0,1,–} oraz X = U $\cup$ V jest zbiorem argumentów funkcji f, to:

f = h(U, g (V, W))

wtedy i tylko wtedy, gdy istnieje dwublokowy podział P_g ³ P_V · P_W taki, że:

P_U · P_g $\le$ P_f,

gdzie g: B ^t-r+p ® {0,1}, przy czym g (k) = c, natomiast k Î K, c Î {0,1}, jeżeli $\Pi_g^c$ .

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_Gmoż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 Π_Gmoż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.

Sposób postępowania wyjaśnimy na przykładzie funkcji podanej w tablicy 3.5.
Tablica 3.5

	x₁	x₂	x₃	x₄	x₅	f
1	0	0	0	0	0	0
2	0	1	0	1	1	0
3	0	0	1	0	1	0
4	0	1	1	1	1	0
5	0	0	1	1	0	0
6	0	1	0	0	1	1
7	0	0	1	0	0	1
8	0	1	1	1	0	1
9	1	0	1	0	1	1
10	1	1	0	0	1	1
11	1	0	0	0	1	1

Zakładając dekompozycję dla zbiorów: U = {x1,x2}, V = {x3,x4,x5} podziały P_U = P₃•P₄ i P_V = P₁•P₂•P₅można wyznaczyć bezpośrednio z podziałów:

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

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

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

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

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

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

Na tej podstawie obliczamy:

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

$P_V=P_3•P4•P5=(\overline{1};\overline{2};\overline{3,9};\overline{4;5,8};\overline{6,10,11};\overline{7})$

Numerujemy bloki P_V:

P_V= (B₁, B₂, B₃, B₄, B₅, B₆, B₇)

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

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

P_U · g₁₂ $\leq$ P_f,

P_U · g₅₇ $\nleq$ P_f,

czyli para (B₁, B₂) jest zgodna, natomiast para (B₅, B₇) jest sprzeczna.

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łuP_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 {B1,...,B7}, 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₇.

{B1,..., B7} - {B2, B4, B7 }= { B1, B3, B5, B6}

{B1,...,B7} - {B5 , B6 , B7 } = { B1, B2, B3, B4}

{B1,...,B7} - {B1, B2, B3, B4 , B5} = {B6 , B7}

{B1,...,B7} - { B1, B3, B5, B6} = {B2, B4, B7 }

Z powyższych klas bloków zgodnych można wyselekcjonować dwie: { B1, B3, B5, B6} oraz{B2, B4, B7 }, pokrywające zbiór {B1,..., B7}, 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.

Uzupelnij opis obrazka

Rys. 3.4. Konstrukcja podziału P_g

Z podział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\}$

Skuteczność wprowadzonego aparatu pokażemy na przykładzie funkcji TL27 (podroz. 2.6 – tab. 2.28 ).

Dla tej funkcji obliczyliśmy jeden z minimalnych zbiorów argumentów: X = {x3, x5, x6, x7, x8, x9, x10}. Korzystając z tej informacji załóżmy poszukiwanie dekompozycji dla zbiorów U = {x7, x8, x9} oraz V = {x3, x5, x6, x10}. Bezpośrednio z tablicy 2.28 zapisujemy podziały P_i utworzone na zbiorze K ponumerowanych wektorów K = {1, 2, …, 25}:

$P_1=\left\{\overline{1,3,6,8,9,10,11,13,14,15,19,21,24,25};\overline{2,4,5,7,12,16,17,18,20,22,23}\right\}$

$P_2=\left\{\overline{1,2,4,11,15,19,21,23};\overline{3,5,6,7,8,9,10,12,13,14,16,17,18,20,22,24,25}\right\}$

$P_3=\left\{\overline{3,5,6,8,9,11,12,13,14,20,25};\overline{1,2,4,7,10,15,16,17,18,19,21,22,23,24}\right\}$

$P_4=\left\{\overline{1,2,3,5,6,7,8,11,13,14,15,19,21,23,24,25};\overline{4,9,10,12,16,17,18,20,22}\right\}$

$P_5=\left\{\overline{2,3,5,6,9,11,14,15,16,19,21,24};\overline{1,4,7,8,10,12,13,17,18,20,22,23,25}\right\}$

$P_6=\left\{\overline{4,7,9,13,15,17,19,20,21,22,24};\overline{1,2,3,5,6,8,10,11,12,14,16,18,23,25}\right\}$

$P_7=\left\{\overline{2,5,6,7,8,9,11,12,13,15,16,19,20,22,24};\overline{1,3,4,10,14,17,18,21,23,25}\right\}$

$P_8=\left\{\overline{1,4,5,8,9,10,12,13,16,17,19,22,25};\overline{2,3,6,7,11,14,15,18,20,21,23,24}\right\}$

$P_9=\left\{\overline{2,8,11,13,16,17,19,23,25};\overline{1,3,4,5,6,7,9,10,12,14,15,18,20,21,22,24}\right\}$

$P_{10}=\left\{\overline{1,2,3,6,7,8,9,11,13,15,19,22,24,25};\overline{4,5,10,12,14,16,17,18,20,21,23}\right\}$

$P_f=\left\{\overline{1,2,\ldots,9};\overline{10,\ldots,25}\right\}$

Kolejne obliczenia uzyskane bezpośrednio z podziałów P_i są następujące:

$P_U=P_7•P8•P9=(\overline{1,4,10};\overline{2,11};\overline{3,14,18,21};\overline{5,9,12,22};\overline{6,7,15,20,24};\overline{8,13,16,19};\overline{17,25};\overline{23})$

$P_V=P_3•P5•P6•P10=(\overline{1};\overline{2};\overline{3,6,11};\overline{4,17};\overline{5,14};\overline{7,22};\overline{8,25};\overline{9};\overline{10,18,23};\overline{12};\overline{13};\overline{15,19,24};\overline{16};\overline{20};\overline{21})$

Dla wygody dalszych obliczeń podział P_U zapiszemy w postaci podziału ilorazowego:

$P_U|P_f=\overline{\left(1,4\right)\left(10\right)};\overline{\left(2\right)\left(11\right)};\overline{\left(3\right)\left(14,18,21\right)};\overline{\left(5,9\right)\left(12,22\right)};\overline{\left(6,7\right)\left(15,20,24\right)};\overline{\left(8\right)\left(13,16,19\right)};\overline{\left(17\right)\left(25\right)};\overline{\left(23\right)}$

Najważniejszą czynnością jest obliczenie podziału P_g . Aby to zrealizować wystarczy zauważyć, że:

podział P_g musi rozdzielać elementy 1 i 4 od elementu 10; 2 od 11; 3 od 14 i 18 i 21 itp. Wynika to z podziału ilorazowego,
podział P_g musi być zbudowany z bloków podziału P_V.

Zatem, jeśli zaliczymy bloki $\overline {1}$ oraz $\overline {4,17}$ do pierwszego bloku P_g, to blok $\overline {10,18,23}$ musimy zaliczyć do drugiego bloku P_g (ponieważ zawiera element 10) itp. Reszta obliczeń jest pokazana na rys. 3.5.

P_g
Blok pierwszy	Blok drugi
$\overline {1}$ $\overline {4,17}$	$\overline {10,18,23}$
$\overline {3,6,11}$	$\overline {2}$ $\overline {5,14}$ $\overline {21}$
$\overline {12}$ $\overline {7,22}$	$\overline {9}$
$\overline {8,25}$	$\overline {15,19,24}$ $\overline {20}$
	$\overline {13}$ $\overline {16}$

Rys. 3.5. Konstrukcja podziału P_g

Na tej podstawie stwierdzamy, że:

$\Pi _{g} =\left\{\overline{1,3,4,6,7,8,11,12,17,22,25} ;\overline{2,5,9,10,13,14,15,16,18,19,20,21,23,24}\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 dekompozycji na przypadek układów wielowyjściowych. Łączna (jednoczesna) dekompozycja wszystkich funkcji wchodzących w skład układu realizowanego z zastosowaniem modułu wielowyjściowego pozwala na wyodrębnienie wielowyjściowych podukładów H, G, których tablice prawdy stanowią bądź bezpośrednią informację, określającą na przykład zawartość pamięci ROM lub komórki typu LUT, bądź też są punktem wyjścia do dalszych 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, korzystając z podziałów P_V i P_g obliczamy 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 iloczynu podziałów P_U × P_goraz ich przynależnoścido podziałów P₇, P₈, P₉, P_g oraz P_f.

Tablica 3.6	Tablica 3.7

2.2. Dekompozycja zespołów funkcji boolowskich

Ze względu na różne zastosowanie przedstawionego wyżej schematu, blok G będziemy nazywać albo układem składowych dekompozycji g_j, albo układem modyfikacji adresu. Pierwsza nazwa jest analogią do dekompozycji pojedynczej funkcji boolowskiej. Druga z kolei wiąże się z zastosowaniem dekompozycji w projektowaniu układów adresowania pamięci ROM, dla których to układów ograniczenia w liczbie wejść adresowych zmuszają do procesu modyfikacji adresu o n bitach na adres t-bitowy.

Oznaczmy jak poprzednio wektory z B ⁿ liczbami naturalnymi K = {1,...,÷ B n÷}, a przez P_F podział wyjściowy funkcji F skonstruowany w następujący sposób:

(s, t) Î $\mathcal{B_{P_{F}}}$ Û F(s) = F(t)

Inaczej mówiąc, wektory s i t należą do jednego bloku B podziału P_F tylko wtedy, gdy odwzorowanie F przyporządkowuje tym wektorom taki sam wektor z {0,1}^m. Na przykład, dla odwzorowania F określonego jak w tabl. 3.8 podział P_F (zapisany w postaci podziału na zbiorze K = {1,2,...,15}) będzie miał postać:

$P_F=\left(\overline{1,9,14};\overline{5,7,8,13};\overline{2,6,12};\overline{4,11};\overline{3,10,15}\right)$

Tablica 3.8

x₁ x₂ x₃ x₄ x₅

y₁ y₂ y₃

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0 0 0 0 0

0 0 0 1 1

0 0 0 1 0

0 1 1 0 0

0 1 1 0 1

0 1 1 1 0

0 1 0 0 0

1 1 0 0 0

1 1 0 1 0

1 1 1 0 0

1 1 1 1 1

1 1 1 1 0

1 0 0 0 1

1 0 0 1 1

1 0 0 1 0

0 0 0

0 1 0

1 0 0

0 1 1

0 0 1

0 1 0

0 0 1

0 0 0

1 0 0

0 1 1

0 1 0

0 0 1

0 0 0

1 0 0

Warunek istnienia dekompozycji o schemacie blokowym jak na rys. 3.6, gdzie U, V są rozłącznymi podzbiorami zbioru X funkcji F(X) oraz W Í U formułuje następujące twierdzenie.

Funkcja F: B ⁿ ®{0,1,–}^m ma dekompozycję (rys. 3.6):

F = H (U, G (V, W ))

wtedy i tylko wtedy, gdy istnieje podział P_G ³ P_V_È_W taki, że:

P_U × P_G £ P_F

Uzupelnij opis obrazka

Dekompozycja wg twierdzenia 3.3

Jak widać zastosowanie rachunku podziałów okazało się wyjątkowo wygodne, gdyż odpowiednie twierdzenie o dekompozycji układów wielowyjściowych traktuje zespół funkcji jako pojedynczy obiekt, podlegający zasadom dekompozycji identycznie jak pojedyncza funkcja boolowska.

Dla układu funkcji F z tabl. 3.9 przyjmijmy U = {x1, x3, x4} oraz z V = {x2, x5} oraz W = f.

Tablica 3.9

x₁ x₃ x₄ g

y₁ y₂ y₃

1

2

3

4

5

6

7

8,13

9,14

10

11

12

15

0 0 0 0

0 0 1 1

0 0 1 0

0 1 0 1

0 1 0 0

0 1 1 1

0 0 0 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 0

1 1 1 1

1 0 1 0

0 0 0

0 1 0

1 0 0

0 1 1

0 0 1

0 1 0

0 0 1

0 0 0

1 0 0

0 1 1

0 1 0

1 0 0

Podział P_U = P₁ × P₃ × P₄ (P_i = P(x_i)), P_V = P₂ × P₅. Zapisując P_U w postaci podziału ilorazowego mamy, że:

$P_{U} |P_{F} =\overline{( 1)( 7)} ;\overline{( 8)( 13)} ;\overline{( 2)( 3)} ;\overline{( 9,14)( 15)} ;\overline{( 4)( 5)} ;\overline{( 10)} ;\overline{( 6)} ;\overline{( 11)( 12)}$

$P_{V} =\left\{\overline{1,3,15} ;\overline{2,13,14} ;\overline{4,6,7,8,9,1012} ;\overline{5,11}\right\}$

Blokom H₁,...,H₄ podziału P_V odpowiadają wektory D(H₁) = 00, D(H₂) = 01, D (H₃) = 10, D(H₄) = 11. W celu wyznaczenia dwublokowego podziału P_G ³ P_V spełniającego warunek dekompozycji (3-1) zauważmy, że jeśli blok H₁ przeznaczymy do pierwszego bloku podziału P_G, to blok H₃ należy przeznaczyć do drugiego bloku tego podziału. Stwierdzenie to jest wynikiem faktu, że H₁ zawiera wektor 1, H₃ zawiera wektor 7, a ponadto wektory te należą do różnych bloków podziału wyjściowego P_F. Fakt ten jest zresztą zaznaczony w podziale ilorazowym P_U½P_F. Mamy więc $\Pi ^{0}_{G} =\{1,3,15\}$ , więc $\Pi ^{1}_{G} =\{4,6,7,8,9,10,12\}$ . Następnie sprawdzamy kolejną parę wektorów z P_U½P_F, czyli 2 i 3. Skoro 3 jest w $\Pi ^{0}_{G}$ , to $\Pi ^{1}_{G} =\Pi ^{1}_{G} \cup \{2,3,14\}$ . Kolejna para (9,14) i (15) należy już do różnych bloków P_G, a więc sprawdzamy 4 i 5. Stąd:

$\Pi _{G} =\left(\overline{1,3,5,11,15} ;\overline{2,4,6,7,8,9,10,12,13,14}\right)$

Łatwo stwierdzić, że funkcja g przyporządkowuje wektorowi (x₂, x₅) = (0,0) wartość 0, i analogicznie g(0,1) = 1, g(1,0) = 1, g(1,1) = 0. Ostatecznie g = x₂ Å x₅. W rezultacie, dla układu y₁, y₂, y₃ funkcji z tabl. 3.9 danego odwzorowaniem F : (y₁, y₂, y₃) = F(x₁,...,x₅) uzyskaliśmy dekompozycję: F = H(x₁, x₃, x₄, g(x₂ Å x₅)).

Tablicę prawdy funkcji H można wyznaczyć na podstawie przynależności bloków iloczynu P₁ × P₃ × P₄ × P_G do bloków podziałów P₁, P₃, P₄, P_G oraz P_F. Odpowiednie obliczenia podane są w tabl. 3.10.

Tablica 3.10

(2)	(9,14)	(3,15)
$\overline{2};$	$\begin{array}{{>{\displaystyle}l}} \overline{8,9,10,12}\\ \overline{13,14} \end{array}$	$\begin{array}{{>{\displaystyle}l}} \overline{1,3}\\ \overline{15} \end{array}$
$\overline{4,6,7};$		$\overline{5}$
		$\overline{11}$

Z kolei dla U = {x3, x4} oraz V = {x1, x2, x5}, podział P_U = P₃ × P₄, P_V = P₁ × P₂× P₅, a więc:

$P_U=\left(\overline{1,7,8,13};\overline{2,3,9,14,15};\overline{4,5,10};\overline{5,6,11,12}\right)$

$P_F=\left(\overline{1,9,14};\overline{5,7,8,13};\overline{2,6,12};\overline{4,11};\overline{3,10,15}\right)$

$P_U|P_F=\overline{\left(1\right)\left(7,8,13\right)};\overline{\left(2\right)\left(9,14\right)\left(3,15\right)};\overline{\left(4\right)\left(5\right)\left(10\right)};\overline{\left(11\right)\left(6,12\right)}$

$P_V=\left(\overline{1,3};\overline{2};\overline{4,6,7};\overline{5};\overline{8,9,10,12};\overline{11};\overline{13,14};\overline{15}\right)$

gdzie bloki P_V są oznaczone kolejno B₁, B₂,..., B₈.

Z podziału ilorazowego P_U|P_F wnioskujemy, że odpowiedni P_G powinien mieć co najmniej 3 bloki. Wynika to z faktu, że elementy (2), (9,14) i (3,15) muszą należeć do trzech różnych bloków P_G (to samo dotyczy (4), (5) i (10)). Ponadto pamiętamy, że P_G³ P_V. Zatem wprowadzenie bloków z P_V do tworzonego P_G powinno przebiegać według schematu pokazanego w tablicy 3.10. Stąd:

$\Pi_G=\left(\overline{2,4,6,7};\overline{8,9,10,12,13,14};\overline{1,3,5,11,15}\right)$

Przyjmując, że kodowanie bloków P_Gjest: pierwszy blok – 01, drugi blok – 10, trzeci blok – 00 i uwzględniając, iż kolejnym blokom z podziału P_V odpowiadają wektory (zmienne x₁, x₂, x₅) odpowiednio: B₁ = 000, B₂ = 001, B₃ = 010, B₄ = 011, B₅ = 110, B₆ = 111, B₇ = 101 oraz B₈ = 100, wyznaczamy tablicę prawdy funkcji G (tab. 3.11).

Tablica 3.11

x₁ x₂ x₅

g₁ g₂

$\overline {8,9,10,12}$

$\overline {11}$

$\overline {13,14}$

$\overline{15}$

0 0 0

0 0 1

0 1 0

0 1 1

1 1 0

1 1 1

1 0 1

1 0 0

0 0

0 1

0 0

1 0

0 0

1 0

0 0

Podobnie, po obliczeniu iloczynu: $P_{U} \cdot \Pi _{G} =\left(\overline{1} ;\overline{7} ;\overline{8,13} ;\overline{3,15} ;\overline{2} ;\overline{9,14} ;\overline{4} ;\overline{5} ;\overline{10} ;\overline{6} ;\overline{11} ;\overline{12}\right)$ wyznaczamy tablicę prawdy funkcji H (tab. 3.12).

Tablica 3.12

	x₃	x₄	g₁	g₂	y₁	y₂	y₃
$\overline {1}$	0	0	0	0	0	0	0
$\overline {7}$	0	0	0	1	0	0	1
$\overline {8,13}$	0	0	1	0	0	0	1
$\overline {3,15}$	0	1	0	0	1	0	0
$\overline {2}$	0	1	0	1	0	1	0
$\overline {9,14}$	0	1	1	0	0	0	0
$\overline {4}$	1	0	0	1	0	1	1
$\overline {5}$	1	0	0	0	0	0	1
$\overline {10}$	1	0	1	0	1	0	0
$\overline {6}$	1	1	0	1	0	1	0
$\overline {11}$	1	1	0	0	0	1	1
$\overline {12}$	1	1	1	0	0	1	0

2.3. Pojęcie r-przydatności

Istotną zaletą rachunku podziałów wprowadzonego w poprzednim rozdziale jest prosta metoda selekcji zbioru argumentów należących do zbioru U.

W selekcji argumentów x_i ze zbioru U spełniających warunek (3-1) z twierdzenia 3.3 pomocne jest pojęcie r - p r z y d a t n o ś c i zbioru podziałów względem podziału P [3.1], [3.15].

Oznaczmy przez g(t÷d) liczbę elementów w największym bloku ilorazu podziałów t i d.

Niech G(t÷d) = log₂ g(t÷d).

Zbiór {P1,...,Pk} jest r-przydatny względem P, gdzie:

r = k + G(P₁...P_k|P · P₁...P_k) (3-2)

Dla zmiennej x₁ z tab. 3.9 obliczymy r dla $P_1=\left(\overline{1,2,3,4,5,6,7};\overline{8,9,10,11,12,13,14,15}\right)$ oraz $P=\left(\overline{1,9,14};\overline{5,7,8,13};\overline{2,6,12};\overline{4,11};\overline{3,10,15}\right)$

Mamy tu:

$P\cdot \ P_{1} =\left(\overline{1} ;\overline{9,14} ;\overline{5,7} ;\overline{8,13} ;\overline{2,6} ;\overline{12} ;\overline{4} ;\overline{11} ;\overline{3} ;\overline{10,15}\right)$

$P|P\cdot P_{1} =\left\{\overline{( 1)( 2,6)( 3)( 4)( 5,7)} ;\overline{( 8,13)( 9,14)( 10,15)( 11)( 12)}\right\}$

g(P₁|P · P₁) = 5, G(P₁|P · P₁) = 3, czyli r = 4

Można więc r-przydatności dwublokowych podziałów P_i względem podziału P obliczać bezpośrednio z P_i oraz P, grupując po prostu elementy w bloku podziału P_i w podzbiory o maksymalnej liczności należące do ustalonego bloku podziału P. Dlatego też iloraz P_i÷P·P_i oznaczać będziemy często po prostu przez P_i, zapisując elementy tego ilorazu w nawiasach.

Jeśli {P1,...,Pk} jest r-przydatny (k < r) względem P, to istnieje zbiór podziałów {Pk+1,...,Pr}, dla których:

P₁...P_k · P_k₊₁...P_r £ P

natomiast nie istnieje {Pk’+1,...,Pr’-1} taki, że:

P₁...P_k · P_k^’₊₁,...,P_r^’_-1 £ P

jest m-przydatność zbioru {P1,...,Pk} względem P.

Można również wykazać, że jeśli P = {P1,...,Pk} jest m-przydatny względem P, to każdy podzbiór z P jest m'-przydatny, gdzie m' £ m. Tym samym warunkiem koniecznym na to, aby P = {P1,...,Pk} był m-przydatny względem P jest r-przydatność podzbiorów z P taka, że dla każdego P' zawartego w P, r(P') £ m. To proste stwierdzenie pozwala w łatwy sposób grupować podziały 2-blokowe w zbiory o ustalonej przydatności.

Na przykład, jeśli w zbiorze podziałów {P1,...,P5} następujące podzbiory są m-przydatne: {P1, P3}, {P1, P4}, {P3, P4}, {P4, P5}, to jedynym m-przydatnym zbiorem o liczności 3 może być tylko zbiór {P1, P3, P4}.

Zastosowanie r-przydatności w syntezie funkcji g, to jest składowych dekompozycji wyjaśnia następujący przykład.

Obliczymy r-przydatność podziałów P(x_i) dla układu F funkcji z tab. 3.9. Mamy tu:

$P( x_{1}) =\left\{\overline{( 1)( 2,6)( 3)( 4)( 5,7)} ;\overline{( 8,13)( 9,14)( 10,15)( 11)( 12)}\right\}$

czyli P(x₁) jest 4-przydatny względem P_F. Dokonując analogicznych obliczeń dla pozostałych podziałów, stwierdzamy, że P(x₃), P(x₄) są 3-przydatne, natomiast P(x₂), P(x₅), 4-przydatne.

Uzupelnij opis obrazka

Rys. 3.7. Ilustracja obliczeń z przykładu 3.4: a) przy założeniu, że zbiór {P(x3), P(x4)} jest 3-przydatny; b) przy założeniu, że {P(xi), P(xj), P(xk)} jest 4-przydatny

Jeśli więc istnieje dekompozycja układu F taka, jaką pokazano na rys. 3.7a, to byłoby to możliwe tylko pod warunkiem, że zbiór {P(x3), P(x4)} jest 3-przydatny. Ale

$P( x_{3}) \cdot P( x_{4}) =\left\{\overline{( 1)( 7,8,13)} ;\overline{( 9,14)( 2)( 3,15)} ;\overline{( 4)( 5)( 10)} ;\overline{( 11)( 6,12)} ;\right\}$

czyli {P(x3), P(x4)} jest 4-przydatny. Sprawdźmy więc, czy istnieje dekompozycja o schemacie blokowym jak na rys. 3.7b.

W tym celu obliczymy r dla każdego zbioru {P(xi), P(xj)}. W wyniku uzyskujemy, że 4-przydatnymi parami są tylko {P1, P3}¹⁾, {P1, P4}, {P2, P3}, {P2, P4}, {P3, P4}, {P3, P5} oraz {P4, P5}.

W związku z tym 4-przydatnymi trójkami mogą być tylko: a) {P1, P3, P4}; b) {P2, P3, P4}; c) {P3, P4, P5}.

Następnie stwierdzamy, że wyłącznie trójki a) oraz c) są 4-przydatne. Dla trójek tych odpowiednie iloczyny podziałów są:

$P( x_{1}) \cdot P( x_{3}) \cdot P( x_{4}) =\left\{\overline{( 1)( 7)} ;\overline{( 8,13)} ;\overline{( 2)( 3)} ;\overline{( 9,14)( 15)} ;\overline{( 4)( 5)} ;\overline{( 10)} ;\overline{( 6)} ;\overline{( 11)( 12)}\right\}$

$P( x_{3}) \cdot P( x_{4}) \cdot P( x_{5}) =\left\{\overline{( 1)( 7,8)} ;\overline{( 13)} ;\overline{( 9)( 3,15)} ;\overline{( 14)( 2)} ;\overline{( 4)( 10)} ;\overline{( 5)} ;\overline{( 6)( 12)} ;\overline{( 11)}\right\}$

¹⁾ Stosujemy tu oznaczenie P(x_i) = P_i.

Z przykładu 3.4 wynika, że synteza składowych dekompozycji wymaga utworzenia wszystkich możliwych dwójek, trójek... podziałów o ustalonej r-przydatności. Przy dużej liczbie zmiennych wejściowych (dużym n) wymaga to obliczenia stosunkowo dużej liczby r-przydatności zbiorów {Pi , Pj} (i, j Î {1,...,n}), gdyż liczba wszystkich różnych par {Pi , Pj} jest n!/2(n – 2)!.

Proces ten można uprościć, określając związki między r-przydatnością podziałów dwublokowych.

Jeżeli r(P_a) = n i r(P_b) = n, to zbiór {Pa , Pb} ma przydatność co najwyżej równą n+1, jeżeli natomiast r(P_a) = n i r(P_b) = n + 1, to zbiór {Pa , Pb} jest n+1-przydatny.

Zastosujemy powyższe związki w celu obliczenia 4-przydatnych par P_i , P_j dla podziałów P₁,..., P₅ z przykładu 3.4. Poprzednio obliczyliśmy, że r-przydatności tych podziałów wynoszą odpowiednio: 3 dla P₃, P₄ oraz 4 dla P₁, P₂, P₅ . Na mocy powyższych związków, 4-przydatnymi zbiorami {Pi , Pj} są: {P1, P3}, {P1, P4}, {P2, P3}, {P2, P4}, {P3, P5}, {P4, P5}, natomiast r-przydatność pary {P3, P4} jest r': 3 £ r' £ 4, a par {P1, P2}, {P1, P5}, {P2, P5} jest r": 4 £ r" £ 5. Stąd wniosek, że w celu wyselekcjonowania wszystkich 4-przydatnych par wystarczy obliczyć
r-przydatność wyłącznie dla par {Pi , Pj}: (i, j) Î {(3,4),(1,2), (1,5),(2,5)} – czyli czterech par. Poprzednio (w przykładzie 3.4) obliczenia te należało wykonać dla 10 par.

Dla funkcji F z tablicy 3.13 zbiory podziałów {P1, P2}, {P1, P4}, {P1, P5}, {P2, P3}, {P2, P4}, {P3, P4},{P3, P5},{P4, P5} są 4-przydatne. Obliczyć wszystkie najlepsze dekompozycje szeregowe tej funkcji dla U = {xi, xj, xk}, czyli F = H(x_i, x_j, x_k, G₀). Wykazać, że dla żadnej z nich nie istnieje dekompozycja F = H(G₁(x_i, x_j, x_k), G₀).

Tablica 3.13

	x₁	x₂	x₃	x₄	x₅	y₁	y₂	y₃
1	0	0	0	1	1	1	0	0
2	0	0	0	1	0	1	0	1
3	0	1	1	0	0	0	1	1
4	0	1	1	0	1	0	1	0
5	1	1	0	0	0	0	0	1
6	1	1	0	1	0	0	0	0
7	1	1	1	0	0	1	0	1
8	1	1	1	1	0	0	1	0
9	1	0	0	0	1	1	1	1
10	1	0	0	1	1	1	0	0
11	1	0	0	1	0	1	0	1

Rozwiązanie

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

Z podanych par {Pi, Pj} tworzymy trójki podejrzane o r = 4

A={x1,x2,x4}, B={x1,x4,x5} C={x2,x3,x4} D={ x3,x4,x5}

$P( A) |P_{F} =P_{1} \cdot P_{2} \cdot P_{4} |P_{F} =\left\{\overline{( 1)( 2)} ;\overline{( 3)( 4)} ;\overline{( 5)( 7)} ;\overline{( 6)( 8)} ;\overline{( 9)} ;\overline{( 10)( 11)}\right\}$ r = 3+1

$P( B) |P_{F} =P_{1} \cdot P_{4} \cdot P_{5} |P_{F} =\left\{\overline{( 1)} ;\overline{( 2)} ;\overline{( 3)} ;\overline{( 4)} ;\overline{( 5,7)} ;\overline{( 6)( 8)( 11)} ;\overline{( 9)} ;\overline{( 10)}\right\}$ r = 3+2

$P( C) |P_{F} =P_{2} \cdot P_{3} \cdot P_{4} |P_{F} =\left\{\overline{( 1,10)( 2,11)} ;\overline{( 3)( 4)( 7)} ;\overline{( 5)} ;\overline{( 6)} ;\overline{( 8)} ;\overline{( 9)}\right\}$ r = 3+2

$P\left(D\right)|P_F=P_3\cdot P_4{\cdot P}_5|P_F=\left\{\overline{\left(1,10\right)};\overline{\left(2,11\right)\left(6\right)};\overline{\left(3\right)\left(7\right)};\overline{\left(4\right)};\overline{\left(5\right)};\overline{\left(8\right)};\overline{\left(9\right)}\right\}$ r = 3+1

Obliczenia dla U = {x1, x2, x4} (rys. 3.7)

$P_{V} =P( x_{3} x_{5}) =\left(\overline{1,9,10} ;\overline{2,5,6,11} ;\overline{3,7,8} ;\overline{4}\right)$

Z podziału ilorazowego $P( A) |P_{F}$ wynika, że warunki dekompozycji będą spełnione, gdy rozdzielimy wektory: 1 od 2, 3 od 4, 5 od 7, 6 od 8 oraz 10 od 11. Uzyskamy to, gdy podział $\Pi_{G_0}$ będzie 2-blokowy (tab. 3.14):

Tablica 3.14

	x₃x₅	g₀
1,9,10	0 1	0
2,5,6,11	0 0	1
3,7,8	1 0	0
4	1 1	1

$P_{V} =P( x_{3} x_{5}) =\left(\overline{1,9,10} ;\overline{2,5,6,11} ;\overline{3,7,8} ;\overline{4}\right)$

1. blok: $\overline{1,9,10}\ \ i\ \ \overline{\ 3,7,8}$

2. blok: $\overline{2,5,6,11}\ i\overline{\ 4}\$

zatem

$\Pi _{G_{0}} =\left(\overline{1,3,7,8,9,10} ;\overline{2,4,5,6,11}\right)$

$\begin{array}{{>{\displaystyle}l}} P_{H} =P(U)\Pi _{G_{0}} =\left(\overline{1,2} ;\overline{3,4} ;\overline{5,7} ;\overline{6,8} ;\overline{9} ;\overline{10,11}\right) \cdot \left(\overline{1,3,7,8,9,10} ;\overline{2,4,5,6,11}\right) =\\ =\left(\overline{1} ;\overline{2} ;\overline{3} ;\overline{4} ;\overline{5} ;\overline{6} ;\overline{7} ;\overline{8} ;\overline{9} ;\overline{10} ;\overline{11}\right) \end{array}$

Uzupelnij opis obrazka

Rys. 3.8. Pierwszy krok dekompozycji

Pierwszy krok dekompozycji przedstawiono w tab. 3.14 i na rys. 3.8.

Sprawdzamy czy istnieje dekompozycja F = H(G₁(x_i, x_j, x_k), G₀).

W tym celu liczymy r-przydatność $\Pi _{G_{0}}$ :

$\Pi _{G_{0}} |P_{F} =\left\{\overline{( 1,10)( 3)( 7)( 8)( 9)} ;\overline{( 2,11)( 4)( 5)( 6)}\right\}$

czyli r = 1+3 = 4, zatem wymagana dekompozycja nie istnieje, gdyż blok G₁ musiałby mieć 3 wyjścia (rys. 3.9). Obliczenia dla U = {x3, x4, x5} są analogiczne. Funkcję H podano w tab. 3.15.

Rys. 3.9. Drugi krok dekompozycji

Tablica 3.15

	x₁x₂x₄g₀	y₁y₂y₃
1	0010	100
2	0011	101
3	0100	011
4	0101	010
5 6	1101 1111	001 000
7 8 9	1100 1110 1000	101 010 111
10 11	1010 1011	100 101

2.4. Dekompozycja nierozłączna

Zauważmy, że r-przydatność k-elementowego zbioru U nie oznacza, że istnieje dekompozycja:

F = H((U,G(V))

w której funkcja G ma r – k wyjść. Sytuacja ta oznacza tylko, że istnieje dekompozycja z funkcją G o argumentach V È W gdzie WÍ U.

Oczywiście w najlepszym przypadku W jest zbiorem pustym, a w najgorszym W = U i wtedy dekompozycja taka nie ma sensu. Można się jednak spodziewać, że sytuacja najlepsza i najgorsza są najmniej prawdopodobne.

Z powyższego wynika, że w praktyce często stajemy przed problemem wyznaczania dekompozycji nierozłącznej. Podstawowym problemem w obliczaniu dekompozycji nierozłącznej jest wyznaczenie zbioru W o możliwie minimalnej liczności. Wybór argumentów do zbioru W jest przeprowadzany na podstawie analizy podziału P_V. Otóż, w przypadku, gdy nie istnieje dekompozycja rozłączna, nie istnieje również Π_G³ P_Vspełniający nierówność P_V ∙Π_G ≤ P_F.

Jest zrozumiałe, że powiększenie zbioru V o argumenty z W Í U prowadzi w konsekwencji do utworzenia „drobniejszego” Π’_G ³ P’_V(gdzie P’_V jest zbiorem indukowanym argumentami V’ = V È W). Drobniejszy Π’_G może zapewnić spełnienie warunku:

P ∙ Π_G’ £ P_F

Sposób postępowania przy wyznaczaniu W wyjaśnimy na przykładzie.

Dla funkcji podanej w tabl. 3.16 poszukujemy dekompozycji, w której U = {x1,x2,x3}, V = {x4,x5}.

Tablica 3.16

	x₁	x₂	x₃	x₄	x₅	y₁	y₂	y₃
1	0	0	0	0	0	0	0	0
2	0	0	0	1	1	0	1	0
3	0	1	0	1	0	1	0	0
4	0	1	1	1	1	0	1	1
5	0	1	1	0	1	0	0	1
6	0	1	0	0	0	0	0	1
7	1	1	0	1	0	0	0	0
8	1	0	0	1	1	1	0	0
9	1	0	0	1	0	0	0	1
10	1	0	1	1	1	0	0	0

Wyznaczamy kolejno:

$\Pi_{G_{0}}=\left(\overline{1,3,7,8,9,10};\overline{2,4,5,6,11}\right)$

$\begin{array}{{>{\displaystyle}l}} P_{H} =P( U) \Pi _{G_{0}} =\left(\overline{1,2} ;\overline{3,4} ;\overline{5,7} ;\overline{6,8} ;\overline{9} ;\overline{10,11}\right) \cdot\left(\overline{1,3,7,8,9,10} ;\overline{2,4,5,6,11}\right) =\\ =\ \left(\overline{1} ;\overline{2} ;\overline{3} ;\overline{4} ;\overline{5} ;\overline{6} ;\overline{7} ;\overline{8} ;\overline{9} ;\overline{10} ;\overline{11}\right) \end{array}$

$P_{F} =\left(\overline{1,7,10} ;\overline{2} ;\overline{3,8} ;\overline{4} ;\overline{5,69}\right)$

$P_{U} =\left(\overline{1,2} ;\overline{3,6} ;\overline{4,5} ;\overline{7} ;\overline{8,9} ;\overline{10}\right)$

$P_{V} =\left(\overline{1,6} ;\overline{2,4,8,10} ;\overline{3,7,9} ;\overline{5}\right)$

Podział P_G konstruujemy w sposób pokazany na rys. 3.10. Niestety nie można spełnić warunków rozdziału z podziału ilorazowego: elementy 8 i 9 są w jednym bloku podziału P_G.

Uzupelnij opis obrazka

Rys. 3.10. Konstrukcja podziału ΠG

Warunki te byłyby spełnione, gdybyśmy przenieśli element 9 do pierwszego bloku (strzałka na rys. 3.9). Byłoby to jednak możliwe, gdyby elementy 3, 7 były oddzielone od elementu 9. Z tablicy 3.17 wynika, że wektory 3 i 9 różnią się na pozycjach x₁ oraz x₂, natomiast wektory 7 i 9 różnią się na pozycji x₂. Zatem zmienna x₂ wystarczy do oddzielenia 3, 7 od 9. Stąd wniosek, że W = {x2}, czyli istnieje dekompozycja nierozłączna. Jej wyznaczenie nie nastręcza trudności, gdyż dla nowego P_V_’ obliczenie odpowiedniego P_G jest już możliwe:

P_V’ = P_V • P₂

_{$P_{V} =\left(\overline{1} ;\overline{6} ;\overline{2,8,10} ;\overline{4} ;\overline{3,7} ;\overline{9} ;\overline{5}\right)$}

_{$\Pi _{G_{0}} =\left(\overline{1,5,6,9} ;\overline{2,3,4,7,8,10}\right)$}

Pojęcie r-przydatności i dekompozycja nierozłączna ułatwiają znajdowanie najlepszych dekompozycji.

Dla funkcji z tablicy 3.17 podziały P₁, P₂, P₅ są 3-przydatne, a P₃, P₄ – 4-przydatne. Należy obliczyć wszystkie dekompozycje szeregowe z najmniejsza liczbą wejść do bloku H oraz najmniejszą liczbą wejść i wyjść bloku G.

Uwaga: wystarczy obliczyć odpowiednie podziały Π_G spełniające warunek wystarczający dekompozycji.

Tablica 3.17

	x₁	x₂	x₃	x₄	x₅	Y
1	0	0	0	0	0	D
2	0	0	0	0	1	A
3	0	0	0	1	0	C
4	1	0	0	1	0	D
5	1	0	0	1	1	B
6	0	0	0	1	1	B
7	0	0	1	0	0	D
8	1	0	1	0	1	B
9	0	0	1	0	1	A
10	0	1	1	0	0	C
11	1	1	1	0	0	E
12	1	1	1	0	1	A

W rozwiązaniu podać też schematy blokowe obliczonych dekompozycji, w szczególności wejścia i wyjścia bloków G i H.

Rozwiązanie:

$P_{F} =\left(\overline{1,4,7} ;\overline{2,9,12} ;\overline{3,10} ;\overline{4,8} ;\overline{5,6,8} ;\overline{11}\right)$
$P_{1} \cdot P_{5} \|P_{F} =\left\{\overline{( 1,7)( 3,10)} ;\overline{( 2,9)( 6)} ;\overline{( 4)( 11)} ;\overline{( 5,8)( 12)}\right\}$	r = 3
$P_{1} \cdot P_{2} \|P_{F} =\left\{\overline{( 1,7)( 2,9)( 3)( 6)} ;\overline{( 5,8)( 4)} ;\overline{( 10)} ;\overline{( 11)( 12)} \ \right\}$	r = 4
$P_{2} \cdot P_{5} \|P_{F} =\left\{\overline{( 1,4,7)( 3)} ;\overline{( 2,9)( 5,6,8)} ;\overline{( 10,11)} ;\overline{( 12)} \ \right\}$	r = 3

Dla U = {x1, x5} (rys. 3.11)

Uzupelnij opis obrazka

Rys. 3.11. Dekompozycja funkcji z przykładu 3.6

$P_{1} \cdot P_{5} |P_{F} =\left\{\overline{( 1,7)( 3,10)} ;\overline{( 2,9)( 6)} ;\overline{( 4)( 11)} ;\overline{( 5,8)( 12)}\right\}$

$P_{V} =P( x_{2} ,x_{3} ,x_{4}) =\left(\overline{1,2} ;\overline{3,4,5,6} ;\overline{7,8,9} ;\overline{10,11,12}\right)$

Tworzenie podziału P_G:

1. blok $\overline{1,2}$ i $\overline{7,8,9}$

2. blok $\overline{3,4,5,6}$ i $\overline{10,11,12}$

Wektory 4, 5 trzeba oddzielić od 3, 6. Stąd dekompozycja nierozłączna z x₁, czyli V’ = x₁ x₂ x₃ x₄

$P_{V\prime } =\left(\overline{1,2} ;\overline{3,6} ;\overline{4,5} ;\overline{7,9} ;\overline{8} ;\overline{10} ;\overline{11,12}\right)$

$\Pi _{G\prime } =\left(\overline{1,2,4,5,7,8,9} ;\overline{3,6,10,11,12}\right)$

$\begin{array}{{>{\displaystyle}l}} P_{H} =P( U) \cdot \Pi _{G\prime } =\left(\overline{1,3,7,10;} ;\overline{2,6,9} ;\overline{4,11} ;\overline{5,8,12}\right) \cdot \left(\overline{1,2,4,5,7,8,9} ;\overline{3,6,10,11,12}\right) =\\ =\left(\overline{1,7} ;\overline{3,10} ;\overline{2,9} ;\overline{6} ;\overline{4} ;\overline{11} ;\overline{5,8} ;\overline{12}\right) \end{array}$

Tablice bloków G i H przedstawiono odpowiednio w tab. 3.18. i tab. 3.19.

Tablica 3.18

	x₁x₂x₃x₄	g
1,2	0 0 0 0	0
3,6	0 0 0 1	1
4,5	1 0 0 1	0
7,9	0 0 1 0	0
8	1 0 1 0	0
10	0 1 1 0	1
11,12	1 1 1 0	1

Tablica 3.19

	x₁x₅g’	Y
1,7	0 0 0	D
2,9	0 1 0	A
3,10	0 0 1	C
4	1 0 0	D
5,8	1 1 0	B
6	0 1 1	B
11	1 0 1	E
12	1 1 1	A

Dla U = {x2, x5} (rys. 3.12):

$P_{2} \cdot P_{5} |P_{F} =\left\{\overline{( 1,4,7)( 3)} ;\overline{( 2,9)( 5,6,8)} ;\overline{( 10)( 11)} ;\overline{( 12)} \ \right\}$

$P_{V} =P( x_{1} ,x_{3} ,x_{4}) =\left(\overline{1,2} ;\overline{3,6} ;\overline{4,5} ;\overline{7,9,10} ;\overline{8,11,12}\right)$

Podział P_G można utworzyć następująco:

Aby zlikwidować konflikt wektor 5 należy oddzielić od wektora 4. Stąd dodatkowo x₅, czyli V’ = {x1, x3, x4, x5}

$P_{V\prime } =\left(\overline{1} ;\overline{2} ;\overline{3} ;\overline{4} ;\overline{5} ;\overline{6} ;\overline{7,10} ;\overline{9} ;\overline{8,12} ;\overline{11}\right)$

$\Pi _{G\prime } =\left(\overline{1,2,4,7,9,10} ;\overline{3,5,6,8,11,12}\right)$

Tablice bloków H i G’ podano odpowiednio w tab. 3.20 i tab. 3.21.

Tablica 3.20

	x₁x₃x₄x₅	g
1	0 0 0 0	0
2	0 0 0 1	0
3	0 0 1 0	1
4	1 0 1 0	0
5	1 0 1 1	1
6	0 0 1 1	1
7,10	0 1 0 0	0
9	0 1 0 1	0
8,12	1 1 0 1	1
11	1 1 0 0	1

Tablica 3.21

	x₂x₅g’	Y
1,7	0 0 0	D
2,9	0 1 0	A
3,10	0 0 1	C
4	1 0 0	D
5,8	1 1 0	B
6	0 1 1	B
11	1 0 1	E
12	1 1 1	A

Dekompozycja nierozłączna, mimo iż zwiększa liczbę wejść do komponentu G, może w rezultacie prowadzić do uzyskania realizacji z mniejszą liczbą komórek logicznych. Sytuację taką omawiamy w poniższym przykładzie.

Dla funkcji F z tab. 3.22a istnieje dekompozycja:

F = H(x₄, x₅, x₆, G₁(x₁, x₂, x₃))

dla której funkcja G₁ jest podana w tablicy 3.22b.

a)									b)
	x₁	x₂	x₃	x₄	x₅	x₆	y₁	y₂			x₁	x₂	x₃	g₁
1	1	0	0	1	0	0	0	0		1	1	1	0	0
2	1	0	1	1	1	0	0	1		2	0	0	1	0
3	1	1	0	1	1	1	0	1		3	1	0	1	1
4	1	0	1	1	0	0	0	0		4	1	0	0	1
5	0	0	1	1	1	0	1	0
6	1	1	0	1	0	0	1	0
7	1	0	0	1	1	1	1	0
8	0	0	1	0	1	1	1	1
9	0	0	1	0	1	0	1	1

Ponieważ $P_U=P\left(g_1\right)=\left(\overline{3,5,6,8,9};\overline{1,2,4,7}\right)$ . jest 3-przydatny, możemy wyznaczyć:

$\Pi_G=\left(\overline{3,7};\overline{2,5};\overline{1,4,6};\overline{8,9}\right)$ ,

który zapewnia realizację funkcji F = H(G₂(x₄, x₅, x₆), G₁(x₁, x₂, x₃)) w strukturze przedstawionej na rys. 3.13.

Uzupelnij opis obrazka

Rys. 3.13.Schemat dekompozycji funkcji

Przy założeniu, że dysponujemy strukturami z komórkami o wymiarach 3/1, do realizacji tej funkcji jest potrzebnych 5 komórek.

Postaramy się znaleźć dekompozycję prowadzącą do oszczędniejszej realizacji. W tym celu obliczymy r-przydatność dla podziałów reprezentujących pary zmiennych: (g₁, x₄), (g₁, x₅), (g₁, x₆).

$P_{V} =\left(\overline{1,6} ;\overline{2,4,8,10} ;\overline{3,7,9} ;\overline{5}\right)$

$P_{U} |P_{F} =\left\{\overline{( 1)( 2)} ;\overline{( 3)( 6)} ;\overline{( 4)( 5)} ;\overline{( 7)} ;\overline{( 8)( 9)} ;\overline{( 10)}\right\}$

U = {<i>g</i><sub>1</sub>,<i>x</i><sub>4</sub>}
$P_{U} =\left(\overline{1,2,4,7} ;\overline{3,5,6} ;\overline{8,9}\right)$
$P_{U} \|P_{F} =\left\{\overline{( 1,4)} ;\overline{( 2)( 7)} ;\overline{( 3)( 5,6)} ;\overline{( 8,9)}\right\}$	r = 4
U = {<i>g</i><sub>1</sub>,<i>x</i><sub>5</sub>}
$P_{U} =\left(\overline{1,4} ;\overline{2,7} ;\overline{3,5,8,9} ;\overline{6}\right)$
$P_{U} \|P_{F} =\left\{\overline{( 1,4)} ;\overline{( 2)( 7)} ;\overline{( 3)( 5)( 8,9)} ;\overline{6}\right\}$	r = 4
U = {<i>g</i><sub>1</sub>,<i>x</i><sub>6</sub>}
$P_{U} =\left(\overline{1,2,4} ;\overline{3,8} ;\overline{5,6,9} ;\overline{7}\right)$
$P_{U} \|P_{F} =\left\{\overline{( 1,4)( 2)} ;\overline{( 3)( 8)} ;\overline{( 5,6)( 9)} ;\overline{7}\right\}$	r = 3

Zatem tylko dla U = {g1,x6} istnieje dekompozycja o strukturze, jak na rys. 3.13, której realizacja wymaga tylko czterech komórek typu 3/1. Obliczenia uzasadniające taką dekompozycję są podane poniżej.

Najpierw wyznaczamy podział P_V:

$P_{U} =\left(\overline{1,4,6} ;\overline{2,3,5,7} ;\overline{8,9}\right)$

$P_{U} |P_{F} =\left\{\overline{( 1)( 2)} ;\overline{( 3)( 6)} ;\overline{( 4,5)} ;\overline{( 7)( 8)( 9)} ;\overline{( 10)}\right\}$

Do wyznaczenia P_G dwa pierwsze bloki podziału P_V przeznaczamy do pierwszego bloku podziału P_G, natomiast trzeci blok P_V przeznaczamy do drugiego bloku P_G (rys. 3.14).

Uzupelnij opis obrazka

Rys. 3.14. Konstrukcja podziału Π_G

Ale tak utworzony P_G jest sprzeczny z warunkami narzuconymi przez podział ilorazowy P_U|P_F, z którego wynika, że mintermy o numerach (5,6) oraz (9) muszą należeć do różnych bloków P_G. Aby tak było, należy element 6 (rys. 3.14) „przenieść” do drugiego bloku. Będzie to możliwe, gdy mintermy 1,4 będą „oddzielone” od mintermu 6. Z tab. 3.22a wynika, że mintermy 1 i 6 różnią się na pozycji x₂, natomiast 4 i 6 różnią się na pozycjach x₂ i x₃. Zatem W = {x2}, czyli V’ = {x2,x4, x5}. Na podstawie nowego P_V_’= P_V×P(x₂):

$P_{V\prime } =\left(\overline{1,4} ;\overline{2,5,7} ;\overline{8,9}\right)$

łatwo wyznaczyć P_G_’:

$\Pi _{G\prime } =\left(\overline{1,4,8,9} ;\overline{2,3,6,7}\right)$

spełniający warunek P_U×P_G_’ ≤ P_F, co uzasadnia schemat blokowy dekompozycji pokazany na rys. 3.13.

3. Dekompozycja funkcjonalna – model ogólny

Niech X = {x1,...,xn} będzie zbiorem zmiennych wejściowych funkcji F(x₁,...,x_n) specyfikowanej zbiorem kostek typu fr. Niech U i V będą dwoma rozłącznymi podzbiorami zbioru X takimi, że U È V = X.

Załóżmy, że zbiór zmiennych x₁,...,x_n został w odpowiedniej tablicy funkcji przenumerowany w taki sposób, że U = {x1,...,xr} oraz V = {xr + 1,...,xn}. Niech dla dowolnej n-krotki x, pierwsze r składowe będą oznaczone przez x^U, a ostatnie s = n – r składowe, przez x^V.

Niech F będzie funkcją fr posiadającą n > 0 wejść oraz m > 0 wyjść, w której para (U,V) jest określona jak wyżej. Załóżmy, że F jest specyfikowana zbiorem kostek K. Niech G będzie funkcją fr o s = n – r wejściach i p wyjściach oraz H będzie funkcją fr o r + p wejściach i m > 0 wyjściach.

Parę (G,H) nazywamy dekompozycją szeregową rozłączną funkcji F (rys. 3.15) ze względu na (U,V), jeśli, dla każdego mintermu b odpowiedniego do K, G(b^V), jest zdefiniowana a ponadto G(b^V) Î {0,1}^p oraz F(b) Ê H(b^U,G(b^V)}.

Uzupelnij opis obrazka

3.15. Dekompozycja szeregowa – model ogólny

Funkcja F typu fr określona zbiorem kostek K ma dekompozycję szeregową rozłączną ze względu na (U,V) wtedy i tylko wtedy, gdy istnieje nakrycie b_G na K takie, że:

b_V £ b_G oraz

b_U · b_G £ b_F,

gdzie b_U i b_V są nakryciami indukowanymi przez U i V oraz b_F jest nakryciem wyjściowym.

Analogiczne twierdzenie obowiązuje również w przypadku, gdy nakrycia b zostaną zastąpione systemami zbiorów s.

Funkcja F typu fr określona zbiorem kostek K ma dekompozycję szeregową rozłączną ze względu na (U,V) wtedy i tylko wtedy, gdy istnieje system zbiorów s_G na K taki, że:

s_V £ s_G oraz

s_U · s_G £ s_F,

gdzie: s_U = maxb_U oraz s_V = maxb_V są systemami zbiorów indukowanymi przez U i V oraz s_F= maxb_F jest odpowiednim systemem wyjściowym.

Jak wynika z powyższych twierdzeń głównym zadaniem w obliczeniu dekompozycji funkcji F przy danych zbiorach U i V jest znalezienie nakrycia b_G, które spełnia warunki twierdzenia 3.4. Podział ten nie tylko weryfikuje istnienie dekompozycji, ale również pozwala na wyznaczenie tablic fr dla funkcji G i H. Wynika to z faktu, że nakrycia b_V i b_G oraz b_U · b_G i b_F umożliwiają skonstruowanie odpowiednio tablic funkcji G i H. Konstrukcję tych tablic, a także metody obliczania b_G omówimy dokładnie w dalszej części rozdziału. Na razie zajmiemy się podstawowymi zasadami tych obliczeń.

Skoro b_G musi być konstruowany przez sklejanie bloków nakrycia b_V, to dwa bloki B_i i B_j nakrycia b_V są zgodne, jeśli nakrycie g_ij uzyskane z b_V przez sklejenie B_i i B_j do jednego bloku i pozostawienie wszystkich pozostałych bloków bez zmiany, spełnia drugi warunek twierdzenia 3.4, czyli b_U · g_ij £ b_F. W przeciwnym przypadku bloki B_i i B_j są niezgodne.

Podzbiór d bloków nakrycia b_V jest klasą zgodną, jeśli bloki w zbiorze d są parami zgodne. Klasa zgodna jest klasą maksymalną, jeśli nie jest podzbiorem żadnej innej klasy zgodnej. Maksymalne klasy zgodne umożliwiają konstrukcję b_G. Bloki nakrycia b_G powstają z klas zgodności tworzących minimalne pokrycie zbioru wszystkich bloków b_V. Wyselekcjonowane według minimalnego pokrycia klasy zgodne są następnie redukowane o bloki powtarzające się i przyjmowane jako bloki nakrycia b_G (lub s_G), po podstawieniu pierwotnych elementów w postaci numerów kostek funkcji F .

Dla funkcji F z tablicy 3.23 i zbiorów U = {x1} i V = {x2,x3,x4} nakrycia b_U, b_V są następujące:

$\beta _{V} =\left\{\overline{1,2,3} ;\overline{3,7} ;\overline{6,7} ;\overline{5} ;\overline{4,6} ;\overline{1,2} ;\overline{4}\right\}$

Tablica 3.23

Uwzględniając, że $\sigma _{F} =\left\{\overline{4,5} ;\overline{4,6} ;\overline{2,3,7} ;\overline{1,3,6,7}\right\}$ możemy obliczyć, iż sklejenie bloków B₁ i B₂ prowadzi do g₁₂ = {1,2,3,7}, co po obliczeniu $\beta _{U} \cdot \gamma _{12} =\left\{\overline{1,3,7} ;\overline{2,3}\right\}$ pozwala wnioskować, że b_U · g₁₂ £ s_F, zatem (B₁, B₂) jest parą zgodną. Inaczej jest z parą (B₁, B₃), dla której g₁₃ = {1,2,3,6,7}, stąd, $\beta _{U} \cdot \gamma _{13} =\left\{\overline{1,3,6,7} ;\overline{2,3,6}\right\} \nleq \sigma _{F}$ . (B₁, B₃) jest więc parą niezgodną. W rezultacie wszystkie pary zgodne są następujące: (B₁, B₂), (B₁, B₆), (B₂, B₃), (B₂, B₆), (B₄, B₇) i (B₅, B₇). Łatwo więc wyznaczyć maksymalne klasy zgodne: {B1, B2, B6},{B2, B3}, {B4, B7} i {B5,B7}. Minimalne pokrycie zbioru {B1,..., B7} podanymi wyżej klasami prowadzi do rozwiązania: {B1, B2, B6},{B4}, {B3} i {B5,B7}. Na tej podstawie nakrycie $\beta _{G} =\left\{\overline{1,2,3,7} ;\overline{5} ;\overline{6,7} ;\overline{4,6}\right\}$ (po uwzględnieniu pierwotnych numerów kostek z bloków b_V). Łatwo sprawdzić, że b_V £ b_G, ponadto $\beta _{U} =\left\{\overline{1,3,4,5,6,7} ;\overline{2,3,4,5,6}\right\}$ , $\beta _{F} =\left\{\overline{4,5} ;\overline{4,6} ;\overline{2,3,7} ;\overline{1,3,6,7}\right\}$ , czyli:

$\beta _{U} \cdot \beta _{G} =\left\{\overline{1,3,7} ;\overline{2,3} ;\overline{5} ;\overline{6,7} ;\overline{6} ;\overline{4,6}\right\} \leq \beta _{F}$

Warunki twierdzenia 3.4 są więc spełnione i odpowiednia dekompozycja istnieje. Należy więc wyznaczyć tablice opisujące funkcje G i H.

W tym celu będziemy analizowali b_V £ b_G, oraz b_U · b_G i b_F. Tablica funkcji G powstaje w następujący sposób. Dla każdego bloku B nakrycia b_V tworzymy kostkę, której poszczególne pozycje reprezentują wartości zmiennych wejściowych funkcji G. Wartości te dla zmiennej x_i są wyznaczane w zależności od przynależności bloku B do bloku nakrycia b_i. Z kolei wartość funkcji G dla obliczonej w ten sposób kostki wynika z przynależności bloku B do bloku b_G.

Dla funkcji F z przykładu 3.8 otrzymana w ten sposób tablica podana jest w tablicy 3.24a.

Tablica 3.24

a)						b)
Blok	x₂	x₃	x₄	g₁	g₂	Blok	x₁	g₁	g₂	y₁	y₂
1,2,3	0	0	0	0	0	1,3,7	0	0	0	1	1
3,7	0	0	1	0	0	2,3	1	0	0	1	0
6,7	1	0	1	1	0	5	*	0	1	0	0
5	1	1	0	0	1	6,7	0	1	0	1	1
4,6	1	1	1	1	1	6	*	1	*	–	1
1,2	0	*	0	0	0	4,6	*	1	1	0	1
4	*	1	1	1	1

W analogiczny sposób tworzymy tablicę funkcji H. Każdemu blokowi B z iloczynu:

$\beta _{U} \cdot \beta _{G} =\left\{\overline{1,3,7} ;\overline{2,3} ;\overline{5} ;\overline{6,7} ;\overline{6} ;\overline{4,6}\right\} \leq \beta _{F}$

przyporządkowujemy kostkę o składowych x₁,g₁, g₂, przy czym wartości tych składowych wynikają z przynależności bloku B do bloków nakrycia b₁ oraz b_G. Należy więc określić kodowanie bloków
$\beta _{G} =\left\{\overline{1,2,3,7} ;\overline{5} ;\overline{6,7} ;\overline{4,6}\right\}$ , które tu przyjmujemy następująco: 00 dla {1,2,3,7}, 01 dla {5}, 10 dla {6,7} oraz 11 dla {4,6}. Wartości funkcji H wynikają z przynależności bloków B do poszczególnych bloków z s_F. Przypomnijmy, że bloki s_F (por. przykład 3.8) są kodowane następująco: 4,5, jako 00; 4,6 jako 01; 2,3,7 jako 10 oraz 1,3,6,7 jako 11. W rezultacie tablica H jest taka, jak w tablicy 3.24b.

Obliczenia tablic funkcji G i H w przykładzie 3.8, jak też obliczenie b_G w przykładzie 3.9 są proste i nie wymagają stosowania wszystkich, potrzebnych do tego celu procedur. W bardziej skomplikowanych przypadkach obliczenia te wymagają stosowania dodatkowych procedur, których rolę wyjaśnimy poniżej.

Przy konstrukcji tablicy funkcji G pierwszą czynnością jest wyznaczanie kostki C odpowiadającej blokowi B z nakrycia b_G oraz wartości funkcji G dla tej kostki, tj. G(C). Kostkę C_i kojarzoną z B_i nazywać będziemy reprezentantem bloku B_i. W ogólnym przypadku może się zdarzyć, że dla dwóch różnych B_i, B_j, kostki C_i, C_j będą miały niepuste przecięcie, a jednocześnie odpowiadające im wartości funkcji G będą różne:

C_i Ç C_j ¹ f, G(C_i) ¹ G(C_j)

Jest to sytuacja niedopuszczalna z punktu widzenia niesprzeczności tablicy specyfikującej funkcję.

Celem niedopuszczenia do takich sprzeczności należy odpowiednio modyfikować kostki reprezentujące bloki B Î b_V. Niech C = r(B) oraz niech B₁, ..., B_k oznaczają bloki z b_V, dla których:

B Ì B₁, G(C₁) ¹ G(C)

B Ì B₂, G(C₂) ¹ G(C)

·

B Ì B_k, G(C_k) ¹ G(C)

gdzie: C, C₁, ..., C_k są reprezentantami bloków B, B₁,..., B_k.

W takiej sytuacji sprzeczność w tablicy funkcji G usuniemy zastępując kostkę C kostką (lub kostkami) obliczonymi jako różnica: C – {C1,..., Ck}. Różnicę taką najwygodniej jest obliczyć jako przecięcie C z uzupełnieniem {C1,..., Ck}, czyli kostka zmodyfikowana:

C’ = C Ç {C1,..., Ck}.

Rozważmy dekompozycję funkcji F z tablicy 3.25 dla U = {x1,x2} i V = = {x3,x4,x5,x6}. Odpowiednie nakrycie b_V jest tu następujące:

$\beta _{V} =\overset{}{\{}\overset{B_{1}}{\overline{7,8}} ;\overset{B_{2}}{\overline{3,4,8}} ;\overset{B_{3}}{\overline{8}} ;\overset{B_{4}}{\overline{4,8}} ;\overset{B_{5}}{\overline{1,5,8}} ;\overset{B_{6}}{\overline{3,5,8}} ;\overset{B_{7}}{\overline{6,8}} ;\overset{B_{8}}{\overline{1,2,5,8}} ;\}$

Tablica 3.25

	x₁	x₂	x₃	x₄	x₅	x₆	y₁	y₂	y₃
1	*	0	1	*	0	0	1	–	–
2	0	*	1	1	0	0	1	–	–
3	1	*	*	*	0	1	–	1	–
4	0	*	0	*	*	1	–	1	–
5	1	*	1	*	0	*	–	–	1
6	*	*	1	0	1	*	0	0	0
7	*	*	0	*	0	0	–	–	0
8	1	1	*	*	*	*	0	–	–

Łatwo sprawdzić, że nakrycie:

$\sigma _{G} =\underset{}{\{}\overset{00}{\overline{3,4,7,8}} ;\ \overset{01}{\overline{3,5,8}} ;\ \overset{10}{\overline{6,8}} ;\overset{11}{\overline{\ 1,2,5,8}}\}$

spełnia warunki twierdzenia 3.4, zatem dekompozycja istnieje.

Dla kolejnych bloków b_V, ich reprezentantów obliczamy albo wg zawartości tych bloków w blokach nakryć b_i albo bezpośrednio z tablicy 3.25, korzystając z faktu, że reprezentant bloku B jest iloczynem kostek zawartych w B. Na przykład dla B₁ = {7,8}, B₂ = {3,4,8}, B₃ = {8},

C₁= r(B₁) = 0*00 Ç **** = 0*00

C₂= r(B₂) = **01 Ç 0**1 Ç **** = 0*01

C₃= r(B₃) = ****

C₄= r(B₃) = 0**1

Pełna tablica reprezentantów podana jest w tabl. 3.26.

Tablica 3.26

Blok b_V	Reprezentant	Wyjścia
B₁	0 * 0 0	0 0
B₂	0 * 0 1	0 0
B₃	* * * *	0 0
B₄	0 * * 1	0 0
B₅	1 * 0 0	1 1
B₆	1 * 0 1	0 1
B₇	1 0 1 *	1 0
B₈	1 1 0 0	1 1

Skoro B₁ Í {3,4,7,8}, któremu w b_G został przyporządkowany kod 00, to G(0*00) = 00. Podobnie dla B₂ Í {3,4,7,8} mamy G(0*01) = 00. Zatem przyjmując, że G(C₃) = 00 (B₃ Í {3,4,7,8}, można więc jako wartość G dla kostki C₃ przyjąć kod bloku {3,4,7,8}), konflikt znajdujemy dla kostek reprezentujących bloki B₅, B₆, B₇, B₈, stąd następująca modyfikacja C₃:

{(****)} – {1*00, 1*01, 101*, 1100} = COMPLEMENT{1*00, 1*01, 101*, 1100} = {0***, *11*}.

Omawiana wyżej dekompozycja, w której zbiory U i V są rozłączne, jest przypadkiem szczególnym dekompozycji, dla której założenie U Ç V = f jest nieistotne. Istotne jest jedynie założenie dotyczące sensownej liczby wejść do poszczególnych komponentów.

Niech U i V będą podzbiorami X takimi, że U È V = X. Załóżmy, że zmienne x₁,...,x_n są uporządkowane w taki sposób, iż U = {x1,...,xr} i V = {xn–s+1,...,xn}.

Niech F będzie funkcją o n > 0 wejściach i m > 0 wyjściach, i niech (U,V) będzie określone jak wyżej. Zakładamy też, że F jest specyfikowana zbiorem kostek K. Niech G będzie funkcją o s wejściach i p wyjściach, natomiast H funkcją fr o r + p wejściach i m wyjściach. Parę (G,H) nazywamy dekompozycją funkcji F ze względu na (U,V), jeśli dla każdego mintermu b odpowiedniego do K, G(b^V) Î {0,1}^p oraz

F(b) Ê H(b^U, G(b^V)).

Jeśli istnieje nakrycie b_G na K takie, że:

b_V £ b_G, oraz

b_U · b_G £ b_F,

to F ma dekompozycję szeregową ze względu na (U,V).

Dla funkcji z tablicy 3.23 rozważmy dekompozycję nierozłączną ze zbiorami:

U = {x1,x4} i V = {x2, x3, x4}. Mamy tu:

$\beta _{U} =\left\{\overline{1,3,5} ;\overline{3,4,6,7} ;\overline{2,3,5} ;\overline{3,4,6} ;\right\}$

$\beta _{V} =\left\{\overline{1,2,3} ;\overline{3,7} ;\overline{1,2} ;\overline{4} ;\overline{6,7} ;\overline{5} ;\overline{4,6}\right\}$

Do obliczenia b_G zastosujemy algorytm wyznaczania klas zgodnych wg par niezgodności: (B₁, B₄), (B₁, B₆), (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₂B₅B₆+ B₁B₂B₃B₄B₇+ B₄B₆B₇.

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

{B1,..., B7} - {B1, B2, B3, B5 }= {B4, B6, B7}

{B1,...,B7} - {B1, B2 , B5 , B6 } = {B3, B4, B7}

{B1,...,B7} - {B1, B2, B3, B4 , B7} = {B5 , B6}

{B1,...,B7} - {B4, B6, B7} = {B1, B2, B3, B5 }

Z powyższych klas bloków zgodnych można wyselekcjonować dwie: {B1, B2, B3, B5} oraz {B4, B6, B7}, pokrywające zbiór {B1,..., B7}, czyli $\beta _{G} =\left\{\overline{B_{1} ,B_{2} ,B_{3} B_{5}} ;\overline{B_{4} ,B_{6} ,B_{7}}\right\}$ . W tym przypadku rozwiązanie jest trywialne. Wracając do pierwotnych kostek tworzących poszczególne bloki B_i otrzymujemy:

$\beta _{G} =\overset{}{\{}\overset{0}{\underset{}{\overline{1,2,3,6,7}}} ;\overset{1}{\overline{4,5,6}}\}$ ,

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

Identyczny wynik uzyskamy obliczając klasy zgodne algorytmem korzystającym z par zgodnych. Następujące pary są zgodne: (B₁, B₂), (B₁, B₃), (B₁, B₅), (B₂, B₃), (B₂, B₅), (B₃, B₄), (B₃, B₅), (B₃, B₇), (B₄, B₆), (B₄, B₇), (B₅, B₆), (B₆, B₇). Na tej podstawie wyznaczamy zbiory S_j i tworzymy kolejne listy (rodziny RKZ_k) klas zgodnych (porównaj algorytm z rozdz. 1), które dla uproszczenia zapisów podawać będziemy w postaci zbiorów indeksów:

S₁ = f	{1}
S₂= {1}	{1, 2}
S₃= {1, 2}	{1, 2, 3}
S₄= {3}	{3, 4}, {1, 2, 3}
S₅= {1, 2, 3}	~~{3, 5}~~, {1, 2, 3, 5}, {3, 4}
S₆= {4, 5}	{5, 6}, {4, 6}, {1, 2, 3, 5}, {3, 4}
S₇= {3, 4, 6}	~~{6, 7}~~, {4, 6, 7}, ~~{3, 7}~~, {3, 4, 7}, {5, 6}, {1, 2, 3, 5}

W obliczeniach powyższych przekreśleniem zaznaczyliśmy zbiory, które są usuwane na mocy definicji maksymalnych klas zgodnych. Dysponując nakryciem b_G, łatwo już wyznaczyć tablice funkcji G i H. Podane są one odpowiednio w tablicach 3.27a i 3.27b.

Tablica 3.27

a)				b)
x₂	x₃	x₄	g	x₁	x₄	g	y₁	y₂
0	0	0	0	0	0	0	1	1
0	0	1	0	*	0	1	0	0
0	*	0	0	0	1	0	1	1
*	1	1	1	*	1	1	0	1
1	0	1	0	1	0	0	1	0
1	1	0	1	*	1	0	1	1
1	1	1	1

W wielu przypadkach dekompozycja szeregowa z przecinającymi się zbiorami U i V – zwana często dekompozycją nierozłączną – jest pożyteczna. Załóżmy realizację funkcji z powyższego przykładu na komórkach FPGA o strukturze: 3 wejścia, 1 wyjście. Obliczona dekompozycja nierozłączna (rys. 3.16a) wymaga do całkowitej realizacji tej zdekomponowanej funkcji 3 komórek: jedną do funkcji G i dwie do funkcji H (po jednej na każde wyjście). Dekompozycja rozłączna o strukturze H(x₁,x₂,G(x₃,x₄)), również wymagałaby do swojej realizacji 3 komórek; niestety, taka dekompozycja nie istnieje. Istnieje natomiast dekompozycja rozłączna H(x₁,G(x₂,x₃,x₄)) – rys. 3.16b, w której funkcja G ma 2 wyjścia, i dla tego jej realizacja wymaga aż 4 komórek (dwóch dla funkcji G i dwóch dla H).

Uzupelnij opis obrazka

Rys. 3.16. Dekompozycja szeregowa: a) nierozłączna; b) rozłączna

4. Dekompozycja liniowa

Dekompozycja liniowa polega na łączeniu zmiennych w pary i wprowadzaniu ich za pośrednictwem bramek EXOR do głównego układu realizującego detekcję i klasyfikację (czyli indeksowanie) danych. Jest to istotne, gdyż prowadzi do dalszego redukowania liczby wejść w generatorach indeksu. I pewnie z tych powodów dekompozycja liniowa jest intensywnie wykorzystywana w syntezie funkcji generowania indeksów [3.20].

W dotychczasowych rozwiązaniach problem dekompozycji liniowej ogranicza się do syntezy silnie nieokreślonych funkcji boolowskich, o specyficznej własności: |Dⁿ| = k. Ograniczenie tego problemu do funkcji, w których wszystkie wektory wyjściowe są różne, jest niepotrzebne, gdyż problem ten można sprowadzić do ogólniejszego zadania syntezy systemów funkcji boolowskich o dowolnych wyjściach. Inaczej mówiąc lepiej przyjąć założenie, że liczność zbioru wektorów wyjściowych Y funkcji F jest ≤ |Dⁿ|.

Ogólnie rzecz biorąc problem można sprowadzić do wskazania warunków jakie muszą być spełnione, aby funkcja F posiadała dekompozycję z dwu-argumentowymi funkcjami G.

F = H(G₁(X₁), G₂(X₂),..., x_n),

gdzie: $X_1=\left\{x_{i_1},x_{i_2}\right\}$ , $X_2=\left\{x_{i_3},x_{i_4}\right\}$ ,

Funkcję G nazywać można g-argumentem, stosownie do ogólnej teorii dekompozycji funkcji boolowskich. Przyjmujemy również założenie, że w dekompozycji liniowej stosujemy funkcje o zredukowanej liczbie argumentów, czyli tzw. minimalno-argumentowe reprezentacje funkcji F.

Przy tak postawionym zagadnieniu wygodne jest stosowanie uporządkowanego i zwartego sposobu reprezentowania funkcji, jakim jest rachunek podziałów. Szczegóły dotyczące tego sposobu przedstawiana funkcji zostały już omówione w rozdz. 1.4 i nie będą tu dyskutowane. Niezbędne jest jednak krótkie przypomnienie, gdyż własności podziałów będą wykorzystywane do skonstruowania metody syntezy układów bramkowych, omawianej w dalszej części artykułu.

Rozpatrzmy funkcję logiczną zdefiniowaną w tab. 3.28, w której symbole T: 1,2,...,11 reprezentują wektory, x₁,...,x₅ reprezentują zmienne wejściowe, zaś y – zmienną wyjściową.

Tablica 3.28

T	x₁	x₂	x₃	x₄	x₅	y
1	0	0	0	0	0	0
2	0	0	1	1	1	0
3	0	1	0	1	0	0
4	0	1	1	1	1	0
5	0	1	1	0	0	0
6	0	0	0	1	1	1
7	0	1	0	0	0	1
8	0	1	1	0	1	1
9	1	1	0	1	0	1
10	1	0	0	1	1	1
11	1	0	0	1	0	1

Dla tego przykładu, różne wartości, przyjmowane przez zmienną wejściową x₄, wyznaczają podzbiory wektorów {1,5,7,8} i {2,3,4,6,9,10,11}. Dla wektorów 1,5,7 i 8, x₄ = 0, dla 2,3,4,6,9,10,11, x₄ = 1. Zatem wiedząc, że x₄ = 0, wiemy, że wybrany został wektor 1,5,7 lub 8, nie wiemy jednak który z nich. Analogicznie wiedząc, że x₃ = 1 wiemy, że wybrano symbol 2,4,5 lub 8, nie jesteśmy jednak wstanie wskazać, który z nich konkretnie. W ten sposób informacja modelowana jest przez podziały, pokrycia i systemy zbiorów.

Dla funkcji z tab, 3.29 podziały wejściowe i wyjściowy są następujące

$P\left(x_1\right)=\left\{\overline{1,2,3,4,5,6,7,8};\overline{9,10,11}\right\}$ ,
$P\left(x_2\right)=\left\{\overline{1,2,6,10,11};\overline{3,4,5,7,8,9}\right\}$ ,

$P\left(x_3\right)=\left\{\overline{1,3,6,7,9,10,11};\overline{2,4,5,8}\right\}$ ,
$P\left(x_4\right)=\left\{\overline{1,5,7,8};\overline{2,3,4,6,9,10,11}\right\}$ ,
$P\left(x_5\right)=\left\{\overline{1,3,5,7,9,11};\overline{2,4,6,8,10}\right\}$ ,
$P_F=\left\{\overline{1,\ldots,5};\overline{6,\ldots,11}\right\}$ ,

W celu uproszczenia zapisów wektory a,b Î{0,1}ⁿ : F(a) ≠ F(b), będą reprezentowane liczbami p,q Î K = {1,..., | Dn |}.

Niech F będzie wielowyjściową funkcją boolowską, gdzie zbiór zmiennych X = (x₁,…, x_n)_, zbiór wektorów (mintermów) M = (m₁,…, m_t)_.Przez C_pq, gdzie p, q są wektorami z M, dla których F(p) ¹ F(q) oznaczamy zbiór niezgodności, definiowany jak następuje:

C_pq = {x Î X : x(p) ¹ x(q)} dla p,q = 1,…,t and p < q}. (3-3)

Rodzinę zbiorów C = (C₁,…, C_n_), dla wszystkich C_pq oznaczać będziemy RC_pq. W obliczeniach par zmiennych tworzących dekompozycję liniową posługiwać się będziemy rodziną zbiorów C_pq.

Problem wyznaczenia odpowiednich warunków, oparty jest na pojęciu funkcji rozdzielającej. O funkcji g będziemy mówić, że jest funkcją rozdzielająca (dystrybucją) pary wektorów p,q wtedy i tylko wtedy, gdy p i q należą do różnych bloków podziału P(g). W uproszczeniu można powiedzieć, że w takim przypadku funkcja g umożliwia rozdzielenie wektorów p i q.

Z przyjętej definicji wynika, że każda jednoargumentowa funkcja g(x_j) = x_j, gdzie x_j Î C_pq jest dystrybucją p, q. Ponadto jeśli g rozdziela parę p, q, to również parę tę rozdziela funkcja g .

Wykorzystując powyższe ustalenia można teraz warunkowi dekompozycji nadać wygodniejszą postać: F = H(g₁, g₂,..., g_t) wtedy i tylko wtedy, gdy dla każdej pary p, q: takiej, że (p,q) nie jest zawarta w jednym bloku podziału charakterystycznego P_Fistnieje g_j rozdzielająca parę p, q. Zalety tego warunku zostaną obecnie wykorzystane do sformułowania metodyki syntezy układów w których argumenty z X = (x₁,…, x_n)łączone będą w pary i wprowadzane do układu H za pośrednictwem funktorów g(x_i, x_j) tzn. F = H(g₁, g₂,…, g_t, x_a, x_b…).

Wykorzystując powyższe ustalenia można zaproponować sposób prowadzenia syntezy logicznej jako dekompozycję bezpośrednio na bramki, w odróżnieniu od dekompozycji funkcjonalnej, w której składowe są funkcjami opisanymi tablicami prawdy. Możliwe jest obliczenie podziału P(g) dla dowolnej funkcji o skończonej liczbie zmiennych wejściowych i w następnym kroku usunięcie wszystkich zbiorów C_pq,dla których g nie jest dystrybucją. Obliczamy w ten sposób dekompozycję funkcji F i zapisujemy ją w postaci:

$F=H\left(G\left(x_{i_1},\ldots,x_{i_t}\right),\ldots,x_{i_n}\right)$

Liczba argumentów funkcji H wynosi w tym przypadku co najwyżej n – 1, w związku z czym proces prowadzi do zmniejszenia złożoności funkcji.

Funkcja

$g\ =x_{i} \ \oplus \ x_{j}$ jest funkcją rozdzielającą (dystrybucją) parę (p, q) wtedy i tylko wtedy gdy {xi, xj} Ï C_pq

$\left|\left\{x_i,x_j\right\}\right|\cap\ C_{pq}=1$

Powyższe twierdzenie prowadzi do prostej metody dekomponowania funkcji i wyznaczania g = g(x_i, x_j) bezpośrednio ze zbiorów C_pq i podziałów P(x_i), np. podziałów generowanych przez funkcję jednoargumentową g(x_i) = x_i.

$G=x_{i} \ \oplus \ x_{j}$ jest dekompozycją funkcji F, wtedy i tylko wtedy, gdy {xi, xj} Ï RC_pq, gdzie RC_pq jest rodziną zbiorów C_pq, dla których p oraz q należą do różnych bloków podziału wyjściowego P_F.

Dla funkcji F z tabeli 3.28 rodzinę RC_pq ograniczoną do zbiorów dwuelementowych zapisano w tabeli 3.29. Łatwo zauważyć, że RC_pq nie zawiera 3 następujących par: x₁, x₅; x₃, x₄; x₃, x₅.
Łatwo zauważyć, że RC_pq nie zawiera 3 następujących par: x₁, x₅; x₃, x₄; x₃, x₅.
Tablica 3.29

p,q	C_pq
1,6	x₄,x₅
1,11	x₁,x₄
2,8	x₂,x₄
2,10	x₁,x₃
3,6	x₂,x₅
3,11	x₁,x₂
4,6	x₂,x₃

Stąd wniosek, że możliwe są g-argumenty reprezentowane przez dekompozycje funkcji F:

F = H(x₁Å x₅, x₂, x₃,x₄); F= H(x₃Å x₄, x₁, x₂,x₅); F= H(x₃ Å x₅, x₁, x₂,x₄).

Proces obliczania dekompozycji liniowej może być wykonywany iteracyjnie, aż do uzyskania dekompozycji F = H(g₁, g₂,…, X) z maksymalną liczbą funkcji G, co zapewnia minimalna liczbę argumentów dla funkcji H, oczywiście łącznie z g-argumentami typu EXOR.

Twierdzenie 3.7 i test 3.1 można uogólnić na przypadek tzw. dekompozycji wielokrotnej. Wtedy dodatkowym warunkiem na istnienie dekompozycji z parą funkcji {xi Å xj , xk Å xl}, jest sprawdzenie czy zbiór zmiennych {xi, xj, xk, xl} jest zawarty w rodzinie RC_pq.

Dla uproszczenia zapisów uzupełnienie RC_pq względem rodziny wszystkich podzbiorów o liczności równej liczności analizowanych C_pq oznaczać będziemy COM(RC_pq).

Dla funkcji z przykładu 3.12 w celu sprawdzenia, które g-argumenty mogą tworzyć dekompozycję wielokrotną (w tym przypadku podwójną), należy obliczyć czteroelementowe zbiory RC_pq. W wyniku uzyskujemy, że wszystkie cztero-elementowe zbiory RC_pq są: {x2 x3 x4 x5}_, {x1 x2 x3 x5}_, {x1 x2 x3 x4}. Zatem uzupełnienie COM(RC_pq) zawiera dwa zbiory {{x1 x2 x4 x5}_,{ x1 x3 x4 x5}} i jeden z nich reprezentuje zmienne g-argumentów x₁Å x₅, x₃Å x₄. Na tej podstawie stwierdzamy, że funkcja z przykładu 3.12 ma dekompozycję: F = H(x₁Å x₅, x₃Å x_4,x₂).

Inne uogólnienie Twierdzenia 3.7 dotyczy dekompozycji nierozłącznej. W tym przypadku dodatkowy warunek na istnienie dekompozycji z parą funkcji {xi Å xj , xj Å xk} polega na sprawdzeniu, czy zbiór zmiennych {xi, xj, xk} jest zawarty w rodzinie RC_pq.

Omówioną metodykę obliczania dekompozycji liniowej skonfrontujemy teraz z algorytmem zaproponowanym w [3.20]. Obliczenia przeprowadzimy dla funkcji reprezentującej koder 1 z 10 – tab. 3.30.

Tablica 3.30

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	y₁	y₂	y₃	y₄	y₅	y₆
1	1	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
2	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	0	0	0	0	0	0	0	0	1	1	0	0	0
4	0	0	0	1	0	0	0	0	0	0	0	0	0	1	1	0
5	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1
6	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1
7	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0
8	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0
9	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0
10	0	0	0	0	0	0	0	0	0	1	0	0	0	0	1	0

Dla funkcji tej w [3.20] obliczono dekompozycję liniową z 6 g-argumentami, które w tab. 3.30 oznaczono y₁,…, y₆:

F = H(x₁Åx_6, x₃Åx_7,x₃ Åx_9, x₄Åx₈, x₄ Åx_10, x₅Åx₆)

Obliczenia wykonano za pomocą heurystycznego algorytmu s-min. Ponieważ w uzyskanym rozwiązaniu nie ma zmiennej x₂, wygodnie będzie wprowadzić nowe oznaczenia zmiennych, zgodnie z tabelą 3.31.

Tablica 3.31

x₁	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀
a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉

Przy tych oznaczeniach uzyskuje się nowa tablicę kodera podaną w tabeli 3.32, jak też nowe wyrażenie na uzyskaną w [3.20] dekompozycję

F = H(a₁Åa_5, a₂Åa_6,a₂ Åa_8, a₃Åa₇, a₃ Åa_9, a₄Åa₅)

Tablica 3.32

	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉
1	1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0	0
4	0	0	1	0	0	0	0	0	0
5	0	0	0	1	0	0	0	0	0
6	0	0	0	0	1	0	0	0	0
7	0	0	0	0	0	1	0	0	0
8	0	0	0	0	0	0	1	0	0
9	0	0	0	0	0	0	0	1	0
10	0	0	0	0	0	0	0	0	1

Dla uproszczonego wg tabeli 3.32 kodera 1 z 10 obliczamy rodzinę RC_pq, a następnie COM(RC_pq). W wyniku uzyskujemy: uzupełnienie rodziny RC_pq ma pusty zbiór par, ale zawiera wszystkie możliwe (84) podzbiory trój-elementowe zbioru {a1, a2, a3, a4, a5, a6, a7, a8, a9}. Stąd wniosek, że dla kodera 1 z 10 istnieje dekompozycja nierozłączna wielokrotna reprezentowana trójelementowymi podzbiorami zbioru {a1, a2, a3, a4, a5, a6, a7, a8, a9}, czyli

F = H(a_iÅa_j_,a_jÅa_k_,a_lÅa_m_,a_mÅa_n_,a_pÅa_q_,a_qÅa_r) (3-4)

Tym samym potwierdza to istnienie dekompozycji:

F = H(a₁Åa_5, a₂Åa_6,a₂ Åa_8, a₃Åa₇, a₃ Åa_9, a₄Åa₅)

uzyskanej w [3.20], przy czym należy podkreślić, że dekompozycja taka istnieje dla wszystkich możliwych trójek:

a_i a_ja_k,

a_l a_ma_n,

a_p a_q a_r

Zatem przy zastosowaniu metody z [3.20] znalezienie jakiegokolwiek rozwiązania nie było trudne.

Wykazana własność dekompozycji (wg (3-4)) pozwala zapisać dekompozycję kodera 1 z 10 w naturalnym porządku zmiennych

F = H(a₁Å a_2, a₂Å a_3,a₄ Å a_5, a₅ Å a_6, a₇ Å a_8, a₈ Å a₉)= H(b_1,b₂, b_3, b_4,b_5,b₆), (3-5)

któremu odpowiada tablica indeksów przedstawiona w tabeli 3.33.

Tablica 3.33

b₁	b₂	b₃	b₄	b₅	b₆	f
1	0	0	0	0	0	1
0	0	0	0	0	0	2
1	1	0	0	0	0	3
0	1	0	0	0	0	4
0	0	1	0	0	0	5
0	0	1	1	0	0	6
0	0	0	1	0	0	7
0	0	0	0	1	0	8
0	0	0	0	1	1	9
0	0	0	0	0	1	10

W rozwiązaniu tym indeksy są reprezentowane wektorami 6-bitowymi b₁b₂b₃b₄b₅b₆.

Można przypuszczać, że stosując raz jeszcze metodykę zbiorów niezgodności uzyskamy rozwiązanie z mniejszą liczbą bitów. Ponieważ rodzina zbiorów niezgodności zawiera wszystkie możliwe pary b_ib_j, 12 zbiorów trójelementowych oraz żadnego zbioru 5 i 6 elementowego, znalezienie dekompozycji liniowej jest możliwe wyłącznie dla funkcji typu {xi Å xj , xj Å xk}.

Z przeglądu w RC_pqzbiorów trójelementowych:

1. b₁, b₃, b₄;

2. b₁, b₅, b₆;

3. b₁, b₂, b₃;

4. b₁, b₂, b₄;

5. b₁, b₂, b₅;

6. b₁, b₂, b₆;

7. b₂, b₃, b₄;

8. b₂, b₅, b₆;

9. b₃, b₅, b₆;

10. b₃, b₄, b₅;

11. b₃, b₄, b₆;

12. b₄, b₅, b₆;

wynika, że trójelementowymi zbiorami b_i, b_j,b_k możliwymi do utworzenia dekompozycji nierozłącznej są {b1, b3, b5}, {b1, b3, b6}, {b1, b4, b5}, {b1, b4, b6}, {b2, b3, b5}, {b2, b3, b6}, {b2, b4, b5}, {b2, b4, b6}. Ponieważ są wśród nich dwa zbiory rozłączne: {b1, b3, b5} i {b2, b4, b6}, a ponadto w COM(RC_pq) jest zbiór 6 elementowy b_1,b_2,b_3,b_4,b_5,b_6,spełnione są warunki istnienia dekompozycji: F = H(b₁Å b_3, b₃Å b_5,b₂ Å b_4, b₄ Å b₆). W rezultacie indeksy kodera 1 z 10 są 4-bitowe (tab. 3.34) i jest to rozwiązanie lepsze niż w [3.20].

Tablica 3.34

y₁	y₂	y₃	y₄	h
1	0	0	0	1
0	0	0	0	2
1	0	1	0	3
0	0	1	0	4
1	1	0	0	5
1	1	1	1	6
0	0	1	1	7
0	1	0	0	8
0	1	0	5	9
0	0	0	1	10

5. Dekompozycja równoległa

Dekompozycja funkcjonalna jest – podobnie jak redukcja argumentów – metodą syntezy logicznej, dostosowaną do implementacji na komórkach FPGA i pamięciach ROM. W związku z tym jej stosowanie w projektowaniu układów cyfrowych staje się coraz bardziej znaczące. W [3-20] problem dekompozycji określa się jako jedno z najpilniejszych zadań syntezy logicznej.

W szczególności proponuje się dalsze rozwijanie metody dekompozycji, polegającej na stosowaniu tzw. tablic dekompozycji (Decomposition Chart). Wydaje się jednak, że metoda zaproponowana w niniejszym rozdziale (podrozdz. 3.1, 3.2 oraz 3.3) jest znacznie skuteczniejsza. Jej zaletą jest stosowanie rachunku podziałów, co umożliwia sformułowanie wygodnego praktyce twierdzenia (Twierdzenie 3.3), w którym warunek wystarczający dekompozycji polega na wyznaczaniu podziałów na zbiorze ponumerowanych wektorów tablicy funkcji. Twierdzenie to wyraźnie wskazuje, że istotnym ograniczeniem dekompozycji jest podział wyjściowy funkcji (P_F) – im drobniejszy jest podział P_F, tym trudniejsze jest spełnienie warunku dekompozycji P_U × P_G £ P_F. Stąd pomysł uzupełnienia procesu dekompozycji funkcjonalnej – dekompozycją równoległą.

D e k o m p o z y c j a r ó w n o l e g ł a w układzie opisanym przez:

(y₁,..., y_m ) = F(x₁,..., x_n ) (3-5)

to podział zbioru {y₁,..., y_m} na takie rozłączne podzbiory Y₁ ,..., Y_i ,..., Y_k , z których każdy można zrealizować w układzie kombinacyjnym o argumentach odpowiednio X₁ ,..., X_i ,..., X_k , gdzie X_i Í {x₁,..., x_n}.

Sens powyższej dekompozycji wynika z ograniczeń konstrukcyjnych produkowanych modułów PLD i FPGA. Jeśli bowiem liczba wyjść, np. modułu PLD jest mniejsza od m, to do realizacji układu opisanego przez (3-5) można przeznaczyć (w zależności od m) kilka modułów, uzyskując w rezultacie układ pokazany na rys. 3.17. W układzie tym wyjścia y_i trzeba odpowiednio rozdzielić na poszczególne moduły. Wskazane jest, aby zbiór {y₁,..., y_m} rozdzielić na takie podzbiory Y_i , dla których odwzorowanie Y_i = h_i (X_i ) wymagałoby możliwie najmniejszej liczby argumentów X_i, przy czym X_i Í {x₁,..., x_n}, Y_i Í {y₁,..., y_m}.

Uzupelnij opis obrazka

Rys. 3.17. Dekompozycja równoległa

Pełną informację o rozdziale zbioru Y = {y₁,...,y_m} na podzbiory Y₁,...,Y_k uzyskać można z minimalno-argumentowych realizacji poszczególnych wyjść y_i.

Dla funkcji F z tablicy 3.35 redukty poszczególnych (pojedynczych) funkcji są odpowiednio:

y₁: {x₁, x₂, x₆}

y₂: {x₃, x₄}

y₃: {x₁, x₂, x₄, x₅, x₈}, {x₁, x₂, x₄, x₆, x₈}

y₄: {x₁, x₂, x₃, x₄, x₇}

y₅: {x₁, x₂, x₄}

y₆: {x₁, x₂, x₆, x₈}

Tablica 3.35

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	y₁	y₂	y₃	y₄	y₅	y₆
1	0	0	0	1	1	1	0	0	0	0	0	0	–	0
2	1	0	1	0	0	0	0	0	0	0	–	1	0	1
3	1	0	1	1	1	0	0	0	0	1	1	0	1	1
4	1	1	1	1	0	1	0	0	0	1	1	1	1	0
5	1	0	1	0	1	0	0	0	0	0	0	–	0	1
6	0	0	1	1	1	0	0	0	1	1	0	1	0	0
7	1	1	1	0	0	0	0	0	1	0	–	0	1	0
8	1	0	1	1	0	1	0	0	1	1	0	0	–	1
9	1	0	1	1	0	1	1	0	–	1	0	1	–	1
10	0	0	0	1	1	1	0	1	0	0	1	0	–	1
11	0	0	0	1	1	0	0	1	–	–	1	0	0	0

Zatem rozsądnie jest funkcji G₁ przyporządkować wyjścia y₁, y₃, y₆, a funkcji G₂ wyjścia y₂, y₄, y₅ (rys. 3. 18), gdyż wtedy uzyska się minimalne zbiory argumentów dla komponentów G₁ i G₂ dekompozycji równoległej funkcji F, a mianowicie {x₁, x₂, x₄, x₆, x₈} dla G₁ oraz {x₁, x₂, x₃, x₄, x₇} dla G₂. Tablice funkcji G₁ i G₂ są podane w tablicach 3.36a i 3.36b.

Tablica 3.36

a)									b)
	x₁	x₂	x₄	x₆	x₈	y₁	y₃	y₆		x₁	x₂	x₃	x₄	x₇	y₂	y₄	y₅
1	0	0	1	1	0	0	0	0	1	0	0	0	1	0	0	0	0
2	1	0	0	0	0	0	0	1	2	1	0	1	0	0	0	1	0
3	1	0	1	0	0	0	1	1	3	1	0	1	1	0	1	0	1
4	1	1	1	1	0	0	1	0	4	1	1	1	1	0	1	1	1
5	0	0	1	0	0	1	0	0	5	0	0	1	1	0	1	1	0
6	1	1	0	0	0	1	1	0	6	1	1	1	0	0	0	0	1
7	1	0	1	1	0	1	0	1	7	1	0	1	1	1	1	1	–
8	0	0	1	1	1	0	1	1
9	0	0	1	0	1	–	1	0

Uzupelnij opis obrazka

Rys. 3.18. Dekompozycja równoległa funkcji z przykładu 3.15

Wpływ dekompozycji zrównoważonej na ostateczny wynik syntezy w układzie FPGA zostanie pokazany na przykładzie pewnej funkcji F z 10 wejściami i 2 wyjściami (tab. 3.37), którą realizujemy w komórkach o 4 wejściach i 1 wyjściu (w uproszczeniu oznaczanych (4,1).

Tablica 3.37

.type fr
.i 10
.o 2
.p 25
0101000000 00
1110100100 00
0010110000 10
0101001000 10
1110101101 01
0100010101 01
1100010001 00
0011101110 01
0001001110 01
0110000110 01
1110110010 10
0111100000 00
0100011011 00
0010111010 01
0110001110 00
0110110111 11
0001001011 11
1110001110 10
0011001011 10
0010011010 01
e.


Rys. 3.19. Dekompozycja funkcji F – strategia szeregowa	Rys. 3.20. Dekompozycja funkcji F – strategia równoległa	Rys. 3.21. Dekompozycja funkcji F – strategia szeregowa

Skoro funkcja F ma 10 wejść i 2 wyjścia, pierwszym krokiem dekompozycji może być dekompozycja równoległa lub szeregowa. Jednak w tym przypadku zastosujemy dekompozycję szeregową. Algorytm wydziela funkcję G mającą wejścia x₁, x₃, x₄ i x₆,. Następny krok dotyczy więc funkcji 7-wejściowej H, dla której ponownie jest wykonywana dekompozycja szeregowa. Otrzymujemy blok G o 4 wejściach i 2 wyjściach (implementowany przez 2 komórki). Blok G ma na wejściu zmienne x₀, x₂, x₅, and x₇. Są to pierwotne zmienne wejściowe i na tym etapie nie jest zwiększona liczba poziomów, co widać na rys. 3.19.

W następnym kroku dokonujemy dekompozycji równoległej. Tworzy ona dwa komponenty, każdy o jednym wyjściu, natomiast odpowiednio o 4 i 5 wejściach. Pierwszy komponent realizuje pojedyncza komórka. Drugi komponent podlega dwupoziomowej dekompozycji szeregowej. Utworzona sieć może być zrealizowana za pomocą 7 komórek (4,1). Liczba poziomów ścieżki krytycznej wynosi 3.

Ta sama funkcja zdekomponowana tak, że najpierw wykonuje się dekompozycję równoległą, jest realizowana w zupełnie innej strukturze (rys. 3.20).

Uzupelnij opis obrazka

Rys. 3.22 Dekompozycja funkcji F – strategia równoległa

Dekompozycja równoległa zastosowana bezpośrednio dla funkcji F tworzy 2 komponenty o 6 wejściach i jednym wyjściu. Każdy z nich podlega dwupoziomowej dekompozycji szeregowej. Dla pierwszego z nich możliwa do zastosowania jest rozłączna dekompozycja szeregowa z blokiem G₁ (4,1). Drugi komponent może być również zdekomponowany szeregowo, jednak liczba wyjść bloku G₂ wynosi 2. Aby zmniejszyć łączną liczbę komórek, można zastosować dekompozycję nierozłączną, uzyskując tylko 4 komórki. Tablice prawdy tych komórek podane są w tabeli 3.38. Ta znacząca zmiana struktury wynika z tego, że dekompozycja równoległa zmniejsza liczbę wejść obu komponentów, prowadząc do uproszczenia końcowej implementacji.

Tablica 3.38

a) funkcja G₁

b) funkcja H₁

c) funkcja G₂

d) funkcja H₂

0110 1

1101 1

1000 1

0010 1

0000 0

0101 0

1100 0

0100 0

0011 0

1011 0

1111 0

-01 0

011 1

111 0

100 1

0-0 0

110 0

0110 1

0011 1

0100 1

1000 1

0101 1

1100 0

0010 0

1010 0

1110 0

0001 0

0111 0

1111 0

10-1 0

-101 1

-111 1

0011 0

0001 1

1-00 0

0000 0

1110 1

1010 0

0100 1

0010 1

Z powyższego przykładu wynika, że skuteczność dekompozycji w transformacji funkcji boolowskich na sieci komórek FPGA silnie zależy od scenariusza całego procesu dekompozycji, a w szczególności od kolejności wykonywania poszczególnych procedur, a także od parametrów składowej G oraz od rozdziału wyjść na komponenty dekompozycji równoległej.

6. Zadania

Automat z tablicy 3.39 zrealizować na pamięci ROM o 4 wejściach adresowych. W rozwiązaniu podać tablicę prawdy UMA oraz organizację pamięci ROM.

Tablica 3.39

	v₁	v₂	v₃	v₄	v₅
a	a	b	c	a	c
b	–	–	d	e	a
c	c	b	e	–	b
d	a	c	e	b	b
e	b	–	e	c	b

W tablicy 3.40 dana jest funkcja f(a,b,c,d,e):

$P_{F\ } =\left(\overline{1,10,17} ;\overline{5,7,19} ;\overline{6,8,14} ;\overline{3,12,16} ;\overline{2,13} ;\overline{4,15} ;\overline{9,18} ;\overline{11,20}\right)$

Należy obliczyć dekompozycję nierozłączną dla U = {d, e}. W rozwiązaniu podać tablice funkcji G oraz H. Kodowanie bloków P_Fprzyjąć dowolne wg NKB.

Tablica 3.40

de *a b c*	0 0	0 1	1 1	1 0
0 0 0	1	2	–	3
0 0 1	4	5	6	–
0 1 1	–	7	8	9
0 1 0	10	–	11	12
1 1 0	–	13	14	–
1 1 1	15	–	–	16
1 0 1	17	–	–	18
1 0 0	–	19	20	–

Wiedząc, że dla funkcji z tablicy 3.41 podziały P₁, P₃, P₅ są 3-przydatne, a P₂, P₄ – 4-przydatne, obliczyć najlepszą dekompozycję szeregową tej funkcji

Tablica 3.41

	x₁	x₂	x₃	x₄	x₅	y₁	y₂	y₃
1	0	0	0	0	0	1	0	1
2	0	0	0	1	0	1	0	0
3	0	0	0	1	1	0	1	1
4	0	0	1	1	1	0	0	0
5	0	1	0	0	0	1	0	0
6	1	0	1	1	1	0	0	1
7	1	1	0	0	0	0	1	1
8	1	1	1	0	0	0	0	0
9	1	1	1	0	1	0	0	1
10	1	1	1	1	1	0	1	0

Strona:	SEZAM - System Edukacyjnych Zasobów Akademickich i Multimedialnych
Kurs:	Dekompozycja funkcji boolowskich
Książka:	Podręcznik

Wydrukowane przez użytkownika:	Gość
Data:	sobota, 25 października 2025, 22:26

Spis treści

1. Metoda klasyczna

2. Dekompozycja funkcjonalna metodą rachunku podziałów

2.1. Dekompozycja funkcjonalna – model podstawowy

2.2. Dekompozycja zespołów funkcji boolowskich

2.3. Pojęcie r-przydatności

2.4. Dekompozycja nierozłączna

3. Dekompozycja funkcjonalna – model ogólny

4. Dekompozycja liniowa

5. Dekompozycja równoległa

6. Zadania