Algorytm ekspansji

Algorytm ekspansji

Algorytm ekspansji to składnik metody Espresso, która służy do minimalizacji funkcji boolowskich. Samodzielnie również umożliwia znalezienie minimalnej realizacji określonej funkcji boolowskiej.

Algorytm ten operuje na zbiorach F oraz R (więcej informacji w sekcji Zapis funkcji boolowskiej w artykule Funkcja boolowska). Jego głównym celem jest maksymalne powiększenie kostek zbioru F, przy jednoczesnym uwzględnieniu ograniczeń wynikających z kostek ze zbioru R.

Algorytm

Proces działania algorytmu przebiega według następujących kroków:

• Wyznaczenie macierzy blokujących B(ki, R) dla ki∈F.
• Wyznaczenie implikantów prostych funkcji f=(F, R).
• Określenie zbioru implikantów prostych, które pokrywają wszystkie kostki ki.

Macierze blokujące

Macierz blokującą B(ki, R) tworzy się poprzez negację

j-tej kolumny macierzy R, gdzie j-te elementy kostki ki są jedynkami. Przykład:

k₁ = {0, 0, 0, 1, 0}

R = {1, 0, 0, 0, 1; 1, 0, 1, 0, 1; 0, 1, 0, 0, 1}

B₁ = {1, 0, 0, 1, 1; 1, 0, 1, 1, 1; 0, 1, 0, 1, 1}

zanegowana kolumna – 4

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

Wyznaczenie implikantów prostych

Dla danej kostki ki należy określić ekspansję k+(L, ki). Jeśli L jest minimalnym pokryciem kolumnowym macierzy blokującej, wówczas k+ jest implikantem prostym funkcji f.

W związku z tym, ważne jest znalezienie minimalnych pokryć kolumnowych macierzy B_i. Dla wcześniej wyznaczonej macierzy B₁, minimalnymi pokryciami kolumnowymi są:

• L = {4}
• L = {5}.

Zauważmy, że istnieje również pokrycie L = {1, 2}, jednak nie jest ono minimalne.

Kostkę k+(L, k) wyznacza się według następującego wzoru:

k⁺(L, k) = {k_j, gdy j ∈ L; , w pozostałych przypadkach}

Zatem:

k⁺({4}, k₁) = (*1*) = x₄.

Końcowy krok

Po zidentyfikowaniu wszystkich implikantów prostych, należy wyznaczyć taki ich podzbiór, który pokrywa wszystkie kostki ki ze zbioru F. Suma tych implikantów będzie minimalną realizacją określonej funkcji f(F, R).