| Lektionsplanering och lektionsmaterial | 11:e klass | Planeringslektioner för läsåret (enligt läroboken av K.Yu. Polyakov, E.A. Eremina, fullständig fördjupningskurs, 4 timmar per vecka) | Informationsmängd

Lektion 2 - 3
Information och sannolikhet. Hartleys formel. Shannons formel
(§1. Informationsmängd)

Det blev möjligt att svara på denna fråga först efter att du studerat logaritmer i en matematikkurs. Från formeln

Det följer omedelbart att I är den potens till vilken 2 måste höjas för att få N, dvs logaritmen:

Denna formel kallas Hartleys formel för att hedra den amerikanske ingenjören Ralph Hartley, som föreslog det 1928.

Låt till exempel finnas 10 plan på flygfältet (med nummer från 1 till 10) och det är känt att ett av dem flyger till St. Petersburg.

Hur mycket information finns det i meddelandet "Plane nr. 2 flyger till St. Petersburg"? Vi har 10 alternativ, varav ett väljs, så enligt Hartleys formel är mängden information lika med

I = log 2 10 ≈ 3,322 bitar.

Observera att för värden på N som inte är lika med en heltalspotens 2, är mängden information i bitar ett bråktal.

Med hjälp av Hartleys formel kan du beräkna den teoretiska mängden information i ett meddelande. Låt oss anta att alfabetet (hela uppsättningen av giltiga tecken) innehåller 50 tecken (i det här fallet säger vi att alfabetets maktär lika med 50). Då är informationen vid mottagandet av varje symbol

I = log 2 50 ≈ 5,644 bitar.

Om ett meddelande innehåller 100 tecken är dess totala informationsvolym ungefär lika med

5,644 100 = 564,4 bitar.

I allmänhet är storleken på ett meddelande med längden L tecken som använder ett alfabet med N tecken lika med I = L log 2 N.

Sådan ett tillvägagångssätt att bestämma mängden information kallas alfabetiskt. Naturligtvis är det i praktiken omöjligt att använda ett icke-heltalsantal bitar för att koda ett tecken, så det första heltal används, vilket är större än det teoretiskt beräknade värdet. Om du till exempel använder ett alfabet på 50 tecken, kommer varje tecken att kodas med 6 bitar (50 ≤ 2 6 = 64).

Hur många olika meddelanden kan skickas om alfabetet och meddelandelängden är kända? Låt oss anta att 4 bokstäver används för att koda ett meddelande, som "A", "B", "C" och "D", och meddelandet består av två tecken. Eftersom varje karaktär kan väljas på 4 olika sätt, för varje val av det första tecknet finns det 4 val av det andra. Därför beräknas det totala antalet olika meddelanden på två bokstäver som 4 4 = 4 2 = 16. Om ytterligare ett tecken läggs till meddelandet, kan det tredje för var och en av de 16 kombinationerna av de två första tecknen vara vald på fyra sätt, så antalet olika tre-teckenmeddelanden är 4 4 4 = 4 3 = 64.

I allmänhet, om ett alfabet med N tecken används, är antalet olika möjliga meddelanden med längden L tecken Q = N L .

Nästa sida

När man studerade olika fenomen och föremål i omvärlden, försökte människor associera siffror med dessa föremål och introducera deras kvantitativa mått. Människor lärde sig att mäta avstånd, väga olika föremål, beräkna arean av figurer och volymer av kroppar. Efter att ha lärt oss att mäta tid och dess varaktighet försöker vi fortfarande förstå dess natur. Termometern uppfanns många år innan forskarna förstod vad den mätte: ungefär tre århundraden gick från uppfinningen av den första termometern till utvecklingen av termodynamiken. Den kvantitativa studien av ett visst fenomen eller objekt kan ligga före dess kvalitativa studie, och processen att bilda motsvarande begrepp kan följa den kvantitativa studien.

En liknande situation har utvecklats när det gäller information. R. Hartley 1928, och sedan K. Shannon 1948, föreslog formler för att beräkna mängden information, men de svarade aldrig på frågan om vad information är. Inom kommunikationsteori förekommer information i form av olika meddelanden: till exempel bokstäver eller siffror, som i telegrafi, eller som en kontinuerlig funktion av tiden, som i telefoni eller radiosändningar. I något av dessa exempel är uppgiften i slutändan att förmedla det semantiska innehållet i mänskligt tal. I sin tur kan mänskligt tal representeras i ljudvibrationer eller i skriftlig form.

Detta är en annan egenskap hos denna typ av information: förmågan att representera samma semantiska innehåll i olika fysiska former. W. Ashby var den första som uppmärksammade detta särskilt. Att representera information i olika fysiska former kallas kodning. För att kunna kommunicera med andra människor måste en person ständigt engagera sig i kodning, omkodning och avkodning. Det är uppenbart att information kan överföras genom kommunikationskanaler i en mängd olika kodningssystem.

R. Hartley var den första som introducerade metoden att "mäta mängden information" i teorin om informationsöverföring. Samtidigt trodde R. Hartley att informationen som han skulle mäta var "... en grupp fysiska symboler - ord, punkter, streck etc., som enligt allmän överenskommelse har en känd betydelse för motsvarande parter .” Således satte Hartley sig själv i uppgift att införa något slags mått för att mäta kodad information.

Låt en sekvens av n tecken a 1 a 2 a 3 a n sändas, som var och en tillhör alfabetet A m som innehåller m tecken. Vad är antalet K för olika varianter av sådana sekvenser? Om n = 1 (ett tecken sänds), då K = m; om n=2 (en sekvens av 2 tecken sänds), då K = m*m = m 2 ; i det allmänna fallet, för en sekvens av n tecken får vi

Hartley föreslog att man skulle beräkna mängden information som finns i en sådan sekvens som logaritmen av talet K till bas 2:

I = Log 2 K, (2.1)

där K = mn.

Det vill säga mängden information som finns i en sekvens av n tecken från alfabetet A m , i enlighet med Hartleys formel, är lika med

I = Log 2 (m n) = n Log 2 m. (2.2)

Anmärkning 1. Hartley antog att alla symboler i alfabetet A m kan förekomma med lika stor sannolikhet (frekvens) var som helst i meddelandet. Detta villkor överträds för alfabet med naturliga språk: till exempel förekommer inte alla bokstäver i det ryska alfabetet i texten med samma frekvens.

Anmärkning 2. Alla meddelanden med längden n i alfabetet A m kommer att innehålla samma mängd information. Till exempel, i alfabetet (0; 1), innehåller meddelandena 00111, 11001 och 10101 samma mängd information. Detta innebär att när vi beräknar mängden information som finns i ett meddelande distraheras vi från dess semantiska innehåll. Ett "meningsfullt" meddelande och ett meddelande som härleds från det genom en godtycklig symbolförändring kommer att innehålla samma mängd information.

Exempel. Ett telegrafmeddelande använder två symboler - en punkt (.) och ett bindestreck (-), d.v.s. alfabetet består av m = 2 tecken. Sedan, vid sändning av ett tecken (n = 1), mängden information I = Log 2 2 = 1. Denna mängd togs som en måttenhet för mängden information och kallas 1 bit (från engelska binär enhet = bit). Om ett telegrafmeddelande i alfabetet (. ; -) innehåller n tecken, så är informationsmängden I = n Log 2 2 = n (bitar).

Med hjälp av symbolerna 0 och 1 kodas information i en dator och när den sänds över datornätverk, d.v.s. alfabetet består av två tecken (0; 1); en symbol i detta fall innehåller också I = Log 2 2 = 1 informationsbitar, därför kommer ett meddelande med längden n tecken i alfabetet (0; 1) i enlighet med Hartleys formel (2.2) att innehålla n informationsbitar.

Om vi ​​betraktar överföringen av meddelanden i det ryska alfabetet, bestående av 33 bokstäver, är mängden information i ett meddelande med n tecken, beräknat med Hartleys formel, lika med I = n*Log 2 33 » n* 5,0444 bitar . Det engelska alfabetet innehåller 26 bokstäver, ett tecken innehåller Log 2 26 » 4,7 bitar, så ett meddelande på n tecken, beräknat med Hartleys formel, innehåller n* Log 2 26 » 4,7 *n bitar information. Detta resultat är dock inte korrekt, eftersom inte alla bokstäver förekommer i texten med samma frekvens. Dessutom måste skiljetecken läggas till bokstäverna i alfabetet: mellanslag, punkt, kommatecken, etc.

Formel (2.1) liknar ytligt Boltzmanns formel för att beräkna entropin för ett system med N lika sannolika mikrotillstånd:

S= - k*Ln(W), (2,3)

där k är Boltzmanns konstant = 1,38*10 -23, och W är sannolikheten för spontan adoption av ett av systemets mikrotillstånd per tidsenhet t = 10 -13 sekunder, W = 1/N, dvs.

S= -k*Ln(1/N) = k*Ln(N), (2,4)

vilket är helt förenligt med formel (2.1) med undantag för faktorn k och basen för logaritmen. På grund av denna externa likhet kallas värdet på Log 2 K i informationsteorin även för entropi och betecknas med symbolen H. Informationsentropi är ett mått på osäkerheten i tillståndet för någon slumpmässig variabel (fysiskt system) med en ändlig resp. räkneligt antal stater. Slumpmässigt värde(s.v.) är en storhet som till följd av ett experiment eller observation får ett numeriskt värde, som är okänt på förhand.

Så låt X vara en slumpvariabel som kan ta N olika värden x 1, x 2, ... x N; om alla värden för r.v. X är lika sannolika, då är entropin (mått på osäkerhet) för storheten X lika med:

H(X) = Log 2N. (2,5)

Kommentar. Om en slumpvariabel (system) bara kan vara i ett tillstånd (N=1), så är dess entropi lika med 0. I själva verket är det inte längre en slumpvariabel. Ju större antal möjliga lika sannolika tillstånd, desto högre är osäkerheten i ett system.

Entropi och mängden information mäts i samma enheter - bitar.

Definition. 1 bit är entropin för ett system med två lika sannolika tillstånd.

Låt system X vara i två tillstånd x1 och x2 med lika sannolikhet, d.v.s. N = 2; då dess entropi H(X) = Log 2 2 = 1 bit. Ett exempel på ett sådant system ges av ett mynt, när det kastas visas antingen huvuden (x1) eller svansar (x2). Om myntet är "korrekt", är sannolikheten att få huvuden eller svansar densamma och lika med 1/2.

Låt oss ge en annan definition av måttenheten för information.

Definition. Svaret på en fråga av vilken karaktär som helst (vilket som helst) innehåller 1 bit information om det kan vara "ja" eller "nej" med lika stor sannolikhet.

Exempel. Spel av "tom-tjock". Du gömmer ett litet föremål i ena handen och ber din partner att gissa i vilken hand du gömt det. Han frågar dig "i din vänstra hand?" (eller helt enkelt väljer en hand: vänster eller höger). Du svarar "ja" om han gissade rätt, eller "nej" annars. För varje svar får partnern 1 bit information, och osäkerheten i situationen är helt borta.

Hartleys formel kan användas när man löser problem med att bestämma det valda elementet i en given mängd. Detta resultat kan formuleras som följande regel.

Om i en given uppsättning M, bestående av N element, något element x väljs, om vilket inget annat är känt, är det för att bestämma detta element nödvändigt att erhålla Log 2 N bitar av information.

Låt oss överväga flera problem med Hartleys formel.

Uppgift 1. Någon har tänkt på ett naturligt tal i intervallet 1 till 32. Vilket är det minsta antalet frågor som måste ställas för att garanterat gissa det avsedda (markerade) numret. Svaren kan bara vara "ja" eller "nej".

En kommentar. Du kan försöka gissa det avsedda antalet genom enkel sökning. Om du har tur behöver du bara ställa en fråga, men i värsta fall måste du ställa 31 frågor. I den föreslagna uppgiften måste du bestämma det minsta antalet frågor med vilka du garanterat kommer att bestämma det avsedda antalet.

Lösning. Med hjälp av Hartleys formel kan du beräkna mängden information som behöver erhållas för att bestämma det valda elementet x från mängden heltal (1,2,3 32). För att göra detta måste du få H = Log 2 32 = 5 bitar av information. Frågor måste ställas på ett sådant sätt att svaren på dem är lika sannolika. Då kommer svaret på varje sådan fråga att ge 1 bit information. Du kan till exempel dela upp siffrorna i två lika stora grupper från 1 till 16 och från 17 till 32 och fråga vilken grupp det avsedda numret finns i. Därefter bör du göra samma sak med den valda gruppen, som redan innehåller endast 16 nummer, etc. Låt till exempel tänka på siffran 7.

Fråga nr 1: Hör det avsedda numret till uppsättningen (17; 32)? Svaret "nej" ger dig 1 bit information. Vi vet nu att numret tillhör mängden (1; 16).

Fråga nr 2: Hör det tänkta numret till uppsättningen (1; 8)? Att svara "ja" ger dig ytterligare 1 bit information. Vi vet nu att numret hör till mängden (1; 8).

Fråga nr 3: Hör det tänkta numret till uppsättningen (1; 4)? Svaret "nej" ger dig ytterligare 1 bit information. Vi vet nu att numret hör till mängden (5; 8).

Fråga nr 4: Hör det tänkta numret till uppsättningen (7; 8)? Att svara "ja" ger dig ytterligare 1 bit information. Vi vet nu att numret hör till mängden (7; 8).

Fråga nr 5: Är det avsedda antalet lika med 8? Svaret "nej" ger dig ytterligare 1 bit information. Vi vet nu att det avsedda antalet är 7. Problemet är löst. Fem frågor ställdes, 5 bitar av information mottogs som svar och det avsedda antalet bestämdes. ‚

Problem 2. (Problem med ett falskt mynt). Det finns 27 mynt, varav 26 är riktiga och ett är falskt. Vilket är det minsta antalet vägningar på en hävstångsvåg för vilket ett falskt mynt av 27 kan identifieras tillförlitligt, med hjälp av det faktum att det falska myntet är lättare än det riktiga?

Spakvåg har två koppar och med deras hjälp kan du bara avgöra om innehållet i kopparna är lika i vikt, och om inte, så är innehållet i vilken kopp som är tyngre.

Lösning. Detta är en uppgift för att identifiera ett utvalt element av 27. Med Hartleys formel kan vi omedelbart bestämma mängden information som behöver erhållas för att identifiera ett falskt mynt: det är lika med I = Log 2 27 = Log 2 (3) 3) = 3 log 2 3 bitar. Observera att utan att ännu veta vägningsstrategin kan vi säga hur mycket information vi behöver få för att lösa problemet.

Om du lägger lika många mynt på vågen är tre lika sannolika utfall möjliga:

1. Den vänstra koppen är tyngre än den högra (L > R);

2. Den vänstra koppen är lättare än den högra (L< П);

3. Den vänstra koppen är i balans med den högra (L = R);

"Spakvågssystemet" kan vara i tre lika sannolika tillstånd, så en vägning ger Log 2 3 bitar av information. Totalt, för att lösa problemet behöver du få I = 3 Logga 2 3 bitar av information, vilket innebär att du måste göra tre vägningar för att fastställa ett falskt mynt. Vi vet redan det lägsta antalet vägningar, men vi vet ännu inte hur de ska genomföras. Strategin bör vara sådan att varje vägning ger maximal informationsmängd. Låt oss dela upp alla mynten i tre lika högar A, B och C, 9 bitar vardera. Ett falskt mynt, betecknat med bokstaven f, kan hittas i någon av de tre högarna med lika stor sannolikhet. Låt oss välja två av dem, till exempel A och B, och väga dem.

Det finns tre möjliga resultat:

1) A är tyngre än B (A > B); betyder fÎB;

2) A är lättare än B (A< B); значит f Î A;

3) A är i jämvikt med B (A = B); betyder f Î C.

För vilket resultat som helst kommer vi att bestämma i vilken hög det falska myntet f finns, men i denna hög kommer det bara finnas 9 mynt. Dela den i tre lika högar A1, B1, C1, 3 mynt i varje. Låt oss välja vilka två som helst och väga dem. Som i föregående steg kommer vi att bestämma i vilken hög med mynt det falska myntet finns, men nu består högen av endast tre mynt. Låt oss välja två valfria mynt och väga dem. Detta blir den sista, tredje vägningen, varefter vi hittar det förfalskade myntet.

Problem 3. Utan att använda en miniräknare, uppskatta, till närmaste bit, entropin för ett system som kan vara i 50 tillstånd med lika sannolikhet.

Lösning. Med hjälp av Hartleys formel, H = Log 2 50. Låt oss utvärdera detta uttryck.

Uppenbarligen 32< 50 < 64; логарифмируем это неравенство à Log 2 32 < Log 2 50 < Log 2 64 à 5 < Log 2 50 < 6. Энтропия системы с точностью до 1 бита 5 < H < 6 . ‚

Uppgift 4. Det är känt att entropin i systemet är 7 bitar. Bestäm antalet tillstånd i detta system om det är känt att de alla är lika sannolika.

Lösning. Låt oss beteckna med N antalet tillstånd i systemet. Eftersom alla tillstånd är lika sannolika, så är H = Log 2 N à N = 2 H, d.v.s. N = 27 = 128.

Information kan finnas i form av:

texter, teckningar, teckningar, fotografier;

ljus- eller ljudsignaler;

radiovågor;

elektriska och nervimpulser;

magnetiska inspelningar;

gester och ansiktsuttryck;

dofter och smakupplevelser;

kromosomer, genom vilka organismers egenskaper och egenskaper ärvs osv.

Objekt, processer, fenomen av materiella eller immateriella egenskaper, betraktade ur deras informationsegenskaper, kallas informationsobjekt.

1.4. Hur överförs information?

Information överförs i form av meddelanden från någon informationskälla till dess mottagare genom en kommunikationskanal mellan dem. Källan sänder ett sänt meddelande, som kodas till en sänd signal. Denna signal skickas över en kommunikationskanal. Som ett resultat visas en mottagen signal vid mottagaren, som avkodas och blir det mottagna meddelandet.

Ett meddelande som innehåller information om väderprognosen sänds till mottagaren (TV-tittaren) från källan - en meteorolog - via en kommunikationskanal - TV-sändningsutrustning och en TV.

En levande varelse med sina sinnesorgan (öga, öra, hud, tunga etc.) uppfattar information från omvärlden, bearbetar den till en viss sekvens av nervimpulser, överför impulser längs nervfibrer, lagrar den i minnet i form av tillståndet i hjärnans neurala strukturer, reproducerar i form av ljudsignaler, rörelser, etc., används i processen av sitt liv.

Överföring av information via kommunikationskanaler åtföljs ofta av störningar, vilket orsakar förvrängning och förlust av information.

1.5. Hur mäts mängden information?

Hur mycket information finns i verk av stora poeter, författare, poeter eller i den mänskliga genetiska koden? Vetenskapen ger inga svar på dessa frågor och kommer med all sannolikhet inte att ge svar snart. Är det möjligt att objektivt mäta mängden information? Det viktigaste resultatet av informationsteorin är följande slutsats:

Under vissa, mycket breda förhållanden, är det möjligt att försumma informationens kvalitativa egenskaper, uttrycka dess kvantitet som ett tal och även jämföra mängden information som finns i olika grupper av data.

För närvarande har metoder för att definiera begreppet "mängd information" blivit utbredda, baserat på det faktum att informationen i ett meddelande kan tolkas löst i betydelsen av dess nyhet eller, med andra ord, minska osäkerheten i vår kunskap om ett föremål. Dessa tillvägagångssätt använder matematiska begrepp sannolikheter Och logaritm

Metoder för att bestämma mängden information. Hartley och Shannon formler.

Amerikansk ingenjör R. Hartley 1928 ansågs processen att erhålla information som valet av ett meddelande från en ändlig förutbestämd uppsättning av N lika sannolika meddelanden, och mängden information jag innehöll i det valda meddelandet definierades som den binära logaritmen av N.

Hartleys formel: I = log 2 N

Låt oss säga att du behöver gissa ett nummer från en uppsättning nummer från ett till hundra. Med hjälp av Hartleys formel kan du räkna ut hur mycket information som krävs för detta: I = log 2 100 = 6,644. Således innehåller ett meddelande om ett korrekt gissat nummer en mängd information som är ungefär lika med 6,644 informationsenheter.

Låt oss ge andra exempel på lika sannolika meddelanden:

när du kastar ett mynt: "Det kom upp i huvudet", "huvuden föll";

på boksidan: "antalet bokstäver är jämnt", "antalet bokstäver är udda".

Låt oss nu avgöra om meddelandena är lika sannolika "Den första kvinnan att lämna byggnadens dörrar" Och "Mannen kommer att vara den första att lämna dörren till byggnaden". Det är omöjligt att besvara denna fråga entydigt. Allt beror på vilken typ av byggnad vi pratar om. Om det här till exempel är en biograf, så är sannolikheten att lämna dörren först densamma för en man och en kvinna, och om det här är en militärkasern, så är sannolikheten för en man mycket högre än för en kvinna.

För problem av detta slag, den amerikanske vetenskapsmannen Claude Shannon föreslog 1948 en annan formel för att bestämma mängden information, med hänsyn till den möjliga ojämna sannolikheten för meddelanden i uppsättningen.

Shannons formel: I = - (s 1 logga 2 sid 1 +s 2 logga 2 sid 2 + . . . +s N logga 2 sid N ), där sid i- sannolikheten att exakt i Det e meddelandet väljs i en uppsättning av N meddelanden.

Det är lätt att se att om sannolikheterna sid 1 , ..., sid När lika, då är var och en av dem lika 1/N, och Shannons formel förvandlas till Hartleys formel.

Utöver de två övervägda metoderna för att bestämma informationsmängden finns det andra. Det är viktigt att komma ihåg att alla teoretiska resultat endast är tillämpliga på ett visst antal fall, som beskrivs av de initiala antagandena.

Som en informationsenhet föreslog Claude Shannon att ta en bit (engelsk. bit - bi nary digit - binär siffra).

Biti informationsteori- mängden information som krävs för att skilja mellan två lika sannolika meddelanden (som "huvuden" - "svansar", "jämna" - "udda", etc.). I datoranvändning En bit är den minsta "delen" av datorns minne som krävs för att lagra ett av de två tecknen "0" och "1" som används för intern maskinrepresentation av data och instruktioner.

Lite är en för liten måttenhet. I praktiken används en större enhet oftare - byte, lika med åtta bitar. Det är exakt åtta bitar som krävs för att koda något av de 256 tecknen i datorns tangentbordsalfabet (256 = 2 8).

Även större härledda informationsenheter används också i stor utsträckning:

1 kilobyte (KB) = 1024 byte = 2 10 byte,

1 megabyte (MB) = 1024 KB = 2 20 byte,

1 Gigabyte (GB) = 1024 MB = 2 30 byte.

Nyligen, på grund av ökningen av volymen bearbetad information, har sådana härledda enheter som:

1 Terabyte (TB) = 1024 GB = 2 40 byte,

1 Petabyte (PB) = 1024 TB = 2 50 byte.

Per informationsenhet kunde man välja hur mycket information som behövs för att skilja mellan till exempel tio lika sannolika meddelanden. Detta kommer inte att vara en binär (bit), utan en decimal (dit) informationsenhet.

Denna formel, liksom Hartleys formel, används inom datavetenskap för att beräkna den totala mängden information med olika sannolikheter.

Ett exempel på olika ojämlika sannolikheter är människors utträde från barackerna i en militär enhet. En soldat, en officer och till och med en general kan lämna barackerna. Men fördelningen av soldater, officerare och generaler i barackerna är olika, vilket är uppenbart, eftersom det kommer att finnas flest soldater, sedan officerare i antal, och den sällsynta typen kommer att vara generaler. Eftersom sannolikheterna inte är lika för alla tre typer av militär, för att beräkna hur mycket information en sådan händelse kommer att ta, använder vi Shannons formel.

För andra lika sannolika händelser, som en myntkastning (sannolikheten att huvuden eller svansar dyker upp är densamma - 50%), används Hartleys formel.

Låt oss nu titta på tillämpningen av denna formel med ett specifikt exempel:

Vilket meddelande innehåller minst information (Räkna i bitar):

1. Vasily åt 6 godis, varav 2 var berberis.
2. Det finns 10 mappar på datorn, den önskade filen hittades i mapp 9.
3. Baba Luda gjorde 4 pajer med kött och 4 pajer med kål. Gregory åt 2 pajer.
4. Afrika har 200 dagar med torrt väder och 165 dagar med monsunregn. afrikanen jagade 40 dagar om året.

Låt oss i detta problem uppmärksamma det faktum att alternativ 1, 2 och 3 är lätta att räkna, eftersom händelserna är lika sannolika. Och för detta kommer vi att använda Hartleys formel I = log 2 N(Fig. 1) Men med punkt 4 där det är tydligt att fördelningen av dagar inte är jämn (övervikt mot torrt väder), vad ska vi då göra i detta fall? För sådana händelser används Shannons formel eller informationsentropi: I = - (p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p N log 2 p N),(Fig.3)

FORMEL FÖR MÄNGD INFORMATION (HARTLEY FORMEL, FIG. 1)

Vart i:

• I - mängd information
• p är sannolikheten att denna händelse kommer att inträffa

De händelser som intresserar oss i vårt problem är

1. Det fanns två berberisar av sex (2/6)
2. Det fanns en mapp där den önskade filen hittades i förhållande till det totala antalet (1/10)
3. Det blev åtta pajer totalt, varav Gregory åt två (2/8)
4. och de senaste fyrtio dagarnas jakt i förhållande till tvåhundra torra dagar och fyrtio dagars jakt i förhållande till hundra sextiofem regndagar. (40/200) + (40/165)

så får vi att:

SANNOLIKHETSFORMEL FÖR ETT HÄNDELSE.

Där K är händelsen vi är intresserade av, och N är det totala antalet av dessa händelser, även för att kontrollera dig själv, kan sannolikheten för en viss händelse inte vara större än en. (eftersom det alltid är färre sannolika händelser)

SHANNONS FORMEL FÖR ATT BERÄKNA INFORMATION (FIG. 3)

Låt oss återgå till vår uppgift och beräkna hur mycket information som finns.

Förresten, när du beräknar logaritmen är det bekvämt att använda webbplatsen - https://planetcalc.ru/419/#

• För det första fallet - 2/6 = 0,33 = och sedan Log 2 0,33 = 1,599 bitar
• För det andra fallet - 1/10 = 0,10 Log 2 0,10 = 3,322 bitar
• För den tredje - 2/8 = 0,25 = Log 2 0,25 = 2 bitar
• För den fjärde - 40/200 + 40/165 = 0,2 respektive 0,24, då beräknar vi med formeln -(0,2 * log 2 0,2) + -(o,24 * log 2 0,24) = 0,95856 bitar

Således var svaret på vårt problem 4.

Skicka ditt goda arbete i kunskapsbasen är enkelt. Använd formuläret nedan

Studenter, doktorander, unga forskare som använder kunskapsbasen i sina studier och arbete kommer att vara er mycket tacksamma.

Postat på http://www.allbest.ru

1. Informationsteori

Informationsteori (eller matematisk kommunikationsteori) är en gren av cybernetik som studerar processerna för lagring, transformation och överföring av information; som vilken matematisk teori som helst, arbetar den med matematiska modeller och inte med verkliga fysiska objekt (källor och kommunikationskanaler). Använder främst den matematiska apparaten sannolikhetsteorin och matematisk statistik.

Claude Shannon (1916-2001) kallas "informationsteorins fader".

Informationsteori bygger på ett visst sätt att mäta mängden information. Informationsteori, som kommer från problem inom kommunikationsteori, betraktas ibland som en matematisk teori för informationsöverföringssystem. Baserat på K. Shannons (1948) framträdande arbete, fastställer informationsteori de grundläggande gränserna för kapaciteten hos informationsöverföringssystem, sätter de första principerna för deras utveckling och praktiska genomförande.

Informationens grundläggande egenskaper kan beskrivas med hjälp av en matematisk modell som speglar många av de karakteristiska egenskaperna hos ett informationsmått som det vanligtvis förstås intuitivt. Informationskällan och kommunikationskanalen genom vilken information överförs kan modelleras med hjälp av probabilistiska representationer. Entropin för en informationskälla är lika med logaritmen för det (effektiva) antalet meddelanden som den genererar. Detta är ett mått på källbeskrivningens komplexitet (eller, som det ibland sägs, ett mått på meddelandets osäkerhet). Denna förståelse av entropi är nära relaterad till begreppet entropi som används inom termodynamiken.

Fysiskt kan överföringen av information representeras som induktionen av det erforderliga fysiska tillståndet i den mottagande anordningen. Avsändaren har för avsikt att sända ett meddelande till mottagaren. Kärnan i överföringen är att reproducera det sända meddelandet vid utgången av kommunikationskanalen. Vid tidpunkten för överföringen väljer avsändaren det önskade meddelandet från en lista över alla möjliga meddelanden. Mottagaren vet inte i förväg vilken som kommer att väljas. (Om han hade blivit informerad om detta i förväg, då skulle det inte behövas skicka meddelandet.) Kommunikationskanalen introducerar slumpmässigt brus i processen att överföra information, vilket förvränger meddelandet och därmed gör det svårt att läsa. I början av kommunikationsprocessen är mottagaren i fullständig osäkerhet om vilket meddelande som väljs från en lista över möjliga. I slutet av kommunikationen vet mottagaren detta, d.v.s. den exakta beskrivningen av det valda meddelandet blir känd.

En kommunikationskanals förmåga att överföra information kännetecknas av ett visst antal - genomströmning (kapacitet), lika med logaritmen för det effektiva antalet meddelanden som kan särskiljas vid dess utgång. Processen för informationsöverföring kan anses tillförlitlig om meddelandeöverföringshastigheten är mindre än kanalkapaciteten. Annars är tillförlitlig överföring av information omöjlig. Huvudresultatet av informationsteorin är påståendet: om källans entropi är mindre än kanalkapaciteten, kan originalmeddelandet vid dess utgång reproduceras med ett godtyckligt litet fel; om källans entropi överstiger dess bärförmåga är det omöjligt att göra felet litet.

Svårigheten att förmedla ett budskap beror inte på dess innehåll; Det är inte mindre svårt att förmedla meningslösa budskap än meningsfulla. Till exempel kan siffran 23 i ett sammanhang vara priset på ett fat olja, och i ett annat kan det vara numret på vinnaren av ett lopp. Innebörden av ett meddelande beror på sammanhang och semantik, och svårigheten för dess överföring bestäms endast av listan över möjliga meddelanden (och deras sannolikheter).

Varje informationsöverföringssystem kan anses bestå av: en meddelandekälla, en sändare, en kommunikationskanal och en mottagande anordning, samt en mottagare. Till exempel när man pratar i telefon är källan talaren, meddelandet är hans tal. Kommunikationskanalen är ledningar som överför en elektrisk signal från talaren till lyssnaren - mottagaren av meddelandet. En kommunikationskanal är ett medium för att sända en signal från en sändare till en mottagare. När signalen passerar genom kanalen kan den påverkas av störningar, vilket skapar förvrängningar i värdena för informationsparametrarna för signalen.

Mellan avsändaren av meddelandet och kommunikationskanalen kan det finnas enheter som omvandlar meddelandet till en form som är lämplig för överföring över kommunikationskanalen. En avkodare installerad i den andra änden av kanalen rekonstruerar det mottagna meddelandet.

Studiet av informationsöverföringssystem börjar med källan till meddelanden. En stor mängd information kan överföras via en kommunikationskanal: text, direktsändning, musik eller bilder. För varje källa kan du ange en lista över meddelanden som den kan generera. Till exempel sänder källan till telegrafiska meddelanden eller telexmeddelanden endast bokstäver och innehåller till exempel inte musiknoter. Om levande tal sänds över en kommunikationskanal förlorar signalen användbart innehåll vid en frekvens över 20 000 Hz, den övre gränsen som uppfattas av mänsklig hörsel. Dessa fakta kan användas när man utformar ingången för en kommunikationskanal.

För att uppskatta mängden information i ett meddelande i informationsteori, används ett logaritmiskt mått som introducerats av R. Hartley, vars probabilistiska tolkning gavs i Shannons verk. Om sannolikheten för att meddelande x dyker upp är p(x), och 0<р (х)<1, то количество информации - I(x), содержащееся в сообщении, определяется формулой:

Postat på http://www.allbest.ru

Postat på http://www.allbest.ru

2. Hartley och Shannon formler

1928 Den amerikanske ingenjören Ralph Hartley betraktar processen att erhålla information som att välja ett meddelande från en ändlig given uppsättning av N lika sannolika händelser.

Hartleys formel:

K=log2 N,

där K är mängden information, N är antalet lika sannolika händelser.

Hartleys formel kan också skrivas på följande sätt: N=2k

Eftersom förekomsten av var och en av N händelser har samma sannolikhet P, då:

där P är sannolikheten för att händelsen inträffar.

Då kan formeln skrivas annorlunda:

1948 föreslog den amerikanske forskaren Claude Shannon en annan formel för att bestämma mängden information, med hänsyn till den möjliga ojämna sannolikheten för händelser i uppsättningen.

Shannons formel:

K = - (p1 *log2 p1+ p2 *log 2p 2 + p 3 *log 2p 3 +…+ pi * log2 pi),

där pi är sannolikheten att det är det i:te meddelandet som väljs i en uppsättning av N meddelanden.

Denna formel kan också skrivas:

Modern vetenskap om informationens egenskaper och informationsprocessernas mönster kallas informationsteori. Innehållet i begreppet "information" kan avslöjas med exemplet med två historiskt första tillvägagångssätt för att mäta mängden information: Hartleys och Shannon:s tillvägagångssätt: det första av dem är baserat på mängdteori och kombinatorik, och det andra på sannolikhetsteori.

Information kan förstås och tolkas i olika problem och ämnesområden på olika sätt. Som ett resultat finns det olika tillvägagångssätt för att definiera mätningen av information och olika sätt att införa ett mått på informationsmängden.

Informationsmängden är ett numeriskt värde som adekvat karakteriserar den uppdaterade informationen i termer av mångfald, komplexitet, struktur (ordning), säkerhet och val av tillstånd i det visade systemet.

Om vi ​​överväger ett system som kan ta ett av n möjliga tillstånd, så är den faktiska uppgiften att utvärdera detta val, resultatet. En sådan bedömning kan vara ett mått på information (händelse).

Ett mått är en kontinuerlig verklig icke-negativ funktion definierad på en uppsättning händelser och som är additiv.

Åtgärder kan vara statiska och dynamiska, beroende på vilken typ av information de tillåter att utvärdera: statisk (inte uppdaterad; i själva verket utvärderas meddelanden utan att ta hänsyn till resurser och formen för uppdatering) eller dynamiska (uppdaterad, d.v.s. resurskostnader för uppdatering) är också utvärderad information).

Det finns olika sätt att bestämma mängden information. De vanligaste är volymetriska och probabilistiska.

Volym tillvägagångssätt.

Det binära talsystemet används eftersom det i en teknisk anordning är lättast att implementera två motsatta fysiska tillstånd: magnetiserat/ej magnetiserat, på/av, laddat/ej laddat och andra.

Mängden information som registreras i binära tecken i datorns minne eller på ett externt lagringsmedium beräknas helt enkelt genom antalet binära tecken som krävs för sådan inspelning. I det här fallet är ett icke-heltalsantal bitar inte möjligt.

För att underlätta användningen har större enheter informationskvantitet än bitar införts. Således innehåller ett binärt ord med åtta tecken en byte information, 1024 byte bildar en kilobyte (KB), 1024 kilobyte bildar en megabyte (MB) och 1024 megabyte bildar en gigabyte (GB).

Entropi (probabilistisk) tillvägagångssätt.

Detta tillvägagångssätt används i informations- och kodningsteori. Denna mätmetod är baserad på följande modell: mottagaren av meddelandet har en viss uppfattning om hur vissa händelser kan inträffa. Dessa idéer är i allmänhet opålitliga och uttrycks av sannolikheterna med vilka han förväntar sig den eller den händelsen. Det allmänna måttet på osäkerhet kallas entropi. Entropi kännetecknas av ett visst matematiskt beroende av den totala sannolikheten för att dessa händelser ska inträffa.

Mängden information i ett meddelande bestäms av hur mycket detta mått har minskat efter mottagandet av meddelandet: ju större entropi systemet har, desto större grad av osäkerhet. Ett inkommande meddelande tar helt eller delvis bort denna osäkerhet, därför kan mängden information mätas efter hur mycket entropin i systemet har minskat efter att ha tagit emot meddelandet. Samma entropi, men med motsatt tecken, tas som ett mått på mängden information.

R. Hartleys tillvägagångssätt bygger på grundläggande mängdteoretiska, väsentligen kombinatoriska grunder, samt flera intuitivt tydliga och ganska uppenbara antaganden.

Om det finns många element och ett av dem väljs, så kommuniceras eller genereras en viss mängd information. Denna information är att om det före urvalet inte var känt vilket element som skulle väljas, så blir det känt efter urvalet. Det är nödvändigt att hitta den typ av funktion som kopplar samman mängden information som erhålls när man väljer ett visst element från en uppsättning med antalet element i denna uppsättning, d.v.s. med dess kraft.

Om den uppsättning element från vilken ett val görs består av ett enda element, så är det tydligt att dess val är förutbestämt, dvs. det finns ingen osäkerhet om valet - noll mängd information.

Om uppsättningen består av två delar är osäkerheten i valet minimal. I det här fallet är mängden information minimal.

Ju fler element i uppsättningen, desto större osäkerhet i valet, desto mer information.

Således uppfyller det logaritmiska måttet på information som föreslås av Hartley samtidigt villkoren för monotonitet och additivitet. Hartley kom själv fram till sitt mått på grundval av heuristiska överväganden liknande de nyss beskrivna, men det har nu rigoröst bevisats att det logaritmiska måttet för informationsmängden entydigt följer av dessa två förhållanden som han postulerade.

1948, för att utforska problemet med rationell överföring av information genom en bullrig kommunikationskanal, föreslog Claude Shannon ett revolutionerande probabilistiskt tillvägagångssätt för att förstå kommunikation och skapade den första riktigt matematiska teorin om entropi. Hans sensationella idéer blev snabbt grunden för utvecklingen av två stora områden: informationsteori, som använder begreppet sannolikhet och ergodisk teori för att studera de statistiska egenskaperna hos data- och kommunikationssystem, och kodningsteori, som huvudsakligen använder algebraiska och geometriska verktyg för att utveckla effektiva koder.

Claude Shannon föreslog att vinsten i information är lika med förlusten av osäkerhet, och ställde krav för dess mätning:

1. Åtgärden måste vara kontinuerlig. det vill säga en förändring i värdet av sannolikhetsvärdet med ett litet belopp bör orsaka en liten resulterande förändring i funktionen;

2. om alla alternativ (bokstäver i det givna exemplet) är lika sannolika, bör en ökning av antalet alternativ (bokstäver) alltid öka värdet på funktionen;

3. Det ska vara möjligt att göra ett val (i vårt exempel på bokstäver) i två steg, där värdet på slutresultatfunktionen ska vara summan av de mellanliggande resultatfunktionerna.

Därför måste entropifunktionen uppfylla villkoren:

definierad och kontinuerlig för alla,

var för alla och. (Det är lätt att se att denna funktion bara beror på sannolikhetsfördelningen, men inte på alfabetet).

För positiva heltal måste följande olikhet gälla:

För positiva heltal, där måste likheten gälla:

informationsbandbreddsentropi

Shannon fastställde att en mätning av entropi som tillämpas på en informationskälla kunde bestämma den minsta kanalkapacitet som krävs för att tillförlitligt överföra information i form av kodade binära tal. För att härleda Shannons formel är det nödvändigt att beräkna den matematiska förväntan på "mängden information" som finns i en figur från informationskällan. Shannon-entropimåttet uttrycker osäkerheten i implementeringen av en slumpvariabel. Entropi är alltså skillnaden mellan informationen i ett meddelande och den del av informationen som är exakt känd (eller väl förutspådd) i meddelandet. Ett exempel på detta är språkets redundans - det finns uppenbara statistiska mönster i utseendet på bokstäver, par av på varandra följande bokstäver, trillingar, etc.

Postat på Allbest.ru

Liknande dokument

Beräkning av mängden information per tecken med Shannons formel. Förändringar i informationsentropi i texter av ekonomiskt, naturvetenskapligt och litterärt innehåll. Maximal mängd information per tecken enligt Hartleys formel.

laboratoriearbete, tillagt 2013-12-06


Ämne och uppgifter för informationsteori, dess funktioner i skapandet av automatiserade styrsystem. Bestämning av genomströmningen av diskreta (digitala) kanaler i frånvaro av brus. Beräkning av informationsöverföringshastighet. Beräkning av entropivärdet - den genomsnittliga mängden information.

test, tillagt 2015-01-18


Bit, osäkerhet, mängd information och entropi. Shannons formel. Hartleys formel. Logaritmer. Mängden information som tas emot under kommunikationsprocessen. Interaktion mellan källan och mottagaren av information. Antal, informationskapacitet för minnesceller.

abstrakt, tillagt 2008-07-17


Det centrala begreppet cybernetik är information. Komplex automatisering av processerna för perception, transformation, överföring, bearbetning och visning av information och skapandet av automatiserade kontrollsystem på olika nivåer. Informationsöverföringssystem.

bok, tillagd 2009-07-05


Grunderna i teorin om informationsöverföring. Experimentell studie av kvantitativa aspekter av information. Mängd information om Hartley och K. Shannon. Frekvensegenskaper för textmeddelanden. Mängden information som ett mått på osäkerhet borttagen.

laboratoriearbete, tillagt 2011-02-15


presentation, tillagd 2014-10-19


Grundläggande begrepp om informationsteori som vetenskap. Den genomsnittliga mängden information per 1 tecken bestäms av Shannons formel. Allmänt schema för meddelandeöverföring. Kanalkapacitet. Boolesk algebra och teknisk implementering av beräkningsprocessen.

presentation, tillagd 2013-08-13


Konceptet och metoderna för att söka efter information, metoder för att lagra den och funktioner i överföringsprocessen från källa till mottagare. Syftet med kommunikationskanalen och kodningsenheten. Regler för behandling av information, dess användning i beslutsfattande och skyddsåtgärder.

presentation, tillagd 2013-10-14


Totalt antal meddelanden som inte upprepas. Beräkning av informationsöverföringshastighet och kommunikationskanalkapacitet. Bestämning av meddelanderedundans och optimal kodning. Proceduren för att konstruera en optimal kod med Shannon-Fano-metoden.

kursarbete, tillagd 2009-04-17


Mekanismen för att överföra information, dess kvantitet och mätkriterier. Informationsenheter beroende på basen för logaritmen. Grundläggande egenskaper och egenskaper hos mängden information, dess entropi. Bestämning av entropi och redundans för informationsmeddelanden.