Podręcznik: Dekompozycja nierozłączna

2. Dekompozycja funkcjonalna metodą rachunku podziałów

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.