Tilfeldig hendelse plass
I 1946 foreslo den amerikanske statistikeren John Tukey navnet BIT
Tenk deg et rom med tilfeldige hendelsersom består av å kaste en falsk mynt, på begge sider av hvilken er en ørn. Når faller en ørn? Det er klart at alltid. Vi vet dette på forhånd, fordi rommet vårt er så ordnet. Fallet av en ørn er en pålitelig hendelse, det vil si at sannsynligheten er lik 1. Vil vi gi mye informasjon om vi sier om en tapt eagle? Nei. Mengden informasjon i en slik melding, vil vi bli ansett som 0.
La oss nå snu den rettferdige mynten:på den ene siden er det hoder, og på den andre, haler, som det skal være. Landende hoder eller haler vil være to forskjellige hendelser som utgjør vårt rom med tilfeldige hendelser. Hvis vi rapporterer utfallet av ett kast, vil det faktisk være ny informasjon. Hvis hoder slippes, vil vi rapportere 0, og hvis haler er 1. For å rapportere denne informasjonen trenger vi bare 1 bit.
Hva endret seg?Det har dukket opp usikkerhet i arrangementslokalet vårt. Vi har noe å fortelle om det til noen som ikke kaster en mynt selv og ikke ser utfallet av kastet. Men for å forstå budskapet vårt, må han vite nøyaktig hva vi gjør og hva 0-ene og 1-ene betyr.Våre hendelsesrom må samsvare, og dekodingsprosessen er unik for å gjenopprette kastets resultat.Dersom hendelsesrommet til senderen og mottakeren ikke er sammenfallende eller det ikke er mulighet for entydig dekoding av meldingen, vil informasjonen kun forbli støy i kommunikasjonskanalen.
Hvis du kaster to uavhengig og samtidigmynter, så vil det være fire forskjellige like sannsynlige resultater: hode-hoder, hode-haler, hale-hoder og hale-haler. For å overføre informasjon trenger vi 2 biter, og meldingene våre vil være som følger: 00, 01, 10 og 11. Det er dobbelt så mye informasjon. Dette skjedde fordi usikkerheten økte. Hvis vi prøver å gjette utfallet av et slikt toss, har vi dobbelt sjanse for å ta feil.
Jo større usikkerheten til arrangementsområdet er, desto mer informasjon inneholder meldingen om tilstanden.
La oss komplisere arrangementsrommet vårt litt.Så langt har alle hendelsene som har skjedd vært like sannsynlige. Men i virkelige rom har ikke alle hendelser lik sannsynlighet. La oss si at sannsynligheten for at kråka vi ser blir svart er nær 1. Sannsynligheten for at den første forbipasserende vi møter på gaten vil være en mann er omtrent 0,5. Men å møte en krokodille på gatene i Moskva er nesten umulig. Intuitivt forstår vi at en rapport om et møte med en krokodille har mye større informasjonsverdi enn om en svart kråke.Jo lavere sannsynligheten for en hendelse er, jo mer informasjon i meldingen om en slik hendelse.
La arrangementet ikke være så eksotisk. Vi står bare ved vinduet og ser på de forbipasserende bilene. Biler med fire farger passerer, som vi må rapportere. For å gjøre dette, vil vi kode inn fargene: svart - 00, hvit - 01, rød - 10, blå - 11. For å rapportere nøyaktig hvilken bil som kjørte, trenger vi bare å overføre 2 biter av informasjon.
Men for ganske lang tid å se bilene,Vi merker at bilens farge er ujevnt fordelt: svart - 50% (hvert sekund), hvit - 25% (hver fjerde), rød og blå - 12,5% (hver åttende). Da kan du optimalisere den overførte informasjonen.
De fleste bilene er svarte, altsåla oss angi svart - 0 - den korteste koden, og la koden for alle de andre starte på 1. Av den gjenværende halvparten begynner hvit - 10, og de resterende fargene på 11. La oss til slutt angi rød - 110, og blå - 111.
Nå sender vi informasjon om fargen på bilen, og vi kan kode det nærmere.
Shannon Entropy
La vårt arrangementsrom bestå av nulike hendelser. Når man kaster en mynt med to hoder er det nøyaktig én slik hendelse, når man kaster én rettferdig mynt er det nøyaktig 2, når man kaster to mynter eller ser på biler er det nøyaktig 4. Hver hendelse har en sannsynlighet for at den inntreffer. Når du kaster en mynt med to hoder, er det én hendelse (fall ut hoder) og sannsynligheten er p1 = 1. Når du kaster en rettferdig mynt, er det to hendelser, de er like sannsynlige og sannsynligheten for hver er 0,5: p1 = 0,5, p2 = 0,5. Når du kaster to rettferdige mynter, er det fire hendelser, de er alle like sannsynlige og sannsynligheten for hver er 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Ved observasjon av biler er det fire hendelser, og de har forskjellige sannsynligheter: svart - 0,5, hvit - 0,25, rød - 0,125, blå - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Dette er ikke en tilfeldighet.Shannon valgte entropi (et mål for usikkerhet i hendelsesrommet) slik at tre betingelser ble oppfylt:
- 1 Entropien til en pålitelig hendelse, hvis sannsynlighet er 1, er lik 0.
- Entropien til to uavhengige hendelser er lik summen av entropier av disse hendelsene.
- Entropi er maksimal hvis alle hendelser er like sannsynlige.
Alle disse kravene er helt i samsvar med våreideer om usikkerheten i arrangementsrommet. Hvis det bare er én hendelse (det første eksempelet), er det ingen usikkerhet. Hvis hendelsene er uavhengige – usikkerheten til summen er lik summen av usikkerhetene – summeres de ganske enkelt sammen (eksemplet med å kaste to mynter). Og til slutt, hvis alle hendelser er like sannsynlige, så er graden av usikkerhet i systemet maksimal. Som i tilfellet med å kaste to mynter, er alle fire hendelser like sannsynlige og entropien er 2, den er større enn i tilfellet med biler, når det også er fire hendelser, men de har forskjellige sannsynligheter - i dette tilfellet er entropien 1,75.
Mengden H spiller en sentral rolle i informasjonsteori som et mål på informasjon, valg og usikkerhet.
Claude Shannon
Claude Elwood Shannon- Amerikansk ingeniør, kryptoanalytiker ogmatematiker. Regnes som "informasjonsalderens far". Grunnlegger av informasjonsteori, som har funnet anvendelse i moderne høyteknologiske kommunikasjonssystemer. Gitt grunnleggende konsepter, ideer og deres matematiske formuleringer som i dag danner grunnlaget for moderne kommunikasjonsteknologi.
I 1948, foreslått å bruke ordet "bit"for å indikere den minste informasjonsenheten. Han viste også at entropien som er innført av ham, er ekvivalent med informasjonen i den sendte meldingen. Shannons artikler "Matematisk teori for kommunikasjon" og "Teori for kommunikasjon i hemmelige systemer" regnes som grunnleggende for informasjonsteori og kryptografi.
Under andre verdenskrig jobbet Shannon ved Bell Laboratories for å utvikle kryptografiske systemer, som senere hjalp ham med å oppdage feilkorrigerende kodingsmetoder.
Shannon gjorde et viktig bidrag til teorien om probabilistiske ordninger, spillteori, automatteori og styresystemteori - vitenskapsområder som inngår i konseptet cybernetikk.
koding
Og kastet mynter, og passerer biler er ikkeligner tallene 0 og 1. For å rapportere hendelser som forekommer i mellomrom, må du tenke på en måte å beskrive disse hendelsene på. Denne beskrivelsen kalles koding.
Meldinger kan kodes på et uendelig antall forskjellige måter. Men Shannon viste at den korteste koden ikke kan være mindre i biter enn entropien.
Det er derfor entropien til en melding er et målinformasjon i meldingen. Siden antall biter under koding i alle de betraktede tilfellene er lik entropi, betyr dette at kodingen var optimal. Kort sagt, det er ikke lenger mulig å kode meldinger om hendelser i våre rom.
Med optimal koding kan du ikke miste ellerforvrenge en enkelt overført bit i meldingen. Hvis bare én bit går tapt, vil informasjonen bli forvrengt. Men alle reelle kommunikasjonskanaler gir ikke 100 prosent tillit til at alle biter av meldingen vil nå mottakeren uforvrengt.
For å fikse dette problemet må du gjørekoden er ikke optimal, men overflødig. Send for eksempel sammen med meldingen kontrollsummen - en spesielt beregnet verdi oppnådd ved konvertering av meldingskoden, og som kan verifiseres ved å beregne på nytt ved mottak av meldingen. Hvis den overførte sjekksummen samsvarer med den beregnede, vil sannsynligheten for at overføringen var feilfri være ganske stor. Og hvis kontrollsummen ikke stemmer overens, må det bes om en ny overføring. Omtrent slik fungerer de fleste kommunikasjonskanaler i dag, for eksempel ved overføring av informasjonspakker over Internett.
Naturlige språkmeldinger
Vurder hendelsesplassen som bestårfra innlegg i naturlig språk. Dette er et spesielt tilfelle, men en av de viktigste. Hendelsene her vil være de overførte tegnene (bokstavene i et fast alfabet). Disse tegnene finnes på språket med forskjellige sannsynligheter.
Mestfrekvenssymbolet (det vil si en somer oftest funnet i alle tekster skrevet på russisk) er et mellomrom: av tusen tegn, er en gjennomsnittlig plass funnet 175 ganger. Den andre i frekvensen er symbolet "o" - 90, etterfulgt av andre vokaler: "e" (eller "e" - vi skiller dem ikke) - 72, "a" - 62 og i - 62, og bare videre den første konsonanten "t" - 53. Og den sjeldneste "f" - dette symbolet er bare funnet to ganger per tusen tegn.
Vi vil bruke 31-bokstavs alfabetet av russiskspråk (det er ikke forskjellig "e" og "e", så vel som "ъ" og "ь"). Hvis alle bokstavene ble møtt på språket med samme sannsynlighet, ville entropien per symbol være H = 5 biter, men hvis vi tar hensyn til de reelle frekvensene av symbolene, vil entropien være mindre: H = 4,35 biter. (Dette er nesten to ganger mindre enn med tradisjonell koding, når et tegn overføres som en byte - 8 bits).
Men entropien av tegnet på språket er enda lavere. Sannsynligheten for forekomst av neste tegn er ikke fullstendig forhåndsbestemt av tegnets gjennomsnittlige frekvens i alle tekster. Hvilken karakter vil følge avhenger av tegnene som allerede er overført. For eksempel kan i moderne russisk etter symbolet "ъ" ikke følge konsonant-symbollyden. Etter to påfølgende vokaler "e" følger den tredje vokalen "e" ekstremt sjelden, med mindre i ordet "langhalset". Det vil si, det neste tegnet er til en viss grad forhåndsbestemt. Hvis vi tar hensyn til slik forhåndsbestemmelse av det neste symbolet, vil usikkerheten (det vil si informasjonen) til det neste symbolet være enda mindre enn 4,35. Ifølge noen estimater er følgende symbol på russisk forhåndsbestemt av språkets struktur med mer enn 50%, det vil si med optimal koding, all informasjon kan overføres ved å slette halvparten av bokstavene fra meldingen.
En annen ting er at ikke alle bokstaver kan trygt slettes. Høyfrekvente "o" (og generelt vokaler), for eksempel, er lett å krysse ut, men sjeldne "f" eller "e" er ganske problematiske.
Det naturlige språket vi kommuniserer med hverandre på er svært overflødig, og derfor pålitelig hvis vi har hørt feil, er det greit, informasjonen vil fortsatt bli overført.
Men inntil Shannon introduserte måleinformasjonen, kunne vi ikke forstå at språket er overflødig, og i hvilken grad kan vi komprimere meldinger (og hvorfor tekstfiler er så godt komprimert av arkiveren).
Naturlig språkredundans
I artikkelen "Om hvordan vi vorpsimanie tektkt"(navnet lyder akkurat som dette!) Et fragment av Ivan Turgenevs Noble Nest-roman ble tatt og utsatt for noe transformasjon: 34% av bokstavene, men ikke tilfeldige, ble slettet fra fragmentet. De første og siste bokstavene i ord ble igjen, bare vokaler ble slettet, og ikke alle. Målet var ikke bare å få muligheten til å gjenopprette all informasjon om den konverterte teksten, men også for å sikre at personen som leser denne teksten, ikke opplevde noen spesielle vanskeligheter på grunn av manglende bokstaver.
Hvorfor er det relativt lett å lese dette ødelagttekst? Den inneholder faktisk den nødvendige informasjonen for å rekonstruere hele ord. En som har russisk som morsmål har et visst sett med hendelser (ord og hele setninger) som han bruker i gjenkjennelse. I tillegg har foredragsholderen også standard språkstrukturer til disposisjon som hjelper ham å gjenopprette informasjon. For eksempel,"Hun er blae blee"- med stor sannsynlighet kan leses som"Hun var mer følsom.". Men tatt separat"Hun er mer bla", snarere, vil bli gjenopprettet som"Hun var hvitere". Siden i daglig kommunikasjon handler vimed kanaler der det er støy og forstyrrelser, er vi ganske flinke til å gjenopprette informasjon, men bare det vi allerede vet på forhånd. For eksempel uttrykket"Hennes trender er ikke minst hyggelige, og det er ikke så godt som en splash"leser godt bortsett fra det siste ordet"Splash" - "rallied". Dette ordet er ikke i det moderne leksikonet. Når du leser et ord raskt"Splls"lyder mer som "fast sammen" når det er sakte, forvirrer det ganske enkelt.
Signal Digitalisering
Lyd- eller akustiske svingninger er en sinusoid. Dette kan ses på for eksempel lydredigeringsskjermbildet. For å overføre lyden nøyaktig, trenger du et uendelig antall verdier - hele sinusbølge. Dette er mulig med en analog tilkobling. Han synger - du hører, kontakten blir ikke avbrutt mens sangen varer.
I digital kommunikasjon over en kanal kan vi bare overføre et begrenset antall verdier. Betyr dette at lyden ikke kan gjengis nøyaktig? Det viser seg ikke.
Ulike lyder er en forskjellig modulert sinusbølge.Vi overfører bare diskrete verdier (frekvenser og amplituder), og sinusbølgen selv trenger ikke overføres - mottaksenheten kan generere den.Den genererer en sinusoid, og legges over denmodulasjon opprettet fra verdier overført over en kommunikasjonskanal. Det er nøyaktige prinsipper for hvilke diskrete verdier som må overføres slik at lyden ved inngangen til kommunikasjonskanalen faller sammen med lyden ved utgangen, hvor disse verdiene er lagt over en standard sinusoid (dette er hva Kotelnikovs teorem er Om).
Kotelnikovs setning (i engelskspråklig litteratur - Nyquist-Shannon-teoremet, lesestudien)- en grunnleggende uttalelse innen digitaliseringsignalbehandling, kobler kontinuerlige og diskrete signaler og sier at "enhver funksjon F(t), som består av frekvenser fra 0 til f1, kan overføres kontinuerlig med hvilken som helst nøyaktighet ved bruk av tall som følger hverandre gjennom 1/(2*f1) sekunder
Anti-interferens koding. Hamming koder
Hvis på en upålitelig kanal å overføreIvan Turgenevs kodede tekst, om enn med noen feil, vil resultere i en ganske meningsfull tekst. Men hvis vi trenger å overføre alt opp til litt, vil oppgaven være uløst: vi vet ikke hvilke biter som er feil, fordi feilen er tilfeldig. Selv sjekksummet sparer ikke alltid.
Det er derfor i dag når data overføresnettverk har en tendens til ikke så mye å optimal koding, hvor den maksimale mengden informasjon kan skyves inn i kanalen, men snarere til en slik koding (åpenbart overflødig) der feil kan gjenopprettes - akkurat som når vi leser ordene i Ivan Turgenevs fragment.
Det er spesielle feilkorrigerende koder som lar deg gjenopprette informasjon etter en feil. En av dem er Hamming-koden.La oss si at hele språket vårt består av tre ord:111000, 001110, 100011. Både kilden til meldingen og mottakeren kjenner disse ordene. Og vi vet at det oppstår feil i en kommunikasjonskanal, men når du overfører ett ord, blir ikke mer enn en bit informasjon forvrengt.
Anta at vi først sender ordet 111000. Som et resultat, har ikke mer enn en feil (vi har identifisert feilen) det kan bli et av ordene:
1) 111 000,011.000, 101000, 110000, 111100, 111010, 111001.
Ved overføring av ordet 001110 kan noen av ordene fås:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Til slutt, for 100011 kan vi komme i resepsjonen:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Merk at alle tre lister ikke er parvise.krysser hverandre. Med andre ord, hvis i den andre enden av kommunikasjonskanalen et hvilket som helst ord fra liste 1 dukker opp, vet mottakeren sikkert at ordet 111000 ble overført til ham, og hvis et ord fra liste 2 vises, vises ordet 001110 og fra liste 3 ordet 100011. De sier at vår kode fikse en feil.
Korreksjonen skjedde på grunn av to faktorer.Først kjenner mottakeren hele "ordboken", dvs. hendelsesplassen til meldingsmottakeren sammenfaller med plassen til den som sendte meldingen. Når koden ble overført med bare en feil, kom et ord ut, som ikke var i ordboken.
For det andre ble ord i ordboken valgt på en spesiell måte.Selv om det oppsto en feil, kunne ikke mottakerenforveksle ett ord med et annet. For eksempel, hvis ordboken består av ordene "datter", "prikk", "bump", og under overføringen var resultatet "vochka", vil mottakeren, som vet at et slikt ord ikke eksisterer, ikke være i stand til å rett feilen - hvilket som helst av de tre ordene kan vise seg å være riktig. Hvis ordboken inkluderer "prikk", "daw", "gren" og vi vet at ikke mer enn én feil er tillatt, så er "vochka" definitivt en "prikk" og ikke en "daw". I feilrettingskoder velges ord nøyaktig slik at de er "gjenkjennelige" selv etter en feil. Den eneste forskjellen er at koden "alfabet" bare har to bokstaver - null og en.
Redundansen av slik koding er veldig stor, og antallet ord som vi kan formidle er relativt liten.Vi må ekskludere et hvilket som helst ord fra ordboken,som, hvis det er en feil, kan falle sammen med hele listen som tilsvarer de overførte ordene (for eksempel kan ordene "datter" og "prikk" ikke være i ordboken). Men nøyaktig meldingsoverføring er så viktig at det brukes stor innsats på forskning på feilbestandige koder.
sensasjon
Begreper entropi (eller usikkerhet oguforutsigbarhet) av meldingen og redundansen (eller forhåndsbestemmelse og forutsigbarhet) samsvarer veldig naturlig med våre intuitive ideer om måleinformasjonen. Jo mer uforutsigbare meldingen (jo større dens entropi, fordi det er mindre sannsynlighet), jo mer informasjon det bærer. En følelse (for eksempel et møte med en krokodille på Tverskaya) er en sjelden hendelse, forutsigbarheten er svært lav, og derfor er informasjonen høy. Ofte kalles informasjon nyheter - rapporter om hendelser som nettopp har skjedd, om hvilke vi fortsatt ikke vet noe. Men hvis de forteller oss om andre og tredje ganger om de samme ordene, vil redundansen av meldingen være stor, dens uforutsigbarhet vil falle til null, og vi vil ikke bare lytte, vinker vekk fra taleren med ordene "Jeg vet jeg vet. Derfor prøver media å være så vanskelig å være den første. Denne korrespondansen til den intuitive følelsen av nyhet, som gir opphav til virkelig uventede nyheter, spilte en viktig rolle i det faktum at Shannons artikkel, som ikke var beregnet for den generelle leseren, ble en følelse som pressen vedtok, som forskere fra ulike spesialiteter godtok - fra lingvister og litterære kritikere til biologer.
MenShannon informasjonskonsept - streng matematisk teoriog dens anvendelse utenfor kommunikasjonsteori er svært upålitelig. Men i selve kommunikasjonsteorien spiller den en sentral rolle.
Semantisk informasjon
Shannon, introduserer begrepet entropi som et målinformasjon, fikk muligheten til å jobbe med informasjon – først og fremst å måle den og vurdere egenskaper som kanalkapasitet eller optimal koding. Men hovedantakelsen som tillot Shannon å lykkes med å operere med informasjon, var antakelsen om at generering av informasjon er en tilfeldig prosess som med hell kan beskrives i form av sannsynlighetsteori.Hvis prosessen er ikke-tilfeldig, det vil si, den overholder lovene (dessuten er det ikke alltid klart, som det skjer i naturlig språk), så er Shants resonnement ikke aktuelt for det.Ingenting Shannon sier har noe å gjøre med at informasjonen er meningsfull.
Mens vi snakker om tegn (eller bokstaver i alfabetet)Vi kan godt argumentere når det gjelder tilfeldige hendelser, men så snart vi kommer til språkets ord, vil situasjonen endres dramatisk. Tale er en prosess som er spesielt organisert, og her er strukturen i meldingen ikke mindre viktig enn tegnene som den overføres til.
For nylig virket det som om vi ikke kunne gjøre noe.gjort for i det minste på en eller annen måte å komme nærmere å måle tekstens meningsfullhet, men de siste årene har situasjonen begynt å endre seg. Og dette er først og fremst på grunn av bruken av kunstige nevrale nettverk til oppgavene med maskinoversettelse, automatisk oppsummering av tekster, uttrekk av informasjon fra tekster og generering av rapporter på naturlig språk. Alle disse oppgavene involverer transformering, koding og dekoding av meningsfull informasjon i naturlig språk. Og etter hvert dannes det en idé om informasjonstap under slike transformasjoner, og derfor om omfanget av meningsfull informasjon. Men i dag er klarheten og nøyaktigheten som Shannons informasjonsteori har, ennå ikke tilgjengelig i disse vanskelige problemene.