Minimalizacja funkcji logicznych


      Temat nieco trudny, ale konieczny. Adresowany do elektroników zajmujących się projektowaniem, (wymyślaniem), i nie tylko, różnych układów cyfrowych niekoniecznie związanych z naszą Atarynką. Zakładam, że czytelnik tego opisu wie i orientuje się jak działają bramki (to takie "klocki" elektroniczne współczesnej techniki cyfrowej). To co opisano niżej, dotyczy tzw. kombinacyjnych układów logicznych, (są też sekwencyjne, ale na razie damy sobie z tym spokój).

Dla przypomnienia krótka ściągawka, tzw. "tablica prawdy":

AND
NAND
OR
NOR
NOT
A B C
0 0 0
0 1 0
1 0 0
1 1 1
A B C
0 0 1
0 1 1
1 0 1
1 1 0
A B C
0 0 0
0 1 1
1 0 1
1 1 1
A B C
0 0 1
0 1 0
1 0 0
1 1 0
A C
0 1
1 0
A-B - wejścia, C - wyjście

Są jeszcze inne, np. EXOR, ale to temat na inną lekcję!

Przykład/założenia:

Urządzenie pomiarowe ma cztery wejścia na których oczywiście pojawić się może sygnał cyfrowy. A ten jak wiemy jest reprezentowany albo przez 0, co oznacza stan niski, (zero logiczne), albo przez 1, stan wysoki, (logiczna jedynka). Urządzenie ma też dwa wyjścia, które wysterowują coś tam, w tej chwili jest to nieistotne, tak samo jak nieistotne jest to, jakie czujniki wymuszają odpowiednie sygnały wejściowe. Ważne, że zarówno jedne jak i drugie są sygnałami cyfrowymi!

Zadanie:

Zaprojektować układ kombinacyjny który realizować będzie następującą funkcję, do powyższego założenia.

A, B, C, D- to syganły wejściowe
E, F- to sygnały wyjściowe
-- kreseczka informuje, że sygnał wyjściowy może być dowolny, (0 lub 1), a i tak urządzenie działać będzie prawidłowo

     A B C D  E F
 0   0 0 0 0  0 1
 1   0 0 0 1  0 0
 2   0 0 1 0  - 1
 3   0 0 1 1  - 0
 4   0 1 0 0  - 1
 5   0 1 0 1  1 1
 6   0 1 1 0  1 0
 7   0 1 1 1  - 1
 8   1 0 0 0  - 0
 9   1 0 0 1  - 0
10   1 0 1 0  1 0
11   1 0 1 1  1 0
12   1 1 0 0  - 1
13   1 1 0 1  1 0
14   1 1 1 0  - -
15   1 1 1 1  1 -

Jak widać, sygnały wejściowe układają się nam w "piękną" reprezentację liczb od 0-15, ale w zapisie dwójkowym. Nic dziwnego, wejść jest cztery, a każdy wie, że w takim wypadku może być dokładnie szesnaście kombinacji sygnałów. Ale co z tymi sygnałami wyjściowymi! Są jakieś "dziwne", trudno w nich dopatrzeć się logiki. To tylko pozory! Czego dowiadujemy się z analizy pierwszego wiersza:
          A B C D  E F
      0   0 0 0 0  0 1

Ano, że jeżeli wszystkie sygnały wejściowe są zerem, to sygnał wyjściowy E ma być zerem a F jedynką. Aby to zrealizować wystarczy wziąść czterowejściową bramkę typu AND i w prosty sposób otrzymamy sygnał wyjściowy E, (patrz tablica prawdy). A sygnał wyjściowy F zrealizuje nam czterowejściowa bramka typu NAND. Podobnej analizie możemy poddać pozostałe wiersze.

Rozważmy nieco trudniejszy przypadek, np. wiersz 4

          A B C D  E F
      4   0 1 0 0  - 1

Tu sygnał wyjściowy E może być zarówno jedynką jak i zerem, nie ma to znaczenia dla pracy układu.

Jeżeli zanegujemy sygnały wejściowe A,C,D i wszystkie cztery podamy na wejścia czterowejściowej bramki AND to otrzymamy na wyjśiu E jedynkę, co automatycznie może być użyte dla wysterowania sygnału wyjściowego F. Nietrudno zauważyć, że zaczyna się to coraz bardziej gmatwać, i jest tego za dużo do zapamiętania. Zaczyna też powstawać bardzo rozbudowany układ logiczny który to zrealizuje. A to jest dopiero pierwszy poziom tworzenia z sygnałów wejściowych, sygnału wyjściowego! Dochodzimy do wniosku, że należy użyć jakiejś innej, bardziej przejrzystej metody. Tworzenie z "kupy" zagmatwanych łączeń, tylko kilku, które i tak zrealizują tą samą funkcję, nazywa się Minimalizacją funkcji logicznych. Trudne słowo, ale metoda prosta.

      Podarujemy sobie wywody na temat różnych kodów dwójkowych tej samej liczby dziesiętnej. Warto jednak wspomnieć o jednym, o kodzie GRAYA. A cóż to takiego? Kod GRAYA to taki kod, że każda następna liczba dwójkowa ma tylko zmieniony jeden bit w stosunku do poprzedniej jak i następnej pozycji w szeregu Należy do tzw. kodów niewagowych. Oto ten kod dla liczb od 0-7

0  000
1  001
2  011
3  010
4  110
5  111
6  101
7  100
   pierwsza pozycja też różni się tylko jednym bitem od pozycji ostatniej, czyli 7

0  000
7  100

Właśnie kod GRAYA znalazł zastosowanie w minimalizacji z powodu swojej specyficznej właściwości. Opisana jest nim tzw. tablica KARNAUGHTA (czyt. KANO) kolejny dziwoląg? Nic podobnego, oto ta tablica dla reprezentacji czterech zmiennych wejściowych, akurat nadaje się dla naszego przykładu.
                 D0 1 1 0
                 C0 0 1 1
              AB
              00  0 0 - -

              01  - 1 1 -

              11  - 1 1 -

              10  - - 1 1

Pionowo reprezentowane są sygnały (czyli zmienne) A i B, a poziomo C i D Tablica jest już wypełniona sygnałami wyjściowymi w/g założeń naszego zadania, dla sygnału wyjścia E. Gdy A, B, C, D=0 to E=0 i w odpowiednią kratkę wpisujemy 0, itd...

      Co teraz. Gdy tablica jest już prawidłowo wypełniona, przystępujemy do tzw. sklejania, czyli zakreślamy maksymalnie duży obszar w którym znajdować się będą same jedynki (ewentualnie też kreseczki (-), bo przyjmujemy, że tam gdzie kreseczka, równie dobrze mogłaby być jedynka. Jak sklejamy: Obszarem może być albo prostokąt, albo kwadrat, ale ich pola (ilość zaznaczonych pozycji) MUSI być potęgą dwójki. Czyli obszary mogą mieć tych pól 1, 2, 4, 8, 16, itd. (dla większych tablic). Raz jeszcze ta sama tablica z zaznaczeniem pierwszego obszaru a obok jest zaznaczony drugi obszar (włącz opcję MRUGAJ w czytniku):

           D0 1 1 0        D0 1 1 0
           C0 0 1 1        C0 0 1 1
        AB              AB
        00  0 0 - -     00  0 0 - -

        01  - 1 1 -     01  - 1 1 -

        11  - 1 1 -     11  - 1 1 -

        10  - - 1 1     10  - - 1 1

Proszę zauważyć, że drugi obszar można było inaczej zaznaczyć, obejmując nim dwa dolne wiersze! Efekt byłby podobny, z tym że, powstałyby inne tzw. formuły Boolowskie o czym niżej. Błędem byłoby obejmować jednym obszarem trzy dolne wiersze, co prawda nie byłoby w nim zer, i byłby to prostokąt, ale ilość jego pól nie byłaby potęgą dwójki!. W tym obszarze byłoby dwanaście pól! Co nam to dało? Tymi dwoma obszarami objęliśmy wszystkie jedynki, w związku z tym proces sklejania mamy zakończony Gdyby jeszcze w tablicy jedynka była zaznaczona w górnym lewym rogu, na pozycji AB=00 CD=00, to należałoby też objąć ją jakimś obszarem w tym wypadku trzecim. Można by było tylką ją samą objąć obszarem, bo tak też można, ale z tablicy wynika, że kiedy skleimy wszystkie rogowe pola w jeden obszar to powstanie kwadrat! A o to chodzi, by obszary były jak największe! Jak to możliwe zapytasz? Otóż wyobraź sobie że tablica Karnaughta nie jest narysowana na płaszczyźnie, ale na kuli! Czy teraz widzisz ten kwadrat?

Przystępujemy dla wyznaczenia formuł Boolowskich. Jak się to robi? Patrzymy na pierwszy obszar, widać że sygnał A, jest raz zerem, a raz jedynką, odrzucamy go! Sygnał B jest tylko jedynką, pozostaje Syganły C i D odrzucamy, bo raz są zerem a raz jedynką. Teraz drugi obszar. Odrzucamy sygnały A,B i D, bo nie spełniają warunku, jednakowości, natomiast synał C pozostaje, bo jest jedynką. Gdyby np. drugi obszar obejmował sobą dwie pierwsze kolumny, to też postąpilibyśmy podobnie z tym że sygnał C, należałoby zanegować, by spełniał warunek "być jedynką", i jako taki powinien brać udział w tworzeniu sygnału wyjściowego E.

Podsumujmy: do utworzenia sygnału wyjśiowego E, potrzebne są tylko sygnały wejściowe B i C. No więc sumujemy logicznie dwa sygnały B i C (co zrobi nam jedna bramka NOR), i otrzymujemy sygnał wyjściowy E, o poziomach zgodnych z założeniem. Dlaczego sumujemy? Bo wyznaczamy sumę iloczynów!

Podam jeszcze, dla ciekawych, że gdybyśmy zakreślili tylko środkowe jedynki w pierwszym obszarze, to sygnały B i D, ale połączone jako iloczyn logiczny byłyby brane pod uwagę. Otrzymalibyśmy taki układ: Sygnały B i D podlegałyby operacji AND, a sygnał z wyjścia tej bramki należałoby podać na bramkę NOR, łącznie z sygnałem C. Efekt byłby taki sam (proszę sprawdzić), ale... wcale przez to nie powstałaby najprostsza realizacja danej funkcji. To oczywiste, zamiast jednaj bramki (jak nam wyszło), należy teraz użyć dwóch bramek. Jasne jest zatem, dlaczego w tablicy Karnaughta należy dążyć do zakreślania jaknajwiększych obszarów i by było ich jaknajmniej! Ale, w tablicy WSZYSTKIE jedynki (zera) MUSZĄ przynależeć do jakiegoś obszaru!

      Na koniec w ramach zadania domowego, czytelnik tego opisu powinien spróbować (oczywiście jeżeli nie potrafi jeszcze tego), sam wyznaczyć minimalną formułę Boolowską dla otrzymania sygnału wyjściowego F. Warto dodać, że opisany jest sposób na wyznaczanie sum iloczynów, tak się to nazywa, bo w tablicy zakreślaliśmy jedynki. Jeżeli byłyby zakreślane zera bo też tak można, to wtedy wyznaczalibyśmy iloczyn sum. W praktyce polega to na tym, że wpierw łączylibyśmy za pomocą bramek NOR dane sygnały, a potem dopiero tak powstałe sygnały cząstkowe poddawali operacji AND.

      Ufff... mam nadzieję, że ktoś to zrozumiał. Zapewniam że to działa, o czym upewnia nas działająca Atarynka która przecież została zaprojektowana w oparciu o realizację powyższego! Opisana metoda jest jedną z wielu. Jednak uważam (z praktyki), że jest łatwa i przejrzysta :-) dlatego nią posługuję się od lat. Jeżeli ktoś zdobyłby się na wysiłek napisania programu na Atari do minimalizowania funkcji logicznych, to polecam metodę Quine'a-McCluskeya (Q-M). Służę doradą. Moim zdaniem metoda Q-M idealnie nadaje się do napisania programu, a z tego co wiem nikt jeszcze takowego nie napisał! Ci, którzy mają dostęp do "większego brata" naszej Atarynki (PC), niech zainteresują się programem ESPRESSO, jeżeli ich to.... interesuje!

      Zdaję sobie sprawę, że w tak krótkim artykule :-) nie można opisać wszystkiego, zatem potraktujmy go jako zwiastun tego co potrzebne.

A oto, raz jeszcze schematy tablic do wyznaczenia minimalnych funkcji logicznych dla naszego przykładu.

Zenon/DIAL