1. Vad ett Karnaughdiagram är
Ett Karnaughdiagram är en sanningstabell omritad som ett rutnät. Maurice Karnaugh presenterade det på Bell Labs 1953 som ett sätt att förenkla kopplingsnät med ögat, och det är fortfarande det snabbaste sättet att minimera en liten boolesk funktion för hand: ingen algebra, inga lagar att minnas, bara rektanglar.
Varje ruta i diagrammet rymmer en rad ur sanningstabellen. Det som gör diagrammet till mer än en omflyttning är ordningen raderna står i: rutor som ligger intill varandra skiljer sig i exakt en variabel.
Den enda egenskapen gör hela arbetet. Om två grannrutor båda är sanna kan variabeln som ändras mellan dem inte vara det som gör uttrycket sant: den faller bort, och en enda term täcker båda rutorna. Att förenkla blir en fråga om att rita de största rektanglar man kan.
2. Varför kolumnerna ser felsorterade ut
Kolumnerna i ett Karnaughdiagram räknar inte 00, 01, 10, 11. De går 00, 01, 11, 10 - reflekterad Gray-kod, en ordning där varje värde skiljer sig från nästa i en enda bit. Binär räkning skulle sätta 01 bredvid 10, som skiljer sig i två bitar, och då skulle grannrutor inte säga någonting.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Kanterna är också grannar. Första och sista kolumnen skiljer sig i en variabel, och detsamma gäller översta och nedersta raden, så en grupp får löpa ut över en kant och fortsätta på den andra - därför bildar de fyra hörnen i ett diagram med fyra variabler en enda grupp. Ett Karnaughdiagram är i själva verket ritat på en torus; det platta arket är en bekvämlighet.
3. Att gruppera ettorna
För att läsa av en minimal summa av produkter täcker du varje ruta med en etta med rektangulära grupper, enligt fyra regler:
- En grupp är en rektangel om 1, 2, 4, 8 … rutor - en tvåpotens längs varje sida.
- En grupp får gå runt diagrammets kanter, vågrätt, lodrätt eller båda.
- Grupper får överlappa. En ruta som täcks två gånger kostar ingenting; en ruta som lämnas otäckt ändrar funktionen.
- Gör varje grupp så stor den kan bli, och använd sedan så få grupper som täcker alla ettor.
Varje grupp blir en term. Du läser av den genom att fråga vilka variabler som är desamma i hela gruppen: de står i termen - oförändrade där de är 1, negerade där de är 0 - och varje variabel som ändras faller bort. En grupp om två rutor förlorar en variabel, en om fyra förlorar två, en om åtta förlorar tre. Det minimala uttrycket är disjunktionen av termerna.
4. Ett genomräknat exempel
Ta (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Diagrammet har fyra variabler: A och B i raderna, C och D i kolumnerna.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Två grupper täcker alla ettor. Den ena är blocket om fyra rutor i de två rader där A = 0 och de två kolumner där C = 1: både B och D ändras inuti det, så de faller bort och termen är ¬A ∧ C. Den andra är hela raden där A och B båda är 1, tvärs över alla fyra kolumner: C och D ändras längs den, och kvar blir A ∧ B.
Den minimala formen är alltså (¬A ∧ C) ∨ (A ∧ B). Den tredje termen i originalet, B ∧ C ∧ D, har försvunnit: varje ruta den täckte var redan täckt av någon av de två grupperna. Så ser absorption ut när man kan se den.
5. Primimplikatorer och väsentliga implikatorer
En grupp som inte kan göras större kallas primimplikator. Att lista primimplikatorerna är problemets lätta halva; att välja vilka som ska behållas är den halva som går fel.
Om en ruta täcks av bara en enda primimplikator är den implikatorn väsentlig: ingen minimal form kan utelämna den, eftersom inget annat täcker den rutan. Ta de väsentliga implikatorerna först och täck sedan det som är kvar med så få av de återstående grupperna som möjligt.
Att vara girig - att gång på gång ta den största grupp som återstår - är frestande och fungerar inte alltid. På ett cykliskt schema, där ingen implikator är väsentlig och varje ruta täcks två gånger, kan det giriga valet sluta en term längre än det bästa svaret. Diagrammet på den här webbplatsen söker i stället igenom alla återstående val, vilket vid fyra variabler inte kostar något.
6. Att gruppera nollorna i stället
Allt ovanstående fungerar lika bra på nollorna. Täck dem med samma rektanglar, läs varje grupp med negerade literaler - en variabel som är 1 i hela gruppen står negerad, en som är 0 står oförändrad - och foga samman grupperna med ∧ i stället för ∨.
Resultatet är en produkt av summor: en konjunktion av disjunktioner som är falsk i exakt de rutor där uttrycket är falskt, och därmed sann överallt annars. Vilken av formerna som är kortast beror på funktionen - en formel med få ettor har en kort summa av produkter, en med få nollor en kort produkt av summor - så det lönar sig att läsa av båda innan man väljer.
7. Större diagram och don't care-rutor
Fem och sex variabler kan ritas som två eller fyra fyravariabeldiagram staplade på varandra, där rutor på samma plats i intilliggande lager räknas som grannar. Det fungerar, men den grannskap som gjorde metoden synlig är nu något att minnas snarare än att se. Bortom det gör Quine-McCluskeys algoritm samma jobb i tabellform: den är den mekaniska formen av precis denna gruppering, och det är den som kör bakom diagrammen här.
Hårdvarukonstruktion lägger till ännu en idé. Vissa indatakombinationer inträffar aldrig - en binärkodad decimalsiffra är aldrig 1010 - så konstruktören bryr sig inte om vad kretsen gör med dem. De rutorna märks med X och får läsas som vilket värde som helst, det som gör grupperna större. Diagrammen i den här räknaren byggs ur en formel, som ger varje tilldelning ett värde, så ingen ruta är någonsin ett don't care.
8. Prova själv
Skriv ett uttryck med två till fyra variabler i räknaren, så ritas diagrammet under sanningstabellen med varje grupp inringad i sin egen färg och den minimala formen utskriven under. Byt till produkt av summor för att se nollorna grupperade i stället.