Podręcznik: Dekompozycja zespołów funkcji boolowskich

2. Dekompozycja funkcjonalna metodą rachunku podziałów

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₃

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₃

8,13

9,14

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