Shannonin laajennus

Matematiikassa Shannon -hajotelma tai Shannon- hajotelma muuttujassa on tapa esittää muuttujien Boolen funktio muiden muuttujien kahden alifunktion summana . Vaikka tämä menetelmä on usein katsottu Claude Shannonin ansioksi , Boole osoitti sen paljon aikaisemmin, ja tällaisen laajennuksen mahdollisuus missä tahansa muuttujassa johtuu suoraan mahdollisuudesta määrittää mikä tahansa Boolen funktio totuustaulukon avulla . $x_{i}$ $n$ $(n-1)$

Hajoaminen

Shannonin laajennus muuttujan suhteen perustuu siihen, että binäärimuuttujien Boolen funktion totuustaulukko voidaan jakaa kahteen osaan siten, että ensimmäinen osa sisältää vain ne syöteyhdistelmät, joissa muuttuja saa aina arvon , ja toinen osa sisältää vain ne syöttöyhdistelmien yhdistelmät, joissa muuttuja saa aina arvon (ja sen käänteinen arvo arvon ). Tämän seurauksena seuraava identiteetti tulee voimaan , jota kutsutaan Shannon-laajennukseksi: $x_{i}$ $n$ $x_{i}$ $yksi$ $x_{i}$ $0$ ${\overline {x_{i))}$ $yksi$

f(x)=x_{i}\cdot f_{x_{i}}(x)+{\overline {x_{i}}}\cdot f_{\overline {x_{i}}}(x) )=({\overline {x_{i}}}+f_{x_{i}}(x))\cdot ({x_{i}}+f_{\overline {x_{i}}}(x))

missä on laajennettava Boolen funktio, ja ovat sen muuttujan ei-invertoidut ja käänteiset arvot, joiden suhteen laajennus suoritetaan, ja ovat vastaavasti funktion positiivinen ja negatiivinen komplementti suhteessa muuttujaan . Shannon-laajennuksessa symbolit ja tarkoittavat konjunktio ("AND", AND) ja disjunktio ("OR", OR) operaatioita, mutta identiteetti pysyy voimassa, kun disjunktio korvataan ankaralla disjunktiolla (moduuli 2 lisäys, poissulkeva " TAI", XOR), koska termit eivät koskaan saa todellista arvoa samaan aikaan (koska positiivinen komplementti yhdistetään konjunktiolla , ja negatiivinen komplementti yhdistetään konjunktiolla sen käänteisen kanssa ). $f(x)$ $x_{i}$ ${\overline {x_{i))}$ $f_{x_{i))(x)$ $f_{\overline {x_{i))}(x)$ $f(x)$ $x_{i}$ $\cdot$ $+$ $f_{x_{i))(x)$ $x_{i}$ $f_{\overline {x_{i))}(x)$ ${\overline {x_{i))}$

Positiivisen komplementin määrää se totuustaulukon osa, jossa muuttuja saa aina arvon (ja sen käänteinen arvo saa arvon ): $f_{x_{i))(x)$ $x_{i}$ $yksi$ ${\overline {x_{i))}$ $0$

f_{x_{i}}(x)=f(x_{1},...,x_{i-1},1,x_{i+1},...,x_{n})

Negatiivinen komplementti määräytyy taulukon muun osan mukaan, jossa muuttuja saa aina arvon (ja käänteinen arvo saa arvon ): $f_{\overline {x_{i))}(x)$ $x_{i}$ $0$ ${\overline {x_{i))}$ $yksi$

f_{\overline {x_{i}}}(x)=f(x_{1},...,x_{i-1},0,x_{i+1},...,x_ {n})

Shannonin hajottelulause on kaikesta ilmeisyydestään huolimatta tärkeä idea Boolen algebrassa Boolen funktioiden esittämiseksi binääripäätöskaavioina , Boolen kaavojen tyydyttävyysongelman ratkaisemiseksi ja monien muiden tietokonesuunnitteluun ja digitaalisten piirien muodolliseen todentamiseen liittyvien tekniikoiden toteuttamiseksi. .

Artikkelissa "The Synthesis of Two-Terminal Switching Circuits" [1] Shannon kuvaili funktion hajoamista suhteessa muuttujaan seuraavasti: $x_{1}$

f(x_{1},x_{2},\dots ,x_{n})=x_{1}\cdot f(1,x_{2},\dots ,x_{n})+{\ overline {x_{1}}}\cdot f(0,x_{2},\dots ,x_{n})

jota seurasi laajentaminen kahdessa muuttujassa, ja totesi, että laajentamista voitiin jatkaa useilla muuttujilla.

Hajotusesimerkki

Olkoon kolmen muuttujan , ja Boolen funktio täydellinen disjunktiivinen normaalimuoto , eli alkeiskonjunktioiden disjunktiona, joista jokainen sisältää jokaisen muuttujan tai sen komplementin (inversion) samassa järjestyksessä: $x$ $y$ $z$

f=x\cdot y\cdot z+x\cdot {\overline {y}}\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot z+{\overline {x }}\cdot y\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot {\overline {z}}

Muuttujan laajentamista varten tämä funktio voidaan kirjoittaa uudelleen summaksi: $x$

f=x\cdot g_{x}+{\overline {x}}\cdot g_{\overline {x}}

saatuaan Boolen funktion laajennuksen muuttujassa yksinkertaisesti soveltamalla muuttujan jakoominaisuutta ja sen komplementtia (inversio) : $f$ $x$ $x$ $x'$

f=x(y\cdot z+{\overline {y}}\cdot z)+{\overline {x}}({\overline {y}}\cdot z+y\cdot z+{\overline { y))\cdot {\overline {z)))

Samoin funktion laajennus muuttujan tai suhteen suoritetaan : $f$ $y$ $z$

f=y(x\cdot z+{\overline {x}}\cdot z)+{\overline {y}}(x\cdot z+{\overline {x}}\cdot z+{\overline {x ))\cdot {\overline {z)))

f=z(x\cdot y+x\cdot {\overline {y}}+{\overline {x}}\cdot {\overline {y}}+{\overline {x}}\cdot { \overline {y)))+{\overline {z}}({\overline {x}}\cdot {\overline {y}})

Jokaisen jäljellä olevan funktion osalta pienemmässä määrässä muuttujia voidaan puolestaan jatkaa laajennusta yhdessä jäljellä olevista muuttujista.

Yleistys

Boolen funktion laajennuksen muuttuja ei voi olla vain tähän funktioon sisältyviä yksittäisiä muuttujia, vaan mikä tahansa multipleksointiehto. Esimerkiksi se on tiedossa laajennus lausekkeella (x > y) ja sen negaatiolla.

Katso myös

Muistiinpanot

↑ Shannon, Claude E. The Synthesis of Two-Tinal Switching Circuits // Bell System Technical Journal : päiväkirja. — Voi. 28 . - s. 59-98 .

Linkit

Shannonin hajotusesimerkki multipleksereillä.
Peräkkäisten syklien optimointi Shannon Decomposition and Retiming (PDF) -sovelluksen avulla.