Shannonin kapasitanssi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8.3.2020 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Shannon-kapasiteetti ( Shannon-kapasiteetti ) on suuntaamattoman graafin ominaisuus, joka kuvaa maksimikoodaustiheyttä mahdollisuudella taattua virheenseurantaa viestintäkanavassa, jonka malli edustaa tätä kuvaajaa.

Tässä mallissa graafin kärjet vastaavat aakkosten merkkejä , ja kahden kärjen välisen reunan olemassaolo tarkoittaa, että lähetyksen aikana ensimmäinen merkki voidaan korvata toisella ja toinen ensimmäisellä. Mallissa ei huomioida todennäköisyyksiä tai taajuutta, jolla näin tapahtuu, vaan tavoitteena on rakentaa optimaalinen koodausmenetelmä, joka kestää tämän tyyppisiä mielivaltaisesti arvaamattomia virheitä.

"Käytännön" muotoilusta huolimatta tehtävä graafin Shannonin kapasiteetin määrittäminen on tällä hetkellä puhtaasti teoreettinen .

Motivaatio oppimiseen

Olkoon viiden merkin aakkosilla lähetetty teksti välitetty viestintäkanavan kautta : Signaalin lähetyksen virheistä johtuen viereiset merkit voivat sekoittua, samoin kuin viimeinen ( ) voidaan sekoittaa ensimmäiseen ( ). Tämän viestintäkanavan mahdollisia virheitä kuvaava kaavio on 5 pituinen sykli. ${\näyttötyyli \{0,1,2,3,4\}}$ $neljä$ $0$ $G$

Jos teksti lähetetään "sellaisenaan", vastaanottaja ei voi merkin vastaanotettuaan ymmärtää, onko merkin lähettänyt lähettäjä vai onko se lähettäjän lähettämä merkki , jonka lähetyksen aikana tapahtui virhe ja se muuttui merkiksi . $2$ $2$ $yksi$ $2$

Tällaista epäselvyyttä voi aina esiintyä, kun käytetään vähintään kahta merkkiä, jotka on yhdistetty virhekaavion reunalla. Tämän estämiseksi voit valita tämän graafin itsenäisen joukon pisteitä ja koodata tekstin vain näitä pisteitä vastaavilla merkeillä. Samalla, jotta kunkin merkin tietoarvo kärsisi mahdollisimman vähän, on tarkoituksenmukaista ottaa tällaisista sarjoista suurin koko (sen kokoa merkitään ). $\alpha (G)$

Tarkasteltavassa esimerkissä se on ilmeistä, ja siksi teksti on koodattava kahdella merkillä (esimerkiksi ja ). Jos lähetettävän tekstin pituus (alkuperäisen aakkoston merkkien lukumäärä) on yhtä suuri kuin , niin tästä tekstistä on kaikki muunnelmat, ja niiden kaikkien koodaaminen kaksikirjaimien aakkosten merkeillä vie vähintään bittiä , eli tekstin koko kasvaa vähintään kerran. $\alpha (G)=2$ $yksi$ $3$ $n$ $5^n$ $\log _{2}{(5^{n})}=n\log _{2}5$ $\log _{2}5$

Tätä tulosta voidaan parantaa, jos ei oteta huomioon kunkin yksittäisen merkin lähetyksen virheiden joukkoa, vaan virheitä merkkiparin lähetyksessä. Toistensa korvattavissa olevien merkkiparien kaaviolla (merkitty merkillä ) on yhtä paljon riippumattomuutta. $G^{2}$

Tarkasteltavassa esimerkissä ja yksi suurimmista riippumattomista joukoista on . Tämä tarkoittaa, että kaikkia viittä merkkiä voidaan käyttää lähetetyssä viestissä, mutta sillä ehdolla, että kun ne yhdistetään peräkkäisiksi pareiksi, tästä sarjasta muodostuu vain pareja (esim. tekstiä ei voi käyttää, koska se voidaan muodostaa tekstiä , jota myös käytetään ). Jos alun perin lähetetyssä tekstissä oli merkkejä, jokainen niistä voidaan kääntää yhdeksi näistä pareista ja saada pituinen teksti , jolla on vaaditut virheenseurantaominaisuudet. Koska , tämä koodausmenetelmä on tehokkaampi kuin ensimmäinen. $\alpha (G^{2})=5$ ${\näyttötyyli \{(0,3),(1,0),(2,2),(3,4),(4,1)\}}$ $00$ $kymmenen$ $n$ $2n$ $2<\log _{2}5$

Luonnollisesti herää kysymys, voidaanko tätä tulosta parantaa ottamalla huomioon peräkkäiset kolmoset, nelinkertaiset ja useammat merkit parien sijaan, ja mikä on paras tulos, joka tällä menetelmällä voidaan saavuttaa. Tämän kysymyksen virallistaminen johtaa Shannonin kapasiteetin käsitteeseen.

Muodollinen määritelmä

Shannonin kapasiteetin määrittämiseen käytetään graafien suoratulon apumääritelmää:

$G_{1}\times G_{2}=(V_{1},E_{1})\times (V_{2},E_{2})=(V',E')$ , missä

V'=V_{1}\times V_{2}

((v_{1},w_{1}),(v_{2},w_{2}))\in E'\iff ((v_{1},v_{2})\in E_{ 1}\lor v_{1}=v_{2})\land ((w_{1},w_{2})\in E_{2}\lor w_{1}=w_{2})\land (( v_{1},w_{1})\not =(v_{2},w_{2}))

Tämä operaatio isomorfismiin asti on assosiatiivinen ja kommutatiivinen, joten voidaan luonnollisesti määrittää graafin aste :

{\displaystyle G^{k}=G\times G^{k-1))

Määritelmä

Kuvaajan Shannonin kapasiteetti on [1] $G$

c(G)=\sup \limits _{n\in {\mathbb {N} }}{\sqrt[{n}]{\alpha (G^{n)))))=\lim \ rajat _{n\to \infty }{\sqrt[{n}]{\alpha (G^{n))}}

Viimeinen yhtäläisyys johtuu siitä, että [2] . $\alpha (G\times H)\geq \alpha (G)\alpha (H)$

Lähentymisen luonne

Saavutettava raja

Sarjarajaa ei aina saavuteta. Esimerkiksi milloin on 5 ( ) pituisen syklin ja eristetyn kärjen liitto, niin , mutta ${\sqrt[{n}]{\alpha (G^{n))}}$ $G$ $C_{5}$ $c(G)={\sqrt {5}}+1$ ${\sqrt[{n}]{\alpha (G^{n})}}<{\sqrt {5}}+1$

Tämä johtuu siitä, että ja , joten sama pätee eristetyn kärjen yhdistämiseen minkä tahansa graafin kanssa, jolle $\alpha (G^{n})=\sum \limits _{k=1}^{n}{{\binom {n}{k}}\alpha ({C_{5}}^{k })}+1$ $\alpha (C_{5})<c(C_{5})$ $H$ ${\näyttötyyli \alpha (H)<c(H)}$

Kasvuvauhti

Olennainen kysymys on, kuinka nopeasti arvot lähestyvät . Vuonna 2006 Alon ja Lyubetsky näyttivät. että riittävän suurelle graafikoolle rajallinen määrä arvoja ei riitä tietämään vähintään :n tarkkuudella . Samassa työssä he esittivät useita hypoteeseja tästä aiheesta. [3] $\alpha _{n}={\sqrt[{n}]{\alpha (G^{n)))))$ $c(G)$ $\alpha_{n}$ $G$ $|G|^{\varepsilon }\forall \epsilon >0$

Lause

Jokaiselle kokonaisluvulle on olemassa mielivaltaisen suuri ja kokoinen kaavio , joka on sellainen $v$ $N$ $G$ $N$

$\alpha _{k}=O(\log N)$ klo $k<v$

$\alpha _{v}=N^{\frac {1}{v}}$

Suunnittelun kuvaus

Alonin ja Lyubetskyn todiste oli todennäköisyyspohjainen (eli siitä ei voida päätellä yksittäisen graafin tiettyä rakennetta , mutta sellaisen olemassaolo on todistettu).

He pitivät täydellistä kärkien graafia ( - riittävän suuri kokonaisluku), jonka reunat on jaettu ryhmiin ja yksi reuna poistetaan satunnaisesti jokaisesta ryhmästä (todennäköisesti kaikkia ryhmän reunoja pitkin). $nv$ $n$

Jos indeksoimme graafin kärjet pareittain , niin kaksi reunaa ja kuuluvat samaan ryhmään, jos: ${\näyttötyyli (i,k),i\in [1;n],k\in [1;v]}$ $((i_{1},k_{1}),(j_{1},l_{1}))$ $((i_{2},k_{2}),(j_{2},l_{2}))$

$i_{1}=i_{2}$
${\displaystyle j_{1}=j_{2))$
$l_{1}-k_{1}=l_{2}-k_{2}$

Visuaalisesti tämä voidaan esittää kuvattaessa graafia toruksessa toistensa ryhmittymänä, joka on saatu rinnakkaissiirrolla yhtä suoraa pitkin (katso kuva).

Arvosanat ja opintomenetelmät

Yleisiä Shannonin kapasiteetin laskentaalgoritmeja ei tunneta vuodesta 2019 lähtien. Tämä ei johdu pelkästään siitä, että itse riippumattomuusluvun ongelma on NP-täydellinen ja siksi laskennallisesti vaikea, vaan myös siitä, että pienten laskettujen arvojen osalta on ongelmallista ennustaa näiden lisäkasvua. määrät eivät myöskään ole triviaaleja. $\alpha (G^{k})$ $k$

Lisäksi kapasiteetin tarkkaa arvoa jaksolle, jonka pituus on 7 tai enemmän, ei tunneta. [4] [5] Parittoman pituisille jaksoille rajalaki kuitenkin tunnetaan [6] :

c(C_{2n+1})=n+{\frac {1}{2}}+o(1)

Lovas numero

Laszlo Lovas osoitti vuonna 1979 sen . [7] Todisteeksi hän johti Shannonin kapasiteetille yleisen ylärajan vektorijärjestelmän ominaispiirteenä, jonka rakenne liittyy graafin rakenteeseen , nimittäin $c(C_{5})={\sqrt {\alpha (C_{5}^{2)))))={\sqrt {5))$ $(u_{i})_{i\in V}$ $G=(V,E)$

u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&i=j,\\0,&(i,j)\notin E.\end{cases }}

Tällä lähestymistavalla ylemmän arvion saamiseksi riittää, että esitetään vähintään yksi vektorijärjestelmä, jolla on tarvittavat ominaisuudet, eli tapahtuu siirtymä todisteen ongelmasta vastaesimerkin esittämisen ongelmaan .

Lovaksen rakenteessa vain vektorien lukumäärän tulee vastata graafin kokoa, mutta ei tilan mittaa . Todistukseen käytettiin esimerkiksi kolmiulotteisia vektoreita . $c(C_{5})={\sqrt {5}}$

Algebralliset arviot

Haemers sai kapasiteettiestimaatin vierekkäisyysmatriisin rakenteeltaan samankaltaisten matriisien järjestyksen perusteella , nimittäin

c(G)\leq R(G)=\min _{B}\operaattorin nimi {sijoitus} (B),

jossa minimi otetaan kaikkiin mielivaltaisen kentän kokomatriisien päälle siten, että: $B$ $n\ kertaa n$

$b_{ii}\not =0$
$(i,j)\not \in E\Rightarrow b_{ij}=0$

Siten ylempään estimaattiin riittää myös vähintään yksi matriisi , jolla on pieni arvo. [kahdeksan] $B$

Katso myös

Itsenäisen joukon ongelma

Muistiinpanot

↑ Nimitystä käytetään joskus myös $\Theta (G)$
↑ Diat MIPT-luennosta "Tiedonsiirtokanavan graafinen malli. Shannon-kapasitanssi" . Käyttöpäivä: 30. joulukuuta 2019. Arkistoitu alkuperäisestä 13. tammikuuta 2017. (määrätön)
↑ Alon, Noga & Lubetzky, Eyal (2006), Kuvaajan Shannon-kapasiteetti ja sen potenssien riippumattomuusluvut , IEEE Transactions on Information Theory T. 52: 2172–2176 , DOI 10.1109/tit.2006.872856 .
↑ katso esim. arXiv:1504.01472 Arkistoitu 30. joulukuuta 2019 Wayback Machinessa , jossa heidän tulosten numeerinen parantaminen esitetään erillisen työn aiheena
↑ Shannonin kapasiteettiseitsemän jakson . Käyttöpäivä: 30. joulukuuta 2019. Arkistoitu alkuperäisestä 30. joulukuuta 2019. (määrätön)
↑ Bohman, Tom (2003), Rajalause parittomien syklien Shannonin kapasiteeteille, Proceedings of the American Mathematical Society, osa 131(11): 3559-3569
↑ Lovász, László (1979), On the Shannon Capacity of a Graph , IEEE Transactions on Information Theory T. IT-25(1) , DOI 10.1109/TIT.1979.1055985
↑ Haemers, Willem H. (1978), Kuvaajan Shannonin kapasiteetin yläraja , Colloquia Mathematica Societatis János Bolyai T. 25: 267–272 , < https://pure.uvt.nl/portal/files/997000 /UPPER___.PDF > Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa . Tässä oleva määritelmä korjaa kirjoitusvirheen tässä artikkelissa.