1 Elementy cyfrowe i układy logicznewykład № 4 Dr Galina Cariowa
2 Legenda Optymalizacja wielopoziomowa Inne typy bramek logicznychSystem funkcjonalnie pełny
3 Optymalizacja układów wielopoziomowychUkłady wielopoziomowe – układy zawierające więcej niż dwa poziomy logiczne. Istnieją dodatkowe możliwości uzyskania oszczędności kosztów związane z zastosowaniem układów wielopoziomowych.
4 Optymalizacja układów wielopoziomowych-koszt wejść bramkowych
5 Optymalizacja układów wielopoziomowychOptymalizacja wielopoziomowa bazuje na zastosowaniu ciągu przekształceń, które są wykonywane w powiązaniu z obliczeniami kosztów w celu znalezienia dobrego, choć nieoptymalnego, rozwiązania. N
6 Optymalizacja układów wielopoziomowychFaktoryzacja (ang.factorihg) – to znalezienie postaci iloczynowej na podstawie zarówno wyrażenia funkcji w postaci sumy iloczynów, jak i wyrażenia w postaci iloczynu sum. Dekompozycja (ang.decomposition) - to wyrażenie funkcji za pomocą zbioru funkcji. Ekstrakcja (ang.extraction) – to wyrażenie wielu funkcji za pomocą zbioru nowych funkcji. Zastępowanie (ang. substitution) funkcji G w funkcji F to wyrażanie funkcji F jako funkcji G oraz pierwotnych zmiennych funkcji F (niektórych lub wszystkich). Eliminacja (ang. elimination) – to operacja odwrotna do zastępowania: funkcja G w wyrażeniu funkcji F jest zastępowana wyrażeniem opisującym G.
7 Przykład (zilustrowanie przekształceńPrzykład (zilustrowanie przekształceń do optymalizacji wielopoziomowej) Schemat logiczny odpowiadający pierwotnym postaciom sum iloczynów funkcji G i H
8 Faktoryzacja
9 I Faktoryzacja - przykładFaktoryzacja– to znalezienie postaci iloczynowej funkcji logicznej Postać iloczynowa
10 II Dekompozycja- przykładDekompozycja - to wyrażenie funkcji za pomocą zbioru funkcji. Dekompozycja jest wykonana po rozkładzie na czynniki (po faktoryzacji): Zdefiniujemy funkcje pomocnicze: Zanegujemy Wtedy: : Dekompozycja sfaktoryzowanej funkcji : - dekompozycja funkcji G
11 III Ekstrakcja– przykładEkstrakcja– to wyrażenie wielu funkcji za pomocą zbioru nowych funkcji. Dekompozycja funkcji H: Faktoryzacja funkcji H Funkcja H po dekompozycji
12 Schemat logiczny po wykonaniu ekstrakcji
13 Zastosowanie przekształceń do optymalizacji wielopoziomowejTen przykład ilustruje znaczenie przekształceń w redukcji liczby wejść. Otrzymanie prawdziwie optymalnego rozwiązania pod względem liczby wejść bramkowych jest zwykle niewykonalnie (znajdowane tylko dobre rozwiązania). Kluczem do wykonania udanych transformacji jest określenie czynników w dekompozycji lub ekstrakcji.
14 IV Eliminacja - zmnieszenie opóznienia układuOperacja eliminacji, w której zastępuje się pośrednie zmienne Xi wyrażeniami stojącymi po ich prawej stronie lub usuwa się inne czynniki, stanowi przekształcenie zmniejszające liczbę bramek połączonych kaskadowo. Skracanie ścieżek powinno być dokonane przy minimalnym wzroście liczby wejść bramkowych.
15 IV Eliminacja Długość najdłuższej ścieżki układu jest ograniczana ze względu na czas, który upływa od zmiany sygnału na początku ścieżki do chwili zmiany stanu na jej końcu. Dopuszczalne opóźnienie ścieżki może być co najwyżej równe opóźnieniu ścieżki złożonej z trzech wielowejściowych bramek lub równoważnym im opóźnieniom bramek wielowejściowych i inwertorów. W naszym układzie po wykonaniu ekstrakcji wszystkie ścieżki od wejść C, D, E, F, A do wyjścia H przechodzą przez cztery 2-wejściowe bramki. Te ścieżki wprowadzają najdłuższe opóźnienie w układzie.
16 IV Eliminacja Ze względu na wymagania związane z maksymalnym opóźnieniem ścieżki w układzie, te ścieżki muszą być skrócone. Dopuszczalne opóźnienie ścieżki może być co najwyżej równe opóźnieniu ścieżki złożonej z trzech wielowejściowych bramek lub równoważnym im opóźnieniom bramek wielowejściowych i inwertorów W przykładzie istnieje tylko 3 połączenia eliminacji : Eliminacja czynnika B; Eliminacja X1, X2, X3; Eliminacja zarówno czynnika B jak i X1, X2, X3. Wzrost wejść bramkowych wynosi odpowiednio 0, 12 i 12.
17 Eliminacja– przykład Usunięcie czynnika B nie powoduje zwiększenie liczby wejść bramkowych (Kb=25).
18 Inne typy bramek. Bufor.
19 Inne typy bramek. Bufor 3–stanowy.E- dodatkowe wejście zezwolenia Wyjście Hi-Z – trzecia wartość, określana jako stan wysokiej impedancji. Wyjście w stanie wysokiej impedancji zachowuje się jako przerwa w obwodzie – pozostaje ono nie podłączone.
20 Bufor 3-stanowy Bramki z wyjściami Hi-Z można łączyć ze sobą wyjściami, pod warunkiem że żadne dwie bramki w tym samym czasie nie przyjmą na wyjściach przeciwnych wartości 0 i 1. 1 Hi-Z F X E Wyjście Wejście Jeśli E=0, to na wyjściu jest stan wysokiej impedancji Hi-Z, niezależnie od wartości X. Jeśli wejście zezwolenia E=1, to bramka zachowuje się jako zwykły bufor. Wyjścia bufora trójstanowego połączone razem tworzą multipleksowaną (przełączaną) linię wyjściową.
21 AND–OR–INVERT (AOI) (dopełnienie sumy iloczynów)Przykład 1. Przykład 2.
22 OR–AND–INVERT (OAI) (dopełnienie iloczynu sum)
23 AND – OR (AO) (wersja bramki AOI bez końcowej negacji)
24 OR – AND (OA) (wersja bramki OAI bez końcowej negacji)
25 Stosowanie bramek złożonych1) Zmniejszyć stopień złożoności układu potrzebnego do zrealizowania określonych funkcji boolowskich, a tym samym zmniejszyć koszty wytwarzania układu scalonego; 2) Zmniejszyć czas propagacji sygnałów przez układ.
26 Operator i bramki typu EXOROperacja EXOR jest przemienna i łączna: Dwa wejścia bramki EXOR mogą być ze sobą zamienione Wartość funkcji EXOR trzech zmiennych można wyliczać w dowolnej kolejności
27 Operator i bramki typu EXORDwuwejściową funkcję EXOR można zrealizować przy użyciu typowych bramek NOT, AND i OR. Funkcja EXOR więcej niż dwóch zmiennych jest definiowana jako funkcja kontroli nieparzystości. Funkcja EXNOR wielu zmiennych jest definiowana jako funkcja kontroli parzystości.
28 Operator i bramki typu EXORFunkcja kontroli nieparzystości może być zrealizowana za pomocą dwóch dwuwejściowych bramek typu EXOR.
29 Funkcja kontroli nieparzystościOperacje EXOR dla trzech zmiennych można przekształcić do postaci zwykłej funkcji boolowskiej: Funkcja EXOR trzech zmiennych jest równa 1 tylko wtedy, gdy jedna z trzech zmiennych ma wartość 1, lub wartości wszystkich zmiennych są równe 1, czyli Nieparzysta liczba zmiennych musi mieć wartość 1.
30 System funkcjonalnie pełnyZbiór funkcji boolowskich nazywa się systemem funkcjonalnie pełnym (bazą), jeśli dowolna funkcja boolowska może być przedstawiona za pomocą stałych 0 i 1 oraz funkcji należących do tego zbioru i argumentów funkcji. Przykład. Funkcje sumy, iloczynu i negacji tworzą tzw. podstawowy system funkcjonalnie pełny.
31 Realizacja bramki OR za pomocą bramek NOT i AND
32 Realizacja bramki AND za pomocą bramek NOT i OR
33 System funkcjonalnie pełny
34 System funkcjonalnie pełnyPrzy realizacji układów logicznych może czasem zajść potrzeba przedstawienia funkcji logicznej za pomocą jedynie funktorów NAND lub jedynie funktorów NOR. Ta potrzeba wynika z: minimalizacji układów scalonych (za pomocą których buduje się bramki logiczne); wykorzystania jednakowych układów w celu powtarzalności procesu produkcji.
35 System funkcjonalnie pełnyKorzystając z zapisu za pomocą samych NAND i NOR wystarczy użyć jedynie jeden czy dwa układy i to na dodatek tego samego rodzaju. Poza tym, funkcja NAND jest podstawową funkcją w technice TTL i jest reprezentowana przez pojedynczy tranzystor, a więc i ich produkcja jest łatwiejsza i tańsza.
36 System funkcjonalnie pełnyAby udowodnić, iż za pomocą jedynie NAND lub jedynie NOR możemy przedstawić dowolną funkcję wystarczy pokazać, że za ich pomocą można przedstawić trzy funkcje podstawowe: mnożenie, sumę i negację.
37 Przedstawienie funkcji NOT za pomocą NAND-więc, na wejścia NAND należy podać ten sam sygnał a.
38 Przedstawienie funkcji NOT za pomocą NOR-więc, na wejścia NOR należy podać ten sam sygnał a
39 Przedstawienie funkcji AND za pomocą NANDOtrzyma się zanegowany iloczyn zmiennych a i b plus dodatkowa negacja, którą można zrealizować jako drugi NAND ze zwartymi wejściami:
40 Przedstawienie funkcji AND za pomocą NOROtrzyma się zanegowaną sumę zanegowanych argumentów. Zanegowane argumenty- to dwa NOR-y ze zwartymi wejściami, na pierwszy podajemy a, na drugi b. Zanegowana ich suma- to trzeci NOR.
41 Przedstawienie funkcji OR za pomocą NANDOtrzyma się zanegowany iloczyn zanegowanych zmiennych. Zanegowane argumenty- to dwa NAND-y, negujące a i b. Zanegowany ich iloczyn- to trzeci NAND.
42 Przedstawienie funkcji OR za pomocą NOROtrzyma się dwa NOR -y, jeden jako zanegowaną sumę argumentów, drugi - jako negacja tego wyrażenia.
43 Przedstawienie za pomocą jedynie NAND bramki NOR
44 Przedstawienie za pomocą jedynie NOR bramki NAND
45 Zapis funkcji przy pomocy bramek NANDPrzedstawić za pomocą NAND funkcję Otrzymujemy trzy NAND-y – zanegowany iloczyn ‘a’ i ‘b’, zanegowane ‘c’, oraz zanegowany iloczyn ‘’ i ‘c’ . Korzystając z prawa de Morgana i podwójnej negacji: Zamiast dwóch układów scalonych, jeden do OR (+) a drugi do AND (*) można użyć jednego z 3 NAND-ami. Oszczędza się więc miejsce, czas montażu i wykonania.
46 Zapis funkcji przy pomocy bramek NORPrzedstawić za pomocą NOR funkcję Korzystając z prawa de Morgana i podwójnej negacji:
47 Zapis funkcji przy pomocy bramek NANDEXOR: Aby zrealizować to z pomocą funkcji podstawowych należałoby użyć 2-ch AND, OR i dwóch NOT- trzech różnych funkcji- trzech różnych układów scalonych. Potrzeba 5 NAND -ów, a więc tylko dwa takie same układy scalone, które mają w sobie cztery NAND -y każdy.
48 Przykłady. Zapis funkcji EXOR przy pomocy bramek NAND
49 Przykłady. Zapis funkcji EXOR przy pomocy bramek NOROtrzymujemy 6-NOR-ów. Zamiast 3 różnych układów scalonych można użyć jedynie dwóch i to takich samych, zawierających po cztery NOR-y.
50 Przykłady. Zapis funkcji EXOR przy pomocy bramek NOR
51 Zapis funkcji przy pomocy bramek NANDNależy zamienić znaki sum na mnożenie – prawo De Morgana Otrzymujemy 5 NAND-ów: dwa 2-wejściowe do negacji ‘a’ i ‘b’, jeden dwuwejściowy do zanegowanego iloczynu ‘a’ i ‘b’ - , i trzy 3-wejściowe do realizacji: oraz negacji iloczynu wszystkich składników.
52 Zapis funkcji przy pomocy bramek NAND
53 Zapis funkcji przy pomocy bramek NAND
54 Zapis funkcji przy pomocy bramek NAND c.d.
55 Zapis funkcji przy pomocy bramek NOR
56 Zapis funkcji przy pomocy bramek NOR c.d.
57 Dziękuję za uwagę