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ę . 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 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 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 . Kostki będziemy oznaczać nieindeksowanymi literami, na przykład , a ich składowe będziemy indeksowali, na przykład . Również, w celu uproszczenia oznaczeń kostki (i wektory) będziemy zapisywać bez przecinków. Na przykład zapiszemy jako .
Kostka to uproszczony zapis zbioru wektorów binarnych. Kostka reprezentuje zbiór wektorów: Kostka reprezentuje również niepełny iloczyn zmiennych binarnych: Na przykład kostkę można zapisać jako |
|
W metodzie ekspansji podobnie jak w standardzie Espresso zbiór wektorów (w ogólności kostek), dla których funkcja oznacza się . Natomiast zbiór tych wektorów (kostek), dla których funkcja oznacza się . |
|
Na planszy przedstawiono tablicę prawdy funkcji boolowskiej 7-argumentowej oraz podano odpowiednie zbiory i tej funkcji. Funkcję tę w dalszej części wykładu oznaczać będziemy EXTL. Wektory zbioru oznaczono symbolami . |
|
Ekspansja jest procesem działającym na kostkach zbiorów i , a jej celem jest uzyskanie dla danej kostki 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 . W swoich obliczeniach Ekspansja wykorzystuje tzw. macierz blokującą . |
|
|
|
|
|
|
|
|
|
|
|
 
|
|
