Teoria e informacionit

Teoria e informacionit është studimi matematikor i kuantifikimit, ruajtjes dhe komunikimit të informacionit . Fusha u krijua dhe u formalizua nga Claude Shannon në vitet 1940, megjithëse kontributet e hershme u bënë në vitet 1920 përmes veprave të Harry Nyquist dhe Ralph Hartley. Ajo ndodhet në kryqëzimin e inxhinierisë elektronike, matematikës, statistikës, shkencës kompjuterike, neurobiologjisë, fizikës dhe inxhinierisë elektrike .

Një masë kyçe në teorinë e informacionit është entropia. Entropia përcakton sasinë e pasigurisë së përfshirë në vlerën e një variabli të rastësishëm ose në rezultatin e një procesi të rastësishëm . Për shembull, identifikimi i rezultatit të një hedhjes së një monedhe (e cila ka dy rezultate po të mundshme dhe të barabarta) ofron më pak informacion (entropi më të ulët, më pak pasiguri) sesa identifikimi i rezultatit të hedhjes së një zari (e cila ka gjashtë rezultate po aq të mundshme dhe të barabarta). Disa masa të tjera të rëndësishme në teorinë e informacionit janë informacioni i ndërsjellë, kapaciteti i kanalit, eksponentët e gabimit dhe entropia relative. Nënfushat e rëndësishme të teorisë së informacionit përfshijnë kodimin e burimit, teorinë e kompleksitetit algoritmik, teorinë e informacionit algoritmik dhe sigurinë teorike të informacionit .

Zbatimet e temave themelore të teorisë së informacionit përfshijnë kodimin e burimit/ kompresimin e të dhënave (p.sh. për skedarët ZIP ) dhe kodimin e kanalit/ zbulimin dhe korrigjimin e gabimeve (p.sh. për DSL ). Ndikimi i tij ka qenë thelbësor për suksesin e misioneve Voyager në hapësirën e thellë, shpikjen e diskut kompakt, realizueshmërinë e telefonave celularë dhe zhvillimin e internetit dhe inteligjencës artificiale . Teoria ka gjetur gjithashtu zbatim edhe në fusha të tjera, përfshirë inferencën statistikore, kriptografinë, neurobiologjinë perceptimin, përpunimin e sinjalit, linguistikën, evolucionin dhe funksionin e kodeve molekulare ( bioinformatikën ), fizikën termike, dinamikën molekulare, vrimat e zeza, informatikën kuantike, rikuperimin e informacionit, mbledhjen e inteligjencës, zbulimin e plagjiaturës, njohjen e modeleve, zbulimin e anomalive, analizën e muzikës, krijimin e artit, projektimin e sistemit të imazhit, studimin e hapësirës së jashtme, dimensionalitetin e hapësirës, dhe epistemologjinë .

Përmbledhje

Teoria e informacionit studion transmetimin, përpunimin, nxjerrjen dhe shfrytëzimin e informacionit . Në mënyrë abstrakte, informacioni mund të konsiderohet si zgjidhja e pasigurisë. Në rastin e komunikimit të informacionit përmes një kanali me zhurmë, ky koncept abstrakt u formalizua në vitin 1948 nga Claude Shannon në një punim të titulluar A Mathematical Theory of Communication, ku informacioni konsiderohet si një grup mesazhesh të mundshme, dhe qëllimi është që këto mesazhe të dërgohen përmes një kanali me zhurmë, dhe marrësi t'i rindërtojë ato me një probabilitet të ulët gabimi, pavarësisht zhurmës së kanalit. Rezultati kryesor i Shannon-it, teorema e kodimit të kanalit me zhurmë, tregoi se, në kufirin e përdorimeve të shumta shpejtësia e informacionit që arrihet asimptotikisht është e barabartë me kapacitetin e kanalit, një madhësi që varet vetëm nga statistikat e kanalit përmes të cilit dërgohen mesazhet.

Teoria e kodimit merret me gjetjen e metodave të qarta, të quajtura kode, për të rritur efikasitetin dhe për të ulur normën e gabimeve në komunikimin e të dhënave përmes kanaleve, duke u afruar sa më shumë me kapacitetin e kanalit. Këto kode mund të ndahen kryesisht në kompresimin e të dhënave (kodimi burimor) dhe korrigjimit të gabimeve (kodimi i kanalit). Në rastin e dytë, u deshën shumë vite për të gjetur metodat që puna e Shannon-it vërtetoi se ishin të mundshme.

Një klasë e tretë e kodeve në teorinë e informacionit janë algoritmet kriptografike (si kode ashtu edhe shifra). Konceptet, metodat dhe rezultatet nga teoria e kodimit dhe teoria e informacionit përdoren gjerësisht në kriptografi dhe kriptanalizë, siç është njësia e ndalimit .

Sfondi historik

Ngjarja historike që themeloi disiplinën e teorisë së informacionit dhe e solli atë në vëmendjen e menjëhershme botërore ishte botimi i punimit klasik të Claude Shannon "Një Teori Matematikore e Komunikimit" në Bell System Technical Journal në Korrik dhe Tetor 1948. Historiani James Gleick e vlerësoi punimin si zhvillimin më të rëndësishëm të vitit 1948, duke vënë në dukje se punimi ishte "edhe më i thellë dhe më themelor" sesa transistor. Ai u bë i njohur si "babai i teorisë së informacionit". Shannon përvijoi disa nga idetë e tij fillestare të teorisë së informacionit që në vitin 1939 në një letër drejtuar Vannevar Bush.

Para këtij punimi, në Bell Labs ishin zhvilluar disa ide të kufizuara të teorisë së informacionit, të gjitha duke supozuar në mënyrë implicite ngjarje me probabilitet të barabartë. Punimi i Harry Nyquist në vitin 1924, "Caktuar Faktorë që Ndikojnë në Shpejtësinë e Telegrafit ", përmban një seksion teorik që përcakton sasinë e "inteligjencës" dhe "shpejtësisë së linjës" me të cilën mund të transmetohet nga një sistem komunikimi, duke dhënë marrëdhënien W = K log m (në të cilin kujtohet konstanta e Boltzmann-it ), ku W është shpejtësia e transmetimit të inteligjencës, m është numri i niveleve të ndryshme të tensionit nga të cilat mund të zgjidhet në çdo hap kohor, dhe K është një konstante. Punimi i Ralph Hartley i vitit 1928, "Transmetimi i Informacionit", përdor fjalën informacion si një sasi të matshme, duke reflektuar aftësinë e marrësit për të dalluar një sekuencë simbolesh nga çdo tjetër, duke përcaktuar kështu sasinë e informacionit si H = log Sⁿ = n log S, ku S ishte numri i simboleve të mundshme, dhe n numri i simboleve në një transmetim. Njësia e informacionit ishte pra shifra dhjetore, e cila që atëherë ndonjëherë është quajtur hartley në nder të tij si një njësi ose shkallë ose masë e informacionit. Alan Turing në vitin 1940 përdori ide të ngjashme si pjesë e analizës statistikore të zbulimit të shifrave gjermane Enigma të Luftës së Dytë Botërore.

Shumica e matematikës pas teorisë së informacionit me ngjarje me probabilitete të ndryshme u zhvillua fillimisht për fushën e termodinamikës nga Ludwig Boltzmann dhe J. Willard Gibbs. Lidhjet midis entropisë në teori të informacioni dhe entropisë termodinamike, përfshirë kontributet e rëndësishme të Rolf Landauer në vitet 1960, janë eksploruar në punimin e Entropy in thermodynamics and information theory.

Në punimin revolucionar dhe themelor të Shannon-it, puna për të cilën ishte kryesisht përfunduar në Laboratorët Bell deri në fund të vitit 1944, Shannon për herë të parë prezantoi modelin cilësor dhe sasior të komunikimit si një proces statistikor që qëndron në themel të teorisë së informacionit, duke nisur me pohimin:

" Problemi themelor i komunikimit është ai i riprodhimit në një moment, saktësisht ose përafërsisht, të një mesazhi të zgjedhur në një moment tjetër. "

Me të erdhën idetë e:

• Entropia e informacionit dhe redundanca e një burimi, dhe rëndësia e saj përmes teoremës së kodimit të burimit ;
• Informacioni i ndërsjellë dhe kapaciteti i kanalit të një kanali me zhurmë, duke përfshirë premtimin e komunikimit të përsosur pa humbje të dhënë nga teorema e kodimit të kanalit me zhurmë;
• Rezultati praktik i ligjit Shannon-Hartley për kapacitetin e kanalit të një kanali Gaussian ; si dhe
• Biti — një mënyrë e re për të parë njësinë më themelore të informacionit.

Sasitë e informacionit

  Teoria e informacionit bazohet në teorinë e probabilitetit dhe statistikë, ku informacioni i kuantifikuar zakonisht përshkruhet në terma të biteve.Teoria e informacionit merret shpesh me matjet e informacionit të shpërndarjeve që lidhen me me variablat e rastësishme. Një nga masat më të rëndësishme quhet entropi, e cila formon bllokun ndërtues të shumë masave të tjera. Entropia lejon kuantifikimin e masës së informacionit në një variabël të vetëm të rastësishëm.

Një koncept tjetër i dobishëm është informacioni i ndërsjellë i përcaktuar mbi dy variabla të rastësishëm, i cili përshkruan masën e informacionit të përbashkët midis këtyre variablave, i cili mund të përdoret për të përshkruar korrelacionin e tyre.

Sasia e parë është një veti e shpërndarjes së probabilitetit të një variabli të rastësishëm dhe jep një kufi mbi shkallën me të cilën të dhënat e gjeneruara nga mostrat e pavarura me shpërndarjen e dhënë mund të kompresohen në mënyrë të besueshme. Kjo e fundit është një veti e shpërndarjes së përbashkët të dy variablave të rastësishme dhe është shkalla maksimale e komunikimit të besueshëm nëpër një kanal të zhurmshëm në kufirin e gjatësive të bllokut të gjatë, kur statistikat e kanalit përcaktohen nga shpërndarja e përbashkët.

Zgjedhja e bazës logaritmike në formulat e mëposhtme përcakton njësinë e entropisë së informacionit që përdoret. Një njësi e zakonshme informacioni është biti ose shannon, bazuar në logaritmin binar. Njësi të tjera përfshijnë nat, i cili bazohet në logaritmin natyror, dhe shifër dhjetore, e cila bazohet në logaritmin e zakonshëm.

Në vijim, një shprehje e formës p log p konsiderohet me anë të konventës të jetë e barabartë me zero sa herë që p = 0. Kjo justifikohet sepse $\lim _{p\rightarrow 0^{+}}p\log p=0$ për çdo bazë logaritmike.

Entropia e një burimi informacioni

Bazuar në funksionin e masës së probabilitetit të një burimi, entropia Shannon H, në njësi bit për simbol, përcaktohet si vlera e pritur e përmbajtjes së informacionit të simboleve.

Sasia e informacionit që përcjellë një simbol burimor individual $x_{i}$ me probabilitet $p_{i}$ njihet si vetë-informimi ose sasia e informacionit të saj, $I(p_{i})$ Kjo sasi përcaktohet si:

$H(X)=\log _{2}(n)$

Një simbol më pak i mundshëm ka një sasi të informacionit më të madhe, që do të thotë se ndodhja e tij ofron më shumë informacion. Entropia $H$ është mesatarja e ponderuar e surprizës së të gjitha simboleve të mundshme nga shpërndarja e probabilitetit të burimit:

$H(X)\ =\ \mathbb {E} _{X}[I(x)]\ =\ \sum _{i}p_{i}I(p_{i})\ =\ -\sum _{i}p_{i}\log _{2}(p_{i})$

Për shembull, nëse dikush transmeton 1000 bit (0 dhe 1), dhe vlera e secilit prej këtyre biteve i dihet marrësit (ka një vlerë të caktuar me siguri) përpara transmetimit, nuk transmetohet asnjë informacion. Megjithatë, nëse secili bit ka në mënyrë të pavarur dhe të barabartë gjasa të jetë 0 ose 1, janë transmetuar 1000 shannone informacioni (më shpesh të quajtura bit).

Entropia e një prove Bernoulli si një funksion i probabilitetit të suksesit, shpesh e quajtur funksioni binar i entropisë, Hb(p). Entropia maksimizohet në 1 bit për provë kur dy rezultatet e mundshme janë po aq të mundshme, si në një hedhje monedhe të paanshme.

Prona

Një veti kyçe e entropisë është se ajo maksimizohet kur të gjitha mesazhet në hapësirën e mesazheve janë ekuiprobabile . Për një burim me n simbole të mundshme, ku ${\textstyle p_{i}={\frac {1}{n}}}$ për të gjithë $i$, entropia jepet nga:

$I(p_{i})=-\log _{2}(p_{i})$

Kjo vlerë maksimale përfaqëson gjendjen më të paparashikueshme.

Zgjedhja e bazës logaritmike në formulën e entropisë përcakton njësinë e entropisë që përdoret:

• Një logaritëm me bazë 2 (siç tregohet në formulën kryesore) mat entropinë në bit për simbol. Kjo njësi nganjëherë quhet edhe shannon për nder të Claude Shannon.
• Një logaritëm natyror (baza e ) mat entropinë në nats për simbol. Kjo përdoret shpesh në analizat teorike pasi shmang nevojën për konstante shkallëzimi (si ln 2) në derivime.
• Baza të tjera janë gjithashtu të mundshme. Një logaritëm me bazë 10 mat entropinë në shifra dhjetore, osehartleys, për simbol. Një logaritëm me bazë 256 mat entropinë në bajt për simbol, meqenëse 2⁸ = 256

Funksioni i Entropisë Binare

Rasti i veçantë i entropisë së informacionit për një ndryshore të rastësishme me dy rezultate (një provë Bernoulli ) është funksioni binar i entropisë . Ky zakonisht llogaritet duke përdorur një logaritëm me bazë 2, dhe njësia e tij është shannon. Nëse një rezultat ka probabilitet p, tjetri ka probabilitet 1 − p. Entropia jepet nga:

$H_{\mathrm {b} }(p)=-p\log _{2}p-(1-p)\log _{2}(1-p)$

Ky funksion është paraqitur në grafikun e treguar më sipër, duke arritur maksimumin e tij prej 1 biti kur p = 0.5, që korrespondon me pasigurinë më të lartë.

Entropia e përbashkët

Entropia e përbashkët e dy variablave të rastësishme diskrete X dhe Y është thjesht entropia e çiftëzimit të tyre: (X, Y). Kjo nënkupton që nëse X dhe Y janë të pavarur, atëherë entropia e tyre e përbashkët është shuma e entropive të tyre individuale.

Për shembull, nëse (X, Y) përfaqëson pozicionin e një guri shahu X rreshti dhe Y kolona, atëherë entropia e përbashkët e rreshtit të gurit dhe kolonës së gurit do të jetë entropia e pozicionit të gurit.

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

Entropia e kushtëzuar (ekuivok)

Pasiguria e kushtëzuar e X duke pasur parasysh ndryshoren e rastësishme Y (e quajtur edhe ekuivok i X rreth Y ) është entropia mesatare e kushtëzuar mbi Y:

$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 p(x|y).$

Pasi entropia mund të kushtëzohet nga një ndryshore e rastësishme ose nga një vlerë e caktuar e asaj ndryshoreje të rastësishme, duhet pasur kujdes që të mos ngatërrohen këto dy përkufizime të entropisë së kushtëzuar, ku e para është më e përdorur zakonisht. Një veti themelore e kësaj forme të entropisë së kushtëzuar është se:

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

Informacion i ndërsjellë (transinformacion)

Informacioni i ndërsjellë mat sasinë e informacionit që mund të merret për një variabël të rastësishme duke vëzhguar një tjetër. Është i rëndësishëm në komunikim ku mund të përdoret për të maksimizuar sasinë e informacionit të ndarë midis sinjaleve të dërguara dhe të marra. Informacioni i ndërsjellë i X në lidhje me Y jepet nga:

$I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}$

ku SI (Informacion i ndërsjellë specifik ) është informacioni i ndërsjellë pikësor .

Një veti themelore e informacionit të ndërsjellë është se:

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

Informacioni i ndërsjellë është simetrik :

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

Informacioni i ndërsjellë mund të shprehet si mesatarja e divergjences Kullback-Leibler (fitimi i informacionit) midis shpërndarjes së probabilitetit të pasmë të $X$ duke pasur parasysh vlerën e ${\textstyle Y}$ dhe shpërndarja paraprake në $X$ :

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

Me fjalë të tjera, kjo është një masë e sa shumë, mesatarisht, është shpërndarja e probabilitetit në $X$ do të ndryshojë nëse na jepet vlera e ${\textstyle Y}$ Kjo shpesh rillogaritet si divergjencë nga produkti i shpërndarjeve marxhinale në shpërndarjen aktuale të përbashkët:

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

Divergjenca Kullback-Leibler (fitimi i informacionit)

Divergjenca Kullback-Leibler (ose divergjenca e informacionit, fitimi i informacionit ose entropia relative) është një mënyrë për të krahasuar dy shpërndarje: një shpërndarje probabiliteti "e vërtetë" p(X) ⁠dhe një shpërndarje probabiliteti arbitrare ⁠q(X). Nëse i kompresojmë të dhënat në një mënyrë që supozon ⁠q(X) është shpërndarja që qëndron në themel të disa të dhënave, kur, në realitet, ⁠p(X) është shpërndarja e saktë, divergjenca Kullback-Leibler është numri i bitëve shtesë mesatarë për të dhënë të nevojshme për kompresim. Kështu përcaktohet

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

Edhe pse ndonjëherë përdoret si një 'metrikë distancë', divergjenca KL nuk është një metrikë e vërtetë pasi nuk është simetrike dhe nuk plotëson pabarazinë e trekëndëshit (gjë që e bën atë një gjysmë-kuazimetrike).

Një interpretim tjetër i divergjencës KL është "surpriza e panevojshme" e prezantuar nga një paraprior nga e vërteta: supozojmë se një numër $X$ është gati të nxirret rastësisht nga një bashkësi diskrete me shpërndarje probabiliteti ⁠⁠p(x) Nëse Alice e di shpërndarjen e vërtetë ⁠p(X), ndërsa Bob beson (ka një paraprior) se shpërndarja është ⁠q(X), atëherë Bob do të jetë më i befasuar se Alice, mesatarisht, kur të shohë vlerën e $X$. Divergjenca KL është vlera e pritur (objektive) e surprizës (subjektive) të Bobit minus surpriza e Alisës, e matur në bit nëse logaritmi është në bazën 2. Në këtë mënyrë, shkalla në të cilën paraprirja e Bobit është "e gabuar" mund të përcaktohet në terma të asaj se sa "të befasuar panevojshëm" pritet ta bëjë atë.

Informacion i drejtuar

Informacion i drejtuar, $I(X^{n}\to Y^{n})$, është një masë e teorisë së informacionit që përcakton sasinë e rrjedhës së informacionit nga procesi i rastësishëm $X^{n}=\{X_{1},X_{2},\dots ,X_{n}\}$ në procesië e rastësishëm $Y^{n}=\{Y_{1},Y_{2},\dots ,Y_{n}\}$ Termi informacion i drejtuar u shpik nga James Massey dhe përkufizohet si:

$I(X^{n}\to Y^{n})\ \triangleq \ \sum _{i=1}^{n}I(X^{i};Y_{i}|Y^{i-1})$,

ku $I(X^{i};Y_{i}|Y^{i-1})$ është informacioni i ndërsjellë i kushtëzuar $I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})$.

Në dallim me informacionin e ndërsjellë, informacioni i drejtuar nuk është simetrik. $I(X^{n}\to Y^{n})$ mat bitët e informacionit që transmetohen në mënyrë kauzale nga $X^{n}$ për $Y^{n}$ Informacioni i drejtuar ka shumë zbatime në problemet ku shkakësia luan një rol të rëndësishëm, siç është kapaciteti i kanalit me reagime, kapaciteti i rrjeteve diskrete pa memorie me reagime, loja me informacionin e anës shkakësore, kompresimi me informacionin e anës shkakësore, cilësimet e komunikimit të kontrollit në kohë reale, dhe në fizikën statistikore.

Sasi të tjera

Madhësi të tjera të rëndësishme në teorinë e informacionit përfshijnë Rényi entropy (entropinë e Rényit) dhe Tsallis entropy (entropinë e Tsallisit) përgjithësime të konceptit të entropisë, entropinë diferenciale (një përgjithësim i sasive të informacionit në shpërndarje të vazhdueshme) dhe informacionin e ndërsjellë të kushtëzuar . Gjithashtu, informacioni pragmatik është propozuar si një masë se sa informacion është përdorur në marrjen e një vendimi.

Teoria e kodimit

 

Një fotografi që tregon gërvishtje në sipërfaqen e lexueshme të një CD-R. CD-të e muzikës dhe të të dhënave janë koduar duke përdorur kode korrigjimi të gabimeve dhe kështu mund të lexohen edhe nëse kanë gërvishtje të vogla duke përdorur zbulimin dhe korrigjimin e gabimeve .

Teoria e kodimit është një nga aplikimet më të rëndësishme dhe të drejtpërdrejta të teorisë së informacionit. Ajo mund të ndahet në teorinë e kodimit të burimit dhe teorinë e kodimit të kanalit. Duke përdorur një përshkrim statistikor për të dhënat, teoria e informacionit përcakton sasinë e bitëve të nevojshëm për të përshkruar të dhënat, që është entropia e informacionit të burimit.

• Kompresimi i të dhënave (kodimi burimor): Ekzistojnë dy formulime për problemin e kompresimit:
  • Kompresimi i të dhënave pa humbje : të dhënat duhet të rindërtohen saktësisht;
  • Kompresimi i të dhënave me humbje : ndan bitët e nevojshëm për të rindërtuar të dhënat, brenda një niveli të specifikuar besnikërie të matur nga një funksion shtrembërimi. Ky nëngrup i teorisë së informacionit quhet teoria e shkallës së shtrembërimit .
• Kodet e korrigjimit të gabimeve (kodifikimi i kanalit): Ndërsa kompresimi i të dhënave largon sa më shumë tepricë të jetë e mundur, një kod korrigjues gabimesh shton pikërisht llojin e duhur të tepricës (domethënë, korrigjimin e gabimeve) të nevojshme për të transmetuar të dhënat në mënyrë efikase dhe besnike përmes një kanali me zhurmë.

Kjo ndarje e teorisë së kodimit në kompresim dhe transmetim justifikohet nga teoremat e transmetimit të informacionit, ose teoremat e ndarjes burim-kanal të cilat justifikojnë përdorimin e biteve si monedha universale për informacionin në shumë kontekste. Megjithatë, këto teorema vlejnë vetëm në situatën ku një përdorues që transmeton dëshiron të komunikojë me një përdorues që merr. Në skenarë me më shumë se një transmetues (kanali me akses të shumëfishtë), më shumë se një marrës ( kanali i transmetimit ) ose "ndihmës" ndërmjetës, ose rrjete më të përgjithshme, kompresimi i ndjekur nga transmetimi mund të mos jetë më optimal.

Teoria e burimit

Çdo proces që gjeneron mesazhe të njëpasnjëshme mund të konsiderohet si një burim informacioni. Një burim pa memorie është ai në të cilin çdo mesazh është një ndryshore e rastësishme e pavarur dhe e shpërndarë identikisht, ndërsa vetitë e ergodicitetit dhe stacionaritetit imponojnë kufizime më pak kufizuese. Të gjitha burimet e tilla janë stokastike . Këta terma janë studiuar mirë në teorinë e tyre të jashtme të informacionit.

Vlerëso

Shkalla e informacionit është entropia mesatare për simbol. Për burime pa memorie, kjo është thjesht entropia e secilit simbol, ndërsa, në rastin e një procesi stokastik stacionar, ajo është:

$r=\lim _{n\to \infty }H(X_{n}|X_{n-1},X_{n-2},X_{n-3},\ldots );$

domethënë, entropia e kushtëzuar e një simboli duke marrë parasysh të gjitha simbolet e gjeneruara më parë. Për rastin më të përgjithshëm të një procesi që nuk është domosdoshmërisht stacionar, shpejtësia mesatare është:

$r=\lim _{n\to \infty }{\frac {1}{n}}I(X_{1},X_{2},\dots X_{n};Y_{1},Y_{2},\dots Y_{n});$

domethënë, kufiri i entropisë së përbashkët për simbol. Për burime stacionare, këto dy shprehje japin të njëjtin rezultat.

Shkalla e informacionit përcaktohet si më poshtë:

$r=\lim _{n\to \infty }{\frac {1}{n}}I(X_{1},X_{2},\dots X_{n};Y_{1},Y_{2},\dots Y_{n});$

Në teorinë e informacionit është e zakonshme të flitet për "shpejtësinë" ose "entropinë" e një gjuhe. Kjo është e përshtatshme, për shembull, kur burimi i informacionit është proza angleze. Shpejtësia e një burimi informacioni lidhet me redundancën e tij dhe sa mirë mund të kompresohet, që është subjekt i kodimit burimor.

Kapaciteti i kanalit

Komunikimet përmes një kanali është motivimi kryesor i teorisë së informacionit. Megjithatë, kanalet shpesh nuk arrijnë të sigurojnë një rindërtim të saktë të një sinjali; zhurma, periudhat e heshtjes dhe format e tjera të korruptimit të sinjalit shpesh e degradojnë cilësinë.

Merrni parasysh procesin e komunikimit përmes një kanali diskret. Një model i thjeshtë i procesit tregohet më poshtë:

${\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}$

Këtu $X$ përfaqëson hapësirën e mesazheve të transmetuara, dhe ${\textstyle Y}$ hapësira e mesazheve të marra gjatë një njësie kohe mbi kanalin tonë. Le të jetë p ( y | x ) funksioni i shpërndarjes së probabilitetit të kushtëzuar të ${\textstyle Y}$ dhënë $X$ Ne do ta konsiderojmë p ( y | x ) si një veti fikse të natyrshme të kanalit tonë të komunikimit (që përfaqëson natyrën e zhurmës së kanalit tonë). Pastaj shpërndarja e përbashkët e $X$ dhe ${\textstyle Y}$ përcaktohet plotësisht nga kanali ynë dhe nga zgjedhja jonë e f ( x ), shpërndarja kufitare e mesazheve që zgjedhim të dërgojmë në kanal. Nën këto kufizime, dëshirojmë të maksimizojmë shpejtësinë e informacionit, ose sinjalin, që mund të komunikojmë në kanal. Masa e përshtatshme për këtë është informacioni i ndërsjellë, dhe ky informacion maksimal i ndërsjellë quhet channel capacity dhe jepet nga:

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

Ky kapacitet ka vetinë e mëposhtme lidhur me komunikimin me shpejtësinë e informacionit R (ku R zakonisht është bit për simbol). Për çdo shpejtësi informacioni R < C dhe gabim kodimi ε > 0, për një N mjaftueshëm të madh, ekziston një kod me gjatësi N dhe shpejtësi ≥ R dhe një algoritëm dekodimi, i tillë që probabiliteti maksimal i gabimit në bllok është ≤ ε ; domethënë, është gjithmonë e mundur të transmetohet me një gabim blloku arbitrarisht të vogël. Përveç kësaj, për çdo shpejtësi R > C, është e pamundur të transmetohet me një gabim blloku arbitrarisht të vogël.

Kodimi i kanalit merret me gjetjen e kodeve pothuajse optimale që mund të përdoren për të transmetuar të dhëna një kanali me zhurmë me një gabim kodimi shumë të vogël me një shpejtësi afër kapacitetit të kanalit.

Kapaciteti i modeleve të veçanta të kanaleve

• Një kanal komunikimi analog me kohë të vazhdueshme i nënshtruar zhurmës Gaussiane — shih teoremën Shannon-Hartley .
• Një kanal binar simetrik (BSC) me probabilitet kryqëzimi p është një kanal binar hyrjeje, kanal binar daljeje që e përmbys bitin e hyrjes me probabilitet p . BSC ka një kapacitet prej 1 − H_b(p) bitësh për përdorim kanali, H_b është funksioni binar i entropisë me logaritmin bazë 2:

• Një kanal fshirjeje binar (BEC) me probabilitet fshirjeje p është një hyrje binar, kanal daljeje ternare. Daljet e mundshme të kanalit janë 0, 1 dhe një simbol i tretë 'e' i quajtur fshirje. Fshirja përfaqëson humbjen e plotë të informacionit në lidhje me një bit hyrjeje. Kapaciteti i BEC është 1 − p bit për përdorim kanali.

Kanale me memorie dhe informacion të drejtuar

Në praktikë, shumë kanale kanë memorie. Domethënë, në kohën $i$ kanali përshkruhet nga probabiliteti i kushtëzuar:$P(y_{i}|x_{i},x_{i-1},x_{i-2},...,x_{1},y_{i-1},y_{i-2},...,y_{1})$ Shpesh është më e përshtatshme të përdoret notacioni $x^{i}=(x_{i},x_{i-1},x_{i-2},...,x_{1})$ dhe atëherë kanali bëhet $P(y_{i}|x^{i},y^{i-1})$ Në këtë rast, kapaciteti jepet nga shkalla e informacionit të ndërsjellë dhe nga informacionit të drejtuar në rastin kur ka ose jo reagime (nëse nuk ka reagime, informacioni i drejtuar është i barabartë me informacionin e ndërsjellë).

Informacion i këmbyeshëm

Informacioni i zëvendësueshëm është ai lloj informacioni për të cilin mënyra e kodimit nuk ka rëndësi. Teoricienët klasikë të informacionit dhe shkencëtarët kompjuterikë merren kryesisht me informacionin e këtij lloji. Ndonjëherë quhet informacion i shqiptuar/i folshëm.

Zbatime në fusha të tjera

Përdorimet e inteligjencës dhe zbatimet e sekretit

Konceptet e teorisë së informacionit zbatohen në kriptografi dhe kriptanalizë. Njësia e informacionit e Turing-ut, ndalimi, u përdor në projektin Ultra, për të thyer kodin e makinës gjermane Enigma dhe duke përshpejtuar fundin e Luftës së Dytë Botërore në Evropë .Vetë Shannon përkufizoi një koncept të rëndësishëm që sot quhet distanca unikate .Bazuar në tepricën e tekstit të thjeshtë, ai përpiqet të japë një sasi minimale të tekstit të koduar të nevojshëm për të siguruar deshifrueshmëri unike.

Teoria e informacionit na çon të besojmë se është shumë më e vështirë të mbash sekretet sesa mund të duket fillimisht. Një sulm me forcë brutale mund të thyejë sisteme të bazuara në algoritme çelësash asimetrikë ose në metodat më të përdorura të algoritmeve çelësash simetrikë (ndonjëherë të quajtura algoritme çelësash sekretë), siç janë shifrat bllok . Siguria e të gjitha metodave të tilla vjen nga supozimi se asnjë sulm i njohur nuk mund t'i thyejë ato në një kohë praktike.

Siguria sipas teorisë së informacionit i referohet metodave të tilla si blloku i vetëm, të cilat nuk janë të ndjeshme ndaj sulmeve të tilla brutale. Në raste të tilla, informacioni i ndërsjellë pozitiv i kushtëzuar midis tekstit të thjeshtë dhe tekstit të koduar (i kushtëzuar nga çelësi ) mund të sigurojë transmetim të duhur, ndërsa informacioni i ndërsjellë i pakushtëzuar midis tekstit të thjeshtë dhe tekstit të koduar mbetet zero, duke rezultuar në komunikime absolutisht të sigurta. Me fjalë të tjera, një përgjues nuk do të përmirësonte përmirësonte hamendësimin e tij ose të saj për tekstin e thjeshtë duke fituar njohuri për tekstin e koduar, por jo për çelësin. Megjithatë, si në çdo sistem tjetër kriptografik, duhet treguar kujdes për të aplikuar saktë edhe metodat e sigurta teorikisht të informacionit; projekti Venona ishte në gjendje të thyente bllokët e vetëm që përdoreshin nga Bashkimi Sovjetik për shkak të ripërdorimit të papërshtatshëm të materialit kyç.

Gjenerimi i numrave pseudo të rastësishëm

Gjeneratorët e numrave pseudorandom janë gjerësisht të disponueshëm në bibliotekat e gjuhëve kompjuterike dhe programet e aplikimit. Ata janë, pothuajse universalisht, të papërshtatshëm për përdorim kriptografik pasi nuk i shmangen natyrës deterministe të pajisjeve dhe softuerëve modernë kompjuterikë. Një klasë e gjeneratorëve të përmirësuar të numrave të rastësishëm quhet gjeneratorë të numrave pseudorandom të sigurt kriptografikisht, por edhe ata kërkojnë fara të rastësishme jashtë softuerit për të funksionuar siç është menduar. Këto mund të merren nëpërmjet nxjerrësve, nëse bëhen me kujdes. Masa e rastësisë së mjaftueshme në nxjerrës është min-entropia, një vlerë e lidhur me entropinë Shannon përmes entropisë Rényi ; entropia Rényi përdoret gjithashtu në vlerësimin e rastësisë në sistemet kriptografike. Megjithëse të lidhura, dallimet midis këtyre masave nënkuptojnë se një ndryshore e rastësishme me entropi të lartë Shannon nuk është domosdoshmërisht e kënaqshme për përdorim në një nxjerrës dhe kështu për përdorime kriptografike.

Eksplorim sizmik

Një zbatim i hershëm komercial i teorisë së informacionit ishte në fushën e eksplorimit sizmik të naftës. Puna në këtë fushë bëri të mundur heqjen dhe ndarjen e zhurmës së padëshiruar nga sinjali i dëshiruar sizmik. Teoria e informacionit dhe përpunimi dixhital i sinjalit ofrojnë një përmirësim të madh të rezolucionit dhe qartësisë së imazhit krahasuar me metodat e mëparshme analoge.

Semiotikë

Semiotistët Doede Nauta dhe Winfried Nöth konsideruan Charles Sanders Peirce si krijuesin e një teorie informacioni në veprat e tij mbi semiotikën. Nauta e përcaktoi teorinë semiotike të informacionit si studimin e " proceseve të brendshme të kodimit, filtrimit dhe përpunimit të informacionit".

Koncepte nga teoria e informacionit, të tilla si redundanca dhe kontrolli i kodit, janë përdorur nga semiotistë si Umberto Eco dhe Ferruccio Rossi-Landi për të shpjeguar ideologjinë si një formë të transmetimit të mesazhit ku një klasë shoqërore mbizotëruese e lëshon mesazhin e saj duke përdorur shenja që shfaqin një shkallë të lartë të redundancës, në mënyrë që vetëm një mesazh të dekodifikohet midis një përzgjedhjeje të atyre konkurruese.

Organizimi i integruar i procesit të informacionit nervor

Metodat teorike sasiore të informacionit janë aplikuar në shkencën kognitive për të analizuar organizimin e integruar të procesit të informacionit nervor në kontekstin e problemit të lidhjes në neuroshkencën kognitive . Në këtë kontekst, ose përcaktohet një masë teorike e informacionit, siç janë functional clusters (modeli i grupimit funksional dhe hipoteza e bërthamës dinamike (DCH) e Gerald Edelman dhe Giulio Tononi) ose effective information ( teoria e informacionit të integruar (IIT) e vetëdijes e Tononi-t ), (Këto masa bazohen në organizimin e rindërtimit të proceseve, sinkronizimin e aktivitetit neurofiziologjik midis grupeve të popullatës neuronale.), ose masa e minimizimit të energjisë së lirë në bazë të metodave statistikore ( parimi i energjisë së lirë (FEP) i Karl J. Friston, një masë teorike e informacionit që pohon se çdo ndryshim adaptiv në një sistem të vetëorganizuar çon në një minimizim të energjisë së lirë, dhe hipoteza Bayesiane e trurit ).

Aplikime të ndryshme

Teoria e informacionit ka zbatime edhe në kërkimin e inteligjencës jashtëtokësore, vrimat e zeza, bioinformatikën, dhe lojërat e fatit .