Kanoniczna postać normalna
W algebrze Boole'a każdą funkcję Boole'a można wyrazić w kanonicznej postaci normalnej dysjunkcyjnej ( CDNF ) lub postaci kanonicznej minterm oraz jej podwójnej kanonicznej koniunkcyjnej postaci normalnej ( CCNF ) lub postaci kanonicznej maxterm . Inne formy kanoniczne obejmują pełną sumę głównych implikantów lub formę kanoniczną Blake'a (i jej podwójną) oraz algebraiczną postać normalną (zwaną także Zhegalkin lub Reed-Muller).
Mintermy nazywane są produktami, ponieważ są logicznym AND zestawu zmiennych, a maxtermy nazywane są sumami, ponieważ są logicznym LUB zestawu zmiennych. Pojęcia te są dualne ze względu na ich relację komplementarności-symetrii, wyrażoną przez prawa De Morgana .
Dwie podwójne formy kanoniczne dowolnej funkcji boolowskiej to „suma minterms” i „iloczyn maxterms”. Termin „ Suma produktów ” ( SOP lub SOP ) jest szeroko stosowany w odniesieniu do formy kanonicznej, która jest dysjunkcją (OR) mintermów. Jego liczba dualna De Morgana jest „ iloczynem sum ” ( PoS lub POS ) dla postaci kanonicznej, która jest koniunkcją (AND) makstermów. Formy te mogą być przydatne do uproszczenia tych funkcji, co ma ogromne znaczenie w optymalizacji formuł boolowskich w ogóle, aw szczególności układów cyfrowych .
Mintermy
Dla funkcji logicznej zmiennych , termin produktu , w każdy z zmienne pojawiające się raz (w formie uzupełnionej lub nieuzupełnionej) nazywa się minterm . Zatem minterm jest logicznym wyrażeniem n zmiennych, które wykorzystuje tylko operator dopełnienia i operator koniunkcji .
Na przykład za za b trzech , i do . Zwyczajowe odczytanie ostatniego z nich to a AND b AND NOT-c .
Istnieje 2 n mintermów z n zmiennych, ponieważ zmienna w wyrażeniu minterm może być w formie bezpośredniej lub uzupełnionej — dwie możliwości na zmienną.
Indeksowanie mintermów
Mintermy są często numerowane za pomocą binarnego kodowania wzorca uzupełniania zmiennych, w którym zmienne są zapisywane w standardowej kolejności, zwykle alfabetycznie. Ta konwencja przypisuje wartość 1 do formy bezpośredniej ( , a 0 do formy uzupełnionej ( ; ∑ . Na przykład minterm ponumerowany 110 2 = 6 10 i oznaczony m }
Równoważność funkcjonalna
Dany minterm n daje prawdziwą wartość (tj. 1) tylko dla jednej kombinacji zmiennych wejściowych. Na przykład minterm 5, a b ' c , jest prawdziwe tylko wtedy, gdy oba a i c są prawdziwe, a b jest fałszywe — układ danych wejściowych, w którym a = 1, b = 0, c = 1 daje w wyniku 1.
Mając tablicę prawdy funkcji logicznej, można zapisać tę funkcję jako „sumę iloczynów”. Jest to szczególna postać dysjunktywnej postaci normalnej . Na przykład, jeśli dana jest tablica prawdy dla sumy arytmetycznej bitu u logiki jednej pozycji bitowej obwodu sumatora, jako funkcja x i y z dodanych i przeniesionych, ci :
| ci | X | y | u(ci,x,y) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Obserwując, że wiersze, które mają wynik 1, to wiersze 2, 3, 5 i 8, możemy zapisać u jako sumę mintermów i . Jeśli chcemy to zweryfikować: zmiennych dopasować do tabeli.
Maksymalne warunki
Dla funkcji logicznej n zmiennych sumy, w którym każda n się ( uzupełnionym lub forma nieuzupełniona) nazywa się maxterm . Tak więc maxterm jest logicznym wyrażeniem n zmiennych, które wykorzystuje tylko operator dopełnienia i operator alternatywy . Maxtermy są dualnością idei minterm (tj. wykazują komplementarną symetrię pod każdym względem). Zamiast używać ORAZ i dopełnień, używamy OR i dopełnień i postępujemy podobnie.
Na przykład poniżej przedstawiono dwa z ośmiu maksymalnych warunków trzech zmiennych:
- za + b ′ + do
- za ′ + b + do
Znowu mamy 2 n maxtermów z n zmiennych, ponieważ zmienna w wyrażeniu maxterm może być albo w formie bezpośredniej, albo w formie uzupełnionej — dwie możliwości na zmienną.
Indeksowanie maxterms
0 Każdemu maxtermowi przypisany jest indeks oparty na przeciwstawnym konwencjonalnym kodowaniu binarnym używanym w przypadku mintermów. Konwencja maxterm przypisuje wartość 0 do formy bezpośredniej \ . Na przykład indeks 6 do maxterm 110 ) M . Podobnie M z tych trzech zmiennych to ) M 7 to 111 ).
Równoważność funkcjonalna
Jest oczywiste, że maxterm n daje fałszywą wartość (tzn. 0) tylko dla jednej kombinacji zmiennych wejściowych. Na przykład maxterm 5, a ′ + b + c ′, jest fałszywy tylko wtedy, gdy oba a i c są prawdziwe, a b jest fałszywe — układ wejściowy, w którym a = 1, b = 0, c = 1 daje w wyniku 0.
Jeśli dana jest tablica prawdy funkcji logicznej, można zapisać tę funkcję jako „iloczyn sum”. Jest to szczególna forma koniunkcyjnej postaci normalnej . Na przykład, jeśli dana jest tabela prawdy dla bitu wykonania co logiki jednej pozycji bitowej obwodu sumatora, jako funkcja x i y z dodanych i przeniesionych elementów, ci :
| ci | X | y | co(ci,x,y) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Obserwując, że wiersze, które mają wynik 0, to 1, 2, 3 i 5, możemy zapisać co jako iloczyn maxterms i . Jeśli chcemy to zweryfikować:
obliczone dla wszystkich 8 kombinacji trzech zmiennych będzie pasować do tabeli.
Dualizacja
Uzupełnieniem minterm jest odpowiedni maxterm. Można to łatwo zweryfikować, korzystając z prawa de Morgana . Na przykład:
Niekanoniczne formularze PoS i SoP
Często zdarza się, że kanoniczny formularz minterm można uprościć do równoważnego formularza SoP. Ta uproszczona forma nadal składałaby się z sumy terminów produktów. Jednak w uproszczonej formie możliwe jest posiadanie mniejszej liczby terminów produktów i/lub terminów produktów zawierających mniej zmiennych. Na przykład następująca funkcja 3-zmienna:
| A | B | C | f(a,b,c) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
kanoniczną reprezentację minterm: równoważną uproszczoną postać: W tym trywialnym przykładzie jest oczywiste, że , ale uproszczona forma ma zarówno mniej terminów produktowych, jak i termin ma mniej zmiennych.
Najbardziej uproszczona reprezentacja SoP funkcji jest określana jako minimalna forma SoP .
W podobny sposób kanoniczny formularz maxterm może mieć uproszczony formularz PoS.
Chociaż ten przykład został uproszczony przez zastosowanie normalnych metod algebraicznych [ ], w mniej oczywistych przypadkach wygodna metoda znajdowania minimalnego PoS / SoP postać funkcji z maksymalnie czterema zmiennymi wykorzystuje mapę Karnaugha .
Minimalne formy PoS i SoP są ważne dla znajdowania optymalnych implementacji funkcji boolowskich i minimalizowania obwodów logicznych.
Przykład zastosowania
Przykładowe tabele prawdy dla minterms i maxterms powyżej są wystarczające do ustalenia postaci kanonicznej dla pojedynczej pozycji bitowej po dodaniu liczb binarnych, ale nie są wystarczające do zaprojektowania logiki cyfrowej, chyba że twój inwentarz bramek zawiera AND i OR. Tam, gdzie wydajność jest problemem (jak w Apollo Guidance Computer), dostępne części to raczej NAND i NOR ze względu na działanie uzupełniające nieodłącznie związane z logiką tranzystorową. Wartości są zdefiniowane jako stany napięciowe, jeden w pobliżu masy i jeden w pobliżu napięcia zasilania DC V cc , np. +5 VDC. Jeśli wyższe napięcie jest zdefiniowane jako „prawdziwa” wartość 1, bramka NOR jest najprostszym możliwym użytecznym elementem logicznym.
W szczególności 3-wejściowa bramka NOR może składać się z 3 bipolarnych tranzystorów złączowych z uziemionymi emiterami, połączonymi ze sobą kolektorami i połączonymi z Vcc przez impedancję obciążenia. Każda baza jest podłączona do sygnału wejściowego, a wspólny punkt kolektora przedstawia sygnał wyjściowy. Każde wejście, które ma 1 (wysokie napięcie) do swojej bazy, powoduje zwarcie emitera tranzystora z kolektorem, powodując przepływ prądu przez impedancję obciążenia, co powoduje, że napięcie kolektora (wyjście) jest bardzo bliskie ziemi. Ten wynik jest niezależny od innych danych wejściowych. Tylko wtedy, gdy wszystkie 3 sygnały wejściowe są równe 0 (niskie napięcie), impedancje emiter-kolektor wszystkich 3 tranzystorów pozostają bardzo wysokie. Wtedy płynie bardzo mały prąd, a efekt dzielnika napięcia z impedancją obciążenia nakłada na punkt kolektora wysokie napięcie bardzo bliskie Vcc .
Właściwość komplementarności tych obwodów bramek może wydawać się wadą przy próbie zaimplementowania funkcji w postaci kanonicznej, ale istnieje kompensująca premia: taka bramka z tylko jednym wejściem implementuje funkcję komplementarną, która jest często wymagana w logice cyfrowej.
Ten przykład zakłada inwentaryzację części Apollo: tylko 3-wejściowe bramki NOR, ale dyskusję upraszcza się, zakładając, że dostępne są również 4-wejściowe bramki NOR (w Apollo zostały one złożone z par 3-wejściowych bramek NOR).
Kanoniczne i niekanoniczne konsekwencje bramek NOR
Zestaw 8 bramek NOR, jeśli wszystkie ich dane wejściowe są kombinacjami form bezpośrednich i dopełniających 3 zmiennych wejściowych ci, x i y , zawsze dają mintermy, nigdy makstermy — to znaczy z 8 bramek wymaganych do przetworzenia wszystkich kombinacji z 3 zmiennych wejściowych tylko jedna ma wartość wyjściową 1. Dzieje się tak dlatego, że bramkę NOR, pomimo swojej nazwy, można lepiej postrzegać (używając prawa De Morgana) jako AND dopełnień jej sygnałów wejściowych.
Powodem, dla którego nie stanowi to problemu, jest dwoistość minterms i maxterms, tj. każdy maxterm jest uzupełnieniem minterm o podobnym indeksie i vice versa.
W powyższym przykładzie minterm napisaliśmy , ale aby wykonać to z 4-wejściową bramką NOR, musimy przekształcić ją jako iloczyn sum (PoS), gdzie sumy są przeciwstawnymi makstermami. To jest,
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
W powyższym przykładzie maxterm napisaliśmy , ale aby wykonać to z 4-wejściową bramką NOR, musimy zauważyć równość z NOR tych samych mintermów. To jest,
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Oprócz form kanonicznych uwzględniono kompromisy projektowe
Można by przypuszczać, że praca nad zaprojektowaniem etapu dodawania jest już zakończona, ale nie odnieśliśmy się jeszcze do faktu, że wszystkie 3 zmienne wejściowe muszą występować zarówno w formie bezpośredniej, jak i dopełniającej. Pod tym względem nie ma trudności z dodatkami x i y , ponieważ są one statyczne podczas dodawania i dlatego zwykle są trzymane w obwodach zatrzaskowych, które rutynowo mają zarówno wyjścia bezpośrednie, jak i uzupełniające. (Najprostszy obwód zatrzaskowy wykonany z bramek NOR to para bramek połączonych krzyżowo w celu utworzenia przerzutnika: wyjście każdej z nich jest połączone jako jedno z wejść do drugiej.) Nie ma również potrzeby tworzenia formy uzupełnienia sumy u . Jednak przeniesienie z jednej pozycji bitowej musi zostać przekazane jako przeniesienie do następnej pozycji bitowej zarówno w formie bezpośredniej, jak i uzupełniającej. Najprostszym sposobem na to jest przekazanie co przez 1-wejściową bramkę NOR i oznaczenie wyjścia co ′, ale to dodałoby opóźnienie bramki w najgorszym możliwym miejscu, spowalniając falowanie przenoszenia od prawej do lewej. Dodatkowa 4-wejściowa bramka NOR budująca postać kanoniczną co ′ (spośród przeciwstawnych mintermów jako co ) rozwiązuje ten problem.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kompromis związany z utrzymaniem pełnej prędkości w ten sposób obejmuje nieoczekiwany koszt (oprócz konieczności użycia większej bramy). Gdybyśmy po prostu użyli tej 1-wejściowej bramki do uzupełnienia , nie byłoby pożytku z minterm a bramka, która ją wygenerowała, mogłaby zostać wyeliminowana Niemniej jednak nadal jest to dobry handel.
Teraz moglibyśmy zaimplementować te funkcje dokładnie zgodnie z ich kanonicznymi formami SoP i PoS, zamieniając bramki NOR na określone funkcje. Bramka NOR jest przekształcana w bramkę OR, przepuszczając jej wyjście przez 1-wejściową bramkę NOR; i jest przekształcany w bramkę AND, przepuszczając każde z jego wejść przez 1-wejściową bramkę NOR. Jednak takie podejście nie tylko zwiększa liczbę używanych bramek, ale także podwaja liczbę opóźnień bramek przetwarzających sygnały, zmniejszając prędkość przetwarzania o połowę. W związku z tym, ilekroć wydajność jest niezbędna, warto wyjść poza formy kanoniczne i wykonać algebrę Boole'a, aby niewzmocnione bramki NOR wykonały zadanie.
Projektowanie od góry do dołu vs. od dołu do góry
Widzieliśmy teraz, w jaki sposób narzędzia minterm/maxterm mogą być użyte do zaprojektowania stopnia sumującego w postaci kanonicznej z dodatkiem pewnej algebry Boole'a, kosztem zaledwie 2 opóźnień bramek dla każdego z wyjść. To „odgórny” sposób projektowania obwodu cyfrowego dla tej funkcji, ale czy jest to najlepszy sposób? Dyskusja skupiła się na określeniu „najszybszego” jako „najlepszego”, a rozszerzona forma kanoniczna spełnia to kryterium bezbłędnie, ale czasami dominują inne czynniki. Głównym celem projektanta może być zminimalizowanie liczby bramek i/lub zminimalizowanie rozgałęzień sygnałów do innych bramek, ponieważ duże rozgałęzienia zmniejszają odporność na obniżone zasilanie lub inne czynniki środowiskowe. W takim przypadku projektant może opracować projekt w formie kanonicznej jako punkt odniesienia, następnie spróbować rozwoju oddolnego i na koniec porównać wyniki.
Rozwój oddolny polega na zauważeniu, że u = ci XOR ( x XOR y ), gdzie XOR oznacza wyłączne LUB [prawda, gdy którekolwiek wejście jest prawdziwe, ale nie, gdy oba są prawdziwe], oraz że co = ci x + xy + y ci . Jeden taki rozwój wymaga łącznie dwunastu bramek NOR: sześć bramek 2-wejściowych i dwie bramki 1-wejściowe do wytworzenia u w 5 opóźnieniach bramkowych, plus trzy bramki 2-wejściowe i jedna bramka 3-wejściowa do wytworzenia co ′ w opóźnieniach 2 bramek. Kanoniczna linia bazowa obejmowała osiem 3-wejściowych bramek NOR plus trzy 4-wejściowe bramki NOR, aby wytworzyć u, co i co ′ w 2 opóźnieniach bramek. Jeśli inwentarz obwodów faktycznie obejmuje 4-wejściowe bramki NOR, kanoniczny projekt odgórny wygląda jak zwycięzca zarówno pod względem liczby bramek, jak i szybkości. Ale jeśli (w przeciwieństwie do naszego wygodnego założenia) obwody są w rzeczywistości 3-wejściowymi bramkami NOR, z których dwie są wymagane dla każdej 4-wejściowej funkcji NOR, to projekt kanoniczny przyjmuje 14 bramek w porównaniu do 12 dla podejścia oddolnego, ale nadal generuje cyfrę sumy u znacznie szybciej. Porównanie fanoutów przedstawiono w tabeli jako:
| Zmienne | Z góry na dół | Od dołu do góry |
|---|---|---|
| X | 4 | 1 |
| X' | 4 | 3 |
| y | 4 | 1 |
| ty' | 4 | 3 |
| ci | 4 | 1 |
| ci' | 4 | 3 |
| M lub m | 4@1,4@2 | Nie dotyczy |
| x XOR y | Nie dotyczy | 2 |
| różne | Nie dotyczy | 5@1 |
| Maks | 4 | 3 |
Opis rozwoju oddolnego wymienia co ′ jako produkt, ale nie co . Czy ten projekt po prostu nigdy nie potrzebuje bezpośredniej formy realizacji? Cóż, tak i nie. Na każdym etapie obliczenie co ′ zależy tylko od ci ′, x ′ i y ′, co oznacza, że propagacja przeniesienia faluje wzdłuż pozycji bitów tak samo szybko, jak w projekcie kanonicznym, bez rozwijania co . Obliczenie u , które wymaga wykonania ci z ci ′ przez 1-wejściowy NOR, jest wolniejsze, ale dla dowolnej długości słowa projekt płaci tę karę tylko raz (kiedy rozwijana jest najbardziej wysunięta na lewo cyfra sumy). Dzieje się tak, ponieważ te obliczenia nakładają się na siebie, a każde z nich stanowi własny mały potok bez wpływu na to, kiedy można obliczyć bit sumy następnej pozycji bitowej. I, dla pewności, co ′ na skrajnej lewej pozycji bitowej będzie prawdopodobnie musiało zostać uzupełnione jako część logiki określającej, czy dodatek został przepełniony. Ale przy użyciu 3-wejściowych bramek NOR, projekt oddolny jest prawie tak szybki, aby wykonać równoległe dodawanie na nietrywialnej długości słowa, zmniejsza liczbę bramek i wykorzystuje mniejsze fanouty ... więc wygrywa, jeśli liczba bramek i/lub fanout są najważniejsze!
Dokładny schemat układu oddolnego, w którym wszystkie te stwierdzenia są prawdziwe, zostawimy jako ćwiczenie dla zainteresowanego czytelnika, wspomagane jeszcze jednym wzorem algebraicznym: u = ci ( x XOR y ) + ci ′ ( x XOR y ) )′]′. Oddzielenie propagacji przeniesienia od tworzenia sumy w ten sposób podnosi wydajność sumatora przeniesienia wyprzedzającego w porównaniu z sumatorem przeniesienia tętnienia .
Zastosowanie w projektowaniu obwodów cyfrowych
Jednym z zastosowań algebry Boole'a jest projektowanie obwodów cyfrowych, którego jednym celem jest zminimalizowanie liczby bramek, a drugim zminimalizowanie czasu ustalania.
Istnieje szesnaście możliwych funkcji dwóch zmiennych, ale w sprzęcie logiki cyfrowej najprostsze obwody bramek implementują tylko cztery z nich: koniunkcję (AND), dysjunkcję (włącznie z OR) i odpowiednie ich uzupełnienia (NAND i NOR).
Większość obwodów bramek akceptuje więcej niż 2 zmienne wejściowe; na przykład kosmiczny komputer nawigacyjny Apollo , który był pionierem w stosowaniu układów scalonych w latach 60. XX wieku, został zbudowany tylko z jednym typem bramki, 3-wejściowym NOR, którego wyjście jest prawdziwe tylko wtedy, gdy wszystkie 3 wejścia są fałszywe. [ potrzebna strona ]
Zobacz też
Dalsza lektura
-
Bender, Edward A.; Williamson, S. Gill (2005). Krótki kurs matematyki dyskretnej . Mineola, NY: Dover Publications, Inc. ISBN 0-486-43946-1 .
Autorzy przedstawiają dowód na to, że dowolną funkcję boolowską (logiczną) można wyrazić w postaci normalnej rozłącznej lub koniunkcyjnej (por. strony 5–6); dowód po prostu przebiega przez utworzenie wszystkich 2 N wierszy N zmiennych boolowskich i pokazuje, że każdy wiersz („minterm” lub „maxterm”) ma unikalne wyrażenie boolowskie. Dowolną funkcję boolowską N zmiennych można wyprowadzić ze złożenia wierszy, których minterm lub maxterm to logiczne jedynki („trues”) -
McCluskey, EJ (1965). Wprowadzenie do teorii obwodów przełączających . NY: McGraw-Hill Book Company. P. 78. LCCN 65-17394 .
Zdefiniowano i opisano wyrażenia kanoniczne
-
Hill, Fredrick J.; Petersona, Geralda R. (1974). Wprowadzenie do teorii przełączania i projektowania logicznego (wyd. 2). Nowy Jork: John Wiley & Sons. P. 101. ISBN 0-471-39882-9 .
Minterm i maxterm wyznaczanie funkcji
Linki zewnętrzne
- Boole, George (1848). Przetłumaczone przez Wilkinsa, Davida R. „Rachunek logiczny” . Cambridge i Dublin Mathematical Journal . III : 183–198.