Laboratorium techniki cyfrowej 2014/15

ćw. 1

Minimalizacja funkcji logicznych

 

UWAGA! Wszystkie zbudowane układy należy zapisać celem sprawdzenia przez prowadzącego.

 

1.     Mintermy, maxtermy, pełna postać kanoniczna funkcji

 

Każdą funkcję logiczną f można przedstawić jednoznacznie za pomocą tablicy prawdy, w której każdej kombinacji wejść przyporządkowana jest wartość funkcji (0 lub 1). Poniższa tablica przedstawia tablicę prawdy pewnej funkcji f:

 

 

indeks

a

b

c

d

f(a,b,c,d)

0

0

0

0

0

0

1

0

0

0

1

0

2

0

0

1

0

1

3

0

0

1

1

1

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

1

9

1

0

0

1

1

10

1

0

1

0

0

11

1

0

1

1

0

12

1

1

0

0

1

13

1

1

0

1

0

14

1

1

1

0

1

15

1

1

1

1

1

 

“Indeksy” każdego wiersza opisują odpowiednią kombinację wejść liczbą dziesiętną. Przyjmując, że zmienna d ma najmniejszą wagę, a zmienna a największą, „indeks” powstaje w wyniku obliczenia: d´20+c´21+b´22+a´23.

 

Istnieją takie funkcje, które przyjmują wartość 1 tylko dla jednej kombinacji wejść. Przykładowo funkcja  będzie miała wartość 1 tylko dla kombinacji wejść 0000. Z kolei funkcja wartość 1 będzie miała dla kombinacji wejść 0110. Przy n zmiennych możemy określić dokładnie 2n takich funkcji, a więc jest ich dokładnie tyle, co możliwych kombinacji wejść. A zatem każdej takiej funkcji można jednoznacznie przypisać indeks z powyższej tablicy.

 

Funkcję logiczną, która przyjmuje wartość 1 tylko dla jednej kombinacji wejść nazywamy mintermem.

 

Każdą funkcję logiczną można zapisać jako sumę mintermów, ważoną wartościami funkcji f:

 

 

,

gdzie fk jest wartością funkcji f dla k-tej kombinacji wejść, a mk jest mintermem z wartością 1 dla k-tej kombinacji wejść.

 

Stosując tego typu reprezentację dla funkcji f wyrażonej w powyższej tablicy prawdy, otrzymujemy jej pełną kanoniczną postać dysjunkcyjną:

 

Składniki, w których występuje mnożenie przez 0 można pominąć, a zatem kanoniczna postać dysjunkcyjna upraszcza się do postaci:

Funkcję można także jednoznacznie opisać za pomocą następującego uproszczonego wyrażenia, określającego sumę mintermów:

 

 

Zwróć uwagę na równoznaczność numeru mintermu z indeksem danej kombinacji w podanej tablicy prawdy.

 

***

 

Poza dysjunkcyjną  postacią kanoniczną funkcję można wyrazić także w pełnej kanonicznej postaci koniunkcyjnej:

Tak jak wcześniej, fk jest wartością wyjściowej funkcji f dla k-tej kombinacji wejść. Natomiast Mk jest maxtermem z wartością 0 dla k-tej kombinacji wejściowej.

 

Maxtermem nazwamy funkcję logiczną, która tylko dla jednej kombinacji wejść przyjmuje wartość 0.

 

Poniżej wypisano kilka maxtermów:

 

 

Podobnie jak w przypadku postaci dysjunkcyjnej, można zastosować uproszczenie zapisu. Tym razem polega ono na pominięciu czynników iloczynu, w których wartość funkcji (fk) przyjmuje wartość 1. Oto postać kanoniczna koniunkcyjna rozważanej funkcji f:

 

 

2.     Minimalizacja funkcji logicznej z użyciem siatek Karnaugha.

Realizacji funkcji logicznej w postaci kanonicznej często towarzyszy pewna nadmiarowość sprzętowa. Twierdzenie o minimalizacji mówi, że:

 

 

Postępując w taki sposób można „sklejać” ze sobą mintermy/maxtermy, co prowadzi do prostszej postaci funkcji logicznej. Przy niewielkiej liczbie zmiennych logicznych, minimalizację można poglądowo przeprowadzić w siatkach Karnaugha.

 

Siatka Karnaugha jest uporzadkowaną strukturą złożoną z 2n kratek (dla n zmiennych logicznych). Każda kratka reprezentuje jeden minterm/maxterm, przy czym sąsiadujące kratki różni wartość tylko jednej zmiennej. Sąsiedztwo dotyczy także kratek leżących wzdłuż przeciwległych brzegów siatki, a także wszystkich czterech kratek narożnych. 

 

Każdy minterm lub sumę mintermów, które można „skleić” w tabeli Karnaugha nazywamy implikantem. 

 

Implikant, którego nie można już rozszerzyć w tablicy Karnaugha określa się mianem implikantu prostego.

 

Implikant istotny to implikant prosty, który zawiera minterm nie występujący w żadnym innym implikancie prostym.

 

Implikant powstaje w operacji minimalizacji. Przykładowo sklejając mintermy oraz powstaje implikant ab.

 

Podobne definicje w przypadku minimalizacji „w zerach” dotyczą implicentów.

 

Poniżej przedstawiono siatki Karnaugha dla dwóch, trzech i czterech zmiennych. Wypisane w prawych narożnikach kratek liczby są to numery implikantów/implicentów, odpowiadających poszczególnym kombinacjom wejść (są to też numery wierszy z tablicy prawdy).

 

Siatki Karnaugha

 

 

Odpowiednie kratki tabeli Karnaugha wypełniamy wartościami funkcji f, którą chcemy minimalizować. Sklejać można tylko sąsiadujące ze sobą kratki, dla których funkcja ma tę samą wartość. Liczba sklejanych kratek musi być potęgą dwójki. Poniżej przykład sklejania „w jedynkach” dla funkcji f(a,b,c,d).

 

Minimalizacja w jedynkach

Poszczególne implikanty proste wyróżniono różnymi kolorami. Następnym krokiem jest taki wybór zaznaczonych implikantów, aby zapewnić „pokrycie” wszystkich mintermów funkcji f(a,b,c,d). Istnieje więcej niż jedno rozwiązanie, przy czym niektóre mogą prowadzić do prostszych funkcji, inne – do bardziej złożonych. Decydują o tym liczba oraz „rozmiary” zastosowanych implikantów. 

 

 

Implikanty oznaczone kolorami: żółtym, czerwonym i granatowym są implikantami istotnymi, tzn. muszą zostać użyte w realizacji funkcji. Natomiast możemy dokonać wyboru pomiędzy implikantami w kolorze zielonym i błękitnym. Oba te implikanty mają takie same rozmiary, jednak w ogólnym przypadku tak być nie musi.

 

Z tablicy Karnaugha można wprost odczytać uproszczoną postać funkcji. Przy minimalizacji „w jedynkach” zminimalizowana funkcja ma postać sumy implikantów. Wyznaczone zostaną teraz funkcje, które są realizowane przez poszczególne implikanty proste.

 

Implikant żółty – obejmuje mintermy, dla których b=0 lub b=1, zatem implikant żółty nie zależy od b. Tak samo nie zależy od zmiennej d. Implikant żółty obejmuje mintermy, dla których zmienna a=0 i c=1. A zatem implikant żółty realizuje funkcję .   

 

Implikant czerwony – nie zależy od a, nie zależy od d, realizuje funkcję bc,

 

Implikant  granatowy – niezależny od d, realizuje funkcję .

 

Implikant zielony – niezależny od b, realizuje funkcję .

 

Implikant błękitny – niezależny od c, realizuje funkcję . 

 

Dla pokrycia wszystkich implikantów musimy użyć implikantów: żółtego, czerwonego, granatowego oraz jednego z dwóch: zielonego lub błękitnego. Wybierając  zielony, zminimalizowana funkcja ma postać:

 

Natomiast wybierając błękitny:

 

 

Minimalizacja w jedynkach przyniosła ewidentne korzyści: zamiast 9 składników i 36 literałów w pełnej dysjunkcyjnej postaci kanonicznej mamy 4 składniki i 10 literałów.

 

Minimalizacja w zerach

Obecnie zminimalizujemy funkcję f(a,b,c,d) w zerach:

 

Minimalizacja w 0

 

 

Jak widać, przy minimalizacji w zerach liczba implicentów jest mniejsza niż implikantów przy minimalizacji w jedynkach. Wszystkie implicenty są istotne, co oznacza, że nie mamy żadnego wyboru i wszystkie znalezione implicenty muszą zostać użyte:

 

Implicent żółty – nie zależy od b, nie zależy od d, realizuje funkcję a+c.

 

Implicent czerwony  - nie zależy od a, realizuje funkcję .

 

Implicent granatowy – nie zależy od zmiennej d, realizuje funkcję  .

 

Funkcja f(a,b,c,d) zminimalizowana w zerach ma postać

 

Zysk z minimalizacji jest ewidentny: wyjściowa kanoniczna postać koniunkcyjna miała 7 czynników (makstermów) i 28 literałów. W postaci zminimalizowanej występują jedynie 3 czynniki i 8 literałów. Widać, że minimalizacja w zerach doprowadziła do prostszej realizacji niż minimalizacja w jedynkach.

 

3.       Realizacja funkcji z wykorzystaniem wyłącznie bramek NAND albo tylko bramek NOR.

 

Prawo DeMorgana określa związek pomiędzy operacjami AND i OR:

 

        

 

A zatem do realizacji dowolnej funkcji logicznej wystarczające jest użycie jedynie bramek dwóch rodzajów: AND, NOT lub OR, NOT (zbiory funkcji {AND, NOT} oraz {OR, NOT} stanowią systemy funkcjonalnie pełne). Realizacja sumy za pomocą AND i NOT:

Negując obie strony otrzymujemy:

Wyrażenia X i Y mogą być mintermami lub implikantami. A zatem suma implikantów może być zrealizowana jako zanegowany iloczyn zanegowanych implikantów. Aby pozbyć się operacji NOT, można wykorzystać bramki realizujące zanegowany iloczyn (NAND).

 

Poniższe układy realizują taką samą funkcję:

NAND

W implikantach mogą występować zmienne wejściowe w postaci zanegowanej (np. ), jednak negację można zrealizować także za pomocą bramki NAND (jak?). Dlatego też cały układ można zbudować wykorzystując jedynie bramki NAND (funkcja NAND stanowi system funkcjonalnie pełen).

 

Pewną trudność stanowi przypadek, gdy dysponujemy wyłącznie bramkami NAND o dwóch wejściach. Poniżej przykładowe przekształcenie rozwiązujące ten problem:

 

Lub też alternatywnie:

Pamiętamy, że negację wykonujemy za pomocą bramek NAND.

 

* * *

W przypadku postaci koniunkcyjnej, funkcja ma postać iloczynu maxtermów lub implicentów. Wówczas układ może być łatwo zbudowany z wykorzystaniem jedynie bramek NOR. Prowadzi do tego przekształcenie:

 

Za pomocą bramek NOR można zrealizować także funkcję w postaci dysjunkcyjnej. Z reguły takie postępowanie prowadzi jednak do większej złożoności:

Podobnie, gdyby chcieć zrealizować funkcję w postaci koniunkcyjnej na bramkach NAND.

 

 

 

 

 

4.     Pierwsza symulacja w MultiSim

 

Po otwarciu programu MultiSim automatycznie tworzony jest nowy projekt (Circuit 1) , którego struktura jest ukazana w oknie w lewym narożniku ekranu.  Posiada on jeden schemat o tej samej nazwie. Środkową część ekranu tworzy obszar roboczy. Umieszcza się tam elementy wybrane z bibliotek lub utworzone przez użytkownika.

 

Elementy (bramki logiczne, przełączniki, multipleksery itp.) znajdują się w bibliotekach. Biblioteka jest dostępna poprzez menu Place>Component. Otwiera się wówczas okno jak na rysunku 1. Menu to jest też dostępne poprzez kliknięcie prawym klawiszem w obszarze roboczym lub kombinację Ctrl+W. 

 

Select%20a%20Component

Rys.  1 Biblioteka elementów

Należy wybrać rodzinę elementów cyfrowych. Zasadniczo w ćwiczeniach wykorzystywać będziemy rodzinę TTL. Po dokonaniu tego wyboru w środkowej części okna należy wybrać konkretny element. Można je znaleźć wpisując odpowiedni numer w okienku edycji, albo wybrać z listy. W oknie „Function” znajduje się opis danego elementu. W przypadku rys. 1 jest to dwuwejściowa bramka logiczna realizująca funkcję NOR. Po naciśnięciu OK element można umieścić w dowolnym miejscu schematu.

 

Często elementy scalone złożone są z kilku sekcji, realizujących takie same funkcje. Sekcje oznaczone są kolejnymi literami. Na rys. 2 pokazano fragment obszaru roboczego, na którym znajdują się dwa inwertery. Należą one do różnych elementów scalonych (U2 i U3). Na rys. 3 pokazano okienko pojawiające się przy wstawianiu kolejnego inwertera. Widać, że w elemencie scalonym U2 wykorzystana jest już sekcja „A”, w elemencie U3 – sekcja „B”. Wstawiając nowy inwerter, możemy go przypisać do niewykorzystanych sekcji używanych już elementów scalonych, lub też wstawić kolejny element scalony. 

Segmenty

Rys.  2 Inwertery należące do różnych elementów scalonych (jeden stanowi sekcję „A” układu scalonego U2, drugi – sekcję „B” układu U3).

 

Wybór%20segmentu

Rys.  3 Przypisanie bramki do elementu scalonego

 

Położenie wyprowadzeń („pinów”) w modelach elementów scalonych nie odpowiada rzeczywistości. W szczególności brakujeeśla się ści brak wyprowadzeń, na które należy podać zasilanie i masę. eczywistości.  wyprowadzeń, na które podaje się zasilanie i masę. W MultiSim zasilanie każdego z elementów odbywa się wirtualnie poprzez umieszczenie w dowolnym miejscu na schemacie obiektów z grupy Sources: DGND  oraz VCC  (w przypadku stosowania elementów TTL).Nie należy do nich niczego podłączać!

Jako źródła stałych logicznych „1” i „0” można używać odpowiednio obiektów VCC  oraz GND . Do zbudowania pierwszego układu cyfrowego potrzebne jeszcze będą przełączniki (Group: Basic> SWITCH>SPDT  oraz element Group: Indicators> PROBE> PROBE ). Można przypisać klawisz, który powoduje zmianę położenia przełącznika. W przeciwnym razie wszystkie przełączniki będą zmieniane jednym klawiszem.

 

Przykładowy schemat zbudowany w MultiSim przedstawia rys. 4. Wszystkie przełączniki są sterowane klawiszem spacji. Zwróć uwagę na umieszczone elementy VCC i DGND w lewym rogu.

 

 

Rys.  4 Prosty schemat układu kombinacyjnego w MultiSim

 

Uruchomienie symulacji: Simulate>Run, klawisz F5 lub kontrolka „Play”. Po uruchomieniu symulacji na pasku w prawym narożniku wyświetlany jest bieżący czas symulacji.

 

Word Generator 

Jako źródło sygnałów logicznych wygodnie jest korzystać z Word Generatora. Można go znaleźć pośród narzędzi MultiSim, zgrupowanych wzdłuż prawej krawędzi okna symulatora.

WordGen

 

Narzędzie to umożliwia generowanie dowolnych sekwencji. W panelu Controls wybieramy tryb pracy generatora:

Cycle – ciągły,

Burst – pojedynczy przebieg sekwencji,

Step – praca krok w sekwencji, wyzwalanie poprzez naciskanie Step.

 

Kolejne zmienne logiczne podawane są przez Generator na wyprowadzenia 0…15 i 16…31 (zmienna odpowiadająca najmniej znaczącej pozycji binarnej jest generowana na wyjściu 0).

 

Po kliknięciu Set następuje przejście do ustawień sekwencji: Długość sekwencji ustawia się w polu Buffer size. Zależnie od wyboru Hex/Dec wielkość tę podaje się szesnastkowo lub dziesiętnie. Clear Buffer czyści poprzednią zawartość sekwencji. Up counter oraz Down counter nadają sekwencji postać ciągu rosnącego/malejącego pomiędzy wartościami Initial Pattern oraz Buffer size. Natomiast opcje Shift Right/Shift left oznaczają sekwencje z jedynką przesuwaną w prawo/lewo o jedną pozycję (czyli ciąg geometryczny o q=2 lub q=1/2).

 

Bardzo przydatną cechą jest możliwość edycji dowolnego wyrazu w sekwencji. W tym celu wystarczy kliknąć w niego i nanieść odpowiednie zmiany (uwaga na format zapisu zależny od wyboru w przełącznikach Display!). Aby nie było konieczności każdorazowej zmiany wielkości bufora, możliwe jest ustawienie znaczników Initial Position oraz Final Position w polach przy wartościach poszczególnych wyrazów.

 

 

 

Zadanie 1. Znajdź minimalną postać dysjunkcyjną funkcji f(a,b,c,d)=m(0,2,3,7,8,9,12)+d(1,10,13) i zrealizuj ją w MultiSim wyłącznie za pomocą dwuwejściowych bramek NAND.

 

Zadanie 2. Zminimalizuj funkcję g(a,b,c,d)=M(0,1,2,3,11,13)+d(8,12,15) w zerach i zbuduj układ realizujący tę funkcję wyłącznie za pomocą dwuwejściowych bramek NOR.