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$

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---