Kanonická normální forma - Canonical normal form

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek je tón nebo styl nemusí odrážet encyklopedický tón použitý na Wikipedii. Viz Wikipedia průvodce psaním lepších článků pro návrhy. (Únor 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Kanonická normální forma“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Říjen 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek představuje neúplný pohled na předmět. (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v Booleova algebra, jakýkoli Booleovská funkce lze vložit do kanonická disjunktivní normální forma (CDNF)^[1] nebo minterm kanonická forma a jeho dvojí kanonická konjunktivní normální forma (CCNF) nebo maxterm kanonická forma. jiný kanonické formy zahrnout úplný součet hlavních implikantů nebo Blake kanonická forma (a jeho duální) a algebraická normální forma (také nazývaný Zhegalkin nebo Reed – Muller).

Minterms se nazývají produkty, protože jsou logické AND množiny proměnných a maxterms se nazývají součty, protože jsou logické NEBO množiny proměnných. Tyto koncepty jsou dvojí kvůli jejich vztahu komplementární symetrie, jak je vyjádřeno De Morganovy zákony.

Dvě duální kanonické formy žádný Booleovskou funkcí je „součet minterms“ a „produkt maxterms“. Termín "Součet produktů" (Úplatek nebo ÚPLATEK) je široce používán pro kanonickou formu, která je disjunkcí (OR) mintermů. Své De Morgan dual je "Součin součtů" (PoS nebo POS) pro kanonickou formu, která je spojkou (AND) maxtermů. Tyto formy mohou být užitečné pro zjednodušení těchto funkcí, což má velký význam při optimalizaci booleovských vzorců obecně a zejména digitálních obvodů.

souhrn

Jednou z aplikací booleovské algebry je návrh digitálních obvodů. Cílem může být minimalizace počtu bran, minimalizace doby usazení atd.

Existuje šestnáct možných funkcí dvou proměnných, ale v hardwaru digitální logiky nejjednodušší hradlové obvody implementují pouze čtyři z nich: spojení (A), disjunkce (včetně OR) a příslušné doplňky k nim (NAND a NOR).

Většina hradlových obvodů přijímá více než 2 vstupní proměnné; například vesmírný Naváděcí počítač Apollo, který byl průkopníkem v používání integrovaných obvodů v 60. letech, byl postaven pouze s jedním typem brány, třívstupovým NOR, jehož výstup je pravdivý pouze v případě, že jsou všechny 3 vstupy nepravdivé.^{[2][stránka potřebná ]}

Minterms

Pro booleovská funkce z ${ displaystyle n}$ proměnné ${ displaystyle {x_ {1}, dots, x_ {n}}}$, a výraz produktu ve kterém každý z ${ displaystyle n}$ se zobrazí proměnné jednou (v jeho doplněné nebo nekomplementované formě) se nazývá a minterm. Tak, a minterm je logickým vyjádřením n proměnné, které používají pouze doplněk provozovatel a spojení operátor.

Například, ${ displaystyle abc}$, ${ displaystyle ab'c}$ a ${ displaystyle abc '}$ jsou 3 příklady 8 minterms pro booleovskou funkci tří proměnných ${ displaystyle a}$, ${ displaystyle b}$, a ${ displaystyle c}$. Obvyklé čtení posledního z nich je a AND b AND NOT-c.

K dispozici jsou 2ⁿ mintermy z n proměnné, protože proměnná ve výrazu minterm může být buď v přímé, nebo v její komplementární formě - dvě možnosti na proměnnou.

Indexování minterms

Mintermy jsou často číslovány binárním kódováním doplňkového vzoru proměnných, kde jsou proměnné psány ve standardním pořadí, obvykle v abecedním pořadí. Tato konvence přiřadí hodnotu 1 přímému tvaru (${ displaystyle x_ {i}}$) a 0 do doplněného formuláře (${ displaystyle x '_ {i}}$); minterm je pak ${ displaystyle sum limity _ {i = 1} ^ {n} 2 ^ {i} operatorname {hodnota} (x_ {i})}$. Například minterm ${ displaystyle abc '}$ má číslo 110₂ = 6₁₀ a označil ${ displaystyle m_ {6}}$.

Funkční ekvivalence

Daná minterm n dává skutečnou hodnotu (tj. 1) pouze pro jednu kombinaci vstupních proměnných. Například minterm 5, A b' C, je pravda, pouze když A a C obě jsou pravdivé a b je nepravdivé - vstupní uspořádání, kde A = 1, b = 0, C = 1 má za následek 1.

Vzhledem k pravdivostní tabulka logické funkce je možné zapsat funkci jako „součet produktů“. Toto je speciální forma disjunktivní normální forma. Například pokud je dána pravdivostní tabulka pro bit aritmetického součtu u logiky polohy jednoho bitu sčítacího obvodu, jako funkce X a y z dodatků a přenášení, ci:

Pozorujeme, že řádky, které mají výstup 1, jsou 2., 3., 5. a 8., můžeme psát u jako součet minut ${ displaystyle m_ {1}, m_ {2}, m_ {4},}$ a ${ displaystyle m_ {7}}$. Pokud si to přejeme ověřit: ${ displaystyle u (ci, x, y) = m_ {1} + m_ {2} + m_ {4} + m_ {7} = (ci ', x', y) + (ci ', x, y' ) + (ci, x ', y') + (ci, x, y)}$ hodnoceno pro všech 8 kombinací tří proměnných bude odpovídat tabulce.

Maxterms

Pro booleovská funkce z n proměnné ${ displaystyle {x_ {1}, dots, x_ {n}}}$, souhrnné období, ve kterém každý z n se zobrazí proměnné jednou (v jeho doplněné nebo nekomplementované formě) se nazývá a maxterm. Tak, a maxterm je logickým vyjádřením n proměnné, které používají pouze doplněk provozovatel a disjunkce operátor. Maxtermy jsou duálem myšlenky mintermu (tj. Vykazují komplementární symetrii ve všech ohledech). Namísto použití AND a doplňků používáme OR a doplňky a postupujeme podobně.

Například následující jsou dvě z osmi maxtermů tří proměnných:

A + b′ + C

A′ + b + C

Jsou tu opět 2ⁿ maxterms of n proměnné, protože proměnná ve výrazu maxterm může být také v přímé nebo doplněné podobě - ​​dvě možnosti na proměnnou.

Indexování maxtermů

Každému maxtermu je přiřazen index založený na opačném konvenčním binárním kódování použitém pro mintermy. Konvence maxterm přiřadí hodnotu 0 přímému formuláři ${ displaystyle (x_ {i})}$ a 1 do doplněné formy ${ displaystyle (x '_ {i})}$. Například index 6 přiřadíme maxtermu ${ displaystyle a '+ b' + c}$ (110) a označte tuto maxterm jako M₆. Podobně M₀ těchto tří proměnných je ${ displaystyle a + b + c}$ (000) a M₇ je ${ displaystyle a '+ b' + c '}$ (111).

Funkční ekvivalence

Je zřejmé, že maxterm n dává Nepravdivé hodnota (tj. 0) pouze pro jednu kombinaci vstupních proměnných. Například maxterm 5, A′ + b + C′, Je nepravdivé, pouze když A a C oba jsou pravdivé a b je nepravdivé - vstupní uspořádání, kde a = 1, b = 0, c = 1 vede k 0.

Pokud je dáno a pravdivostní tabulka logické funkce je možné funkci napsat jako „součin součtů“. Toto je speciální forma konjunktivní normální forma. Například pokud je uvedena pravdivostní tabulka pro prováděcí bit co logiky polohy jednoho bitu sčítacího obvodu, jako funkce X a y z dodatků a přenášení, ci:

Pozorujeme, že řádky, které mají výstup 0, jsou 1., 2., 3. a 5., můžeme psát co jako produkt maxterms ${ displaystyle M_ {0}, M_ {1}, M_ {2}}$ a ${ displaystyle M_ {4}}$. Pokud si to přejeme ověřit:

${ displaystyle co (ci, x, y) = M_ {0} M_ {1} M_ {2} M_ {4} = (ci + x + y) (ci + x + y ') (ci + x' + y) (ci '+ x + y)}$

hodnoceno pro všech 8 kombinací tří proměnných bude odpovídat tabulce.

Dualizace

Doplňkem minterm je příslušná maxterm. To lze snadno ověřit pomocí de Morganův zákon. Například:${ displaystyle M_ {5} = a '+ b + c' = (ab'c) '= m_ {5}'}$

Nekanonické formuláře PoS a SoP

Často je možné, že kanonický mintermový formulář lze zjednodušit na ekvivalentní SoP formulář. Tato zjednodušená forma by stále sestávala ze součtu výrazů produktu. Ve zjednodušené formě je však možné mít méně výrazů produktů a / nebo výrazů produktů, které obsahují méně proměnných. Například následující funkce 3 proměnných:

má kanonické mintermální zastoupení:${ displaystyle f = a'bc + abc}$, ale má ekvivalentní zjednodušenou formu:${ displaystyle f = bc}$V tomto triviálním příkladu je zřejmé, že ${ displaystyle bc = a'bc + abc}$, ale zjednodušená forma má jak méně produktových termínů, tak termín má méně proměnných. Nejjednodušší SoP reprezentace funkce se označuje jako minimální formulář SoP.

Podobným způsobem může mít kanonický maxterm formulář zjednodušený formulář PoS.

Zatímco tento příklad byl snadno zjednodušen použitím běžných algebraických metod [${ displaystyle f = (a '+ a) bc}$], v méně zjevných případech je vhodnou metodou pro nalezení minimální formy PoS / SoP funkce s až čtyřmi proměnnými použití Karnaugh mapa.

Minimální formy PoS a SoP jsou velmi důležité pro nalezení optimální implementace booleovských funkcí a pro minimalizaci logických obvodů.

Příklad aplikace

Ukázkové pravdivostní tabulky pro mintermy a maxtermy výše jsou dostatečné k vytvoření kanonického tvaru pro pozici jednoho bitu s přidáním binárních čísel, ale nestačí k návrhu digitální logiky, pokud váš inventář bran nezahrnuje AND a OR. Tam, kde je problémem výkon (jako v počítači Apollo Guidance Computer), je pravděpodobné, že dostupné části budou NAND a NOR kvůli doplňkové akci vlastní logice tranzistoru. Hodnoty jsou definovány jako napěťové stavy, jeden v blízkosti země a druhý v blízkosti stejnosměrného napájecího napětí V_cc, např. +5 V ss. Pokud je vyšší napětí definováno jako hodnota 1 „true“, je brána NOR nejjednodušším možným užitečným logickým prvkem.

Konkrétně brána NOR se 3 vstupy se může skládat ze 3 bipolárních spojovacích tranzistorů s uzemněnými vysílači, s kolektory spojenými dohromady a spojenými s V_cc přes impedanci zátěže. Každá základna je připojena ke vstupnímu signálu a společný kolektorový bod představuje výstupní signál. Jakýkoli vstup, který má na své základně 1 (vysoké napětí), zkratuje emitor tranzistoru na jeho kolektor, což způsobí, že proud protéká impedancí zátěže, což přivádí napětí kolektoru (výstup) velmi blízko k zemi. Tento výsledek je nezávislý na ostatních vstupech. Pouze když jsou všechny 3 vstupní signály 0 (nízké napětí), zůstávají impedance emitoru a kolektoru všech 3 tranzistorů velmi vysoké. Pak teče velmi málo proudu a efekt děliče napětí s impedancí zátěže ukládá na kolektorový bod vysoké napětí velmi blízko V_cc.

Vlastnost doplňování těchto obvodů brány se může zdát jako nevýhoda při pokusu o implementaci funkce v kanonické podobě, ale existuje kompenzační bonus: taková brána s jediným vstupem implementuje doplňkovou funkci, která je v digitální logice často vyžadována.

Tento příklad předpokládá inventář dílů Apollo: pouze 3-vstupní NOR brány, ale diskuse je zjednodušena za předpokladu, že jsou k dispozici také 4-vstupní NOR brány (v Apollu, ty byly složeny z párů 3-vstupních NOR).

Kanonické a nekanonické důsledky bran NOR

Fakt # 1: sada 8 bran NOR, pokud jsou jejich vstupy všechny kombinace přímých a doplňkových forem 3 vstupních proměnných ci, x, a y, vždy vytvářejte mintermy, nikdy maxtermy - tj. z 8 bran potřebných ke zpracování všech kombinací 3 vstupních proměnných, pouze jedna má výstupní hodnotu 1. Je to proto, že bránu NOR lze přes její název lépe zobrazit (pomocí De Morganův zákon) jako AND doplňků jeho vstupních signálů.

Fakt č. 2: Důvodem, proč Fakta č. 1 není problémem, je dualita mintermů a maxtermů, tj. Každá maxterm je doplňkem obdobně indexované mintermy a naopak.

Ve výše uvedeném příkladu jsme psali ${ displaystyle u (ci, x, y) = m_ {1} + m_ {2} + m_ {4} + m_ {7}}$ ale abychom to mohli provést pomocí brány NOR se 4 vstupy, musíme to přepracovat jako součin součtů (PoS), kde součty jsou opačné maxtermy. To znamená

${ displaystyle u (ci, x, y) = mathrm {AND} (M_ {0}, M_ {3}, M_ {5}, M_ {6}) = mathrm {NOR} (m_ {0}, m_ {3}, m_ {5}, m_ {6}).}$

Ve výše uvedeném příkladu maxterm jsme psali ${ displaystyle co (ci, x, y) = M_ {0} M_ {1} M_ {2} M_ {4}}$ ale abychom to mohli provést pomocí brány NOR se 4 vstupy, musíme si všimnout rovnosti NOR se stejnými mintermy. To znamená

${ displaystyle co (ci, x, y) = mathrm {AND} (M_ {0}, M_ {1}, M_ {2}, M_ {4}) = mathrm {NOR} (m_ {0}, m_ {1}, m_ {2}, m_ {4}).}$

Kromě kanonických forem se zvažují i ​​kompromisy designu

Dalo by se předpokládat, že práce na návrhu fáze sčítače je nyní dokončena, ale my jsme se nezabývali skutečností, že všechny 3 vstupní proměnné se musí objevit v přímé i doplňkové formě. S doplňky není žádný problém X a y v tomto ohledu proto, že jsou statické po celou dobu sčítání, a proto jsou normálně drženy v západkových obvodech, které běžně mají přímé i doplňkové výstupy. (Nejjednodušší západkový obvod vyrobený z bran NOR je dvojice bran vzájemně propojených, aby se vytvořil klopný obvod: výstup každého z nich je zapojen jako jeden ze vstupů do druhého.) Není také nutné vytvářet formu doplňku částky u. Provedení jedné bitové pozice však musí být předáno jako přenesení do další bitové pozice v přímé i komplementární formě. Nejpřímější způsob, jak toho dosáhnout, je projít co prostřednictvím brány NOR s 1 vstupem a označte výstup co′, Ale to by přidalo zpoždění brány na nejhorším možném místě a zpomalilo vlnění nosítek zprava doleva. Další brána NOR se 4 vstupy vytvářející kanonickou podobu co′ (Z opačných mintermů jako co) tento problém řeší.

${ displaystyle co '(ci, x, y) = mathrm {AND} (M_ {3}, M_ {5}, M_ {6}, M_ {7}) = mathrm {NOR} (m_ {3} , m_ {5}, m_ {6}, m_ {7}).}$

Kompromis pro udržení plné rychlosti tímto způsobem zahrnuje neočekávané náklady (kromě nutnosti použít větší bránu). Kdybychom právě použili tuto 1-vstupní bránu k doplnění co, pro minterm by to nebylo k ničemu ${ displaystyle m_ {7}}$a brána, která ji vygenerovala, mohla být odstraněna. Přesto je to stále dobrý obchod.

Nyní bychom mohli implementovat tyto funkce přesně podle jejich kanonických forem SoP a PoS, a to tak, že se brány NOR změní na zadané funkce. Z brány NOR je brána OR tím, že její výstup prochází bránou NOR s jedním vstupem; a je vytvořen do brány AND průchodem každého ze svých vstupů přes bránu NOR s 1 vstupem. Tento přístup však nejen zvyšuje počet použitých bran, ale také zdvojnásobuje počet zpoždění brány při zpracování signálů a snižuje rychlost zpracování na polovinu. Následně, kdykoli je výkon zásadní, jít za hranice kanonických forem a dělat booleovskou algebru, aby nezvýšené brány NOR dělaly práci, stojí za to.

Design shora dolů vs. zdola nahoru

Nyní jsme viděli, jak lze nástroje minterm / maxterm použít k návrhu fáze sčítače v kanonické podobě s přidáním nějaké booleovské algebry, která stojí jen 2 zpoždění brány pro každý z výstupů. To je způsob „shora dolů“, jak navrhnout digitální obvod pro tuto funkci, ale je to nejlepší způsob? Diskuse se zaměřila na identifikaci slova „nejrychlejší“ jako „nejlepšího“ a rozšířená kanonická forma splňuje toto kritérium bezchybně, ale někdy převládají jiné faktory. Projektant může mít primární cíl minimalizovat počet bran a / nebo minimalizovat rozdvojení signálů do ostatních bran, protože velké rozdvojení snižují odolnost vůči degradovanému napájení nebo jiným faktorům prostředí. V takovém případě může návrhář vyvinout návrh kanonické formy jako základ, poté zkusit vývoj zdola nahoru a nakonec porovnat výsledky.

Vývoj zdola nahoru zahrnuje všimnutí si toho u = ci XOR (X XOR y), kde XOR znamená EXKLUZIVNÍ OR [true, když je jeden vstup pravdivý, ale ne, když jsou oba pravdivé], a to co = ci x + x y + y ci. Jeden takový vývoj vyžaduje celkem dvanáct bran NOR: šest bran se 2 vstupy a dvě brány s 1 vstupy u v 5 zpožděných branách, plus tři 2-vstupní brány a jedna 3-vstupní brána k výrobě co′ Ve 2 zpožděních brány. Kanonická základní čára vyprodukovala osm 3-vstupních bran NOR plus tři 4-vstupní brány NOR u, spol a co′ Ve 2 zpožděních brány. Pokud inventář obvodů ve skutečnosti zahrnuje brány NOR se 4 vstupy, kanonický design shora dolů vypadá jako vítěz v počtu bran i rychlosti. Ale pokud (na rozdíl od našeho pohodlného předpokladu) jsou obvody ve skutečnosti 3-vstupní brány NOR, z nichž jsou pro každou funkci NOR se 4 vstupy vyžadovány dvě, pak kanonický návrh trvá 14 bran ve srovnání s 12 pro přístup zdola nahoru, ale stále vytváří číslici součtu u podstatně rychlejší. Porovnání fanout je uvedeno v tabulce jako:

Co je třeba udělat s rozhodovací pravomocí? Pozorný si všiml, že popis vývoje zdola nahoru zmiňuje co′ Jako výstup, ale ne co. Vyžaduje tento design jednoduše nikdy přímou formu provedení? No, ano a ne. V každé fázi je výpočet co′ Záleží jen na ci′, X' a y′, Což znamená, že šíření přenosu se vlní podél bitových pozic stejně rychle jako v kanonickém designu, aniž by se někdy vyvíjel co. Výpočet u, což vyžaduje ci být vyroben z ci′ Pomocí 1-vstupního NOR, je pomalejší, ale pro jakoukoli délku slova design zaplatí tento trest pouze jednou (když je vyvinuta číslice součtu nejvíce vlevo). Je to proto, že se tyto výpočty překrývají, každý v tom, co se rovná jeho vlastnímu malému kanálu, aniž by to ovlivnilo, kdy lze vypočítat součet bitů další bitové pozice. A pro jistotu co′ Z pozice nejvíce vlevo bit bude pravděpodobně nutné doplnit jako součást logiky určující, zda přetečení přetečelo. Ale s použitím 3-vstupových bran NOR je design zdola nahoru téměř tak rychlý pro paralelní sčítání na netriviální délce slova, snižuje počet bran a používá nižší fanouty ... takže vyhraje, pokud počet bran a / nebo fanout jsou prvořadé!

Přesné obvody designu zdola nahoru, u nichž jsou všechny tyto výroky pravdivé, ponecháme jako cvičení pro zainteresovaného čtenáře, kterému pomůže ještě jeden algebraický vzorec: u = ci(X XOR y) + ci′(X XOR y) ′] ′. Tímto způsobem odděluje šíření přenosu od tvorby součtu to, co zvyšuje výkon a carry-lookahead zmije přes to a zvlnění nést zmije.

Chcete-li vidět, jak byla logika brány NOR použita v ALU Apollo Guidance Computer, navštivte http://klabs.org/history/ech/agc_schematics/index.htm, vyberte libovolnou položku 4-BIT MODULU v rejstříku výkresů a podle potřeby obrázky rozbalte.

Viz také

• Seznam témat booleovské algebry

Reference

Další čtení

• Bender, Edward A .; Williamson, S. Gill (2005). Krátký kurz diskrétní matematiky. Mineola, NY: Dover Publications, Inc. ISBN  0-486-43946-1.
  Autoři prokazují, že jakoukoli booleovskou (logickou) funkci lze vyjádřit buď v disjunktivní, nebo konjunktivní normální formě (srov. Strany 5–6); důkaz jednoduše pokračuje vytvořením všech 2^N řádky N Booleovské proměnné a ukazuje, že každý řádek („minterm“ nebo „maxterm“) má jedinečný logický výraz. Libovolná booleovská funkce N proměnné lze odvodit ze složených řádků, jejichž minterm nebo maxterm jsou logické 1 s („trues“)
• McCluskey, E. J. (1965). Úvod do teorie spínacích obvodů. NY: McGraw – Hill Book Company. str. 78. LCCN  65-17394. Jsou definovány a popsány kanonické výrazy
• Hill, Fredrick J .; Peterson, Gerald R. (1974). Úvod do teorie přepínání a logického designu (2. vyd.). NY: John Wiley & Sons. str. 101. ISBN  0-471-39882-9. Minterm a maxterm označení funkcí

externí odkazy

• Boole, Georgi (1848). Přeložil Wilkins, David R. „Logický kalkul“. Cambridge a Dublin Mathematical Journal. III: 183–198.