Espresso heuristische logische minimalisator

De Espresso heuristische logische minimalisator is een wijd verspreid computerprogramma voor het efficiënt reduceren van de complexiteit van digitale elektronische poortschakelingen. Minilog is een publicdomainprogramma, deel uitmakend van het Publicad-educatieve ontwerppakket, waarin gebruik wordt gemaakt van dit algoritme.

Ontwerp van digitale schakelingen bewerken

Elk digitaal systeem is opgebouwd uit twee elementaire basisfuncties: geheugenelementen om informatie in op te slaan en combinatorische poortschakelingen om die informatie te bewerken. Statusmachines, zoals tellers, zijn niets anders dan een combinatie van geheugenelementen en combinatorische poortschakelingen. Aangezien geheugenelementen standaardcomponenten zijn, die worden geselecteerd uit een beperkt repertoire, komt het ontwerp van digitale systemen in essentie neer op het implementeren van de combinatorische poortschakelingen van de basisbouwstenen en het onderling verbinden van al die bouwstenen.

In het algemeen wordt de implementatie van poortschakelingen aangeduid als logische synthese, die weliswaar met de hand kan worden uitgevoerd, maar in de regel wordt overgelaten aan een of andere vorm van ontwerpsoftware op een computer.

De beginsituatie bij het ontwerp van een logische poortschakeling is de vereiste functionaliteit, afgeleid uit de analyse van het gedrag van het systeem in zijn geheel, waarvan de schakeling deel uit gaat maken. De beschrijving ervan kan geschieden in een algoritmische vorm of met behulp van logische vergelijkingen, maar kan ook de vorm van een tabel aannemen. Het onderstaande voorbeeld laat een deel van zo’n tabel zien voor een zevensegmentendisplay-driver, die de binaire code voor de waarden van een decimaal getal omzet naar de signalen die de respectievelijke segmenten van het display doen oplichten.

  Getal  Code      Segmenten A-G
    0    0000      1 1 1 1 1 1 0          -A-
    1    0001      0 1 1 0 0 0 0         F   B
    2    0010      1 1 0 1 1 0 1         |-G-|
    3    0011      1 1 1 1 0 0 1         E   C
    .    ....      . . . . . . .          -D-

Het realisatietraject begint met een hieronder te beschrijven logische minimalisatie-fase, teneinde te functietabel zo veel mogelijk te vereenvoudigen door de afzonderlijke termen te combineren tot een groter geheel dat minder variabelen bevat.

Vervolgens wordt het minimalisatieresultaat opgesplitst in kleinere, afzonderlijk te realiseren delen door een factorisatieprocedure en uiteindelijk samengesteld uit de beschikbare logische basispoorten die binnen de toe te passen technologie beschikbaar zijn. Deze bewerking wordt wel aangeduid als logische optimalisatie.

Klassieke minimalisatiemethoden bewerken

Het met de hand minimaliseren van booleaanse functies met behulp van het welbekende Karnaugh-diagram is een tijdrovende, saaie en foutgevoelige bewerking. Deze is niet geschikt voor meer dan zes variabelen, terwijl de praktische uitvoerbaarheid gelimiteerd is tot maximaal vier variabelen. Het gemeenschappelijk gebruik van producttermen bij functies met meerdere uitgangen (productterm sharing) is verder nog een orde van grootte lastiger. De methode is ten overvloede niet geschikt om te worden geautomatiseerd in de vorm van een computerprogramma. Aangezien hedendaagse logische functies in het algemeen niet begrensd zijn tot zo’n klein aantal variabelen, terwijl de kostprijs zowel als het risico van het maken van fouten in het ontwerp het handmatig implementeren van logische functies simpelweg niet toelaat, is het gebruik van computers onmisbaar geworden.

De eerste alternatieve methode die in zwang raakte was een tabellarische methode, ontwikkeld door Quine en McCluskey. In de waarheidstabel voor een aantal logische functies wordt gezocht naar een serie priemimplicanten, door de mintermen waarvoor de functies actief zijn (het ON-cover) of welke er niet toe doen (het Don’t Care-cover) optimaal te combineren. Ten slotte wordt een systematische procedure uitgevoerd om de kleinste set van priemimplicanten samen te stellen waarmee de uitgangsfuncties kunnen worden gerealiseerd.

Hoewel dit Quine-McCluskey-algoritme uitstekend geschikt is voor implementatie in een computerprogramma, is het resultaat verre van efficiënt in termen van rekentijd en geheugengebruik. Elke variabele waarmee de functie wordt uitgebreid leidt ruwweg tot een verdubbeling van beide omdat de lengte van de waarheidstabel exponentieel samenhangt met het aantal variabelen. Het uitbreiden van een functie met een extra uitgang veroorzaakt een vergelijkbaar probleem. Als gevolg hiervan is de methode van Quine-McCluskey in de praktijk alleen toepasbaar bij functies met een beperkt aantal ingangsvariabelen en uitgangsfuncties.

Het Espresso-algoritme bewerken

Een radicaal verschillende aanpak voor dit probleem wordt gevolgd bij het Espresso-algoritme, ontwikkeld aan de Universiteit van Californië - Berkeley. In plaats van een functie te expanderen in mintermen, worden door het programma iteratief zogenaamde "cubes" gemanipuleerd, waarmee de producttermen van de functie in het ON-, het OFF-, respectievelijk het DC-cover worden gerepresenteerd. Hoewel niet kan worden gegarandeerd dat het minimalisatieresultaat wordt gevormd door het globale minimum, wordt dit in de praktijk toch dicht benaderd en is de oplossing met zekerheid vrij van redundantie. Vergeleken met andere methoden is dit algoritme in essentiële mate efficiënter, waarbij het geheugengebruik en de rekentijd met orden van grootte zijn gereduceerd. Deze eigenschap wordt met de naam van het algoritme benadrukt door de vergelijking met het in een oogwenk zetten van een kopje verse koffie. In het algemeen vormen meerdere tientallen ingangsvariabelen in combinatie met tientallen uitgangsfuncties geen enkel probleem.

De invoer voor Espresso bestaat uit een functietabel van de bedoelde functionaliteit; het resultaat is een geminimaliseerde tabel die ofwel het ON-cover ofwel het OFF-cover bevat, afhankelijk van de ingestelde opties. Standaard worden de producttermen zo veel mogelijk gedeeld bij de verschillende uitgangsfucties, maar het programma kan worden geïnstrueerd om elk der uitgangsfuncties afzonderlijk af te handelen. Dit staat een efficiënte implementatie toe in tweelaags logische array’s zoals een PLA (Programmable Logic Array) of een PAL (Programmable Array Logic), waarvan bij de eerste het gebruik van gecombineerde producttermen mogelijk is, in tegenstelling tot bij de laatste.

Het Espresso-algoritme is zo succesvol gebleken dat het ingebouwd is als een standaard logische minimalisatiestap in zowat elke hedendaagse synthesesoftware. Bij de implementatie van een functie in meerlaagslogica wordt het minimalisatieresultaat geoptimaliseerd met een factorisatieprocedure alvorens deze op te bouwen uit de beschikbare logische basiscellen die in de toe te passen technologie beschikbaar zijn, onafhankelijk van of dit een FPGA (Field Programmable Gate Array) dan wel een ASIC (Application Specific Integrated Circuit) betreft.

Software bewerken

Voor niet-commerciële doeleinden kan het logische minimalisatieprogramma Minilog kosteloos worden gedownload. Als onderdeel van het Publicad-onderwijskundig ontwerppakket kan hiermee een tweelaags poortimplementatie worden gerealiseerd van een combinatorisch functieblok met maximaal 40 ingangen en uitgangen evenals een statusmachine met maximaal 256 toestanden. Indien het pakket is geïnstalleerd in combinatie met het ispLever ® FPGA-ontwerppakket van Lattice Semiconductor, kunnen leesbare poortschema’s worden gegenereerd, compleet met de bijbehorende symbolen, ter gebruik in een groter geheel. Met een VHDL-extractieprogramma wordt een pad geboden naar het simuleren en synthetiseren van een design in zijn geheel.

Referenties bewerken

Ir Wim de Valk, Leerboek ASIC’s - Digitale Systemen, HB-Uitgevers, 3e druk, 2002;
R.H. Katz, Contemporary Logic Design, The Benjamin/Cummings Publishing Company, 1994;
P.K. Lala, Practical Digital Logic Design and Testing, Prentice Hall, 1996;
R.K. Brayton e.a., Logic Minimization Algorithms for VHDL Synthesis, Kluwer Academic Publishers, 1984.

Zie ook bewerken

https://en.wikipedia.org/wiki/Logic_synthesis Engelstalig Wikipedia-artikel over logische synthese