Dzisiaj jest 23 kwietnia 2025 r.
Chcę dodać własny artykuł
Reklama

Algorytm ekspansji

Chcę dodać własny artykuł

Algorytm ekspansji

Algorytm ekspansji jest kluczowym elementem metody Espresso, służącej do minimalizacji funkcji boolowskich. Jego głównym celem jest maksymalne powiększenie kostek zbioru F przy jednoczesnym uwzględnieniu ograniczeń ze zbioru R.

Przebieg algorytmu

Algorytm składa się z trzech głównych kroków:

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

Macierze blokujące

Macierz blokującą B(ki, R) tworzy się poprzez zanegowanie kolumny j w macierzy R, gdzie j odpowiada elementom kostki ki równym jedynkom. Należy utworzyć macierz blokującą dla każdej kostki ze zbioru F.

Wyznaczenie implikantów prostych

Dla kostki ki wyznaczamy ekspansję k+(L,ki). Jeśli L jest minimalnym pokryciem kolumnowym macierzy blokującej, to k+ jest implikantem prostym funkcji f. Minimalne pokrycia kolumnowe macierzy B1 to L{=}\{4\} oraz L{=}\{5\}.

Kostkę k+(L,k) definiuje się w następujący sposób:

k^+(L,k)=\left\{\begin{align} &k_j, && \mbox{gdy } j \in L \\ &**, && \mbox{w pozostałych przypadkach} \end{align}\right.

Przykład: k^+(\{4\}, k_1) = (***1*) = x_4.

Końcowy krok

Po wyznaczeniu wszystkich implikantów prostych, należy zidentyfikować ich podzbiór, który pokrywa wszystkie kostki ki ze zbioru F. Suma tych implikantów stanowi minimalną realizację zadanej funkcji f(F, R).