Piotr Kawalec

Wykład V - 1

Wykład V

Minimalizacja funkcji

logicznych

metodą Quin’a - Mc

Cluskey’a

Technika cyfrowa

Piotr Kawalec

Wykład V - 2

Technika cyfrowa

Plan wykładu



Cechy metody



Wyznaczanie implikantów

prostych



Tworzenie tablic implikantów



Wyznaczanie postaci minimalnej funkcji



Dziesiętna metoda minimalizacji funkcji

logicznych

Piotr Kawalec

Wykład V - 3

Technika cyfrowa

Cechy metody



Metoda analityczna



Stosowana przy większej liczbie zmiennych



Oddzielnie wyznacza się



minimalną normalną postać sumy

PNS



minimalną normalną postać iloczynu

PNI

Piotr Kawalec

Wykład V - 4

Technika cyfrowa

Algorytm metody Quin’a - Mc
Cluskey’a (bin)



Dla wyznaczenia minimalnej PNS należy:

 binarne wartości argumentów dla których

funkcja

jest równa

1

lub

nieokreślona

należy wypisać

w

kolumnie porządkując wg. liczby jedynek

(indeksów);



Porównuje się kolejne ciągi jednej grupy ze

wszystkimi ciągami następnej grupy, łącząc ze

sobą

ciągi różniące się jedną cyfrą. Ciągi te się

oznacza

(co oznacza że nie są prostymi implikantami);

Piotr Kawalec

Wykład V - 5

Technika cyfrowa

 Otrzymany w wyniku połączenia ciąg zapisuje

się w

następnej kolumnie umieszczając

kreskę

w

miejscu

różnych cyfr;



W kolumnie tej wypisuje się wszystkie wyniki

połączeń dokonanych w kolumnie 1,

oddzielając

wyniki porównań poszczególnych grup;



Procedurę łączenia kontynuuje się dla kolumny

2

łącząc ciągi sąsiednich grup różniące się jedną

cyfrą;



Wyniki połączeń zapisuje się w następnej

kolumnie;

Piotr Kawalec

Wykład V - 6

Technika cyfrowa



Opisaną procedurę kontynuuje się do

zrealizowania

wszystkich połączeń;



W wyniku tych działań uzyskuje się zbiór

wszystkich

prostych implikantów;

 Dla znaleziena postaci końcowych funkcji należy

zbudować tablicę Quine’a;


Wiersze tablicy odpowiadają

prostym

implikantom;

a kolumny zespołom wartości zmiennych dla

których

funkcja ma wartość

1;

 W tablicy zaznacza się jakie 1 pokrył dany

implikant;

Piotr Kawalec

Wykład V - 7

Technika cyfrowa



Ze zbioru wszystkich prostych implikantów

wybieramy te które są niezbędne do pokrycia

wszystkich jedynek funkcji, a więc wszystkich

kolumn w tablicy;

 Jeśli jakaś wartość funkcji jest pokrywana tylko

przez

jeden

prosty implikant to jest on

zasadniczym

implikantem prostym

i musi być wzięty do zapisu

funkcji;


Jeżeli zasadnicze implikanty proste nie

pokrywają

wszystkich jedynek funkcji to należy dołączyć

dodatkowe implkanty zapewniające to pokrycie;

Piotr Kawalec

Wykład V - 8

Technika cyfrowa

Przykład minimalizacji funkcji



Zminimalizować metodą binarną Quine’a

Mc Cluskey’a funkcję

y= f(x

4

, x

3

, x

2

,

x

1

) = [0,1,5,8,9,10,13,15,

(2)]

Piotr Kawalec

Wykład V - 9

Technika cyfrowa

Algorytm metody Quin’a - Mc Cluskey’a
(dec)



Dla wyznaczenia minimalnej PNS należy:

 odpowiedniki dziesiętne zespołów wartości

argumentów

dla których funkcja jest równa

1

lub

nieokreślona

,

dzieli

się na grupy o jednakowych indeksach i wypisuje

w kolumnie;



Porównuje się parami wszystkie liczby z sąsiednich

grup,

różniące się o potęgę dwójki, przy czym liczba

należąca

do grupy o

niższym

indeksie musi być

mniejsza

;

Piotr Kawalec

Wykład V - 10

Technika cyfrowa

 Jeśli porównywane liczby różnią się o

potęgę

dwójki

(a więc dają się połączyć), zapisuje się je

rosnąco

w następnej kolumnie, a za nimi w nawiasie -

ich

różnicę;



Czynność

łączenia prowadzi się dla wszystkich

grup

pierwszej kolumny;



W nowo utworzonej kolumnie porównuje się

pierwsze

liczby w wierszach sąsiednich grup

analogicznie jak

poprzednio;

Piotr Kawalec

Wykład V - 11

Technika cyfrowa



Wiersze, w których liczby w nawiasach są

jednakowe,
a pierwsze liczby różnią się o potęgę dwójki,
łączy się

ze sobą i umieszcza w kolejnej

kolumnie;

 Liczby muszą być wypisane w porządku
rosnącym,
a w nawiasie rosnąco wypisuje się różnice z
nawiasów
łączonych liczb oraz różnicę pierwszych liczb
połączonych wierszy;

 Po wykonaniu połączeń tworzymy tablicę
Quine’a;


Przy zapisie postaci minimalnej należy dla

pierwszych
liczb skreślić bity, których wagi odpowiadają
wartościom
umieszczonym w nawiasach.

Piotr Kawalec

Wykład V - 12

Technika cyfrowa

Przykład minimalizacji funkcji



Zminimalizować metodą dziesiętną Quine’a

Mc Cluskey’a funkcję

y= f(x

4

, x

3

, x

2

,

x

1

) = [0,1,5,8,9,10,13,15,

(2)]