Vi gjorde det!
"Syftet med den här kursen är att förbereda dig för din tekniska framtid."
Hej, Habr. Kom ihåg den fantastiska artikeln (+219, 2588 bokmärken, 429 XNUMX lästa)?
Så Hamming (ja, ja, självövervakning och självkorrigerande ) det finns en helhet , skriven utifrån hans föreläsningar. Vi översätter det, eftersom mannen säger vad han tycker.
Det här är en bok som inte bara handlar om IT, det är en bok om hur otroligt coola människor tänker. "Det är inte bara ett uppsving för positivt tänkande; den beskriver de förhållanden som ökar chanserna att göra ett bra arbete.”
Tack till Andrey Pakhomov för översättningen.
Informationsteori utvecklades av C. E. Shannon i slutet av 1940-talet. Bell Labs ledning insisterade på att han skulle kalla det "kommunikationsteori" eftersom... detta är ett mycket mer exakt namn. Av förklarliga skäl har namnet "Informationsteori" en mycket större inverkan på allmänheten, varför Shannon valde det, och det är namnet vi känner till än i dag. Namnet i sig antyder att teorin handlar om information, vilket gör den viktig när vi går djupare in i informationsåldern. I det här kapitlet kommer jag att beröra flera huvudslutsatser från denna teori, jag kommer att ge inte strikta, utan snarare intuitiva bevis på några individuella bestämmelser i denna teori, så att du förstår vad "Informationsteori" faktiskt är, var du kan tillämpa den och var inte.
Först och främst, vad är "information"? Shannon likställer information med osäkerhet. Han valde den negativa logaritmen för sannolikheten för en händelse som ett kvantitativt mått på informationen du får när en händelse med sannolikhet p inträffar. Till exempel, om jag berättar att vädret i Los Angeles är dimmigt, så är p nära 1, vilket egentligen inte ger oss mycket information. Men om jag säger att det regnar i Monterey i juni blir det osäkerhet i beskedet och det kommer att innehålla mer information. En tillförlitlig händelse innehåller ingen information, eftersom log 1 = 0.
Låt oss titta på detta mer i detalj. Shannon ansåg att det kvantitativa måttet på information borde vara en kontinuerlig funktion av sannolikheten för en händelse p, och för oberoende händelser borde den vara additiv - mängden information som erhålls som ett resultat av förekomsten av två oberoende händelser bör vara lika med mängd information som erhållits till följd av att en gemensam händelse inträffat. Till exempel behandlas resultatet av ett tärningskast och ett myntkast vanligtvis som oberoende händelser. Låt oss översätta ovanstående till matematikens språk. Om I (p) är mängden information som finns i en händelse med sannolikhet p, så får vi för en gemensam händelse bestående av två oberoende händelser x med sannolikhet p1 och y med sannolikhet p2
(x och y är oberoende händelser)
Detta är den funktionella Cauchy-ekvationen, sann för alla p1 och p2. För att lösa denna funktionella ekvation, anta att
p1 = p2 = p,
detta ger
Om p1 = p2 och p2 = p då
etc. Om man förlänger denna process med standardmetoden för exponentialer, för alla rationella tal m/n gäller följande
Av informationsmåttets antagna kontinuitet följer att den logaritmiska funktionen är den enda kontinuerliga lösningen på den funktionella Cauchy-ekvationen.
Inom informationsteorin är det vanligt att ta logaritmbasen till 2, så ett binärt val innehåller exakt 1 bit information. Därför mäts information med formeln
Låt oss pausa och förstå vad som hände ovan. Först och främst definierade vi inte begreppet "information", vi definierade helt enkelt formeln för dess kvantitativa mått.
För det andra är denna åtgärd föremål för osäkerhet, och även om den är rimligen lämplig för maskiner – till exempel telefonsystem, radio, tv, datorer etc. – speglar den inte normala mänskliga attityder till information.
För det tredje är detta ett relativt mått, det beror på det aktuella läget för din kunskap. Om du tittar på en ström av "slumptal" från en slumptalsgenerator, antar du att varje nästa tal är osäkert, men om du kan formeln för att beräkna "slumptal" kommer nästa tal att vara känt, och därför inte innehålla information.
Så Shannons definition av information är lämplig för maskiner i många fall, men verkar inte passa den mänskliga förståelsen av ordet. Det är av denna anledning som "Informationsteori" borde ha kallats "Kommunikationsteori". Det är dock för sent att ändra definitionerna (som gav teorin dess ursprungliga popularitet och som fortfarande får folk att tro att denna teori handlar om "information"), så vi måste leva med dem, men samtidigt måste du tydligt förstå hur långt Shannons definition av information är från dess vanliga betydelse. Shannons information handlar om något helt annat, nämligen osäkerhet.
Här är något att tänka på när du föreslår någon terminologi. Hur stämmer en föreslagen definition, som Shannons definition av information, överens med din ursprungliga idé och hur annorlunda är den? Det finns nästan ingen term som exakt återspeglar din tidigare vision av ett koncept, men i slutändan är det den använda terminologin som återspeglar innebörden av konceptet, så att formalisera något genom tydliga definitioner introducerar alltid en del brus.
Betrakta ett system vars alfabet består av symboler q med sannolikheter pi. I detta fall genomsnittlig mängd information i systemet (dess förväntade värde) är lika med:
Detta kallas entropin för systemet med sannolikhetsfördelning {pi}. Vi använder termen "entropi" eftersom samma matematiska form förekommer inom termodynamik och statistisk mekanik. Det är därför som termen "entropi" skapar en viss aura av betydelse runt sig själv, som i slutändan inte är motiverad. Samma matematiska form av notation innebär inte samma tolkning av symboler!
Entropin av sannolikhetsfördelningen spelar en stor roll i kodningsteorin. Gibbs-olikheten för två olika sannolikhetsfördelningar pi och qi är en av de viktiga konsekvenserna av denna teori. Så det måste vi bevisa
Beviset är baserat på en uppenbar graf, Fig. 13.I, vilket visar det
och likhet uppnås endast när x = 1. Låt oss tillämpa olikheten på varje term av summan från vänster sida:
Om alfabetet i ett kommunikationssystem består av q-symboler, tar vi sannolikheten för överföring av varje symbol qi = 1/q och ersätter q, får vi från Gibbs-olikheten
Figur 13.I
Detta betyder att om sannolikheten att sända alla q-symboler är densamma och lika med - 1 / q, så är den maximala entropin lika med ln q, annars gäller olikheten.
När det gäller en unikt avkodningsbar kod har vi Krafts ojämlikhet
Om vi nu definierar pseudo-sannolikheter
var såklart = 1, vilket följer av Gibbs ojämlikhet,
och tillämpa lite algebra (kom ihåg att K ≤ 1, så att vi kan släppa den logaritmiska termen, och kanske förstärka ojämlikheten senare), får vi
där L är den genomsnittliga kodlängden.
Således är entropi den minimala gränsen för varje tecken-för-symbol-kod med en genomsnittlig kodordslängd L. Detta är Shannons sats för en störningsfri kanal.
Betrakta nu huvudsatsen om begränsningarna för kommunikationssystem där information överförs som en ström av oberoende bitar och brus är närvarande. Det är underförstått att sannolikheten för korrekt överföring av en bit är P > 1/2, och sannolikheten för att bitvärdet kommer att inverteras under överföring (ett fel kommer att uppstå) är lika med Q = 1 - P. För enkelhetens skull har vi anta att felen är oberoende och att sannolikheten för ett fel är densamma för varje skickad bit - det vill säga det finns "vitt brus" i kommunikationskanalen.
Sättet vi har en lång ström av n bitar kodad i ett meddelande är den n-dimensionella förlängningen av enbitskoden. Vi kommer att bestämma värdet på n senare. Betrakta ett meddelande som består av n-bitar som en punkt i det n-dimensionella rummet. Eftersom vi har ett n-dimensionellt utrymme - och för enkelhetens skull kommer vi att anta att varje meddelande har samma sannolikhet att inträffa - det finns M möjliga meddelanden (M kommer också att definieras senare), därför är sannolikheten för ett meddelande som skickas
(avsändare)
Schema 13.II
Överväg sedan idén om kanalkapacitet. Utan att gå in på detaljer definieras kanalkapacitet som den maximala mängd information som kan överföras tillförlitligt över en kommunikationskanal, med hänsyn tagen till användningen av den mest effektiva kodningen. Det finns inget argument för att mer information kan överföras via en kommunikationskanal än dess kapacitet. Detta kan bevisas för en binär symmetrisk kanal (som vi använder i vårt fall). Kanalkapaciteten, vid sändning av bitar, anges som
där, som tidigare, P är sannolikheten för inget fel i någon skickad bit. Vid sändning av n oberoende bitar ges kanalkapaciteten av
Om vi är nära kanalkapaciteten måste vi skicka nästan denna mängd information för var och en av symbolerna ai, i = 1, ..., M. Med tanke på att sannolikheten för förekomst av varje symbol ai är 1 / M, vi får
när vi skickar något av M lika sannolika meddelanden ai, har vi
När n bitar skickas förväntar vi oss att nQ-fel uppstår. I praktiken, för ett meddelande som består av n-bitar, kommer vi att ha ungefär nQ-fel i det mottagna meddelandet. För stort n, relativ variation (variation = distributionsbredd, )
fördelningen av antalet fel kommer att bli allt smalare när n ökar.
Så från sändarsidan tar jag meddelandet ai för att skicka och ritar en sfär runt den med en radie
vilket är något större med ett belopp lika med e2 än det förväntade antalet fel Q, (Figur 13.II). Om n är tillräckligt stort, så finns det en godtyckligt liten sannolikhet för att en meddelandepunkt bj dyker upp på mottagarsidan som sträcker sig bortom denna sfär. Låt oss skissa situationen som jag ser den ur sändarens synvinkel: vi har alla radier från det sända meddelandet ai till det mottagna meddelandet bj med en felsannolikhet lika (eller nästan lika med) normalfördelningen, som når ett maximum av nQ. För varje given e2 finns ett n så stort att sannolikheten för att den resulterande punkten bj ligger utanför min sfär är så liten som du vill.
Låt oss nu titta på samma situation från din sida (Fig. 13.III). På mottagarsidan finns det en sfär S(r) med samma radie r runt den mottagna punkten bj i ett n-dimensionellt utrymme, så att om det mottagna meddelandet bj är inuti min sfär, så är meddelandet ai som jag skickat inuti din sfär.
Hur kan ett fel uppstå? Felet kan uppstå i de fall som beskrivs i tabellen nedan:
Figur 13.III
Här ser vi att om det i sfären som är byggd kring den mottagna punkten finns minst en punkt till som motsvarar ett eventuellt skickat okodat meddelande, så uppstod ett fel under överföringen, eftersom du inte kan avgöra vilket av dessa meddelanden som skickades. Det skickade meddelandet är felfritt endast om punkten som motsvarar det är i sfären, och det inte finns några andra punkter möjliga i den givna koden som är i samma sfär.
Vi har en matematisk ekvation för sannolikheten för fel Pe om meddelande ai skickades
Vi kan kasta ut den första faktorn i den andra termen, ta den som 1. Därmed får vi ojämlikheten
Det är uppenbart att
därmed
återansöka till den sista terminen till höger
Om du tar n tillräckligt stor, kan den första termen tas så liten som önskas, säg mindre än ett antal d. Därför har vi
Låt oss nu titta på hur vi kan konstruera en enkel ersättningskod för att koda M meddelanden som består av n bitar. Utan att ha någon aning om exakt hur man konstruerar en kod (felkorrigerande koder hade ännu inte uppfunnits), valde Shannon slumpmässig kodning. Slå ett mynt för var och en av de n bitarna i meddelandet och upprepa processen för M meddelanden. Totalt måste nM coin flips göras, så det är möjligt
kodordböcker med samma sannolikhet ½nM. Naturligtvis innebär den slumpmässiga processen att skapa en kodbok att det finns en möjlighet till dubbletter, samt kodpunkter som kommer att ligga nära varandra och därför vara en källa till troliga fel. Man måste bevisa att om detta inte sker med en sannolikhet som är större än någon liten vald felnivå, så är det givna n tillräckligt stort.
Den avgörande punkten är att Shannon tog ett genomsnitt av alla möjliga kodböcker för att hitta medelfelet! Vi kommer att använda symbolen Av[.] för att beteckna medelvärdet över mängden av alla möjliga slumpmässiga kodböcker. Medelvärde över en konstant d ger naturligtvis en konstant, eftersom för medelvärdesberäkning är varje term densamma som alla andra termer i summan,
som kan ökas (M–1 går till M)
För ett givet meddelande, när medelvärdesberäkning över alla kodböcker, går kodningen genom alla möjliga värden, så den genomsnittliga sannolikheten för att en punkt är i en sfär är förhållandet mellan sfärens volym och den totala rymdvolymen. Volymen av sfären är
där s=Q+e2 <1/2 och ns måste vara ett heltal.
Den sista termen till höger är den största i denna summa. Låt oss först uppskatta dess värde med hjälp av Stirling-formeln för fakulteter. Vi kommer sedan att titta på den minskande faktorn för termen framför den, notera att denna faktor ökar när vi flyttar till vänster, och så kan vi: (1) begränsa värdet av summan till summan av den geometriska progressionen med denna initiala koefficient, (2) expandera den geometriska progressionen från ns termer till ett oändligt antal termer, (3) beräkna summan av en oändlig geometrisk progression (standardalgebra, inget signifikant) och slutligen erhålla gränsvärdet (för en tillräckligt stor n):
Lägg märke till hur entropin H(s) dök upp i den binomiala identiteten. Observera att Taylor-seriens expansion H(s)=H(Q+e2) ger en uppskattning som erhålls med hänsyn till endast den första derivatan och ignorerar alla andra. Låt oss nu sätta ihop det slutliga uttrycket:
där
Allt vi behöver göra är att välja e2 så att e3 < e1, och då blir den sista termen godtyckligt liten, så länge n är tillräckligt stor. Följaktligen kan det genomsnittliga PE-felet erhållas så litet som önskas med kanalkapaciteten godtyckligt nära C.
Om medelvärdet av alla koder har ett tillräckligt litet fel måste åtminstone en kod vara lämplig, därför finns det åtminstone ett lämpligt kodningssystem. Detta är ett viktigt resultat som Shannon har erhållit - "Shannons teorem för en bullrig kanal", även om det bör noteras att han bevisade detta för ett mycket mer allmänt fall än för den enkla binära symmetriska kanalen som jag använde. För det allmänna fallet är de matematiska beräkningarna mycket mer komplicerade, men idéerna är inte så olika, så väldigt ofta, med hjälp av exemplet på ett visst fall, kan du avslöja den sanna innebörden av satsen.
Låt oss kritisera resultatet. Vi har upprepade gånger upprepat: "För tillräckligt stort n." Men hur stort är n? Väldigt, väldigt stort om du verkligen vill vara både nära kanalkapaciteten och vara säker på korrekt dataöverföring! Faktiskt så stor att du kommer att behöva vänta väldigt länge för att samla ett meddelande med tillräckligt många bitar för att koda det senare. I det här fallet kommer storleken på slumpkodslexikonet helt enkelt att vara enorm (trots allt kan en sådan ordbok inte representeras i en kortare form än en komplett lista över alla Mn-bitar, trots att n och M är väldigt stora)!
Felkorrigerande koder undviker att vänta på ett väldigt långt meddelande och sedan koda och avkoda det genom väldigt stora kodböcker eftersom de själva undviker kodböcker och använder vanlig beräkning istället. I enkel teori tenderar sådana koder att förlora förmågan att närma sig kanalkapaciteten och fortfarande behålla en låg felfrekvens, men när koden korrigerar ett stort antal fel presterar de bra. Med andra ord, om du allokerar viss kanalkapacitet till felkorrigering, måste du använda felkorrigeringsförmågan för det mesta, d.v.s. ett stort antal fel måste korrigeras i varje meddelande som skickas, annars slösar du bort denna kapacitet.
Samtidigt är den ovan bevisade satsen fortfarande inte meningslös! Det visar att effektiva överföringssystem måste använda smarta kodningsscheman för mycket långa bitsträngar. Ett exempel är satelliter som har flugit bortom de yttre planeterna; När de rör sig bort från jorden och solen tvingas de korrigera fler och fler fel i datablocket: vissa satelliter använder solpaneler, som ger cirka 5 W, andra använder kärnkraftskällor, som ger ungefär samma effekt. Strömförsörjningens låga effekt, den lilla storleken på sändarskålar och den begränsade storleken på mottagarplattor på jorden, det enorma avståndet som signalen måste färdas - allt detta kräver användning av koder med en hög nivå av felkorrigering för att bygga en effektivt kommunikationssystem.
Låt oss återgå till det n-dimensionella utrymmet som vi använde i beviset ovan. När vi diskuterade det visade vi att nästan hela volymen av sfären är koncentrerad nära den yttre ytan - alltså är det nästan säkert att den skickade signalen kommer att vara belägen nära ytan av sfären byggd runt den mottagna signalen, även med en relativt liten radie för en sådan sfär. Därför är det inte förvånande att den mottagna signalen, efter att ha korrigerat ett godtyckligt stort antal fel, nQ, visar sig vara godtyckligt nära en signal utan fel. Länkkapaciteten vi diskuterade tidigare är nyckeln till att förstå detta fenomen. Observera att liknande sfärer konstruerade för felkorrigerande Hamming-koder inte överlappar varandra. Det stora antalet nästan ortogonala dimensioner i n-dimensionellt rum visar varför vi kan passa in M sfärer i rymden med liten överlappning. Om vi tillåter en liten, godtyckligt liten överlappning, vilket kan leda till endast ett litet antal fel under avkodningen, kan vi få en tät placering av sfärer i rymden. Hamming garanterade en viss nivå av felkorrigering, Shannon - en låg sannolikhet för fel, men bibehöll samtidigt den faktiska genomströmningen godtyckligt nära kommunikationskanalens kapacitet, vilket Hamming-koder inte kan göra.
Informationsteorin talar om för oss inte hur man designar ett effektivt system, men den visar vägen mot effektiva kommunikationssystem. Det är ett värdefullt verktyg för att bygga maskin-till-maskin kommunikationssystem, men, som nämnts tidigare, har det liten relevans för hur människor kommunicerar med varandra. I vilken utsträckning biologiskt arv är som tekniska kommunikationssystem är helt enkelt okänd, så det är för närvarande inte klart hur informationsteori gäller gener. Vi har inget annat val än att försöka, och om framgången visar oss den maskinliknande naturen hos detta fenomen, kommer misslyckande att peka på andra viktiga aspekter av informationens natur.
Låt oss inte avvika för mycket. Vi har sett att alla ursprungliga definitioner, i större eller mindre utsträckning, måste uttrycka essensen av våra ursprungliga övertygelser, men de kännetecknas av en viss grad av förvrängning och är därför inte tillämpliga. Det är traditionellt accepterat att den definition vi använder i slutändan faktiskt definierar essensen; men detta berättar bara för oss hur vi ska bearbeta saker och förmedlar inte på något sätt någon mening för oss. Det postulerande tillvägagångssättet, så starkt gynnat i matematiska kretsar, lämnar mycket övrigt att önska i praktiken.
Nu ska vi titta på ett exempel på IQ-tester där definitionen är så cirkulär som du vill att den ska vara och som ett resultat vilseledande. Ett test skapas som ska mäta intelligens. Den revideras sedan för att göra den så konsekvent som möjligt och sedan publiceras den och kalibreras på ett enkelt sätt så att den uppmätta ”intelligensen” visar sig vara normalfördelad (på en kalibreringskurva förstås). Alla definitioner måste kontrolleras igen, inte bara när de först föreslås, utan också mycket senare, när de används i de slutsatser som dras. I vilken utsträckning är definitionsgränserna lämpliga för det problem som ska lösas? Hur ofta kommer definitioner som ges i en miljö att tillämpas i helt olika miljöer? Detta händer ganska ofta! Inom humaniora, som du oundvikligen kommer att stöta på i ditt liv, händer detta oftare.
Således var ett av syftena med denna presentation av informationsteori, förutom att visa dess användbarhet, att varna dig för denna fara, eller att visa dig exakt hur du använder den för att uppnå önskat resultat. Det har länge noterats att initiala definitioner avgör vad du hittar i slutändan, i mycket större utsträckning än det verkar. Inledande definitioner kräver mycket uppmärksamhet från dig, inte bara i en ny situation, utan också inom områden som du har arbetat med länge. Detta gör att du kan förstå i vilken utsträckning de erhållna resultaten är en tautologi och inte något användbart.
Den berömda historien om Eddington berättar om människor som fiskade i havet med ett nät. Efter att ha studerat storleken på fisken de fångade, bestämde de minimistorleken på fisk som finns i havet! Deras slutsats drevs av det instrument som användes, inte av verkligheten.
Fortsättning ...
Vem vill hjälpa till med översättning, layout och publicering av boken – skriv i ett personligt meddelande eller mejl [e-postskyddad]
Vi har förresten även lanserat översättningen av en annan cool bok - )
Vi söker speciellt de som hjälper till att översätta . (överföring i 10 minuter, de första 20 har redan tagits)
Bokens innehåll och översatta kapitel
- Introduktion till The Art of Doing Science and Engineering: Learning to Learn (28 mars 1995)
- "Foundations of the Digital (Discrete) Revolution" (30 mars 1995)
- "History of Computers - Hardware" (31 mars 1995)
- "History of Computers - Software" (4 april 1995)
- "History of Computers - Applications" (6 april 1995)
- "Artificiell intelligens - del I" (7 april 1995)
- "Artificiell intelligens - del II" (11 april 1995)
- "Artificiell intelligens III" (13 april 1995)
- "n-Dimensional Space" (14 april 1995)
- "Coding Theory - The Representation of Information, Del I" (18 april 1995)
- "Coding Theory - The Representation of Information, Del II" (20 april 1995)
- "Felkorrigerande koder" (21 april 1995)
- "Informationsteori" (25 april 1995)
- "Digitala filter, del I" (27 april 1995)
- "Digitala filter, del II" (28 april 1995)
- "Digitala filter, del III" (2 maj 1995)
- "Digitala filter, del IV" (4 maj 1995)
- "Simulering, del I" (5 maj 1995)
- "Simulering, del II" (9 maj 1995)
- "Simulering, del III" (11 maj 1995)
- "Fiber Optics" (12 maj 1995)
- "Computer Aided Instruction" (16 maj 1995)
- "Matematik" (18 maj 1995)
- "Quantum Mechanics" (19 maj 1995)
- "Kreativitet" (23 maj 1995). Översättning:
- "Experter" (25 maj 1995)
- "Otillförlitliga data" (26 maj 1995)
- "Systems Engineering" (30 maj 1995)
- "Du får vad du mäter" (1 juni 1995)
- (Juni 2, 1995) översätt i 10 minuters bitar
- Hamming, "Du och din forskning" (6 juni 1995).
Vem vill hjälpa till med översättning, layout och publicering av boken – skriv i ett personligt meddelande eller mejl [e-postskyddad]
Källa: will.com