Wykład 3
Układy elektroniczne
1
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