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}, . . ., 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, . . ., 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_{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 . Natomiast dla $L = {2, 3, 6}$ (inne pokrycie kolumnowe), $k^{+} (L, k) = (* 00 * * 1 *)$ .

TC Moduł 4

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia