Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki: zadania z rozwiązaniami krok po kroku

1Jedynki, zera i bramki

Układy cyfrowe operują dwiema wartościami: 0 (niskie napięcie, fałsz) i 1 (wysokie napięcie, prawda). Bramka logiczna przyjmuje jedno lub więcej wejść i daje jedno wyjście.

• AND daje 1 tylko wtedy, gdy wszystkie wejścia są równe 1. Zapis A·B lub AB.
• OR daje 1, gdy co najmniej jedno wejście jest równe 1. Zapis A + B.
• NOT neguje: 0 staje się 1, a 1 staje się 0. Zapis A′ (lub z kreską nad A).
• NAND i NOR to AND i OR z następującym po nich NOT; małe kółko na symbolu oznacza „zanegowane”.
• XOR (A ⊕ B) daje 1, gdy wejścia się różnią.

Tablica prawdy podaje wyjście dla każdej kombinacji wejść: 2ⁿ wierszy dla n wejść. Wiersz ABC = 101 ma numer 5 i nazywa się mintermem m₅.

2Algebra Boole’a

Wyrażenia logiczne podlegają regułom podobnym do zwykłej algebry, plus kilku własnym. Najprzydatniejsze:

Reguła sklejania X·Y + X·Y′ = X jest sercem upraszczania: dwa składniki różniące się jedną zmienną łączą się, a ta zmienna znika.

Suma iloczynów (SOP) to OR składników AND, na przykład F = AB′ + C. Iloczyn sum (POS) to AND składników OR, na przykład F = (A + B)(B′ + C). Każdy iloczyn składa się z literałów: zmiennych z negacją lub bez.

3Mapy Karnaugha

Mapa Karnaugha to tablica prawdy narysowana jako siatka, w której sąsiednie komórki różnią się dokładnie jedną zmienną. Dlatego wiersze i kolumny idą 00, 01, 11, 10 (kod Graya), a nie w kolejności binarnej.

1. Wpisz 1 w komórce każdego mintermu; mała liczba w komórce to numer mintermu.
2. Narysuj prostokąty z 1, 2, 4, 8 lub 16 komórek wokół jedynek. Grupy mogą zawijać się przez brzegi: lewa i prawa kolumna sąsiadują ze sobą, podobnie górny i dolny wiersz.
3. Rób każdą grupę jak największą i używaj jak najmniej grup, aż każda jedynka będzie pokryta.
4. Odczytaj każdą grupę jako iloczyn: zostaw tylko zmienne, które się w niej nie zmieniają. Grupa 2ᵏ komórek traci k zmiennych.

Na powyższej mapie cztery jedynki tworzą jedną grupę. W niej A się zmienia i C się zmienia, stałe jest tylko B = 1, więc F = B.

Komórki oznaczone X to stany nieokreślone (don’t care): kombinacje wejść, które nigdy nie występują. Użyj X jako 1, gdy powiększa grupę, a w przeciwnym razie zignoruj. Grupowanie zer daje minimalną postać POS.

4Przykład krok po kroku

Przejdź przez każdy krok. Spróbuj przewidzieć następny, zanim go odsłonisz.

5Przerzutniki i liczniki

Bramki reagują na wejścia natychmiast. Przerzutnik przechowuje jeden bit i zmienia się tylko przy aktywnym zboczu zegara (zwykle narastającym).

• Przerzutnik D: Q przyjmuje wartość D przy każdym zboczu zegara (Q⁺ = D).
• Przerzutnik T: zmienia stan na przeciwny, gdy T = 1, utrzymuje, gdy T = 0.
• Przerzutnik JK: JK = 00 utrzymuje, 01 zeruje do 0, 10 ustawia na 1, 11 zmienia stan na przeciwny.

Przerzutnik zmieniający stan na przeciwny przełącza się przy każdym zboczu narastającym, więc jego wyjście ma połowę częstotliwości zegara. Połączenie n takich przerzutników daje n-bitowy licznik binarny o 2ⁿ stanach. Licznik mod-N liczy 0, 1, …, N − 1 i wraca do 0; potrzebuje najmniejszego n, dla którego 2ⁿ ≥ N, a jego ostatnie wyjście pracuje z częstotliwością f_clk/N.

W liczniku asynchronicznym każdy stopień jest taktowany przez poprzedni, więc opóźnienia się sumują: okres zegara musi wynosić co najmniej n·t_pd. Liczniki z rejestrem przesuwającym używają mniejszej liczby stanów: licznik pierścieniowy z n przerzutników ma n stanów, licznik Johnsona 2n.

6Typowe błędy

• Zapisywanie kolumn mapy Karnaugha jako 00, 01, 10, 11. Kolejność to kod Graya: 00, 01, 11, 10.
• Zapominanie, że grupy zawijają się przez brzegi mapy.
• Tworzenie grup po 3 lub 6 komórek. Grupy mają 1, 2, 4, 8 lub 16 komórek.
• Pokrywanie stanu nieokreślonego, który nie pomaga: X nigdy nie musi być pokryte.
• Odczytywanie grupy przez zachowanie zmiennych, które się zmieniają. Zachowaj tylko te, które są stałe.
• Zapominanie, że licznik się zawija: n-bitowy licznik liczy modulo 2ⁿ.

7Jak wyglądają zadania egzaminacyjne

• Łatwe: obliczanie układu bramek dla danych wejść, liczenie jedynek w jego tablicy prawdy, umieszczanie mintermu na mapie Karnaugha, liczba bramek NAND dla funkcji albo najgorsze opóźnienie propagacji.
• Średnie: upraszczanie wyrażenia, znajdowanie minimalnej postaci SOP lub POS za pomocą mapy Karnaugha, funkcja zbudowana z multipleksera albo izolowana jedynka mapy.
• Trudne: mapy ze stanami nieokreślonymi, istotne implikanty proste, diagramy czasowe przerzutników, liczniki po wielu impulsach, liczba przerzutników lub częstotliwość wyjścia oraz rejestry przesuwające.

Sprawdź uproszczone wyrażenie, testując jeden lub dwa wiersze tablicy prawdy: oryginał i postać uproszczona muszą dawać to samo wyjście.