TC Moduł 5

Redukcja argumentów

---

Minimalizacja funkcji boolowskich jest podstawową procedurą syntezy logicznej w komputerowych systemach projektowania układów cyfrowych. Skuteczność i szybkość działania tej procedury może być decydująca o jakości implementacji sprzętowych wielu systemów cyfrowych o różnorodnych zastosowaniach. Niestety ze względu na heurystyczny sposób obliczeń w programie Espresso uzyskany wynik $F_M$ może nie być pokryciem minimalnym, co przy wzrastającej złożoności układów realizowanych w nowoczesnych technologiach może okazać się istotną barierą. Niniejszy wykład omawia oryginalną metodę zmniejszania złożoności obliczeniowej algorytmów minimalizacji funkcji boolowskich. Istotą tej metody jest zastosowanie algorytmu redukcji argumentów, jako oddzielnej procedury poprzedzającej właściwą minimalizację. Redukcja argumentów jest procedurą do tej pory rzadko stosowaną w komputerowych systemach syntezy logicznej. Jedną z przyczyn takiej sytuacji jest brak świadomości, że złożone układy cyfrowe są – od strony pojedynczych wyjść - reprezentowane funkcjami boolowskimi o znacznie nadmiarowych zależnościach wejściowych.

---

Celem wprowadzenia wróćmy do przykładu funkcji omawianej w poprzednim wykładzie. Jej tablica prawdy podana na planszy ma 7 argumentów. Ale na poprzednim wykładzie obliczyliśmy metodą ekspansji, że minimalne wyrażenie boolowskie tej funkcji zawiera wyłącznie 4 argumenty. Gdybyśmy to wiedzieli wcześniej, to zadanie minimalizacji moglibyśmy skutecznie uprościć. Wystarczyłoby w tym celu usunąć z tablicy prawdy tej funkcji kolumny odpowiadające nadmiarowym argumentom. Zatem problem obliczania od jakich argumentów funkcja istotnie zależy jest bardzo ważny w zmniejszaniu złożoności obliczeniowej procedur minimalizacji.

---

W innym przykładzie funkcji 10 argumentowej, dla której programem Espresso zostało obliczone minimalne wyrażenie boolowskie zauważamy, że w wyrażeniu tym brak jest zmiennej $x_3$. Czyli według Espresso funkcja ta zależy od 9 argumentów.

---

Można jednak obliczyć (programem Pandor), że funkcja ta w rzeczywistości jest zależna od 7 argumentów. Czyli Espresso doskonale redukuje składniki iloczynowe funkcji, ale w przypadku argumentów jego obliczenia nie są skuteczne. Potwierdza to sygnalizowany już mankament metody i programu Espresso.

---

Z powyższych przykładów wynika, że obliczanie minimalnej liczby argumentów od których funkcja istotnie zależy jest bardzo istotne w redukowaniu złożoności obliczeniowej procedur minimalizacji funkcji boolowskich, a w konsekwencji może się przyczynić do uzyskiwania lepszych rezultatów. Do obliczeń w metodzie redukcji argumentów będziemy stosować rachunek podziałów. Niezbędne pojęcia tego rachunku podajemy na planszach 7, 8 oraz 9.

---

Podziałem na zbiorze $S$ jest system zbiorów $\pi =\left\{Bi\right\}$, którego bloki są rozłączne, czyli $B_i\cap B_j=\varnothing$ , jeśli tylko $i\ne j$ . Na przykład dla $S=\{1,2,3,4,5,6\}$ , $\{\{1,2\},\{3,5\},\{4,6\}\}$ jest podziałem na $S$, co zapisujemy: $\pi =(\overline{1,2};\overline{3,4};\overline{5,6})$ Dla podziałów – podobnie jak dla zbiorów –definiuje się relację porządku oraz typowe działania iloczynu, sumy itp.,

---

Powiemy, że podział ${\pi }_1$ jest nie większy od ${\pi }_2$ (co oznaczamy: ${\pi }_1\le {\pi }_2$), jeśli każdy blok z ${\pi }_1$ jest zawarty w pewnym bloku z ${\pi }_2$. Wprowadzamy oznaczenia odpowiednio dla podziału najmniejszego $\pi (0)$ oraz największego $\pi (1)$. Podział $\pi (0)$ jest podziałem, którego bloki są elementami zbioru $S$. Podział $\pi (1)$ jest podziałem o jednym bloku wyczerpującym cały zbiór $S$. Na przykład: dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle S = \left\{1, 2, 3}\right\}\,} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi (0) = \left\{\overline{1}, \overline{2}, \overline{3}}\right\}\,} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi (1) = \left\{\overline{1,2,3}}\right\}\,} .

---

Iloczynem podziałów ${\pi }_1\bullet {\pi }_2$ nazywamy największy (względem relacji $\le$) podział, który jest nie większy od ${\pi }_1$ oraz ${\pi }_2$. ${\mathrm{\Pi }}_a=(\overline{1,2,4};\overline{3,5,6})$ ${\mathrm{\Pi }}_b=(\overline{1,4};\overline{2,6};\overline{3,5})$ ${\mathrm{\Pi }}_1\bullet {\mathrm{\Pi }}_2=(\overline{1,4};\bar{2};\bar{6};\overline{3,5})$ Symetrycznie, sumą ${\pi }_1+{\pi }_2$ nazywamy najmniejszy podział nie mniejszy od ${\pi }_1$ oraz ${\pi }_2$. ${\mathrm{\Pi }}_a=(\overline{1,2};\overline{3,4};\overline{5,6};\overline{7,8,9})$ ${\mathrm{\Pi }}_b=(\overline{1,6};\overline{2,3};\overline{4,5};\overline{7,8};\bar{9})$ ${\mathrm{\Pi }}_1+{\mathrm{\Pi }}_2=(\overline{1,2,3,4,5,6};\overline{7,8,9})$

---

---

---

---

---

---

---

---

---

---

---

---

---

---