Informacje dotyczące minimalizacji

funkcji logicznych

Wykonał:

Jacek Bednarek

Grupa 26

1. Wprowadzenie.

Zasady algebry Boole'a

Algebra Boole'a określa działania na dwuelementowym zbiorze {prawda, fałsz} odpowiadającemu zbiorowi {0,1}, na którym określono podstawowe działania: sumy, iloczynu i negacji oraz podstawowe prawa: przemienności, łączności, rozdzielności i De Morgana. Zmienna logiczna (nazywana również zmienną boolowską) przyjmuje więc wartości z tego zbioru : zero albo jeden. Argumenty funkcji odpowiadają stanom wejściowym układu, natomiast wartość funkcji stanowi wyjścia.

Sposoby zapisu funkcji logicznych

	Przykład
Kanoniczna postać sumy(DCF)
Kanoniczna postać iloczynu(CCF)
Liczbowa

Ponadto funkcję logiczną można zadawać w postaci opisu słownego, tablicy wartości funkcji (tabeli prawdy) lub wykresu czasowego.

Podstawowe funkcje logiczne

		negacja	suma	iloczyn
				NIE	LUB	I
				NOT	OR	AND	EXOR	EXNOR
A	B	~A	A+B	A*B	A⊕B	A⊗B
0	0	1	0	0	0	1
0	1	1	1	0	1	0
1	0	0	1	0	1	0
1	1	0	1	1	0	1

Podstawowe prawa algebry Boole'a

Dotyczące sumy	Dotyczące iloczynu

2. Podstawowe definicje.

Rozważana jest funkcja y=f(x₁,x₂,...,x_n).

Definicja1

Zmienna x_i lub jej negacja
nazywana jest literałem i oznaczana symbolem x_i^a , przy czym :

Definicja 2

Elementarny iloczyn jest to iloczyn dowolnej liczy różnych literałów danej funkcji.

Definicja 3

Elementarna suma jest to suma dowolnej liczby różnych literałów danej funkcji.

Elementarny iloczyn oraz elementarna suma, w szczególnym przypadku, gdy liczba ich literałów osiąga wartość n, staje się, odpowiednio, pełnym iloczynem, i pełną sumą.

Definicja 4

Normalna postać sumy DCF funkcji logicznej jest to suma różnych elementarnych iloczynów tej funkcji.

Definicja 5

Normalna postać iloczynu CCF funkcji logicznej jest to iloczyn różnych elementarnych sum tej funkcji.

DCF (CCF) w szczególnym przypadku, gdy zawiera wszystkie pełne iloczyny (wszystkie pełne sumy) danej funkcji staje się jej postacią kanoniczną FDCF (FCCF).

Definicja 6

Implikant funkcji f jest to funkcja tych samych zmiennych posiadająca następującą własność: jeśli dla określonego zespołu wartości zmiennych implikant jest równy jeden, to również funkcja f jest równa jeden,

Implikant f=1
f=1

Przykładem implikantów funkcji są jej wszystkie pełne iloczyny. Można wykazać, że również pewne elementarne iloczyny funkcji mogą być jej implikantami.

Definicja 7

Implicent funkcji f jest to funkcja tych samych zmiennych posiadająca następującą własność: jeśli dla określonego zespołu wartości zmiennych implicent jest równy zero, to również funkcja f jest równa zero:

Implicent f=0
f=0

Analogicznie jak w przypadku implikantów, implicentami funkcji są jej wszystkie pełne sumy, a mogą być - również pewne elementarne sumy.

Definicja 8

Prosty implikant funkcjif, jest to implikant, będący elementarnym iloczynem, Który zmniejszony o dowolny literał przestaje być implikantem funkcji f.

Definicja 9

Prosty implicent funkcji f, jest to implicent, będący elementarną sumą, który zmniejszony o dowolny literał przestaje być implicentem funkcji f.

Definicja 10

Postać skrócona funkcji to suma wszystkich prostych implikantów (lub - iloczyn prostych implicentów ) tej funkcji.

3. Zasady minimalizacji funkcji logicznych.

Postać kanoniczną (sumy lub iloczynu) funkcji, zazwyczaj można uprościć tak, aby realizacja stała się prostsza i tańsza. A zatem postać kanoniczna jest jedynie przejściową formą opisu funkcji logicznej, a dla celów prostej realizacji niezbędne są efektywne, zalgorytmizowane metody upraszczania wyrażeń logicznych (postać kanoniczna funkcji może być punktem wyjścia dla tych metod). Najpierw należy jednak określić kryteria optymalizacji funkcji logicznych. Ponieważ optymalna dla realizacji postać funkcji w istotnym stopniu zależy od rodzaju zastosowanych elementów, jest możliwe podanie ogólnych zasad optymalizacji wyrażeń logicznych. Analiza różnych rozwiązań umożliwia jedynie stwierdzenie, że typowym etapem optymalizacji rozwiązania jest sprowadzenie opisu funkcji do postaci o najmniejszej liczbie najprostszych składników (czynników). Można zatem przyjąć następującą zasadę minimalizacji funkcji logicznej minimalizacja funkcji polegać będzie na przedstawieniu jej w postaci normalnej (sumy DCF lub iloczynu CCF ), zawierającej najmniejszą liczbę wyrażeń ( iloczynów - w przypadku DCF; sum - w przypadku. CCF), z których każdy zawiera możliwie mała. liczbę literałów. Tym samym postać taka daje się zrealizować z pomocą, najmniejszej liczby elementów o najmniejszej liczbie wejść (chodzi tu o elementy małej skali integracji SSI, czyli bramki logiczne). Liczba użytych bramek oraz liczba wejść tych bramek jest najczęściej minimalizowanym w praktyce wskaźnikiem jakości. Wynika to z faktu, że suma liczby wejść i liczby wyjść bramek jest mniej więcej stała dla typowych układów scalonych SSI. A zatem, stosując ten wskaźnik w przybliżeniu minimalizuje się liczbę użytych układów scalonych SSI. Niestety, powyższe zasady nie przenoszą się w tak bezpośredni sposób na elementy i układy scalone średniej i dużej skali integracji MSI, LSI.

Zgodnie z przedstawioną wyżej zasadą minimalizacji funkcji logicznej, proces poszukiwania minimalnej DCF lub CCF obejmuje dwa etapy odpowiadające dwóm czynnikom determinującym minimalność DCF lub CCF:

a)minimalizacja liczby literałów w elementarnych iloczynach (w przypadku DCF) lub elementarnych sumach (w przypadku CCF), czyli generowanie wszystkich prostych implikantów (dla DCF) lub wszystkich prostych implicentów (dla CCF),

b) minimalizacja liczby wykorzystanych prostych implikantów (prostych

implicentów) funkcji.

W niektórych algorytmach minimalizacji funkcji powyższe dwa etapy "zlewają się" ze sobą, w innych są wyraźnie wyodrębnione.

Łatwo wykazać, że minimalna, w rozpatrywanym sensie, DCF funkcji zawiera wyłącznie proste implikanty, zaś minimalna CCF funkcji wyłącznie proste implicenty.

Suma wszystkich prostych implikantów (lub iloczyn wszystkich prostych implicentów) funkcji tworzy postać skróconą tej funkcji. Okazuje się jednak, i temu odpowiada wymieniony wyżej punkt b). że w ogólnym przypadku z postaci skróconej możliwe jest usunięcie pewnych zbędnych prostych implikantów (zbędnych prostych implicentów) bez zmiany wartości funkcji. Uzyskane w ten sposób postaci funkcji nazywają się postaciami końcowymi. Postaci takich może być kilka. Co najmniej jedna z nich jest minimalną postacią normalną. Etapy minimalizacji funkcji logicznej przedstawiono na schemacie niżej:

Etapy minimalizacji funkcji logicznej.

Postacie kanoniczne FDCF(FCCF)

generowanie wszystkich -Zawierają wszystkie pełne iloczyny

prostych implikantów (pełne sumy);

(prostych implicentów) funkcji -Zawierają wszystkie proste

implikanty(proste implicenty);

Postacie skrócone DCF(CCF)

-zawierają wszystkie proste implikanty (proste implicenty)

Postacie końcowe DCF(CCF)

Minimalizacja liczby - zawierają wszystkie niezbędne

wykorzystanych proste implikanty (proste implicenty);

prostych

implikantów

(prostych implicentów)

funkcji

Postać minimalna DCF(CCF)

Przykład 1

Rozpatrzona zostanie funkcja trzech zmiennych zapisana w postaci:

DCF:

Wykorzystując iloczyny nr 3 i 4 dwukrotnie (a+a=a, a
{O.1} oraz dokonując wyłączeń przed nawias uzyskuje się:

Można wykazać, że wszystkie elementarne iloczyny w powyższym wyrażeniu są prostymi implikantami; jest to zatem postać skrócona funkcji. Pierwszy prosty implikant , czyli iloczyn x₁x₂ jest „aktywny” (tzn. równy jeden) wyłącznie wtedy gdy
. Ale wówczas pozostała część wyrażenia ma postać:

Zatem, w jedynym przypadku, gdy iloczyn x₁x₂. Jest równy jeden, funkcja f, ze względu na swą postać i tak przyjmuje wartość jeden, niezależnie od x₁x₂. Wynika stąd, że prosty implikant x₁x₂ jest zbędny - można go usunąć bez zmiany wartości funkcji f. Uzyskuje się w ten sposób postać końcową:

która, ponieważ jest jedna jednocześnie minimalna DCF dla funkcji f.

Na obecnym etapie rozważań określone są już zasady oraz etapy minimalizacji funkcji logicznych, natomiast podstawowym mankamentem pozostają metody tej minimalizacji. Przedstawione wyżej upraszczanie funkcji poprzez stosowanie odpowiednich praw algebry Boole'a, a następnie również "ręczna" weryfikacja czy otrzymane implikanty (implicenty) są proste i niezbędne jest procedurą bardzo żmudną nawet w przypadku stosunkowo prostych funkcji. Z tego względu opracowano szereg algorytmów umożliwiających "automatyczne" generowanie minimalnych postaci funkcji w znacznie szybszy sposób i dla znacznie bardziej złożonych funkcji, niż byłoby to możliwe przy stosowaniu sposobu "ręcznego".

4. Algorytmy minimalizacji

Wszystkie algorytmy minimalizacji funkcji logicznych bazują na tych samych prawach algebry Boole'a, które były wykorzystywane przy "ręcznym" upraszczaniu funkcji. Prawa te (nazwiemy je tu regułami), to:

1) reguła sklejania:

2) reguła niepełnego sklejania:

przy czym A -to dowolne wyrażenie logiczne (boolowskie), x -zmienna logiczna. Każda z tych reguł zapisana jest w dwojakiej postaci -jedna dotyczy funkcji typu DCF druga funkcji typu CCF .

Reguła sklejania stwierdza, że dwa elementarne iloczyny (dwie elementarne sumy) można „skleić”­ (tzn. po łączyć ze sobą uzyskując prostsze wyrażenie), gdy mają one taką samą ilość literałów i gdy różnią się między sobą na dokładnie jednej pozycji negacją jednego literału.

Operacja sklejania może być zapisywana również w innej, w stosunku do postaci, a mianowicie przy pomocy ciągów binarnych. Rozważmy dla przykładu, dwa pełne iloczyny o numerach 1 i 2. Iloczyny te, reprezentują dwie "jedynki" funkcji (w zapisie binarnym): 0100 i 0101. Jednocześnie iloczyny te różnią wyłącznie na jednej, ostatniej pozycji. Można więc skleić. Efekt tego sklejenia w zapisie binarnym wygląda

następująco: 010-. Podobnie, w przypadku CCF funkcji, sklejenie pełnych sum: nr 1 i nr 2, opisywanych binarnie przez 0000, 0001 , daje w rezultacie 000-. Sklejenie sum nr 3 i 4 (0010, 0011) w tym samym wyrażeniu daje 001-. Z kolei, można skleić ze sobą 000­ i 001­ (różnią się na jednej pozycji); uzyskuje się 00--.

Powyższe operacje nazywane będą sklejaniem wektorów.

Reguła niepełnego sklejania stwierdza, że jeden elementarny iloczyn (jedna elementarna suma) może być wykorzystany (wykorzystana) do sklejania więcej niż jeden raz. Ten zabieg również stosowano we wcześniejszym "ręcznym" upraszczaniu postaci funkcji.

Definicja 11

Elementarne iloczyny (elementarne sumy) podlegające sklejaniu, czyli różniące się tylko o negację jednego literału, noszą nazwę sąsiednich.

Zasadnicza różnica między minimalizacj­ą funkcji przy pomocy różnego rodzaju algorytmów a minimalizacją­ „ręczną" polega na tym, że w pierwszym przypadku iloczyny (sumy) sąsiednie są wyszukiwane w usystematyzowany, "automatyczny" sposób, podczas, gdy w drugim przypadku są one wynikiem ręcznego przekształcania postaci funkcji.

Różne metody minimalizacji różnią­ się technikami wyszukiwania iloczynów (sum) sąsiednich.

W niniejszej pracy przedstawione zostaną typowe, klasyczne metody minimalizacji funkcji logicznych. Są to:

1) metoda tablic Karnaugha,

2) metoda Quine'a -McCluskey'a,

3) metoda minimalizacji funkcji słabo określonych,

4) metoda minimalizacji zespołu funkcji ,

5) faktoryzacja.

Można spotkać wiele innych metod minimalizacji jednakże są one mniej popularne niż wyżej wymienione.

Powyższe klasyczne metody, choć opracowywane pod kątem realizacji funkcji na elementach SSI (czy też elementach stykowo-przekaźnikowych), znajdują również zastosowanie w procedurach projektowania układów kombinacyjnych z wykorzystaniem elementów o wyższym stopniu integracji - średnim (MSI) i dużym (LSI). Jest to o tyle istotne, że ostatnie dwie grupy elementów wypierają­ obecnie elementy małej skali integracji przy projektowaniu rozważanej klasy układów cyfrowych.

1) Metoda tablic Karnaugha

Podstawowym zadaniem a jednocześnie główna, trudnością w procesie minimalizacji (sklejania) jest efektywne wyszukiwanie wyrażeń sąsiednich. W metodzie tablic Karnaugha, problem ten rozwiązuje się w ten sposób, że sąsiednim, w sensie definicji 11, pełnym iloczynom (pełnym sumom) przyporządkowuje się leżące obok siebie tzn. sąsiednie fizycznie - pola tablicy, do których następnie wpisuje się wartości funkcji. Aby uzyskać w tablicy wspomniany efekt sąsiedztwa,

współrzędne poszczególnych jej pól należy opisać przy pomocy kodu Graya. Jeżeli w tak zbudowanej tablicy dwa symbole 1 (czy też dwa symbole O) leżą w sąsiednich polach to odpowiadają one wyrażeniom sąsiednim w sensie definicji 11, a zatem można je „skleić”. „Sklejone” pola tablicy obwodzi się linią , aby zaznaczyć, że są one opisywane jednym. prostszym wyrażeniem logicznym.

Proste implikanty (proste implicenty) w tablicy Karnaugha wyznacza się łącząc ze sobą sąsiednie jedynki (sąsiednie zera) w możliwie jak największe grupy składające się jednak z 2 lub 4 lub 8 lub 16 itd. pól (ogólnie liczba pól w obrębie grupy musi być równa potędze dwójki). W szczególnym przypadku grupa może obejmować tylko jedno pole (gdy nie da się jej w żaden sposób powiększyć); odpowiadający mu opis ma postać pełnego iloczynu (pełnej sumy).

Należy pamiętać, że krawędzie tablicy parami (lewa z prawą oraz górna z dolną) również sąsiadują ze sobą.

Zakreślone grupy opisywane są wyrażeniami elementarnymi (iloczynami w przypadku sklejania jedynek, sumami w przypadku zer) w skład których wchodzą wyłącznie literały o wartości nie zmieniającej się w obrębie grupy.

W przypadku opisywania grupy obejmującej jedynki (jest to prosty implikant). Zmienne, których wartość w obrębie grupy jest równa 1 wchodzą do iloczynu elementarnego w postaci afirmacji, a zmienne których wartość jest równa 0­ w postaci negacji.

W przypadku opisywania grupy obejmującej zera (prosty implicent) sytuacja jest odwrotna. Zmienne. których wartość w obrębie grupy jest równa 1 wchodzą do sumy elementarnej w postaci negacji, zaś zmienne, których wartość jest równa 0­ w postaci afirmacji.

Poszczególne grupy odpowiadające prostym implikantom (lub prostym implicentom) mogą zawierać pola wspólne. Inaczej mówiąc dane pole może być włączone do wielu różnych grup, jeśli tylko umożliwi to właściwe poszerzenie tych grup (zgodnie z regułą niepełnego sklejania).

Im większą grupę uda się zbudować w tablicy. tym prostsze będzie wyrażenie opisujące tę grupę, więc w procesie minimalizacji należy tworzyć pola największe z możliwych. W przypadku funkcji niezupełnych bardzo pomocne w zwiększaniu rozmiarów grup mogą być wartości nieokreślone funkcji (kreski w tablicy), którym dowolnie można przypisywać wartości 1 lub O (1 -w przypadku włączenia do grupy

jedynek, O -w przypadku włączenia do grupy zer) tak, aby wynik minimalizacji był jak najlepszy.

Należy pamiętać, że przy realizacji DCF, przy pomocy grup "nakrywa się" jedynki funkcji, zaś przy realizacji CCF -zera funkcji .

Na podstawie powyższych uwag można sformułować następującą, ogólną zasadę postępowania: należy zbudować jak najmniej jak największych grup nakrywających wszystkie jedynki (przy realizacji DCF funkcji) lub wszystkie zera (przy realizacji CCF funkcji) w tablicy Karnaugha; jeśli to możliwe - wykorzystać w tym celu kreski w tablicy; również w tym celu pewne pola tablicy mogą być włączone do więcej niż jednej grupy.

Powyższe uwagi wskazują, że dwa zasadnicze etapy minimalizacji funkcji, tzn. generowanie wszystkich prostych implikantów (implicentów) funkcji a następnie minimalizacja liczby wykorzystanych prostych implikantów (implicentów), w przypadku metody tablic Karnaugha nie są wyraźnie rozgraniczone.

Podsumowując, algorytm wyznaczania minimalnej DCF funkcji przy pomocy tabel Karnaugha jest następujący:

1. Wyszukać i ,jeśli są , zakreślić w tablicy wszystkie te jedynki, które nie mogą być połączone ( nie sąsiadują) z żadną inną jedynką ani kreską ( generowanie grup obejmujących jedno pole tablicy).

2. Wśród pozostałych jedynek odszukać takie, które mają tylko jedną sąsiednią jedynkę lub kreskę, a zatem mogą tworzyć grupy obejmujące wyłącznie dwa pola: zakreślić te grupy. Zacząć należy od tych jedynek, które mogą połączone tylko jednym sposobem.

3. Analizując pozostałe jedynki należy wyszukać grupy obejmujące cztery pola z jedynką lub kreską ale takie, które nie mogą być powiększone do ośmiu pól. Dopuszczalne jest (niekiedy wskazane) częściowe zachodzenie nowych grup na te, które wygenerowano poprzednio; oznacza to, że pewne pola z jedynką lub kreską są wykorzystywane wielokrotnie - należą do kilku grup.

4. Kontynuując wyszukiwanie grup obejmujących 2^k pól z jedynką lub kreską dopuszczając częściowo zachodzenie grup na siebie, aż do „nakrycia” wszystkich pól zawierających jedynki.

5. Znając lokalizację grup w tablicy, zbudować wyrażenie logiczne opisujące rozważaną funkcję.

Jeżeli na którymś etapie występuje kilka możliwości połączenia należy je wszystkie przeanalizować, przy czym dojść można do kilku rożnych postaci końcowych spośród, których należy wybrać postać minimalną.

Opisana wyżej kolejność wyznaczania grup można odwrócić zaczynając od generowania grup największych, jednakże trzeba wówczas sprawdzić. czy któraś z grup większych nie została całkowicie pokryta przez niezbędne grupy mniejsze.

Na zakończenie powtórzmy jeszcze raz, że ogólna minimalizacji funkcji metoda, tablic Karnauhga polega na „nakryciu” wszystkich jej jedynek (albo wszystkich jej zer) przy pomocy jak najmniejszej liczby jak największych grup. W tym celu wykorzystać można również kreski w tablicy, zaś pewne jedynki (pewne zera) mogą być

włączone do więcej niż jednej grupy.

Metoda minimalizacji za pomocą tablic Karnaugha jest prosta i skuteczna przy niewielkiej liczbie zmiennych - w praktyce dla funkcji do pięciu, najwyżej sześciu zmiennych. Powyżej tej granicy wyszukiwanie pól sąsiednich tablicy staje się kłopotliwe i metoda przestaje być użyteczna. Należy wówczas zastosować inne metody, a w przypadku szczególnie dużej liczby zmiennych - metody komputerowe.

Przykład 2

Stosując tablicę Karnoughta zminimalizować funkcję:

1. Wyznaczamy wektor wartości:

X=[1,0,1,0,0,0,0,0,1,0,11,0,0,0,1]^T

2. Sporządzamy tablicę Karnoughta:

x2x1 x4x3	00	01	11	10
00	1	0	0	1
01	0	0	0	0
11	0	0	1	0
10	1	0	1	1

3. Na podstawie zaznaczonych pól możemy zapisać:

Jest to szukana minimalna postać zadanej funkcji logicznej.

2) Metoda Quine'a-McCluskey'a.

Metoda ta może być stosowana do funkcji dowolnej liczby zmiennych, a w praktyce - gdy liczba zmiennych jest większa lub równa sześć.

Zasady minimalizacji

Minimalizacja funkcji logicznych metodą Quine'a-McCluskeya jest metodą systematyczną, wykorzystującą w zalgorytmizowany sposób operację grupowania i obróbki danych, co pozwala na w miarę proste wykorzystanie ją w minimalizujących programach komputerowych. Najczęściej stosuje się ją przy dużej ilości zmiennych, gdzie inne metody (algebraiczna, tablic Karnaugha) stają się uciążliwe.

a)Postać kanoniczna funkcji

W pierwszym kroku należy otrzymać postać kanoniczną funkcji, która będzie zawierała wszystkie składniki jedynki.

b)Znalezienie prostych implikantów

Tworzymy tabelę zawierającą wszystkie składniki jedynki w postaci zerojedynkowej . Następnie porównujemy każde dwa elementy tej tablicy i sprawdzamy czy obie liczby różnią się tylko na jednej pozycji (np. 0110 i 0100 spełnia ten wymóg, na trzeciej pozycji występuje jedyna różnica między nimi), zaznaczamy oba implikanty, a do nowej tabeli wpisujemy 01-0 (kreska na pozycji występowania różnicy). Po sprawdzeniu pierwszej tabeli wszystkie niezaznaczone implikanty wpisujemy do tablicy prostych implikantów. Podobnie postępujemy z drugą tabelą, z tym że do warunku o różnicy 0,1 na tylko jednej pozycji, dochodzi warunek występowania kresek na dokładnie tych samych pozycjach. Tworząc w ten sposób kolejne tabele, wypełniając stopniowo tablicę prostych implikantów, dochodzimy do momentu w którym żaden z implikantów tabeli, po jej całkowitym porównaniu, nie będzie zaznaczony i wpisując je do tablicy prostych implikantów zakończymy ten etap pracy.

c)Wyróżnienie istotnych prostych implikantów

Tworzymy tablicę prostych implikantów - tablicę pokrycia, w której każdy wiersz odpowiada kolejnym prostym implikantom, natomiast kolumny składnikom postaci kanonicznej funkcji. Następnie wypełniamy tabelę krzyżykami, tam gdzie dany implikant zawiera w sobie dany składnik postaci kanonicznej.

Po wypełnieniu tabeli szukamy kolumn w których występuje tylko jeden krzyżyk tj. dany składnik postaci kanonicznej funkcji jest pokrywany tylko przez jeden prosty implikant. Ten prosty implikant, zwany implikantem istotnym zaznaczamy w dodatkowej skrajnej kolumnie.

Po odszukaniu wszystkich istotnych implikantów, łączymy je w tzw. jądro funkcji i usuwamy z tabeli pokrycia wszystkie pokrywane przez nie proste implikanty.

d)Określenie form minimalnych

Z pozostałych prostych implikantów musimy wybrać minimalną ich ilość, która pokryje wszystkie składniki postaci kanonicznej funkcji. Często możemy tego dokonać na wiele sposobów, a więc funkcja ma wiele postaci minimalnych. Ma to duże znaczenie przy minimalizacji funkcji wielowyjściowych, gdzie wykorzystuje się równorzędne składniki poszczególnych funkcji.

Przykład minimalizacji funkcji z trzema postaciami minimalnymi

Dana jest funkcja

którą poddajemy minimalizacji metodą Quine'a - McCluskeya

a)Postać kanoniczna funkcji

b)Znalezienie prostych implikantów

Przekształcamy poszczególne składniki postaci kanonicznej na ich odpowiedniki zapisane w systemie binarnym.

	1100	12
	1101	13
	1110	14
	1111	15
	0100	4
	0101	5
	0011	3
	0001	1
	1011	11

Następnie sortujemy elementy ze względu na ilość jedynek w postaci binarnej co ma ułatwić porównywanie elementów, które dokonujemy teraz pomiędzy składnikami sąsiednich grup

		1. porównanie	2. porównanie	Proste implikanty
	0100v	-100v	-10-	-10-
	0001v	00-1	11--	11--
	1100v	0-01	11--	-011
	0011v	110-v		1-11
	0101v	11-0v		00-1
	1101v	-011		0-01
	1011v	-101v
	1110v	11-1v
	1111v	1-11
		111-v

Tablice Karnaugh'a odpowiadające kolejnym etapom minimalizacji

Po pierwszym porównaniu Po drugim porównaniu

		CD
				00	01	11	10
	AB	00	0	1	1	0
		01	1	1	0	0
		11	1	1	1	1
		10	0	0	1	0

		CD
				00	01	11	10
	AB	00	0	1	1	0
		01	1	1	0	0
		11	1	1	1	1
		10	0	0	1	0

Proste implikanty

		CD
				00	01	11	10
	AB	00	0	1	1	0
		01	1	1	0	0
		11	1	1	1	1
		10	0	0	1	0

Implikanty istotne

		CD
				00	01	11	10
	AB	00	0	1	1	0
		01	1	1	0	0
		11	1	1	1	1
		10	0	0	1	0

Implikanty pozostałe

		CD
				00	01	11	10
	AB	00	0	1	1	0
		01	1	1	0	0
		11	1	1	1	1
		10	0	0	1	0

3). 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. Uwzględnianie wszystkich zespołów wartości zmiennych dla których funkcja jest nieokreślona (zbiór F^”-„­ ), niezbędne w metodzie Quine'a-McCluskey'a, powoduje, że w tych przypadkach metoda ta staje się mało efektywna. Wyznacza się bowiem wiele prostych implikantów (prostych implicentów), które nie pokrywają żadnych jedynek (żadnych zer) funkcji.

Definicja 12

Funkcja logiczna n zmiennych f(x₁,x₂,....,x_n) jest słabo określona, gdy spełniony jest warunek:

gdzie IFI oznacza liczbę elementów zbioru F. Warunek powyższy jest równoważny poniższemu:

przy czym Dⁿ oznacza dziedzinę funkcji f.

A zatem, o funkcji słabo określonej mówi się w przypadku, gdy liczba jej "kresek" (nieokreśloności) jest większa niż liczba jej zer i jedynek.

Przedmiotem rozważań będzie tu minimalizacja normalnej postaci sumy (DCF) funkcji. W tym celu najpierw należy znaleźć wszystkie proste implikanty funkcji .W przedstawionych dotychczas metodach minimalizacji, poszukiwanie prostych implikantów wymaga rozważenia wszystkich jedynek i "kresek" funkcji. Jednakże, z punktu widzenia złożoności obliczeniowej, w przypadku funkcji słabo określonych dużo korzystniejszy jest algorytm uzyskiwania prostych implikantów na podstawie zer jedynek funkcji. Algorytm wyjaśniony będzie poniższym przykładzie.

Przykład 3

Rozpatrywana jest funkcja pięciu zmiennych f(x₁,x₂,x₃,x₄,x₅ )

określona następująco:

F¹={3,12,13,16,25,29}, F⁰={1,10,21,28}

Binarne zbiory F'¹ i F'⁰ odpowiadające F¹ i F⁰ są zatem następujące:

Poszukiwanie prostych implikantów tej funkcji dokonuje się za pomocą tzw. Tablicy niezgodności przedstawionej poniżej:

Kolumny reprezentują jedynki funkcji, a wiersze - zera. Na przecięciu kolumn i wierszy wypisane są literały, które będą użyte do stworzenia prostego implikantu zawierającego (nakrywającego) daną jedynkę.

Przeanalizujmy pierwszą kolumnę (jedynka 00011). Prosty implikant, który zawiera tę jedynkę nie może, tak jak każdy implikant, zawierać żadnego zera funkcji. W skład opisującego go iloczynu musi zatem wchodzić literał x₄ , gdyż zmienna x₄ przyjmuje inną wartość w rozważanej jedynce i w zerze 00001 (odróżnia te dwa ciągi wejściowe). To, że zmienna x₄ ma być nie zanegowana wynika z jej wartości (równej 1) w rozważanej jedynce. Podobnie literały x₂ lub x₅ odróżniają jedynkę 00011 od

zera 01010. Zmienna x₂ ma być zanegowana, gdyż jej wartość w rozważanej jedynce wynosi 0. Zmienna x₅ z analogicznego względu, nie jest zanegowana. Z kolei, literały
lub x₃ lub x₄ odróżniają rozważaną jedynkę 00011 od zera 10101, zaś literały
lub
lub
lub x₄ lub x₅ - od zera 11100.

Prosty implikant nie może obejmować żadnego zera, a więc w skład opisującego go iloczynu musi wchodzić co najmniej jeden literał odróżniający jedynkę 00011 od każdego zera funkcji. Stosując metodę zbliżoną do analizy Petricka uzyskuje się

następujące wyrażenie logiczne:

Wyrażenie to musi przyjąć wartość logiczną "prawda", aby spełniony był

warunek nienakrywania przez generowane implikanty żadnego z zer funkcji.

W ten sposób buduje się wszystkie proste implikanty funkcji. W celu znalezienia implikantów nakrywających wszystkie jedynki funkcji postępujemy identycznie jak w Etapie II metody Quine'a-McCluskey'a. Tablicę Quine'a oraz jej postać zredukowane przedstawiono na rys poniżej.

W ten sposób zbudowane zostały wszystkie proste implikanty funkcji.

W celu znalezienia minimalnego zbioru implikantów nakrywających wszystkie jedynki funkcji postępujemy identycznie jak w Etapie II metody Quine'a-McCluskey'a. Tablicę Quine'a oraz jej postać zredukowaną przedstawiono na rys. poniżej.

Stosując analizę Petricka do zredukowanej tablicy Quine'a z rys. ponizej stwierdza się, że występuje 18 równoważnych, minimalnych zestawów prostych implikantów nakrywających wszystkie jedynki funkcji. Wynika to z rozwinięcia poniższego wyrażenia:

(nr 1 albo nr 2) i (nr 3 albo nr 4 albo nr 5) i (nr 7 albo nr 9)

Każdy z minimalnych zestawów prostych implikantow zawiera, włączając implikant zasadniczy nr 6, po 4 elementy. Stosując dodatkowe kryterium, jakim jest minimalna liczba literałów oraz negacji w obrębie rozpatrywanych implikantów (ma to wpływ na złożoność realizacji układu ), otrzymuje się z powyższego jeden zestaw implikantów:

nr 2 i nr 3 i nr 8

Ostatecznie, minimalna postać funkcji jest następująca:

Opisana metoda generuje minimalną postać funkcji, chociaż w przypadku dużej liczby argumentów, stosowanie jej "ręcznej" (a nie np. komputerowej) wersji może być dosyć uciążliwe. Istnieją również metody prostsze obliczeniowo ale dające

quasi-optymalne rozwiązania.

Przedstawiona metoda dotyczyła minimalizacji normalnej postaci sumy (DCF) funkcji. W zupełnie analogiczny sposób uzyskać można przy jej pomocy, minimalną normalną postać iloczynu (CCF) funkcji.

4). Faktoryzacja

Przedstawione dotychczas metody minimalizacji funkcji (zarówno jej DCF jak i CCF) dawały w rezultacie wyrażenia o sztywnej strukturze. Na przykład minimalna DCF funkcji to suma pewnej liczby iloczynów zmiennych, przy czym niektóre zmienne wchodzące do iloczynów mogą być zanegowane. Przenosząc te rozważania na płaszczyznę realizacji funkcji z wykorzystaniem elementów małej skali integracji SSI, tzn. bramek logicznych, można stwierdzić, że struktura uzyskiwanych układów również jest sztywna i zawiera trzy poziomy elementów: poziom inwerterów i dwa poziomy bramek wielowejściowych, odpowiednio, bramek iloczynu i bramek sumy. Analogicznie w przypadku minimalnej CCF funkcji, jest to iloczyn pewnej liczby sum zmiennych bądź negacji zmiennych. Struktura układu w tym przypadku zawiera poziom inwerterów, poziom bramek sumy oraz poziom bramek iloczynu.

Okazuje się, że sztywna struktura schematów odpowiadających wyrażeniom DCF i

CCF funkcji nie w każdym przypadku zapewnia rozwiązanie wymagające rzeczywiście minimalnej liczby bramek. W związku z tym opracowane zostały metody, które lepiej minimalizują liczbę bramek i liczbę ich wejść. Jedną z nich jest faktoryzacja. Polega ona na przekształcaniu minimalnych wyrażeń DCF lub CCF do postaci, która zawiera mniej literałów, a tym samym daje się zrealizować z pomocą mniejszej liczby bramek lub bramek o mniejszej liczbie wejść.

Przekształcenia te to najczęściej prawa de Morgana, wyciąganie przed nawias wspólnego czynnika (w przypadku DCF) lub częściowe wymnażanie (w przypadku CCF). Opisują je wzory:

AB + AC = A(B+C),

(A+B) (A+C) =A+BC,

gdzie A, B, C są zmiennymi lub wyrażeniami logicznymi.

Należy stwierdzić, że metoda faktoryzacji jest godna polecenia szczególnie wtedy, gdy negacje zmiennych są realizowane poza projektowanym układem i nie ma potrzeby stosowania inwerterów do ich uzyskania. Istotną wadą faktoryzacji jest to, że trudno poddaje się ona algorytmizacji; wyniki, w istotnym stopniu, zależą od spostrzegawczości i wprawy projektującego układ. Najczęściej stosuje się ją do "poprawiania" rezultatów osiągniętych przez minimalizację DCF (CCF) funkcji. Faktoryzacja jest również przydatna wtedy, gdy chce się zrealizować funkcję przy użyciu bramek o mniejszej liczbie wejść.

Schematy uzyskane metodą faktoryzacji mają strukturę wielopoziomową - w odróżnieniu od schematów DCF i CCF zawierających dwa poziomy bramek wielowejściowych oraz w ogólnym przypadku, jeden poziom inwerterów. Jednak wielopoziomowość układów faktoryzowanych może być w pewnych sytuacjach poważnym mankamentem tych układów.

5). Minimalizacja zespołów funkcji logicznych

W zagadnieniach praktycznych rzadko pojawiaj­ się problemy, które dają się opisać pojedynczą funkcją logiczną, zwykle pojawia się konieczność użycia kilku funkcji logicznych i skonstruowania układu realizującego ten zespół funkcji. Mówi się w takich przypadkach o minimalizacji zespołu funkcji logicznych lub o projektowaniu wielowyjściowego układu kombinacyjnego.

Metody minimalizacji zespołów funkcji logicznych są rozwinięciem, w określonym kierunku przedstawionych poprzednio algorytmów dotyczących pojedynczej funkcji logicznej. Podstawowa różnica polega na wprowadzeniu innego kryterium minimalizacji układu. Z oczywistych względów interesuje nas teraz minimalizacja zespołu funkcji a nie poszczególnych funkcji osobno. Warto zauważyć, że niezależna minimalizacja poszczególnych funkcji wcale nie oznacza minimalizacji zespołu funkcji jako całości i na odwrót.

Ogólna zasada minimalizowania zespołów funkcji logicznych.

Polega ona na opisywaniu poszczególnych funkcji takimi wyrażeniami, które mają możliwie dużą liczbę części wspólnych.

W przypadku DCF funkcji zasada ta jest łatwa do praktycznego wykorzystania. Elementami DCF funkcji są iloczyny literałów opisujące poszczególne proste implikanty. Jeżeli zależy nam na wyrażeniach zawierających możliwie duże części wspólne, należy uwzględnić części wspólne implikantów rożnych funkcji, tzn. proste implikanty iloczynów poszczególnych funkcji. Minimalnego zbioru prostych implikantów nakrywających jedynki wszystkich funkcji poszukuje się wówczas wśród prostych implikantów funkcji i prostych implikantów wszystkich kombinacji iloczynów funkcji.

Zbiór wszystkich prostych implikantów dla zespołu funkcji można określić posługując się tablicami Karnaugha (dotyczy to raczej prostszych przypadków), bądź też zmodyfikowaną wersją Etapu I metody Quine'a-McCluskey'a. Ta ostatnia metoda jest znacznie bardziej uniwersalna, gdyż może być stosowana do dowolnie złożonych zespołów funkcji.

Algorytm Etapu I metody Quine'a-McCluske'a dla minimalizacji zespołów funkcji:

1. Dziesiętne reprezentacje zespołów wartości zmiennych dla których funkcje są równe jedności lub nieokreślone należy podzielić na grupy o jednakowych indeksach i wypisać w pierwszej kolumnie w kolejności zgodnej ze wzrastającą wartością indeksu. Dodatkowo, należy zaznaczyć np. symbolami literowymi do których funkcji poszczególne zespoły wartości zmiennych należą.

2.Procedura łączenia opiera się na zasadach obowiązujących przy minimalizacji jednej funkcji, rozszerzonych o dodatkowe reguły:

2. 1. Można łączyć tylko te wyrażenia, które mają choć jeden wspólny symbol funkcji.

2.2. Przy powstałym w wyniku połączenia wyrażeniu należy wpisać tylko te symbole funkcji, które są wspólne dla obu łączonych wyrażeń.

2.3. Znak V należy postawić tylko w tych przypadkach, gdy:

a) łączone są, dwa wyrażenia o takich samych symbolach literowych (wtedy znak V należy postawić przy obu łączonych wyrażeniach.

b) łączone są, dwa wyrażenia, z których jedno ma symbole literowe będące podzbiorem drugiego (wtedy znak V należy postawić przy tym pierwszym ).

Prostymi implikantami są wszystkie te wyrażenia, które nie oznaczono znakiem V; tradycyjnie będą one oznaczane symbolem *.

W przypadku zespołów zawierających dwie lub trzy funkcje niewielkiej liczby zmiennych, wyznaczanie zbioru prostych implikantów dla zespołu funkcji można także przeprowadzić przy pomocy tablic Karnaugha.

Algorytm dla zespołu m funkcji jest następujący:

1. Rozpatrzyć funkcję będącą m-elementowym iloczynem pojedyńczych funkcji i wypisać wszystkie jej proste implikanty.

2. Przeanalizować kolejne poziomy k-elementowych iloczynów funkcji dla k=m-1,

m-2, ..., 2,1, zaznaczając w nich (np. przez zakreskowanie ) implikanty określone w punkcie 1.

3. Wypisać wszystkie nie zakreskowane implikanty z poziomu o jeden niższego, tzn. dla m-1.

4. Powtórzyć punkt 2 dla kolejnych poziomów poczynając od m-2 (zatem

dla k=m-2, m-3, ..., 2, 1) .

5. Czynności z punktu3 a następnie4 wykonać dla poziomu m-2 następnie m-3, itd. Aż do poziomu 1, tzn. poziomu pojedyńczych funkcji. Wszystkie wypisane implikanty należy wpisać do tablicy Quine'a.

Z powyższych rozważań wynika ogólny wniosek, że w każdym zagadnieniu należy rozważyć różne rozwiązania i warunki, będzie tu również rodzaj dostępnych układów scalonych, aby uzyskać rozwiązanie rzeczywiście minimalne.

BIBLIOGRAFIA

1.”Układy logiczne” Władysław Majewski, Podręczniki Akademickie: Elektronika, Informatyka, Telekomunikacja, Wydawnictwo Naukowo-Techniczne,Warszawa,1999;

2.”Układy cyfrowe, Metody syntezy” Tom I „Elementy , Układy Kombinacyjne”, Marian B. Gorzałczany, Politechnika Świętokrzyska, Kielce,1997;

3.”Układy cyfrowe, Metody syntezy” Tom II „Układy Sekwencyjne,Układy Mikroprogramowane”, Marian B. Gorzałczany, Politechnika Świętokrzyska, Kielce,1997;

4.Ćwiczenia laboratoryjne do przedmiotu ”Układy logiczne”, mgr inż. Sylwia Rawa, Wydział Informatyki Politechniki Szczecińskiej,Szczecin,1996 ;

5.”Układy logiczne”, praca zbiorowa, Wydział Informatyki Politechniki Szczecińskiej,Szczecin,1995 ;

13

---