TC Moduł 4: Różnice pomiędzy wersjami

Wersja z 22:44, 28 sie 2006

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.

@@ Linia 103: / Linia 103: @@
 {| border="0" cellpadding="4" width="100%"
 |valign="top" width="450px"|[[Grafika:TC_M4_Slajd11.png]]
-|valign="top"|Pokryciem kolumnowym macierzy <math>B=[b_{ij}]</math>, <math>i\epsilon left \{1,...,w\right \}\,</math>, <math>j\epsilon left \{1,...,n\right \}\,</math> jest zbiór <math>L\subseteq left \{1,...,n\right \}\,</math> taki, że dla każdego <math>i\epsilon left \{1,...,w\right \}\,</math> istnieje <math>j\epsilon L\,</math> , dla którego <math>b_{ij} = 1</math> . Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje <math>L' \subseteq L\,</math>, który jest pokryciem macierzy <math>B\,</math>.
+|valign="top"|Pokryciem kolumnowym macierzy <math>B=[b_{ij}]</math>, <math>i\epsilon \left \{1,...,w\right \}\,</math>, <math>j\epsilon \left \{1,...,n\right \}\,</math> jest zbiór <math>L\subseteq \left \{1,...,n\right \}\,</math> taki, że dla każdego <math>i\epsilon \left \{1,...,w\right \}\,</math> istnieje <math>j\epsilon L\,</math> , dla którego <math>b_{ij} = 1</math> . Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje <math>L' \subseteq L\,</math>, który jest pokryciem macierzy <math>B\,</math>.
 |}
@@ Linia 111: / Linia 111: @@
 {| border="0" cellpadding="4" width="100%"
 |valign="top" width="450px"|[[Grafika:TC_M4_Slajd12.png]]
-|valign="top"|
+|valign="top"|Obliczenia pokrycia kolumnowego omówimy na przykładzie macierzy blokującej wyznaczonej dla kostki <math>k_2\,</math>. Dla tak obliczonej macierzy <math>B\,</math> , <math>L= \left \{2,3,6\right \}\,</math> (kolumny macierzy B są numerowane od lewej do prawej) jest minimalnym pokryciem kolumnowym. Natomiast <math>L= \left \{2, 3\right \}\,</math> ,  <math>L= \left \{2,6\right \}\,</math> oraz  <math>L= \left \{3,6\right \}\,</math> nie są pokryciami kolumnowymi tej macierzy.
 |}

TC Moduł 4: Różnice pomiędzy wersjami

Wersja z 22:44, 28 sie 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia