TC Moduł 4

From Studia Informatyczne

Grafika:TC_M4_Slajd1.png Minimalizacja funkcji boolowskich metodą ekspansji.

Grafika:TC_M4_Slajd2.png Kolejną klasyczną metodą minimalizacji funkcji boolowskich jest metoda Quine’a-McCluskey’a . Jest ona wykonywana w dwóch etapach:

a) generacji implikantów prostych,

b) selekcji minimalnego zbioru implikantów wiernie reprezentującego funkcję f\,.

Mimo dużej złożoności obliczeniowej każdego z wyżej wymienionych etapów, metoda Quine’a-McCluskey’a jest najczęściej nauczaną metodą minimalizacji, głównie ze względu na podstawowy charakter jej procedur. Niestety – podobnie jak w przypadku tablic Karnaugha – jest to metoda absolutnie nieprzydatna do algorytmicznych obliczeń komputerowych. Dla potrzeb komputerowych systemów projektowania układów cyfrowych opracowano wiele nowych metod minimalizacji funkcji boolowskich. Najbardziej znaną i uznawaną za najskuteczniejszą jest metoda ESPRESSO opracowana w latach 80. na Uniwersytecie Kalifornijskim w Berkeley.


Grafika:TC_M4_Slajd3.png Metoda Espresso polega na iteracyjnym stosowaniu różnych procedur, z których najważniejsze to Ekspansja (Expand), Pokrycie nienadmiarowe (Irredundant Cover) i Uzupełnienie (Complement). Są to bardzo złożone procedury, których omówienie przekracza zakres niniejszego wykładu. Ich pełny opis można znaleźć w książce Brayton R., Hachtel G.D., McMullen C., and Sangiovanni-Vincentelli A.: Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston, 1984 lub w podręczniku Synteza układów logicznych.

Grafika:TC_M4_Slajd4.png Najprostszą i najogól¬niejszą procedurą metody ESPRESSO jest procedura Ekspansji. Sama procedura ekspansji wykorzystuje znaną od dawna metodę powiększania mintermu k \epsilon F\, w taki sposób, aby powiększona kostka nie zawierała żadnego mintermu należącego do zbioru wektorów zerowych funkcji. Ponieważ właściwie powiększony minterm zbioru F\, może być implikantem funkcji, odpowiednio zmodyfikowana metoda ekspansji może być stosowana autonomicznie jako niezależna metoda minimalizacji funkcji boolowskich. Metoda ta została zrealizowana w programie PANDOR. Program ten jest udostępniony na stronie internetowej www.zpt.tele.pw.edu.pl w katalogu OPROGRAMOWANIE.

Grafika:TC_M4_Slajd5.png Pojęciem podstawowym w metodzie ekspansji jest – podobnie jak w innych metodach minimalizacji – pojęcie kostki. Kostkami nazywać będziemy ciągi elementów ze zbioru \left \{0, 1, *\right \} . Kostki będziemy oznaczać nieindeksowanymi literami, na przykład k\, , a ich składowe będziemy indeksowali, na przykład k_i\, . Również, w celu uproszczenia oznaczeń kostki (i wektory) będziemy zapisywać bez przecinków. Na przykład (*,1,*,0,1)\, zapiszemy jako (*1*01)\,.

Kostka to uproszczony zapis zbioru wektorów binarnych. Kostka K=(0*1*) reprezentuje zbiór wektorów:

\begin{matrix} 0010 \\ 0011 \\ 0110 \\ 0111 \end{matrix}

Kostka reprezentuje również niepełny iloczyn zmiennych binarnych: Na przykład kostkę K=0*1* można zapisać jako \overline{x}_1x_3\,


Grafika:TC_M4_Slajd6.png W metodzie ekspansji podobnie jak w standardzie Espresso zbiór wektorów (w ogólności kostek), dla których funkcja f=1\, oznacza się F\,. Natomiast zbiór tych wektorów (kostek), dla których funkcja f=0\, oznacza się R\,.

Grafika:TC_M4_Slajd7.png Na planszy przedstawiono tablicę prawdy funkcji boolowskiej 7-argumentowej oraz podano odpowiednie zbiory F\, i R\, tej funkcji. Funkcję tę w dalszej części wykładu oznaczać będziemy EXTL. Wektory zbioru F\, oznaczono symbolami k_1,...,k_5\, .

Grafika:TC_M4_Slajd8.png Ekspansja jest procesem działającym na kostkach zbiorów F\, i R\,, a jej celem jest uzyskanie dla danej k \epsilon F\, kostki k'\, tak dużej, jak to tylko możliwe (tzn. z możliwie dużą liczbą pozycji o wartości *\,) i nie pokrywającej żadnego wektora zbioru R\,. W swoich obliczeniach Ekspansja wykorzystuje tzw. macierz blokującą B\,.

Grafika:TC_M4_Slajd9.png Macierzą blokującą (kostkę k) nazywać będziemy macierz:

B(k,R)=[b_{ij}] , 1\le i\le |R|\, , 1\le j\le n\,

w której każdy element b_{ij}\epsilon \left \{0,1\right \} jest definiowany następująco:

b_{ij}=1 , jeśli k_j=1 oraz r_{ij}=0 lub k_j=0 oraz r_{ij}=1 ;

b_{ij}=0, w pozostałych przypadkach.

W przypadku funkcji opisanej wektorami binarnymi macierz blokująca dla danej kostki k \epsilon F\, powstaje z macierzy R\, przez zanegowanie tych kolumn R\,, których pozycje są wyznaczone przez pozycje jedynek w kostce k \epsilon F\,.


Grafika:TC_M4_Slajd10.png Wyznaczymy macierz blokującą dla kostki k_1\, funkcji EXTL z planszy 7. Macierze F\, i R\, tej funkcji podane są ponownie na niniejszej planszy. Zgodnie z definicją, skoro k_1=(0100101), to dla uzyskania B\, wystarczy w macierzy R\, „zanegować” kolumny drugą, piątą i siódmą, co zaznaczono odpowiednimi kolorami.

Grafika:TC_M4_Slajd11.png Pokryciem kolumnowym macierzy B=[b_{ij}], i\epsilon \left \{1,...,w\right \}\,, j\epsilon \left \{1,...,n\right \}\, jest zbiór L\subseteq \left \{1,...,n\right \}\, taki, że dla każdego i\epsilon \left \{1,...,w\right \}\, istnieje j\epsilon L\, , dla którego b_{ij} = 1 . Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje L' \subseteq L\,, który jest pokryciem macierzy B\,.

Grafika:TC_M4_Slajd12.png Obliczenia pokrycia kolumnowego omówimy na przykładzie macierzy blokującej wyznaczonej dla kostki k_2\,. Dla tak obliczonej macierzy B\, , L= \left \{2,3,6\right \}\, (kolumny macierzy B są numerowane od lewej do prawej) jest minimalnym pokryciem kolumnowym. Natomiast L= \left \{2, 3\right \}\, , L= \left \{2,6\right \}\, oraz L= \left \{3,6\right \}\, nie są pokryciami kolumnowymi tej macierzy.

Grafika:TC_M4_Slajd13.png Macierz blokująca B(k,R)\, pozwala wyznaczyć rozwinięcie (ekspansję) kostki k\, oznaczane k^{+}(L,k)\, w sposób następujący:

k^{+}_j = \begin{cases}k_j & ,gdy\, j\,\epsilon\, L \\ * & ,w\, pozostalych\, przypadkach \end{cases}

Można wykazać, że k^{+}(L,k)\, jest implikantem funkcji f=(F,R)\,. W szczególności k^{+}(L,k)\, jest implikantem prostym, gdy L\, jest minimalnym pokryciem kolumnowym macierzy B(k,R)\,.


Grafika:TC_M4_Slajd14.png Kontynuujemy obliczenia dla funkcji EXTL. Dla kostki k_2=(1000110) odpowiednia macierz blokująca B=B(k_2, R) jest:


\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \end{matrix}

B=\,\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}


Zbiór L= \left \{4,7\right \}\, jest pokryciem kolumnowym B, a więc k^{+}(L,k)=(***0**0) , czyli implikantem F\, jest \overline{x}_4\overline{x}_7\, . Natomiast dla L= \left \{2,3,6\right \}\, (inne pokrycie kolumnowe), k^{+}(L,k)=(*00**1*)=\overline{x}_2\overline{x}_3x_6 .


Grafika:TC_M4_Slajd15.png Postępując podobnie dla pozostałych kostek uzyskujemy następujące zbiory implikantów prostych funkcji F\,:


\begin{matrix} I_1=\overline{x}_1 & I_3=\overline{x}_4\overline{x}_7 & I_5=\overline{x}_5 & I_7=x_3\overline{x}_6 \\ I_2=x_2\overline{x}_6 & I_4=\overline{x}_2\overline{x}_3x_6 & I_6=\overline{x}_6\overline{x}_7 \end{matrix}

Spośród obliczonych implikantów prostych należy teraz wyselekcjonować minimalny podzbiór implikantów pokrywający wszystkie wektory prawdziwe realizowanej funkcji. Proces selekcji wykonuje się za pośrednictwem tzw. tablicy implikantów prostych.


Grafika:TC_M4_Slajd16.png W celu utworzenia tablicy implikantów prostych skorzystamy z relacji pokrycia dla kostek:


k \subseteq k'\, wtedy i tylko wtedy, gdy k_i= {k'}_i\, lub {k'}_i=* dla każdego i\, , 1\le i\le n\, ,

gdzie: k=(k_1,...,k_n) i k'=({k'}_1,...,{k'}_n) .

Na tej podstawie dla każdego obliczonego w poprzednim etapie implikanta (ale interpretowanego jako kostka) wyznaczamy wszystkie kostki zbioru F\, pokrywane przez ten implikant. Przykładowo

I_1=\overline{x}_1\supseteq k_1
I_2=x_2\overline{x}_6\supseteq k_1,\, k_5
I_3=\overline{x}_4\overline{x}_7\supseteq k_2,\, k_3,\, k_4\,

Grafika:TC_M4_Slajd17.png Tablicę implikantów prostych konstruujemy w następujący sposób. Jeśli implikant I_j\, pokrywa kostkę k_i\, , to na przecięciu wiersza wiersza k_i\, z kolumną I_j\, piszemy 1, w przeciwnym przypadku piszemy 0.

Tablica implikantów prostych umożliwia wybór (selekcję) takiego minimalnego zbioru implikantów, który pokrywa wszystkie kostki funkcji pierwotnej


Grafika:TC_M4_Slajd18.png Minimalny zbiór implikantów prostych reprezentujących funkcję f\, można wyznaczyć obliczając minimalne pokrycie kolumnowe tablicy implikantów prostych. W tym celu zapisujemy wiersze tablicy w postaci zbiorów kolumn wskazywanych przez pozycje jedynek w danym wierszu, a następnie zauważając, że implikant I_3\, tworzy zbiór jednoelementowy wykreślamy wiersze z tym implikantem. Po takiej redukcji wierszy spostrzegamy, że I2 jest wspólny dla obu wierszy. Zatem minimalne pokrycie tworzą implikanty I_2\, , I_3\,. Czyli f=\overline{x}_4\overline{x}_7+x_2\overline{x}_6 .

Grafika:TC_M4_Slajd19.png Analogiczny wynik obliczy program PANDOR.

Pandor jest akademickim narzędziem minimalizacji funkcji boolowskich zmodyfikowaną metodą ekspansji z zastosowaniem dodatkowej procedury redukcji argumentów. Pandor został opracowany w ramach pracy dyplomowej Mirosława Cagary w Ośrodku Kształcenia na Odległość OKNO Politechniki Warszawskiej. Program Pandor jest dostępny na stronie internetowej www.zpt.tele.pw.edu.pl, a także na stronie internetowej jego autora www.domicil.pl.


Grafika:TC_M4_Slajd20.pngGrafika:TC_M4_Slajd21.png Również program ESPRESSO obliczy taki sam wynik. Zapis funkcji EXTL w standardzie Espresso podano na planszach 20 i 21. Więcej informacji na temat standardu Espresso można znaleźć w książce Synteza układów logicznych.

Taki sam wynik minimalizacji funkcji EXTL w programie PANDOR (wyposażonym tylko w jedną procedurę ekspansji) oraz w programie ESPRESSO (zbudowanym z wielu procedur) nasuwa wątpliwości. Dlaczego program PANDOR za pomocą jednej procedury minimalizuje tak samo dobrze jak ESPRESSO zbudowane z wielu procedur.



Grafika:TC_M4_Slajd22.png Barierą ograniczającą obliczenia systematyczną metodą zastosowaną w Pandorze jest ogromna złożoność obliczeniowa zarówno w procesie generacji, jak też w procesie obliczania pokrycia kolumnowego.

Program PANDOR został stworzony po to, aby naocznie zaobserwować zjawisko wzrostu złożoności obliczeniowej wraz ze wzrostem liczby argumentów funkcji.

Funkcja EXTL ma 7 implikantów (Pandor dokonuje lepszej selekcji i oblicza ich zaledwie 5). W tym przypadku obliczenie minimalnego pokrycia kolumnowego jest zadaniem łatwym. Ale już dla bardziej skomplikowanych funkcji takich jak TL27 i KAZ, których tablice w standardzie Espresso są podane na planszy, sytuacja jest całkiem inna – właśnie ze względu na dużą liczbę implikantów. Czas obliczeń programem PANDOR jest drastycznie większy od czasu obliczeń programem Espresso. Oczywiście Espresso nie zawsze poda wynik minimalny. W celu uzyskania minimalnych rozwiązań w rozsądnym czasie obliczeń w programie PANDOR zastosowano procedurę redukcji argumentów. Jej wpływ na proces minimalizacji omówimy w następnym wykładzie.