Karnaugh.doc

Optymalizacja układów logicznych

1. Wstęp
2. 1. Układy cyfrowe to rodzaj układów elektronicznych, w których sygnały napięciowe przyjmują tylko określoną liczbę poziomów, którym przypisywane są wartości liczbowe. Najczęściej (choć nie zawsze) liczba poziomów napięć jest równa dwa, a poziomom przypisywane są cyfry 0 i 1, wówczas układy cyfrowe realizują operacje zgodnie z algebrą Boole'a i z tego powodu nazywane są też układami logicznymi. Obecnie układy cyfrowe budowane są w oparciu o bramki logiczne realizujące elementarne operacje znane z algebry Boola: iloczyn logiczny (AND, NAND), sumę logiczną (OR, NOR), negację NOT, różnicę symetryczną (XOR) itp. Ze względu na stopień skomplikowania współczesnych układów wykonuje się je w postaci układów scalonych.
   2. W przypadku złożonych funkcji wielu zmicnnych wyszukiwanie wyrażeń podlegających sklejaniu oraz ich sklejanie metodą przekształceń algebraicznych staje się bardzo uciążliwe, zwłaszcza, że dla otrzymania postaci minimalnej trzeba dokonać wszystkich możliwych sklejeń. Istnieją metody upraszczające procedurę minimalizacji. Jedną z nich jest metoda tablic Karnaugha. Stosuje się ją do maksymalnie 6 zmiennych.  Polega ona na zapisaniu kolejnych wartości funkcji w tablicy(prostokątnej lub kwadratowej), a później na łączeniu zer lub jedynek. Gdy łączymy zera, uzyskujemy funkcję złożoną z pełnych sum, a gdy łączymy jedynki, uzyskujemy pełne iloczyny.

3. 3. Zasady zakreślania grup:
   4. 1. Liczba pól musi być potęgą liczby 2
      2. Łączone pola muszą ze sobą sąsiadować(tyczy się to też pól na krawędziach)
      3. Połączone pola muszą tworzyć kwadraty lub prostokąty
      4. Jeżeli w tablicy występują znaki „ – ”(czyli funkcja jest nieokreślona), to takie pola można łączyć z zerami lub jedynkami. Ma to sens, gdy pozwala nam zakreślić większą grupę zamiast mniejszej.
4. 
   Wykonane ćwiczenia
5. 1. Zaprojektuj dwuwejściowy układ logiczny realizujący działanie określone następującą tabelą prawdy:

o       Z logiki wiemy, że powyższa tabela prawdy określa działanie funkcji implikacji logicznej.

o       Funkcję implikacji możemy przedstawić jako sumę zanegowanego p i q.

o       Metodą tabeli Karnaugh zaznaczając „1”

W poziomej grupie nie zmienia się wartość zmiennej p ale że jest ona równa 0, to zapisujemy ją z negacją. W grupie pionowej nie ulega zmianie wartość zmiennej q. ze względu na to że zaznaczaliśmy „1”, dodajemy obie zmienne. W efekcie uzyskujemy funkcję:

o       Metodą tabeli Karnaugh zaznaczając „0”

Mamy zaznaczoną tylko jedną grupę. Ponadto grupa ta składa się tylko z jednej wartości. Dlatego zapisujemy obie zmienne z tym że wartość p negujemy (zaznaczaliśmy „0”). W efekcie uzyskujemy:

o       Układ logiczny narysowany za pomocą 1 bramki:

2. 2. Zaprojektuj dwuwejściowy układ logiczny realizujący działanie określone następującą tabelą prawdy:

-         Metodą tabeli Karnaugh zaznaczając grupy „0”

              Nie zaznaczamy jednej grupy złożonej z dwóch wartości, gdyż wtedy uzyskalibyśmy układ złożony tylko z jednej zmiennej. W efekcie uzyskujemy nastepującą funkcję:

Układ logiczny realizujący działanie tej funkcji:

Dowód działania w postaci tabeli prawdy: