Funkcje logiczne definiują zależność sygnału wyjściowego od wartości zmiennych. Funkcje logiczne są pełną formą opisu działania układów kombinacyjnych (tzn. nie posiadających możliwości pamiętania swojego stanu).
Najczęściej stosowane są następujące formy funkcji:
Opis słowny
Spotyka się go w zasadzie wyłącznie we wstępnej fazie projektowania układu. Do dalszej analizy tworzy się na podstawie opisu słownego tabelę lub/oraz postacie kanoniczne.
Tabela funkcji.
Postać najczęściej spotykana, zwłaszcza dla funkcji niewielu zmiennych. W tabeli można uwzlędnić oprócz stanów 0 i 1 również stany nieokreślone, oznaczane zwykle - (minus) lub x.
Postać tabelaryczna dla funkcji silnie nieokreślonych może mieć postać skróconą, obejmującą tylko stany 0 i 1 (stany nieokreślone są pominięte).
W tabeli przedstawia się również zespoły wielu funkcji (dla układów wielowyjściowych).
Postać kanoniczna.
Jest to postać wynikająca z teorii algebry Boole'a. Występuje w dwóch formach:
- postać kanoniczna sumy KPS (stosowana częściej)
- postać kanoniczna iloczynu KPI
Wyrazy KPS są iloczynami wszystkich kombinacji zmiennych funkcji. Nazywane są implikantami.
Wyrazy KPI są sumami wszystkich kombinacji zmiennych funkcji. Nazywane są implicentami.
W KPS funkcja stanowi sumę iloczynów (implikantów) pomnożonych przez wartości funkcji. Implikanty dla 0 znikają:
W KPI funkcja stanowi iloczyn sum (implicentów) z dodanymi wartościami funkcji. Implicenty dla 1 znikają:
W praktyce najczęściej stosuje się postać skróconą KPS. W tym zapisie można również uwzględnić stany nieokreślone przez podanie indeksów tych stanów w nawiasach okrągłych:
Jest to metoda graficzna. Jest wygodna dla funkcji od 2 do 6 zmiennych. Dla większej ilości zmiennych staje się zbyt trudna.
Metoda ta występuje w dwóch wersjach: dla postaci sumacyjnej oraz dla postaci iloczynowej. Poniżej omówiona jest metoda dla postaci sumacyjnej.
Postępujemy według następujących punktów:
Funkcję należy przedstawić w postaci kanonicznej lub tabelarycznej.
Tworzymy tabelę dla odpowiedniej ilości zmiennych
2 zmienne
3 zmienne
4 zmienne
lub
5 zmiennych
lub
Wartości umieszczone z lewej strony i u góry oznaczają wartości podanych zmiennych
W kratki tabeli wpisujemy wartości funkcji ("0", "1" lub "-") zgodnie z postacią funkcji.
Zakreślamy pola (grupy) w siatce tabeli zgodnie z następujacymi zasadami:
Pole jest kwadratem lub prostokątem o bokach będących potęgą 2, tzn. 1, 2, 4, 8, ..
Pola obejmują kratki sąsiednie, kratki skrajne (pola mogą być "zawinięte" przez brzeg tablicy), oraz w tabeli dla 5 zmiennych symetryczne względem podwójnej linii.
Grupy muszą objąć wszystkie "1".
Grupy nie mogą obejmować "0".
Stany nieokreślone "-" mogą, ale nie muszą być zakreślane.
Grupy powinny być jak największe.
Ilość grup powinna być możliwie mała.
Grupy mogą na siebie zachodzić.
Odczytu funkcji wykonujemy według zasad:
Funkcja ma postać normalną sumy, tzn. suma implikantów prostych. W niektórych zastosowaniach wygodniej jest wypisać implikanty proste w postaci dwójkowej, np:
abd- = (01-1)
Jednemu polu odpowiada jeden implikant.
Jeżeli zmienna przyjmuje dla danego pola wartość 1 to piszemy ją wprost.
Jeżeli zmienna przyjmuje dla danego pola wartość 0 to piszemy ją z negacją.
Jeżeli zmienna przyjmuje dla danego pola wartości 0 i 1 (zmienia wartość), to jej nie piszemy.
W razie potrzeby można dokonać dalszych przekształceń funkcji.
Metoda ta może być stosowana dla funkcji dowolnej liczby zmiennych, a w praktyce - gdy liczba zmiennych przekracza pięć. Spotyka się dwa warianty: dla funkcji w postaci kanonicznej uproszczonej dwójkowej i dziesiętnej. Postać dziesiętna jest częściej stosowana, dlatego tą właśnie przedstawiam.
Metoda QMC realizowana jest w dwóch etapach:
ETAP I ma na celu wyznaczenie wszystkich prostych implikantów.
ETAP II polega na wybraniu ze zbioru prostych implikantów minimalnego zestawu pokrywającego wszystkie jedynki funkcji.
Postępujemy według następujących punktów:
Funkcję należy przedstawić w postaci kanonicznej dziesiętnej lub tabelarycznej.
ETAP I
Wyznaczamy tzw. indeksy dla składników jedynek i stanów nieokreślonych. Indeksem liczby dziesiętnej nazywa się ilość jedynek w odpowiadającej jej liczbie dwójkowej.
Tworzymy zbiór Z0 grupując składniki jedynek i stanów nieokreślonych według indeksów. W granicach grupy należy je uporządkować.
Tworzymy zbiór Z1 sklejając wyrazy zbioru Z0 według nastepujących zasad:
Sklejeniu podlegają dwie liczby sąsiednich grup różniące się potęgą dwójki (1,2,4,8,...)
Sklejane liczby muszą być uporządkowane, np. skleimy liczby 9 i 11, a nie liczby 9 i 7 mimo tej samej różnicy.
Liczby ze zbioru Z0 użyte do sklejania należy zaznaczyć.
Próbie sklejania należy poddać wszystkie pary liczb sąsiednich grup.
Liczba może być wielokrotnie użyta do sklejania.
W zbiorze Z1 wpisujemy użyte liczby oraz w nawiasie różnicę.
Tworzymy kolejne zbiory Z2, Z3 ... (dopóki się da) sklejając wyrazy poprzednich zbiorów, przy czym dodatkowo obowiązują zasady:
Sklejeniu podlegają dwa składniki o tych samych różnicach.
Porównuje się pierwsze wyrazy składników (różnice jw, tzn 1,2,4,8,...).
W zbiorze wynikowym wpisujemy wszystkie użyte liczby oraz w nawiasie wszystkie różnice.
Powtarzające się implikanty wypisujemy tylko raz.
Nie zaznaczone (nie użyte do sklejania) implikanty stanowią pełny zbiór implikantów prostych (na rysunku powyżej oznaczone gwiazdką).
ETAP II
Z wyznaczonego w I etapie pełnego zbioru implikantów prostych dokonujemy wyboru minimalnej ilości pokrywającej wszystkie "jedynki". Realizuje się to za pomocą tablicy Quine'a zwanej inaczej tablicą pokryć. Wiersze tej tablicy odpowiadają implikantom prostym (I etap), natomiast kolumny składnikom jedynek.
Oznaczamy (np: "+") pokrycia jedynek przez implikant.
Jeżeli w którejś z kolumn znajduje się tylko jeden znak + to odpowiadający mu implikant jest niezbędny (jest to tzw. zasadniczy prosty implikant). Należy wyszukać wszystkie zasadnicze proste implikanty i je oznaczyć. Oznaczamy również wszystkie jedynki (kolumny) pokrywane przez te implikanty.
Dla dalszej analizy oznaczone wcześniej wiersze i kolumny można z tablicy wykreślić. Nie jest konieczne przerysowywanie tabeli, ale w przypadku dużych tabel daje to lepszą czytelność.
Usuwamy z tabeli wiersze zdominowane. Wiersz zdominowany to taki, dla którego istnieje inny wiersz (dominujący) nakrywający te same jedynki (i ew. inne). Wierszem zdominowanym jest również wiersz pusty.
Usuwamy z tabeli kolumny dominujące. Kolumna dominująca to taka, która jest pokrywana przez wszystkie wiersze pokrywające inną kolumnę (zdominowaną).
Jeżeli w wyniku poprzednich skreśleń pojawiły się wtórne implikanty zasadnicze, to je oznaczamy i skreślamy.
Jeżeli tabela ma nieskreślone wiesze i kolumny, a powyższych reguł nie da się już dalej stosować należy przeprowadzić tzw. analizę Petricka (patrz dalej) lub wybrać implikanty w sposób intuicyjny.
Oznaczone w powyższych etapach oraz wyznaczone w analizie Petricka implikanty stanowią zbiór minimalny. Zapis postaci funkcyjnej ułatwi tabelka (jak w przykładzie). Wypisujemy pierwszą liczbę implikantu oraz skreślamy pozycje o wagach będących różnicami implikantu. Dalej już prosto: 1 - zmienna, 0 - zmienna z negacją, skreślenie - brak zmiennej.
Analiza Petricka stosowana jest m.in. do wyznaczenia minimalnego zestawu pokryć w tabeli Quine'a. Weźmy przykładową tablicę Quine'a:
Dla uproszczenia implikanty proste oznaczono dużymi literami, a składniki jedynek małymi.
Rozumowanie jest następujące:
Aby pokryć składnik a należy użyć implikantów A lub B → (A+B)
Aby pokryć składnik b należy użyć implikantów C lub D → (C+D)
Aby pokryć składnik c należy użyć implikantów B lub C → (B+C)
Aby pokryć składnik d należy użyć implikantów A lub C → (A+C)
Aby pokryć składnik e należy użyć implikantów B lub D → (B+D)
Tak więc powinno być prawdziwe wyrażenie będące iloczynem powyższych sum.
Następnie należy przekształcić wyrażenie typu "iloczyn sum" tak, aby uzyskać "sumę iloczynów". Należy wykorzystać grupowanie wyrazów podobnych i prawa pochłaniania. Ten etap wymaga dobrej umiejętności w posługiwaniu się prawami Boole'a.
Z powyższych obliczeń wynika, że należy użyć implikantów B i C, gdyż stanowią zbiór najmniej liczny. Można też użyć jednego z pozostałych zbiorów (ACD lub ABD), o ile jest to korzystniejsze z innych względów, np. z prostszych postaci implikantów.
Technika cyfrowa
lub
lub
