Atsitiktinė įvykių vieta
1946 m. Amerikiečių statistikas Johnas Tukey pasiūlė pavadinimą BIT
Įsivaizduokite atsitiktinių įvykių erdvękuris susideda iš vienos padirbtos monetos, kurios abiejose pusėse yra erelis, mėtymas. Kada erelis patenka? Akivaizdu, kad visada. Tai žinome iš anksto, nes mūsų erdvė yra taip išdėstyta. Erelio kritimas yra patikimas įvykis, ty jo tikimybė yra lygi 1. Ar mes suteiksime daug informacijos, jei pasakysime apie kritusį erelį? Ne Informacijos kiekis tokiame pranešime bus laikomas lygiu 0.
Dabar išmeskime tinkamą monetą: vienoje pusėje yra galvos, o kitoje - uodegos, kaip turėtų būti.Galvos ar uodegos bus du skirtingi įvykiai, kurie sudaroJei pranešime apie vieno metimo rezultatą, tai tikrai busNauja informacija: vadovai praneš apie 0 ir uodegą 1.Norint pateikti šią informaciją, mums reikia tik 1 bito.
Mūsų renginių erdvėje atsirado netikrumas, ir mes turime ką apie tai papasakoti tiems, kurie patys neišmeta monetosTačiau norėdamas teisingai suprasti mūsų žinią, jis turi tiksliai žinoti, ką darome, ką turime omenyje0 ir 1.Mūsų renginių erdvės turi sutapti, o dekodavimo procesas yra unikalus atkurti metimo rezultatą.Jei siųstuvo ir imtuvo įvykio erdvė nesutampa arba nesutampagalimybė vienareikšmiškai dekoduoti pranešimą, informacija išliks tik triukšmas ryšio kanale.
Jei dvi monetos bus išmestos atskirai ir tuo pačiu metu, bus skirtingi vienodai tikėtini rezultataiNorėdami perduoti informaciją, mums reikės 2 bitų, o mūsų pranešimai bus00, 01, 10 ir 11.Yra dvigubai daugiau informacijos.Jei bandysime atspėti tokio dvigubo metimo baigtį, dvigubai didesnė tikimybė suklysti.
Kuo didesnis įvykio erdvės neapibrėžtumas, tuo daugiau informacijos yra įvykio būsenos pranešime.
Šiek tiek apsunkinkime savo renginių erdvę, kol kas visi įvykiai, kurie įvyko, buvo vienodai tikėtini.Tačiau realiose erdvėse ne visi įvykiai turi trauminę tikimybę.Tarkime, tikimybė, kad varna, kurią matome, bus juoda, yra artima 1.Tikimybė, kad pirmasis praeivis, kurį sutiksite gatvėje, bus vyras, yra apie 0,5.Tačiau beveik neįtikėtina susitikti su krokodilu Maskvos gatvėje.Intuityviai mes suprantame, kad žinia apie susitikimą su krokodilu turidaug daugiau informacinės vertės nei apie juodąją varną.Kuo mažesnė įvykio tikimybė, tuo daugiau informacijos pranešime apie tokį įvykį.
Tegul renginio vieta nėra tokia egzotiška. Mes tiesiog stovi prie lango ir pažvelgiame į praeinančius automobilius. Pravažiuoja keturių spalvų automobiliai, apie kuriuos turime pranešti. Norėdami tai padaryti, mes koduojame spalvas: juoda - 00, balta - 01, raudona - 10, mėlyna - 11. Norėdami tiksliai pranešti, kuris automobilis važiuoja, mums reikia tik perkelti 2 informacijos.
Tačiau gana ilgą laiką žiūrint automobilius,pastebime, kad automobilių spalva yra nevienodai paskirstyta: juoda - 50% (kas sekundė), balta - 25% (kas ketvirtas), raudona ir mėlyna - 12,5% (kas aštuoni). Tada galite optimizuoti perduotą informaciją.
Dauguma jų yra juodi automobiliai, todėl pažymėkime juodą - 0 yra trumpiausias kodas, o visų kitų kodas prasideda nuo 1.Iš likusių pusė yra balta ties 10, o likusios spalvos prasideda nuo 11.Galiausiai pažymėkime raudoną kaip 110, o mėlyną - kaip 111.
Dabar, perduodami informaciją apie automobilio spalvą, mes galime jį koduoti.
Shannon Entropija
Tarkime, kad mūsų renginių erdvę sudaro n skirtingų įvykių.Kai moneta mėtoma dviem galvomis, yra lygiai vienas toks įvykis, kai mėtoma viena teisinga moneta, 2, kai mėtomos dvi monetosarba automobilio stebėjimas – 4.Kiekvienas įvykis atitinka jo atsiradimo tikimybę.Kai moneta yra išmesta dviem galvomis, yra tik vienas įvykis (galvos sukimas) ir jo tikimybė yra p1 = 1.Kai apversite dešinę monetą, yra du įvykiai, jie yra vienodai tikėtini, o kiekvieno tikimybė yra 0,5: p1 = 0,5, p2 = 0,5.Jei išmetate dvi teisingas monetas, yra keturi įvykiai, visi jie yra vienodai tikėtini, o kiekvieno tikimybė yra 0, 25: p1 = 0, 25, p2 = 0, 25, p3 = 0, 25, p4 = 0, 25.Stebint automobilius, yra keturi įvykiai, ir jie turi skirtingas tikimybes: juoda yra 0, 5, balta yra 0, 25, raudona yra 0, 125, mėlyna yra 0, 125: p1 = 0, 5, p2 = 0, 25, p3 = 0, 125, p4 = 0, 125.
Tai nėra atsitiktinumas.Šanonas pasirinko entropiją (įvykių erdvės neapibrėžtumo matas), kad įvykdytos trys sąlygos:
- 1Galiojančio įvykio, kurio tikimybė yra 1, entropija yra 0.
- Dviejų nepriklausomų įvykių entropija yra lygi šių įvykių entropijų sumai.
- Entropija yra didžiausia, jei visi įvykiai yra vienodai tikėtini.
Visi šie reikalavimai visiškai atitinka mūsų idėjas apie renginių erdvės neapibrėžtumą.Jei įvykiai yra nepriklausomi, sumos neapibrėžtumas yra lygus neapibrėžtumų sumai, jie tiesiog susumuojami (pavyzdysIr, galiausiai, jei visi įvykiai yra vienodai tikėtini, sistemos neapibrėžtumo laipsnis yra didžiausias.Kaip ir dviejų monetų mėtymo atveju, visi keturi įvykiai yra vienodai tikėtini, o entropija yra 2, kuri yra didesnė nei automobilių atveju, kur taip pat yra keturi įvykiai, tačiau jie turiŠiuo atveju entropija yra 1, 75.
H vertė vaidina pagrindinį vaidmenį informacijos teorijoje kaip informacijos kiekio, pasirinkimo ir neapibrėžtumo matas.
Klodas Šenonas
Claude Elwood Shannon– Amerikos inžinierius, kriptoanalitikas irmatematikas. Laikomas „informacijos amžiaus tėvu“. Informacijos teorijos, kuri rado pritaikymą šiuolaikinėse aukštųjų technologijų komunikacijos sistemose, įkūrėjas. Pateiktos pagrindinės sąvokos, idėjos ir jų matematinės formuluotės, kurios šiuo metu sudaro šiuolaikinių komunikacijos technologijų pagrindą.
1948 m. Pasiūlė naudoti žodį „bit“nurodyti mažiausią informacijos vienetą. Jis taip pat parodė, kad jo įvesta entropija yra lygi perduodamo pranešimo informacijos neapibrėžtumui. „Shannon“ straipsniai „Komunikacijos matematinė teorija“ ir „Komunikacijos teorija slaptose sistemose“ yra laikomi esminiais informacijos teorijos ir kriptografijos elementais.
Antrojo pasaulinio karo metu Šenonas dirbo „Bell Laboratories“ kurdamas kriptografines sistemas, kurios vėliau padėjo atrasti klaidų taisymo kodavimo metodus.
Šanonas labai prisidėjo prie tikimybinių schemų, žaidimų teorijos, automatikos teorijos ir kontrolės sistemos teorijos - mokslo sričių, kurios yra kibernetikos sąvokos, teorijos.
Kodavimas
Ir ne mestos monetos, nei einantys automobiliai nėrayra panašūs į 0 ir 1 numerius. Jei norite pranešti apie įvykius erdvėse, turite galvoti apie būdą, kaip apibūdinti šiuos įvykius. Šis aprašymas vadinamas kodavimu.
Žinutės gali būti užkoduotos be galo daugybe skirtingų būdų. Tačiau Šenonas parodė, kad trumpiausias kodas negali būti mažesnis bitais nei entropija.
Štai kodėl pranešimo entropija yra matasinformacija žinutėje. Kadangi visais nagrinėjamais atvejais kodavimo metu bitų skaičius yra lygus entropijai, tai reiškia, kad kodavimas buvo optimalus. Trumpai tariant, nebeįmanoma užkoduoti pranešimų apie įvykius mūsų erdvėse.
Naudodami optimalų kodavimą negalite prarasti arbaiškraipyti vieną perduotą pranešimo bitą. Praradus nors vieną bitą, informacija bus iškraipyta. Tačiau visi tikri komunikacijos kanalai nesuteikia 100 procentų pasitikėjimo, kad visi pranešimo fragmentai gavėją pasieks neiškraipyti.
Norėdami išspręsti šią problemą, turite padarytikodas nėra optimalus, bet perteklinis. Pavyzdžiui, kartu su pranešimu perduokite jo kontrolinę sumą – specialiai apskaičiuotą reikšmę, gautą konvertuojant pranešimo kodą ir kurią galima patikrinti perskaičiavus gavus pranešimą. Jei perduota kontrolinė suma sutampa su apskaičiuotąja, tikimybė, kad perdavimas buvo be klaidų, bus gana didelė. O jei kontrolinė suma nesutampa, reikia prašyti pakartotinio siuntimo. Maždaug taip šiandien veikia dauguma komunikacijos kanalų, pavyzdžiui, perduodant informacijos paketus internetu.
Natūralūs kalbos pranešimai
Apsvarstykite renginio erdvęiš įrašų natūralia kalba. Tai yra ypatingas atvejis, bet vienas iš svarbiausių. Įvykiai bus perduodami simboliai (fiksuotos abėcėlės raidės). Šie simboliai randami skirtingomis tikimybėmis.
Dažniausias simbolis (t. Y. Vienasdažniausiai randamas visuose rusų kalba parašytuose tekstuose) yra erdvė: tūkstančio simbolių, vidutinė erdvė yra 175 kartus. Antrasis dažnumas yra simbolis "o" - 90, po kurio seka kiti balsiai: "e" (arba "e" - mes jų nepadarysime) - 72, "a" - 62 ir i - 62, ir tik toliau pirmasis priebalsis "t" - 53. Ir rečiausias "f" - šis simbolis randamas tik du kartus per tūkstantį simbolių.
Mes naudosime rusų 31 raidžių abėcėlękalba (ji nesiskiria „e“ ir „e“, taip pat „ъ“ ir „ь“). Jei visos raidės susidūrė su ta pačia tikimybe, tuomet simbolio entropija būtų H = 5 bitai, bet jei atsižvelgsime į realius simbolių dažnius, entropija bus mažesnė: H = 4.35 bitai. (Tai beveik du kartus mažiau nei naudojant tradicinį kodavimą, kai simbolis perduodamas kaip baitas - 8 bitai).
Bet kalbos simbolio entropija yra dar mažesnė. Kitų simbolių atsiradimo tikimybė nėra visiškai iš anksto nustatoma pagal vidutinį visų teksto simbolių dažnį. Koks simbolis bus taikomas, priklauso nuo jau perduotų simbolių. Pavyzdžiui, šiuolaikinėje rusų kalba po simbolio „follow“ negali sekti konsonanto simbolio garsas. Po dviejų iš eilės balsių "e", trečias balsis "e" labai retai seka, nebent žodyje "ilgas kaklas". Tai reiškia, kad kitas simbolis tam tikru mastu yra iš anksto nustatytas. Jei atsižvelgsime į tokį kito simbolio nustatymą, kito simbolio netikrumas (tai yra informacija) bus net mažesnis nei 4.35. Remiantis kai kuriais skaičiavimais, toliau pateikiamas simbolis rusų kalba yra nustatytas iš kalbos struktūros daugiau nei 50%, tai yra, optimaliai koduojant, visa informacija gali būti perduodama ištrinant pusę laiško raidės.
Kitas dalykas yra tas, kad ne kiekviena raidė gali būti saugiai ištrinta. Pavyzdžiui, aukšto dažnio „o“ (ir paprastai balsių) yra lengva kirsti, bet retas „f“ arba „e“ yra gana problemiškas.
Natūrali kalba, kuria bendraujame vieni su kitais, yra labai perteklinė, todėl patikima, jei ką nors išgirdome, viskas gerai, informacija vis tiek bus perduota.
Tačiau kol „Shannon“ nepateikė informacijos matavimo, mes negalėjome suprasti, kad ši kalba yra nereikalinga, ir kokiu mastu galime suspausti pranešimus (ir kodėl archyvas taip gerai suglaudina tekstinius failus).
Natūralus kalbos atleidimas
Straipsnyje „Apie tai, kaip mes vorpsimanie tektkt“(pavadinimas skamba lygiai taip!) buvo paimtas Ivano Turgenevo „Noble Nest“ romano fragmentas, kuris buvo paveiktas: iš fragmento ištrinti 34% raidžių, bet ne atsitiktinai. Pirmosios ir paskutinės raidės žodžiu liko, tik išnyko balsiai, o ne visi. Tikslas buvo ne tik gauti galimybę susigrąžinti visą konvertuojamo teksto informaciją, bet ir užtikrinti, kad asmuo, skaitantis šį tekstą, nepatirtų jokių ypatingų sunkumų dėl trūkstamų raidžių.
Kodėl gana lengva skaityti tai sugadintątekstas? Iš tikrųjų jame yra informacijos, reikalingos ištisiems žodžiams atkurti. Gimtoji rusų kalba turi tam tikrą įvykių rinkinį (žodžius ir ištisus sakinius), kuriuos jis naudoja atpažindamas. Be to, kalbėtojas taip pat turi standartines kalbos struktūras, kurios padeda atkurti informaciją. Pavyzdžiui,„Ji blee blee“- su didele tikimybe galima perskaityti kaip"Ji buvo jautresnė.". Bet paimta atskirai„Ji daugiau bla“, greičiau bus atkurta kaip„Ji buvo baltesnė“. Kadangi kasdieniame bendravime mes susiduriamesu kanalais, kuriuose yra triukšmo ir trukdžių, mes gana gerai atkuriame informaciją, bet tik tą, kurią jau žinome iš anksto. Pavyzdžiui, frazė„Jos funkcijos nėra mažiausiai malonios, htya nmngo rspkhli ir splash“skaito gerai, išskyrus paskutinį žodį„Splash“ - „rallied“. Šio žodžio šiuolaikinėje leksike nėra. Greitai skaitant žodį„Splash“skaito kaip „sulipęs“, kai lėtas, tai tiesiog glumina.
Signalų skaitmeninimas
Garsas arba akustiniai virpesiai yra sinusoidas. Tai galima pamatyti, pavyzdžiui, garso redaktoriaus ekrane. Norint tiksliai perteikti garsą, jums reikės begalinio skaičiaus vertybių - visos sinusinės bangos. Tai įmanoma naudojant analoginį ryšį. Jis dainuoja - klausotės, kontaktas nėra nutraukiamas, kol daina trunka.
Skaitmeninio ryšio metu per kanalą galime perduoti tik baigtinį skaičių reikšmių. Ar tai reiškia, kad garso negalima tiksliai atkurti? Pasirodo, kad ne.
Skirtingi garsai yra skirtingai moduliuojama sinusinė banga.Mes perduodame tik diskrečias reikšmes (dažnius ir amplitudes), o sinusinės bangos nereikia perduoti - priimantis įrenginys gali jį generuoti.Jis sukuria sinusoidą ir yra ant jo uždėtasmoduliacija, sukurta iš verčių, perduodamų ryšio kanalu. Yra tikslūs principai, pagal kuriuos turi būti perduodamos atskiros reikšmės, kad garsas ryšio kanalo įėjime sutaptų su garsu išvestyje, kur šios reikšmės yra uždėtos ant kokios nors standartinės sinusoidės (tai yra Kotelnikovo teorema apie).
Kotelnikovo teorema (anglų kalbos literatūroje - Nyquist - Shannon teorema, skaitymo teorema)– esminis teiginys skaitmeninės srities srityjesignalų apdorojimas, jungiantis nuolatinius ir atskirus signalus ir nurodantis, kad „bet kuri funkcija F(t), susidedanti iš dažnių nuo 0 iki f1, gali būti nuolat perduodama bet kokiu tikslumu, naudojant skaičius, einančius vienas po kito per 1/(2*f1) sekundes.
Anti-interferencijos kodavimas. Hammingo kodai
Jei nepatikimas kanalas perduodamasIvano Turgenevo koduotas tekstas, nors ir su tam tikromis klaidomis, sukurs gana prasmingą tekstą. Bet jei mums reikia visko perkelti į viršų, užduotis bus neišspręsta: mes nežinome, kurie bitai yra neteisingi, nes klaida yra atsitiktinė. Net kontrolinė suma ne visada išsaugoma.
Štai kodėl šiandien perduodant duomenistinklai nėra tokie daug optimalaus kodavimo, kai maksimalus informacijos kiekis gali būti stumiamas į kanalą, o toks kodavimas (akivaizdžiai nereikalingas), kuriame gali būti atkurtos klaidos - kaip ir tada, kai skaitome žodžius Ivano Turgenevo fragmente.
Yra specialių klaidų ištaisymo kodų, kurie leidžia atkurti informaciją po gedimo. Vienas iš jų yra Hammingo kodas.Tarkime, kad visa mūsų kalba susideda iš trijų žodžių:111000, 001110, 100011. Šiuos žodžius žino ir pranešimo šaltinis, ir gavėjas. Ir žinome, kad komunikacijos kanale pasitaiko klaidų, tačiau perduodant vieną žodį iškraipoma ne daugiau nei vienas informacijos bitas.
Tarkime, mes pirmiausia perduodame žodį 111000. Todėl ne daugiau kaip viena klaida (mes nustatėme klaidą) gali virsti vienu iš žodžių:
1) 111000,011 000, 101000, 110000, 111100, 111010, 111001.
Perduodant žodį 001110, bet kuris iš žodžių gali būti:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Galiausiai už 100011 galime gauti registratūroje:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Atminkite, kad visi trys sąrašai nėra poriniai.susikerta. Kitaip tariant, jei kitame ryšio kanalo gale atsiranda bet kuris 1 sąrašo žodis, gavėjas tikrai žino, kad jam buvo perduotas žodis 111000, o jei atsiranda bet kuris 2 sąrašo žodis, pasirodo žodis 001110 ir 3 sąraše žodis 100011. Jie sako, kad mūsų kodas nustatė vieną klaidą.
Korekcija įvyko dėl dviejų veiksnių.Pirma, gavėjas žino visą „žodyną“, t. y. pranešimo gavėjo įvykių erdvė sutampa su pranešimo perduodančio asmens erdve. Kai kodas buvo perduotas tik su viena klaida, išėjo žodis, kuris nebuvo įtrauktas į žodyną.
Antra, žodynas žodynuose buvo pasirinktas specialiai.Net jei įvyko klaida, gavėjas negalėjo to padarytisupainioti vieną žodį su kitu. Pavyzdžiui, jei žodynas susideda iš žodžių „dukra“, „taškas“, „guzas“, o perdavimo metu rezultatas buvo „vochka“, tada gavėjas, žinodamas, kad tokio žodžio nėra, negalėtų ištaisykite klaidą – bet kuris iš trijų žodžių gali pasirodyti teisingas. Jei žodyne yra „taškas“, „aušra“, „šaka“ ir žinome, kad leidžiama ne daugiau kaip viena klaida, „vochka“ tikrai yra „taškas“, o ne „daw“. Klaidų taisymo koduose žodžiai parenkami tiksliai taip, kad būtų „atpažįstami“ net ir po klaidos. Vienintelis skirtumas yra tas, kad kode „abėcėlė“ yra tik dvi raidės - nulis ir viena.
Tokio kodavimo atleidimas yra labai didelis, o žodžių, kuriuos mes galime perteikti, skaičius yra gana mažas.Turime pašalinti bet kurį žodį iš žodyno,kuris klaidos atveju gali sutapti su visu sąrašu, atitinkančiu perduodamus žodžius (pvz., žodyne negali būti žodžių „dukra“ ir „taškas“). Tačiau tikslus pranešimų perdavimas yra toks svarbus, kad daug pastangų reikia skirti klaidoms atsparių kodų tyrimams.
Jautrumas
Entropijos sąvokos (arba netikrumas ir. \ Tnenuspėjamumas), o atleidimas iš darbo (arba iš anksto nustatymas ir nuspėjamumas) labai natūraliai atitinka mūsų intuityvias idėjas apie informacijos matą. Kuo labiau nenuspėjamas pranešimas (kuo didesnė jo entropija, nes yra mažesnė tikimybė), tuo daugiau informacijos ji gauna. Jausmas (pvz., Susitikimas su krokodilu apie Tverskają) yra retas įvykis, jo nuspėjamumas yra labai mažas, todėl informacijos vertė yra didelė. Dažnai informacija vadinama naujienomis - pranešimai apie įvykius, kurie ką tik įvyko, apie kuriuos mes vis dar nežinome. Bet jei jie pasakys mums apie antrą ir trečią kartą apie tuos pačius žodžius, pranešimo atleidimas bus didelis, jo nenuspėjamumas sumažės iki nulio, o mes paprasčiausiai neklausysime, nustumdami nuo kalbėtojo su žodžiais „Aš žinau, aš žinau“. Todėl žiniasklaida labai stengiasi būti pirmuoju. Šis atitikimas intuityviam naujumo jausmui, kuris sukelia tikrai netikėtas žinias, suvaidino svarbų vaidmenį tuo, kad Šanono straipsnis, kuris nebuvo skirtas bendram skaitytojui, tapo pojūčiu, kurį spauda pasiėmė kaip visuotinį gamtos pažinimo raktą. - iš lingvistų ir literatūros kritikų iki biologų.
Bet„Shannon“ informacijos koncepcija - griežta matematinė teorijair jos taikymas ne komunikacijos teorijoje yra labai nepatikimas. Tačiau komunikacijos teorijoje jis atlieka pagrindinį vaidmenį.
Semantinė informacija
Shannon, pristatydamas entropijos kaip mato sampratąinformaciją, gavo galimybę dirbti su informacija – pirmiausia ją išmatuoti ir įvertinti tokias charakteristikas kaip kanalo talpa ar optimalus kodavimas. Tačiau pagrindinė prielaida, leidusi Šenonui sėkmingai dirbti su informacija, buvo prielaida, kad informacijos generavimas yra atsitiktinis procesas, kurį galima sėkmingai apibūdinti tikimybių teorija.Jei procesas yra atsitiktinis, ty laikosi įstatymų (be to, ne visada aišku, kaip tai vyksta natūralia kalba), tada Shannon argumentai jai netaikomi.Niekas, ką Šenonas sako, neturi nieko bendra su informacijos prasmingumu.
Nors kalbame apie simbolius (arba raidžių raidę),mes galime gerai ginčytis atsitiktinių įvykių požiūriu, tačiau kai tik mes pasiekiame kalbos žodžius, padėtis dramatiškai pasikeis. Kalbėjimas yra specialiai organizuotas procesas, ir čia pranešimo struktūra yra ne mažiau svarbi nei simboliai, kuriais jis perduodamas.
Visai neseniai atrodė, kad nieko negalime padaryti.padaryta, kad bent kažkaip priartėtų prie teksto prasmingumo matavimo, tačiau pastaraisiais metais situacija ėmė keistis. Ir tai visų pirma lemia dirbtinių neuroninių tinklų naudojimas mašininio vertimo, automatinio tekstų apibendrinimo, informacijos iš tekstų ištraukimo ir ataskaitų natūralia kalba kūrimo užduotims atlikti. Visos šios užduotys apima prasmingos informacijos, esančios natūralia kalba, transformavimą, kodavimą ir dekodavimą. Ir palaipsniui formuojasi idėja apie informacijos praradimus tokių transformacijų metu, taigi ir apie prasmingos informacijos mastą. Tačiau šiandien Šenono informacijos teorijos aiškumo ir tikslumo šiose sudėtingose problemose dar nėra.