Direkt zum Inhalt

Lexikon der Mathematik: funktionale Dekomposition einer Booleschen Funktion

Zerlegung einer Booleschen Funktion f : {0, 1}n → {0,1} in der Form \begin{align} & f(x_{1},\ldots,x_{n})=g(\alpha(x_{i_{1}},\ldots,x_{i_{p}}),\beta(x_{i_{p+1}},\ldots,x_{i_{n}})). \end{align} Hierbei ist {{xi1, …,xip},{xip+1, …, xin}} eine Partition der Menge der Booleschen Variablen von f mit 1 ≤ pn − 1, α : {0, 1}p → {0, 1}r, β : {0, 1}n−p → {0, 1}s und g : {0,1}r+s → {0, 1}. Die Booleschen Funktionen α und β heißen Zerlegungsfunktionen, die Boolesche Funktion g Zusammensetzungsfunktion der Zerlegung.

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos