Teorya ng impormasyon

Ang Teoriya ng impormasyon ay sangay ng nilalapat na matematika at inhinyerong elektrikal na pag-aaral ng kwantipikasyon o pagsasabilang ng isang impormasyon. Ang teoriyang ito ay binuo ni Claude E. Shannon upang hanapin ang mga pundamental na hangganan sa mga operasyon ng pagpoproseso ng signal gaya ng kompresyon, pag-iimbak at pagpapadala ng datos. Simula ng pagkakalikha nito, ito ay lumawak upang humanap ng mga aplikasyon sa maraming mga iba pang sakop kabilang ang inperensiyang estadistikal, pagpoproseso ng natural na wika, kriptograpiya, mga network na iba sa mga network ng komunikasyon gaya na sa neurobiolohiya,^[1] ebolusyon ^[2] at tungkulin ^[3] ng mga kodigong molekular, seleksiyon ng modelo^[4] sa ekolohiya, thermal na pisika,^[5] pagkukwentang quantum, deteksiyon ng plagiarismo^[6] at iba pang mga anyo ng analisis ng datos.^[7]

Ang isang mahalagang sukat ng impormasyon ay tinatawag na entropiya na karaniwang inilalarawan ng aberaheng bilang ng mga bit na kailangan upang iimbak o ihatid ang isang simbolo sa isang mensahe. Ang entropiya ay nagkakwantipika ng walang katiyakan na sangkot sa paghuhula ng halaga ng isang randomang bariabulo. Halimbawa, ang pagtukoy ng kalalabasan ng isang patas na pagbaliktad ng barya(dalawang magkatumbas na malamang na kalalabasan) ay nagbibigay ng kaunting impormasyon(mas mababang entropiya) kesa sa pagtukoy ng kalalabasan mula sa pag-ikot ng isang Padron:Dice (anim na magkatumbas na malamang na kalalabasan).

Ang mga aplikasyon ng pundamental na mga paksa ng teoriya ng impormasyon ay kinabibilangan ng walang kawalang kompresyon ng datos(lossless data compression)(e.g. ZIP files), may kawalang kompresyon ng datos(lossy data compression) (e.g. MP3s and JPGs), at pagkokodigo ng channel (e.g. for Digital Subscriber Line (DSL)). Ang larangang ito ay nasa interseksiyon ng matematika, estadistika, agham pang-kompyuter, pisika, neurobiolohiya at inhinyeryang elektrikal. Ang epekto nito ay mahalaga sa pagtatagumpay ng mga misyong Voyager sa malalim na kalawakan, sa imbensiyon ng compact disc, pagiging posible ng mga mobile phone, pagkakabuo ng internet, pag-aaral ng linguistika at persepsiyong pang-tao, pag-unawa ng mga itim na butas at marami pang ibang mga larangan. Ang mahalagang mga pang-ilalim na larangan ng teoriya ng impormasyon ay kinabibilangan ng pagkokodigo ng pinagkunan(source coding), pagkokodigo ng channel(channel coding), teoriya ng algoritmikong kompleksidad, seguridad na impormasyon teoretiko at mga sukat ng impormasyon.

Konsepto

Ang pangunahing mga konsepto ng teoriya ng impormasyon ay mauunawaan sa pamamagitan ng pagsasaalang alang ng pinakamalawak na mga paraan ng komunikasyong pantao:wika. Ang dalawang mahalagang mga aspeto ng isang maikling wika ang sumusunod: Una, ang pinakakaraniwang mga salita(e.g., "a", "the", "I") ay dapat mas maiksi kesa sa hindi karaniwang mga salita(e.g., "roundabout", "generation", "mediocre",) upang ang mga pangungusap ay hindi maging labis na mahaba. Ang gayong pagpapalit sa haba ng salita ay analogo sa kompresyon ng datos at isang mahalagang aspeto ng pagkokodigo ng pinagkunan. Ikalawa, kung ang isang bahagi ng pangungusap ay hindi narinig o maling narinig dahil sa ingay gaya halimbawa ng pagdaan ng isang sasakyan, ang nakikinig ay dapat mabatid pa rin ang kahulugan ng saligang mensahe. Ang gayong kasaganaan ay mahalaga sa sistema ng elektronikong komunikasyon gaya ng sa wika. Ang angkop na pagtatayo ng gayong kasaganaan sa mga komunikasyon ay ginagawa sa pamamagitan ng pagkokodigo ng channel. Ang pagkokodigo ng pinagkunan at pagkokodigo ng channel ang mga pundamental na pinag-uukulan ng teoriya ng impormasyon.

Dapat maunawaan na ang mga pinag-uukulan ay walang kinalaman sa kahalagahan ng mga mensahe. Halimbawa, ang isang platitudo gaya ng "Salamat, bumalik ka ulit" ay mas mahabang sabihin o isulat kesa sa mahalagang pagsusumamo na "Tawagin ang ambulansiya!" samantalang ang huli ay mas mahalaga at mas makahulugan sa maraming mga konteksto. Gayunpaman, ang teoriya ng impormasyon ay hindi nagsasaalang alang ng kahalagahan ng mensahe o kahulugan dahil ang mga ito ay bagay ng kalidad ng datos kesa sa kantidad at pagiging mababasa ng datos na ang huli ay tanging matutukoy sa pamamagitan ng mga probabilidad.

Ang teoriya ng impormasyon ay pangkalahatang itinuturing na itinatag noong 1948 ni Claude Shannon sa kanyang seminal na akdang "A Mathematical Theory of Communication". Ang sentral na paradigm ng klasikong teoriyang impormasyon ang problemang pag-iinhinyerya ng transmisyon ng impormasyon sa ibabaw ng isang maingay na channel. Ang pinakapundamental na mga resulta ng teoriyang ito ay ang teorema ng pagkokodigo ng pinagkunan ni Shannon na nagpapatunay na sa aberahe, ang bilang ng mga bit na kailangan upang ikatawan ang resulta ng isang hindi matiyak na pangyayari ay ibinigay ng entropiya nito at ang teorema ng pagkokodigo ng maingay na channel ni Shannon na nagsasaad na ang isang maasahang komunikasyon ay posible sa ibabaw ng mga maingay na channel sa kondisyong ang rate ng komunikasyon ay nasa ilalim ng isang threshold na tinatawag na kapasidad ng channel. Ang kapasidad ng channel ay maaaring pakitunguhan sa pagsasanay sa pamamagitan ng angkop na pagkokodigo at pagdedekodigo ng mga sistema.

Ang teoriya ng impormasyon ay malapit na nauugnay sa isang koleksiyon ng puro at nilalapat na mga disiplina na inimbestigahan at napaliit sa pagsasanay na pagiinhinyerya sa ilalim ng iba't ibang mga rubric sa buong mundo sa loob ng nakaraang kalahating sigo o higit pa: mga adaptipong sistema, mga antisipatoryong sistema, intelihensiyang artipisyal, mga sistemang kompleks, cybernetika, impormatika, pagkatuto ng makina kasama ng mga agham ng mga sistema ng maraming mga deskripsiyon. Ang teoriya ng impormasyon ay isang malawak at malalim na teoriyang matematikal na may katumbas na malawak at malalim na mga aplikasyon na ang pinakamahalagang larangan ang teoriya ng pagkokodigo.

Ang teoriya ng pagkokodigo ay nauukol sa paghahanap ng mga hayagang paraang tinatawag na mga kodigo(codes) ng pagpaparami ng kaigihan at pagpapaliit ng net na kamaliang(error) rate ng komunikasyon ng datos sa ibabaw ng isang maingay ng channel tungo sa malapit sa hangganan na pinatunayan ni Shannon na ang maksimum na posible para sa channel na ito. Ang mga kodigong ito ay maaaring hatiin sa mga paraang kompresyon ng datos(source coding) at pagtutuwid ng kamalian(error correction/channel coding). Sa huling kaso, tumagal ng maraming mga tao upang hanapin ang mga paraan na napatunayan ng akda ni Shannon na posible. Ang ikatlong uri ng mga kodigo ng teoriya ng impormasyon ang mga algoritmong kriptograpiko (ang parehong mga kodig) at sipero. Ang mga konsepto, paraan at resulta mula sa teoriya ng pagkokodigo at teoriya ng impormasyon ay malawak na ginagamit sa kriptograpiya at kriptanalisis.

Ang teoriya ng impormasyon ay ginagamit rin sa pagkuha ng impormasyon, pagtitipon ng intelihensiya, pagsusugal, estadistika at kahit sa komposisyon ng musika.

Kasaysayan

Ang mahalagang pangyayari na nagtatag ng disiplina ng teoriya ng impormasyon at nagdala rito sa agarang pandaigdigang atensiyon ang publikasyo ng klasikong papel ni Claude E. Shannon na "A Mathematical Theory of Communication" in the Bell System Technical Journal noong Hulyo at Oktubre 1948.

Bago ng papel na ito, ang limitadong mga ideyang impormasyon teoretiko ay nabuo sa Bell Labs na ang lahat ng ito ay hindi hayagang nagpapalagay ng mga pangyayari ng magkatumbas na probabilidad. Ang papel ni Harry Nyquist noong 1924 na Certain Factors Affecting Telegraph Speed ay naglalaman ng isang teoretikal na seksiyon na nagkakwantipika ng intelihensiya at bilis linya kung saan ito ay maaaring ipadala sa pamamagitan ng isang sistema ng komunikasyon na nagbibigay ng relasyong $W=K\log m$ , kung saan ang W ang bilis ng transmisyon ng intelihensiya, ang m ang bilang ng iba't ibang mga lebel ng boltahe na pagpipilian sa bawat hakbang npanahon at ang K ay isang konstante. Ang papel ni Ralph Hartley noong 1928 na Transmission of Information ay gumamit ng impormasyon bilang isang masusukat na kantidad na nagpapakita ng kakayahan ng tumatanggap na makilala ang isang sekwensiya ng mga simbolo mula sa iba pa kaya ito ay nagkakwantipiko ng impormasyon bilang $H=\log S^{n}=n\log S$ kung saan ang S ang bilang ng mga posibleng simbol at ang n ang bilang ng mga simbol sa isang transmisyon. Ang natural na unit ng impormasyon kung gayon ay isang decimal na digit na kalaunang muling pinangalanan na harley sa kanyang karangalan bilang unit o skala o sukat ng impormasyon. Si Alan Turing noong 1940 ay gumamit ng mga parehong ideya bilang bahagi ng analisis estadistikal ng pagbasag ng mga sipero ng Enigma na ginamit ng Alemanyang Nazi noong Ikalawang Digmaang Pandaigdig.

Ang karamihan ng matematika sa likod ng teoriya ng impormasyon sa mga pangyayari ng iba't ibang mga probabilidad ay binuo para sa larangang termodinamika nina Ludwig Boltzmann at J. Willard Gibbs. Ang ugnayan sa pagitan ng entropiyang impormasyon teoretika at entropiyang termodinamiko kabilang ang mahalagang mga kontribusyon ni Rolf Landauer noong mga dekada 1960 ay ginalugad sa Entropy in thermodynamics and information theory.

Sa rebolusyonaryo at bagong papel ni Shano na papel na labis na nakumpleto sa Bell Labs sa dulo ng 1933, ipinakilala ni Shanon sa unang pagkakataon ang kwalitatibo at kwantitatibong modelo ng komunikasyon bilang isang prosesong estadistikal na sumasalig sa teoriya ng impormasyin na nagbubukas ng asersiyon na

"The fundamental problem of communication is that of reproducing at one point, either exactly or approximately, a message selected at another point."(Ang pundamental na problema ng komunikasyon ay sa muling paglikha sa isang punto, eksakto man o sa pagtatantiya, ang isang mensahe na napili sa isa pang punto)

Dito ay dumating ang mga ideya na

ang entropiya ng impormasyon at redundansiya ng isang pinagkunan at kalahagahan nito sa pamamagitan ng teorema ng pagkokodigo ng pinagkunan;
Ang mutwal na impormasyon at ang kapasidad ng channel ng isang maingay na channel kabilang ang pangako ng isang perprektong malaya sa kawalang komunikasyon na ibinigay ng teorema ng pagkokodigo ng maingay na channel;
ang praktikal na resulta ng batas na Shannon-Harley para sa kapasidad ng channel ng isang channel na Gaussian; gayundin
ang bit na isang bagong paraan ng pagtingin sa pinakapundamental na unit ng impormasyon.

Mga kantidad ng impormasyon

Ang teoriya ng impormasyon ay batay sa teoriya ng probabilidad at estadistika. Ang pinakamahalagang mga kantiad ng impormasyon ang entropiya na impormasyon sa isang randomang bariabulo, at mutwal na impormasyon na halaga ng impormasyon na karaniwan sa pagitan ng dalawang mga randomang bariabulo. Ang nakaraang kantidad ay nagpapakita kung paanong madali ang datos ay masisiksik samantalang ang huli ay maaaring gamitin upang hanapin ang rate ng komunikasyon sa kahabaan ng isang channel.

Ang pagpili ng baseng logaritmiko sa sumusunod na mga pormula ay tumutukoy sa mga sukat ng entropiya ng impormasyon na ginagamit. Ang pinakakaraniwang unit ng impormasyon ang bit batay sa binaryong logaritmo. Ang iba pang mga unit ay kinabibilangan ng nat na batay sa natural na logaritmo at harley na batay sa karaniwang logaritmo.

Sa sumusunod, ang isang ekspresyon sa anyong $p\log p\,$ ay itinuturing sa konbensiyon na katumbas ng sero kapag ang i $p=0.$ Ito ay makatwiran dahil ang $\lim _{p\rightarrow 0+}p\log p=0$ para sa anumang baseng logaritmiko.

Entropiya

Entropiya ng isang pagsubok na Bernoulli bilang punsiyon ng tagumpay ng probabilidad na kadalasang tinatawag na binaryong entropiyang punsiyon,

H_{\mbox{b}}(p)

. Ang entropiya namamaksima sa 1 bit kada pagsubok kapag ang dalawang mga posibleng kalalabasan ay magkatumbas na malamang gaya ng sa walang kinikilingang paghagig ng isang barya.

Ang entropiya na $H$ ng isang diskretong randomang bariabulo na $X$ ay isang sukat ng halaga ng walang katiyakan na nauugnay sa halaga ng $X$ .

Ipagpalagay na ang isa ay nagpapadala ng 1000 mga bit(mga 0 at 1). Kung ang mga bit na ito ay alam na bago ang transmisyon(na maging isang tiyak na halaga na may absolutong probabilidad), ang lohika ay nagdidikta na walang impormasyon ang naipadala. Gayunpaman, kung ang bawat isa ay magkatumbas at independiyenteng malamang na maging 0 o 1, ang 1000 mga bit(sa kahulugang impormasyon teoretiko) ay naipadala. Sa pagitan ng dalawang mga kasukdulang ito, ang impormasyon ay maaaring ikwantipika sa sumusunod. Kung ang $\mathbb {X}$ ang hanay ng lahat ng mga mensaheng $\{x_{1},...,x_{n}\}$ na ang $X$ ay maaaring maging at ang $p(x)$ ang probabilidad ng $x$ sa ibinigay na isang $x\in \mathbb {X}$ , kung gayon, ang entropiya ng $X$ ay inilalarawang:^[8]

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

Dito, ang $I(x)$ ang sariling-impormasyon na kontribusyong entropiya ng indbidwal na mensahe at ang $\mathbb {E} _{X}$ ang inaasahang halaga. Ang mahalagang katangian ng entropiya ay ito ay minamaksima kapag ang lahat ng mga espasyon ng mensahe ay equiprobable $p(x)=1/n$ ,—i.e., pinaka hindi mahuhulaan-kung saang kaso ang $H(X)=\log n$ .

Ang espesyal na kaso ng entropiya ng impormasyon para sa isang randomang bariabulo na may dalawang mga kalalabasan ang binaryong entropiyang punsiyon na karaniwang kinukuha sa logaritmikong baseng 2:

H_{\mbox{b}}(p)=-p\log _{2}p-(1-p)\log _{2}(1-p).\,

Magkasanib na entropiya

Ang magkasanib na entropiya ng dalawang mga diskretong randomang baribulong $X$ at $Y$ ay tanging ang entropiya ng kanilang pagpapares: $(X,Y)$ . Ito ay nagpapahiwatig na kung ang $X$ at ang $Y$ ay independiyente, kung gayon ang kanilang magkasanib na entropiya ang suma ng kanilang mga indibidwal na entropiya.

Halimbawa, kung ang $(X,Y)$ ay kumakatawan sa posisyon ng piyesa ng chess — ang $X$ ang row at ang $Y$ ang column, kung gayon, ang magkasanib na entropiya ng row of piyesa at column ng piyesa ay ang entropiya ng posisyon ng piyesa.

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

Sa kabila ng parehong notasyon, ang magkasanib na entropiya ay hindi dapat ikalito sa krus na entropiya.

Kondisyonal na entropiya(ekwibokasyon)

Ang kondisyonal na entropiya o kondisyonal na kawalang katiyakan ng $X$ sa ibinigay na randomang baribaulong $Y$ (na tinatawag ring equivocation ng $X$ tungkol sa $Y$ ) ang aberaheng kondisyonal na entropiya sa ibabaw ng $Y$ :^[9]

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(x,y)}{p(y)}}.

Dahil ang entropiya ay maaaring ikondisyon sa isang randomang bariabulo o sa randomang baribaulo na isang halaga, ang isang pag-iingat ay dapat kunin upang hindi ikalito ang dalawang mga depinisyon ng kondisyonal na entropiyang ito na ang huli ay nasa mas karaniwang paggamit. Ang basikong katangian ng anyong ito ng konsiyonal na entropiya ang:

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

Mutal na impormasyon(transimpormasyon)

Ang Mutual na impormasyon ay sumusukat sa halaga ng impormasyon na maaaring matamo tungkol sa isang randomang baribulo sa pamamagitan ng pagmamasid pa ng isa. Ito ay mahalaga sa komunikasyon kung saan ito ay maaaring gamitin upang imaksima ang halaga ng impormasyon na pinagsasaluhan sa pagitan ng ipinadala at tinanggap na mga signal. Ang mutual na impormasyon na $X$ na relatibo sa $Y$ ay ibinigay ng:

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

kung saan ang $SI$ (Spesikong mutual na Impormasyon) ang pointwise mutual na impormasyon.

Ang isang basikong katangian ng mutual na impormasyon ang

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

Na ang ibig sabih, kung alam ang Y, maaari tayong makatipid ng aberaheng $I(X;Y)$ mga bit sa pagkokodig ng X kumpara sa hindi pagkaalam ng Y.

Ang mutual na impormasyon ay isang symmetriko:

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

Ang mutual na impormasyon ay maaaring ilarawan bilang aberahang Diberhensiyang Kullback–Leibler (natamong impormasyon) ng distribusyong posterior na probabilidad ng X sa ibinigay na halaga ng Y sa prior na distribusyon sa X:

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

Sa ibang salita, ito ay sukat kung gaano sa aberahe ang distribusyong probabilidad sa X ay magbabago kung tayo binigyan ng halagang Y. Ito ay kadalasang muling kinukwenta bilang diberhensiya mula sa produkto ng marhinal na mga distribusyon sa aktuwal na magkasanib na distribusyong:

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

Ang mutual na impormasyon ay malapit na kaugnay ng pagsubok na rasyong pagiging malamang(likelihood-ratio test) sa konteksto ng mga tablang kontinhensiya at distribusyong multinomial at Pearson's χ² test: ang mutual na impormasyon ay maaaring ituring na estadistika sa pagtatatya ng independiyensiya ng mga bariabulo at mayroong isang mahusay na nailarawan na asymptotikong distribusyon.

Diberhensiyang Kullback–Leibler (pagtatamo ng impormasyon)

Ang diberhensiyang Kullback–Leibler (o information divergence, information gain, o relative entropy) ay isang paraan ng pagkukumpara ng dalawang mga distribusyon: ang isang "totoo" distribusyong probabilidad na p(X), at isang arbitraryong distribusyong probabilidad na q(X). Kung ating sisiksikin ang datos sa paraang nagpapalagay na ang q(X) ang distribusyong sumasalig sa ilang datos kung sa katotohanan ang p(X) ang tamang distribusyon, ang diberhensiyang Kullback–Leibler ang bilang ng aberaheng karagdagang mga bit kada datum na kailangan para sa kompresyon(pagsisiksik). Kaya ito ay inilalarawan na

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

Bagama minsang ginagamit ito bilang 'metrikong distansiya', ang diberhensiyang KL ay hindi totoong metriko dahil ito ay hindi symmetriko at hindi sumasapat sa inekwalidad na tatsulok(na gumagawa ditong isang semi-quasimetriko).

Diberhensiyang Kullback–Leibler ng isang prior mula sa katotohanan

Ang isa pang interpretasyon ng diberhensiyang KL ay ito: ipagpalagay na ang isang bilang na X ay huhuguting randoma mula sa isang diskretong hanay na may distribusyong probabilida na p(x). Kung alam ni Alice ang totoong distribusyong p(x), samantalang si Bob ay naniniwalang(may prior) na ang distribusyon ay q(x), kung gayon, si Bob ay mas masusupresa kesa kay Alice sa aberahe sa pagkita ng halaga ng X. Ang diberhensiyang KL ang (obhektibong) inaasahang halaga ng (subhektibon) surprisal ni Bob menos ng surprisal ni Alice na sinukat ng mga bit kung ang log ay nasa baseng 2. sa paraang ito, ang lawak kung saan ang prior ni Bob ay "mali" ay maaaring ikwantipika sa mga termino kung paanong "hindi kinakailangang masurpresa" na inaasahang gawin siya.

Iba pang mga kantidad

Ang iba pang mahalagang mga kantidad na impormasyon teoretiko ay kinabibilangan ng entropiyang Rényi (na isang paglalahat ng entropiya), diperensiyal na entropiya(na paglalarawan ng mga kantidad ng impormasyon sa mga tuloy tuloy na distribusyon) at kondisyonal na mutual na impormasyon.

Teoriya ng pagkokodigo

Ang teoriya ng pagkokodigo ay isa sa pinakamahalaga at direktang mga aplikasyon ng teoriya ng impormasyon. Ito ay maaaring hatiin sa pagkokodigo ng pinagkunan at pagkokodigo ng channel. Sa paggamit ng estadistikal na deskripisyon para sa datos, ang teoriya ng impormasyon ay nagkakwantipika ng bilang ng mga bit na kailangan upang ilarawan ang datos na entropiya ng impormasyon ng pinagkunan.

Kompresyon ng datos(pagkokodigo ng pinagkunan); May dalawang mga pormulasyon para sa problema ng kompresyon:

walang kawalang kompresyon ng datos(lossless data compression): ang datos ay dapat eksaktong muling buuin;
may kawalang kompresyon ng datos(lossy data compression): naglalaan ng mga bit na kailangan upang muling buuin ang datos sa loob ng isang natukoy na lebel ng pidelidad na sinukat ng punsiyon ng distorsiyon. Ang pangilalim na hanay ng teoriya ng impormasyong ito ay tinatawag na teoriya ng rate-distorsiyon.

Nagtutuwid ng mga kamaliang kodig(pagkokodigo ng channel): Bagaman ang kompresyon ng datos ay nag-aalis ng hangga't posibleng redundansiya, isang kodigong nagtutuwid ng kamalian ay nagdadagdag ng tama lamang na uri ng redundansiya(i.e., pagtutuwid ng kamalian) na kailangan upang ipadala ang datos na maigi at tapat sa kahabaan ng isang maingay na channel.

Ang dibisyon ng teoriya ng pagkokodigo sa kompresyon at transmisyon ay pinangangatwiran ng mga teorema ng transmisyin ng impormasyon o mga teorema ng paghihiwalay ng pinagkunang channel na nangangatwiran sa paggamit ng mga bit bilang pangkalahatang kurensiya ng impormasyon sa maraming mga konteksto. Gayunpaman, ang mga teoremang ito ay totoo lamang sa sitwasyon kung saan ang nagpapadalang gumagamit ay nagnanais na makipagtalastasan sa isang tumantanggap ng gumagamit. Sa mga eksenang may higit sa isang tagapagpadala(ang maraming magagamit na channel), ang higit sa isang tagatanggap (ang broadcast channell) o namamagitang mga katulong (ang relay channel) o sa pangkalahatang ang mga network, ang kompresyon na sinundan ng transmsiyon ay hindi na optimal. Ang teoriya ng impormasyon ng network ay tumutukoy sa maraming ahenteng mga modelo ng komunikasyon.

Teoriya ng pinagkunan

Ang anumang proseso na lumilikha ng sunod sunod na mga mensahe ay maaaring ituring na pinagkunan ng impormasyon. Ang isang walang memoryang pinagkaunan ay isa kung saan ang bawat mensahe ay independiyente magkatulad na ipinamahaging mga randomang bariabulo samantalang ang mga katangian ng ergodisidad at hindi gumagalaw ay nagtatkda ng mas pangkalahatang mga pagtatakda. Ang lahat ng gayong mga pinagkunan ay stokastiko. Ang mga terminong ito ay maiging pinag-aralan sa mga sarili nito sa labas ng teoriya ng impormasyon.

Rate

Ang rate ng impormasyon ang aberaheng entropiya kada simbol. Para sa mga walang memoryang pinagkuna, ito ay isa lamang entropiya ng bawat simbol samantalang sa kaso ng hindi gumaglawa ng prosesong stokastiko, ito ay

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

na ang ibig sabihin, ang kondisyonal na entropiya ng isang simbolo sa ibinigay na lahat ng mga nakaraang simbolong nalikha. Para sa mas pangkalahatang kaso ng isang proseso na hindi kinakailangang hindi gumagalaw, ang aberaheng rate ay

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

na ang ibig sabihin, ang hangganan ng magkasanib na entropiya kada simbolo. Para sa mga pinagkunang hindi gumagalaw, ang dalawang mga ekspresyon ito ay nagbibigay ng parehong resulta.^[10]

Karaniwan sa teoriya ng impormasyon na magsalita tungkol sa rate o entropiya ng isang wika. Ito ay angkop halimbawa kapag ang pinagkunan ng impormasyon ay ang prosang Ingles. Ang rate ng isang pinagkunan ng impormasyon ay kaugnay sa redundansiya nito at kung gaano ito masisiksik na paksa ng pagkokodigo ng pinagkunan.

Kapasidad ng channel

Ang mga komunikasyon sa ibabaw ng isang channel gaya ng sa isang kableng ethernet ang pangunahing motibasyon ng teoriya ng impormasyon. Gayunpaman, gaya ng alam ng sinuman na nakagamit ng isang telepono(mobile o landline), ang gayong mga channel ay kadalasang nabibigong lumikha ng eksaktong rekonstruksiyon ng isang signal. Ang ingay, mga yugto ng katahimikan, at iba pang mga anyo ng korupsiyon ng signal ay kadalasang sumisira sa kalidad. Gaanong impormasyon ay isa ay maaasahang ipadala sa ibabaw ng isang maingay o hindi pepektong channel?

Isaalang ang ang proseso ng mga komunikasyon sa ibabaw ng isang diskretong channel. Ang isang simpleng model ng proseso ay pinapakita sa ibaba:

Dito ang X ay kumakatawan sa espasyon ng mga mensaheng ipinadala at ang Y ang espasyo ng mga mensaheng natanggap sa isang unit na panahon sa ibabaw ng ating channel. Itakda ang $p(y|x)$ na maging distribusyong kondisyonal na probabildiad ng Y sa ibinigay na X. Ating ituturing ang $p(y|x)$ na likas na nakapirmeng katangian ng ating channel ng mga komunikasyon(na kumakatawan sa kalikasan ng ingay ng ating channel). Kung gayon, ang magkasanib na distribusyon ng X at Y ay buong matutukoy ng ating channel at sa ating piniling $f(x)$ , ang marhinal na distribusyon ng mga mensaheng ating pinili na ipadala sa ibabaw ng channel. Sa ilalim ng mga pagtatakdang ito, ating nais na imaksima ang rate ng impormasyon o ang signal na ating ipapadala sa ibabaw ng channel. Ang angkop na sukat para dito ang mutual na impormasyon at ang maksimun na mutual na impormasyong ito ay tinatawag na kapasidad ng channel at ibinigay ng:

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

Ang kapasidad na ito ay may sumusunod na katangiang kaugnay ng pagpapadala sa rate ng impormasyon na R (kung saan ang R ay karaniwang mga bit kada simbolo). Para sa anumang rate ng impormasyon na R < C at kamalian ng pagkokodigong ε > 0, para sa sapat na malaking N, may umiiral na isang kodigo ng habang N at rate na ≥ R at isang nagdedekodigong algoritmo sa paraang ang maksimal na probabilidad ng kamaliang bloke ay ≤ ε; na ang ibig sabihin, palaging posible na ipadala ang isang arbitraryong maliit na kamaliang bloke. Sa karagdagan, para sa anumang rate na R > C, imposible na magpadala na may arbitraryong maliit na kamaliang bloke.

Ang pagkokodigo ng channel ay umuukol sa paghahanap ng gayong malapit sa optimal na mga kodigo na maaaring gamitin upang ipadala ang datos sa ibabaw ng isang maingay na channel na may isang maliit na kamalian ng pagkokodigo sa rate na malapit sa kapasidad ng channel.

Kapasidad ng partikular na mga modelo ng channel

Ang isang tuloy tuloy na panahong analog na channel ng mga komunikasyon na napapasailalim ng ingay na Gaussian.

Ang isang binaryong simmetrikong channel na may probabilidad na crossover na p ay isang binaryong input, binaryong output channel na nagbabaliktad ng input bit na may probabilidad na p. Ang BSC ay may kapasidad na $1-H_{\mbox{b}}(p)$ mga bit kada gamit ng channel kung saan ang $H_{\mbox{b}}$ ang binaryong entropiyang punsiyon sa baseng 2 logartimo:

Ang isang binaryong pagbuburang channel(BEC) na may pagbuburang probabilidad na p ay isang binaryong iput, ternaryong output channel. Ang mga posibleng channel output ay 0, 1, at isang ikatlong simbolong 'e' na tinatawag na erasure. Ang erasure ay kumakatawan sa buong kawalan ng impormasyon tungkol sa input bit. Ang kapasidad ng BEC ay 1 - p kada paggamit ng channel.

Mga aplikasyon sa ibang mga larangan

Mga gamit na intelihensiya at mga aplikasyon ng kalihiman

Ang mga konseptong impormasyon teoretiko ay lumalapat sa kriptograpiya at kriptanalisis. Ang unit ng impormasyon ni Alan Turing na ban, ay ginamit sa proyektong Ultra na bumabasg making Enigma ng Alemanyang Nazi na nagpabilis ng pagwawakas ng Ikalawang Digmaang Pandaigdig sa Europa. Mismong si Shanno ay naglarawan ng mahalagang konseptong tinatawag ngayong distansiyang unisidad. Batay sa redundansiya ng plaintext, ito ay nagtatangka na magbigay ng minimum na halaga ng ciphertext na kailangan upang masiguro ang natatanging desiperabilidad.

Ang teoriya ng impormasyon ay nagtutulak sa atin na maniwalang mas mahirap na panatilihin ang mga sikteto kesa sa unang tingin. Ang isang atakeng brutong pwersa ay maaaring bumasag ng mga sistema batay sa asymmetrikong susing mga algoritmo o sa karamihan ng karaniwang ginagamit na mga paraang ng simmetrikong susisng mga algoritmo(na minsang mga sikretong susing algoritmo) gaya ng mga blokeng sipero. Ang seguridad ng lahat ng gayong mga paraang ay kasalukuyang nagmumula sa asumpsiyon na walang alam na atake ang maaaring bumasag dito sa isang praktikal na halaga ng panahon.

Ang seguridad na impormasyon teoretiko ay tumutukoy sa mga paraan gaya ng isang beses na pad na hindi marupok sa gayong mga atakeng brutong pwersa. Sa gayong mga kaso, ang positibong kondisyonal na mutual impormasyon sa pagitan ng plaintext at ciphertext (na nakondisyon sa susi) ay maaaring sumiguro ng angkop na transmsiyon samantalang ang hindi kondisyonal na mutual impormasyon sa pagitan ng plaintext at ciphertext ay nananatiling seor na nagreresulta sa absolutong seguradong mga komunikasyon. Sa ibang salita, ang isang nakinig ng mensahe(eavesdropper) ay hindi magagawang pabutihin ang kanyang paghula ng plaintext sa pamamagitan ng pagtatamo ng kaalaman ng ciphertext ngunit hindi ng susi. Gayunpaman, gaya sa anumang ibang mga sistemang kriptograpiya, ang pag-iingat ay dapat gamit upang tamang mailapat ang kahit mga impormasyon teoretikong seguradong paraan. Ang proyektong Verona ay nagawang basagin ang mga isang beses na pad ng Unyong Soviet sanhi ng kanilang hindi angkop na paggamit ng susing materyal.

Mga sanggunian

↑ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).
↑ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
↑ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Naka-arkibo 2012-02-04 sa Wayback Machine., Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
↑ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
↑ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620
↑ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories Naka-arkibo 2007-10-07 sa Wayback Machine., Scientific American 288:6, 76-81
↑ David R. Anderson (1 Nobyembre 2003). "Some background on why people in the empirical sciences may want to better understand the information-theoretic methods" (PDF). Inarkibo mula sa orihinal (pdf) noong 2011-07-23. Nakuha noong 2010-06-23.{{cite web}}: CS1 maint: date auto-translated (link)
↑ Fazlollah M. Reza (1961, 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2. {{cite book}}: Check date values in: |year= (tulong)
↑ Robert B. Ash (1965, 1990). Information Theory. Dover Publications, Inc. ISBN 0-486-66521-6. {{cite book}}: Check date values in: |year= (tulong)
↑ Jerry D. Gibson (1998). Digital Compression for Multimedia: Principles and Standards. Morgan Kaufmann. ISBN 1-55860-369-7.{{cite book}}: CS1 maint: date auto-translated (link)

[1] F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).

[2] . Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314

[3] Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Naka-arkibo 2012-02-04 sa Wayback Machine., Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122

[4] Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.

[5] Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620

[6] Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories Naka-arkibo 2007-10-07 sa Wayback Machine., Scientific American 288:6, 76-81

[7] David R. Anderson (1 Nobyembre 2003). "Some background on why people in the empirical sciences may want to better understand the information-theoretic methods" (PDF). Inarkibo mula sa orihinal (pdf) noong 2011-07-23. Nakuha noong 2010-06-23.{{cite web}}: CS1 maint: date auto-translated (link)

[Reza-8] Fazlollah M. Reza (1961, 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2. {{cite book}}: Check date values in: |year= (tulong)

[Ash-9] Robert B. Ash (1965, 1990). Information Theory. Dover Publications, Inc. ISBN 0-486-66521-6. {{cite book}}: Check date values in: |year= (tulong)

[10] Jerry D. Gibson (1998). Digital Compression for Multimedia: Principles and Standards. Morgan Kaufmann. ISBN 1-55860-369-7.{{cite book}}: CS1 maint: date auto-translated (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]