TC Moduł 5

From Studia Informatyczne

Grafika:TC_M5_Slajd1.png Redukcja argumentów

Grafika:TC_M5_Slajd2.png 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.


Grafika:TC_M5_Slajd3.png 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.

Grafika:TC_M5_Slajd4.png 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.

Grafika:TC_M5_Slajd5.png 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.

Grafika:TC_M5_Slajd6.png 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.


Grafika:TC_M5_Slajd7.png 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\neq j .

Na przykład dla S = \left \{1,2,3,4,5,6\right \} \, , \left \{\left \{1,2\right \} , \left \{3,5\right \}, \left \{4,6\right \}\right \} 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.,


Grafika:TC_M5_Slajd8.png 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 S = \left\{1, 2, 3}\right\}\,, \pi (0) = \left\{\overline{1}, \overline{2}, \overline{3}}\right\}\, , \pi (1) = \left\{\overline{1,2,3}}\right\}\, .


Grafika:TC_M5_Slajd9.png 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\,.

\Pi_a=(\overline{1,2,4}; \overline{3,5,6})

\Pi_b=(\overline{1,4}; \overline{2,6}; \overline{3,5})

\Pi_1\bullet \Pi_2=(\overline{1,4}; \overline{2}; \overline{6}; \overline{3,5})

Symetrycznie, sumą \pi_1+ \pi_2\, nazywamy najmniejszy podział nie mniejszy od \pi_1\, oraz \pi_2\,.

\Pi_a=(\overline{1,2}; \overline{3,4}; \overline{5,6}; \overline{7,8,9})

\Pi_b=(\overline{1,6}; \overline{2,3}; \overline{4,5}; \overline{7,8}; \overline{9})

\Pi_1+ \Pi_2=(\overline{1,2,3,4,5,6}; \overline{7,8,9})


Grafika:TC_M5_Slajd10.png Rachunek podziałów zastosujemy do reprezentacji funkcji boolowskich. Dla funkcji EXTL, której tablicę prawdy powtarzamy na niniejszej planszy jej zapis w postaci podziałów jest następujący:

P_1=(\overline{5}; \overline{1,2,3,4,6,7,8,9})

P_2=(\overline{1,2,6,7,8}; \overline{3,4,5,9})

P_3=(\overline{1,3,5,6}; \overline{2,4,7,8,9})

P_4=(\overline{1,4,5,6,7,8,9}; \overline{2,3})

P_5=(\overline{7}; \overline{1,2,3,4,5,6,8,9})

P_6=(\overline{1,5,7,9}; \overline{2,3,4,6,8})

P_7=(\overline{2,3,6,7,8}; \overline{1,4,5,9})

P_f=(\overline{1,2,3,4}; \overline{5,6,7,8,9})


Grafika:TC_M5_Slajd11.png Jeżeli wektory X_a\, oraz X_b\,: f\,(X_a)\neq f\,(X_b) , różnią się dokładnie dla jednej zmiennej to nazywamy ją zmienną niezbędną. Sens fizyczny zmiennej niezbędnej wynika z faktu, że usunięcie kolumny odpowiadającej tej zmiennej w tablicy prawdy tworzy tablicę, w której dwa takie same wektory mają różne wartości (są sprzeczne).

Grafika:TC_M5_Slajd12.png Na przykładzie funkcji EXTL wyjaśniamy poszukiwanie zmiennych niezbędnych.

Zmiennymi niezbędnymi tej funkcji są x_4\, , x_6\,. Co łatwo sprawdzić, gdyż wiersze o numerach 2 i 8 (zaznaczone kolorem różowym) różnią się wyłącznie na pozycji x_4\,, natomiast wiersze 4 i 9 (zaznaczone kolorem niebieskim) różnią się tylko na pozycji x_6\,.

Po wyznaczeniu zmiennych niezbędnych obliczamy iloczyn podziałów P = P_4\cdot P_6\, .


Grafika:TC_M5_Slajd13.png Iloczyn podziałów wyznaczonych przez zmienne niezbędne ma bardzo ważną interpretację.

Zauważmy, że kolejne bloki iloczynu P = (B_1,...,B_3)\,B_1=\left \{1,5,7,9 \right \} , B_2=\left \{4,6,8\right \} , B_3 = {2,3\}.Blok B_3\, jest zawarty w jednym bloku podziału P_f\,. Ale bloki B_1\, i B_2\, zawierają elementy należące do dwóch różnych bloków podziału P_f\,, czyli same zmienne x_4\, , x_6\, nie wystarczają do oddzielenia wektorów prawdziwych od fałszywych realizowanej funkcji.


Grafika:TC_M5_Slajd14.png Zatem należy się zastanowić jakie argumenty należy dołożyć do argumentów niezbędnych, aby zapewnić jednoznaczną realizację tej funkcji. Obserwując zbiory B_1=\left \{1,5,7,9\right \}, B_2=\left \{4,6,8\right \} , łatwo stwierdzić, że wystarczy w tym celu dobrać takie argumenty, aby „oddzielić” wektory (wiersze) o numerach 1 od 5, 7, 9 oraz 4 od 6, 8. Zatem należy oddzielić 1 od 5, 1 od 7 itd. Zapisujemy zbiory argumentów, dla których różnią się wiersze 1 i 5, 1 i 7 itd. w formie stosownej tabelki (jak na planszy). W tabelce tej zbiór w wierszu oznaczonym 4, 6 pokrywa zbiór z wiersza 1, 9. Zatem wiersz „większy” usuwamy.

Ogólnie usuwamy każdy zbiór Z\, dla którego istnieje Z': Z'\subseteq Z\,. Tak wyznaczana tabelka (w szczególności) zredukowana może być interpretowana jako zadanie obliczania minimalnego pokrycia kolumnowego.


Grafika:TC_M5_Slajd15.png Chcąc zatem obliczyć minimalne zbiory argumentów zapisujemy zredukowaną tabelkę w postaci wyrażenia boolowskiego typu „iloczyn sum”. Kolejną czynnością jest przekształcenie „iloczynu sum” w wyrażenie typu „suma iloczynów” W czynności tej oczywiście stosujemy zasady algebry Boole’a. I w rezultacie uzyskujemy wyrażenie:

x_2x_3+x_2x_5+x_2x_7+x_1x_3x_7+

które interpretujemy następująco. Wszystkie składniki tego wyrażenia o minimalnej liczbie czynników (zmiennych x_i\,) reprezentują minimalne zbiory argumentów, które łącznie ze zmiennymi niezbędnymi tworzą minimalne zbiory argumentów wystarczające do realizacji funkcji:

\left \{x_2, x_3, x_4, x_6\right \}, \left \{x_2, x_3, x_5, x_6\right \}, \left \{x_2, x_3, x_6, x_7\right \} .

Stąd wniosek, że siedmio-argumentowa funkcja f w rzeczywistości jest zależna wyłącznie od czterech argumentów.


Grafika:TC_M5_Slajd16.png Zauważmy też, że ostatnie z podanych rozwiązań oznacza usunięcie z tablicy funkcji f\, kolumn odpowiadających zmiennym x1, x3, x5\, . W rezultacie uzyskujemy tablicę, której wymiary umożliwiają zastosowanie nawet najprostszej metody minimalizacji jaką jest tablica Karnaugha.

Grafika:TC_M5_Slajd17.png Omówioną metodę zrealizowaną w postaci oddzielnego modułu oprogramowania można traktować jako procedurę wspomagająca metodę i program Espresso. W celu przekonania się o skuteczności wspomagania minimalizacji funkcji boolowskich dodatkową procedurą redukcji argumentów omówimy kilka eksperymentów wykonanych programami Espresso i Pandor. W eksperymentach tych dokonamy minimalizacji dwóch typowych funkcji boolowskich: TL27 i KAZ. W szczególności porównamy wyniki minimalizacji uzyskane programem Espresso z wynikami uzyskanymi przy wspomaganiu minimalizacji dodatkową procedura redukcji argumentów.

Grafika:TC_M5_Slajd18.png Eksperyment z funkcją TL27. Na planszy z lewej strony podany jest plik wejściowy programu Espresso z zapisaną funkcją TL27. Z prawej strony tej planszy podany jest wynik minimalizacji tej funkcji programem Espresso. Jak widać espresso minimalizuje tę funkcję do 6 termów (składników iloczynowych) z łączną liczbą 9 argumentów.

Grafika:TC_M5_Slajd19.png Za pomocą programu Pandor można obliczyć, że funkcja ta ma 10 rozwiązań dla minimalnych zbiorów argumentów. Jedno z tych rozwiązań jest podane na planszy. Jest zrozumiałe, że funkcja o mniejszej liczbie argumentów jest „łatwiejsza” do minimalizacji. Zatem tak zredukowaną funkcję można poddać obliczeniom za pomocą programu Pandor.

Grafika:TC_M5_Slajd20.png Porównajmy wyniki tak przeprowadzanych minimalizacji.

Wynik Espresso – 9 argumentów, 6 termów

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

Wynik Pandora – 7 argumentów, 5 termów

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


Grafika:TC_M5_Slajd21.png Eksperyment z funkcją KAZ. Na planszy z lewej strony podany jest plik wejściowy programu Espresso z zapisaną funkcją KAZ. Z prawej strony tej planszy podany jest wynik redukcji argumentów tej funkcji programem Pandor. Jak widać Pandor oblicza, że funkcja ta w rzeczywistości (mimo pierwotnej specyfikacji o 21 argumentach) istotnie zależy wyłącznie od 5 argumentów. Zatem tak zredukowaną funkcję można poddać obliczeniom za pomocą systematycznej procedury ekspansji wbudowanej do programu Pandor.

Grafika:TC_M5_Slajd22.png Możemy więc porównać wynik minimalizacji programem Espresso:

f=\overline{x}_2x_{14}\overline{x}_{19}x_{21}+x_7\overline{x}_8\overline{x}_{12}+x_5x_8\overline{x}_{20}

z minimalizacją systematyczną wspomaganą procedurą redukcji argumentów.

f=\overline{x}_2\overline{x}_4x_9\overline{x}_{19}+\overline{x}_2x_4\overline{x}_9+x_2x_{19}\overline{x}_{20}


</math>