Lexikon der Mathematik: funktionale Dekomposition einer Booleschen Funktion
Zerlegung einer Booleschen Funktion f : {0, 1}n → {0,1} in der Form
Ist r + s < n, so wird die Zerlegung nichttriviale funktionale Dekomposition genannt. Ist entweder α oder β die identische Abbildung, so heißt die Zerlegung einseitige funktionale Zerlegung.
Funktionale Dekompositionen Boolescher Funktionen werden im Rahmen der Logiksynthese kombinatorischer logischer Schaltkreise eingesetzt.
Können in jedem Schritt nichttriviale Zerlegungen berechnet werden, so kann das entsprechende Verfahren rekursiv auf die jeweiligen Zerlegungs- und Zusammensetzungsfunktionen angewendet werden, um so eine Realisierung über einer gegebenen vollständigen Bausteinbibliothek zu erhalten.
[1] Molitor, P.; Scholl, Chr.: Datenstrukturen und Effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen. B.G. Teubner Stuttgart-Leipzig, 1999.
Schreiben Sie uns!