Espresso heuristische logische minimalisator: verschil tussen versies

Een radicaal verschillende aanpak voor dit probleem wordt gevolgd bij het ESPRESSO-algoritme, ontwikkeld aan de University of California, Berkeley. In plaats van een functie te expanderen in mintermen, worden door het programma iteratief z.g. "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.

 

 

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 meerlaags logica 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) or an ASIC (Application Specific Integrated Circuit) betreft.