Shannon kapacitás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. március 8-án felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A Shannon-kapacitás ( Shannon-kapacitás ) egy irányítatlan gráf jellemzője, amely a maximális kódolási sűrűséget írja le garantált hibakövetési lehetőséggel a kommunikációs csatornában, amelynek modellje ezt a grafikont reprezentálja.

Ebben a modellben a gráf csúcsai az ábécé karaktereinek felelnek meg , és a két csúcs közötti él jelenléte azt jelenti, hogy az átvitel során az első karakter helyettesíthető a másodikkal, a második pedig az elsővel. Ennek valószínűségét vagy gyakoriságát a modell nem veszi figyelembe, a cél egy olyan optimális kódolási módszer felépítése, amely ellenáll az ilyen jellegű tetszőlegesen előre nem látható hibáknak.

A „gyakorlati” megfogalmazás ellenére a gráf Shannon-kapacitásának meghatározása jelenleg tisztán elméleti feladat .

Motiváció a tanuláshoz

Legyen egy öt karakterből álló ábécé használatával továbbított szöveg egy kommunikációs csatornán keresztül : A jelátvitel hibái miatt a szomszédos karakterek összekeveredhetnek, valamint az utolsó ( ) az elsővel ( ). A kommunikációs csatorna lehetséges hibáit leíró grafikon egy 5 hosszúságú ciklus lesz. ${\megjelenítési stílus \{0,1,2,3,4\))$ $négy$ $0$ $G$

Ha a szöveget "ahogyan" továbbítják, akkor a címzett a karakter vétele után nem fogja tudni megérteni, hogy a karaktert a feladó küldte-e tovább, vagy az volt-e a feladó által továbbított karakter , amelynek továbbítása során egy hiba történt, és karakterré változott . $2$ $2$ $egy$ $2$

Ilyen kétértelműség mindig előfordulhat, ha legalább két karaktert használunk, amelyeket egy él köt össze a hibagráfban. Ennek elkerülése érdekében kiválaszthatja a gráf független csúcskészletét, és a szöveget csak az ezeknek a csúcsoknak megfelelő karakterekkel kódolhatja. Ugyanakkor annak érdekében, hogy az egyes karakterek információs értéke a lehető legkevesebbet szenvedjen, célszerű az ilyen halmazokból a maximális méretet venni (a méretét jelöljük ). $\alpha (G)$

A vizsgált példában ez nyilvánvaló, ezért a szöveget két karakterrel kell kódolni (például és ). Ha a továbbított szöveg hossza (az eredeti ábécé karaktereinek száma) egyenlő , akkor ennek a szövegnek minden változata létezik, és ezek mindegyikének kétbetűs ábécé karaktereivel történő kódolása legalább bitet vesz igénybe. , vagyis a szöveg mérete legalább egyszer megnő. $\alpha (G)=2$ $egy$ $3$ $n$ $5^n$ $\log _{2}{(5^{n})}=n\log _{2}5$ $\log _{2}5$

Ez az eredmény javítható, ha nem az egyes karakterek átvitelének hibahalmazát vesszük figyelembe, hanem egy karakterpár átvitelének hibáit. Az egymást helyettesíthető karakterpárok grafikonja (jelölése ) nem kevesebb függetlenséggel rendelkezik. $G^{2}$

A vizsgált példában és az egyik maximális független halmaz a . Ez azt jelenti, hogy mind az öt karakter használható a továbbított üzenetben, de azzal a feltétellel, hogy ha egymást követő párokká egyesítik, akkor ebből a halmazból csak párok jönnek létre (például szöveg nem használható, mert az szöveg , amelyet szintén használnak). Ha kezdetben voltak karakterek a továbbított szövegben, akkor mindegyiket le lehet fordítani egy ilyen párba, és egy hosszú szöveget kaphat a szükséges hibakövetési tulajdonságokkal. Mivel , akkor ez a kódolási módszer hatékonyabb, mint az első. $\alpha (G^{2})=5$ ${\megjelenítési stílus \{(0,3),(1,0),(2,2),(3,4),(4,1)\}}$ $00$ $tíz$ $n$ $2n$ $2<\log _{2}5$

Természetesen felmerül a kérdés, hogy javítható-e ez az eredmény, ha párok helyett egymást követő hármasokat, négyeseket és több karaktert veszünk figyelembe, és mi a legjobb eredmény, amit ezzel a módszerrel lehet elérni. Ennek a kérdésnek a formalizálása a Shannon-kapacitás fogalmához vezet.

Formális definíció

A Shannon-kapacitás meghatározásához a gráfok közvetlen szorzatának segéddefinícióját használjuk:

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

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}))

Ez a művelet az izomorfizmusig asszociatív és kommutatív, így természetesen meg lehet határozni a gráf fokát :

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

Meghatározás

A grafikon Shannon-kapacitása [ 1] $G$

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

Az utolsó egyenlőség annak a ténynek köszönhető, hogy [2] . $\alpha (G\times H)\geq \alpha (G)\alpha (H)$

A konvergencia természete

Elérhető határ

A sorozathatárt nem mindig éri el. Például mikor egy 5 ( ) hosszúságú ciklus és egy izolált csúcs uniója, akkor , de ${\sqrt[{n}]{\alpha (G^{n))}}$ $G$ $C_{5}$ $c(G)={\sqrt {5}}+1$ ${\sqrt[{n}]{\alpha (G^{n})}}<{\sqrt {5}}+1$

Ez annak a ténynek köszönhető, hogy és , így ugyanez igaz egy izolált csúcs uniójára bármely gráfra , amelyre $\alpha (G^{n})=\sum \limits _{k=1}^{n}{{\binom {n}{k}}\alpha ({C_{5}}^{k })}+1$ $\alpha (C_{5})<c(C_{5})$ $H$ $\alpha (H)<c(H)$

Növekedési ütem

Lényeges kérdés, hogy milyen gyorsan közelednek az értékek . 2006-ban Alon és Lyubetsky megmutatta. hogy kellően nagy grafikonmérethez nem elég véges számú értéket legalább -ig terjedő pontossággal tudni . Ugyanebben a munkában több hipotézist is felállítottak ebben a témában. [3] $\alpha _{n}={\sqrt[{n}]{\alpha (G^{n)))))$ $c(G)$ $\alpha_{n}$ $G$ $|G|^{\varepsilon }\forall \epsilon >0$

Tétel

Bármely egész számhoz létezik egy tetszőlegesen nagy és méretű gráf $v$ $N$ $G$ $N$

$\alpha _{k}=O(\log N)$ nál nél $k<v$

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

Tervezési leírás

Alon és Lyubetsky bizonyítása valószínűségi volt (azaz egyetlen gráf konkrét konstrukciója nem vezethető le belőle , de ennek létezése bebizonyosodott).

A csúcsok teljes gráfját tekintették ( - egy kellően nagy egész szám), amelynek éleit csoportokra osztják, és minden csoportból véletlenszerűen eltávolítanak egy élt (valószínűleg a csoport összes éle mentén). $nv$ $n$

Ha páronként indexeljük a gráf csúcsait , akkor két él és ugyanabba a csoportba tartozik, ha: $(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}$

Vizuálisan ez ábrázolható, ha egy gráfot a tóruszon ábrázolunk egy egyenes mentén párhuzamos fordítással kapott élek csoportosításaként (lásd a képet).

Osztályzatok és tanulmányi módszerek

A Shannon-kapacitás kiszámítására szolgáló általános algoritmusok 2019-től ismeretlenek. Ez nemcsak annak köszönhető, hogy magának a függetlenségi számnak a problémája NP-teljes , és ezért számításilag nehéz, hanem abból is, hogy a kicsire számított értékek esetén ezek további növekedésének előrejelzése a probléma. a mennyiségek szintén nem triviálisak maradnak. $\alpha (G^{k})$ $k$

Sőt, még a 7 vagy annál hosszabb páratlan hosszúságú ciklus kapacitásának pontos értéke sem ismert. [4] [5] A páratlan hosszúságú ciklusok esetében azonban ismert a határtörvény [6] :

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

Lovas szám

Lovas László 1979-ben megmutatta, hogy . [7] Bizonyításképpen levezette Shannon kapacitásának általános felső korlátját egy olyan vektorrendszer karakterisztikájában, amelynek szerkezete a gráf szerkezetéhez kapcsolódik . $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 }}

Ezzel a megközelítéssel a felső becslés megszerzéséhez elegendő legalább egy vektorrendszert bemutatni a szükséges tulajdonságokkal, vagyis átmenet van a bizonyítási problémától az ellenpélda bemutatásának problémája felé .

Lovas konstrukciójában csak a vektorok számának kell egyeznie a gráf méretével, de nem a tér méretével . Például háromdimenziós vektorokat használtak a bizonyításhoz . $c(C_{5})={\sqrt {5}}$

Algebrai becslések

Haemers kapacitásbecslést kapott a szomszédsági mátrixhoz hasonló szerkezetű mátrixok rangja alapján , nevezetesen

c(G)\leq R(G)=\min _{B}\operátornév {rang} (B),

ahol a minimumot átveszi az összes méretmátrix egy tetszőleges mezőben úgy, hogy: $B$ $n\szer n$

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

Így a felső becsléshez az is elegendő, ha legalább egy kis rangú mátrixot adunk meg. [nyolc] $B$

Lásd még

A független halmaz probléma

Jegyzetek

↑ A megnevezést néha szintén használják $\Theta (G)$
↑ A "Kommunikációs csatorna grafikus modellje. Shannon-kapacitás" című MIPT előadás diákjai . Hozzáférés dátuma: 2019. december 30. Az eredetiből archiválva : 2017. január 13. (határozatlan)
↑ Alon, Noga és Lubetzky, Eyal (2006), A gráf Shannon-kapacitása és hatványainak függetlenségi számai , IEEE Transactions on Information Theory T. 52: 2172–2176 , DOI 10.1109/tit.2006.872856 .
↑ lásd például : arXiv:1504.01472 Archiválva : 2019. december 30. a Wayback Machine -nél , ahol pontszámaik számszerű javítását egy külön munka témájaként mutatják be
↑ A hétciklus Shannon-kapacitása . Hozzáférés dátuma: 2019. december 30. Az eredetiből archiválva : 2019. december 30. (határozatlan)
↑ Bohman, Tom (2003), A határérték tétel páratlan ciklusok Shannon-kapacitásaihoz, Proceedings of the American Mathematical Society, 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), Egy gráf Shannon-kapacitásának felső határa , Colloquia Mathematica Societatis Bolyai János T. 25: 267–272 , < https://pure.uvt.nl/portal/files/997000 /UPPER___.PDF > Archiválva : 2016. március 4. a Wayback Machine -nél . Az itt található meghatározás egy elírást javít ki ebben a cikkben.