Tilfældigt hændelsesrum
I 1946 foreslog den amerikanske statistiker John Tukey navnet BIT
Forestil dig et rum af tilfældige begivenhedersom består i at kaste en falsk mønt, på begge sider er en ørn. Hvornår falder en ørn? Det er klart, at det altid. Vi ved dette på forhånd, fordi vores rum er så arrangeret. Fallet af en ørn er en pålidelig begivenhed, det vil sige, dens sandsynlighed er lig med 1. Vil vi give meget information, hvis vi siger om en faldet ørn? Nej. Vi vil overveje mængden af oplysninger i en sådan meddelelse lig med 0.
Lad os nu vende den fair mønt:på den ene side er det hoveder, og på den anden side haler, som det skal være. Landende hoveder eller haler vil være to forskellige begivenheder, der udgør vores rum af tilfældige begivenheder. Hvis vi rapporterer resultatet af et kast, vil det i sandhed være ny information. Hvis hoveder droppes, vil vi rapportere 0, og hvis haler er 1. For at rapportere denne information, skal vi kun bruge 1 bit.
Hvad ændrede sig?Der er opstået usikkerhed i vores arrangementsrum. Vi har noget at fortælle om det til en, der ikke selv kaster en mønt og ikke ser resultatet af kastet. Men for at forstå vores budskab ordentligt, skal han vide præcis, hvad vi laver, og hvad 0'erne og 1'erne betyder.Vores arrangement rum skal matche, og afkodningsprocessen er unik for at genskabe resultatet af kastet.Hvis senderens og modtagerens begivenhedsrum ikke er sammenfaldende, eller der ikke er mulighed for entydig afkodning af beskeden, forbliver informationen kun støj i kommunikationskanalen.
Hvis du kaster to uafhængigt og samtidigtmønter, så vil der være fire forskellige lige sandsynlige resultater: hoved-hoveder, hoved-haler, hale-hoveder og hale-haler. For at overføre information skal vi bruge 2 bit, og vores beskeder vil være som følger: 00, 01, 10 og 11. Der er dobbelt så meget information. Det skete, fordi usikkerheden steg. Hvis vi forsøger at gætte udfaldet af sådan et parret kast, har vi dobbelt chance for at tage fejl.
Jo større usikkerheden i begivenhedsrummet er, jo mere information indeholder beskeden om dets tilstand.
Lad os komplicere vores begivenhedsrum lidt.Hidtil har alle hændelser, der er sket, været lige sandsynlige. Men i virkelige rum har ikke alle begivenheder lige stor sandsynlighed. Lad os sige, at sandsynligheden for, at den krage, vi ser, bliver sort, er tæt på 1. Sandsynligheden for, at den første forbipasserende, vi møder på gaden, vil være en mand, er cirka 0,5. Men at møde en krokodille på Moskvas gader er næsten umuligt. Intuitivt forstår vi, at en rapport om et møde med en krokodille har meget større informationsværdi end om en sort krage.Jo lavere sandsynligheden for en begivenhed er, desto mere information i meddelelsen om en sådan begivenhed.
Lad arrangementet ikke være så eksotisk. Vi står lige ved vinduet og kigger på de passerende biler. Biler med fire farver passerer forbi, som vi skal rapportere. For at gøre dette vil vi kode farverne: sort - 00, hvid - 01, rød - 10, blå - 11. For at rapportere præcis hvilken bil der kørte, skal vi bare overføre 2 bits information.
Men for ganske lang tid at se bilerne,Vi bemærker, at bilens farve er ujævnt fordelt: sort - 50% (hvert sekund), hvid - 25% (hver fjerde), rød og blå - 12,5% (hver ottende). Derefter kan du optimere de overførte oplysninger.
De fleste af bilerne er sorte, sålad os betegne sort - 0 - den korteste kode, og lad koden for alle de andre starte ved 1. Af den resterende halvdel begynder hvid - 10, og de resterende farver ved 11. Lad os til sidst betegne rød - 110 og blå - 111.
Nu giver vi information om bilens farve, vi kan kode det nærmere.
Shannon Entropi
Lad vores arrangementsrum bestå af nforskellige begivenheder. Når man kaster en mønt med to hoveder, er der præcis én sådan begivenhed, når man kaster én fair mønt er der præcis 2, når man kaster to mønter eller ser biler, er der præcis 4. Hver begivenhed har en sandsynlighed for, at den indtræffer. Når man kaster en mønt med to hoveder, er der én begivenhed (falder hoveder), og dens sandsynlighed er p1 = 1. Når man kaster en fair mønt, er der to begivenheder, de er lige sandsynlige, og sandsynligheden for hver er 0,5: p1 = 0,5, p2 = 0,5. Når du kaster to fair mønter, er der fire begivenheder, de er alle lige sandsynlige, og sandsynligheden for hver er 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Når man observerer biler, er der fire hændelser, og de har forskellige sandsynligheder: sort - 0,5, hvid - 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 tilfældighed.Shannon valgte entropi (et mål for usikkerhed i tilfælderummet), således at tre betingelser var opfyldt:
- 1 Entropien af en pålidelig hændelse, hvis sandsynlighed er 1, er lig med 0.
- Entropien af to uafhængige hændelser er lig med summen af entropierne af disse begivenheder.
- Entropi er maksimal, hvis alle begivenheder er lige sandsynlige.
Alle disse krav er fuldt ud i overensstemmelse med voresideer om usikkerheden i arrangementsrummet. Hvis der kun er én begivenhed (det første eksempel), er der ingen usikkerhed. Hvis begivenhederne er uafhængige - usikkerheden af summen er lig med summen af usikkerheder - summer de simpelthen sammen (eksemplet med at kaste to mønter). Og endelig, hvis alle hændelser er lige sandsynlige, så er graden af systemets usikkerhed maksimal. Som i tilfældet med at kaste to mønter, er alle fire hændelser lige sandsynlige, og entropien er 2, den er større end i tilfældet med biler, hvor der også er fire hændelser, men de har forskellige sandsynligheder - i dette tilfælde er entropien 1,75.
Størrelsen H spiller en central rolle i informationsteori som et mål for information, valg og usikkerhed.
Claude Shannon
Claude Elwood Shannon- Amerikansk ingeniør, kryptoanalytiker ogmatematiker. Betragtes som "informationsalderens fader". Grundlægger af informationsteori, som har fundet anvendelse i moderne højteknologiske kommunikationssystemer. Forudsat grundlæggende begreber, ideer og deres matematiske formuleringer, der i øjeblikket danner grundlag for moderne kommunikationsteknologier.
I 1948, foreslået at bruge ordet "bit"at angive den mindste informationsenhed. Han viste også, at entropien, som han indtastede, svarer til usikkerheden omkring oplysningerne i den sendte besked. Shannons artikler "Matematisk teori for kommunikation" og "Teori for kommunikation i hemmelige systemer" betragtes som grundlæggende for informationsteori og kryptografi.
Under Anden Verdenskrig arbejdede Shannon hos Bell Laboratories for at udvikle kryptografiske systemer, som senere hjalp ham med at opdage fejlkorrigerende kodningsmetoder.
Shannon lavede et centralt bidrag til teorien om probabilistiske ordninger, spilteori, automatteori og styresystemteori - videnskabsområder, der er en del af begrebet cybernetik.
kodning
Og kastede mønter, og passerer biler er ikkesvarer til tallene 0 og 1. For at rapportere begivenheder, der forekommer i mellemrum, skal du tænke på en måde at beskrive disse begivenheder på. Denne beskrivelse kaldes kodning.
Beskeder kan kodes på et uendeligt antal forskellige måder. Men Shannon viste, at den korteste kode ikke kan være mindre i bit end entropien.
Det er derfor en meddelelses entropi er et måloplysninger i beskeden. Da antallet af bits under kodningen i alle de betragtede tilfælde er lig med entropi, betyder det, at kodningen var optimal. Kort sagt er det ikke længere muligt at indkode beskeder om begivenheder i vores rum.
Med optimal kodning kan du ikke miste ellerforvrænge en enkelt transmitteret bit i meddelelsen. Hvis blot en bit går tabt, vil informationen blive forvrænget. Men alle rigtige kommunikationskanaler giver ikke 100 procent tillid til, at alle dele af beskeden når frem til modtageren uforvrænget.
For at løse dette problem skal du gørekoden er ikke optimal, men overflødig. Send f.eks. sammen med beskeden dens kontrolsum - en specielt beregnet værdi opnået ved konvertering af beskedkoden, og som kan verificeres ved genberegning ved modtagelse af beskeden. Hvis den transmitterede kontrolsum stemmer overens med den beregnede, vil sandsynligheden for, at transmissionen var fejlfri, være ret stor. Og hvis kontrolsummen ikke stemmer overens, så skal der anmodes om en gentransmission. Det er nogenlunde sådan de fleste kommunikationskanaler fungerer i dag, for eksempel når man sender informationspakker over internettet.
Naturlige sprogbeskeder
Overvej begivenhedsrummet, der bestårfra stillinger i naturligt sprog. Dette er en speciel sag, men en af de vigtigste. Begivenhederne her vil være de overførte tegn (bogstaver af et fast alfabet). Disse tegn findes på sproget med forskellige sandsynligheder.
Mestfrekvenssymbolet (dvs. det somfindes mest i alle tekster skrevet på russisk) er et mellemrum: tusind tegn findes et gennemsnitligt rum 175 gange. Den anden i frekvensen er symbolet "o" - 90 efterfulgt af andre vokaler: "e" (eller "e" - vi skelner dem ikke) - 72, "a" - 62 og i - 62 og kun yderligere den første konsonant "t" - 53. Og den sjældneste "f" - dette symbol findes kun to gange pr. tusind tegn.
Vi vil bruge 31-bogstavet alfabet af russisksprog (det adskiller sig ikke fra "e" og "e", såvel som "ъ" og "ь"). Hvis alle bogstaverne var stødt på sproget med samme sandsynlighed, ville entropien pr. Symbol være H = 5 bit, men hvis vi tager hensyn til de reelle frekvenser af symbolerne, vil entropien være mindre: H = 4,35 bits. (Dette er næsten to gange mindre end ved traditionel kodning, når et tegn overføres som en byte - 8 bits).
Men entropien af karakteren i sproget er endnu lavere. Sandsynligheden for forekomsten af det næste tegn er ikke helt forudbestemt af gennemsnitsfrekvensen af karakteren i alle tekster. Hvilket tegn følger, afhænger af de tegn, der allerede er overført. For eksempel kan i moderne russisk efter symbolet "ъ" ikke følge konsonant symbol lyden. Efter to på hinanden følgende vokaler "e" følger den tredje vokal "e" ekstremt sjældent, medmindre i ordet "langhalset". Det vil sige, det næste tegn er til en vis grad forudbestemt. Hvis vi tager hensyn til sådan forudbestemt værdi af det næste symbol, vil usikkerheden (det vil sige informationen) for det næste symbol være endnu mindre end 4,35. Ifølge nogle estimater er det følgende symbol på russisk forudbestemt af sprogets struktur med mere end 50%, det vil sige med optimal kodning, kan al information overføres ved at slette halvdelen af bogstaverne fra meddelelsen.
En anden ting er, at ikke alle bogstaver kan slettes sikkert. Højfrekvente "o" (og generelt vokaler) er for eksempel let at krydse, men sjældne "f" eller "e" er ret problematiske.
Det naturlige sprog, som vi kommunikerer med hinanden på, er meget overflødigt og derfor pålideligt; hvis vi har hørt forkert, er det okay, informationen vil stadig blive transmitteret.
Men indtil Shannon introducerede måleinformationen, kunne vi ikke forstå, at sproget er overflødigt, og i hvilket omfang kan vi komprimere meddelelser (og hvorfor tekstfiler er så komprimerede af arkiveren).
Naturlig sprogafskedigelse
I artiklen "Om hvordan vi vorpsimanie tektkt"(navnet lyder nøjagtigt som dette!) Et fragment af Ivan Turgenevs Noble Nest-roman blev taget og underkastet en vis omdannelse: 34% af bogstaverne, men ikke tilfældige, blev slettet fra fragmentet. De første og sidste bogstaver i ord blev forladt, kun vokaler blev slettet, og ikke alle. Målet var ikke kun at få mulighed for at genoprette alle oplysninger om den konverterede tekst, men også for at sikre, at den person, der læste denne tekst, ikke oplevede særlige vanskeligheder på grund af manglende breve.
Hvorfor er det relativt nemt at læse dette ødelagttekst? Den indeholder faktisk den nødvendige information til at rekonstruere hele ord. En indfødt russisk har et bestemt sæt begivenheder (ord og hele sætninger), som han bruger i genkendelse. Derudover har taleren også standardsprogstrukturer til sin rådighed, der hjælper ham med at gendanne information. For eksempel,"Hun er blae blee"- med stor sandsynlighed kan læses som"Hun var mere følsom.". Men taget separat"Hun er mere bla", snarere vil blive genoprettet som"Hun var hvidere". Da vi i hverdagskommunikation handlermed kanaler, hvor der er støj og interferens, er vi ret gode til at gendanne information, men kun det, vi allerede kender i forvejen. For eksempel sætningen"Hendes træk er ikke i det mindste behagelige, og det er meget behageligt og sprøjtlæser godt bortset fra det sidste ord"Splash" - "rallied". Dette ord findes ikke i det moderne leksikon. Når du læser et ord hurtigt"Splls"lyder mere som "fast sammen"; når det er langsomt, forvirrer det simpelthen.
Signal Digitalisering
Lyd- eller akustiske svingninger er en sinusformet. Dette kan ses på for eksempel lydredigeringsskærmen. For nøjagtigt at formidle lyden skal du bruge et uendeligt antal værdier - hele sinusbølge. Dette er muligt med en analog forbindelse. Han synger - du lytter, kontakten afbrydes ikke, mens sangen varer.
I digital kommunikation over en kanal kan vi kun transmittere et begrænset antal værdier. Betyder det, at lyden ikke kan gengives nøjagtigt? Det viser sig ikke.
Forskellige lyde er en forskelligt moduleret sinusbølge.Vi overfører kun diskrete værdier (frekvenser og amplituder), og sinusbølgen selv behøver ikke overføres - modtagerenheden kan generere den.Det genererer en sinusoid og er overlejret på detmodulering skabt ud fra værdier transmitteret over en kommunikationskanal. Der er nøjagtige principper for, hvilke diskrete værdier der skal transmitteres, så lyden ved input til kommunikationskanalen falder sammen med lyden ved output, hvor disse værdier er overlejret på en standard sinusoid (det er hvad Kotelnikovs sætning er om).
Kotelnikovs sætning (i engelsksproglig litteratur - Nyquist-Shannon-sætningen, læsesetningen)- et grundlæggende udsagn inden for det digitalesignalbehandling, tilslutning af kontinuerlige og diskrete signaler og angivelse af, at "enhver funktion F(t), der består af frekvenser fra 0 til f1, kan transmitteres kontinuerligt med enhver nøjagtighed ved hjælp af tal, der følger hinanden gennem 1/(2*f1) sekunder
Anti-interferens kodning. Hamming koder
Hvis på en upålidelig kanal til at transmittereIvan Turgenevs kodede tekst, om end med nogle fejl, vil resultere i en ret meningsfuld tekst. Men hvis vi skal overføre alt op til en smule, vil opgaven være uløst: vi ved ikke, hvilke bits der er forkerte, fordi fejlen er tilfældig. Selv checksummet sparer ikke altid.
Det er derfor i dag, når data overføresnetværk har ikke en tendens til optimal kodning, hvor den maksimale mængde information kan skubbes ind i kanalen, men snarere til sådan kodning (selvfølgelig overflødig), hvor fejl kan genoprettes - ligesom når vi læser ordene i Ivan Turgenevs fragment.
Der er særlige fejlkorrigerende koder, der giver dig mulighed for at gendanne oplysninger efter en fejl. En af dem er Hamming-koden.Lad os sige, at hele vores sprog består af tre ord:111000, 001110, 100011. Både kilden til beskeden og modtageren kender disse ord. Og vi ved, at der opstår fejl i en kommunikationskanal, men når der sendes et ord, forvrænges ikke mere end en bit information.
Antag, at vi først passerer ordet 111000. Som følge heraf er der ikke mere end en fejl (vi har identificeret fejlen), det kan blive et af ordene:
1) 111000,011.000, 101000, 110000, 111100, 111010, 111001.
Ved overførsel af ordet 001110 kan ethvert af ordene opnås:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Endelig, for 100011 kan vi komme i receptionen:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Bemærk at alle tre lister ikke er parvise.skærer hinanden. Med andre ord, hvis der i den anden ende af kommunikationskanalen fremgår noget ord fra liste 1, ved modtageren sikkert, at ordet 111000 blev overført til ham, og hvis et ord fra liste 2 fremkommer, vises ordet 001110 og fra liste 3 ordet 100011. De siger, at vores kode fik en fejl.
Korrektionen skete på grund af to faktorer.For det første kender modtageren hele "ordbog", dvs. hændelsesrummet for meddelelsesmodtageren falder sammen med rummet for den, der sendte meddelelsen. Når koden blev overført med kun en fejl, kom der et ord ud, som ikke var i ordbogen.
For det andet blev ordene i ordbogen valgt på en særlig måde.Selvom der opstod en fejl, kunne modtageren ikkeforveksle et ord med et andet. For eksempel, hvis ordbogen består af ordene "datter", "prik", "bump", og under transmissionen var resultatet "vochka", så vil modtageren, der ved, at et sådant ord ikke eksisterer, ikke være i stand til at ret fejlen - hvilket som helst af de tre ord kan vise sig at være korrekt. Hvis ordbogen indeholder "prik", "daw", "gren", og vi ved, at ikke mere end én fejl er tilladt, så er "vochka" bestemt en "prik" og ikke en "daw". I fejlretningskoder vælges ord præcist, så de er "genkendelige" selv efter en fejl. Den eneste forskel er, at koden "alfabet" kun har to bogstaver - nul og et.
Redundansen af sådan kodning er meget stor, og antallet af ord, som vi således kan formidle, er relativt lille.Vi er nødt til at udelukke ethvert ord fra ordbogen,som i tilfælde af fejl kan falde sammen med hele listen svarende til de overførte ord (for eksempel kan ordene "datter" og "prik" ikke være i ordbogen). Men præcis meddelelsesoverførsel er så vigtig, at der bruges en stor indsats på forskning i fejlbestandige koder.
sensation
Begreber om entropi (eller usikkerhed oguforudsigelighed) af budskabet og redundansen (eller forudbestemmelse og forudsigelighed) svarer meget naturligt til vores intuitive ideer om informationsmåling. Jo mere uforudsigelige budskabet er (jo større er entropien, fordi der er mindre sandsynlighed), jo mere informationer den bærer. En fornemmelse (for eksempel et møde med en krokodille på Tverskaya) er en sjælden begivenhed, forudsigelsen er meget lav, og derfor er informationsværdien høj. Ofte kaldes information om nyheder - rapporter om begivenheder, der netop er sket, om hvilke vi stadig ikke ved noget. Men hvis de fortæller os om den anden og tredje gang om de samme ord, vil buddets redundans være stor, dens uforudsigelighed vil falde til nul, og vi vil simpelthen ikke lytte og vinker væk fra højttaleren med ordene "Jeg ved jeg ved." Derfor forsøger medierne så svært at være den første. Denne korrespondance med den intuitive følelse af nyhed, som giver anledning til virkelig uventede nyheder, spillede en stor rolle i, at Shannons artikel, som ikke var beregnet til den generelle læser, blev en fornemmelse, som pressen tog op som en universel nøgle til naturkendskabet. - fra lingvister og litterære kritikere til biologer.
MenShannon informationskoncept - streng matematisk teoriog dens anvendelse uden for kommunikationsteori er meget upålidelig. Men i selve kommunikationsteorien spiller den en central rolle.
Semantisk information
Shannon, der introducerer begrebet entropi som et målinformation, fik mulighed for at arbejde med information – først og fremmest at måle den og vurdere egenskaber som kanalkapacitet eller optimal kodning. Men hovedantagelsen, der gjorde det muligt for Shannon at arbejde med information med succes, var antagelsen om, at generering af information er en tilfældig proces, der med succes kan beskrives i form af sandsynlighedsteori.Hvis processen ikke er tilfældig, er den lydig af lovene (desuden er det ikke altid klart, som det sker i naturligt sprog), så er Shants argumentation ikke gældende for det.Intet Shannon siger har noget at gøre med, at informationen er meningsfuld.
Mens vi taler om tegn (eller bogstaver i alfabetet)vi kan godt argumentere for tilfældige begivenheder, men så snart vi kommer til sprogets ord, vil situationen ændre sig dramatisk. Tale er en proces, der er specielt organiseret, og her er meddelelsens struktur ikke mindre vigtig end de tegn, som den overføres til.
For nylig så det ud til, at vi ikke kunne gøre noget.gjort for i det mindste på en eller anden måde at komme tættere på at måle tekstens meningsfuldhed, men i de senere år er situationen begyndt at ændre sig. Og det skyldes primært brugen af kunstige neurale netværk til opgaverne med maskinoversættelse, automatisk opsummering af tekster, udtrækning af information fra tekster og generering af rapporter i naturligt sprog. Alle disse opgaver involverer transformation, kodning og afkodning af meningsfuld information indeholdt i naturligt sprog. Og efterhånden dannes der en idé om informationstab under sådanne transformationer og derfor om omfanget af meningsfuld information. Men i dag er den klarhed og nøjagtighed, som Shannons informationsteori har, endnu ikke tilgængelig i disse vanskelige problemer.