Podręcznik

Niech będzie dana funkcja boolowska f: {0, 1}ⁿ ® {0, 1} oraz pewien podział zmiennych X = {<i>x</i>₁,...,<i>x_n</i>} 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).

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 {<i>x</i>₁, <i>x</i>₂, <i>x</i>₃} względem których funkcja f jest symetryczna. Wiersze natomiast są adresowane zmiennymi {<i>x</i>₄, <i>x</i>₅}.

Tablica  3.1

Grupy kolumn o adresach {(001), (010), (100)} i {(110),  (101), (011)} są odpowiednio równe. Zatem istnieje dekompozycja, w której zmienne {<i>x</i>₁, <i>x</i>₂, <i>x</i>₃} są przeadresowywane na {<i>g</i>₁, <i>g</i>₂} (tablica 3.2a).

Wówczas funkcja f może być specyfikowana w tablicy, w której adresami kolumn są {<i>g</i>₁, <i>g</i>₂}, a wierszy odpowiednio wartości zmiennych {<i>x</i>₄, <i>x</i>₅} (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

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

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 zgod­ności.  Wypisując więc dla funkcji z tabl. 3.4 wszy­stkie pary zgodne: {<i>K</i>₀, <i>K</i>₃}, {<i>K</i>₀, <i>K</i>₄}, {<i>K</i>₀, <i>K</i>₆}, {<i>K</i>₁, <i>K</i>₃}, {<i>K</i>₁, <i>K</i>₄}, {<i>K</i>₁, <i>K</i>₅}, {<i>K</i>₁, <i>K</i>₆}, {<i>K</i>₂, <i>K</i>₅}, {<i>K</i>₂, <i>K</i>₇}, {<i>K</i>₃, <i>K</i>₄}, {<i>K</i>₃, <i>K</i>₆}, {<i>K</i>₄, <i>K</i>₅}, {<i>K</i>₄, <i>K</i>₆}, {<i>K</i>₅, <i>K</i>₇}, łatwo możemy obliczyć – stosując algorytm omówiony w rozdz. 1 – maksymalne klasy zgodności:

{<i>K</i>₀, <i>K</i>₃, <i>K</i>₄, <i>K</i>₆},

{<i>K</i>₁, <i>K</i>₃, <i>K</i>₄, <i>K</i>₆},

{<i>K</i>₁, <i>K</i>₄, <i>K</i>₅},
{<i>K</i>₂, <i>K</i>₅, <i>K</i>₇}.

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:{<i>K</i>₀, <i>K</i>₃, <i>K</i>₄, <i>K</i>₆}, {<i>K</i>₂, <i>K</i>₅}, {<i>K</i>₂, <i>K</i>₇}.

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 oblicze­niach 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₁₀ = {<i>x</i>₃,<i> x</i>₅,<i> x</i>₆,<i> x</i>₇,<i> x</i>₈,<i> x</i>₉,<i> x</i>₁₀} – jest przedstawiona w tab. 3.4.

Tablicę tę skonstruowano przy założeniu, że zbiory zmiennych bezpośrednich oraz pośrednich są odpowiednio A = {<i>x</i>₇,<i> x</i>₈,<i> x</i>₉},  B = {<i>x</i>₃,<i> x</i>₅,<i> x</i>₆,<i> x</i>₁₀}. 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