sobota, 07 grudzień 2024
 
Strona główna Technika cyfrowa Minimalizacja funkcji logicznych

Minimalizacja funkcji logicznych i projektowanie układów kombinacyjnych

  1. Sposoby opisu funkcji logicznych
  2. Metody minimalizacji funkcji logicznych
    - Metoda tablic Karnaugha
    - Metoda Quine'a-McCluskey'a
    - Analiza Petricka

  1. Sposoby opisu funkcji logicznych

  2. 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.

    Przykład: Opis słowny funkcji tworzącej autokorekcyjny kod Hamminga
    Układ wytwarza dodatkowe trzy bity kontrolne (k,l,m) tworzące, wraz z czterema
    bitami (DCBA) kodu BCD8421 7-bitowy kod Hamminga (DCBkAlm).
    Wartości tych bitów te są tak dobrane, aby zachować parzystą liczbę jedynek
    w następujących czwórkach bitów:
      D C B k
      D C A l
      D B A m
    

    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).

    Przykład: Tabele funkcji
    
    

    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.

    Implikanty i implicenty dla funkcji 3 zmiennych
    
    W implikantach:
        wartości 0 odpowiada zmienna zanegowana
        wartości 1 odpowiada zmienna podana wprost
    W implicentach:
        wartości 0 odpowiada zmienna podana wprost
        wartości 1 odpowiada zmienna zanegowana
                            _                 _   _
    np: abc=011 (3) -> I3 = a b c    S3 = a + b + c
                              _           _       _
        abc=101 (5) -> I5 = a b c    S5 = a + b + c
    

    W KPS funkcja stanowi sumę iloczynów (implikantów) pomnożonych przez wartości funkcji. Implikanty dla 0 znikają:

    Postać kanoniczna sumy
    
    

    W KPI funkcja stanowi iloczyn sum (implicentów) z dodanymi wartościami funkcji. Implicenty dla 1 znikają:

    Postać kanoniczna iloczynu
    
    

    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:

    Postać kanoniczna sumy ze stanami nieokreślonymi
    
    
    do góry
  3. Metody minimalizacji funkcji logicznych


  4. Metoda tablic Karnaugha

    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:

    1. Funkcję należy przedstawić w postaci kanonicznej lub tabelarycznej.
    2. Tworzymy tabelę dla odpowiedniej ilości zmiennych
    3. 2 zmienne3 zmienne4 zmienne
      lub
      5 zmiennych
      lub

      Wartości umieszczone z lewej strony i u góry oznaczają wartości podanych zmiennych

    4. W kratki tabeli wpisujemy wartości funkcji ("0", "1" lub "-") zgodnie z postacią funkcji.
    5. Przykład: tabela Karnaugha
      Dla funkcji F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}
      
      
    6. 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ć.
      Przykład: zakreślanie pól w tablicy Karnaugha
      Dla funkcji F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}
      
      
    7. 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.
      Przykład: odczytanie funkcji
      Dla funkcji F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}
      
      
    8. W razie potrzeby można dokonać dalszych przekształceń funkcji.
    9. Schemat układu minimalnego (bez przekształceń).
    10. Przykład: schemat układu
      Schemat układu realizującego funkcję:
      F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}=
      =ab+acd+bc-  --

    do góry

    Metoda Quine'a-McCluskey'a

    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:

    1. ETAP I ma na celu wyznaczenie wszystkich prostych implikantów.
    2. 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:

    1. Funkcję należy przedstawić w postaci kanonicznej dziesiętnej lub tabelarycznej.
    2. ETAP I

    3. 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.
    4. Przykład: indeksy składników funkcji
      F(abcd)=Σ{0,4,5,6,11,15,(2,7,9,12)}
      indeksy=  0 1 2 2  3  4  1 3 2  2
      
    5. 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ć.
    6. Przykład: zbiór Z0
      
      
    7. 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ę.
      Przykład: zbiór Z1
      
      
    8. 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.
      Przykład: dalsze zbiory
      
      
    9. Nie zaznaczone (nie użyte do sklejania) implikanty stanowią pełny zbiór implikantów prostych (na rysunku powyżej oznaczone gwiazdką).
    10. ETAP II

    11. 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.
    12. Oznaczamy (np: "+") pokrycia jedynek przez implikant.
    13. Przykład: tablica Quine'a
      
      
    14. 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.
    15. Przykład: zasadnicze implikanty proste
      
      
    16. 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ść.
    17. Przykład: redukcja tablicy Quine'a
      
      
    18. 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.
    19. Usuwamy z tabeli kolumny dominujące. Kolumna dominująca to taka, która jest pokrywana przez wszystkie wiersze pokrywające inną kolumnę (zdominowaną).
    20. Jeżeli w wyniku poprzednich skreśleń pojawiły się wtórne implikanty zasadnicze, to je oznaczamy i skreślamy.
    21. Przykład: dalsza redukcja
      
      
    22. 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.
    23. 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.
    24. Przykład: odczytanie funkcji
      
      
    25. Schemat układu minimalnego (bez przekształceń).
    26. Przykład: schemat układu
      
      
    do góry

    Analiza Petricka

    Analiza Petricka stosowana jest m.in. do wyznaczenia minimalnego zestawu pokryć w tabeli Quine'a. Weźmy przykładową tablicę Quine'a:

    Przykład: tablica 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.

    Przykład: analiza Petricka
    
    

    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.

    do góry
© mgr inż. Piotr Kotarski, Kalety