Podręcznik: Pojęcie r-przydatności

2. Dekompozycja funkcjonalna metodą rachunku podziałów

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