Algorytm ekspansji


Algorytm ekspansji w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Algorytm ekspansji – ważny element metody Espresso, która jest używana do minimalizacji funkcji boolowskich. Jednakże używany samodzielnie również prowadzi do znalezienia minimalnej realizacji zadanej funkcji boolowskiej.

Algorytm ekspansji działa na zbiorach F i R (patrz Zapis funkcji boolowskiej w artykule Funkcja boolowska). Jego idea polega na maksymalnym powiększeniu kostek zbioru F. Ograniczeniem są tu kostki ze zbioru R.

Spis treści

Algorytm | edytuj kod

Działanie algorytmu przebiega następująco:

  1. Wyznaczenie macierzy blokujących B(ki, R) dla kiF.
  2. Wyznaczenie implikantów prostych funkcji f=(F, R).
  3. Wyznaczenie zbioru implikantów prostych pokrywających wszystkie kostki ki.

Macierze blokujące | edytuj kod

Macierz blokującą B(ki, R) tworzy się negując j {\displaystyle j} -te kolumny macierzy R przy czym j {\displaystyle j} -te elementy kostki ki są jedynkami. Przykładowo:

k 1 = { 0 0 0 1 0 } R = { 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 } B 1 = { 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 } zanegowana kolumna 4 {\displaystyle {\begin{matrix}k_{1}={\begin{Bmatrix}0&0&0&1&0\end{Bmatrix}}\\[1ex]R={\begin{Bmatrix}1&0&0&0&1\\1&0&1&0&1\\0&1&0&0&1\end{Bmatrix}}\quad B_{1}={\begin{Bmatrix}1&0&0&1&1\\1&0&1&1&1\\0&1&0&1&1\end{Bmatrix}}\\[1ex]{\text{zanegowana kolumna}}-4\end{matrix}}}

Należy wyznaczyć macierz blokującą dla każdej kostki ze zbioru F.

Wyznaczenie implikantów prostych | edytuj kod

Dla danej kostki ki wyznaczamy ekspansje k+(L,ki). Jeśli L jest minimalnym pokryciem kolumnowym macierzy blokującej, to k+ jest implikantem prostym funkcji f.

Należy zatem znaleźć minimalne pokrycia kolumnowe macierzy Bi. Dla macierzy B1, wyznaczonej powyżej, minimalnymi pokryciami kolumnowymi są L = { 4 } {\displaystyle L{=}\{4\}} i L = { 5 } . {\displaystyle L{=}\{5\}.} Zauważmy, że istnieje też pokrycie L = { 1 , 2 } , {\displaystyle L{=}\{1,2\},} ale nie jest to pokrycie minimalne.

Kostkę k+(L,k) wyznacza się następująco:

k + ( L , k ) = { k j , gdy  j L , w pozostalych przypadkach {\displaystyle k^{+}(L,k)=\left\{{\begin{aligned}&k_{j},&&{\mbox{gdy }}j\in L\\&**,&&{\mbox{w pozostalych przypadkach}}\end{aligned}}\right.}

Zatem: k + ( { 4 } , k 1 ) = ( 1 ) = x 4 . {\displaystyle k^{+}(\{4\},k_{1})=(***1*)=x_{4}.}

Końcowy krok | edytuj kod

Gdy mamy już wyznaczone wszystkie implikanty proste, należy wyznaczyć taki ich podzbiór, który pokrywa wszystkie kostki ki ze zbioru F. Suma tych implikantów będzie minimalną realizacją zadanej funkcji f(F, R).

Na podstawie artykułu: "Algorytm ekspansji" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy