Espresso heuristische logische minimalisator: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Link naar Engels Wikipedia-pagina heeft dezelfde status als andere literatuurverwijzing en is waardevol |
k →Klassieke minimalisatiemethoden: zo optimaal mogelijk => optimaal |
||
Regel 30:
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 6 variabelen, terwijl de praktische uitvoerbaarheid gelimiteerd is tot maximaal 4 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)
Hoewel dit [[Quine-McCluskey algoritme]] uitstekend geschikt is voor implementatie in een computerprogramma, is het resultaat toch 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.
| |||