TECHNIKA CYFROWA I MIKROKOMPUTERY

WYKŁAD 5

27.03.2003

MINIMALIZACJA FUNKCJI LOGICZNYCH

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

Metody minimalizacji funkcji logicznych:
• metoda Quine’a-McCluskeya
• minimalizacja funkcji słabo określonych
• faktoryzacja
Minimalizacja zespołu funkcji przełączających

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

Metoda ta jest używana, gdy stosowanie metod tablicowych
staje się kłopotliwe. W celu znalezienia minimalnej
alternatywnej postaci normalnej funkcji wykonać należy
następujące czynności:
a) Przedstawione w postaci binarnej zespoły lub wartości
zmiennych, dla których funkcja jest równa 1 lub nieokreślona
należy wpisać w kolumnie porządkując je jednocześnie według
liczy jedynej w zespole. U góry kolumny wpisuje się ciąg
zawierający same zera (o ile należy do F

1

lub F

-

), następnie

grupę ciągów zawierających dokładnie jedną jedynkę, dwie
jedynki itd. Ilość jedynek w liczbie binarnej nazywamy
indeksem -w grupach znajdują się więc liczby o jednakowych
indeksach. Poszczególne grupy należy pooddzielać liniami.
Ciągi te dopowiadają pełnym iloczynom funkcji, przy czym
literze x

i

’ odpowiada 0, a literze x

i

odpowiada 1

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

b) należy porównać ze sobą kolejne ciągi jednej grupy ze
wszystkimi ciągami następnej grupy, łącząc ze sobą ciągi
różniące się jedną cyfrą binarną. W wyniku połączenia np. 1011
z 1001 powstaje ciąg 10-1, który wpisuje się do następnej
kolumny. Przy obu połączonych ciągach stawia się znaki
świadczące o tym ,że nie są one prostymi implikantami (z tym ,
że porównuje się je dalej, tak aby znaleźć wszystkie możliwe
połączenia). Łączenie to odpowiada przeprowadzeniu operacji
niepełnego sklejania. Np. ciąg 1011 odpowiada implikantowi
x

1

x

2

’x

3

x

4

, 1001 - x

1

x

2

’x

3

’x

4

. Mamy x

1

x

2

’x

3

x

4

+ x

1

x

2

’x

3

’x

4

= x

1

x

2

’x

4

+

x

1

x

2

’x

3

x

4

+ x

1

x

2

’x

3

’x

4

, przy czym x

1

x

2

’x

4

odpowiada ciągowi 10-1,

który wpisuje się do nowej kolumny, a sklejone już implikanty
nadal można użyć do sklejania z innymi. Jeżeli któryś z ciągów
nie da się połączyć z żadnym innym, to jest on prostym
implikantem, co oznacza się gwiazdką.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

c) W drugiej kolumnie wpisuje się wyniki wszystkich połączeń
dokonanych w pierwszej kolumnie, przy czym wyniki połączeń
1 u 2 oddziela się od wyników połączeń grupy 2 i 3 itd.,
tworząc nowe grupy. Następnie, analogiczny jak poprzednio,
porównuje się ze sobą kolejne ciągi nowo utworzonych grup z
ciągami grup następnych, łącząc ze sobą różniące się jedyną
cyfrą (a więc mające kreski na tych samych pozycjach).
Połączenie np. 10-1 z 00-1 daje -0-1. Wynik ten wpisuje się do
trzeciej kolumny. Nie wolno łączyć ciągów mających kreski na
różnych pozycjach, np. 10-1 i 1-01. Odpowiadające im
implikanty x

1

x

2

’x

4

i x

1

x

3

’x

4

nie podlegają sklejaniu.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

d) Opisana procedura trwa dopóty, dopóki nie skończą się
możliwości łączenia. W wyniku otrzymuje się zbiór wszystkich
prostych implikantów danej funkcji, które można zmienić na
postać literową.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Minimalizacja całkowicie określonej funkcji czterech
zmiennych:
y=f(x

1

,x

2

,x

3

,x

4

)=(4, 7, 9, 10, 12, 13, 14, 15)

Funkcja ta jest równa 1 dla następujących zespołów
zmiennych: 0100, 0111, 1001, 1010, 1100, 1101, 1110, 1111.
Po uporządkowaniu tych ciągów otrzymuje się tablicę:

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

KOLUMNA 1

KOLUMNA 2

KOLUMNA 3

0100 V
1001 V
1010 V
1100 V
0111 V
1101 V
1110 V
1111 V

-100



1-01 

1-10



110- V
11-0 V

-111



11-1 V
111- V

11--



TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Stosując do niej opisaną powyżej procedurę dostaje się
następujące proste implikanty:
-100

=

x

2

x

3

’x

4

’

1-01

=

x

1

x

3

’x

4

1-10

=

x

1

x

3

x

4

’

-111

=

x

2

x

3

x

4

11--

=

x

1

x

2

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

0100

1001

1010

1100

0111

1101

1110

1111

-100

x

2

x

3

’x

4

’

V

V

1-01

x

2

x

3

’x

4

V

V

1-10

x

1

x

3

x

4

V

V

-111

x

2

x

3

x

4

V

V

11--

x

1

x

2

V

V

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Dla znalezienia postaci końcowych funkcji należy się posłużyć
tablicą Quine’a. Wiersze tej tablicy odpowiadają prostym
implikantom, a kolumny zespołom wartości zmiennych, dla
których funkcja jest równa 1 - a więc jedynkom funkcji. Znaki w
tablicy pokazują jakie jedynki funkcji pokrył dany implikant. Ze
zbioru wszystkich prostych implikantów należy wybrać te,
które są niezbędne do pokrycia wszystkich jedynek funkcji, a
więc wszystkich kolumn tablicy. Jeżeli w którejś z kolumn
znajduje się tylko jeden znak V - to odpowiadający mu
implikant jest niezbędny (zasadniczy prosty implikant). W
rozpatrywanym przykładzie końcowa funkcja będzie
następująca:
y= x

2

x

3

’x

4

’+x

1

x

3

’x

4

+x

1

x

3

x

4

’+x

2

x

3

x

4

Postać ta jest jednocześnie postacią minimalną.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Zbiór wszystkich zasadniczych prostych implikantów
nazywamy jądrem funkcji. W przykładzie jądro stanowią
wszystkie implikanty wchodzące do minimalnej APN funkcji.
Jeżeli tak nie jest, czyli jeżeli zasadnicze proste implikanty nie
pokryją wszystkich funkcji , to spośród pozostałych
implikantów należy wybrać minimalną liczbę implikantów,
które realizują to pokrycie. Przed tym tablicę można uprościć
wykreślając wiersze odpowiadające implikantom zasadniczym
oraz wszystkie kolumny pokryte przez te implikanty.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

W tablicy jądro funkcji stanowi
tylko implikant F pokrywający
jedynki b, c, g, h. Tak więc wiersz
F i kolumny b, c, g, h można
wykreślić z tablicy. Otrzymamy
następującą tablicę.

a b c d e

f

g h

A V

V

B V

V

C

V V

D

V V

E

V

V

F

V V

V V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Do tej tablicy można zastosować
metodę Petricka poszukiwania
minimalnego pokrycia. Metoda ta
opiera się na następującym
rozumowaniu:
dla pokrycia jedynki a potrzebny
jest implikant A lub B, dla
pokrycia d potrzebny jest
implikant A lub C, dla pokrycia e -
implikant D lub E i wreszczie dla
pokrycia f - implikant B lub D. W
celu znalezienia minimlanergo
pokrycia możemy napisac
równanie Boole’a:
(A+B)(A+C)(D+E)(B+D)=1

a d e

f

A V V

B V

V

C

V

D

V V

E

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Po wymnożeniu i zastosowaniu prawa pochłaniania otrzymuje
się:
AD+ABE+BCD+BCE=1
Wyznaczono w ten sposób wszystkie pokrycia funkcji prostymi
implikantami (do każdego wchodzi oczywiście również funkcja
F), czyli mamy wyznaczone wszystkie postacie końcowe
funkcji. Jak widać minimalną będzie postać zawierająca
implikanty A, C i F.
y=F+A+C

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Jeżeli po wykreśleniu kolumn i wierszy tablicy pokryć
odpowiadających jądru funkcji tablica ma dalej duże wymiary,
można ją jeszcze uprościć stosując reguły dominacji kolumn i
wierszy. Wiersz a

i

dominuje nad wierszem a

j

(a

i

a

j

) wtedy i

tylko wtedy, gdy wiersz a

i

pokrywa wszystkie kolumny, które

pokrywa wiersz a

j

. Wiersz a

i

nazywamy dominującym,

natomiast wiersz a

j

nazywamy zdominowanym.

Analogicznie kolumna b

i

dominuje nad kolumną b

j

wtedy i tylko

wtedy, gdy b

i

jest pokrywana przez te wszystkie wiersze przez,

które jest pokrywana kolumna b

j.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

a

b

c

d

e

F

g

h

i

j

k

l

A

V

V

V

V

V

V

V

B

V

V

V

V

V

V

V

C

V

V

V

V

D

V

V

V

V

V

E

V

V

V

V

V

V

F

V

V

V

G

V

V

V

H

V

V

V

V

V

V

V

I

V

V

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Rozpatrzmy tablicę przedstawioną na poprzednim slajdzie. Nie
ma w niej implikantów (wierszy) zasadniczych. Bezpośrednie
zastosowanie metody Petricka byłoby bardzo pracochłonne.
Można uprościć tablicę:
aj, bc, ek, fd, gk, lhc,
oraz
AC, BF, EG, HI,
Można więc wykreślić z tablicy dominujące kolumny a, b, e, f,
g, h, l oraz zdominowane wiersze C, F, G, I

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Wyniku uzyskano tablicę. Brak w
tej tablicy wtórnych implikantów
zasadniczych, ale można
wykreślić wiersz D (AD).

Otrzymamy w ten sposób tablicę
z wtórnym zasadniczym
implikantem A pokrywającym
kolumnę j. Stosując dalej metodę
Petricka otrzymamy funkcję:
(B+H)(B+E)(E+H)=BH+BE+HE
Istnieją zatem trzy minimalne
pokrycia ABE, ABH, AHE.

c

d

i

j

k

A

V

V

B

V

V

V

D

V

E

V

V

H

V

V

c

i

j

k

A

V

B

V

V

E

V

V

H

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Minimalizacja metodą Quine’a McCluskeya może być również
przeprowadzona na zespołach wartości zmiennych
przedstawionych w postaci liczby dziesiętnych. Kolejne punkty
algorytmu będą wówczas następujące:
a) Odpowiedniki dziesiętne zespołów wartości zmiennych, dla
których funkcja jest równa jedności bądź nieokreślona, dzieli
się na grupy o jednakowych indeksach.
b) Łączy się ze sobą dwie liczby z sąsiednich grup, różniące się
o potęgę dwójki, przy czym liczba należąca do grupy o
mniejszym indeksie musi być mniejsza. Należy więc kolejne
liczby jednej grupy porównać z wszystkimi większymi od nich
liczbami sąsiedniej grupy. W przypadku, gdy porównywane
liczby różnią się o 1,2,4,8...itd., a więc dadzą się połączyć,
zapisuje się je w następnej kolumnie (mniejsza na początku), a
obok w nawiasie różnicę

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

c) W drugim etapie porównuje się pierwsze liczby w wierszach
sąsiednich grup nowo utworzonej kolumny, w sposób
analogiczny jak poprzednio. Wiersze, w których liczby w
nawiasach są jednakowe, a pierwsze liczby różnią się o potęgę
dwójki, można połączyć ze sobą i umieścić w trzeciej kolumnie.
Obok w nawiasach umieszcza się różnice wpisane w nawiasach
poprzedniej kolumnie oraz różnice pierwszych licz połączonych
wierszy. Podbnie jak poprzednio liczby w każdym wierszu
muszą być uporządkowane co do wielkosci, a więc np..
Wynikiem połaczenia 12,14 (2) i 13,15(2)będzie 12,13,14,15,
(1,2)
d) Opisana procedura trwa tak długo, aż skończą się
możliwości łączenia.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

f(x

1

, x

2

, x

3

, x

4

)=(4,7,9,10,12,13,14,15)

Realizację kolejnych kroków przedstawiono w tablicy.
Gwiazdkami oznaczone są otrzymane proste implikanty.
Wpisuje się je do tablicy Quine’a, przy czym wypełnienie
tablicy jest bardzo łatwe - znaki V należy postawić w
miejscach, gdzie numer kolumny wchodzi do wyrażenia
opisującego wiersz (przed nawiasem).

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

IDNEKS

KOLUMNA 1

KOLUMNA 2

KOLUMNA 3

1

2

3

4

4 V

9 V

10 V
12 V

7 V

13 V
14 V
15 V

4, 12 (8) *
9, 13 (4) *

10, 14 (4) *

12,13 (1) V
12,14 (2) V

7,15 (8) *

13,15 (2) V
14,15 (1) V

12,13,14,15,(1,2)

*

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

4 9 10 12 7 13 14 15

4, 12 (8)

V

V

9, 13 (4)

V

V

10, 14 (4)

V

V

7, 15 (8)

V

V

12,13,14,15 (1,2)

V

V

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Postać minimalna funkcji jest następująca:
y=4,12 (8) +9,13 (4) + 10,14 (4) + 7,15 (8)
Dla zakodowania wyniku należy zamienić pierwszą liczbę
każdego implikantu na liczbę bierną i skreślić bity, których
wagi odpowiadają liczbom podanym w nawiasach.
Y=100+101+110+111
Nieskreślonym bitom odpowiadają afirmacje (1) lub negacje (0)
zmiennych, a więc ostatecznie:
y=x

2

x

3

’x

4

’+ x

2

x

3

’x

4

+ x

2

x

3

x

4

’+ x

2

x

3

x

4

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

W wielu praktycznych zagadnieniach występują funkcje wielu
zmiennych, określone jedynie dla niewielkiej liczby zespołów
wartości zmiennych. Wypisywanie wszystkich zespołów
wartości zmiennych, dla których funkcja jest nieokreślona (F

-

),

niezbędne w metodzie Quine’a-McCluskeya, nie ma wówczas
sensu. W tym, przypadku generuje się proste implikanty
funkcji porównując zespoły wartości zmiennych, dla których
funkcja jest równa jedności (jedynki funkcji), z zespołami
wartości zmiennych, dla których funkcja jest równa zeru
(zerami funkcji).

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

PRZYKŁAD

Weźmy funkcję czterech zmiennych określoną następująco:
F

1

={0, 2, 3, 14}, F

0

-{10, 11, 15}

W postaci zero-jedynkowej zbiory te przedstawiają się następująco:

0000
0010 1010

F

1

=

0111 F

0

=

1011

1110 1111

Porównując oba zbiory widać, że wszystkie elementy F

0

(zera

funkcji) zaczynają się od 1, a pierwsze trzy elementy F

1

zaczynają

się od 0.Wystarczy więc wziąć taki implikant, który dla x

1

=0 będzie

róny 1, a pokryte zostaną pierwsze trzy jedynki funkcji, a nie
pokryte żadne z zer. Takim implikantem jest oczywiście x

1

’. Ostatni

element F

1

różni się od wszystkich elementów F

0

tym, że wystepuje

w nim kombinacja x

2

=1, x

4

=0. Rozumując jak wyżej stwierdzimy, że

odpowiednim implikantem jest x

2

x

4

’ czyli y = x

1

’+x

2

x

4

’

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

Aby znaleźć minimalną postać normalna funkcji trzeba znaleźć
wszystkie proste implikanty funkcji. Algorytm postępowania
zostanie wyjaśniony na przykładzie funkcji pięciu zmiennych
f(x

1

, x

2

, x

3

, x

4

, x

5

) zadanej następująco F

1

={3, 12, 13, 16, 25,

29}, F

0

={1, 10, 21, 28}

czyli

00011
01100

00001

F

1

=

01101

F

0

=

01010

10000

10101

11001

11100

11101

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

a) Należy zbudować tablicę, której wiersze odpowiadają
elementom F

0

, a kolumny elementom F

1

Porównując teraz

kolejno elementy F

1

ze wszystkimi elementami F

0

i wypisując

zmienne, wartością których różnią się te elementy, przy czym
jeżeli w elemencie z F

1

zmienna mała wartość 1 to wypisujemy

jej afirmację, a jeżeli mała wartość 0 - to negację. Ten punkt
algorytmu przedstawia tabela:

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

00011

01100

01101

10000

11001

11101

00001

x

4

x

2

x

3

x

5

’

x

2

x

3

x

1

x

5

’

x

1

x

2

x

1

x

2

x

3

01010

x

2

’x

5

x

3

x

4

’

x

3

x

4

’x

5

x

1

x

2

’x

4

’

x

1

x

4

’x

5

x

1

x

3

x

4

’x

5

10101

x

1

’x

3

’x

4

x

1

’x

2

x

5

’

x

1

’x

2

x

3

’x

5

’

x

2

x

3

’

x

2

11100

x

1

’x

2

’x

3

’x

4

x

5

x

1

’

x

1

’x

5

x

2

’x

3

’

’x

3

x

5

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

PRZYKŁAD

b) Dla każdej jedynki zespołu wartości zmiennych z F

1

znajduje

się generowane przez nią proste implikanty, tworząc wyrażenia,
będące iloczynem sum wszystkich liter, odróżniających daną
jedynkę od wszystkich zer z F

0

. Np. dla zespołu 00011 tworzymy

wyrażenie:

x

4

(x

2

’+x

5

)(x

1

’+x

3

’+x

4

)(x

1

’+x

2

’+x

3

’+x

4

+x

5

)=1.

Uzasadnienie powyższego postępowania jest następujące: aby
pokryć jedynkę 00011 i nie pokryć żadnego zera funkcji, należy
utworzyć implikant, do którego wchodzi x

4

, bo odróżnia on

jedynkę od zera 00001, x

2

’ lub x

5

- aby odróżnić od zera 01010

x

1

’ lub x

3

’ lub x

4

itd. Po wymnożeniu powyższego wyrażenia

otrzymuje się wszystkie proste implikanty, pokrywające jedynkę
00011. Łatwo zauważyć, że w rozpatrywanym wyrażeniu x

4

pochłania

(x

1

’+x

3

’+x

4

) oraz (x

1

’+x

2

’+x

3

’+x

4

+x

5

) wystarczy

więc mnożyć: x

4

(x

2

’+x

5

)= x

4

x

2

’+x

4

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

PRZYKŁAD

Podobnie mamy dla następujących jedynek funkcji:
(

x

2

+x

3

+x

5

’)(x

3

+x

4

’)(x

1

’+x

2

+x

5

’)x

1

’= x

1

’

(

x

2

+x

3

+x

5

’)(x

3

+x

4

’)=

x

1

’

(

x

2

x

3

+ x

2

x

4

’+x

3

x

3

+x

3

x

4

’+ x

5

’x

3

+x

5

’x

4

’)=

x

1

’

(

x

3

[x

2

+x

4

’+x

5

’+ 1]+x

4

’[x

2

+x

5

’])= x

1

’

(

x

3

+

x

4

’[x

2

+x

5

’])=

x

1

’x

3

+

x

1

’x

4

’x

2

+x

1

’x

4

’x

5

’

(x

2

+x

3

)(x

3

+x

4

’+x

5

)(x

1

’+x

2

)(x

1

’+x

5

)=(x

3

+x

2

x

4

’+ x

2

x

5

)(x

1

’x

1

’+ x

1

’x

5

+x

2

x

1

’+x

2

x

5

)=(x

3

+x

2

x

4

’+ x

2

x

5

)(x

1

’[1+ x

5

+x

2

]+x

2

x

5

)=

(x

3

+x

2

x

4

’+ x

2

x

5

)(x

1

’+x

2

x

5

)=x

2

x

5

+

x

1

’x

3

+x

1

’x

2

x

4

’

(x

1

+x

5

’)(x

1

+x

2

’+x

4

’)(x

3

’+x

5

’)(x

2

’+x

3

’)=(x

1

+x

2

’x

5

’+x

5

’x

4

’)(x

3

’+x

2

’x

5

’)=

x

2

’x

5

’+x

1

x

3

’+x

3

’x

4

’x

5

’

(x

1

+x

2

)(x

1

+x

4

’+x

5

)(x

2

+x

3

’)(x

3

’+x

5

)=(x

1

+x

2

x

4

’+x

2

x

5

)(x

3

’+x

2

x

5

)=

x

2

x

5

+x

1

x

3

’

+x

2

x

3

’x

4

’

(x

1

+x

2

+x

3

)(x

3

+x

4

’+x

5

)x

2

x

5

=x

2

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

PRZYKŁAD

Otrzymaliśmy wszystkie proste implikanty funkcji. W celu
znalezienia minimalnego pokrycia tworzymy tablicę
implikantów identyczną jak w metodzie Quine’a McCluskeya.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

PRZYKŁAD

00011

01100

01101

10000

11001

11101

x

2

’x

4

V

x

4

x

5

V

x

1

’x

3

V

V

x

1

’x

2

x

4

’

V

V

x

1

’x

4

’x

5

’

V

x

2

x

5

V

V

V

x

2

’x

5

’

V

x

1

x

3

’

V

V

x

3

’x

4

’x

5

’

V

x

2

x

3

’x

4

’

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

PRZYKŁAD

Po wykreśleniu wiersza x

2

x

5

(zasadniczy) i pokrytych przez
niego kolumn oraz po
zastosowaniu praw dominacji
wierszy i kolumn. Otrzymano
tablicę. Jedno z minimalnych
pokryć daje rozwiązanie:
f=x

2

x

5

+x

4

x

5

+x

1

’x

3

+x

1

x

3

’

Podany algorytm zapewnia
minimalną postać funkcji, ale jest
dość pracochłonny. Podany
zostanie algorytm na znalezienie
quasi-optymalnej wprost z
tablicy.

00011

01100

10000

x

2

’x

4

V

x

4

x

5

V

x

1

’x

3

V

x

1

’x

2

x

4

’

V

x

1

x

3

’

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

a) Wpisując dla każdej kolumny minimalne zbiory zmiennych,
których podzbiory występują w każdym wierszu. W ten sposób
otrzymuje się minimalne proste implikanty pokrywające
odpowiednią jedynkę, a nie pokrywające zer

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

00011

01100

01101

10000

11001

11101

00001

x

4

x

2

x

3

x

5

’

x

2

x

3

x

1

x

5

’

x

1

x

2

x

1

x

2

x

3

01010

x

2

’x

5

x

3

x

4

’

x

3

x

4

’x

5

x

1

x

2

’x

4

’

x

1

x

4

’x

5

x

1

x

3

x

4

’x

5

10101

x

1

’x

3

’x

4

x

1

’x

2

x

5

’

x

1

’x

2

x

3

’x

5

’

x

2

x

3

’

x

2

11100

x

1

’x

2

’x

3

’x

4

x

5

x

1

’

x

1

’x

5

x

2

’x

3

’

’x

3

x

5

x

5

x

4

x

5

, x

2

’x

4

x

1

’x

3

x

1

’x

3

,

x

2

x

5

x

1

x

3

’,

x

2

’x

5

’

x

2

x

5

,

x

1

x

3

’

x

2

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

b) Jeżeli w wypisanych zbiorach są zbiory o mniejszej ilości liter
niż pozostałe, należy sprawdzić czy nie można ich zastąpić
innymi zbiorami spośród wypisanych. W naszym przypadku
wszystkie minimalne zbiory są dwuliterowe, więc nie
realizujemy tego punktu

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

c) Należy wypisać funkcję tak dobierając implikanty, aby było
ich możliwie mało i aby występowały one we wszystkich
kolumnach. U nas możliwych jest kilka rozwiązań np.
Y=x

4

x

5

+x

1

’x

3

+x

1

x

3

’+x

2

x

5

Zamiast x

4

x

5

można napisać x

2

’x

4

, a zamiast x

1

x

3

’ można

napisać x

2

’x

5

’.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI

PRZAŁĄCZAJĄCYCH

Przy minimalizacji zespołu funkcji przełączających,
przedstawionych w postaci normalnej należy dążyć do
minimalizacji sumarycznej liczby liter, przez wprowadzenie jak
największej liczby wspólnych iloczynów (sum) elementarnych
przy czym, jeżeli ten sam iloczyn (suma) wchodzi w skłąd kilku
postaci normalnych, to tworzące go litery liczone są tylko raz.
Postać normalna poszczególnych funkcji może więc zawierać
nie tylko proste implikanty (implicenty) tych samych funkcji,
ale i proste implikanty wszystkich iloczynów (sum) funkcji. Np.
w celu zminimalizowania APN zespołu trzech funkcji y

1

, y

2

, y

3

należy znaleźć proste implikanty tych funkcji, jak również
implikanty iloczynów y

1

y

2

, y

1

y

3

, y

2

y

3

oraz y

1

y

2

y

3

. Można to

zrobić posługując się tablicami Karnaugha, bądź też
zmodyfikowana metodą Quine’a McCluskeya.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Zminimalizować zespół trzech funkcji czterech zmiennych:
y

1

=f

r

(x

1

, x

2

, x

3

, x

4

)=(2, 5, 6, 13, 14)

y

2

=f

s

(x

1

, x

2

, x

3

, x

4

)=(5, 7, 13, 14)

y

3

=f

t

(x

1

, x

2

, x

3

, x

4

)=(2, 6, 7, 13, 15)

Liczby reprezentujące jedynki funkcji łączy się w grupy zgodnie
z ich indeksami, przy czy, w nawiasie zaznacza się np.
symbolami literowymi do jakich funkcji dany iloczyn należy

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

KOLUMNA 1

KOLUMNA 2

2 (r,t) V

5 (r,s) V

6 (r,t) V

7 (s,t)



13 (r,s,t)



14 (r,s)



15 (t) V

2,6 (4,r,t)



5,7 (2,s)



5,13 (8,r,s)



6,7 (1,t)



6,14 (8,r)



7,15 (8,t)



13,15 (2,t)



TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Procedura łączenia opiera się na tych samych zasadach jak przy
minimalizacji jednej funkcji z dodatkowymi regułami:

– można łączyć tylko te wyrażenia, które mają choć jeden wspólny

symbol funkcji

– przy powstałym w wyniku połączenia wyrażeniu wpisujemy tylko

te wspolne symbole funkcji, np. z połączenia 5(r,s) z 7(s,t)
otrzymujemy 5,7(2,s)

– znak V stawiamy tylko w przypadku jeżeli łączymy dwa wyrażenia

o takich samych symbolach literowych (wtedy znak V stawiamy
przy obu łączonych wyrażeniach, np. Przy łączeniu 2(r,t) z 6(r,t)
lub gdy łączymy wyrażenia, z których jedno ma symbole literowe
będące podzbiorem drugiego (wtedy znak stawiamy tylko przy
pierwszym, np. 5(r,s) z 13(r,s,t)

Prostymi implikantami będą oczywiście wszystkie te wyrażenia,
które nie oznaczono znakiem V. Buduje się następnie tablicę
Quine;a i szuka się minimalnego pokrycia według znanych reguł.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Y

1

=f

r

Y

2

=f

s

Y

3

=f

t

2

5

6

13 14

5

7

13 14

2

6

7

13 15

2,6 (4,r,t)

V

V

V

V

5,13 (8,r,s)

V

V

V

V

13(r,s,t)

V

V

V

5,6(3,s)

V

V

6,14(8,r)

V

V

6,7(1,t)

V

V

7(s,t)

V

V

14(r,s)

V

V

7,15(8,t)

V

V

13,15(2,t)

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Analiza tablicy prowadzi do wniosku, że do pokrycia wszystkich
jedynek funkcji prócz zasadniczych prostych implikantów
2,6(4,r,t); 5,13(8,r,s) i 14(r,s) potrzebne są implikanty 7(s,t);
13,15(2,t) a więc:
y

1

= x

1

’x

3

x

4

’+ x

2

x

3

’x

4

+ x

1

x

2

x

3

x

4

’

y

2

= x

2

x

3

’x

4

+ x

1

’x

2

x

3

x

4

+ x

1

x

2

x

3

x

4

’

y

3

=x

1

’x

3

x

4

+ x

1

’x

2

x

3

x

4

+ x

1

x

2

x

4

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Przy niewielkiej liczbie zmiennych, dla zespołów zawierających
2 lub 3 funkcje wyznaczenia prostych implikantów zespołu
prościej dokonywać jest na tablicach Karnaugha.Tablice
Karnaugha dla rozpatrywanych poprzednio funkcji oraz ich
iloczynów przedstawiono na następnym slajdzie.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

x

3

x

4

x

1

x

2

00 01 11 10

00

0 0 0 1

01

0 1 0 1

11

0 1 0 1

10

0 0 0 0

x

3

x

4

x

1

x

2

00 01 11 10

00

0 0 0 0

01

0 1 1 0

11

0 1 0 1

10

0 0 0 0

x

3

x

4

x

1

x

2

00 01 11 10

00

0 0 0 1

01

0 1 1 1

11

0 1 0 0

10

0 0 0 0

0 0 0 0

0 1 0 0
0 1 0 1
0 0 0 0

0 0 0 1

0 0 0 1
0 1 0 0
0 0 0 0

0 0 0 0

0 0 1 0
0 1 0 0
0 0 0 0

0 0 0 0

0 0 0 0
0 1 0 0
0 0 0 0

y

1

y

2

y

1

y

3

y

2

y

3

y

1

y

2

y

3

y

1

y

2

y

3

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Iloczyn dwu funkcji zawiera odpowiedniki dziesiętne pełnych
ilozynów, wspólne dla obu funkcji. Otrzymane proste implikant
funkcji y

1

, y

2

, y

3

, y

1

y

2

, y

1

y

3

, y

2

y

3

, y

1

y

2

y

3

wpisuje się do tablicy

Quine’a. Dalsze postępowanie jest identyczne jak w metodzie
Quine’a-McCluskeya.

TECHNIKA CYFROWA I MIKROKOMPUTERY

FAKTORYZACJA

Dalsze, w stosunku do postaci normalnej, zmniejszenie liczby
liter w wyrażeniu opisującym daną funkcję osiągnąć można
przez tzw. faktoryzację. Polega ona w najprostszym przypadku
na wyciągnięciu przed nawias wspólnego czynnika (w
przypadku normalnej postaci sumy) lub na częściowym
wymnożeniu (w przypadku normalnej postaci iloczynu) zgodnie
ze wzorami:
AB+AC=A(B+C)
(A+B)(A+C)=A+BC

y=(x

1

+x

2

)(x

1

+x

3

)(x

3

+x

4

)(x

2

’+x

4

)=(x

1

+x

2

x

3

)(x

4

+x

2

’x

3

)