Podręcznik: Dekompozycja liniowa

4. Dekompozycja liniowa

Dekompozycja liniowa polega na łączeniu zmiennych w pary i wprowadzaniu ich za pośrednictwem bramek EXOR do głównego układu realizującego detekcję i klasyfikację (czyli indeksowanie) danych. Jest to istotne, gdyż prowadzi do dalszego redukowania liczby wejść w generatorach indeksu. I pewnie z tych powodów dekompozycja liniowa jest intensywnie wykorzystywana w syntezie funkcji generowania indeksów [3.20].

W dotychczasowych rozwiązaniach problem dekompozycji liniowej ogranicza się do syntezy silnie nieokreślonych funkcji boolowskich, o specyficznej własności: |Dⁿ| = k. Ograniczenie tego problemu do funkcji, w których wszystkie wektory wyjściowe są różne, jest niepotrzebne, gdyż problem ten można sprowadzić do ogólniejszego zadania syntezy systemów funkcji boolowskich o dowolnych wyjściach. Inaczej mówiąc lepiej przyjąć założenie, że liczność zbioru wektorów wyjściowych Y funkcji F jest ≤ |Dⁿ|.

Ogólnie rzecz biorąc problem można sprowadzić do wskazania warunków jakie muszą być spełnione, aby funkcja F posiadała dekompozycję z dwu-argumentowymi funkcjami G.

F = H(G₁(X₁), G₂(X₂),..., x_n),

gdzie: $X_1=\left\{x_{i_1},x_{i_2}\right\}$ , $X_2=\left\{x_{i_3},x_{i_4}\right\}$ ,

Funkcję G nazywać można g-argumentem, stosownie do ogólnej teorii dekompozycji funkcji boolowskich. Przyjmujemy również założenie, że w dekompozycji liniowej stosujemy funkcje o zredukowanej liczbie argumentów, czyli tzw. minimalno-argumentowe reprezentacje funkcji F.

Przy tak postawionym zagadnieniu wygodne jest stosowanie uporządkowanego i zwartego sposobu reprezentowania funkcji, jakim jest rachunek podziałów. Szczegóły dotyczące tego sposobu przedstawiana funkcji zostały już omówione w rozdz. 1.4 i nie będą tu dyskutowane. Niezbędne jest jednak krótkie przypomnienie, gdyż własności podziałów będą wykorzystywane do skonstruowania metody syntezy układów bramkowych, omawianej w dalszej części artykułu.

Rozpatrzmy funkcję logiczną zdefiniowaną w tab. 3.28, w której symbole T: 1,2,...,11 reprezentują wektory, x₁,...,x₅ reprezentują zmienne wejściowe, zaś y – zmienną wyjściową.

Tablica 3.28

T	x₁	x₂	x₃	x₄	x₅	y
1	0	0	0	0	0	0
2	0	0	1	1	1	0
3	0	1	0	1	0	0
4	0	1	1	1	1	0
5	0	1	1	0	0	0
6	0	0	0	1	1	1
7	0	1	0	0	0	1
8	0	1	1	0	1	1
9	1	1	0	1	0	1
10	1	0	0	1	1	1
11	1	0	0	1	0	1

Dla tego przykładu, różne wartości, przyjmowane przez zmienną wejściową x₄, wyznaczają podzbiory wektorów {1,5,7,8} i {2,3,4,6,9,10,11}. Dla wektorów 1,5,7 i 8, x₄ = 0, dla 2,3,4,6,9,10,11, x₄ = 1. Zatem wiedząc, że x₄ = 0, wiemy, że wybrany został wektor 1,5,7 lub 8, nie wiemy jednak który z nich. Analogicznie wiedząc, że x₃ = 1 wiemy, że wybrano symbol 2,4,5 lub 8, nie jesteśmy jednak wstanie wskazać, który z nich konkretnie. W ten sposób informacja modelowana jest przez podziały, pokrycia i systemy zbiorów.

Dla funkcji z tab, 3.29 podziały wejściowe i wyjściowy są następujące

$P\left(x_1\right)=\left\{\overline{1,2,3,4,5,6,7,8};\overline{9,10,11}\right\}$ ,
$P\left(x_2\right)=\left\{\overline{1,2,6,10,11};\overline{3,4,5,7,8,9}\right\}$ ,

$P\left(x_3\right)=\left\{\overline{1,3,6,7,9,10,11};\overline{2,4,5,8}\right\}$ ,
$P\left(x_4\right)=\left\{\overline{1,5,7,8};\overline{2,3,4,6,9,10,11}\right\}$ ,
$P\left(x_5\right)=\left\{\overline{1,3,5,7,9,11};\overline{2,4,6,8,10}\right\}$ ,
$P_F=\left\{\overline{1,\ldots,5};\overline{6,\ldots,11}\right\}$ ,

W celu uproszczenia zapisów wektory a,b Î{0,1}ⁿ : F(a) ≠ F(b), będą reprezentowane liczbami p,q Î K = {1,..., | Dn |}.

Niech F będzie wielowyjściową funkcją boolowską, gdzie zbiór zmiennych X = (x₁,…, x_n)_, zbiór wektorów (mintermów) M = (m₁,…, m_t)_.Przez C_pq, gdzie p, q są wektorami z M, dla których F(p) ¹ F(q) oznaczamy zbiór niezgodności, definiowany jak następuje:

C_pq = {x Î X : x(p) ¹ x(q)} dla p,q = 1,…,t and p < q}. (3-3)

Rodzinę zbiorów C = (C₁,…, C_n_), dla wszystkich C_pq oznaczać będziemy RC_pq. W obliczeniach par zmiennych tworzących dekompozycję liniową posługiwać się będziemy rodziną zbiorów C_pq.

Problem wyznaczenia odpowiednich warunków, oparty jest na pojęciu funkcji rozdzielającej. O funkcji g będziemy mówić, że jest funkcją rozdzielająca (dystrybucją) pary wektorów p,q wtedy i tylko wtedy, gdy p i q należą do różnych bloków podziału P(g). W uproszczeniu można powiedzieć, że w takim przypadku funkcja g umożliwia rozdzielenie wektorów p i q.

Z przyjętej definicji wynika, że każda jednoargumentowa funkcja g(x_j) = x_j, gdzie x_j Î C_pq jest dystrybucją p, q. Ponadto jeśli g rozdziela parę p, q, to również parę tę rozdziela funkcja g .

Wykorzystując powyższe ustalenia można teraz warunkowi dekompozycji nadać wygodniejszą postać: F = H(g₁, g₂,..., g_t) wtedy i tylko wtedy, gdy dla każdej pary p, q: takiej, że (p,q) nie jest zawarta w jednym bloku podziału charakterystycznego P_Fistnieje g_j rozdzielająca parę p, q. Zalety tego warunku zostaną obecnie wykorzystane do sformułowania metodyki syntezy układów w których argumenty z X = (x₁,…, x_n)łączone będą w pary i wprowadzane do układu H za pośrednictwem funktorów g(x_i, x_j) tzn. F = H(g₁, g₂,…, g_t, x_a, x_b…).

Wykorzystując powyższe ustalenia można zaproponować sposób prowadzenia syntezy logicznej jako dekompozycję bezpośrednio na bramki, w odróżnieniu od dekompozycji funkcjonalnej, w której składowe są funkcjami opisanymi tablicami prawdy. Możliwe jest obliczenie podziału P(g) dla dowolnej funkcji o skończonej liczbie zmiennych wejściowych i w następnym kroku usunięcie wszystkich zbiorów C_pq,dla których g nie jest dystrybucją. Obliczamy w ten sposób dekompozycję funkcji F i zapisujemy ją w postaci:

$F=H\left(G\left(x_{i_1},\ldots,x_{i_t}\right),\ldots,x_{i_n}\right)$

Liczba argumentów funkcji H wynosi w tym przypadku co najwyżej n – 1, w związku z czym proces prowadzi do zmniejszenia złożoności funkcji.

Funkcja

$g\ =x_{i} \ \oplus \ x_{j}$ jest funkcją rozdzielającą (dystrybucją) parę (p, q) wtedy i tylko wtedy gdy {xi, xj} Ï C_pq

$\left|\left\{x_i,x_j\right\}\right|\cap\ C_{pq}=1$

Powyższe twierdzenie prowadzi do prostej metody dekomponowania funkcji i wyznaczania g = g(x_i, x_j) bezpośrednio ze zbiorów C_pq i podziałów P(x_i), np. podziałów generowanych przez funkcję jednoargumentową g(x_i) = x_i.

$G=x_{i} \ \oplus \ x_{j}$ jest dekompozycją funkcji F, wtedy i tylko wtedy, gdy {xi, xj} Ï RC_pq, gdzie RC_pq jest rodziną zbiorów C_pq, dla których p oraz q należą do różnych bloków podziału wyjściowego P_F.

Dla funkcji F z tabeli 3.28 rodzinę RC_pq ograniczoną do zbiorów dwuelementowych zapisano w tabeli 3.29. Łatwo zauważyć, że RC_pq nie zawiera 3 następujących par: x₁, x₅; x₃, x₄; x₃, x₅.
Łatwo zauważyć, że RC_pq nie zawiera 3 następujących par: x₁, x₅; x₃, x₄; x₃, x₅.
Tablica 3.29

p,q	C_pq
1,6	x₄,x₅
1,11	x₁,x₄
2,8	x₂,x₄
2,10	x₁,x₃
3,6	x₂,x₅
3,11	x₁,x₂
4,6	x₂,x₃

Stąd wniosek, że możliwe są g-argumenty reprezentowane przez dekompozycje funkcji F:

F = H(x₁Å x₅, x₂, x₃,x₄); F= H(x₃Å x₄, x₁, x₂,x₅); F= H(x₃ Å x₅, x₁, x₂,x₄).

Proces obliczania dekompozycji liniowej może być wykonywany iteracyjnie, aż do uzyskania dekompozycji F = H(g₁, g₂,…, X) z maksymalną liczbą funkcji G, co zapewnia minimalna liczbę argumentów dla funkcji H, oczywiście łącznie z g-argumentami typu EXOR.

Twierdzenie 3.7 i test 3.1 można uogólnić na przypadek tzw. dekompozycji wielokrotnej. Wtedy dodatkowym warunkiem na istnienie dekompozycji z parą funkcji {xi Å xj , xk Å xl}, jest sprawdzenie czy zbiór zmiennych {xi, xj, xk, xl} jest zawarty w rodzinie RC_pq.

Dla uproszczenia zapisów uzupełnienie RC_pq względem rodziny wszystkich podzbiorów o liczności równej liczności analizowanych C_pq oznaczać będziemy COM(RC_pq).

Dla funkcji z przykładu 3.12 w celu sprawdzenia, które g-argumenty mogą tworzyć dekompozycję wielokrotną (w tym przypadku podwójną), należy obliczyć czteroelementowe zbiory RC_pq. W wyniku uzyskujemy, że wszystkie cztero-elementowe zbiory RC_pq są: {x2 x3 x4 x5}_, {x1 x2 x3 x5}_, {x1 x2 x3 x4}. Zatem uzupełnienie COM(RC_pq) zawiera dwa zbiory {{x1 x2 x4 x5}_,{ x1 x3 x4 x5}} i jeden z nich reprezentuje zmienne g-argumentów x₁Å x₅, x₃Å x₄. Na tej podstawie stwierdzamy, że funkcja z przykładu 3.12 ma dekompozycję: F = H(x₁Å x₅, x₃Å x_4,x₂).

Inne uogólnienie Twierdzenia 3.7 dotyczy dekompozycji nierozłącznej. W tym przypadku dodatkowy warunek na istnienie dekompozycji z parą funkcji {xi Å xj , xj Å xk} polega na sprawdzeniu, czy zbiór zmiennych {xi, xj, xk} jest zawarty w rodzinie RC_pq.

Omówioną metodykę obliczania dekompozycji liniowej skonfrontujemy teraz z algorytmem zaproponowanym w [3.20]. Obliczenia przeprowadzimy dla funkcji reprezentującej koder 1 z 10 – tab. 3.30.

Tablica 3.30

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	y₁	y₂	y₃	y₄	y₅	y₆
1	1	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
2	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	0	0	0	0	0	0	0	0	1	1	0	0	0
4	0	0	0	1	0	0	0	0	0	0	0	0	0	1	1	0
5	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1
6	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1
7	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0
8	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0
9	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0
10	0	0	0	0	0	0	0	0	0	1	0	0	0	0	1	0

Dla funkcji tej w [3.20] obliczono dekompozycję liniową z 6 g-argumentami, które w tab. 3.30 oznaczono y₁,…, y₆:

F = H(x₁Åx_6, x₃Åx_7,x₃ Åx_9, x₄Åx₈, x₄ Åx_10, x₅Åx₆)

Obliczenia wykonano za pomocą heurystycznego algorytmu s-min. Ponieważ w uzyskanym rozwiązaniu nie ma zmiennej x₂, wygodnie będzie wprowadzić nowe oznaczenia zmiennych, zgodnie z tabelą 3.31.

Tablica 3.31

x₁	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀
a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉

Przy tych oznaczeniach uzyskuje się nowa tablicę kodera podaną w tabeli 3.32, jak też nowe wyrażenie na uzyskaną w [3.20] dekompozycję

F = H(a₁Åa_5, a₂Åa_6,a₂ Åa_8, a₃Åa₇, a₃ Åa_9, a₄Åa₅)

Tablica 3.32

	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉
1	1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0	0
4	0	0	1	0	0	0	0	0	0
5	0	0	0	1	0	0	0	0	0
6	0	0	0	0	1	0	0	0	0
7	0	0	0	0	0	1	0	0	0
8	0	0	0	0	0	0	1	0	0
9	0	0	0	0	0	0	0	1	0
10	0	0	0	0	0	0	0	0	1

Dla uproszczonego wg tabeli 3.32 kodera 1 z 10 obliczamy rodzinę RC_pq, a następnie COM(RC_pq). W wyniku uzyskujemy: uzupełnienie rodziny RC_pq ma pusty zbiór par, ale zawiera wszystkie możliwe (84) podzbiory trój-elementowe zbioru {a1, a2, a3, a4, a5, a6, a7, a8, a9}. Stąd wniosek, że dla kodera 1 z 10 istnieje dekompozycja nierozłączna wielokrotna reprezentowana trójelementowymi podzbiorami zbioru {a1, a2, a3, a4, a5, a6, a7, a8, a9}, czyli

F = H(a_iÅa_j_,a_jÅa_k_,a_lÅa_m_,a_mÅa_n_,a_pÅa_q_,a_qÅa_r) (3-4)

Tym samym potwierdza to istnienie dekompozycji:

F = H(a₁Åa_5, a₂Åa_6,a₂ Åa_8, a₃Åa₇, a₃ Åa_9, a₄Åa₅)

uzyskanej w [3.20], przy czym należy podkreślić, że dekompozycja taka istnieje dla wszystkich możliwych trójek:

a_i a_ja_k,

a_l a_ma_n,

a_p a_q a_r

Zatem przy zastosowaniu metody z [3.20] znalezienie jakiegokolwiek rozwiązania nie było trudne.

Wykazana własność dekompozycji (wg (3-4)) pozwala zapisać dekompozycję kodera 1 z 10 w naturalnym porządku zmiennych

F = H(a₁Å a_2, a₂Å a_3,a₄ Å a_5, a₅ Å a_6, a₇ Å a_8, a₈ Å a₉)= H(b_1,b₂, b_3, b_4,b_5,b₆), (3-5)

któremu odpowiada tablica indeksów przedstawiona w tabeli 3.33.

Tablica 3.33

b₁	b₂	b₃	b₄	b₅	b₆	f
1	0	0	0	0	0	1
0	0	0	0	0	0	2
1	1	0	0	0	0	3
0	1	0	0	0	0	4
0	0	1	0	0	0	5
0	0	1	1	0	0	6
0	0	0	1	0	0	7
0	0	0	0	1	0	8
0	0	0	0	1	1	9
0	0	0	0	0	1	10

W rozwiązaniu tym indeksy są reprezentowane wektorami 6-bitowymi b₁b₂b₃b₄b₅b₆.

Można przypuszczać, że stosując raz jeszcze metodykę zbiorów niezgodności uzyskamy rozwiązanie z mniejszą liczbą bitów. Ponieważ rodzina zbiorów niezgodności zawiera wszystkie możliwe pary b_ib_j, 12 zbiorów trójelementowych oraz żadnego zbioru 5 i 6 elementowego, znalezienie dekompozycji liniowej jest możliwe wyłącznie dla funkcji typu {xi Å xj , xj Å xk}.

Z przeglądu w RC_pqzbiorów trójelementowych:

1. b₁, b₃, b₄;

2. b₁, b₅, b₆;

3. b₁, b₂, b₃;

4. b₁, b₂, b₄;

5. b₁, b₂, b₅;

6. b₁, b₂, b₆;

7. b₂, b₃, b₄;

8. b₂, b₅, b₆;

9. b₃, b₅, b₆;

10. b₃, b₄, b₅;

11. b₃, b₄, b₆;

12. b₄, b₅, b₆;

wynika, że trójelementowymi zbiorami b_i, b_j,b_k możliwymi do utworzenia dekompozycji nierozłącznej są {b1, b3, b5}, {b1, b3, b6}, {b1, b4, b5}, {b1, b4, b6}, {b2, b3, b5}, {b2, b3, b6}, {b2, b4, b5}, {b2, b4, b6}. Ponieważ są wśród nich dwa zbiory rozłączne: {b1, b3, b5} i {b2, b4, b6}, a ponadto w COM(RC_pq) jest zbiór 6 elementowy b_1,b_2,b_3,b_4,b_5,b_6,spełnione są warunki istnienia dekompozycji: F = H(b₁Å b_3, b₃Å b_5,b₂ Å b_4, b₄ Å b₆). W rezultacie indeksy kodera 1 z 10 są 4-bitowe (tab. 3.34) i jest to rozwiązanie lepsze niż w [3.20].

Tablica 3.34

y₁	y₂	y₃	y₄	h
1	0	0	0	1
0	0	0	0	2
1	0	1	0	3
0	0	1	0	4
1	1	0	0	5
1	1	1	1	6
0	0	1	1	7
0	1	0	0	8
0	1	0	5	9
0	0	0	1	10