Espresso heuristische logische minimalisator: verschil tussen versies

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.

 

 

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.