Z pogranicza

Minimalizacja funkcji logicznych

  • 11 komentarzy
  • 1863 odsłony
  • Oceń ten tekst jako pierwszy
Na wstępie należałoby w zasadzie objaśnić podstawy tegoż zagadnienia ? zapis bitowy, funkcje Boolowskie czy też działania na nich. Jednak bądź co bądź jesteśmy na forum programistycznym ? dlatego też ograniczę się w objaśnianiu nudnych podstaw, założeń i od razu postaram się skoncentrować na tym, co w temacie.

Nie raz zapewne programując niezależnie w jakim to języku, czy też C++, Perl lub Delphi mieliście do czynienia z różnymi warunkami. Popularne ?if (a = 1) or (b = 0) and ?? (1) itd. każdy zapewne zna, nawet dopiero co początkujący programista. Zapewne każdy chciał, aby jego kod wyglądał jak najbardziej schludnie i do tego był maksymalnie krótki ? ?ale nie krótszy niż to możliwe?. Problem pojawia się, gdy przychodzi większa ilość danych występujących w naszym warunku. W zależności od tych danych musimy poskładać nasz warunek, aby został spełniony lub też nie. Zasadniczy problem pojawia się w zapisie tychże warunków (funkcji logicznych ? w przypadku zmiennych typu Boolean) zwłaszcza w sytuacjach, gdy ich ilość jest znaczna.

(1) ? aby w jakiś sposób móc zapisywać funkcje ? będą one pisane jak w środowisku Delphi.

Spójrzmy na poniższy przykład: mając dane tylko trzy zmienne Boolowskie (w różnych kombinacjach) nasza funkcja ma mieć taki rezultat:

<image>http://4programmers.net/bin/tabela.jpg</image>

Powstaje pytanie: jak się za to zabrać? Rzecz jasna chcielibyśmy, aby funkcja była możliwie jak najkrótsza. Zapewne można podejść do tego tak jak niektórzy początkujący programiści: spójrzmy gdzie są ?jedynki?, w ten sposób złóżmy wszystkie kombinacje. Jak widać ?jedynka? występuje w drugiej, piątej i szóstej kombinacji, zatem można zapisać tak:

If ((A = 0) and (B = 0) and (C = 1)) or ((A = 1) and (B = 0) and (A = 0)) or ((A = 1) and (B = 0) and (C = 1)) then ?


Ale czy jest to możliwie najkrótsza forma zapisu tejże funkcji? Cóż ? jeśli zadałem to pytanie to zapewne odpowiedź brzmi: Nie. W kolejnym kroku, bardziej zaawansowani programiście zaczną szukać pewnych prawidłowości ? na przykład w każdym przypadku zmienna B przyjmuje wartość 0, można zatem skrócić..

If (((A = 0) and (C = 1)) or ((A = 1) and (C = 0)) or ((A = 1) and (C = 1))) and (B = 0) then ?


.. wyłączając zmienną B poza nawias, teraz ?warunek na B? odwołuje się do wszystkich przypadków. Jednak i ten zabieg nie dał oczekiwanych rezultatów znaczącego skrócenia zapisu.

Istnieje jednak algorytm, który pozwoli na uzyskanie minimalnej formy zapisu ? co prawda nie jest on specjalnie prosty ? jednak czasami może przynieść bardzo dobre efekty. Wykorzystane zostaną tylko trzy typy operatorów (jak w zapisanych powyżej): AND, OR oraz NOT. (2)

(2) NOT w zapisie należy traktować z pewnym założeniem. W zapisach powyżej można użyć tego operatora aby oznaczyć te zmienne, które mają równać się 0, a tam gdzie ?1? ? nie pisać nic jako, że warunek sam w sobie jest tylko Boolowskiego ? nie trzeba ?rzutować? na ten typ stosując znaki równości. A zatem wyrażenie:

If (((A = 0) and (C = 1)) or ((A = 1) and (C = 0)) or ((A = 1) and (C = 1))) and (B = 0) then ?

można zamienić na:

If (((not A) and C) or (A and (not C)) or (A and C)) and (not B) then ?

Zapis staje się jak widać prostszy ? I od tej chwili będziemy używać tej konwencji.


Przed rozpoczęciem warto jeszcze wspomnieć iż istnieją dwa sposoby wykorzystania tegoż algorytmu: SOP [FDCF] (Sum Of Products) oraz POS [FCCF] (Produkt of Sum). Wykorzystamy nasz wcześniejszy przykład, przypomnę:

<image>http://4programmers.net/bin/tabela.jpg</image>

Mamy trzy zmienne, a zatem 2^3 = 8 kombinacji. Funkcja ma przyjmować wartość ?1? tylko dla trzech przypadków. W pierwszym kroku tabelę tą trzeba zamienić na inną postać ? tzw. mapę Karnough.

<image>http://4programmers.net/bin/karno.jpg</image>

Kilka słów wyjaśnienia: Jako kolumny i wiersze zostały podane zmienne A, B, C ? ich kolejność nie ma znaczenia (dokładniej mówiąc nie ma znaczenia czy kolumny będą reprezentowane przez A, B lub C ? podobnie wiersze). We wnętrzu tabeli wpisujemy tylko wartość funkcji dla konkretnej kombinacji ? kombinacja jest określona współrzędną. Na przykład kratka w prawym ?dolnym rogu oznacza rezultat funkcji dla A =1, B = 1 oraz C = 0 (zgodnie ze współrzędnymi). Komentarza wymaga natomiast sposób numerowania kolejnych współrzędnych: spójrzmy na pierwszy wiersz (wiersz opisujący współrzędne): 00, 01, 11, 10. Nie jest to naturalny kod dwójkowy tylko tzw. kod. Gray'a ? w każdej nowej pozycji zmienia się tylko i wyłączenie jeden bit (np. dla trzech argumentów kod Gray`a wyglądałby następująco: 000, 001, 011, 010, 110, 111, 101, 100. Również współrzędne w pierwszej kolumnie są zapisane w tym kodzie ? 0, 1 (chociaż tego nie widać). Trzeba zdawać sobie sprawę, że nie zawsze naturalny kod dwójkowy jest wszędzie optymalnym rozwiązaniem i inne zapisy liczb również są powszechnie stosowane.

Kolejnym krokiem jest połączenie tych samych wartości (samych zer (metoda POS) lub samych jedynek (metoda SOP)) w grupy. Skupmy się na razie na metodzie SOP ? suma produktów. Łączenie w grup również wymaga niestety stosownego komentarza. Powiedzmy sobie, że długość boku grupy może przyjmować tylko wartość 2^n, czyli 1, 2, 4, 8, 16 itd. A zatem grupy 1x2, 2x2, 2x4, 1x4 są dozwolone, a 1x3, 2x3, 4x5 już nie. Pyzatym grupy mogą się dowolnie przecinać (nachodzić jedna na drugą). Kratki mogą się też grupować z prawa na lewa, to znaczy: kratka z prawego ? dolnego rogu może się połączyć z kratką z rogu lewego ? dolnego lub prawego ? górnego. W ten sposób można na przykład zaznaczyć cztery kratki po rogach do jednej grupy ? jak gdyby mapa była zdjęta z siatki kuli. Nie można natomiast łączyć po ukosie.

W naszym przykładzie widzimy tylko trzy jedynki, które bez problemu łączymy w dwie, proste grupy:

<image>http://4programmers.net/bin/karno2.jpg</image>

Gdyby hipotetycznie została jakaś jedynka bez grupy ? łączymy ją w grupę 1x1. W zasadzie należy dążyć do uzyskania jak największych grup.

Trzecim krokiem, zarazem ostatnim jest zapis funkcji stworzony na podstawie grup. Można powiedzieć, że jest to najtrudniejsza część, gdyż wymaga poświęcenia największej uwagi. A robimy to tak: patrzymy po kolei na grupy, niech pierwszą będzie ta zielona (kolejność nie ma znaczenia). Interesują nas tylko te współrzędne, które się nie zmieniają w całej grupie. Będą to zatem: A oraz B (przyjmując wartości odpowiednio 1, 0). Współrzędna C jak widać zmienia się z ?0? na ?1?, a zatem nie bierzemy jej pod uwagę. Zapisujemy iloczyn (AND) tych dwóch współrzędnych z tym, że negujemy (NOT) tam gdzie współrzędna równa jest 0 ? jak widać jest to u nas B. A zatem mamy:

A and (not B)

W ten  sposób otrzymaliście jeden ?produkt?. W metodzie tej jak sama nazwa wskazuje mamy otrzymać ich sumę, a zatem bierzemy następną grupę i postępujemy analogicznie otrzymując:

(not B) and C.

Na końcu pozostaje zsumować produkty (jest ich tyle, ile jest grup). Ostatecznie nasz warunek wygląda tak:

If (A and (not B)) or ((not B) and C) then


W ten sposób dokonaliśmy minimalizacji ? juz na pierwszy rzut oka widać, że jest to zapis bardziej elegancji niż pierwsze próby.

Wspomniałem o metodzie drugiej: POS. Jest to metoda, która działa dokładnie odwrotnie niż powyższa, mianowicie stanowi iloraz pewnych sum. W pierwszej kolejności w grupy zaznaczamy tylko zera (tak samo jak zaznaczaliśmy jedynki). Następnie dokonujemy odczytu odwracając negację: NOT tam gdzie współrzędna ma wartość ?1?. Na końcu (jak się domyślacie) zapis funkcji w postaci:

If (E or G or?) and ((not X) or G or?) itd (nazwy przykładowe).


Który jest jak widać jakby odwrotnością metody SOP.

Na koniec pozostaje pytanie: na ile opłaca się stosować tą metodę minimalizacji? Jeśli ktoś ma dobre oko oraz szybki umysł w zasadzie po kilku chwilach potrafi wysunąć odpowiedni zapis warunku z samych kombinacji, jednak nie zawsze to jest takie proste i oczywiste (np. przy większej ilości kombinacji). Również dla niewielkich ich ilości bywają problemy ? tutaj mamy natomiast pewność, że jest to najlepszy zapis z możliwych (3)

(3) Nie używając funkcji XOR :)

11 komentarzy

ciapol 2009-10-22 19:12

Komentarz do:
"Czegoś nie wiem? Czy zamiast "w zasadzie" powinno być "zawsze" ?
Poza tym do tego zdania przydałoby się dodać, że należy również dążyć do jaknajmniejszego nakładania się bloków [aby nie dublować elementów]."



Zasada jest właściwie jedna: im mniej bloków tym lepiej.

Dannte 2007-09-21 01:57

Drobna uwaga (bo mówimy tu o MINIMALIZACJI): skoro już doszedłeś do "if (A and (not B)) or ((not B) and C) then", to dalej wystarczy zastosować (pq)v(qr)<=>(pvr)^q
i masz "if (A or C) and not B then"
Ale metoda Karnaugh'a ciekawa jest (chociaż w praktyce to nie spotkałem się jeszcze z takimi skomplikowanymi warunkami, by trzeba było - i dało się - je do prostej postaci sprowadzić). Mimo to poczytam o tym. Dzięki, fajny art :)

Piniol 2005-11-11 11:16

Ja tylko dodam, że gdyby ktoś chciał więcej o tym poczytać to czasem nazywa się to również siatką Karnough :)

foflik 2005-11-11 19:01

Prawidlowa nazwa to metoda siatek Karnaugh'a. Przy opisie laczenia w grupy brakuje zasady, ze jezeli grupa jest polozona po obu stronach osi symetrii (siatki, polowki siatki, cwiartki...) to musi byc symetryczna wzgledem tej osi. Mozna by tez dopisac kilka slow o uzyciu w grupach stanow nieokreslonych.

Marooned 2005-11-11 02:04

Dobrze prawisz [mam wykształcenie elektroniczne] jednak tutaj opisane jest raczej zastosowanie w informatyce.

Oczywiście pisząc program do modelowania układów elektronicznych uwaga o której piszesz jest jak najbardziej na miejscu i powinna być jako opcja w programie :).

Marooned 2005-11-12 00:16

folfik - skąd masz pewność, że Twoja nazwa jest poprawna?
Mnie w technikum elektronicznym uczyli, że to nazywa się "tablica Karnaugh" - tablica, siatka czy co tam.. to chyba wymienne określenie

a uwagi o symetrii nie rozumiem :| możesz jaśniej?

P.S. A fakt, kopiowałem nazwisko - rzeczywiście miało być Karna...

foflik 2005-11-12 09:46

Z ta nazwa to chodzilo mi bardziej o pisownie nazwiska w technikum i na studiach uczyli mnie, ze pisze sie Karna.. a nie Karno... Co do symetrii to gdy mamy siatke np 2 mienne na 3 zmienne (4 x 8) i wszedzie mamy 0 poza grupa 2x4 jedynek, grupa ta przecina srodek ale w taki sposob, ze na 1 polowce sa 2 jedynki a na drugiej 6 i sprobuj to zminimalizowac tworzac grupe 2x4. W ogole jesli przejdziemy do wymiarow jednego boku >= 3 zmienne to metdoy sie dosyc komplikuja, mozna np. tworzyc grupy, ktore na papierze wygladaja jak by byly otwarte ;-)

PS.
Jak tlumaczenie niejasne to moge narysowac

Marooned 2005-11-10 22:42

Świetnie!
Co prawda nie czytałem :P [nie mam zwyczaju czytać artów] ale podejście programistyczne do optymalizacji a'la tablica Karnough to jest coś, co często się przydaje.

Taki mały komentarz do:
<quote>W zasadzie należy dążyć do uzyskania jak największych grup.</quote>Czegoś nie wiem? Czy zamiast "w zasadzie" powinno być "zawsze" ?
Poza tym do tego zdania przydałoby się dodać, że należy również dążyć do jaknajmniejszego nakładania się bloków [aby nie dublować elementów].

Sanjuro 2005-11-11 00:34

Marooned: Teoretycznie dazy sie do nienakladania blokow co zmniejszy dlugosc funkcji, ale jest to bledne podejscie gdy mamy do czynienia z ukladem elektronicznym. Po zaznaczeniu blokow i zminimalizowaniu funkcji nalezy przeanalizowac uklad na mozliwosc wystapienia hazardu (krotkotrwale, przypadkowe impulsy wynikajace z czasu propagacji bramek logicznych) i jesli jest takie ryzyko nalezy dolozyc w odpowiednich miejscach bloczki sprzegajace ktore wyeliminuja zjawisko hazardu.

flabra 2005-11-11 07:50

linjki (kwestia jakiegos błędu przy optymalizacji):

If (((A = 0) and (C = 1)) or ((A = 1) and (C = 0)) or ((A = 1) and (C = 1))) and (B = 0) then ?  
If (((not A) and C) or (A and (not C)) or (A and C)) and B then ?

nie dadza takich wynikow jak w tabelce, bo :

If (*) and (B = 0) then ?
If (*) and B then ?

jak widac wszystko wisi na B, wiec linijki w tabelce:

a 0 c | 1  (dla dowolnych a i c) nie dadza oczekiwanego efetku

inna rzecz, ze (b=0) to raczej (not b)

Deti 2005-11-11 09:41

Dzieki za komentarze :) flabra - pomyłka, już poprawiłem, dzieki za wyłapanie.