Wykład 3

Układy elektroniczne

1

Minimalizacja funkcji
boolowskich

Minimalizacja funkcji boolowskich - polega na

znalezieniu dla danej funkcji formuły minimalnej,
która jest jak najmniej skomplikowana. Przy
porównywaniu stopnia skomplikowania reguł
wprowadza się pojęcie współczynnika
skomplikowania.

Dla funkcji boolowskiej zapisanej przy pomocy

kanonicznej postaci sumy, współczynnik
skomplikowania jest równy sumie liczby mnożeń i
sumie liczby dodawań.

W syntezie logicznej, minimalizację funkcji

boolowskich stosuje się w celu zredukowania
liczby potrzebnych zasobów (bramek logicznych,
bloków bramek) do realizacji danej funkcji.

2

Metody minimalizacji funkcji
boolowskich

Tradycyjne:

1.

metoda Karnaugh,

2.

metoda Quine'a-McCluskeya,

3.

metoda iteracyjnego konsensusu

4.

metoda Espresso (oparta na algorytmie
ekspansji)

Do syntezy logicznej:

1.

dekompozycja funkcji boolowskich

2.

redukcja argumentów

3

Budowa bramek podstawowych
z samych bramek NAND

4

Budowa bramek podstawowych
z samych bramek NOR

5

Negacja bramek logicznych

6

Kanoniczna postać sumy
(suma iloczynów)

Forma skrócona:

7

Kanoniczna postać iloczynu
(iloczyn sum)

Forma skrócona:

8

Budowa z bramek NAND, NOR
funkcji boolowskich postaci
kanonicznych

9

Realizacja postaci
kanonicznych

10

?

?

Kanoniczna postać sumy
(suma iloczynów)

Kanoniczna postać iloczynu
(iloczyn sum)

Kod Graya

1
1

dwubitowy

Kod Graya – zapis wszystkich
liczb binarnych (o określonej
długości – liczbie bitów) w takiej
kolejności, że kolejne słowa
kodowe różnią się tylko stanem
jednego bitu.

trzybitowy

Metoda Karnaugh

12

Algorytm metody Karnaugh

1.

Zapis w formie tabeli Karnaugh, używając
kodu Greya.

2.

Zaznaczenie (możliwie największych) skupisk
jedynek i wartości nieustalonych

(zakładając

realizację przy użyciu bramek NAND).

Skupiska mogą się

pokrywać.

3.

Wybór możliwie najmniejszej liczby skupisk,
takich, by wszystkie jedynki były tam zawarte.

4.

Zapis funkcji zminimalizowanej.

13

Metoda Karnaugh – 3
zmienne

Tabela prawdy

14

Metoda Karnaugh – 4
zmienne



f(x

1

,x

2

,x

3

,x

4

) = Σ[2,3,6,7,8,10,11,15,(0,13)]

15

Metoda Quine’a-
McCluskeya

16

Metoda Quine’a-
McCluskeya

Cechy:



Dużo łatwiejsza do zaimplementowania jako algorytm
komputerowy od metody Karnaugha



znajduje minimalną postać dysjunkcyjną (sumę
iloczynów)



Użyteczna w minimalizacji manualnej do około 6
zmiennych wejściowych, jednak bardziej pracochłonna
(dla prostych funkcji) od metody Karnaugh

17

Algorytm metody Quine’a-
McCluskeya

1.

Wypisujemy w jednej kolumnie wektory wejściowe odpowiadające jedynkom
oraz wartościom nieustalonym.

2.

Grupujemy te wektory rosnąco według ilości jedynek w wektorze.

3.

Porównujemy wektory o o k-tej liczbie jedynek z wektorami o k+1 liczbie
jedynek i łączymy te które różnią się tylko jednym bitem (np. 0100 oraz 0101),
i zapisujemy wynikowe wektory (postaci np. 010*). Plusem oznaczamy
„połączone” wektory.

4.

Analogicznie tworzymy następne tabele dopóki występują możliwości łączenia.

5.

Wypisujemy nieoznaczone plusem implikanty jako wiersze tabeli, kolumny
tabeli to wartości dziesiętne „jedynek”. Na przecięciach w tabeli oznaczmy
„kółkami” związek między implikantem i wektorem wejściowym – „kółkiem
pełnym” dla implikantów bez wartości nieustalonych, a „kółkiem pustym” dla
implikantów zawierających w sobie wartości nieustalone.

6.

Znajdujemy kolumny z jednym „kołem pełnym” i oznaczamy cały wiersz
odpowiedniego implikantu. Jeżeli są nieoznaczone kolumny to powtarzamy dla
kolumn z dwoma (itd.) „kołami pełnymi”. Gdy skończą się kółka pełne
analogicznie postępujemy z „kółkami pustymi”.

<przykład>

18

Metoda iteracyjnego
konsensusu

19

Metoda iteracyjnego
konsensusu

Metoda to rozpoczyna się od implikantów funkcji (mogą to

być dowolne implikanty, w szczególności iloczyny zupełne).

Metoda iteracyjnego konsensusu to iteracyjne wykonanie

następujących kroków:

1.

Usuń z postaci dysjunkcyjnej wszystkie pokryte implikanty

2.

Wygeneruj wszystkie (niepuste i różne od 0) konsensusy z
par iloczynów. Dodaj je do postaci dysjunkcyjnej. Przejdź
do kroku 1.

Algorytm kończy się w momencie, gdy nie możemy

wygenerować nowych konsensusów, ponieważ uzyskane
iloczyny to implikanty proste.

20