TC Moduł 4

Minimalizacja funkcji boolowskich metodą ekspansji.

---

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.

---

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.

---

Najprostszą i najogól¬niejszą procedurą metody ESPRESSO jest procedura Ekspansji. Sama procedura ekspansji wykorzystuje znaną od dawna metodę powiększania mintermu $kϵ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.

---

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 $\{0,1,*\}$ . 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{array}{c}0010\\ 0011\\ 0110\\ 0111\end{array}$ Kostka reprezentuje również niepełny iloczyn zmiennych binarnych: Na przykład kostkę $K=0*1*$ można zapisać jako ${\bar{x}}_1{x}_3$

---

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$.

---

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$ .

---

Ekspansja jest procesem działającym na kostkach zbiorów $F$ i $R$, a jej celem jest uzyskanie dla danej $kϵF$ kostki $k^{\prime }$ 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$.

---

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}ϵ\{0,1\}$ 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ϵF$ powstaje z macierzy $R$ przez zanegowanie tych kolumn $R$, których pozycje są wyznaczone przez pozycje jedynek w kostce $kϵF$.

---

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.

---

Pokryciem kolumnowym macierzy $B=[b_{ij}]$, $iϵ\{1,...,w\}$, $jϵ\{1,...,n\}$ jest zbiór $L\subseteq \{1,...,n\}$ taki, że dla każdego $iϵ\{1,...,w\}$ istnieje $jϵL$ , dla którego $b_{ij}=1$ . Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje $L^{\prime }\subseteq L$, który jest pokryciem macierzy $B$.

---

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

---

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{array}{ll}{k}_j& ,gdyjϵL\\ *& ,wpozostalychprzypadkach\end{array}$ 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)$.

---

Kontynuujemy obliczenia dla funkcji EXTL. Dla kostki $k_2=(1000110)$ odpowiednia macierz blokująca $B=B(k_2,R)$ jest: $\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ \end{array}$ $B=\left[\begin{array}{ccccccc}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{array}\right]$ Zbiór $L=\{4,7\}$ jest pokryciem kolumnowym B, a więc $k^{+}(L,k)=(***0**0)$ , czyli implikantem $F$ jest ${\bar{x}}_4{\bar{x}}_7$ . Natomiast dla $L=\{2,3,6\}$ (inne pokrycie kolumnowe), $k^{+}(L,k)=(*00**1*)={\bar{x}}_2{\bar{x}}_3{x}_6$ .

---

Postępując podobnie dla pozostałych kostek uzyskujemy następujące zbiory implikantów prostych funkcji $F$: $\begin{array}{cccc}{I}_1={\bar{x}}_1& I_3={\bar{x}}_4{\bar{x}}_7& I_5={\bar{x}}_5& I_7=x_3{\bar{x}}_6\\ I_2=x_2{\bar{x}}_6& I_4={\bar{x}}_2{\bar{x}}_3{x}_6& I_6={\bar{x}}_6{\bar{x}}_7\end{array}$ 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.

---

W celu utworzenia tablicy implikantów prostych skorzystamy z relacji pokrycia dla kostek: $k\subseteq k^{\prime }$ wtedy i tylko wtedy, gdy $k_i={k^{\prime }}_i$ lub ${k^{\prime }}_i=*$ dla każdego $i$ , $1\le i\le n$ , gdzie: $k=(k_1,...,k_n)$ i $k^{\prime }=({k^{\prime }}_1,...,{k^{\prime }}_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={\bar{x}}_1\supseteq k_1$ $I_2=x_2{\bar{x}}_6\supseteq k_1,k_5$ $I_3={\bar{x}}_4{\bar{x}}_7\supseteq k_2,k_3,k_4$

---

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

---

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={\bar{x}}_4{\bar{x}}_7+x_2{\bar{x}}_6$ .

---

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.

---

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.

---

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.

---