Elektroda.pl
Elektroda.pl
X
IGE-XAOIGE-XAO
Proszę, dodaj wyjątek dla www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Implementacja funkcji logicznych tylko z bramek NAND lub NOR

ghost666 22 Paź 2019 08:31 1629 5
  • Konwersja obwodu logicznego, zrealizowanego przy pomocy bramek AND i OR na formę zestawioną z bramek NAND i NOR jest doskonałym ćwiczeniem, które pomoże zrozumieć podstawowe prawa logiki Boola. Poniższy artykuł podzielono na trzy sekcje. Opiera się on na zadaniu domowym pewnego studenta, który poprosił o pomoc na forum EEWeb. Sedno tego zadania jest następujące:

    * Studentowi przedstawiono równanie logiczne.
    * Polecono mu stworzyć odpowiednią tabelę prawdy.
    * Kazano mu zminimalizować mapę Karnaugh.
    * Wreszcie musi utworzyć implementację, używając tylko bramek NAND lub tylko bramek NOR.

    Zacznijmy od zastanowienia się, dlaczego tego rodzaju klasa problemów powinna być w ogóle rozważana. Następnie przyjrzymy się bardziej szczegółowo konkretnemu równaniu z zadania, przechodząc do początkowego rozwiązania AND-OR. Później rozważymy ogólne koncepcje przekształcania obwodów opartych na AND-OR na ich odpowiedniki NAND-NOR. Na koniec wykorzystamy to, czego się nauczyliśmy, aby odpowiedzieć na ostatnią część zadania.

    Dlaczego warto używać tylko bramek NAND lub tylko bramek NOR?

    Dlaczego na zajęciach pojawiła się prośba o zaimplementowanie funkcji logicznej przy użyciu tylko bramek NAND lub tylko bramek NOR? Chociaż studenci mogą być tym zaskoczeni, niekoniecznie wykładowca jest zgorzkniałym, sfrustrowanym człowiekiem, którego jedyną przyjemnością w życiu jest utrudnienie im życia. Oczywiście nie można wykluczyć tego jako możliwej motywacji, ale zadanie to ma pewne praktyczne uzasadnienie.

    Po pierwsze przekształcenie obwodu opisanego przy użyciu bramek AND i OR (w formacie sumy iloczynów lub iloczynu sum) i przekształcenie go w alternatywną reprezentację przy użyciu tylko bramek NAND, tylko bramek NOR lub mieszaniny bramek NAND i NOR to świetny sposób, aby upewnić się, że rozumie się, jak działają różne bramki logiczne oraz, że potrafi się korzystać z praw DeMorgana.

    Po drugie – jeśli projektuje się płytkę drukowaną (PCB) przy użyciu pojedynczych, scalonych bramek logicznych np. układach scalonych zawierające sześć bramek NOT lub cztery bramki 2-wejściowe AND, OR, NAND lub NOR, to może zdarzyć się sytuacja, w której brakuje jednej bramki np. AND, ale jest nadmiarowa bramka NAND i NOT – w takim przypadku rozumienie bramek logicznych może wyeliminować konieczność dodawania nowego układu scalonego.

    Najprostsza bramka logiczna to NOT. Zakładając, że mówimy o technologii CMOS, to bramka NOT będzie wymagała dwóch tranzystorów. Dalej na drabinie złożoności znajdują się bramki NAND i NOR, z których każda zawiera cztery tranzystory. Potem mamy bramki AND i OR, każda zawiera po sześć tranzystorów. Wszystko to oznacza, że wykorzystanie bramek NAND lub NOR zamiast AND lub OR, pozwala zmniejszyć liczbę tranzystorów o w układzie nawet o jedną trzecią. Ma to ogromne znaczenie podczas implementacji elementów logicznych w układach scalonych.

    Bramka AND jest tak naprawdę utworzona z bramki NAND, po której następuje bramka NOT (podobnie bramka OR składa się z bramki NOR, po której następuje bramka NOT). Oprócz użycia większej liczby tranzystorów: 4 + 2 = 6, jak napisano powyżej, oznacza to, że bramka AND (i bramka OR) składa się z dwóch członów wprowadzających opóźnienie (czas propagacji jest większy). Zatem, zamiana AND na NAND (i OR na NOR) sprawi, że obwód będzie działał szybciej.

    Obecnie niewiele układów projektuje się na poziomie bramek. Zamiast tego powstają układy na wysokim poziomie abstrakcji; następnie używa się złożonego algorytmu syntezy do wygenerowania odpowiedniego ekwiwalentu na poziomie bramek logicznych. Oznacza to, że większość powyższych punktów nie jest tak istotna w praktyce zawodowej jak kiedyś, jednakże nadal dobrze posiadać te umiejętności.

    Powróćmy do naszego zadania. Wykładowca przedstawił następujące równanie:

    $$D = \bar{A}B\bar{C} + AB\bar{C} + A\bar{B}\bar{C} + \bar{A}\bar{B}C + \bar{A}BC + ABC$$

    Można je wykorzystać do wygenerowania poniższej tabeli prawdy. Opisywany wyżej student stworzył taką tabelę:

    ABCD
    0000
    0010
    0101
    0111
    1001
    1010
    1101
    1111


    Tutaj zaczynają się pewnie trudności. W jego równaniu jest sześć iloczynów, z których każdy powinien mieć odpowiadającą 1 w kolumnie wyników tabeli prawdy, ale w przedstawionej tabeli jest tylko pięć jedynek powiązanych z danymi wyjściowymi.

    Podstawowym problemem jest brak zrozumienia zasad logiki Boola. Powoduje to zdezorientowanie podczas konstrukcji tego rodzaju tabeli. Każdy z nas kiedyś zaczynał i był zagubiony w tych prawach, więc poświęćmy trochę czasu na prześledzenie krok po kroku, jak skonstruować można poprawną tabelę prawdy dla powyższego zagadnienia.

    Pierwszą rzeczą, którą należy zrobić, to policzyć poszczególne iloczyny w równaniu, aby zobaczyć, gdzie są poszczególne jedynki w tabeli wyników. Ponumerujmy poszczególne iloczyny:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Następnym krokiem jest utworzenie tabeli prawdy. Zaczynamy od wszystkich kombinacji wejściowych przedstawionych jako standardowa liczba binarna, jak pokazano w (a) poniżej, następnie dodajemy sześć 1 odpowiadających sześciu iloczynom, jak pokazano w (b) do (g), i na koniec wypełniamy wszelkie pozostałe pola wyjściowe zerami, jak pokazano w (h) poniżej.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Należy przede wszystkim zauważyć, że przełożenie równania na tabelę prawdy wcale nie jest trudne. Ważne jest, aby docenić logikę leżącą u podstaw tego procesu. Zrozumienie tego, jak podejść do powyższego równania jest proste, w gruncie rzeczy samo mówi ono: „Dane wyjściowe są prawdziwe (1 na wyjściu), jeśli pierwszy iloczyn (pierwsza funkcja AND) jest prawdziwy, LUB jeśli drugi iloczyn jest prawdziwy, LUB jeśli trzeci iloczyn jest prawdziwy etc.”. Dlatego możemy po prostu postawić jedynki w kolumnie wyjściowej odpowiadającej każdemu z naszych iloczynów - wynik będzie prawdziwy (1), jeśli którykolwiek z tych iloczynów jest prawdziwy, w przeciwnym razie wynik będzie fałszywy (0).

    Następnym krokiem jest utworzenie mapy Karnaugh. Zaczynamy od utworzenia samej siatki. Ponieważ mamy trzy dane wejściowe, możemy to zrobić na dwa sposoby, jak pokazano poniżej:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Nie ma znaczenia, z której opcji skorzystamy. Odpowiedź będzie taka sama w obu przypadkach. Skorzystamy z opcji numer jeden. Patrząc na mapę numer 1, zauważ, gdzie znajduje się „AB”. Po prawej stronie znajdują się cztery kombinacje zer i jedynek, które możemy powiązać z wejściami AB: „00”, „01”, „11” i „10”. Bardzo ważne jest, aby zauważyć, że te kombinacje są przedstawione w kodzie Graya, co oznacza, że tylko jeden bit zmienia się, gdy przechodzimy od jednej wartości do kolejnej. Jest to klucz do działania mapy Karnaugh.

    Kod binarny naturalnyKod Graya
    0000
    0101
    1011
    1110


    W naturalnym kodzie binarnym, kiedy przechodzimy od 01 do 10, zmieniają się dwa bity. Dla porównania, jeśli spojrzymy na odpowiednie przejście w kodzie Graya (od 01 do 11), zmienia się tylko jeden bit.

    Ponadto rozważmy ostatnią linię kodu binarnego. Jeśli mielibyśmy „zawinąć się” i przejść z tej linii do pierwszej linii (11 do 00), to - raz jeszcze - zmieniają się dwa bity. Jeśli jednak spojrzymy na odpowiednie linie w kodzie Graya (10 do 00), zobaczymy, że – ponownie – zmienia się tylko jeden bit.

    Wypełnijmy teraz mapę Karnaugh. Robimy to, dodając 1 do każdego pola odpowiadającego iloczynowi w naszym równaniu. Ponownie wykonamy ten krok po kroku, jak pokazano poniżej (małe cyfry od 1 do 6 w kółkach odpowiadają iloczynom w naszym pierwotnym równaniu):

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Należy również zauważyć, że nie potrzebujemy tabeli prawdy, aby wypełnić mapę Karnaugh. Wystarczy, że przejdziemy przez nasze równanie i dla każdego iloczynu dodajemy 1 do odpowiedniego pola mapy Karnaugh.

    Następnym etapem jest wykorzystanie naszej mapy Karnaugh, aby zminimalizować układ. Patrząc na ostateczną mapę Karnaugh (f) powyżej, od razu widzimy, że możemy ją zredukować do zaledwie trzech terminów. Jak zwykle, zróbmy to krok po kroku.

    Dwie jedynki podświetlone na obrazku poniżej oznaczają, że w obu tych przypadkach wynik wynosi 1. Dla każdego z tych pól A = 0 i C = 1, więc te wartości są ważne, B = 0 dla jednego z tych pól i 1 dla drugiego pola. Oznacza to, że dopóki A = 0 i C = 1, nie ma znaczenia, czy B przyjmuje wartość 0, czy 1.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Następnie spójrzmy na drugą grupę dwóch jedynek wyróżnionych na poniższym obrazku. Dla każdego z tych pól A = 1 i C = 0, więc te wartości są ważne. Ponownie B = 0 dla jednego z tych pól i 1 dla drugiego z nich. Mówi to, że dopóki A = 1 i C = 0, nie ma znaczenia, jaki stan przyjmuje linia B.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Na koniec spójrzmy na grupę czterech jedynek wyróżnionych na poniższym obrazku. Jedną ze sztuczek dotyczących map Karnaugh jest to, że możemy używać tych samych jedynek jako części wielu grup.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    W tym przypadku to wartość zmiennych A oraz C nie ma znaczenia – jedyna zmienna, która ma tą samą wartość dla tych jedynek jest B i wynosi ono zawsze jeden. Oznacza to, że wynik minimalizacji z mapy Karnaugh wygląda następująco:

    $$D = \bar{A}B + A\bar{C} + B$$

    Z tego miejsca z łatwością możemy narysować schemat układu z bramkami logicznymi, wykorzystując bramki NOT, AND i OR. Schemat korespondujący z tym równaniem pokazano poniżej:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Zanim zwrócicie uwagę - wiemy, że nie używamy sygnału !B (znak ! Oznacza negację, a ten zapis oznacza NOT B). Będziemy go jednakże używać w przyszłości, więc niech pozostanie na schemacie. Mówiąc o przyszłości, to właśnie najbliższym kolejnym krokiem jest implementacja ostatniej części zadania i wykorzystanie tylko bramek NAND lub NOR.

    Ale będziemy go używać w niedalekiej przyszłości. Ta przyszłość jest bliższa niż myślisz. To jest punkt, w którym musimy założyć czapki myślenia, ponieważ zadaniem obrzydliwego wykładowcy było przedstawienie końcowego obwodu z wykorzystaniem tylko bramek NAND lub tylko bramek NOR.

    Implementowanie bramek NOT przy użyciu NAND lub NOR

    Zacznijmy od najprostszego, co w tym przypadku oznacza trzy bramki NOT. Po pierwsze, przypomnijmy sobie tabele prawdy dla pięciu popularnych bramek. Są one pokazane poniżej:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Oznacza to, że jeżeli połączymy ze sobą oba wejścia bramki NAND, to rezultatem będzie funkcjonalny odpowiednik bramki NOT. Analogiczna sytuacja dotyczy bramek NOR z połączonymi obiema wejściami.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Transformacje DeMorgan na bramkach AND, OR, NAND i NOR

    Augustus DeMorgan (1806-1871) był współczesny Georgeowi Boolowi. DeMorgan wniósł znaczący wkład w dziedzinę logiki symbolicznej. Przede wszystkim opracował zbiór reguł, które teraz nazywamy transformacjami DeMorgan.

    Aby wykonać transformację DeMorgan na równaniu logicznym, wykonujemy następujące kroki:

    1. Wymień wszystkie operatory AND na operatory OR i odwrotnie.
    2. Odwróć wszystkie zmienne wejściowe; również wymień dowolne zera na jedynki i odwrotnie.
    3. Odwróć całą funkcję.
    4. Zredukuj wielokrotne inwersje.

    Przeprowadzenie takiej transformacji możliwe jest oczywiście na pojedynczych bramkach. Rezultat takiej operacji wygląda następująco:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Reprezentowanie naszego obwodu przy użyciu tylko bramek NAND

    W powyższej części znajdziemy podwaliny pod nasze finalne zadanie – redukcję układu do samych bramek NAND. Przypomnijmy sobie, jak wygląda obwód, w którym bawimy się, gdy jest implementowany za pomocą bramek NOT, AND i OR:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Bramki oznaczone zostały kolorami, aby było jasne, co zaraz następować będzie krok po kroku. Załóżmy, że chcemy stosować wyłącznie bramki NAND. Tak więc, korzystając ze wszystkiego, co zostało dotychczasowo wyjaśnione, zamieńmy bramki NOT, OR i AND na bramki NAND.

    Zacznijmy od trzech bramek NOT pokazanych na różowo po lewej stronie. Możemy wymienić każdą z tych bramek na 2-wejściową bramę NAND z połączonymi wejściami, więc nie ma problemów.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Następnie przyjrzyjmy się trójwejściowej bramce OR, oznaczonej na zielono. Znajduje się ona w prawej części naszego schematu. Zgodnie z transformacją DeMorgana, wiemy, że możemy zastąpić ją trójwejściową bramką NAND, dodając na wejściach bramki NOT, jak pokazano poniżej.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Ponownie, jak poprzednio, każdą z dodanych trzech bramek NOT możemy zamienić na bramkę NAND, jak pokazano poniżej.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Teraz musimy się tylko martwić o dwie bramki AND, zaznaczone na kolor niebieski w środku obwodu. Oczywiście transformacje DeMorgan nie są tutaj pomocne, ponieważ odpowiednikiem bramki AND jest bramka NOR z bramkami NOT na wejściach, a założyliśmy, że w tym ćwiczeniu nie możemy używać bramek NOR.

    Na szczęście ma to proste rozwiązanie, musimy tylko pamiętać, że bramka AND jest naprawdę utworzona z bramki NAND, po której następuje bramka NOT (podobnie brama OR składa się z bramki NOR, po której następuje bramka NOT). Oznacza to, że możemy wymienić zaznaczone bramki AND, tak jak pokazano poniżej:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Oczywiście, po raz kolejny, musimy zmienić bramki NOT na ich ekwiwalent, zbudowany z bramek NAND, jako że chcemy stosować w naszym układzie tylko ten rodzaj bramek logicznych. Układ po transformacji wygląda następująco:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Teraz dochodzimy niemalże do finiszu. Zobaczmy, jak wygląda nasz układ po złożeniu razem wszystkich transformacji, jakie dotychczas przeprowadziliśmy:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Funkcjonalnie układ ten będzie realizował powierzoną mu funkcję, jednakże jest on daleki od optymalnego. Widzimy, że w dwóch przypadkach za bramką NOT jest kolejna bramka NOT (oczywiście obie zaimplementowane z pomocą bramek NAND). Oba przypadki zaznaczono na rysunku poniżej czerwonym obrysem.

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Każda parzysta liczba negacji, połączona szeregowo, daje na swoim wyjściu dokładnie taki sam stan, jaki jest na wejściu (plus opóźnienie, ale to w tych rozważaniach nie jest akurat istotne). Możemy zatem zamienić je po prostu na zwykłe połączenie.

    Po wszystkich optymalizacjach układ prezentuje się następująco:

    Implementacja funkcji logicznych tylko z bramek NAND lub NOR


    Jak pisaliśmy na wstępie - układy transformuje się do postaci z bramkami NAND, aby przyspieszyć ich działanie. Prześledźmy to na powyższym przykładzie. Załóżmy, że każda z bramek NOT, NAND i NOR ma opóźnienie równe jeden, a bramka AND i OR równe dwa.

    W pierwszym, oryginalnym układzie, opóźnienie w najgorszym przypadku wynosi 1 + 2 + 2 = 5, a dla porównania, w przypadku pokazanym na powyższym schemacie czas propagacji równy będzie 1 + 1 + 1 = 3, czyli o 40% mniej.

    Jeśli jesteście studentami i czekają Was jeszcze zajęcia z algebry Boola, to przyswójcie sobie powyższy artykuł – z pewnością informacje w nim zawarte będą przydatne. Zagadnienia transformacji DeMorgana i minimalizacja tablic Karnaugha to podstawa tego przedmiotu.

    Źródło: https://www.eeweb.com/profile/max-maxfield/articles/implementing-logic-functions-using-only-nand-or-nor-gates

    Fajne! Ranking DIY
    Potrafisz napisać podobny artykuł? Wyślij do mnie a otrzymasz kartę SD 64GB.
    O autorze
    ghost666
    Tłumacz Redaktor
    Offline 
    Fizyk z wykształcenia. Po zrobieniu doktoratu i dwóch latach pracy na uczelni, przeszedł do sektora prywatnego, gdzie zajmuje się projektowaniem urządzeń elektronicznych i programowaniem. Od 2003 roku na forum Elektroda.pl, od 2008 roku członek zespołu redakcyjnego.
    ghost666 napisał 9480 postów o ocenie 7498, pomógł 157 razy. Mieszka w mieście Warszawa. Jest z nami od 2003 roku.
  • IGE-XAOIGE-XAO
  • #2
    rafi8112
    Poziom 13  
    Witam, widzę w tym artykule dwa błędy:
    Pierwsza tabela w drugiej pozycji na wyjściu "D" powinno być logiczne 1
    Wynik minimalizacji z siatki Karnaugh powinien wyglądać następująco:
    D=¯AC+A¯C+B
  • IGE-XAOIGE-XAO
  • IGE-XAOIGE-XAO
  • #4
    piotr
    Poziom 23  
    ghost666 dziękuję Tobie za przypomnienie mojej katorgi 😀😀😀😀którą miałem początek w szkole średniej a później kiedy studiowałem. Temat aż chciało się czytać Brawo.
  • #5
    drobok
    Poziom 31  
    Warto dodać też xor'a (i ew ior'a). Generalnie cyfrówka jest dość przyjemna (może pomijając aksjomaty).
  • #6
    ghost666
    Tłumacz Redaktor
    piotr napisał:
    ghost666 dziękuję Tobie za przypomnienie mojej katorgi 😀😀😀😀którą miałem początek w szkole średniej a później kiedy studiowałem. Temat aż chciało się czytać Brawo.


    Mojej też - uczyłem tego kiedyś studentów i o ile samodzielne zrozumienie tego to jest katorga, to sprawienie, żeby grupka innych ludzi to zrozumiala, jak im tłumaczysz, to jest katorga² :D