Teoria informației

Satelitul artificial Skylab reprezintă una dintre aplicațiile teoriei informației

Teoria informației este o disciplină a „ computerului și telecomunicațiilor al cărei obiect este analiza și prelucrarea matematicii de bază a fenomenelor legate de măsurarea și transmiterea informațiilor pe un canal de comunicare fizică

Mărimea care măsoară cantitatea de date se numește entropie și este de obicei exprimată ca numărul de biți necesari pentru stocarea sau transmiterea informațiilor. De exemplu, dacă un alfabet are o entropie egală cu 4 biți, atunci, luând un număr suficient de cuvinte construite cu acel alfabet, sunt necesari în medie 4 biți pentru a reprezenta fiecare literă.

Aplicarea conceptelor fundamentale ale teoriei informației include compresia fără pierderi (de exemplu, Zip ), codarea cu pierderi (de exemplu, Mp3 ) și modulațiile digitale utilizate în transmisiile ethernet . Teoria informației este exact la jumătatea distanței dintre matematica aplicată , statistici , fizica aplicată , telecomunicații și computer . Impactul său a fost crucial în misiunile spațiale , în invenția CD - ului , telefoanelor , internetului , studiului lingvisticii și în multe alte domenii.

Istorie

Același subiect în detaliu: Istoria teoriei informației .

Evenimentul decisiv care a adus apariția teoriei informației și a atras imediat atenția lumii a fost publicarea articolului „ O teorie matematică a comunicării ”, de Claude Shannon în Jurnalul tehnic al sistemului Bell în iulie și octombrie 1948 .

Înainte de acest articol, de asemenea, în Bell Labs , au fost dezvoltate câteva concepte teoretice despre informații și întotdeauna fusese implicit presupus ipoteza tratării evenimentelor la fel de probabile. Articolul din 1924 al lui Harry Nyquist , Anumiți factori care afectează viteza telegrafică , conține câteva secțiuni teoretice care cuantifică „inteligența” și „viteza” la care poate fi transmis pe un sistem de comunicare, oferind raportul $W=K\log m$ ${\ displaystyle W = K \ log m}$ ${\ displaystyle W = K \ log m}$ , Unde W este viteza de transmitere a inteligenței, m este numărul diferitelor niveluri de tensiune pe care le puteți alege la fiecare pas, iar K este o constantă. Articolul din 1928 , lucrarea lui Ralph Hartley , Transmission of Information (Information Transmission), folosește cuvântul informațional pentru a indica o cantitate măsurabilă, care reflectă capacitatea receptorului de a distinge o secvență de simboluri de alta; informațiile din text sunt definite ca $H=\log S^{n}=n\log S$ ${\ displaystyle H = \ log S ^ {n} = n \ log S}$ ${\ displaystyle H = \ log S ^ {n} = n \ log S}$ , Unde S este numărul de simboluri posibile, n este numărul de simboluri transmise. Unitatea naturală de informație a fost deci cifra zecimală, ulterior redenumită hartley în onoarea sa. Alan Turing a folosit în 1940 o idee similară într-o parte a analizei statistice privind descifrarea codurilor criptografice Enigma folosită de germani în al doilea război mondial .

Ludwig Boltzmann în 1875

O mare parte din matematica din spatele teoriei informației în cazul evenimentelor cu probabilități diferite a fost dezvoltată în domeniul termodinamicii de Ludwig Boltzmann și Willard Gibbs . Legăturile dintre entropia definită în teoria informației și cea definită în termodinamică, inclusiv contribuțiile importante ale lui Rolf Landauer din anii 60, sunt explorate în lucrarea Entropie în termodinamică și teoria informației .

În articolul revoluționar al lui Shannon, a introdus pentru prima dată modelele cantitative și calitative de comunicare, concepute ca un proces statistic, la baza teoriei informației. Articolul se deschide cu afirmația că:

„Problema fundamentală a comunicării constă în reproducerea la un moment dat, exact sau aproximativ, a unui mesaj selectat într-un alt punct.”

Odată cu aceasta s-au născut ideile:

entropia și redundanța unei surse și importanța acesteia, prin intermediul teoremei codării sursei ;
Informațiile reciproce și capacitatea unui canal zgomotos, inclusiv promisiunea unei comunicări fără pierderi, utilizând teorema codării canalului ;
rezultatul practic al teoremei lui Shannon-Hartley pentru capacitatea unui canal gaussian;
biții , adică un nou mod de a înțelege unitatea fundamentală de informație.

Generalitate

Principalele concepte care stau la baza teoriei informației pot fi înțelese referindu-ne la un exemplu simplu: limbajul uman. În general, într-o limbă, cele mai utilizate cuvinte sunt mai scurte decât cele mai puțin folosite. De exemplu, „salut” este mai scurt decât „consistent”; în plus, chiar dacă uneori nu este posibil să înțelegem toate cuvintele unui discurs, sensul rămâne clar. Scopul teoriei informației este tocmai de a oferi metode de comprimare la maximum a informațiilor produse de o sursă eliminând toată redundanța (aceasta se numește codare sursă ), înainte de a adăuga un anumit nivel de redundanță într-o manieră țintită, la scopul de a face comunicarea (sau arhivarea) cea mai protejată de zgomot (vorbim în acest caz de codare a canalelor ). Studiul acestei teorii, ale cărui principii sunt deja prezente în formele umane de comunicare, a permis o dezvoltare excepțională în transmiterea și stocarea informațiilor încă din anii 1940.

În general, este considerată ca nașterea teoriei publicării lucrării "A Mathematical Theory of Communication" (O teorie matematică a comunicării) de Claude Shannon ; Rezultatele fundamentale prezentate în lucrarea sa sunt două: enunțarea teoremei primului Shannon (sau teorema de codificare a sursei), care afirmă că, în medie, numărul de biți necesari pentru a reprezenta rezultatul unui eveniment stochastic este egal cu entropia acestuia, astfel furnizarea unei limite superioare pentru posibilitatea comprimării datelor; al doilea rezultat, cunoscut sub numele de teorema de codare a canalului zgomotos sau teorema codării canalului, stabilește totuși că rata maximă de informații transferabile în mod fiabil pe un canal afectat de zgomot este sub un anumit prag care ia numele capacității canalului . Capacitatea poate fi abordată după dorință, utilizând sisteme de codare și decodare adecvate.

Teoria informației este strâns legată de o serie de discipline pure și aplicate care au fost proiectate și proiectate în ultimii șaizeci de ani: sisteme adaptive , inteligență artificială , sisteme complexe , cibernetică , informatică , învățare automată și multe altele. Prin urmare, teoria informației este o teorie matematică largă și aprofundată, cu aplicații la fel de largi și profunde, al cărei scop principal rămâne, totuși, teoria codificării .

Teoria codării se referă la studiul metodelor practice, numite coduri , pentru a crește eficiența unei transmisii și a reduce probabilitatea de eroare cât mai mult posibil, în limitele stabilite și demonstrate de Shannon pentru un canal dat; aceste coduri pot fi împărțite în tehnici de compresie a datelor (codare sursă) și corectare a erorilor (codare canal). În cel de-al doilea caz, au trecut mulți ani până când a fost posibil să se obțină rezultate apropiate de limitele oferite de Shannon. O a treia clasă de coduri sunt algoritmi criptografici. Conceptele și metodele teoriei informației sunt de fapt utilizate pe scară largă în criptografie și criptanaliză .

Teoria informației este folosită acum și în teoria jocurilor și în studiul piețelor bursiere , precum și în compoziția muzicală .

Cantitatea teoriei informației

Teoria informației se bazează pe teoria probabilității și a statisticii . Principala cantitate de informații sunt „ entropia , și anume informațiile conținute într-o variabilă aleatorie , și„ informația reciprocă , adică cantitatea de informații partajate între două variabile aleatoare. Primul indică faptul că un mesaj poate fi comprimat, în timp ce al doilea este util pentru a găsi rata de comunicare posibilă pe un canal .

Alegerea bazei logaritmice utilizate în următoarele formule determină unitatea de măsură utilizată pentru entropie. Cea mai comună unitate de măsură este, fără îndoială, bitul , care este utilizat dacă alegeți să utilizați logaritmi în baza 2. Alte unități de măsură includ nat , dacă utilizați logaritmul natural și hartley , care se bazează pe logaritmul la baza 10 .

În cele ce urmează, o expresie în formă $p\log p\,$ ${\ displaystyle p \ log p \,}$ ${\ displaystyle p \ log p \,}$ Este considerat prin convenție egal cu 0 atunci când p este zero. Acest lucru se justifică cu faptul că $\lim _{p\rightarrow 0+}p\log p=0$ ${\ displaystyle \ lim _ {p \ rightarrow 0+} p \ log p = 0}$ ${\ displaystyle \ lim _ {p \ rightarrow 0+} p \ log p = 0}$ pentru orice bază logaritmică.

Entropie

Entropia unui Bernoulli variabil

În funcție de probabilitatea de succes, denumită adesea entropie binară, $H_{\mathrm {b} }(p)$ ${\ displaystyle H _ {\ mathrm {b}} (p)}$ ${\ displaystyle H _ {\ mathrm {b}} (p)}$ . Entropia este maximă și valorează 1 bit, atunci când probabilitatea de succes este de 0,5, ca în cazul aruncării de monede.

L 'entropie, $H.$ ${\ displaystyle H}$ $H.$ , a unei variabile aleatorii discrete $X$ ${\ displaystyle X}$ $X$ , Valoarea asociată este măsura cantității de incertitudine a $X$ ${\ displaystyle X}$ $X$ .

Să presupunem că transmitem 1000 de biți (0 și 1). Dacă acești biți sunt cunoscuți înainte de transmisie (adică își asumă o anumită valoare cu probabilitatea 1), logica necesită că nu au fost transmise informații. În schimb, dacă fiecare bit este independent de ceilalți și are o probabilitate egală de a fi 0 sau 1, au fost trimiși 1000 de biți (în sensul teoriei informației). Între aceste două extreme, cantitatea de informații poate fi cuantificată după cum urmează. De sine $\mathbb {X} \,$ ${\ displaystyle \ mathbb {X} \,}$ ${\ displaystyle \ mathbb {X} \,}$ este ansamblul tuturor valorilor $X$ ${\ displaystyle x}$ $X$ decât variabila $X$ ${\ displaystyle X}$ $X$ poate lua și $p(x)=Pr(X=x)$ ${\ displaystyle p (x) = Pr (X = x)}$ ${\ displaystyle p (x) = Pr (X = x)}$ este probabilitatea ca $X$ ${\ displaystyle X}$ $X$ merită $X$ ${\ displaystyle x}$ $X$ , asa de $X$ ${\ displaystyle X}$ $X$ are

H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x)

{\ displaystyle H (X) = \ mathbb {E} _ {X} [I (x)] = - \ sum _ {x \ in \ mathbb {X}} p (x) \ log p (x)}

{\ displaystyle H (X) = \ mathbb {E} _ {X} [I (x)] = - \ sum _ {x \ in \ mathbb {X}} p (x) \ log p (x)}

bit de entropie (Aici, $I(x)$ ${\ displaystyle I (x)}$ $Eu (x)$ „ Informarea de sine , este contribuția entropiei atașată fiecărui mesaj). O proprietate importantă a entropiei este că este maximă atunci când toate mesajele din spațiul posibilelor mesaje sunt echipabile, adică mai imprevizibile. În acest caz $H(X)=\log |\mathbb {X} |.$ ${\ displaystyle H (X) = \ log | \ mathbb {X} |.}$ ${\ displaystyle H (X) = \ log | \ mathbb {X} |.}$

Cazul special al unei variabile aleatoare cu două ieșiri posibile este „entropia binară:

H_{\mathrm {b} }(p)=-p\log p-(1-p)\log(1-p).\,

{\ displaystyle H _ {\ mathrm {b}} (p) = - p \ log p- (1-p) \ log (1-p). \,}

{\ displaystyle H _ {\ mathrm {b}} (p) = - p \ log p- (1-p) \ log (1-p). \,}

Entropie articulară

„ Entropia comună a două variabile aleatorii discrete $X$ ${\ displaystyle X}$ $X$ și $Da$ ${\ displaystyle Y}$ $Da$ este pur și simplu entropia cuplului: $(X,Y)$ ${\ displaystyle (X, Y)}$ ${\ displaystyle (X, Y)}$ . Aceasta implică faptul că, dacă $X$ ${\ displaystyle X}$ $X$ Și $Da$ ${\ displaystyle Y}$ $Da$ sunt independenți , atunci entropia lor comună este suma entropiilor lor individuale.

De exemplu, dacă $(X,Y)$ ${\ displaystyle (X, Y)}$ $(X Y)$ Reprezintă poziția unei bucăți de șah ( $X$ ${\ displaystyle X}$ $X$ linia ed $Da$ ${\ displaystyle Y}$ $Da$ coloana), atunci entropia comună a rândului și a coloanei pe care este așezată piesa va fi entropia poziției piesei.

H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,

{\ displaystyle H (X, Y) = \ mathbb {E} _ {X, Y} [- \ log p (x, y)] = - \ sum _ {x, y} p (x, y) \ log p (x, y) \,}

{\ displaystyle H (X, Y) = \ mathbb {E} _ {X, Y} [- \ log p (x, y)] = - \ sum _ {x, y} p (x, y) \ log p (x, y) \,}

În ciuda unei notații similare, entropia articulară nu trebuie confundată cu „ entropia încrucișată .

Entropie condiționată

L ' entropie condițională a unei variabile aleatorii $X$ ${\ displaystyle X}$ $X$ , dată fiind variabila aleatorie $Da$ ${\ displaystyle Y}$ $Da$ Și

H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=\sum _{x,y}p(x,y)\log {\frac {p(y)}{p(x,y)}}.

{\ displaystyle H (X | Y) = \ mathbb {E} _ {Y} [H (X | y)] = - \ sum _ {y \ in Y} p (y) \ sum _ {x \ in X } p (x | y) \ log p (x | y) = \ sum _ {x, y} p (x, y) \ log {\ frac {p (y)} {p (x, y)}} .}

{\ displaystyle H (X | Y) = \ mathbb {E} _ {Y} [H (X | y)] = - \ sum _ {y \ in Y} p (y) \ sum _ {x \ in X } p (x | y) \ log p (x | y) = \ sum _ {x, y} p (x, y) \ log {\ frac {p (y)} {p (x, y)}} .}

„ Entropia condiționată a $X$ ${\ displaystyle X}$ $X$ dată fiind variabila aleatorie $Da$ ${\ displaystyle Y}$ $Da$ (numit și neînțelegere a $X$ ${\ displaystyle X}$ $X$ cu $Da$ ${\ displaystyle Y}$ $Da$ ) este entropia condițională împărțită la medie $Da$ ${\ displaystyle Y}$ $Da$ .

O proprietate fundamentală a entropiei condiționate este că:

H(X|Y)=H(X,Y)-H(Y).\,

{\ displaystyle H (X | Y) = H (X, Y) -H (Y). \,}

{\ displaystyle H (X | Y) = H (X, Y) -H (Y). \,}

Informații reciproce

Informația reciprocă măsoară cantitatea de informații dintr-o variabilă aleatorie care poate fi derivată prin observarea alteia. Într-un sistem de comunicații este important ca cantitatea de informații partajată de semnalele trimise și primite să fie maximizată. Informații reciproce ale $X$ ${\ displaystyle X}$ $X$ , relativ la $Da$ ${\ displaystyle Y}$ $Da$ Și:

I(X;Y)=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}

{\ displaystyle I (X; Y) = \ sum _ {x, y} p (x, y) \ log {\ frac {p (x, y)} {p (x) \, p (y)}} }

{\ displaystyle I (X; Y) = \ sum _ {x, y} p (x, y) \ log {\ frac {p (x, y)} {p (x) \, p (y)}} }

O proprietate importantă a informației reciproce este aceea

I(X;Y)=H(X)-H(X|Y).\,

{\ displaystyle I (X; Y) = H (X) -H (X | Y). \,}

{\ displaystyle I (X; Y) = H (X) -H (X | Y). \,}

Adică, știind Y, putem economisi în medie $I(X;Y)$ ${\ displaystyle I (X; Y)}$ ${\ displaystyle I (X; Y)}$ biți în codificarea lui X, comparativ cu cazul în care Y este necunoscut.

Informațiile reciproce sunt simetrice;

I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,

{\ displaystyle I (X; Y) = I (Y; X) = H (X) + H (Y) -H (X, Y). \,}

{\ displaystyle I (X; Y) = I (Y; X) = H (X) + H (Y) -H (X, Y). \,}

Informarea reciprocă poate fi exprimată ca medie a divergenței Kullback-Leibler a probabilității posterioare a X având în vedere valoarea Y, în comparație cu probabilitatea a priori a X:

I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))].

{\ displaystyle I (X; Y) = \ mathbb {E} _ {p (y)} [D _ {\ mathrm {KL}} (p (X | Y = y) \ | p (X))]. }

{\ displaystyle I (X; Y) = \ mathbb {E} _ {p (y)} [D _ {\ mathrm {KL}} (p (X | Y = y) \ | p (X))]. }

Cu alte cuvinte, măsoară cât de mult, în medie, se schimbă distribuția probabilității lui X dacă știm valoarea lui Y. Aceasta este adesea calculată ca o divergență față de produsul distribuțiilor marginale în ceea ce privește distribuția comună reală:

I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y)).

{\ displaystyle I (X; Y) = D _ {\ mathrm {KL}} (p (X, Y) \ | p (X) p (Y)).}

{\ displaystyle I (X; Y) = D _ {\ mathrm {KL}} (p (X, Y) \ | p (X) p (Y)).}

Informațiile reciproce pot fi considerate o statistică pentru a stabili independența între o pereche de variabile și are o distribuție asimptotică bine specificată.

Kullback - divergența Leibler

Divergența Kullback-Leibler (sau entropia relativă) este o modalitate de a compara două distribuții: o distribuție de probabilitate „adevărată” p (X) și o distribuție arbitrară q (X). Dacă comprimăm datele într-un fel, astfel încât q (x) este distribuția urmată de datele comprimate, atunci când de fapt distribuția datelor este p (x) , divergența Kullback - Leibler este numărul de biți suplimentari medii pentru datele necesare compresiei. Prin urmare, este definit ca

D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}-p(x)\log {q(x)}\,-\,\left(-p(x)\log {p(x)}\right)=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}.

{\ displaystyle D _ {\ mathrm {KL}} (p (X) \ | q (X)) = \ sum _ {x \ in X} -p (x) \ log {q (x)} \, - \, \ left (-p (x) \ log {p (x)} \ right) = \ sum _ {x \ in X} p (x) \ log {\ frac {p (x)} {q (x )}}.}

{\ displaystyle D _ {\ mathrm {KL}} (p (X) \ | q (X)) = \ sum _ {x \ in X} -p (x) \ log {q (x)} \, - \, \ left (-p (x) \ log {p (x)} \ right) = \ sum _ {x \ in X} p (x) \ log {\ frac {p (x)} {q (x )}}.}

Deși este, în unele cazuri, folosit ca metrică pentru „distanță”, nu este o metrică adevărată, deoarece nu este simetrică.

Aplicații

Capacitatea canalului

Același subiect în detaliu: Teorema codării canalelor .

Studiul comunicării pe un canal, cum ar fi un cablu Ethernet , este motivația înainte de nașterea teoriei informației. După cum știe oricine a folosit un telefon, se poate întâmpla ca canalul să nu poată transporta semnalul fără a-l „deteriora”; distorsiunile, ecourile sau zgomotul sunt doar câteva exemple de corupție a semnalului care duc la o degradare a calității comunicării. Întrebarea care se pune este deci care este rata maximă (sau rata de biți ) pe care pot spera să o comunic pe un „canal zgomotos” (adică care degradează comunicarea)?

Să luăm în considerare procesul de comunicare pe un canal discret. Un model simplu al procesului este prezentat în figură

Aici X reprezintă spațiul mesajelor transmise, iar Y spațiul mesajelor primite în timpul unei unități de timp pe canalul nostru. Este $p(y|x)$ ${\ displaystyle p (y | x)}$ ${\ displaystyle p (y | x)}$ distribuția probabilității condiționate a lui Y dat fiind X. Vom lua în considerare $p(y|x)$ ${\ displaystyle p (y | x)}$ ${\ displaystyle p (y | x)}$ o proprietate a canalului, care nu se schimbă și care, în esență, este zgomotul care afectează canalul. Apoi distribuția comună a lui X și Y este complet determinată de canal și de alegerea lui $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ , adică distribuția marginală a mesajului pe care decidem să îl trimitem pe canal. Având în vedere aceste constrângeri, vrem să maximizăm cantitatea de informații sau semnalul, vrem să comunicăm pe canal. Măsura adecvată pentru această cantitate este „ informația reciprocă și informația reciprocă maximă se numește capacitatea canalului , care este dată de:

C=\max _{f}I(X;Y).\!

{\ displaystyle C = \ max _ {f} I (X; Y). \!}

{\ displaystyle C = \ max _ {f} I (X; Y). \!}

Această capacitate are următoarele proprietăți, legate de rata de informații transmisă R (unde R este de obicei în biți pe simbol). Pentru fiecare rată R <C informații și eroare de codare ε> 0, pentru N suficient de mare, există o lungime de cod N și o rată R și un algoritm de codare astfel încât probabilitatea maximă de eroare să fie mai mică sau egală cu ε; cu alte cuvinte, este întotdeauna posibil să transmiteți cu orice rată de eroare scăzută. În plus, pentru fiecare rată R> C, nu puteți transmite cu o rată de eroare scăzută după bunul plac.

Teoria sursei

Orice proces care generează mesaje succesive poate fi considerat o sursă de informații. O sursă de memorie liberă este o sursă astfel încât fiecare mesaj este o variabilă aleatorie independentă și distribuită identic , în timp ce proprietățile ergodicității și staționarității impun constrângeri mai restrictive. Toate aceste surse sunt stochastice .

Bursuc

Rata informației este entropia medie pe simbol. Pentru sursele fără memorie, aceasta este pur și simplu entropia fiecărui simbol, în timp ce în cazul mai general

r=\mathbb {E} H(M_{t}|M_{t-1},M_{t-2},M_{t-3},\ldots ).

{\ displaystyle r = \ mathbb {E} H (M_ {t} | M_ {t-1}, M_ {t-2}, M_ {t-3}, \ ldots).}

{\ displaystyle r = \ mathbb {E} H (M_ {t} | M_ {t-1}, M_ {t-2}, M_ {t-3}, \ ldots).}

Tocmai aceasta este entropia condițională așteptată pe mesaj (adică pe unitate de timp) date tuturor mesajelor generate anterior. În teoria informației este obișnuit să vorbești despre „rata” sau „entropia” unei limbi. Acest lucru este adecvat, de exemplu, atunci când sursa informației este proza engleză. Viteza unei surse fără memorie este pur și simplu $H(M)$ ${\ displaystyle H (M)}$ ${\ displaystyle H (M)}$ , deoarece, prin definiție, nu există interdependență între mesajele succesive ale unei surse fără memorie. Rata unei surse de informații este legată de redundanța acesteia și de cât de bine poate fi comprimată.

Teoria codului

Același subiect în detaliu: teoria codării .

Teoria codului este cea mai importantă și directă aplicare a teoriei informației. Poate fi împărțit în codificare cod sursă și codificare canal. Folosind o descriere statistică a datelor, teoria informației cuantifică numărul de biți necesari pentru a descrie datele, această cantitate fiind entropia informațională a sursei.

Compresia datelor (codare sursă): Există două formulări pentru această problemă:

compresie fără pierderi, atunci când datele trebuie să fie reconstituite exact
compresie cu pierderi prin alocarea biților necesari pentru reconstituirea datelor într-un interval de fidelitate măsurat de funcția de distorsiune. Această ramură a teoriei informației se numește teoria distorsiunii ratei.

Coduri de corectare a erorilor (codare canal): În timp ce compresia datelor este destinată să elimine cât mai multă redundanță posibil, un cod de corectare a erorilor adaugă tipul corect de redundanță necesar pentru a transmite datele în mod eficient și fiabil pe un canal Noisy.

Împărțirea teoriei codului între compresie și transmisie este justificată de teoremele transmiterii informațiilor, care justifică utilizarea biților ca măsură universală a informației în multe contexte. Cu toate acestea, aceste teoreme sunt valabile doar în situația în care un utilizator care transmite vrea să comunice cu un utilizator care primește. În scenariile cu mai mulți expeditori sau mai mulți destinatari, este posibil ca compresia urmată de transmisie să nu fie optimă.

Utilizări de către serviciile secrete și aplicațiile de securitate

Conceptele de teorie a informației sunt utilizate pe scară largă în criptografie și criptanaliză . Pentru un exemplu istoric interesant, a se vedea deciban. Shannon însuși a definit un concept important numit acum distanța unicității . Pe baza redundanței textului, încearcă să ofere cantitatea minimă de text cifrat necesară pentru a asigura decriptarea unică.

Teoria informației lui Shannon este extrem de importantă la locul de muncă, mult mai mult decât indică utilizarea sa în criptografie. Serviciile secrete folosesc teoria informației pentru a păstra secretul informațiilor confidențiale și pentru a descoperi cât mai multe informații despre un adversar într-un mod sigur. Teorema Shannon-Hartley ne face să credem că păstrarea secretelor este mult mai dificilă decât s-ar putea crede inițial. În general, nu este posibilă oprirea scurgerii de informații confidențiale, ci doar încetinirea acestora. Mai mult, pe măsură ce crește numărul persoanelor care au acces la informații și crește timpul pe care acești oameni trebuie să-l dedice muncii și revizuirea acestor informații, crește redundanța pe care o dobândesc aceste informații. Este extrem de dificil să conțineți fluxul de informații care are o redundanță ridicată. Scurgerea inevitabilă a informațiilor confidențiale se datorează faptului psihologic că ceea ce știu oamenii le afectează comportamentul, chiar și într-un mod foarte subtil.

Generarea de numere pseudo-aleatorii

Un bun exemplu de aplicare a teoriei informației la comunicațiile ascunse este proiectarea codificării semnalelor din sistemul de poziționare globală . Sistemul folosește un generator de numere pseudorandom care pune semnalul radio sub podeaua de zgomot. Deci, un ascultător de radio nu ar putea nici măcar să înțeleagă că există un semnal prezent, deoarece ar fi înecat de diferite surse de zgomot (zgomot atmosferic sau de antenă). Cu toate acestea, făcând integralul pe o perioadă lungă de timp, folosind secvența pseudorandomică „secretă” (dar notează destinatarului), este posibil să detectezi semnalul și să înțelegi modulațiile. În sistemul global de poziționare, semnalul C / A a fost publicat ca o secvență de 1023 biți, dar secvența pseudorandom utilizată în P (Y) rămâne secretă. Aceeași tehnică poate fi utilizată pentru a transmite informații ascunse folosind sisteme de rază scurtă și de putere foarte mică, fără ca un dușman să observe existența semnalului radio. Este analog steganografiei . A se vedea, de asemenea, spectrul de comunicații.

Alte aplicații

Teoria informației are și aplicații în domeniul jocurilor de noroc , al bioinformaticii și al muzicii .

Bibliografie

Articolul clasic

(EN) Shannon, CE (1948), " A Mathematical Theory of Communication ", Bell System Technical Journal, 27, pp. 379-423 și 623-656, iulie și octombrie, 1948. PDF.

Alte articole științifice

(EN) CE Shannon,A Mathematical Theory of Cryptography , MM Memorandum 45-110-92, Bell Laboratories, septembrie 1945
(EN) RVL Hartley, Transmission of Information, Bell System Technical Journal, iulie 1928
(EN) JL Kelly, Jr., A New Interpretation of Information Rate , Bell System Technical Journal, Vol. 35, iulie 1956, pp. 917-26
(EN) R. Landauer, Information is Physical, Proc. Workshop on Physics and Computation PhysComp'92 (IEEE Comp. Sci. Press, Los Alamitos, 1993), pp. 1-4.
(EN) R. Landauer, ireversibilitatea și generarea de căldură în procesul de calcul , IBM J. Res. Develop., Vol. 5, nr. 3, 1961
(EN) S. Verdú, 50 de ani de la Teoria lui Shannon , IEEE Transactions on Information Theory, vol. 44 n.6, octombrie 1998

Manuale

(EN) Claude E. Shannon , Warren Weaver. Teoria matematică a comunicării. University of Illinois Press, 1949. ISBN 0-252-72548-4
(EN) Robert Gallager . Teoria informației și comunicarea fiabilă. New York: John Wiley și Sons, 1968. ISBN 0-471-29048-3
(EN) Thomas M. Cover, Joy A. Thomas. Elemente de teorie a informației, ediția I. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6 .

Ediția a II-a. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4 .

(EN) Fazlollah Reza . O introducere în teoria informației. New York: McGraw-Hill, 1961. New York: Dover 1994. ISBN 0-486-68210-2
(EN) Raymond W. Yeung. Un prim curs în teoria informației Kluwer Academic / Plenum Publishers, 2002. ISBN 0-306-46791-7
(RO) David JC MacKay. Teoria informației, inferența și algoritmii de învățare, Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

Alte cărți

(EN) James Bamford, The Puzzle Palace, Penguin Books, 1983. ISBN 0-14-006748-5
(EN) Leon Brillouin, Science and Information Theory, Mineola, NY: Dover, [1956, 1962], 2004. ISBN 0-486-43918-6
(EN) AI Khinchin, Mathematical Foundations of Information Theory, New York: Dover, 1957. ISBN 0-486-60434-9
(EN) HS Leff și AF Rex, editori, Maxwell's Demon: Entropy, Information, Computing, Princeton University Press, Princeton, NJ (1990). ISBN 0-691-08727-X
(EN) Tom Siegfried, Bitul și pendulul, Wiley, 2000. ISBN 0-471-32174-5
(EN) Charles Seife, Decoding The Universe, Viking, 2006. ISBN 0-670-03441-X
( EN ) EM Rogers, TW Valente, A History of information theory in communication research in: JR Schement, BD Ruben (a cura di), Information and behavior volume 4: Between communication and information , Transaction Publishers, New Brunswick (NJ), 1993.

Voci correlate

Applicazioni

Storia

Teoria

Concetti

Collegamenti esterni

( EN ) Teoria dell'informazione , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.
( EN ) Teoria dell'informazione , su The Encyclopedia of Science Fiction .
( EN ) Gibbs, M., "Quantum Information Theory", Eprint
( EN ) Schneider, T., "Information Theory Primer", Eprint
( EN ) IEEE Information Theory Society , su itsoc.org . URL consultato il 29 gennaio 2014 (archiviato dall' url originale il 22 gennaio 2009) .
( EN ) On-line textbook: Information Theory, Inference, and Learning Algorithms , by David MacKay - da un'introduzione piacevole e completa della teoria di Shannon, che include i metodi più recenti di codifica come i codici di parità a bassa densità ei Turbo codici

Controllo di autorità	Thesaurus BNCF 22088 · LCCN ( EN ) sh85066289 · GND ( DE ) 4026927-9 · BNF ( FR ) cb119321069 (data) · NDL ( EN , JA ) 00575012

Portale Informatica

Portale Matematica