Podręcznik: Dekompozycja funkcjonalna – model ogólny

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