TC Moduł 4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
TC M4 Slajd1.png Minimalizacja funkcji boolowskich metodą ekspansji.

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

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.


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.

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

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


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 oznacza się . Natomiast zbiór tych wektorów (kostek), dla których funkcja oznacza się .

TC M4 Slajd7.png 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 .

TC M4 Slajd8.png 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ą .

TC M4 Slajd9.png Macierzą blokującą (kostkę k) nazywać będziemy macierz:

, ,

w której każdy element jest definiowany następująco:

, jeśli oraz lub oraz  ;

, w pozostałych przypadkach.

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


TC M4 Slajd10.png Wyznaczymy macierz blokującą dla kostki funkcji EXTL z planszy 7. Macierze i tej funkcji podane są ponownie na niniejszej planszy. Zgodnie z definicją, skoro , to dla uzyskania wystarczy w macierzy „zanegować” kolumny drugą, piątą i siódmą, co zaznaczono odpowiednimi kolorami.

TC M4 Slajd11.png Pokryciem kolumnowym macierzy , , jest zbiór taki, że dla każdego istnieje , dla którego . Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje , który jest pokryciem macierzy .

TC M4 Slajd12.png Obliczenia pokrycia kolumnowego omówimy na przykładzie macierzy blokującej wyznaczonej dla kostki . Dla tak obliczonej macierzy , (kolumny macierzy B są numerowane od lewej do prawej) jest minimalnym pokryciem kolumnowym. Natomiast , oraz nie są pokryciami kolumnowymi tej macierzy.

TC M4 Slajd13.png Macierz blokująca pozwala wyznaczyć rozwinięcie (ekspansję) kostki oznaczane w sposób następujący:

Można wykazać, że jest implikantem funkcji . W szczególności jest implikantem prostym, gdy jest minimalnym pokryciem kolumnowym macierzy .


TC M4 Slajd14.png Kontynuujemy obliczenia dla funkcji EXTL. Dla kostki odpowiednia macierz blokująca jest:



Zbiór jest pokryciem kolumnowym B, a więc , czyli implikantem jest . Natomiast dla (inne pokrycie kolumnowe), .


TC M4 Slajd15.png Postępując podobnie dla pozostałych kostek uzyskujemy następujące zbiory implikantów prostych funkcji :


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.


TC M4 Slajd16.png W celu utworzenia tablicy implikantów prostych skorzystamy z relacji pokrycia dla kostek:


wtedy i tylko wtedy, gdy lub dla każdego , ,

gdzie: i .

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


TC M4 Slajd17.png Tablicę implikantów prostych konstruujemy w następujący sposób. Jeśli implikant pokrywa kostkę , to na przecięciu wiersza wiersza z kolumną 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


TC M4 Slajd18.png Minimalny zbiór implikantów prostych reprezentujących funkcję 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 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 , . Czyli .

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.


TC M4 Slajd20.pngTC 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.



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.