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{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}}_{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}, \dots, 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^{'}

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_{i j}]$ , $1 \leq i \leq | R |$ , $1 \leq j \leq n$

w której każdy element $b_{i j} ϵ {0, 1}$ jest definiowany następująco:

$b_{i j} = 1$ , jeśli $k_{j} = 1$ oraz $r_{i j} = 0$ lub $k_{j} = 0$ oraz $r_{i j} = 1$ ;

$b_{i j} = 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_{i j}]

,

i ϵ {1, \dots, w}

,

j ϵ {1, \dots, n}

jest zbiór

L \subseteq {1, \dots, n}

taki, że dla każdego

i ϵ {1, \dots, w}

istnieje

j ϵ L

, dla którego

b_{i j} = 1

. Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje

L^{'} \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{cases} k_{j} & , g d y j ϵ L \\ * & , w p o z o s t a l y c h p r z y p a d k a c h \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)$ .

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{matrix} 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{matrix}]$

Zbiór $L = {4, 7}$ 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 = {2, 3, 6}$ (inne pokrycie kolumnowe), $k^{+} (L, k) = (* 00 * * 1 *) = {\overline{x}}_{2} {\overline{x}}_{3} x_{6}$ .

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}}_{3} x_{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.

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 \leq i \leq n$ ,

gdzie: $k = (k_{1}, \dots, k_{n})$ i $k^{'} = ({k^{'}}_{1}, \dots, {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}

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 = {\overline{x}}_{4} {\overline{x}}_{7} + x_{2} {\overline{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.

TC Moduł 4

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia