5- en 6-Variabele Karnaugh-kaarten Beheersen voor Efficiënt Logica-Ontwerp

Naarmate combinatorische logica groeit, vergroot de grootte van de Karnaugh-kaart. Weten wanneer een 5- of 6-variabele kaart geschikt is – en hoe de cellen te interpreteren en te groeperen – kan logica-gebruik drastisch reduceren in FPGA en ASIC ontwerpen.

Altera (nu onderdeel van Intel) analyseerde duizenden klantontwerpen om typische fan-in groottes te begrijpen. De resulterende verdeling was bijna plat van twee tot zes invoeren, met een duidelijke piek bij vijf. In de praktijk gebruiken de meeste schakelingen maximaal zes invoeren, en het gemiddelde ontwerp past comfortabel binnen vijf.

Altera's eigen data, geëxtraheerd uit de bibliotheek van klantontwerpen, ondersteunt de waarde van heterogeniteit. Door logische kegels te onderzoeken, ze op LUT-gebaseerde knopen af te beelden, en ze te sorteren op het aantal invoeren dat het best zou zijn op elke knoop, ontdekte Altera dat de verdeling van fan-ins bijna plat was tussen twee en zes invoeren, met een mooie piek bij vijf.

Hieronder is een klassieke vijf-variabele Karnaugh-kaart.

Vijf Variabele K-map (Reflectie Kaart)

De oudere reflectiestijl labelt de bovenkant (en voor een 6-variabele kaart, de zijkant) van de kaart met volledige Gray-code. De Gray-code wordt gespiegeld rond het centrum van de kaart – een conventie die in veel klassieke teksten gevonden wordt. Een nieuwere, voorkeurslayout wordt hieronder getoond.

Overlay Versie van de K-map

De overlay-kaart bestaat uit twee identieke 4-cel submappen, alleen onderscheiden door de meest-significante bit van het 3-bit adres bovenaan. De nummering verschilt van de reflectiekaart: als de meest-significante digit genegeerd wordt, verschijnt de reeks 00, 01, 11, 10 in beide submappen. De acht-bit reeks is geen Gray-code, maar het twee-bit achtervoegsel 01, 10 wel.

Laten we de vijf-variabele kaart toepassen op een echt probleem: ontwerp een schakeling die een 5-bit binaire invoer (A = MSB, B, C, D, E) accepteert en een logische HOOG uitvoert wanneer het binaire getal een priemgetal is.

De priemgetallen binnen het 5-bit bereik zijn (1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Markeer een 1 in elke corresponderende cel, groepeer dan de enen. Eindig met het schrijven van de vereenvoudigde expressie.

In de reflectiekaart beslaat de 4-cel groep A'B'E twee spiegelsparen, terwijl de 2-cel groep AB'DE verschijnt als een gespiegelde paar. Bij gebruik van de overlay-kaart, zoek naar spiegelafbeeldingen over de twee helften.

Uit = A'B'E + B'C'E + A'CDE + A'CD'E + ABCE + AB'DE + A'B'C'D

Hieronder is de overlay-versie van dezelfde expressie.

Bij het vergelijken van de twee kaarten, verschuiven sommige cellen omdat het adresseringsschema verschilt. Het overlappen van de ene helft op de andere onthult overlappende groepen die vereenvoudiging leiden. Bijvoorbeeld, de 4-cel groep A'B'E dekt het patroon ABCDE = 00xx1, wat betekent dat A, B, en E vastliggen op 0,0,1 respectievelijk terwijl C en D varieren.

Een voorbeeld van een zes-variabele Karnaugh-kaart volgt. Door de vier submappen mentaal te stapelen, kunnen we een 4-cel groep identificeren die Uit = C'F' implementeert.

Om de 6-variabele kaart te illustreren, bekijken we een 3-bit groottevergelijker die drie uitgangen produceert: gelijk, groter-dan, en kleiner-dan. De vergelijker neemt twee 3-bit invoeren A₂A₁A₀ en B₂B₁B₀. Voor de eenvoud lossen we alleen de A > B uitgang op.

6-Variabele K-map

De overlay-kaart hieronder helpt bij het vereenvoudigen van de logica voor de A > B uitgang van een 3-bit vergelijker. De binaire adrescode bovenaan en aan de linkerkant is geen volledige 3-bit Gray-code, maar de 2-bit codes van elk van de vier submappen zijn Gray.

Waar ABC XYZ overschrijdt, wordt een 1 geplottet. De kaart wordt dienovereenkomstig gevuld.

Groepering volgt deze richtlijnen:

• Eén groep van 16 cellen
• Twee groepen van 8 cellen
• Vier groepen van 4 cellen

De 16-cel groep AX' bezit de rechter-onder submapt. Twee 8-cel groepen worden gevormd door identieke 4-cel patronen van de boven- en ondersubmaps te overlappen. Vier 4-cel groepen verschijnen in de kaart; elk levert een productterm op. De finale Som-van-Producten reductie bevat zeven termen.

Het tellen van de 1's, er zijn 28 enen. Voor reductie zou de SOP 28 producttermen van zes invoeren elk bevatten. De K-map vouwt dit in tot zeven producttermen van vier of minder invoeren – een dramatische vereenvoudiging.

Het bedradingsdiagram wordt weggelaten, maar hier is de onderdelenlijst voor een 3-bit groottevergelijker (A > B) met 4-TTL logica-familie componenten:

• 1 × 7410 triple 3-invoers NAND-poort (AX', ABY', BX'Y')
• 2 × 7420 dual 4-invoers NAND-poort (ABCZ', ACY'Z', BCX'Z', CX'Y'Z')
• 1 × 7430 8-invoers NAND-poort (voor de finale 7-term uitgang)

Samenvatting

• Boolesche algebra, Karnaugh-kaarten, en CAD zijn essentiële tools voor logica vereenvoudiging.
• Een minimale-kosten oplossing gebruikt de minste poorten met de minste invoeren.
• Venndiagrammen helpen Boolesche expressies visualiseren voordat ze vertaald worden naar K-maps.
• K-map cellen zijn georganiseerd in Gray-code, wat redundanties onthult die vereenvoudiging mogelijk maken.
• Som-van-Producten (SOP) expressies worden typisch geïmplementeerd als EN-poorten die een enkele OF-poort voeden.
• SOP kan gerealiseerd worden met NAND-NAND logica door EN's en OF's te vervangen door NAND's.
• Product-van-Sommen (POS) is minder algemeen maar kan geïmplementeerd worden met OF-poorten die een enkele EN-poort voeden, gebaseerd op de kaart's 0's (maxtermen).