1 I T P W ZPT 1 Realizacje funkcji boolowskich Omawiane do tej pory metody minimalizacji funkcji boolowskich związane są z reprezentacją funkcji w postaci wyrażenia boolowskiego typu suma iloczynów (Sum-of- products - SOP), co prowadzi do tzw. realizacji AND-OR. Na przykład:

2 I T P W ZPT 2 Realizacja AND-OR x3x1x2x3x1x2 01 0000 0110 1111 1010 …uzyskane z tablicy Karnaugha:

3 I T P W ZPT 3 Realizacje funkcji boolowskich Obie te realizacje są wynikiem dwóch różnych form kanonicznych… Możliwe są również inne realizacje np. w postaci iloczynu sum (Product-of-sums - POS) Na przykład…

4 I T P W ZPT 4 Postaci (formy) kanoniczne Kanoniczna postać sumacyjna (suma iloczynów) Kanoniczna postać iloczynowa (iloczyn sum)

5 I T P W ZPT 5 Kanoniczna postać sumacyjna x1x1 x2x2 x3x3 f 00000 10011 20100 30111 41000 51011 61101 71111 Minterm

6 I T P W ZPT 6 Kanoniczna postać iloczynowa x1x1 x2x2 x3x3 f 00000 10011 20100 30111 41000 51011 61101 71111 Maxterm

7 I T P W ZPT 7 Różnice wynikają ze sposobu interpretacji zmiennej w… Kanonicznej Postaci Sumy: Kanonicznej Postaci Iloczynu: Minimalizacja wg iloczynu sum Czy możliwa jest minimalizacja funkcji dla postaci iloczynu sum. Oczywiście TAK… …ale proces minimalizacji funkcji dla kanonicznej postaci iloczynowej musi być inny.

8 I T P W ZPT 8 Przykład minimalizacji dla „iloczynu sum” f =  0, 5, 6, 7, 10, (2, 3, 11, 12)  x3x4x1x2x3x4x1x2 00011110 0010–– 010111 11–000 1000–1

9 I T P W ZPT 9 Realizacje bramkowe Oprócz realizacji AND-OR (wg sumy iloczynów) Realizacja OR-AND (wg iloczynu sum)

10 I T P W ZPT 10 Realizacja OR-AND x3x1x2x3x1x2 01 0000 0110 1111 1010 Product-of-sums (POS)

11 I T P W ZPT 11 Inne operatory (bramki) logiczne NAND (NOT-AND) EX-OR NAND NOR NOR (NOT-OR) EXOR (Exclusive OR)

12 I T P W ZPT 12 Realizacja NAND x3x1x2x3x1x2 01 0000 0110 1111 1010

13 I T P W ZPT 13 Realizacja NOR x3x1x2x3x1x2 01 0000 0110 1111 1010

14 I T P W ZPT 14 Realizacja zespołów funkcji Należy zaprojektować układ realizujący zespół trzech funkcji czterech argumentów: f 1 =  (3,7,11,14,15) f 2 =  (3,7,12,13,14,15) f 3 =  (3,7,11,12,13,15) Przykład sygnalizujący problem: Układ logiczny abcdabcd f1f2f3f1f2f3

15 I T P W ZPT 15 Przykład sygnalizujący problem… cd ab 00 01 11 10 cd ab 00 01 11 10 cd ab 00 01 11 10 f 1 = abc + cd 00 01 11 10 00 01 11 10 00 01 11 10 Jeśli każdą funkcję zminimalizujemy oddzielnie:

16 I T P W ZPT 16 f1 f2 f3 … to uzyskamy… Do realizacji tych trzech funkcji potrzebujemy 9 bramek. Czy można zredukować ich liczbę? Patrz następna plansza. abcabc cdcd abab cdcd abab cdcd f 1 = abc + cd

17 I T P W ZPT 17 Bramka AND dla f1 może być usunięta przez wykorzystanie bramki AND z f3. f1 f2 f3 abcabc cdcd abab cdcd abab cdcd …usuwamy niektóre bramki Teraz potrzebujemy 8 bramek.

18 I T P W ZPT 18 Bramkę AND z f2 można usunąć przez wykorzystanie faktu f1 f2 f3 abcabc cdcd abab cdcd abab cdcd …co dalej Teraz potrzebujemy zaledwie 7 bramek.

19 I T P W ZPT 19 Komentarz Przykład sugeruje, że w realizacji zespołu funkcji stosowanie minimalnej sumy implikantów prostych nie zawsze prowadzi do rozwiązania z minimalnym kosztem. Aby się o tym przekonać warto przeanalizować…

20 I T P W ZPT 20 Przykład 4.7 ze skryptu Synteza logiczna y 1 =  (2,3,5,7,8,9,10,11,13,15) y 2 =  (2,3,5,6,7,10,11,14,15) y 3 =  (6,7,8,9,13,14,15) …wymagać będzie 7 bramek AND w którym bezpośrednia minimalizacja:

21 I T P W ZPT 21 … zaledwie 5 bramek AND!!! c.d. przykładu 4.7 ze skryptu Synteza logiczna …natomiast minimalizacja ze wspólnymi implikantami mimo pozornie większego skomplikowania wymagać będzie…

22 I T P W ZPT 22 Zalety Espresso… Z powyższego przykładu wynika, że dla metod klasycznych synteza wielowyjściowych funkcji boolowskich jest procesem bardzo złożonym – trudnym do zalgorytmizowania. Metoda Espresso jest szczególnie efektywna w minimalizacji zespołów funkcji boolowskich. W przykładzie tym po żmudnych obliczeniach uzyskujemy wynik na 5 bramkach AND!

23 I T P W ZPT 23 Jak obliczy Espresso?.type fr.i 4.o 3.p 16 0000 000 0001 000 0010 110 0011 110 0100 000 0101 110 0110 011 0111 111 1000 101 1001 101 1010 110 1011 110 1100 000 1101 101 1110 011 1111 111.e. i 4.o 3.p 5 11-1 101 100- 101 01-1 110 -01- 110 -11- 011.e Można sprawdzić, że jest to taki sam wynik jak na planszy 21