Reed-Muller-Erweiterung - Reed–Muller expansion

In der Booleschen Logik ist eine Reed-Muller-Erweiterung (oder Davio-Erweiterung ) eine Zerlegung einer Booleschen Funktion .

Für eine Boolesche Funktion rufen wir auf ${\ displaystyle f (x_ {1}, \ ldots, x_ {n}): \ mathbb {B} ^ {n} \ to \ mathbb {B}}$

{\ displaystyle {\ begin {align} f_ {x_ {i}} (x) & = f (x_ {1}, \ ldots, x_ {i-1}, 1, x_ {i + 1}, \ ldots, x_ {n}) \\ f _ {{\ overline {x}} _ {i}} (x) & = f (x_ {1}, \ ldots, x_ {i-1}, 0, x_ {i + 1 }, \ ldots, x_ {n}) \ end {align}}}

die positiven und negativen Cofaktoren in Bezug auf und ${\ displaystyle f}$ ${\ displaystyle x_ {i}}$

{\ displaystyle {\ begin {align} {\ frac {\ partielle f} {\ partielle x_ {i}}} & = f_ {x_ {i}} (x) \ oplus f _ {{\ overline {x}} _ {i}} (x) \ end {align}}}

die boolesche Ableitung von in Bezug auf , wobei der XOR- Operator bezeichnet wird. ${\ displaystyle f}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ oplus}}$

Dann haben wir für die Reed- Muller- oder positive Davio-Erweiterung :

{\ displaystyle f = f _ {{\ overline {x}} _ {i}} \ oplus x_ {i} {\ frac {\ partielle f} {\ partielle x_ {i}}}.}

Beschreibung

Diese Gleichung ist so geschrieben, dass sie einer Taylor-Erweiterung von ungefähr ähnelt . Es gibt eine ähnliche Zerlegung, die einer Erweiterung über ( negative Davio-Erweiterung ) entspricht: ${\ displaystyle f}$ ${\ displaystyle x_ {i} = 0}$ ${\ displaystyle x_ {i} = 1}$

{\ displaystyle f = f_ {x_ {i}} \ oplus {\ overline {x}} _ {i} {\ frac {\ partielle f} {\ partielle x_ {i}}}.}

Die wiederholte Anwendung der Reed-Muller-Expansion führt zu einem XOR-Polynom in : ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

{\ displaystyle f = a_ {1} \ oplus a_ {2} x_ {1} \ oplus a_ {3} x_ {2} \ oplus a_ {4} x_ {1} x_ {2} \ oplus \ ldots \ oplus a_ {2 ^ {n}} x_ {1} \ cdots x_ {n}}

Diese Darstellung ist einzigartig und wird manchmal auch als Reed-Muller-Erweiterung bezeichnet.

ZB für das Ergebnis wäre ${\ displaystyle n = 2}$

{\ displaystyle f (x_ {1}, x_ {2}) = f _ {{\ overline {x}} _ {1} {\ overline {x}} _ {2}} \ oplus {\ frac {\ partielle f_ {{\ overline {x}} _ {2}}} {\ partielle x_ {1}}} x_ {1} \ oplus {\ frac {\ partielle f _ {{\ overline {x}} _ {1}}} {\ partielle x_ {2}}} x_ {2} \ oplus {\ frac {\ partielle ^ {2} f} {\ partielle x_ {1} \ partielle x_ {2}}} x_ {1} x_ {2} }}

wo

{\ displaystyle {\ partiell ^ {2} f \ über \ partiell x_ {1} \ partiell x_ {2}} = f _ {{\ bar {x}} _ {1} {\ bar {x}} _ {2 }} \ oplus f _ {{\ bar {x}} _ {1} x_ {2}} \ oplus f_ {x_ {1} {\ bar {x}} _ {2}} \ oplus f_ {x_ {1} x_ {2}}}

.

Für das Ergebnis wäre ${\ displaystyle n = 3}$

{\ displaystyle f (x_ {1}, x_ {2}, x_ {3}) = f _ {{\ bar {x}} _ {1} {\ bar {x}} _ {2} {\ bar {x }} _ {3}} \ oplus {\ partielle f _ {{\ bar {x}} _ {2} {\ bar {x}} _ {3}} \ über \ partielle x_ {1}} x_ {1} \ oplus {\ partielle f _ {{\ bar {x}} _ {1} {\ bar {x}} _ {3}} \ über \ partielle x_ {2}} x_ {2} \ oplus {\ partielle f_ { {\ bar {x}} _ {1} {\ bar {x}} _ {2}} \ über \ partiell x_ {3}} x_ {3} \ oplus {\ partiell ^ {2} f _ {{\ bar {x}} _ {3}} \ über \ partiell x_ {1} \ partiell x_ {2}} x_ {1} x_ {2} \ oplus {\ partiell ^ {2} f _ {{\ bar {x}} _ {2}} \ über \ partiell x_ {1} \ partiell x_ {3}} x_ {1} x_ {3} \ oplus {\ partiell ^ {2} f _ {{\ bar {x}} _ {1} } \ over \ partielle x_ {2} \ partielle x_ {3}} x_ {2} x_ {3} \ oplus {\ partielle ^ {3} f \ over \ partielle x_ {1} \ partielle x_ {2} \ partielle x_ {3}} x_ {1} x_ {2} x_ {3}}

wo

{\ displaystyle {\ partiell ^ {3} f \ über \ partiell x_ {1} \ partiell x_ {2} \ partiell x_ {3}} = f _ {{\ bar {x}} _ {1} {\ bar { x}} _ {2} {\ bar {x}} _ {3}} \ oplus f _ {{\ bar {x}} _ {1} {\ bar {x}} _ {2} x_ {3}} \ oplus f _ {{\ bar {x}} _ {1} x_ {2} {\ bar {x}} _ {3}} \ oplus f _ {{\ bar {x}} _ {1} x_ {2} x_ {3}} \ oplus f_ {x_ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3}} \ oplus f_ {x_ {1} {\ bar {x} } _ {2} x_ {3}} \ oplus f_ {x_ {1} x_ {2} {\ bar {x}} _ {3}} \ oplus f_ {x_ {1} x_ {2} x_ {3} }}

.

Geometrische Interpretation

Diesem Fall kann eine kubische geometrische Interpretation (oder eine graphentheoretische Interpretation) wie folgt gegeben werden: Wenn Sie sich entlang der Kante von nach bewegen , XOR die Funktionen der beiden Endscheitelpunkte der Kante nach oben, um den Koeffizienten von zu erhalten . Um von dort nach dort zu gelangen, gibt es zwei kürzeste Pfade: einen zweispurigen Pfad und einen zweikantigen Pfad . Diese beiden Pfade umfassen vier Eckpunkte eines Quadrats, und das XOR-Hochfahren der Funktionen dieser vier Eckpunkte ergibt den Koeffizienten von . Um von dort nach oben zu gelangen, gibt es sechs kürzeste Pfade, die Pfade mit drei Kanten sind, und diese sechs Pfade umfassen alle Scheitelpunkte des Würfels. Daher kann der Koeffizient von erhalten werden, indem die Funktionen aller acht Scheitelpunkte XOR-erhöht werden. (Die anderen, nicht erwähnten Koeffizienten können durch Symmetrie erhalten werden.) ${\ displaystyle n = 3}$ ${\ displaystyle {\ bar {x}} _ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle x_ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle {\ bar {x}} _ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle x_ {1} x_ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle x_ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle {\ bar {x}} _ {1} x_ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle x_ {1} x_ {2}}$ ${\ displaystyle {\ bar {x}} _ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3}}$ ${\ displaystyle x_ {1} x_ {2} x_ {3}}$ ${\ displaystyle x_ {1} x_ {2} x_ {3}}$

Wege

Die kürzesten Pfade beinhalten alle monotone Änderungen der Werte der Variablen, während nicht kürzeste Pfade alle nicht monotone Änderungen solcher Variablen beinhalten; oder anders ausgedrückt, die kürzesten Pfade haben alle Längen, die dem Hamming-Abstand zwischen dem Start- und dem Zielscheitelpunkt entsprechen. Dies bedeutet, dass es einfach sein sollte, einen Algorithmus zum Erhalten von Koeffizienten aus einer Wahrheitstabelle zu verallgemeinern, indem Werte der Funktion aus geeigneten Zeilen einer Wahrheitstabelle XOR-verknüpft werden, selbst für hyperdimensionale Fälle ( und höher). Zwischen den Start- und Zielzeilen einer Wahrheitstabelle bleiben bei einigen Variablen die Werte fest: Suchen Sie alle Zeilen der Wahrheitstabelle so, dass diese Variablen ebenfalls auf den angegebenen Werten fixiert bleiben, und erhöhen Sie dann ihre Funktionen, und das Ergebnis sollte das sein Koeffizient für das Monom, das der Zielzeile entspricht. (Schließen Sie in einem solchen Monom jede Variable ein, deren Wert 1 ist (in dieser Zeile), und schließen Sie jede Variable aus, deren Wert 0 ist (in dieser Zeile), anstatt die Negation der Variablen einzuschließen, deren Wert 0 ist, wie im Minterm-Stil. ) ${\ displaystyle n = 4}$

Ähnlich wie bei binären Entscheidungsdiagrammen (BDDs), bei denen Knoten die Shannon-Expansion in Bezug auf die entsprechende Variable darstellen, können wir ein Entscheidungsdiagramm definieren, das auf der Reed-Muller-Expansion basiert. Diese Entscheidungsdiagramme werden als funktionale BDDs (FBDDs) bezeichnet.

Ableitungen

Die Reed-Muller-Erweiterung kann aus der XOR-Form der Shannon-Zerlegung unter Verwendung der folgenden Identität abgeleitet werden : ${\ displaystyle {\ overline {x}} = 1 \ oplus x}$

{\ displaystyle {\ begin {align} f & = x_ {i} f_ {x_ {i}} \ oplus {\ overline {x}} _ {i} f _ {{\ overline {x}} _ {i}} \ \ & = x_ {i} f_ {x_ {i}} \ oplus (1 \ oplus x_ {i}) f _ {{\ overline {x}} _ {i}} \\ & = x_ {i} f_ {x_ {i}} \ oplus f _ {{\ overline {x}} _ {i}} \ oplus x_ {i} f _ {{\ overline {x}} _ {i}} \\ & = f _ {{\ overline { x}} _ {i}} \ oplus x_ {i} {\ frac {\ partielle f} {\ partielle x_ {i}}}. \ end {align}}}

Ableitung der Erweiterung für : ${\ displaystyle n = 2}$

{\ displaystyle {\ begin {align} f & = f _ {{\ bar {x}} _ {1}} \ oplus x_ {1} {\ partielles f \ über \ partielles x_ {1}} \\ & = {\ Groß (} f _ {{\ bar {x}} _ {2}} \ oplus x_ {2} {\ partiell f \ über \ partiell x_ {2}} {\ Big)} _ {{\ bar {x}} _ {1}} \ oplus x_ {1} {\ partiell {\ Big (} f _ {{\ bar {x}} _ {2}} \ oplus x_ {2} {\ partiell f \ über \ partiell x_ {2 }} {\ Big)} \ über \ partielle x_ {1}} \\ & = f _ {{\ bar {x}} _ {1} {\ bar {x}} _ {2}} \ oplus x_ {2 } {\ partielle f _ {{\ bar {x}} _ {1}} \ über \ partielle x_ {2}} \ oplus x_ {1} {\ Big (} {\ partielle f _ {{\ bar {x}} _ {2}} \ over \ partielle x_ {1}} \ oplus x_ {2} {\ partielle ^ {2} f \ over \ partielle x_ {1} \ partielle x_ {2}} {\ Big)} \\ & = f _ {{\ bar {x}} _ {1} {\ bar {x}} _ {2}} \ oplus x_ {2} {\ partielle f _ {{\ bar {x}} _ {1}} \ over \ partielle x_ {2}} \ oplus x_ {1} {\ partielle f _ {{\ bar {x}} _ {2}} \ over \ partielle x_ {1}} \ oplus x_ {1} x_ {2 } {\ partiell ^ {2} f \ über \ partiell x_ {1} \ partiell x_ {2}}. \ end {align}}}

Ableitung der booleschen Ableitung zweiter Ordnung:

{\ displaystyle {\ begin {align} {\ partiell ^ {2} f \ over \ partiell x_ {1} \ partiell x_ {2}} & = {\ partiell \ über \ partiell x_ {1}} {\ Big ( } {\ partielles f \ über \ partielles x_ {2}} {\ Big)} = {\ partielles \ über \ partielles x_ {1}} (f _ {{\ bar {x}} _ {2}} \ oplus f_ {x_ {2}}) \\ & = (f _ {{\ bar {x}} _ {2}} \ oplus f_ {x_ {2}}) _ {{\ bar {x}} _ {1}} \ oplus (f _ {{\ bar {x}} _ {2}} \ oplus f_ {x_ {2}}) _ {x_ {1}} \\ & = f _ {{\ bar {x}} _ {1 } {\ bar {x}} _ {2}} \ oplus f _ {{\ bar {x}} _ {1} x_ {2}} \ oplus f_ {x_ {1} {\ bar {x}} _ { 2}} \ oplus f_ {x_ {1} x_ {2}}. \ End {align}}}

Siehe auch

Verweise

Weiterführende Literatur

Жега́лкин [Zhegalkin], Ива́н Ива́нович [Ivan Ivanovich] (1927). "O Tekhnyke Vychyslenyi Predlozhenyi gegen Symbolytscheskoi Logykye" О технике вычислений предложений в символической логике [Zur Technik der Berechnung von Sätzen in der symbolischen Logik (Sur le calcul des Propositions dans la logique symbolique)]. Matematicheskii Sbornik (auf Russisch und Französisch). Moskau, Russland. 34 (1): 9–28. Mi msb7433 . Archiviert vom Original am 12.10.2017 . Abgerufen am 12.10.2017 .
Reed, Irving Stoy (September 1954). "Eine Klasse von Mehrfachfehlerkorrekturcodes und das Decodierungsschema". IRE-Transaktionen zur Informationstheorie . IT-4 : 38–49.
Müller, David Eugene (September 1954). "Anwendung der Booleschen Algebra auf das Schaltungsdesign und die Fehlererkennung". IRE-Transaktionen auf elektronischen Computern . EC-3 : 6–12.
Kebschull, Udo; Rosenstiel, Wolfgang (1993). "Effiziente graphbasierte Berechnung und Manipulation von Funktionsentscheidungsdiagrammen". Tagungsband der 4. Europäischen Konferenz für Designautomatisierung : 278–282.
Maxfield, Clive "Max" (29.11.2006). "Reed-Muller-Logik" . Logik 101 . EETimes . Teil 3. Archivierte aus dem Original auf 2017.04.19 . Abgerufen am 19.04.2017 .
Steinbach, Bernd ; Posthoff, Christian (2009). "Vorwort". Logikfunktionen und Gleichungen - Beispiele und Übungen (1. Aufl.). Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8 . LCCN 2008941076 .
Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. Historischer Überblick über die Zersetzungsforschung". Ein Überblick über die Literatur zur Funktionszerlegung . Version IV. Functional Decomposition Group, Fakultät für Elektrotechnik, Portland University, Portland, Oregon, USA. S. 21–22. CiteSeerX 10.1.1.64.1129 . (188 Seiten)

Languages

In other projects