Capacitatea Shannon

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 martie 2020; verificările necesită 8 modificări .

Capacitatea Shannon ( Capacitatea Shannon ) este o caracteristică a unui grafic nedirecționat care descrie densitatea maximă de codare cu posibilitatea de urmărire garantată a erorilor în canalul de comunicație, al cărui model reprezintă acest grafic.

În acest model, vârfurile graficului corespund caracterelor alfabetului , iar prezența unei muchii între două vârfuri înseamnă că în timpul transmiterii primul caracter poate fi înlocuit cu al doilea, iar al doilea cu primul. Probabilitățile sau frecvența cu care se întâmplă acest lucru nu sunt luate în considerare în model, scopul fiind de a construi o metodă de codare optimă care să fie rezistentă la erori arbitrar imprevizibile de acest fel.

În ciuda formulării „practice”, sarcina de a determina capacitatea Shannon a unui graf este în prezent pur teoretică .

Motivația pentru învățare

Un text transmis folosind un alfabet de cinci caractere să fie transmis printr-un canal de comunicare : Din cauza erorilor de transmisie a semnalului, caracterele adiacente pot fi confundate, precum și ultimul ( ) poate fi confundat cu primul ( ). Graficul care descrie posibilele erori ale acestui canal de comunicare va fi un ciclu de lungime 5. $\{0,1,2,3,4\)$ $patru$ $0$ $G$

Dacă textul este transmis „ca atare”, atunci, după ce a primit caracterul , destinatarul nu va putea înțelege dacă caracterul a fost transmis de către expeditor sau dacă a fost caracterul transmis de către expeditor , în timpul transmiterii căruia un a apărut o eroare și s-a transformat într-un personaj . $2$ $2$ $unu$ $2$

O astfel de ambiguitate poate apărea întotdeauna atunci când sunt utilizate cel puțin două caractere, conectate printr-o muchie în graficul de eroare. Pentru a preveni acest lucru, puteți alege un set independent de vârfuri ale acestui grafic și puteți codifica textul numai folosind caracterele corespunzătoare acestor vârfuri. În același timp, pentru ca valoarea informațională a fiecărui caracter să sufere cât mai puțin posibil, este indicat să se ia dimensiunea maximă din astfel de seturi (mărimea acestuia este notată cu ). $\alpha (G)$

În exemplul luat în considerare, este evident și, prin urmare, textul trebuie să fie codificat cu două caractere (de exemplu, și ). Dacă lungimea textului transmis (numărul de caractere din alfabetul original) este egală cu , atunci există toate variantele acestui text și pentru a le codifica pe toate cu caractere ale alfabetului cu două litere, va fi nevoie de cel puțin biți , adică dimensiunea textului va crește cel puțin o dată. $\alpha (G)=2$ $unu$ $3$ $n$ $5^n$ $\log _{2}{(5^{n})}=n\log _{2}5$ $\log _{2}5$

Acest rezultat poate fi îmbunătățit dacă luăm în considerare nu setul de erori în transmiterea fiecărui caracter individual, ci erorile în transmiterea unei perechi de caractere. Graficul perechilor de caractere care pot fi înlocuite unul cu celălalt (se notează ca ) nu va avea un număr mai mic de independență. $G^{2}$

În exemplul luat în considerare, și una dintre mulțimile independente maxime este . Aceasta înseamnă că toate cele cinci caractere pot fi folosite în mesajul transmis, dar cu condiția ca atunci când sunt combinate în perechi consecutive, se vor forma doar perechi din acest set (de exemplu, textul nu poate fi folosit, deoarece poate fi format din text , care este de asemenea folosit ). Dacă inițial au existat caractere în textul transmis, atunci fiecare dintre ele poate fi tradus într-una dintre aceste perechi și obține un text de lungime cu proprietățile de urmărire a erorilor necesare. Din moment ce , atunci această metodă de codificare este mai eficientă decât prima. $\alpha (G^{2})=5$ $\{(0,3),(1,0),(2,2),(3,4),(4,1)\}$ $00$ $zece$ $n$ $2n$ $2<\log _{2}5$

Se pune în mod firesc întrebarea dacă acest rezultat poate fi îmbunătățit prin luarea în considerare a triplelor, cvadruplelor și mai multor caractere succesive în loc de perechi și care este cel mai bun rezultat care poate fi obținut prin această metodă. Formalizarea acestei întrebări conduce la conceptul de capacitate Shannon.

Definiție formală

Pentru a determina capacitatea Shannon, se folosește o definiție auxiliară a produsului direct al graficelor:

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

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

((v_{1},w_{1}),(v_{2},w_{2}))\în E'\iff ((v_{1},v_{2})\în 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}))

Această operație, până la izomorfism , este asociativă și comutativă, astfel încât se poate defini în mod natural gradul unui graf :

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

Definiție

Capacitatea Shannon a graficului este [1] $G$

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

Ultima egalitate se datorează faptului că [2] . $\alpha (G\times H)\geq \alpha (G)\alpha (H)$

Natura convergenței

Limită accesibilă

Limita secvenței nu este întotdeauna atinsă. De exemplu, când este unirea unui ciclu de lungime 5 ( ) și a unui vârf izolat, atunci , dar ${\sqrt[{n}]{\alpha (G^{n))}}$ $G$ $C_{5}$ $c(G)={\sqrt {5}}+1$ ${\sqrt[{n}]{\alpha (G^{n})}}<{\sqrt {5}}+1$

Acest lucru se datorează faptului că și , astfel încât același lucru este valabil și pentru unirea unui vârf izolat cu orice graf pentru care $\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)$

Rata de creștere

O întrebare relevantă este cât de repede se apropie valorile . În 2006, Alon și Lyubetsky au arătat. că, pentru o dimensiune a graficului suficient de mare, un număr finit de valori nu este suficient pentru a se cunoaște cu o precizie de cel puțin până la . În aceeași lucrare, ei au înaintat mai multe ipoteze pe această temă. [3] $\alpha _{n}={\sqrt[{n}]{\alpha (G^{n))))}$ $c(G)$ $\alpha_{n}$ $G$ $|G|^{\varepsilon }\forall \epsilon >0$

Teorema

Pentru orice număr întreg , există un grafic arbitrar de mare și mărime astfel încât $v$ $N$ $G$ $N$

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

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

Descrierea designului

Dovada lui Alon și Lyubetsky a fost probabilistică (adică o construcție specifică a unui singur grafic nu poate fi dedusă din ea , dar existența unui astfel de grafic a fost dovedită).

Ei au considerat un grafic complet de vârfuri ( - un număr întreg suficient de mare), ale cărui margini sunt împărțite în grupuri și o muchie este îndepărtată aleatoriu din fiecare grup (echipprobabil de-a lungul tuturor marginilor grupului). $nv$ $n$

Dacă indexăm vârfurile graficului în perechi , atunci două muchii și aparțin aceluiași grup dacă: $(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}$
$j_{1}=j_{2)$
${\displaystyle l_{1}-k_{1}=l_{2}-k_{2))$

Vizual, acest lucru poate fi reprezentat atunci când descrieți un grafic pe un tor ca o grupare de muchii obținute unele de altele prin translație paralelă de-a lungul unei linii drepte (vezi imaginea).

Note și metode de studiu

Algoritmii generali pentru calcularea capacității Shannon sunt necunoscuți din 2019. Acest lucru se datorează nu numai faptului că problema numărului de independență în sine este NP-complet și, prin urmare, dificilă din punct de vedere computațional, ci și faptului că, pentru valorile calculate pentru mici , problema de a prezice creșterea ulterioară a acestora. cantitățile rămân, de asemenea, netriviale. $\alpha (G^{k})$ $k$

Mai mult, nici măcar valoarea exactă a capacității pentru un ciclu de lungime 7 sau mai mare nu este cunoscută. [4] [5] Cu toate acestea, pentru ciclurile de lungime impară, legea limitei este cunoscută [6] :

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

Numărul Lovas

Laszlo Lovas a arătat în 1979 că . [7] Pentru demonstrație, el a derivat o limită superioară generală pentru capacitatea lui Shannon în termenii unei caracteristici a unui sistem de vectori a căror structură este legată de cea a graficului , și anume $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 }}

Cu această abordare, pentru a obține o estimare superioară, este suficient să se prezinte cel puțin un sistem de vectori cu proprietățile necesare, adică se face trecerea de la problema demonstrației la problema prezentării unui contraexemplu .

În construcția lui Lovas, doar numărul de vectori trebuie să se potrivească cu dimensiunea graficului, dar nu și cu dimensiunea spațiului . De exemplu, vectori tridimensionali au fost utilizați pentru demonstrație . $c(C_{5})={\sqrt {5}}$

Estimări algebrice

Haemers a obţinut o estimare a capacităţii în ceea ce priveşte rangul matricelor similare ca structură cu matricea de adiacenţă , şi anume .

c(G)\leq R(G)=\min _{B}\operatorname {rank} (B),

unde minimul este preluat peste toate matricele de dimensiune într-un câmp arbitrar astfel încât: $B$ $n\ ori n$

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

Astfel, pentru estimarea superioară este de asemenea suficient să se furnizeze cel puțin o matrice având un rang mic. [opt] $B$

Vezi și

Problema setului independent

Note

↑ Desemnarea este uneori folosită și $\Theta (G)$
↑ Diapozitive ale prelegerii MIPT "Modelul grafic al unui canal de comunicare. Capacitatea Shannon" . Data accesului: 30 decembrie 2019. Arhivat din original la 13 ianuarie 2017. (nedefinit)
↑ Alon, Noga și Lubetzky, Eyal (2006), Capacitatea Shannon a unui grafic și numerele de independență ale puterilor sale , IEEE Transactions on Information Theory T. 52: 2172–2176 , DOI 10.1109/tit.2006.872856 .
↑ vezi, de exemplu, arXiv:1504.01472 Arhivat la 30 decembrie 2019 la Wayback Machine , unde îmbunătățirea numerică a scorurilor lor este prezentată ca subiect pentru o lucrare separată
↑ Shannon capacitatea de șapte cicluri . Data accesului: 30 decembrie 2019. Arhivat din original la 30 decembrie 2019. (nedefinit)
↑ Bohman, Tom (2003), A limit theorem for the Shannon capacities of odd cycles, Proceedings of the American mathematical Society vol. 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), An upper bound for the Shannon capacity of a graph , Coloquia Mathematica Societatis János Bolyai T. 25: 267–272 , < https://pure.uvt.nl/portal/files/997000 /UPPER___.PDF > Arhivat 4 martie 2016 la Wayback Machine . Definiția de aici corectează o greșeală de tipar din această lucrare.