Elementy

Dawniej, gdy mikrokontrolery nie były powszechnie dostępne, większość układów cyfrowych (mierniki, zegary, generatory) tworzono właśnie głównie z bramek cyfrowych. W naszych czasach dużą część takich zadań może przejąć mikrokontroler, który również jest siecią logiczną (bardzo skomplikowaną wewnętrznie). Jednak często sam mikrokontroler nie będzie wystarczający. Będzie wymagał dodatkowej sieci logicznej. Właśnie dlatego powinieneś nauczyć się projektować takie sieci.

Sieć logiczna posiada zbiór sygnałów sterujących (wejście), które ustalają jej stan wewnętrzny, oraz zbiór sygnałów wyjściowych (wyjście), które są tworzone na podstawie sygnałów sterujących wg funkcji logicznych zawartych w sieci. Schematycznie wygląda to tak:

Prawo wyłączonego środka

Prawo podwójnej negacji

Prawa przemienności

Prawa łączności

Prawa rozdzielności

W rachunku tym kreska u góry oznacza NOT, + oznacza OR, a · oznacza AND. Niech cię nie przeraża ilość tych praw. Zawsze możesz je sobie wydrukować na małej kartce i mieć pod ręką. Chociaż lepiej się ich nauczyć na pamięć, co może ci się przydać na maturze z matematyki.

Umiejętne stosowanie tych praw pozwala redukować i przekształcać funkcje logiczne.

Załóżmy, że jest nam potrzebna sieć logiczna, która będzie posiadała trzy wejścia a, b, c oraz dwa wyjścia x i y:

Sygnały wyjściowe x i y określimy za pomocą tabelki:

Jak tą tabelkę należy interpretować? W trzech pierwszych kolumnach mamy sygnały wejściowe a, b i c. W poszczególnych wierszach tabelki znajdują się wszystkie możliwe kombinacje tych sygnałów i jest ich 8. Dla każdej kombinacji sygnałów wejściowych w dwóch kolejnych kolumnach mamy stan wyjść x i y. Na przykład dla a = 0, b = 0 i c = 0, mamy x = 1 i y = 0, itd. Skąd to się bierze? Po prostu tak ustalamy, bo taką mamy potrzebę w tworzonym układzie cyfrowym.

Ja się teraz za to zabrać algebraicznie? Obserwuj:

Wyjście x

Rozważamy wiersze tabelki, dla których wyjście x przyjmuje stan logiczny 1.

W wierszu nr 1 mamy: dla a = 0, b = 0, c = 0 x przyjmuje wartość logiczną 1.  Będzie to prawdą dla funkcji logicznej:

Funkcję tę tworzymy jako iloczyn logiczny sygnałów a, b i c. Jeśli sygnał ma wartość 0, to w iloczynie przyjmujemy jego zaprzeczenie (inaczej iloczyn nie dałby wartości 1!).

W wierszu nr 2:

W wierszu nr 3:

W wierszu nr 4:

W wierszu nr 6 (nr 5 pomijamy, bo x = 0):

W wierszu nr 8 (w nr 7 x = 0):

Sumujemy logicznie podwyrażenia:

Otrzymaliśmy funkcję logiczną dla wyjścia x. W tej postaci nie jest ona użyteczna, ponieważ jest zbyt skomplikowana. Spróbujmy ją uprościć, wykorzystując prawa Algebry Boole'a. Wyciągamy wspólne czynniki przed nawias:

Powtarzamy tę samą operację dla wyrażeń w nawiasach:

Stosujemy prawo wyłączonego środka:

Upraszczamy:

Ponownie upraszczamy:

I jeszcze raz upraszczamy:

Stosujemy zasadę rozdzielności:

Upraszczamy:

Upraszczamy:

Jak widzisz, stan wyjścia x zależy tylko od sygnałów a i c. Sygnał b jest tutaj nieistotny. Otrzymaliśmy funkcję logiczną w prostej postaci, którą łatwo da się zrealizować za pomocą bramek.

Wyjście y

Postępujemy podobnie, jak z wyjściem x.

Wiersz trzeci:

Wiersz czwarty:

Wiersz piaty:

Wiersz szósty:

Wiersz siódmy:

Sumujemy logicznie podwyrażenia:

Wyciągamy przed nawiasy powtarzające się czynniki:

Powtarzamy wyciąganie przed nawias:

Upraszczamy:

Upraszczamy:

Zasada rozdzielności i uproszczenie jak dla x:

Mamy obie funkcje wyjść:

Na ich podstawie budujemy sieć logiczną:

Jako ćwiczenie prześledź ją dokładnie i sprawdź, czy odpowiada wyprowadzonym funkcjom.

Kod Graya

Jest to kod, w którym kolejne wyrazy kodowe różnią się wartością tylko jednego bitu. Takich kodów może być wiele. Umówmy się jednak, że bity będziemy zmieniać począwszy od ostatniej pozycji w lewo. Oto kilka kodów Graya o różnej liczbie bitów:

Jak się tworzy wyrazy tego kodu? Przyjrzyj się tabelce. Startową sekwencją jest 1-bitowy kod Graya:

Dwa początkowe wyrazy kodu dwubitowego otrzymamy dołączając do kodu jednobitowego bit o wartości 0:

Dwa następne otrzymujemy dołączając bit o wartości 1 do kodu jednobitowego o odwrotnej kolejności (czytany od końca do początku, lustrzane odbicie):

Gdy mamy kod 2-bitowy, to w analogiczny sposób tworzymy wyrazy kodu 3-bitowego:

Wynika z tego prosty algorytm rekurencyjnego tworzenia kodów Graya:

Zwróć uwagę na jeszcze jedną ciekawą własność kodów Graya: ostatni wyraz i pierwszy również różnią się tylko jednym bitem: 0 i 1, 00 i 10, 000 i 100, 0000 i 1000...

Mapa logiczna Karnaugha

Każda mapa posiada współrzędne, które określają na niej położenie. Mapa logiczna przedstawia wartości funkcji logicznej. Tworzymy ją następująco:

Załóżmy, że mamy funkcję logiczną zadaną tabelką wartości:

Argumentami funkcji są x i y. Funkcja ma 4 wartości, po jednej dla każdej kombinacji argumentów. Argumenty rozdzielamy na dwie grupy: tutaj na x i y. Mapa ma postać tabelki. Współrzędne to wartości argumentów w każdej grupie zapisane w kodzie Graya:

Poziomo mamy wartości x, pionowo mamy wartości y. Każda kratka mapy odpowiada wartości funkcji f(x,y) dla wybranych wartości argumentów:

Przepisujemy z tabelki wartości funkcji:

Otrzymaliśmy mapę Karnaugha dla danej funkcji logicznej.

Załóżmy teraz, że nasza funkcja posiada trzy argumenty a, b i c i jest zadana tabelką:

Postępujemy podobnie, argumenty rozdzielamy na dwie grupy: np. a i bc.  Poziomo będą współrzędne bc, pionowo będzie współrzędna a:

Wpisujemy do mapy Karnaugha wartości funkcji z tabelki:

Gotowe.

Niech z kolei funkcja posiada 4 argumenty a, b, c, d i jest zadana tabelką:

Argumenty dzielimy na dwie grupy: ab i cd:

W pola mapy wpisujemy wartości funkcji zgodnie z tabelką:

Obszary na mapie Karnaugha

Kolejnym elementem do opanowania jest zaznaczanie na mapie obszarów, w których funkcja posiada wartość 1. Zaznaczane obszary obejmują przyległe wiersze i kolumny. Liczba objętych wierszy lub kolumn musi być potęgą 2, np. 1, 2, 4, 8...

Na mapie Karnaugha pierwszy wiersz jest przyległy do ostatniego. Tak samo pierwsza kolumna jest przyległa do ostatniej. Zatem obszary mogą zawierać skrajne wiersze i kolumny (współrzędne w kodzie Graya również przechodzą gładko w siebie na skrajnych pozycjach). Rozważmy kilka przykładów:

Mamy taką mapę Karnaugha:

Tutaj sprawa jest prosta. Zaznaczamy obszar zawierający przyległe jedynki. Przy zaznaczaniu staramy się zawsze objąć jak największą liczbę wierszy i kolumn, jednak liczba ta musi być potęgą 2:

A teraz nieco inna mapa:

Taka mapa wymaga zaznaczenia dwóch obszarów, aby pokryły wszystkie jedynki:

Nie przeszkadza, że obszary się częściowo pokrywają. Ważne, aby były możliwie największe i zawierały liczby wierszy i kolumn będące potęgami 2, a tak jest w tym przypadku.

Kolejna mapa:

Tutaj zwróć uwagę, że jedynki są w skrajnych kolumnach. Skrajne wiersze i kolumny mogą znaleźć się w tym samym obszarze, zatem:

Kolejna mapa:

Stosujemy tę samą zasadę. To jest jeden obszar, w którym znajdą się pola leżące w skrajnych wierszach i kolumnach:

Na koniec taka oto mapa Karnaugha:

Jeśli funkcja może przyjmować dowolną wartość X (0 lub 1), to pola takie w razie potrzeb możemy zawsze dołączyć do obszaru, jeśli uzyskamy w ten sposób obszar większy. I tak postąpimy tutaj:

Mamy już wszystkie potrzebne składniki do opisu metody Karnaugha. Metoda ta ma na celu minimalizację funkcji logicznych, czyli otrzymanie funkcji logicznej w prostej postaci. Dla przykładu wykonamy tą metodą minimalizację funkcji dla x i y z poprzedniego przykładu. Najpierw tabelka wartości:

Metodę Karnaugha zastosujemy tutaj dwukrotnie: raz dla x i raz dla y.

Wyznaczenie funkcji dla sygnału x

Tabelka dla x jest następująca:

Mamy trzy argumenty a, b i c. Dzielimy je na dwie grupy a i bc. Tworzymy mapę Karnaugha:

Zaznaczamy obszary zawierające stany 1:

Ze współrzędnych obszaru pozostawiamy tylko te, które się w nim nie zmieniają.

Dla obszaru czerwonego to a.

Dla obszaru zielonego to c.

Dla każdego obszaru tworzymy jego funkcję jako iloczyn logiczny pozostawionych współrzędnych. Jeśli współrzędna ma w obszarze wartość 0, to w iloczynie umieszczamy jej negację:

Funkcja całkowita jest sumą logiczną wszystkich funkcji obszarów:

Wyznaczenie funkcji dla sygnału y

Tabelka:

Mapa Karnaugha:

Obszary:

Funkcje obszarów:

I ostatecznie:

Otrzymaliśmy pełną zgodność z wynikiem wyprowadzonym algebraicznie, a prawie wcale nie wykonywaliśmy rachunków w Algebrze Boole'a. Na tym właśnie polega metoda Karnaugha – upraszcza obliczenia. Dlatego warto się jej nauczyć.

Czas propagacji zależy od rodzaju bramki oraz jej budowy. Dla typowych bramek TTL wynosi on około 10 ns. Czas propagacji tworzy tzw. zjawisko hazardu, czyli powstawanie stanu przejściowego w sieci, w czasie którego sieć nie realizuje zaprojektowanej funkcji. Aby to zrozumieć, prześledźmy prosty przykład. Mamy następującą sieć logiczną:

Sieć realizuje funkcję:

Zatem na wyjściu bramki AND powinien zawsze panować stan 0 bez względu na stan wejścia A. Tyle teoria. Teraz praktyka. Załóżmy, że na wejściu A panuje stan 0. Wtedy na wyjściu bramki NOT jest stan 1, a na wejściach bramki AND mamy stany odpowiednio 1 z wyjścia bramki not i 0 z wejścia A. Na wyjściu Y jest spodziewany stan 0. To nasz punkt wyjścia:

Teraz stan wejścia zmienia się na 1. Bramka NOT zareaguje dopiero po czasie propagacji i na jej wyjściu wciąż jest poprzedni stan 1. W rezultacie na wejściach bramki AND mamy dwa stany 1. Ta bramka również nie reaguje natychmiast, lecz po swoim czasie propagacji, zatem na jej wyjściu jest wciąż stan 0:

Po czasie propagacji stan wyjścia bramki NOT zmienia się na 0, lecz poprzedni stan 1 i 1 propaguje się przez bramkę AND i na jej wyjściu pojawia się niedozwolony stan 1:

Gdy upłynie czas propagacji bramki AND jej stan wyjścia znów wróci do poziomu 0:

W efekcie przy każdej zmianie stanu wejścia A z 0 na 1 na wyjściu Y pojawia się krótki impuls napięciowy związany z propagacją sygnału przez bramki. To jest właśnie hazard.

Hazardy mogą powodować błędne działanie sieci, dlatego należy je brać pod uwagę przy projektowaniu. Jest to zagadnienie trudne, ale trzeba o nim pamiętać.

Jednym ze sposobów eliminacji hazardów w układach cyfrowych jest wprowadzenie taktowania. Polega to na tym, iż sieć otrzymuje ciąg impulsów (zwanych taktami zegarowymi), wg których następuje synchronizacja. Czas pomiędzy impulsami przeznaczony jest na wygaśnięcie hazardów w sieci.

Czasem zjawisko hazardu może być użyteczne. Generator jest układem, który tworzy ciąg impulsów (naprzemiennych stanów 0 i 1) o określonej częstotliwości. Najprostszy generator da się zbudować z nieparzystej liczby bramek NOT połączonych w sieć:

Wyjście sieci jest połączone z jej wejściem. Uzyskuje się w ten sposób tzw. sprzężenie zwrotne (ang. feedback). Ponieważ liczba bramek NOT jest nieparzysta, to na wejście po czasie propagacji przez poszczególne bramki podawany jest zawsze sygnał przeciwny od poprzedniego. W rezultacie układ generuje ciąg impulsów o częstotliwości zależnej od czasu propagacji bramek. Częstotliwość ta nie jest specjalnie stabilna, zależy od temperatury, napięcia zasilania, budowy i własności bramek. W przybliżeniu wyraża się wzorem:

f – częstotliwość impulsów n – liczba bramek NOT (nieparzysta, zwykle co najmniej 3) tp – czas propagacji bramki

Dla bramek TTL t_p = 10ns = 0,00000001 s, f = 16,6MHz.

NAND

Sieć wyjściowa jest następująca:

Przekształcamy funkcję dla x:

Zaprzeczamy podwójnie:

Zaprzeczenie alternatywy jest koniunkcją zaprzeczeń:

Podwójne zaprzeczenie się znosi:

Mamy już funkcję NAND dla x.

Przekształcamy funkcję dla y:

Zaprzeczamy podwójnie:

Zaprzeczenie alternatywy jest koniunkcją zaprzeczeń:

Zaprzeczamy podwójnie wyrażenie w nawiasach:

Zaprzeczenie alternatywy jest koniunkcją zaprzeczeń:

Podwójne zaprzeczenie się znosi:

Mamy funkcję NAND dla y. Tworzymy sieć.

Ta sieć zachowuje się identycznie jak poprzednia, lecz jest zbudowana z jednorodnych bramek NAND.

NOR

Dla y:

Bramki NAND są bardziej popularne i, jak widzisz, tworzą mniejsze sieci.

Jeśli nie umiesz programować w języku C, to przejdź przez nasz szybki kurs, który znajdziesz tutaj.

Symulacja będzie polegała na znalezieniu odpowiedzi sieci na wszystkie kombinacje sygnałów sterujących, a następnie na sprawdzeniu tych odpowiedzi z projektem. Oprzemy się na przerobionej tutaj przykładowej sieci, którą mamy zadaną tabelką:

Sygnałami wejściowymi są a, b i c. Odpowiedziami sieci na te sygnały są x i y.

Uruchom CodeBlocks i utwórz nowy projekt C dla konsoli.

Sygnały wejściowe i wyjściowe sieci będziemy reprezentować w programie za pomocą zmiennych typu int o nazwach a, b, c, x i y. Najpierw utworzymy środowisko, w którym sygnały wejściowe przyjmują wszystkie kombinacje wartości, jak w powyższej tabelce. Następnie będziemy wyliczać sygnały wyjściowe x i y wg zaprojektowanej sieci. Na koniec program wyświetli sygnały wejściowe i wyjściowe, które porównamy z tabelką.

Projekt pierwszy

Program będzie symulował poszczególne bramki, które ponumerujemy sobie następująco:

Takie podejście pozwoli sprawdzić, czy nie popełniliśmy błędu w przetworzeniu funkcji na bramki w sieci. W poniższej tabelce wypisujemy wszystkie bramki sieci, ich typy oraz to, co otrzymują one na wejściach.

Program jest następujący:

/*
** SYMULACJA SIECI LOGICZNEJ
** (C)2018 mgr Jerzy Wałaszek
*/

#include <stdio.h>
#include <stdlib.h>

int main()
{
    // Sygnały wejściowe sieci
    int a,b,c;
    // Sygnały wyjściowe sieci
    int x,y;
    // Bramki
    int b1,b2,b3,b4,b5,b6,b7,b8;

    printf("Symulacja sieci nr 1\n");
    printf("--------------------\n");
    printf("\n\n");
    printf("a b c   x y\n-----------\n");

    // Tworzymy środowisko pracy sieci
    for(a = 0; a < 2; a++)         // sygnał a 0,1
        for(b = 0; b < 2; b++)     // sygnał b 0,1
            for(c = 0; c < 2; c++) // sygnał c 0,1
            {
                // Wyświetlamy sygnały wejściowe a, b i c
                printf("%d %d %d - ",a,b,c);

                // Wyznaczamy wartości na wyjściach bramek sieci

                b1 = !a;
                b2 = !b;
                b3 = !c;

                x = b4 = b1 || c;

                b5 = b1 && b;
                b6 = b2 || b3;
                b7 = a && b6;
                y = b8 = b5 || b7;

                // Wyświetlamy sygnały wyjściowe

                printf("%d %d\n",x,y);
            }
    printf("\n--- KONIEC SYMULACJI ---\n\n");
    return 0;
}

Projekt drugi

/*
** SYMULACJA SIECI LOGICZNEJ
** (C)2018 mgr Jerzy Wałaszek
*/

#include <stdio.h>
#include <stdlib.h>

int main()
{
    // Sygnały wejściowe sieci
    int a,b,c;
    // Sygnały wyjściowe sieci
    int x,y;
    // Bramki
    int b1,b2,b3,b4,b5,b6,b7;

    printf("Symulacja sieci nr 2\n");
    printf("--------------------\n");
    printf("\n\n");
    printf("a b c   x y\n-----------\n");

    // Tworzymy środowisko pracy sieci
    for(a = 0; a < 2; a++)         // sygnał a 0,1
        for(b = 0; b < 2; b++)     // sygnał b 0,1
            for(c = 0; c < 2; c++) // sygnał c 0,1
            {
                // Wyświetlamy sygnały wejściowe a, b i c
                printf("%d %d %d - ",a,b,c);

                // Wyznaczamy wartości na wyjściach bramek sieci

                b1 = !c;
                b2 = !a;

                b3 = !(b && c);
                x = b4 = !(a && b1);
                b5 = !(b && b2);
                b6 = !(a && b3);
                y = b7 = !(b5 && b6);

                // Wyświetlamy sygnały wyjściowe

                printf("%d %d\n",x,y);
            }
    printf("\n--- KONIEC SYMULACJI ---\n\n");
    return 0;
}

Projekt trzeci

/*
** SYMULACJA SIECI LOGICZNEJ
** (C)2018 mgr Jerzy Wałaszek
*/

#include <stdio.h>
#include <stdlib.h>

int main()
{
    // Sygnały wejściowe sieci
    int a,b,c;
    // Sygnały wyjściowe sieci
    int x,y;
    // Bramki
    int b1,b2,b3,b4,b5,b6,b7,b8,b9,b10;

    printf("Symulacja sieci nr 3\n");
    printf("--------------------\n");
    printf("\n\n");
    printf("a b c   x y\n-----------\n");

    // Tworzymy środowisko pracy sieci
    for(a = 0; a < 2; a++)         // sygnał a 0,1
        for(b = 0; b < 2; b++)     // sygnał b 0,1
            for(c = 0; c < 2; c++) // sygnał c 0,1
            {
                // Wyświetlamy sygnały wejściowe a, b i c
                printf("%d %d %d - ",a,b,c);

                // Wyznaczamy wartości na wyjściach bramek sieci

                b1 = !a;
                b2 = !b;
                b3 = !c;

                b4 = !(c||b1);
                b5 = !(a||b2);
                b6 = !(b2||b3);
                x = b7 = !b4;
                b8 = !(b1||b6);
                b9 = !(b5||b8);
                y = b10 = !b9;

                // Wyświetlamy sygnały wyjściowe

                printf("%d %d\n",x,y);
            }
    printf("\n--- KONIEC SYMULACJI ---\n\n");
    return 0;
}