Koło informatyczne - mapy Karnaugh'a

Sieci logiczne

Przy projektowaniu różnych urządzeń cyfrowych mamy do czynienia z tzw. sieciami logicznymi (ang. logic networks).

 

 

Jest zbiorem reguł przekształcających sygnały wejściowe w sygnały wyjściowe. Odpowiada to dokładnie matematycznemu pojęciu funkcji. Jeśli sygnały wejściowe potraktujemy jako zbiór wartości x, a sygnały wyjściowe jako zbiór wartości y, to sieć logiczna będzie funkcją f(), która dla danego sygnały x produkuje na wyjściu dany sygnał y:

 

y = f(x)

 

W układach cyfrowych sieci są realizowane za pomocą elementów logicznych zwanych bramkami (ang. gates). Na dzisiejszych zajęciach poznamy wygodny sposób określania funkcji realizującej daną sieć logiczną.

 

Kostka cyfrowa

Zaprojektujemy prostą symulację sieci logicznej, która przekształca 3 bitowy kod NBC w układ oczek na kostce do gry.

 

 

Na wejście kostki podajemy trzybitowy kod NBC, który będzie określał liczbę oczek do wyświetlenia na kostce. Określmy wszystkie możliwe sygnały wejściowe oraz pożądane sygnały wyjściowe dla naszej sieci logicznej. Umówmy się, że oczko na kostce zostaje zaczernione, jeśli odpowiadający mu sygnał ma wartość 1. W przeciwnym razie oczko ma kolor kostki i nie jest widoczne.

 

b2 b1 b0 Oczka Kostka A B C D E F G
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0
0 1 0 2 0 0 0 1 0 0 1
0 1 1 3 1 0 0 1 0 0 1
1 0 0 4 0 1 0 1 1 0 1
1 0 1 5 1 1 0 1 1 0 1
1 1 0 6 0 1 1 1 1 1 1
1 1 1 0 0 0 0 0 0 0 0

 

W kolejnym etapie określimy funkcje logiczne sygnałów wejściowych dla każdego wyjścia od A do G sieci logicznej. Możemy tego dokonać, ponieważ nasza tabelka definiuje stany wszystkich wejść i wyjść sieci logicznej. Wykorzystamy tutaj mapy Karnaugh'a. Mapa Karnaugh'a odwzorowuje sygnały wejściowe sieci w sygnały wyjściowe. Tworzymy ją następująco.

 

Sygnały wejściowe dzielimy na dwie grupy. Będą one tworzyły "współrzędne" mapy. W naszym przypadku mamy trzy sygnały wejściowe: b2, b1 i b0. Podzielimy je zatem na dwie grupy:  b2 b1  oraz b0.

 

Tworzymy tabelkę mapy Karnaugha. Tabelka będzie się składała z wierszy oraz z kolumn. Wierszy jest tyle wynosi 2 do potęgi liczby sygnałów w grupie pierwszej (u nas są to dwa sygnały b2 i b1, zatem tabelka będzie miała 22 = 4 wiersze). Kolumn jest tyle, ile wynosi 2 do potęgi liczby sygnałów w grupie drugiej (u nas jest to jeden sygnał b0, zatem w tabelce będzie 21 = 2 kolumny). U góry z boku rysujemy ukośną linię, która będzie rozdzielała grupy sygnałów wejściowych. Pod tą linią zapisujemy oznaczenia pierwszej grupy. Nad linią zapisujemy oznaczenia drugiej grupy. Z boku pierwszej kolumny zapisujemy kody Gray'a dla sygnałów z pierwszej grupy. Ponad pierwszym wierszem zapisujemy kody Gray'a dla sygnałów z grupy drugiej:

 

 

Zacznijmy od sygnału wyjściowego A. Na podstawie tabelki stanów wypełniamy wnętrze mapy Karnaugh'a stanami sygnału A dla wszystkich kombinacji sygnałów wejściowych. W odpowiednie oczka tabelki wpisujemy 0 lub 1. Np. dla sygnałów b2 = 0, b1 = 0, b0 = 0, wyjście A przyjmuje stan 0. Zatem w oczku tabelki o współrzędnych (0 0, 0) wpisujemy 0. Dla sygnałów b2 = 0, b1 = 0, b0 = 1, wyjście A przyjmuje stan 1. W oczku tabelki o współrzędnych (0 0, 1) wpisujemy 1. Kontynuujemy aż do wypełnienia całej mapy Karnaugh'a.

 

 

Wnętrze tabelki określa wartości sygnału A na współrzędnych określonych przez sygnały wejściowe, jest więc czymś w rodzaju mapy. Na mapie tej zaznaczamy maksymalne obszary obejmujące wartości 1. Zaznaczony obszar musi posiadać rozmiary będące potęgą liczby 2 (1, 2, 4, 8, ...). Oznacza to, że nie można zaznaczyć trzech leżących obok siebie jedynek. Obszary mogą łączyć się przez przeciwległe krawędzie tabelki. W naszym przykładzie dla sygnału A można zaznaczyć dwa takie obszary. Obszary te oznaczyliśmy jako FA i FB. Obszar FA mieści się całkowicie wewnątrz mapy. Obszar FB łączy się krawędziowo.

 

 

Teraz sprawdzamy, które współrzędne zmieniają swoją wartość w zaznaczonym obszarze, a które tego nie robią:

FA – zmienia się współrzędna b1, stałe są b2 i b0
FB – zmienia się b2, stałe są b1 i b0

Współrzędne, które zmieniają w obszarze swoją wartość, eliminujemy, ponieważ sygnały te nie wpływają na wartość w tym miejscu mapy sygnału wyjściowego A (czy mają wartość 0, czy 1, to i tak sygnał A przyjmuje dla nich stan 1). Z pozostałych sygnałów tworzymy iloczyn logiczny tak, aby miał on wartość 1. Wynika z tego, że w tym iloczynie sygnał o wartości 0 musi być zaprzeczony:

FA = !b2 && b0
FB = !b1 && b0

Sygnał A powstaje jako suma logiczna pól FA i FB:

A = FA || FB
A = (!b2 && b0) || (!b1 && b0)
A = b0 && (!b1 || !b2)
A = b0 && !(b1 && b2)

 

Dokonaliśmy minimalizacji funkcji logicznej dla sygnału wyjściowego A.

 

W identyczny sposób określamy funkcję logiczną dla sygnałów B i E:

 

FA = b2 && !b0
FB = b2 && !b1

B = E = FA || FB
B = E = (b2 && !b0) || (b2 && !b1)
B = E = b2 && (!b0 || !b1)
B = E = b2 && !(b0 && b1)

 

Sygnały C i F:

 

C = F = b2 && b1 && !b0

 

Sygnały D i G:

 

FA = !b2 && b1
FB = b1 && !b0
FC = b2 && !b1

D = G = FA || FB || FC
D = G = (!b2 && b1) || (b1 && !b0) || (b2 && !b1)
D = G = (b1 && (!b2 || !b0)) || (b2 && !b1)
D = G = (b1 && !(b2 && b0)) || (b2 && !b1)

 

Podsumujmy:

 

A = b0 && !(b1 && b2);
B = E = b2 && !(b0 && b1);
C = F = b2 && b1 && !b0;
D = G = (b1 && !(b2 && b0)) || (b2 && !b1)

 

Mając funkcje logiczne, możemy napisać prostą aplikację, która zasymuluje naszą sieć logiczną:

 
// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// Sieć logiczna
// PRG_46
//-----------------------------------

#include <iostream>

using namespace std;

void dotrow(int x, int y, int z)
{
   cout << "\263";
   if(x) cout << "\376"; else cout << " ";
   if(y) cout << "\376"; else cout << " ";
   if(z) cout << "\376"; else cout << " ";
   cout << "\263\n";
}

int main()
{
    int b2,b1,b0,A,B,C,D,E,F,G;

    for(b2 = 0; b2 < 2; b2++)
      for(b1 = 0; b1 < 2; b1++)
        for(b0 = 0; b0 < 2; b0++)
        {
          cout << " " << b2 << b1 << b0 << endl;

          A = b0 && !(b1 && b2);
          B = E = b2 && !(b0 && b1);
          C = F = b2 && b1 && !b0;
          D = G = (b1 && !(b2 && b0)) || (b2 && !b1);

          cout << "\332\304\304\304\277\n";
          dotrow(B,0,G);
          dotrow(C,A,F);
          dotrow(D,0,E);
          cout << "\300\304\304\304\331\n\n";
        }

    return 0;
}
 000
┌───┐
│   │
│   │
│   │
└───┘

 001
┌───┐
│   │
│ ■ │
│   │
└───┘

 010
┌───┐
│  ■│
│   │
│■  │
└───┘

 011
┌───┐
│  ■│
│ ■ │
│■  │
└───┘

 100
┌───┐
│■ ■│
│   │
│■ ■│
└───┘

 101
┌───┐
│■ ■│
│ ■ │
│■ ■│
└───┘

110
┌───┐
│■ ■│
│■ ■│
│■ ■│
└───┘

 111
┌───┐
│   │
│   │
│   │
└───┘

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.