Slumpmässigt händelseutrymme
1946 föreslog den amerikanske statistikern John Tukey namnet BIT
Föreställ dig ett utrymme för slumpmässiga händelsersom består av att kasta ett falskt mynt, på båda sidor som är en örn. När faller en örn? Det är klart att alltid. Vi vet detta på förhand, för vårt utrymme är så ordnat. Fallet hos en örn är en tillförlitlig händelse, det vill säga att dess sannolikhet är lika med 1. Kommer vi att ge mycket information om vi säger om en tappad örn? Nej. Mängden information i ett sådant meddelande, vi kommer att betraktas som lika med 0.
Låt oss nu vända det rättvisa myntet:på ena sidan är det huvuden, och på den andra, svansar, som det ska vara. Landningshuvuden eller svansar kommer att vara två olika händelser som utgör vårt utrymme för slumpmässiga händelser. Om vi rapporterar resultatet av en kastning kommer det verkligen att vara ny information. Om huvuden tappas kommer vi att rapportera 0, och om svansarna är 1. För att rapportera denna information behöver vi bara 1 bit.
Vad förändrades?Osäkerhet har dykt upp i vårt eventutrymme. Vi har något att berätta om det för någon som inte kastar ett mynt själv och inte ser resultatet av kastningen. Men för att riktigt förstå vårt budskap måste han veta exakt vad vi gör och vad 0:orna och 1:orna betyder.Våra evenemangsutrymmen måste matcha, och avkodningsprocessen är unik för att återställa resultatet av kasta.Om händelseutrymmet för sändaren och mottagaren inte sammanfaller eller det inte finns någon möjlighet till entydig avkodning av meddelandet, kommer informationen att förbli endast brus i kommunikationskanalen.
Om du kastar två oberoende och samtidigtmynt, då blir det fyra olika lika sannolika resultat: huvud-huvud, huvud-svans, svans-huvud och svans-svans. För att överföra information kommer vi att behöva 2 bitar, och våra meddelanden kommer att vara följande: 00, 01, 10 och 11. Det finns dubbelt så mycket information. Detta skedde för att osäkerheten ökade. Om vi försöker gissa resultatet av en sådan parad kast har vi dubbelt så stor chans att ha fel.
Ju större osäkerhet evenemangsutrymmet har, desto mer information innehåller meddelandet om dess tillstånd.
Låt oss komplicera vårt eventutrymme lite.Hittills har alla händelser som inträffat varit lika sannolika. Men i verkliga utrymmen har inte alla händelser samma sannolikhet. Låt oss säga att sannolikheten att kråkan vi ser kommer att vara svart är nära 1. Sannolikheten att den första förbipasserande vi möter på gatan kommer att vara en man är ungefär 0,5. Men att träffa en krokodil på Moskvas gator är nästan omöjligt. Intuitivt förstår vi att ett reportage om ett möte med en krokodil har mycket större informationsvärde än om en svart kråka.Ju lägre sannolikheten för en händelse är desto mer information finns i meddelandet om en sådan händelse.
Låt händelseplatsen inte vara så exotisk. Vi står bara vid fönstret och tittar på de passande bilarna. Bilar med fyra färger passerar, vilket vi måste rapportera. För att göra detta ska vi koda färgerna: svart - 00, vit - 01, röd - 10, blå - 11. För att rapportera exakt vilken bil som körde, behöver vi bara överföra 2 bitar av information.
Men ganska länge tittade på bilarna,Vi noterar att bilens färg är ojämnt fördelad: svart - 50% (varannan sekund), vit - 25% (var fjärde), röd och blå - 12,5% (var tionde). Då kan du optimera den överförda informationen.
De flesta av bilarna är svarta, sålåt oss beteckna svart - 0 - den kortaste koden, och låt koden för alla de andra börja på 1. Av den återstående hälften, vit - 10, och de återstående färgerna börjar på 11. Slutligen, låt oss beteckna rött - 110 och blå - 111.
Nu kan vi koda närmare information om bilens färg.
Shannon Entropy
Låt vårt eventutrymme bestå av nolika händelser. När man kastar ett mynt med två huvuden finns det exakt en sådan händelse, när man kastar ett rättvist mynt är det exakt 2, när man kastar två mynt eller tittar på bilar är det exakt 4. Varje händelse har en sannolikhet att den inträffar. När man kastar ett mynt med två huvuden finns det en händelse (fall ut huvuden) och dess sannolikhet är p1 = 1. När man kastar ett rättvist mynt finns det två händelser, de är lika sannolika och sannolikheten för var och en är 0,5: p1 = 0,5, p2 = 0,5. När man kastar två rättvisa mynt finns det fyra händelser, de är alla lika sannolika och sannolikheten för varje är 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. När man observerar bilar finns det fyra händelser, och de har olika sannolikheter: svart - 0,5, vit - 0,25, röd - 0,125, blå - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Detta är ingen slump.Shannon valde entropi (ett mått på osäkerhet i händelseutrymme) så att tre villkor uppfylldes:
- 1Entropin för en tillförlitlig händelse, vars sannolikhet är 1, är lika med 0.
- Entropin av två oberoende händelser är lika med summan av entropierna av dessa händelser.
- Entropi är maximal om alla händelser är lika sannolika.
Alla dessa krav är helt förenliga med våraidéer om osäkerheten i evenemangsutrymmet. Om det bara finns en händelse (det första exemplet) finns det ingen osäkerhet. Om händelserna är oberoende - summans osäkerhet är lika med summan av osäkerheterna - summeras de helt enkelt (exemplet med att kasta två mynt). Och slutligen, om alla händelser är lika sannolika, då är graden av osäkerhet i systemet maximal. Som i fallet med att kasta två mynt är alla fyra händelserna lika sannolika och entropin är 2, den är större än i fallet med bilar, när det också finns fyra händelser, men de har olika sannolikheter - i det här fallet är entropin 1,75.
Kvantiteten H spelar en central roll i informationsteorin som ett mått på information, val och osäkerhet.
Claude Shannon
Claude Elwood Shannon- Amerikansk ingenjör, kryptoanalytiker ochmatematiker. Anses som "informationsålderns fader". Grundare av informationsteori, som har funnit tillämpning i moderna högteknologiska kommunikationssystem. Tillhandahållit grundläggande begrepp, idéer och deras matematiska formuleringar som för närvarande utgör grunden för modern kommunikationsteknik.
År 1948 föreslogs att man använde ordet "bit"för att ange den minsta informationsenheten. Han demonstrerade också att entropin som han angav motsvarar osäkerheten i informationen i det överförda meddelandet. Shannons artiklar "Matematisk teori om kommunikation" och "Teori om kommunikation i hemliga system" anses vara grundläggande för informationsteori och kryptografi.
Under andra världskriget arbetade Shannon på Bell Laboratories för att utveckla kryptografiska system, vilket senare hjälpte honom att upptäcka felkorrigerande kodningsmetoder.
Shannon gjorde ett viktigt bidrag till teorin om probabilistiska system, spelteori, automatteori och styrsystemteori - områden inom vetenskap som ingår i begreppet cybernetik.
kodande
Och kastade mynt, och passande bilar är inteliknar siffrorna 0 och 1. För att rapportera händelser som förekommer i mellanslag måste du tänka på ett sätt att beskriva dessa händelser. Denna beskrivning kallas kodning.
Meddelanden kan kodas på ett oändligt antal olika sätt. Men Shannon visade att den kortaste koden inte kan vara mindre i bitar än entropin.
Det är därför entropin i ett meddelande är ett måttinformationen i meddelandet. Eftersom antalet bitar under kodningen i alla de betraktade fallen är lika med entropi, betyder detta att kodningen var optimal. Kort sagt, det går inte längre att koda meddelanden om händelser i våra utrymmen.
Med optimal kodning kan du inte förlora ellerförvränga en enda överförd bit i meddelandet. Om ens en bit går förlorad kommer informationen att förvrängas. Men alla riktiga kommunikationskanaler ger inte 100 procents förtroende för att alla bitar av meddelandet kommer att nå mottagaren oförvrängd.
För att åtgärda detta problem måste du görakoden är inte optimal, men överflödig. Skicka till exempel tillsammans med meddelandet dess kontrollsumma - ett speciellt beräknat värde som erhålls vid konvertering av meddelandekoden, och som kan verifieras genom omräkning vid mottagande av meddelandet. Om den överförda kontrollsumman stämmer överens med den beräknade kommer sannolikheten att överföringen var felfri att vara ganska stor. Och om kontrollsumman inte stämmer överens måste en återsändning begäras. Ungefär så fungerar de flesta kommunikationskanaler idag, till exempel vid överföring av informationspaket över Internet.
Naturliga språkmeddelanden
Tänk på händelseutrymmet som bestårfrån inlägg i naturligt språk. Detta är ett speciellt fall, men en av de viktigaste. Händelserna här kommer att vara de överförda tecknen (bokstäver i ett fast alfabet). Dessa tecken finns på språket med olika sannolikheter.
Mestfrekvenssymbolen (dvs en somfinns oftast i alla texter skrivna på ryska) är ett mellanslag: av tusen tecken finns ett genomsnittligt utrymme 175 gånger. Den andra i frekvensen är symbolen "o" - 90, följt av andra vokaler: "e" (eller "e" - vi kommer inte skilja dem) - 72, "a" - 62 och i - 62 och bara längre den första konsonanten "t" - 53. Och den sällsynta "f" - den här symbolen finns bara två gånger per tusen tecken.
Vi kommer att använda 31-bokstavs alfabetet av ryskaspråk (det skiljer sig inte från "e" och "e", såväl som "ъ" och "ь"). Om alla bokstäver uppstod på språket med samma sannolikhet, skulle entropin per symbol vara H = 5 bitar, men om vi tar hänsyn till symbolernas reala frekvenser kommer entropin att vara mindre: H = 4,35 bitar. (Detta är nästan två gånger mindre än med traditionell kodning, när en karaktär överförs som en byte - 8 bitar).
Men entropin av karaktären på språket är ännu lägre. Sannolikheten för förekomst av nästa tecken är inte fullständigt förutbestämd av den genomsnittliga frekvensen av tecknet i alla texter. Vilket tecken kommer att följa beror på de tecken som redan överförts. Till exempel kan i modern ryska efter symbolen "ъ" inte följa konsonant-symbolljudet. Efter två på varandra följande vokaler "e" följer den tredje vokalen "e" extremt sällan, såvida inte ordet "långhalsad". Det vill säga nästa karaktär är i viss utsträckning förutbestämd. Om vi tar hänsyn till sådan förutbestämdhet för nästa symbol, kommer osäkerheten (det vill säga informationen) för nästa symbol att vara ännu mindre än 4,35. Enligt vissa uppskattningar är följande symbol på ryska förutbestämd av språkets struktur med mer än 50%, det vill säga med optimal kodning kan all information överföras genom att radera hälften av bokstäverna från meddelandet.
En annan sak är att inte alla brev kan raderas säkert. Högfrekvens "o" (och allmänt vokaler) är till exempel lätt att korsa, men sällsynt "f" eller "e" är ganska problematisk.
Det naturliga språket som vi kommunicerar med varandra på är mycket överflödigt och därför tillförlitligt; om vi hörde något fel är det okej, informationen kommer fortfarande att överföras.
Men tills Shannon introducerade måtten på information kunde vi inte förstå att språket är överflödigt och i vilken utsträckning vi kan komprimera meddelandena (och varför textfiler är så väl komprimerade av arkivet).
Naturlig språkredundans
I artikeln "Om hur vi vorpsimanie tektkt"(namnet låter exakt som detta!) Ett fragment av Ivan Turgenevs Noble Nest-roman togs och utsattes för någon omvandling: 34% av bokstäverna raderades från fragmentet, men inte slumpmässigt. De första och sista bokstäverna i ord lämnades, endast vokaler raderades, och inte alla. Målet var inte bara att få möjlighet att återhämta all information om den konverterade texten, men också för att säkerställa att den person som läste texten inte upplevde några speciella svårigheter på grund av saknade bokstäver.
Varför är det relativt lätt att läsa detta korrumperattext? Den innehåller faktiskt nödvändig information för att rekonstruera hela ord. En som talar ryska som modersmål har en viss uppsättning händelser (ord och hela meningar) som han använder för att känna igen. Dessutom har talaren också standardspråkstrukturer till sitt förfogande som hjälper honom att återställa information. Till exempel,"Hon är blå blöja"- med stor sannolikhet kan läsas som"Hon var mer känslig.". Men tagna separat"Hon är mer bla", snarare kommer att återställas som"Hon var vitare". Sedan i vardaglig kommunikation handlar vimed kanaler där det finns brus och störningar är vi ganska bra på att återställa information, men bara det som vi redan vet i förväg. Till exempel frasen"Hennes funktioner är inte minst trevliga, htya nmngo rspkhli och splash"läser bra förutom sista ordet"Splash" - "rallied". Detta ord finns inte i det moderna lexikonet. När du läser ett ord snabbt"Splls"läser mer som "fast tillsammans"; när det är långsamt förbryllar det helt enkelt.
Signaldigitalisering
Ljud- eller akustiska svängningar är en sinusoid. Detta kan ses på ljudredigeringsskärmen. För att korrekt överföra ljudet behöver du ett oändligt antal värden - hela sinusvågen. Detta är möjligt med en analog anslutning. Han sjunger - du lyssnar, kontakten avbryts inte medan sången varar.
I digital kommunikation över en kanal kan vi bara överföra ett ändligt antal värden. Betyder detta att ljudet inte kan återges korrekt? Det visar sig inte.
Olika ljud är en olika modulerad sinusvåg.Vi sänder endast diskreta värden (frekvenser och amplitud), och sinusvågen behöver inte överföras - mottagningsenheten kan generera den.Den genererar en sinusform och läggs ovanpå denmodulering skapad från värden som överförs via en kommunikationskanal. Det finns exakta principer för vilka diskreta värden som måste sändas så att ljudet vid ingången till kommunikationskanalen sammanfaller med ljudet vid utgången, där dessa värden är överlagrade på någon standard sinusoid (detta är vad Kotelnikovs teorem är handla om).
Kotelnikovs teorem (i engelskspråkig litteratur - Nyquist-Shannon-teorem, läsest theorem)- ett grundläggande uttalande inom det digitala områdetsignalbehandling, ansluter kontinuerliga och diskreta signaler och anger att "vilken funktion F(t), som består av frekvenser från 0 till f1, kan sändas kontinuerligt med vilken noggrannhet som helst med siffror som följer varandra i 1/(2*f1) sekunder
Anti-interferens kodning. Hammingkoder
Om på en opålitlig kanal att sändaIvan Turgenevs kodade text, om än med några fel, kommer att resultera i en ganska meningsfull text. Men om vi behöver överföra allt upp till lite kommer uppgiften att vara oupplöst: vi vet inte vilka bitar som är felaktiga, eftersom felet är slumpmässigt. Även kontrollsummen sparar inte alltid.
Det är därför idag när data överförsnätverk tenderar inte så mycket för optimal kodning, där den maximala informationen kan skjutas in i kanalen, men snarare till sådan kodning (uppenbarligen redundant), i vilken fel kan återvinnas - precis som när vi läser orden i Ivan Turgenevs fragment.
Det finns särskilda felkorrigeringskoder som låter dig återställa information efter ett fel. En av dem är Hamming-koden.Låt oss säga att hela vårt språk består av tre ord:111000, 001110, 100011. Både källan till meddelandet och mottagaren känner till dessa ord. Och vi vet att fel uppstår i en kommunikationskanal, men när man sänder ett ord förvrängs inte mer än en bit information.
Antag att vi först passerar ordet 111000. Som ett resultat, inte mer än ett fel (vi har identifierat felet) kan det bli ett av orden:
1) 111 000,011.000, 101000, 110000, 111100, 111010, 111001.
Vid överföring av ordet 001110 kan något av orden erhållas:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Slutligen, för 100011 kan vi få i receptionen:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Observera att alla tre listorna inte är parvisa.skär varandra. Med andra ord, om i den andra änden av kommunikationskanalen visas något ord från lista 1, känner mottagaren säkert till att ordet 111000 överfördes till honom och om något ord från lista 2 framträder visas ordet 001110 och från lista 3 ordet 100011. De säger att vår kod fixade ett fel.
Korrigeringen skedde på grund av två faktorer.Först känner mottagaren hela "ordboken", dvs händelseutrymmet för meddelandemottagaren sammanfaller med utrymmet för den som överförde meddelandet. När koden överfördes med bara ett fel kom ett ord ut, vilket inte var i ordlistan.
För det andra valdes orden i ordboken på ett speciellt sätt.Även om ett fel uppstod kunde mottagaren inteblanda ihop ett ord med ett annat. Till exempel, om ordboken består av orden "dotter", "prick", "bump" och resultatet under överföringen var "vochka", skulle mottagaren, som vet att ett sådant ord inte existerar, inte kunna rätta till felet - vilket som helst av de tre orden kan visa sig vara korrekt. Om ordboken innehåller "prick", "daw", "gren" och vi vet att inte mer än ett misstag är tillåtet, så är "vochka" definitivt en "prick" och inte en "daw". I felkorrigerande koder väljs ord exakt så att de är "igenkännbara" även efter ett fel. Den enda skillnaden är att koden "alfabet" bara har två bokstäver - noll och en.
Redundansen för sådan kodning är mycket stor, och antalet ord som vi sålunda kan förmedla är relativt små.Vi måste utesluta alla ord från ordboken,som i händelse av ett fel kan sammanfalla med hela listan som motsvarar de överförda orden (till exempel kan orden "dotter" och "prick" inte finnas i ordboken). Men korrekt meddelandeöverföring är så viktigt att stora ansträngningar läggs på forskning om felbeständiga koder.
sensation
Begrepp av entropi (eller osäkerhet ochoförutsägbarhet) av budskapet och redundansen (eller förutbestämning och förutsägbarhet) motsvarar mycket naturligt våra intuitiva idéer om informationsmåttet. Ju mer oförutsägbart budskapet är (desto större entropi är det, eftersom det är mindre sannolikhet), desto mer information har den. En känsla (till exempel ett möte med en krokodil på Tverskaya) är en sällsynt händelse, dess förutsägbarhet är mycket låg, och därför är informationsvärdet högt. Information kallas ofta nyheter - rapporter om händelser som just har hänt, om vilka vi fortfarande inte vet någonting. Men om de berättar om andra och tredje gången om samma ord, kommer budskapets redundans vara bra, dess oförutsägbarhet kommer att sjunka till noll, och vi kommer helt enkelt inte att lyssna och vinka bort från talaren med orden "Jag vet jag vet". Därför försöker medierna så svårt att vara först. Denna korrespondens med den intuitiva känslan av nyhet, som ger upphov till verkligen oväntade nyheter, spelade en viktig roll i det faktum att Shannons artikel, som inte var avsedd för den allmänna läsaren, blev en känsla som pressen tog upp som en universell nyckel till kunskapen om naturen. - från lingvister och litterära kritiker till biologer.
MenShannon informationskoncept - rigorös matematisk teorioch dess tillämpning utanför kommunikationsteori är mycket opålitlig. Men i teorin om kommunikation i sig spelar den en central roll.
Semantisk information
Shannon, introducerar begreppet entropi som ett måttinformation, fick möjlighet att arbeta med information – först och främst att mäta den och utvärdera egenskaper som kanalkapacitet eller optimal kodning. Men huvudantagandet som gjorde det möjligt för Shannon att framgångsrikt arbeta med information var antagandet att generering av information är en slumpmässig process som framgångsrikt kan beskrivas i termer av sannolikhetsteori.Om processen är icke-slumpmässig, det följer den lagarna (dessutom är det inte alltid klart, som det händer i det naturliga språket), då är Shants resonemang inte tillämplig på det.Inget Shannon säger har något att göra med att informationen är meningsfull.
Medan vi pratar om tecken (eller bokstäver i alfabetet)vi kan väl argumentera i händelse av slumpmässiga händelser, men så fort vi kommer till språket, kommer situationen att förändras dramatiskt. Tal är en process som är speciellt organiserad, och här är meddelandets struktur inte mindre viktig än de tecken som den överförs till.
Nyligen verkade det som om vi inte kunde göra någonting.gjort för att åtminstone på något sätt komma närmare att mäta textens meningsfullhet, men på senare år har situationen börjat förändras. Och detta beror främst på tillämpningen av artificiella neurala nätverk för uppgifterna med maskinöversättning, automatisk sammanfattning av texter, extrahering av information från texter och generering av rapporter på naturligt språk. Alla dessa uppgifter involverar omvandling, kodning och avkodning av meningsfull information som finns i naturligt språk. Och gradvis bildas en idé om informationsförluster vid sådana transformationer, och därför om omfattningen av meningsfull information. Men idag är den tydlighet och noggrannhet som Shannons informationsteori har ännu inte tillgänglig i dessa svåra problem.