Podręcznik: Metoda klasyczna

6. Redukcja argumentów

6.1. Metoda klasyczna

Z praktycznego punktu widzenia istotne są takie realizacje funkcji boolowskich, w których argumenty $x_{i_1},\ldots,x_{i_t}$ , stanowią podzbiór zbioru $\ X\left\{x_1,\ldots,x_n\right\}$ , gdyż uzyskuje się wtedy bezpośrednio realizację n-argumentowej funkcji f w układzie kombinacyjnym o t wejściach (t < n), co ma znaczenie w syntezie na typowych modułach PLD i w strukturach FPGA. Istotne jest również to, że (przy dużych n) zmniejszenie liczby argumentów z n do t upraszcza ewentualnie dalsze zabiegi optymalizacyjne, gdyż zmniejsza wymiary zadań dla procesu minimalizacji i dekompozycji. W szczególności redukcja argumentów stanowi podstawę dekompozycji równoległej, którą omówimy pod koniec niniejszego rozdziału.

Realizację funkcji f = f(x₁,...,x_n) taką, że:

$f=h\left(x_{i_1},\ldots,x_{i_t}\right),\ \ t$

nazywać będziemy minimalno-argumentową realizacją funkcji f wtedy i tylko wtedy, gdy nie istnieje zbiór zmiennych:

$\left\{x_{j_1},\ldots,x_{j_{t-1}}\right\}\subseteq\ X$ , taki że $f=h\left(x_{j_1},\ldots,x_{j_{t-1}}\right)$ ,

Zbiór $x_{i_1},\ldots,x_{i_t}$ oznaczać będziemy X_t.

Niech a Î Bⁿ, b Î Bⁿ. Utwórzmy dla wektorów a,b wyrażenie boolowskie:

$\delta ( a,b) =\bigvee\limits _{i} \ x_{i}$

gdzie sumowanie jest po wszystkich i takich, że a_i ¹ b_i. Inaczej mówiąc, x_i jest składnikiem
d(a,b) tylko wtedy, gdy wektory a oraz b mają różne składowe a_i,b_i. Reprezentacją argumentową funkcji f (oznaczaną dalej przez RA_f) nazywać będziemy wyrażenie boolowskie:

${RA}_f=\begin{matrix}\bigwedge\\a,b\\\end{matrix}\delta\left(a,b\right)$ (2-6)

gdzie iloczyn logiczny Ù jest brany po wszystkich parach a,b : f(a) ¹ f(b).

Można wykazać, że dla każdego rozwiązania równania RA_f = 1:

$RA_{f}( x_{i_{1}} ,\dotsc ,x_{i_{t}}) =\mathbf{1}$ (2-7)

istnieje funkcja h o argumentach $x_{i_1},\ldots,x_{i_t}$ , dla której $f\left(x_1,\ldots,x_n\right)=h\left(x_{i_1},\ldots,x_{i_t}\right)$

Dla dowodu powyższego wystarczy zauważyć, że jeżeli $RA_{f}( x_{i_{1}} ,\dotsc ,x_{i_{t}}) =\mathbf{1}$ ,to dla każdej pary wektorów a,b : f(a) ¹ f(b), wektory $\left(a_{i_1},\ldots,a_{i_t}\right)$ oraz $\left(b_{i_1},\ldots,b_{i_t}\right)$ różnią się co najmniej jedną składową.

Jeżeli zbiór zmiennych $X_t=x_{i_1},\ldots,x_{i_t}$ ,spełniających równanie (2-7) jest zbiorem o możliwie najmniejszej liczności, to funkcja h jest nazywana minimalno-argumentową realizacją funkcji f [1].

Z konstrukcji wyrażenia RA_f wynika, że jest to koniunkcja czynników o postaci $\left(x_{i_1}\vee\ldots\vee x_{i_k}\right)$ . Rozwiązanie równania RA_f = 1 jest więc typowym problemem pokrycia, a odpowiednie obliczenia można uprościć wykorzystując pojęcie elementu zasadniczego, którego rolę w redukcji argumentów spełniać będzie omówione dalej pojęcie zmiennej niezbędnej.

Rozważmy funkcję f z tablicy 2.26a. Postaramy się zmniejszyć liczbę argumentów tej funkcji usuwając z niej po jednej zmiennej. Usuwając z tablicy 2.26a kolumnę odpowiadającą zmiennej x₄ uzyskujemy tablicę, w której dwa wiersze, o numerach 2 i 8, (tabl. 2.26b) są identyczne, ale wierszom tym odpowiadają różne wartości funkcji. Tablica jest więc sprzeczna. Stąd wniosek, że argumentu x₄ usunąć nie można.

Tablica 2.26

	a)								b)								c)
	x₁	x₂	x₃	x₄	x₅	x₆	x₇	f		x₁	x₂	x₃	x₅	x₆	x₇	f		x₂	x₄	x₆	x₇	f
1	1	0	0	0	1	0	1	0	1	1	0	0	1	0	1	0	1	0	0	0	1	0
2	1	0	1	1	1	1	0	0	2	1	0	1	1	1	0	0	2	0	1	1	0	0
3	1	1	0	1	1	1	0	0	3	1	1	0	1	1	0	0	3	1	1	1	0	0
4	1	1	1	0	1	1	1	0	4	1	1	1	1	1	1	0	4	1	0	1	1	0
5	0	1	0	0	1	0	1	1	5	0	1	0	1	0	1	1	5	1	0	0	1	1
6	1	0	0	0	1	1	0	1	6	1	0	0	1	1	0	1	6	0	0	1	0	1
7	1	0	1	0	0	0	0	1	7	1	0	1	0	0	0	1	7	0	0	0	0	1
8	1	0	1	0	1	1	0	1	8	1	0	1	1	1	0	1	8	0	0	1	0	1
9	1	1	1	0	1	0	1	1	9	1	1	1	1	0	1	1	9	1	0	0	1	1

Natomiast usuwając z tablicy 2.26a zmienną x₃ uzyskujemy tablicę, w której wszystkie wiersze są różne.

Można nawet usunąć jeszcze zmienne x₁ i x₅(tabl. 2.26c), a łączny rezultat tych usunięć nie spowoduje pojawienia się sprzeczności. Spostrzeżenie powyższe prowadzi do następującej definicji.

Oznaczmy przez T_f(X – {xi}) tablicę specyfikacji funkcji f uzyskaną z T_f przez usunięcie kolumny x_i, gdzie T_f jest tablicą funkcji f.

Zmienną x_i nazywamy zmienną niezbędną [2.6], jeżeli tablica specyfikacji T_f(X – {xi}) jest sprzeczna.

Zmiennymi niezbędnymi funkcji f z tablicy 2.26a są x₄oraz x₆, gdyż tablice T_f(X – {x4}), T_f(X – {x6}) są sprzeczne.

Można wykazać, że zmienna x_i jest zmienną niezbędną funkcji f(x₁,...,x_n), jeśli istnieją wektory a, b: f(a) ¹ f(b) takie, że a_i¹ b_i oraz a_j = b_j dla każdego j ¹ i.

Przyjmując do opisu funkcji f: Bⁿ ® {0,1,–} podziały na zbiorze K ponumerowanych wektorów z Bⁿ, możemy podane wyżej spostrzeżenia wyrazić analitycznie. Oznaczmy przez P(x_i) podział na K realizowany zmienną x_i, a przez P_f, podział wyjściowy funkcji f. Wtedy warunek na minimalno-argumentową realizację funkcji f można sprawdzić za pomocą nierówności:

$P\left(x_{i_1}\right)\cdot\ P\left(x_{i_2}\right)\cdot\ldots\cdot\ P\left(x_{i_t}\right)\le\ P_f$

Obliczymy wszystkie realizacje minimalno-argumentowe funkcji f = f(x₁,...,x₇), której tablica prawdy podana jest w tabl. 2.26a, z odpowiednią numeracją wektorów.

Wektory prawdziwe i fałszywe tej funkcji ponumerowano liczbami naturalnymi 1,...,9, czyli K = {1,...,9}. Mamy wtedy (przy oznaczeniach P(x_i) = P_i) następujące podziały na K:

$P_1=\left\{\overline{5};\overline{1,2,3,4,6,7,8,9}\right\}$

$P_2=\left\{\overline{1,2,6,7,8};\overline{3,4,5,9}\right\}$

$P_3=\left\{\overline{1,3,5,6};\overline{2,4,7,8,9}\right\}$

$P_4=\left\{\overline{1,4,5,6,7,8,9};\overline{2,3}\right\}$

$P_5=\left\{\overline{7};\overline{1,2,3,4,5,6,8,9}\right\}$

$P_6=\left\{\overline{1,5,7,9};\overline{2,3,4,6,8}\right\}$

$P_7=\left\{\overline{2,3,6,7,8};\overline{1,4,5,9}\right\}$

$P_f=\left\{\overline{1,2,3,4};\overline{5,6,7,8,9}\right\}$

Jak już stwierdziliśmy, zmiennymi niezbędnymi tej funkcji są x₄, x₆. Dlatego najpierw wyznaczymy iloczyn P = P₄×P₆:

${P_4\cdot P}_6=\left\{\overline{1,5,7,9};\overline{4,6,8};\overline{2,3}\right\}$

Blokami iloczynu P = (B₁,...,B₃) są B₁ = {1,5,7,9}, B₂ = {4,6,8}, B₃ = {2,3}. W dalszych obliczeniach pomijamy blok B₃, gdyż B₃ jest zawarty w jednym bloku podziału P_f.

Kolejną czynnością jest obliczenie podziału ilorazowego P₄×P₆| P_f :

${P_4\cdot P}_6|P_f=\left\{\overline{\left(1\right)\left(5,7,9\right)};\overline{\left(4\right)\left(6,8\right)};\overline{\left(2,3\right)}\right\}$

Obliczony podział ilorazowy pozwala wyznaczyć czynniki wyrażenia boolowskiego RA_f. Wyznaczane są one dla każdej pary mintermów p,q, takiej, że p i q należą do jednego bloku iloczynu P₄×P₆, ale do różnych bloków podziału P_f, co łatwo odczytać z podziału ilorazowego biorąc pary p,q z różnych elementów tego podziału. Przez elementy rozumiemy tu podzbiory ograniczone różnymi nawiasami. Dla każdej tak wyznaczonej pary p,q sprawdzamy na jakich pozycjach, czyli dla jakich zmiennych różnią się odpowiadające im wektory w tablicy prawdy. Na przykład, dla pary p = 1, q = 5 mamy, że odpowiednie wektory w tablicy prawdy funkcji f (tabl. 4.17a) różnią się na pozycjach x₁, x₂, a więc odpowiadający tej parze czynnik RA będzie C₁ = x₁ Ú x₂. Zestawienie zmiennych, dla których różnią się pary p,q nazywać będziemy tablicą porównań. Odczytując z podziału ilorazowego (2-8) pary p,q otrzymujemy następująca listę porównań:

1,5: x₁, x₂

1,7: x₃, x₅, x₇

1,9: x₂, x₃

4,6: x₂, x₃, x₇

4,6: x₂, x₇

Redukując w zbiorach C każde C_i, dla którego istnieje $C_j:C_j\subseteq\ C_i$ , otrzymujemy równanie RA = 1 o postaci:

$( x_{1} +x_{2})( x_{3} +x_{5} +x_{7})( x_{2} +x_{3})( x_{2} +x_{7}) =\mathbf{1}$

które przekształcamy do postaci sumo-iloczynowej:

x₂x₃ + x₂x₅ +x₂x₇ + x₁x₃x₇

Na tej podstawie wyznaczamy minimalne rozwiązania o najmniejszej liczności: {x2, x3, x4, x6}, {x2, x4, x5, x6}, {x2, x4, x6, x7}. Stąd wniosek, że siedmioargumentowa funkcja f w rzeczywistości jest zależna wyłącznie od czterech argumentów. Zauważmy też, że ostatnie z podanych rozwiązań oznacza usunięcie z tablicy funkcji f kolumn odpowiadających zmiennym x₁, x₃, x₅. Sytuacja taka była już prezentowana w tablicy 2.26c.

Skuteczność redukcji argumentów, a także jej wpływ na inne procedury logicznej pokażemy na bardziej skomplikowanym przykładzie.

Dla funkcji F podanej w tablicy 2.27 obliczyć wszystkie minimalne zbiory argumentów, od których ta funkcja zależy. Zmienne niezbędne tej funkcji to: x₁, x₃, x₇.

Kolejno obliczamy podziały: według zmiennych niezbędnych, ilorazowy oraz listę porównań.

$P_1\cdot P_3\cdot P_7=\left\{\overline{1,4,8};\overline{2,7};\overline{3};\overline{5,6,10};\overline{9}\right\}$

$P_1\cdot P_3\cdot P_7|P_F=\left\{\overline{\left(1\right)\left(4\right)\left(8\right)};\overline{\left(2\right)\left(7\right)};\overline{\left(3\right)};\overline{\left(5\right)\left(6\right)\left(10\right)};\overline{\left(9\right)}\right\}$

Tablica 2.27

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

Lista porównań (zapis wg indeksów zmiennych):

1|4 : ~~2,4,6,8,9~~

1|8 : 8,9

4|8 : 2,4,6

2|7 : 5,6,9

5|6 : 2,5,6,8

5|10 : ~~4,5,6,9~~

6|10 : ~~2,4,8,9~~

Na podstawie tablicy porównań tworzymy wyrażenie boolowskie, które w zapisie według indeksów zmiennych x_i jest następujące:

(8 + 9)(2 + 4 + 6)(5 + 6 + 9)(2 + 5 + 6 + 8) = (9 + 8)(9 + 5 + 6)(2 + 6 + 4)(2 + 6 + 5 + 8) =

= [9 + 8(5 + 6)][2 + 6 + 4(5 + 8)] = (9 + 5 × 8 + 6 × 8)(2 + 6 + 4 × 5 + 4 × 8) =

= 2 × 9 + 6 × 9 + 4 × 5 × 9 + 4 × 8 × 9 + 2 × 5 × 8 + 5 × 6 × 8 + 4 × 5 × 8 + 4 × 5 × 8 + 2 × 6 × 8 +
+ 6 × 8 + 4 × 5 × 6 × 8 + 4 × 6 × 8

Stąd wszystkie minimalne rozwiazania:

x₁, x₂, x₃, x₇, x₉

x₁, x₃, x₆, x₇, x₉

x₁, x₃, x₆, x₇, x₈

x₁, x₃, x₄, x₅, x₇, x₉

x₁, x₃, x₄, x₇, x₈, x₉

x₁, x₂, x₃, x₅, x₇, x₈

x₁, x₃, x₄, x₅, x₇, x₈

W bardziej skomplikowanych przykładach można zaobserwować wpływ redukcji argumentów na proces realizacji funkcji w postaci minimalnych wyrażeń boolowskich. Na przykład dla funkcji TL27 z tabl. 2.28 można obliczyć następujące redukty.

R₁ = {x1, x2, x4, x5, x6, x7, x10}

R₂ = {x1, x2, x4, x6, x7, x8, x10}

R₃ = {x1, x2, x4, x6, x7, x9, x10}

R₄ = {x1, x4, x5, x6, x7, x9, x10}

R₅ = {x1, x4, x6, x7, x8, x9, x10}

R₆ = {x1, x5, x6, x7, x8, x9, x10}

R₇ = {x2, x3, x4, x5, x6, x7, x10}

R₈ = {x2, x3, x5, x6, x7, x8, x10}

R₉ = {x3, x4, x5, x6, x7, x9, x10}

R₁₀ = {x3, x5, x6, x7, x8, x9, x10}

Tablica 2.28

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	y
1	0	0	1	0	1	1	1	0	1	0	0
2	1	0	1	0	0	1	0	1	0	0	0
3	0	1	0	0	0	1	1	1	1	0	0
4	1	0	1	1	1	0	1	0	1	1	0
5	1	1	0	0	0	1	0	0	1	1	0
6	0	1	0	0	0	1	0	1	1	0	0
7	1	1	1	0	1	0	0	1	1	0	0
8	0	1	0	0	1	1	0	0	0	0	0
9	0	1	0	1	0	0	0	0	1	0	0
10	0	1	1	1	1	1	1	0	1	1	1
11	0	0	0	0	0	1	0	1	0	0	1
12	1	1	0	1	1	1	0	0	1	1	1
13	0	1	0	0	1	0	0	0	0	0	1
14	0	1	0	0	0	1	1	1	1	1	1
15	0	0	1	0	0	0	0	1	1	0	1
16	1	1	1	1	0	1	0	0	0	1	1
17	1	1	1	1	1	0	1	0	0	1	1
18	1	1	1	1	1	1	1	1	1	1	1
19	0	0	1	0	0	0	0	0	0	0	1
20	1	1	0	1	1	0	0	1	1	1	1
21	0	0	1	0	0	0	1	1	1	1	1
22	1	1	1	1	1	0	0	0	1	0	1
23	1	0	1	0	1	1	1	1	0	1	1
24	0	1	1	0	0	0	0	1	1	0	1
25	0	1	0	0	1	1	1	0	0	0	1

Wybierając jeden z tych zbiorów (np. R₃) możemy dla zredukowanej w ten sposób funkcji zastosować inne procedury optymalizacji np. minimalizację. Uzyskamy wtedy następujące wyrażenie:

$f={\bar{x}}_1{\bar{x}}_2{\bar{x}}_7+x_1x_2x_4+{\bar{x}}_1x_{10}+{\bar{x}}_1{\bar{x}}_4{\bar{x}}_6+x_7{\bar{x}}_9$

Warto podkreślić, że rozwiązanie wyznaczone za pomocą programu ESPRESSO [2.1] prowadzi do wyrażenia

$f={\bar{x}}_5{\bar{x}}_6x_8+\ {\bar{x}}_1{\bar{x}}_2{\bar{x}}_5+x_5{\bar{x}}_6{\bar{x}}_8{\bar{x}}_{10}++{x_4\bar{x}}_7{\bar{x}}_{10}+x_7{\bar{x}}_9+x_6x_7x_{10}$

zawierającego 9 argumentów. Jak widać, nie prowadzi ono do realizacji minimalno-argumentowej. Jeśli jednak procedurę minimalizacji zastosujemy do funkcji o zredukowanych argumentach, to uzyskamy wyrażenie o mniejszej liczbie składników iloczynowych.

[1] Zbiór X_t jest również nazywany reduktem [2.10].