1 Dr Galina Cariowa

2 Legenda  Optymalizacja układów dwupoziomowych.  Kryterium kosztu realizacji.  Tablica (mapa) Karnaugh’a.  Metoda Quine’a – Mc Cluske’a.

3 Złożoność układu Złożoność cyfrowego układu logicznego, który realizuje funkcję boolowską, jest bezpośrednio związana z wyrażeniem algebraicznym, na podstawie którego ta funkcja została zaimplementowana.

4 Kryterium kosztu realizacji Ze względu na koszt literału pierwsze równanie jest prostsze.

5 Kryterium kosztu realizacji Poniższe równania opisują tą samą funkcję G: Koszt literału w realizacji obu równań wynosi 8, ale pierwsze równanie ma 2 iloczyny, a drugie ma ich 4! Pierwsze równanie jest tańsze w realizacji od drugiego..

6 Kryterium kosztu realizacji Koszty wejść bramkowych odpowiednio 10 i 12 ( lub 14 i 16 uwzględniając wejścia inwerterów). Pierwsze równanie ma niższy koszt realizacji.

7 Koszt wejść bramkowych Inwertery liczone są wówczas, gdy zmienne wejściowe w postaci zanegowanej nie są dostępne bezpośrednio. W przypadkach, gdy postać równania jest bardziej złożona niż suma iloczynów czy iloczyn sum lub w układzie występują złożone typy bramek, koszt wejść bramkowych musi być określany bezpośrednio z implementacji.

8 Minimalizacja funkcji boolowskich Ogromny wzrost zainteresowania minimalizacją funkcji powstał w latach 80. Przyczyną jest możliwość realizacji układów logicznych w strukturach scalonych o złożoności milionów bramek logicznych.

9 Minimalizacja Minimalizacja-proces, który pozwala na uzyskanie jak najmniejszej struktury Minimalizacja formalna układowa Doprowadzenie do uzyskania funkcji o jak najmniejszej liczbie zmiennych i działań logicznych. Doprowadzenie do uzyskania minimalnej liczby elementów potrzebnych do maksymalnej użyteczności i niezawodności.

10 Metody minimalizacji  Metoda przekształceń opartych na prawach algebry logiki.  Metody algorytmiczne: - metoda tablic Karnaugha; - metoda Quine’a – Mc Cluskey’a; - inne (zaawansowane);  Metoda i system Espresso (1984), Uniwersytet Kalifornijski w Berkeley. Pierwsze skuteczne narzędzie do minimalizacji wieloargumentowych i wielowejściowych funkcji boolowskich.

11 Optymalizacja Optymalizacja - proces, który pozwala na uzyskanie jak najszybszej, najskuteczniejszej struktury. Optymalizacja - wyznaczenie spośród dopuszczalnych rozwiązań danego problemu rozwiązania najlepszego ze względu na przyjęte kryterium jakości (np. koszt, zysk, niezawodność). Badaniem metod optymalizacji zajmuje się teoria optymalizacji.

12 Minimalizacja funkcji logicznych Minimalizacja funkcji logicznych polega na upraszczaniu wyrażeń logicznych, tak aby zawierały jak najmniejszą liczbę tylko niezbędnych argumentów oraz operacji logicznych. W wyniku minimalizacji uzyskujemy wyrażenie równoważne, ale mające najprostszą postać i najmniejszy koszt realizacji.

13 Minimalizacja funkcji boolowskich Metoda algebraiczna

14

15 Tablica Karnaugh’a (1950) Tablica Karnaugh’a- prostokątna tablica, zawierająca kwadratów dla funkcji n zmiennych po jednym na każdy minterm. Przykład. Tablica dla dwóch zmiennych: m0m0 m1m1 m2m2 m3m3 Zależności między kwadratami tablicy a dwoma zmiennymi: 0 i 1 wpisane po lewej stronie oraz u góry tablicy oznaczają wartości zmiennych.

16 Tablica Karnaugh’a Funkcja dwóch zmiennych może być przedstawiona w tablicy Karnaugha przez oznaczenie kwadratów odpowiadających mintermom funkcji. Trzy kwadraty z jedynkami należą do obszaru złożonego z dwóch kwadratów w drugim wierszu dla x oraz obszaru złożonego z dwóch kwadratów w drugiej kolumnie dla y. Uzasadnienie tego uproszczenia:

17 Tablica Karnaugh’a- definicja Tablica dla trzech zmiennych: (n=3) m 0 m 1 m 3 m 2 m 4 m 5 m 7 m 6 Liczby, znajdujące się wzdłuż krawędzi tablicy nie stanowią ciągu binarnego, lecz sąsiednie kombinacje różnią się tylko na jednej pozycji (Kod Gray’a). Dla każdej zmiennej są cztery kwadraty, w której jej wartość wynosi 1, i cztery kwadraty, dla których przyjmuje ona wartość 0.

18 Kod Gray’a

19 Tablica Karnaugh’a Podstawowa własność przylegających do siebie kwadratów: Dowolne dwa przylegające do siebie w pionie lub poziomie (nie po skosie) kwadraty, które tworzą prostokąt, odpowiadają mintermom różniącym się tylko jedną zmienną, która może zostać usunięta w czasie tworzenia sumy logicznej OR obu mintermów. Reguły sklejania

20 Tablica Karnaugh’a Za sąsiednie uważa się także kombinacje kratki pierwszej i ostatniej kolumny. Przykład: Wynikiem dodania do siebie dwóch mintermów w przyległych kwadratach tablicy trzech zmiennych jest iloczyn dwóch zmiennych.

21 Tablica Karnaugh’a Dokonać uproszczenia funkcji boolowskiej: 1.Zaznaczamy jedynki w każdym mintermie, który reprezentuje funkcję. 2. Szukamy najmniejszej liczby prostokątów, które pokrywają wszystkie mintermy oznaczone 1. Trzy zaznaczone prostokąty zawierają wszystkie jedynki w tablicy. Zoptymalizowane wyrażenie na funkcję:

22 Tablica Karnough’a. Przedstawienie zminimalizowanej funkcji w postaci CCF.

23 Tablica Karnaugh’a Jeśli funkcja nie jest wyrażona za pomocą sumy mintermów, można użyć tablicy Karnaugha do znalezienia jej mintermów, a następnie można wykonać uproszczenie. Trzy wyrazy iloczynowe mają po dwa literały. Każdy z tych iloczynów jest reprezentowany w tablicy dwoma kwadratami. Przykład.

24 Cechy tablicy Karnaugha dla trzech zmiennych:  Prostokąt składający się z dwóch kwadratów reprezentuje iloczyn dwóch zmiennych.  Prostokąt składający się z czterech kwadratów reprezentuje iloczyn złożony z jednego literału.  Prostokąt składający się z ośmiu kwadratów tworzy funkcję zawsze równą logicznej 1.

25 Tablica Karnaugh’a (dla czterech zmiennych ) m 0 m 1 m 3 m 2 m 4 m 5 m 7 m 6 m 12 m 13 m 15 m 14 m 8 m 9 m 11 m 10 Przypisanie poszczególnych kwadratów do mintermów: Związek między kwadratami tablicy a czterema zmiennymi:: Numery wierszy i kolumn zapisane w dwubitowym kodzie Gray’a.

26 Tablica Karnaugh’a ( dla czterech zmiennych) Numery mintermów odpowiadające każdemu kwadratowi tablicy można otrzymać przez połączenie numeru wiersza z numerem kolumny. Przykład. Jeśli połączymy numer trzeciego wiersza (11) i czwartej kolumny (10), uzyskamy liczbę dwójkową 1110, która jest binarnym odpowiednikiem 14. Na przecięciu trzeciego wiersza i czwartej kolumny znajduje się minterm m 14. m 14

27 Tablica Karnaugh’a. Wypełnianie tablicy czterech zmiennych. Każdemu polu, w którym wpisana jest jedynka, odpowiada elementarny iloczyn funkcji

28 Minimalizacja funkcji boolowskich Tablica Karnaugha

29 Tablica Karnaugh’a ( dla czterech zmiennych ) Wyznaczamy zbiór kwadratów (prostokątów) tablicy reprezentujących iloczyny, które będą brane pod uwagę w uproszczonym wyrażeniu. Prostokąty mogą zawierać tylko taką liczbę kwadratów tablicy, która stanowi potęgę liczby 2 (1,2,4,8,…). Celem jest: znalezienie najmniejszej liczby takich prostokątów, które pokrywają wszystkie mintermy oznaczone 1.

30 Minimalizacja funkcji boolowskich Tablica Karnaugh’a Sposoby grupowania kwadratów tablicy : wx yz

31 Minimalizacja funkcji boolowskich Tablica Karnaugh’a Sposoby grupowania kwadratów tablicy:

32 Minimalizacja funkcji boolowskich Tablica Karnaugh’a Sposoby grupowania kwadratów tablicy:

33 Minimalizacja funkcji boolowskich Tablica Karnaugh’a Sposoby grupowania kwadratów tablicy:

34 Minimalizacja funkcji boolowskich Tablica Karnaugh’a Sposoby grupowania kwadratów tablicy:

35 Minimalizacja funkcji boolowskich Tablica Karnaugh’a

36 Cechy tablicy Karnaugha dla czterech zmiennych :  Prostokąt składający się z dwóch kwadratów reprezentuje iloczyn trzech zmiennych.  Prostokąt składający się z czterech kwadratów reprezentuje iloczyn dwóch literałów.  Prostokąt składający się z ośmiu kwadratów reprezentuje iloczyn, którym jest pojedynczy literał.  Prostokąt składający się z szesnastu kwadratów tworzy funkcję zawsze równą logicznej 1.

37 Minimalizacja funkcji boolowskich

38 Tablica Karnaugh’a

39 Tablica Karnough’a. Przedstawienie zminimalizowanej funkcji w postaci CCF.

40

41 Implikant funkcji boolowskiej Wyraz iloczynowy jest implikantem funkcji, jeżeli wartość funkcji dla wszystkich mintermów tego wyrazu wynosi 1. Jeżeli usunięcie dowolnego literału z implikantu P spowoduje, że tak powstały iloczyn nie jest już implikantem funkcji, to P nazywamy implikantem prostym. Jeśli minterm funkcji jest zawarty tylko w jednym implikancie prostym, to taki implikant prosty jest istotny. Dla usystematyzowania procedury łączenia kwadratów w tablicy Karnaugha wprowadzimy następujące pojęcia:

42 Implikant funkcji boolowskiej – w interpretacji tablic Karnaugcha W interpretacji tablic Karnaugha wszystkie prostokąty utworzone z kwadratów zawierających jedynki odpowiadają implikantom. Każdy prostokąt zawierający tak dużo kwadratów, jak tylko jest to możliwe, odpowiada prostemu implikantowi. Jeśli prostokąt zawiera co najmniej jeden kwadrat, który nie jest zawarty w żadnym innym implikancie prostym, mówimy, że implikant prosty jest istotnym.

43 Implikant funkcji boolowskiej – interpretacja Implikant Prosty implikant To nie jest implikant! wx

44 Upraszczanie funkcji z użyciem implikantów funkcji 1. Określenie wszystkich implikantow prostych. 2.Tworzenie sumy logicznej wszystkich istotnych implikantów prostych oraz innych implikantów prostych niezbędnych do ujęcia pozostałych mintermów, których nie zawierają istotne implikanty proste. 5 prostych implikantów 3 istotne implikanty proste Minterm 11 wchodzi w skład dwóch nieistotnych implikantów prostych.

45 Zoptymalizowane wyrażenie składa się z sumy logicznej trzech istotnych implikantów prostych i jednego implikantu prostego, który zawiera minterm 11: Upraszczanie funkcji z użyciem implikantów prostych

46 Minimalizacja funkcji boolowskich z wykorzystaniem stanów nieistotnych

47 Minimalizacja funkcji niezupełnych Istnieją zastosowania, w których funkcja jest nieokreślona dla pewnych kombinacji wartości zmiennych: 1) Takie kombinacje sygnałów wejściowych nigdy nie występują (np. kod BCD); 2) Określone kombinacje wejściowe mogą się pojawić, ale nie interesuje nas, w jaki sposób wyjścia odpowiedzą na te kombinacje.

48 Konwencja zapisu funkcji boolowskich x x

49 Implikant funkcji boolowskiej – interpretacja

50 Minimalizacja funkcji z wykorzystaniem stanów nieistotnych x x x x

51

52 Minimalizacja funkcji boolowskich Tablica Karnaugh’a Zoptymalizowane wyrażenie utworzone na podstawie tablicy Karnaugha, zawsze jest w postaci sumy iloczynów lub iloczynu sum. Optymalizacja oparta na tablicach daje optymalizację dwupoziomową. Optymalizacja oparta na tablicach nie nadaje się bezpośrednio do znalezienia możliwej prostszej trzy- lub wielopoziomowej reprezentacji funkcji.

53 Metoda M. Quine’a-McCluskeya (część I) 1. Zapisać funkcję w postaci FDCF. 2. Dla kolejnych zupełnych iloczynów elementarnych zapisać odpowiadające im kombinacje zer i jedynek. 3. Przepisać te kombinacje według liczby jedynek, tworząc grupy.

54 Metoda M. Quine’a-McCluskeya (część I) 4. Porównujemy ze sobą wszystkie kombinacje znajdujące się w dwóch kolejnych grupach. Jeżeli dwie takie kombinacje różnią się tylko jedną pozycją to „sklejamy” je w nową kombinacje (przy wykorzystanych już kombinacjach stawiamy „ * ” ), a zamiast różniącej je pozycji wpisujemy „-”.

55 Metoda M. Quine’a-McCluskeya (część I) 5. Kontynuujemy ten proces dla nowych grup powstałych w wyniku „ sklejania” z tym, że można „sklejać” tylko te kombinacje, które mają „-” na tych samych pozycjach. W przypadku, gdy nie istnieje możliwość dalszego „sklejania” wypisujemy wszystkie kombinacje nie oznaczone „*”).

56 Metoda M. Quine’a-McCluskeya (część II) 1.Rysujemy siatkę z linii poziomych i pionowych, liniom pionowym przyporządkowane są kombinacje odpowiadające zupełnym iloczynom elementarnym minimalizowanej funkcji, a liniom poziomym - kombinacje odpowiadające implikantom prostym otrzymanym w I części algorytmu.

57 Metoda M. Quine’a-McCluskeya (część II) 2. Wstawiamy znak „ ” w miejsce przecięcia linii każdego implikantu prostego z zupełnym iloczynem elementarnym pokrywanym przez ten implikant. 3. Tworzymy minimalny zbiór tych implikantów prostych pokrywających wszystkie zupełne iloczyny elementarne.

58 Metoda M. Quine’a-McCluskeya (przykład 1) 1 1 1 1 0 0 0 00 0 0 000 00 000 0 0 0 0 00 1 1 11 11 11 1 1 1 1 111 Zminimalizować funkcję: Podać minimalną postać sumacyjną.

59 0000 1000 0100 0001 1010 1001 0101 1011 0111 1111 -000 0-00 000- 10-0 100- 010- 0-01 101- 10-1 01-1 1-11 -111 -00- 0-0- -00- 0-0- 10-- Metoda M. Quine’a-McCluskeya (przykład 1) -00- 0-0- 10-- * * * * * *

60 Metoda M. Quine’a-McCluskeya (przykład 1) 0000000101000101011110001001101010111111 01–1 + + 1–11 + + –111 + + –00– + + + + 0–0– + + + + 10–– + + + +

61 Metoda M. Quine’a-McCluskeya (przykład 2) Zminimalizować funkcję niezupełną: Wypisujemy numery wszystkich mintermów ( istotnych i nieistotnych) w postaci dwójkową: 0000, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1101, 1111.

62 Metoda M. Quine’a- McCluskeya (przykład 2) 0000 0-00 -000 0100 1000 010- 01-0 100- 10-0 0101 0110 1001 1010 0111 1101 1111 * 01-- 01-1 -101 011- 1-01 -111 11-1 -1-1 * * - implikanty proste

63 Metoda M. Quine’a- McCluskeya (przykład 2) Implikanty proste 0100 0101 01101000100110101101 0-00 + -000 + 100- + + 10-0 + + 1-01 + + 01-- + + + -1-1 + + Tablica implikantowa

64 Dziękuję za uwagę

65 Tablica Karnough’a. Przedstawienie zminimalizowanej funkcji w postaci DCF. x1x1 x2x3x2x3

66

67 Minimalizacja funkcji boolowskich Metoda algebraiczna

68 Minimalizacja funkcji boolowskich

69 Minimalizacja funkcji boolowskich Tablica Karnaugh’a

70 Minimalizacja funkcji boolowskich

71

72 Metoda M. Quine’a-McCluskeya Implikant