Reed – Mullerova expanze - Reed–Muller expansion - Wikipedia

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Prosince 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v Logická logika, a Reed – Mullerova expanze (nebo Davio expanze) je rozklad a Booleovská funkce.

Pro booleovskou funkci ${ displaystyle f (x_ {1}, ldots, x_ {n}): mathbb {B} ^ {n} to mathbb {B}}$ voláme

${ displaystyle { begin {seřazeno} 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 {zarovnáno}}}$

pozitivní a negativní kofaktory z ${ displaystyle f}$ s ohledem na ${ displaystyle x_ {i}}$, a

${ displaystyle { begin {aligned} { frac { parciální f} { parciální x_ {i}}} & = f_ {x_ {i}} (x) oplus f _ {{ overline {x}} _ {i}} (x) end {zarovnáno}}}$

boolovská derivace ${ displaystyle f}$ s ohledem na ${ displaystyle x_ {i}}$, kde ${ displaystyle { oplus}}$ označuje XOR operátor.

Pak máme Reed – Muller nebo pozitivní expanze Davio:

${ displaystyle f = f _ {{ overline {x}} _ {i}} oplus x_ {i} { frac { částečné f} { částečné x_ {i}}}.}$

Popis

Tato rovnice je napsána tak, že se podobá a Taylorova expanze z ${ displaystyle f}$ o ${ displaystyle x_ {i} = 0}$. Existuje podobný rozklad odpovídající expanzi o ${ displaystyle x_ {i} = 1}$ (negativní expanze Davio):

${ displaystyle f = f_ {x_ {i}} oplus { overline {x}} _ {i} { frac { parciální f} { parciální x_ {i}}}.}$

Opakovaná aplikace expanze Reed – Muller vede k XOR polynomu v ${ 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}}$

Tato reprezentace je jedinečná a někdy se jí také říká Reed – Mullerova expanze.^[1]

Např. pro ${ displaystyle n = 2}$ výsledek by byl

${ displaystyle f (x_ {1}, x_ {2}) = f _ {{ overline {x}} _ {1} { overline {x}} _ {2}} oplus { frac { částečný f_ {{ overline {x}} _ {2}}} { částečné x_ {1}}} x_ {1} oplus { frac { částečné f _ {{ overline {x}} _ {1}}} { částečné x_ {2}}} x_ {2} oplus { frac { částečné ^ {2} f} { částečné x_ {1} částečné x_ {2}}} x_ {1} x_ {2} }$

kde

${ displaystyle { částečné ^ {2} f nad částečné x_ {1} částečné 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}}}$.

Pro ${ displaystyle n = 3}$ výsledek by byl

${ displaystyle f (x_ {1}, x_ {2}, x_ {3}) = f _ {{ bar {x}} _ {1} { bar {x}} _ {2} { bar {x }} _ {3}} oplus { částečný f _ {{ bar {x}} _ {2} { bar {x}} _ {3}} přes částečný x_ {1}} x_ {1} oplus { částečné f _ {{ bar {x}} _ {1} { bar {x}} _ {3}} přes částečné x_ {2}} x_ {2} oplus { částečné f_ { { bar {x}} _ {1} { bar {x}} _ {2}} přes částečné x_ {3}} x_ {3} oplus { částečné ^ {2} f _ {{ bar {x}} _ {3}} přes částečné x_ {1} částečné x_ {2}} x_ {1} x_ {2} oplus { částečné ^ {2} f _ {{ bar {x}} _ {2}} přes částečné x_ {1} částečné x_ {3}} x_ {1} x_ {3} oplus { částečné ^ {2} f _ {{ bar {x}} _ {1} } přes částečné x_ {2} částečné x_ {3}} x_ {2} x_ {3} oplus { částečné ^ {3} f přes částečné x_ {1} částečné x_ {2} částečné x_ {3}} x_ {1} x_ {2} x_ {3}}$

kde

${ displaystyle { částečné ^ {3} f nad částečné x_ {1} částečné x_ {2} částečné 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} }}$.

Geometrická interpretace

Tento ${ displaystyle n = 3}$ případu lze poskytnout kubickou geometrickou interpretaci (nebo graficko-teoretickou interpretaci) následovně: při pohybu podél hrany od ${ displaystyle { bar {x}} _ {1} { bar {x}} _ {2} { bar {x}} _ {3}}$ na ${ displaystyle x_ {1} { bar {x}} _ {2} { bar {x}} _ {3}}$, XOR zvýší funkce dvou koncových vrcholů hrany, aby získal koeficient ${ displaystyle x_ {1}}$. Přesunout se z ${ displaystyle { bar {x}} _ {1} { bar {x}} _ {2} { bar {x}} _ {3}}$ na ${ displaystyle x_ {1} x_ {2} { bar {x}} _ {3}}$ existují dvě nejkratší cesty: jedna je cesta se dvěma okraji, která prochází ${ displaystyle x_ {1} { bar {x}} _ {2} { bar {x}} _ {3}}$ a ten druhý prochází dvěma okraji ${ displaystyle { bar {x}} _ {1} x_ {2} { bar {x}} _ {3}}$. Tyto dvě cesty zahrnují čtyři vrcholy čtverce a XORing funkcí těchto čtyř vrcholů poskytuje koeficient ${ displaystyle x_ {1} x_ {2}}$. Nakonec přejít od ${ displaystyle { bar {x}} _ {1} { bar {x}} _ {2} { bar {x}} _ {3}}$ na ${ displaystyle x_ {1} x_ {2} x_ {3}}$ existuje šest nejkratších cest, které jsou cestami se třemi okraji, a těchto šest cest zahrnuje všechny vrcholy krychle, proto je koeficient ${ displaystyle x_ {1} x_ {2} x_ {3}}$ lze získat XOR zvyšováním funkcí všech osmi vrcholů. (Další, nezmíněné koeficienty lze získat symetrií.)

Cesty

Všechny nejkratší cesty zahrnují monotónní změny hodnot proměnných, zatímco všechny nejkratší cesty zahrnují nemonotické změny těchto proměnných; nebo jinak řečeno, všechny nejkratší cesty mají délky rovné Hammingově vzdálenosti mezi počátečním a cílovým vrcholem. To znamená, že by mělo být snadné zobecnit algoritmus pro získávání koeficientů z tabulky pravdivosti pomocí XOR zvyšování hodnot funkce z příslušných řádků tabulky pravdy, a to i pro hyperdimenzionální případy (${ displaystyle n = 4}$ a výše). Mezi počátečním a cílovým řádkem tabulky pravdivosti mají některé proměnné své hodnoty, které zůstávají pevné: najděte všechny řádky tabulky pravdy tak, aby tyto proměnné rovněž zůstaly pevné na uvedených hodnotách, pak XOR up jejich funkce a výsledkem by měl být koeficient pro monomiál odpovídající cílovému řádku. (V takovém monomiu zahrňte libovolnou proměnnou, jejíž hodnota je 1 (na tomto řádku), a vyloučte jakoukoli proměnnou, jejíž hodnota je 0 (na tomto řádku), místo toho, abyste zahrnovali negaci proměnné, jejíž hodnota je 0, jako ve stylu minterm. )

Podobný binární rozhodovací diagramy (BDD), kde představují uzly Shannonova expanze vzhledem k odpovídající proměnné můžeme definovat a rozhodovací diagram na základě expanze Reed – Muller. Tyto rozhodovací diagramy se nazývají funkční BDD (FBDD).

Odvození

Reed-Mullerovu expanzi lze odvodit z XOR-formy Shannonova rozkladu pomocí identity ${ displaystyle { overline {x}} = 1 oplus x}$:

${ displaystyle { begin {aligned} 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 { částečné f} { částečné x_ {i}}}. end {zarovnáno}}}$

Odvození expanze pro ${ displaystyle n = 2}$:

${ displaystyle { begin {aligned} f & = f _ {{ bar {x}} _ {1}} oplus x_ {1} { částečné f over částečné x_ {1}} & = { Velký (} f _ {{ bar {x}} _ {2}} oplus x_ {2} { částečný f nad částečný x_ {2}} { Velký)} _ {{ bar {x}} _ {1}} oplus x_ {1} { částečné { Big (} f _ {{ bar {x}} _ {2}} oplus x_ {2} { částečné f přes částečné x_ {2 }} { Big)} přes částečné x_ {1}} & = f _ {{ bar {x}} _ {1} { bar {x}} _ {2}} oplus x_ {2 } { částečné f _ {{ bar {x}} _ {1}} nad částečné x_ {2}} oplus x_ {1} { Big (} { částečné f _ {{ bar {x}} _ {2}} nad částečné x_ {1}} oplus x_ {2} { částečné ^ {2} f nad částečné x_ {1} částečné x_ {2}} { Velké)} & = f _ {{ bar {x}} _ {1} { bar {x}} _ {2}} oplus x_ {2} { částečné f _ {{ bar {x}} _ {1}} přes částečné x_ {2}} oplus x_ {1} { částečné f _ {{ bar {x}} _ {2}} přes částečné x_ {1}} oplus x_ {1} x_ {2 } { částečné ^ {2} f nad částečné x_ {1} částečné x_ {2}}. end {zarovnáno}}}$

Odvození booleovské derivace druhého řádu:

${ displaystyle { begin {zarovnáno} { částečné ^ {2} f nad částečné x_ {1} částečné x_ {2}} & = { částečné nad částečné x_ {1}} { Velké ( } { částečné f nad částečné x_ {2}} { Velké)} = { částečné nad částečné 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 {zarovnáno}}}$

Viz také

• Algebraická normální forma (ANF)
• Normální forma kruhového součtu (RSNF)
• Zhegalkin normální forma
• Karnaugh mapa
• Irving Stoy Reed
• David Eugene Muller
• Reed-Mullerův kód

Reference

Další čtení

• Kebschull, U .; Rosenstiel, W. (1993). "Efektivní grafický výpočet a manipulace s funkčními rozhodovacími diagramy". Sborník 4. evropská konference o automatizaci designu: 278–282.
• Maxfield, Clive "Max" (29. 11. 2006). „Reed-Mullerova logika“. Logika 101. EETimes. Část 3. Archivováno z původního dne 2017-04-19. Citováno 2017-04-19.
• Steinbach, Bernd; Posthoff, Christian (2009). "Předmluva". Logické funkce a rovnice - příklady a cvičení (1. vyd.). Springer Science + Business Media B. V. str. xv. ISBN  978-1-4020-9594-8. LCCN  2008941076.