Vi gjorde det!
"Formålet med dette kursus er at forberede dig til din tekniske fremtid."
Hej, Habr. Husk den fantastiske artikel (+219, 2588 bogmærker, 429 læste)?
Så Hamming (ja, ja, selvovervågning og selvkorrigerende ) der er en helhed , skrevet på baggrund af hans forelæsninger. Vi oversætter det, fordi manden siger sin mening.
Dette er en bog, der ikke kun handler om IT, det er en bog om utroligt seje menneskers tænkestil. “Det er ikke kun et boost af positiv tænkning; den beskriver de forhold, der øger chancerne for at udføre et godt stykke arbejde.”
Tak til Andrey Pakhomov for oversættelsen.
Informationsteori blev udviklet af C. E. Shannon i slutningen af 1940'erne. Bell Labs ledelse insisterede på, at han kaldte det "Kommunikationsteori", fordi... dette er et meget mere præcist navn. Af indlysende årsager har navnet "Information Theory" en langt større indflydelse på offentligheden, hvorfor Shannon valgte det, og det er det navn, vi kender den dag i dag. Selve navnet antyder, at teorien omhandler information, hvilket gør den vigtig, når vi bevæger os dybere ind i informationsalderen. I dette kapitel vil jeg komme ind på flere hovedkonklusioner fra denne teori, jeg vil ikke give strenge, men snarere intuitive beviser for nogle individuelle bestemmelser i denne teori, så du forstår, hvad "informationsteori" faktisk er, hvor du kan anvende den og hvor ikke.
Først og fremmest, hvad er "information"? Shannon sidestiller information med usikkerhed. Han valgte den negative logaritme for sandsynligheden for en begivenhed som et kvantitativt mål for den information, du modtager, når en begivenhed med sandsynlighed p indtræffer. For eksempel, hvis jeg fortæller dig, at vejret i Los Angeles er tåget, så er p tæt på 1, hvilket virkelig ikke giver os meget information. Men hvis jeg siger, at det regner i Monterey i juni, vil der være usikkerhed i beskeden, og den vil indeholde flere oplysninger. En pålidelig hændelse indeholder ingen information, da log 1 = 0.
Lad os se på dette mere detaljeret. Shannon mente, at det kvantitative mål for information skulle være en kontinuerlig funktion af sandsynligheden for en hændelse p, og for uafhængige hændelser burde den være additiv - mængden af information opnået som et resultat af forekomsten af to uafhængige hændelser skulle være lig med mængden af information indhentet som følge af forekomsten af en fælles begivenhed. For eksempel behandles resultatet af et terningkast og et møntkast normalt som uafhængige begivenheder. Lad os oversætte ovenstående til matematikkens sprog. Hvis I (p) er mængden af information indeholdt i en hændelse med sandsynlighed p, så får vi for en fælles hændelse bestående af to uafhængige hændelser x med sandsynlighed p1 og y med sandsynlighed p2
(x og y er uafhængige begivenheder)
Dette er den funktionelle Cauchy-ligning, sand for alle p1 og p2. For at løse denne funktionelle ligning, antag det
p1 = p2 = p,
dette giver
Hvis p1 = p2 og p2 = p så
etc. Udvidelse af denne proces ved hjælp af standardmetoden for eksponentialer, for alle rationelle tal m/n gælder følgende
Af informationsmålets formodede kontinuitet følger det, at den logaritmiske funktion er den eneste kontinuerlige løsning på Cauchy funktionelle ligning.
I informationsteori er det almindeligt at tage logaritmebasen til at være 2, så et binært valg indeholder præcis 1 bit information. Derfor måles information ved formlen
Lad os holde pause og forstå, hvad der skete ovenfor. Først og fremmest definerede vi ikke begrebet "information", vi definerede blot formlen for dets kvantitative mål.
For det andet er denne foranstaltning behæftet med usikkerhed, og selvom den er rimeligt egnet til maskiner – for eksempel telefonsystemer, radio, fjernsyn, computere osv. – afspejler den ikke normale menneskelige holdninger til information.
For det tredje er dette et relativt mål, det afhænger af din videns nuværende tilstand. Hvis du ser på en strøm af "tilfældige tal" fra en tilfældig talgenerator, antager du, at hvert næste tal er usikkert, men hvis du kender formlen til at beregne "tilfældige tal", vil det næste tal være kendt, og vil derfor ikke indeholde oplysninger.
Så Shannons definition af information er passende for maskiner i mange tilfælde, men synes ikke at passe til den menneskelige forståelse af ordet. Det er af denne grund, at "Informationsteori" burde have heddet "Kommunikationsteori." Det er dog for sent at ændre definitionerne (som gav teorien dens oprindelige popularitet, og som stadig får folk til at tro, at denne teori omhandler "information"), så vi må leve med dem, men samtidig skal du klart forstå, hvor langt Shannons definition af information er fra dens almindeligt anvendte betydning. Shannons information omhandler noget helt andet, nemlig usikkerhed.
Her er noget at tænke over, når du foreslår en terminologi. Hvordan stemmer en foreslået definition, såsom Shannons definition af information, overens med din oprindelige idé, og hvor forskellig er den? Der er næsten ingen term, der nøjagtigt afspejler din tidligere vision af et begreb, men i sidste ende er det den anvendte terminologi, der afspejler betydningen af begrebet, så formalisering af noget gennem klare definitioner introducerer altid noget støj.
Overvej et system, hvis alfabet består af symboler q med sandsynligheder pi. I dette tilfælde gennemsnitlige mængde information i systemet (dets forventede værdi) er lig med:
Dette kaldes entropien af systemet med sandsynlighedsfordeling {pi}. Vi bruger udtrykket "entropi", fordi den samme matematiske form optræder i termodynamik og statistisk mekanik. Det er derfor, udtrykket "entropi" skaber en vis aura af betydning omkring sig selv, som i sidste ende ikke er berettiget. Den samme matematiske form for notation indebærer ikke den samme fortolkning af symboler!
Entropien af sandsynlighedsfordelingen spiller en stor rolle i kodningsteorien. Gibbs-uligheden for to forskellige sandsynlighedsfordelinger pi og qi er en af de vigtige konsekvenser af denne teori. Så det skal vi bevise
Beviset er baseret på en åbenlys graf, fig. 13.I, som viser det
og lighed opnås kun, når x = 1. Lad os anvende uligheden på hvert led af summen fra venstre side:
Hvis alfabetet i et kommunikationssystem består af q-symboler, tager vi sandsynligheden for transmission af hvert symbol qi = 1/q og erstatter q, får vi fra Gibbs-uligheden
Figur 13.I
Det betyder, at hvis sandsynligheden for at sende alle q-symboler er den samme og lig med - 1 / q, så er den maksimale entropi lig med ln q, ellers holder uligheden.
I tilfælde af en unikt afkodbar kode har vi Krafts ulighed
Hvis vi nu definerer pseudo-sandsynligheder
hvor selvfølgelig = 1, som følger af Gibbs' ulighed,
og anvende lidt algebra (husk at K ≤ 1, så vi kan droppe det logaritmiske led, og måske forstærke uligheden senere), får vi
hvor L er den gennemsnitlige kodelængde.
Entropi er således minimumsgrænsen for enhver tegn-for-symbol kode med en gennemsnitlig kodeordslængde L. Dette er Shannons sætning for en interferensfri kanal.
Overvej nu hovedsætningen om begrænsningerne af kommunikationssystemer, hvor information transmitteres som en strøm af uafhængige bits og støj er til stede. Det er underforstået, at sandsynligheden for korrekt transmission af en bit er P > 1/2, og sandsynligheden for, at bitværdien vil blive inverteret under transmission (en fejl vil opstå) er lig med Q = 1 - P. For nemheds skyld har vi antag, at fejlene er uafhængige, og sandsynligheden for en fejl er den samme for hver sendt bit - det vil sige, at der er "hvid støj" i kommunikationskanalen.
Den måde, hvorpå vi har en lang strøm af n bit kodet ind i én besked, er den n-dimensionelle forlængelse af en-bit koden. Vi bestemmer værdien af n senere. Betragt en besked bestående af n-bits som et punkt i n-dimensionelt rum. Da vi har et n-dimensionelt rum - og for overskuelighedens skyld vil vi antage, at hver meddelelse har samme sandsynlighed for at opstå - er der M mulige meddelelser (M vil også blive defineret senere), derfor er sandsynligheden for en meddelelse sendt
(afsender)
Skema 13.II
Overvej derefter ideen om kanalkapacitet. Uden at gå i detaljer defineres kanalkapacitet som den maksimale mængde information, der pålideligt kan transmitteres over en kommunikationskanal, under hensyntagen til brugen af den mest effektive kodning. Der er intet argument for, at mere information kan transmitteres gennem en kommunikationskanal end dens kapacitet. Dette kan bevises for en binær symmetrisk kanal (som vi bruger i vores tilfælde). Kanalkapaciteten, når der sendes bit, er angivet som
hvor P som før er sandsynligheden for ingen fejl i nogen sendt bit. Når der sendes n uafhængige bit, er kanalkapaciteten givet af
Hvis vi er tæt på kanalkapaciteten, så skal vi sende næsten denne mængde information for hvert af symbolerne ai, i = 1, ..., M. I betragtning af at sandsynligheden for forekomst af hvert symbol ai er 1 / M, vi får
når vi sender nogen af M lige sandsynlige beskeder ai, har vi
Når der sendes n bit, forventer vi, at der opstår nQ fejl. I praksis vil vi for en besked bestående af n-bit have cirka nQ fejl i den modtagne besked. For stor n, relativ variation (variation = distributionsbredde, )
fordelingen af antallet af fejl vil blive stadig mere snæver, efterhånden som n stiger.
Så fra sendersiden tager jeg beskeden ai for at sende og tegner en kugle rundt om den med en radius
som er lidt større med et beløb svarende til e2 end det forventede antal fejl Q, (Figur 13.II). Hvis n er stor nok, så er der en vilkårligt lille sandsynlighed for, at et meddelelsespunkt bj optræder på modtagersiden, som strækker sig ud over denne sfære. Lad os skitsere situationen, som jeg ser den fra senderens synspunkt: vi har enhver radius fra den transmitterede meddelelse ai til den modtagne meddelelse bj med en fejlsandsynlighed lig (eller næsten lig) med normalfordelingen, når et maksimum af nQ. For enhver given e2 er der en n så stor, at sandsynligheden for, at det resulterende punkt bj er uden for min sfære, er så lille, som du vil.
Lad os nu se på den samme situation fra din side (fig. 13.III). På modtagersiden er der en kugle S(r) med samme radius r omkring det modtagne punkt bj i n-dimensionelt rum, sådan at hvis den modtagne besked bj er inde i min kugle, så er beskeden ai sendt af mig inde i din kugle.
Hvordan kan der opstå en fejl? Fejlen kan opstå i de tilfælde, der er beskrevet i nedenstående tabel:
Figur 13.III
Her ser vi, at hvis der i sfæren bygget op omkring det modtagne punkt er mindst et punkt mere svarende til en mulig sendt ukodet besked, så er der opstået en fejl under transmissionen, da man ikke kan afgøre, hvilken af disse beskeder der blev transmitteret. Den sendte besked er kun fejlfri, hvis punktet, der svarer til den, er i kuglen, og der ikke er andre mulige punkter i den givne kode, der er i samme kugle.
Vi har en matematisk ligning for sandsynligheden for fejl Pe, hvis meddelelsen ai blev sendt
Vi kan smide den første faktor ud i anden term og tage den som 1. Dermed får vi uligheden
Det er klart, at
følgelig
genansøge til den sidste periode til højre
Tager n stort nok, kan det første led tages så lille som ønsket, f.eks. mindre end et tal d. Derfor har vi
Lad os nu se på, hvordan vi kan konstruere en simpel substitutionskode til at kode M beskeder bestående af n bit. Uden at have nogen idé om, hvordan man præcist konstruerer en kode (fejlkorrigerende koder var endnu ikke opfundet), valgte Shannon tilfældig kodning. Vend en mønt for hver af de n bits i beskeden, og gentag processen for M beskeder. I alt skal der laves nM coin flips, så det er muligt
kodeordbøger med samme sandsynlighed ½nM. Den tilfældige proces med at oprette en kodebog betyder naturligvis, at der er mulighed for dubletter, samt kodepunkter, der vil være tæt på hinanden og derfor være en kilde til sandsynlige fejl. Man skal bevise, at hvis dette ikke sker med en sandsynlighed større end et hvilket som helst lille valgt fejlniveau, så er det givne n stort nok.
Det afgørende er, at Shannon tog gennemsnittet af alle mulige kodebøger for at finde den gennemsnitlige fejl! Vi vil bruge symbolet Av[.] til at angive gennemsnitsværdien over sættet af alle mulige tilfældige kodebøger. Midlering over en konstant d giver selvfølgelig en konstant, da gennemsnittet af hvert led er det samme som hvert andet led i summen,
som kan øges (M–1 går til M)
For en given meddelelse, når der tages et gennemsnit på tværs af alle kodebøger, løber kodningen gennem alle mulige værdier, så den gennemsnitlige sandsynlighed for, at et punkt er i en kugle er forholdet mellem kuglens volumen og det samlede rumvolumen. Kuglens rumfang er
hvor s=Q+e2 <1/2 og ns skal være et heltal.
Det sidste led til højre er det største i denne sum. Lad os først estimere dens værdi ved hjælp af Stirling-formlen for factorials. Vi vil så se på den aftagende koefficient af udtrykket foran det, bemærk at denne koefficient stiger, når vi bevæger os til venstre, og så kan vi: (1) begrænse værdien af summen til summen af den geometriske progression med denne begyndelseskoefficient, (2) udvide den geometriske progression fra ns led til et uendelig antal led, (3) beregne summen af en uendelig geometrisk progression (standardalgebra, intet signifikant) og endelig opnå grænseværdien (for en tilstrækkelig stor n):
Læg mærke til, hvordan entropien H(s) optrådte i den binomiale identitet. Bemærk, at Taylor-seriens ekspansion H(s)=H(Q+e2) giver et estimat, der kun tager hensyn til den første afledede og ignorerer alle andre. Lad os nu sammensætte det endelige udtryk:
где
Alt vi skal gøre er at vælge e2 sådan, at e3 < e1, og så vil det sidste led være vilkårligt lille, så længe n er stor nok. Som følge heraf kan den gennemsnitlige PE-fejl opnås så lille som ønsket med kanalkapaciteten vilkårligt tæt på C.
Hvis gennemsnittet af alle koder har en lille nok fejl, så skal mindst én kode være egnet, derfor er der mindst et passende kodesystem. Dette er et vigtigt resultat opnået af Shannon - "Shannons teorem for en støjende kanal", selvom det skal bemærkes, at han beviste dette for et meget mere generelt tilfælde end for den simple binære symmetriske kanal, som jeg brugte. For det generelle tilfælde er de matematiske beregninger meget mere komplicerede, men ideerne er ikke så forskellige, så meget ofte, ved at bruge eksemplet på et bestemt tilfælde, kan du afsløre den sande betydning af teoremet.
Lad os kritisere resultatet. Vi har gentagne gange gentaget: "For tilstrækkeligt stort n." Men hvor stor er n? Meget, meget stort, hvis du virkelig både vil være tæt på kanalkapaciteten og være sikker på den korrekte dataoverførsel! Faktisk så stor, at du bliver nødt til at vente meget længe på at akkumulere en besked med nok bits til at kode den senere. I dette tilfælde vil størrelsen af den tilfældige kodeordbog simpelthen være enorm (en sådan ordbog kan trods alt ikke repræsenteres i en kortere form end en komplet liste over alle Mn bit, på trods af at n og M er meget store)!
Fejlkorrigerende koder undgår at vente på en meget lang besked og derefter kode og afkode den gennem meget store kodebøger, fordi de selv undgår kodebøger og i stedet bruger almindelig beregning. I simpel teori har sådanne koder en tendens til at miste evnen til at nærme sig kanalkapaciteten og stadig opretholde en lav fejlrate, men når koden retter et stort antal fejl, klarer de sig godt. Med andre ord, hvis du allokerer noget kanalkapacitet til fejlkorrektion, så skal du bruge fejlkorrektionskapaciteten det meste af tiden, dvs. et stort antal fejl skal rettes i hver meddelelse, der sendes, ellers spilder du denne kapacitet.
Samtidig er sætningen bevist ovenfor stadig ikke meningsløs! Det viser, at effektive transmissionssystemer skal bruge smarte indkodningsskemaer til meget lange bitstrenge. Et eksempel er satellitter, der er fløjet ud over de ydre planeter; Efterhånden som de bevæger sig væk fra Jorden og Solen, er de tvunget til at rette flere og flere fejl i datablokken: Nogle satellitter bruger solpaneler, som yder omkring 5 W, andre bruger atomkraftkilder, som yder omtrent samme effekt. Strømforsyningens lave effekt, den lille størrelse af senderskåle og den begrænsede størrelse af modtagerskåle på Jorden, den enorme afstand som signalet skal tilbagelægge - alt dette kræver brug af koder med et højt niveau af fejlkorrektion for at bygge en effektivt kommunikationssystem.
Lad os vende tilbage til det n-dimensionelle rum, vi brugte i beviset ovenfor. Ved at diskutere det viste vi, at næsten hele kuglens volumen er koncentreret nær den ydre overflade - således er det næsten sikkert, at det sendte signal vil være placeret nær overfladen af kuglen bygget op omkring det modtagne signal, selv med et relativt lille radius af en sådan kugle. Derfor er det ikke overraskende, at det modtagne signal, efter at have rettet et vilkårligt stort antal fejl, nQ, viser sig at være vilkårligt tæt på et signal uden fejl. Linkkapaciteten, vi diskuterede tidligere, er nøglen til at forstå dette fænomen. Bemærk, at lignende sfærer konstrueret til fejlkorrigerende Hamming-koder ikke overlapper hinanden. Det store antal næsten ortogonale dimensioner i n-dimensionelt rum viser, hvorfor vi kan passe M kugler i rummet med lidt overlap. Hvis vi tillader et lille, vilkårligt lille overlap, som kun kan føre til et lille antal fejl under afkodning, kan vi opnå en tæt placering af kugler i rummet. Hamming garanterede et vist niveau af fejlkorrektion, Shannon - en lav sandsynlighed for fejl, men fastholdt samtidig den faktiske gennemstrømning vilkårligt tæt på kommunikationskanalens kapacitet, hvilket Hamming koder ikke kan.
Informationsteori fortæller os ikke, hvordan vi skal designe et effektivt system, men det viser vejen mod effektive kommunikationssystemer. Det er et værdifuldt værktøj til at bygge maskine-til-maskine kommunikationssystemer, men som tidligere nævnt har det ringe relevans for, hvordan mennesker kommunikerer med hinanden. I hvor høj grad biologisk arv er som tekniske kommunikationssystemer er simpelthen ukendt, så det er i øjeblikket ikke klart, hvordan informationsteori gælder for gener. Vi har intet andet valg end at prøve, og hvis succes viser os den maskinlignende natur af dette fænomen, så vil fiasko pege på andre væsentlige aspekter af informationens natur.
Lad os ikke afvige for meget. Vi har set, at alle originale definitioner i større eller mindre grad skal udtrykke essensen af vores oprindelige overbevisning, men de er karakteriseret ved en vis grad af forvrængning og er derfor ikke anvendelige. Det er traditionelt accepteret, at den definition, vi bruger i sidste ende, faktisk definerer essensen; men dette fortæller os kun, hvordan vi skal behandle tingene og giver os på ingen måde nogen mening. Den postulerende tilgang, der er så stærkt begunstiget i matematiske kredse, lader meget tilbage at ønske i praksis.
Nu vil vi se på et eksempel på IQ-test, hvor definitionen er så cirkulær, som du kan lide den, og som et resultat vildledende. Der laves en test, der skal måle intelligens. Derefter revideres den for at gøre den så konsistent som muligt, og derefter publiceres den og på en enkel metode kalibreres den, så den målte "intelligens" viser sig at være normalfordelt (på en kalibreringskurve, selvfølgelig). Alle definitioner skal kontrolleres igen, ikke kun når de først foreslås, men også meget senere, når de bruges i de dragede konklusioner. I hvilket omfang er definitionsgrænserne passende for det problem, der skal løses? Hvor ofte kommer definitioner givet i én indstilling til at blive anvendt i helt forskellige omgivelser? Dette sker ret ofte! Inden for humaniora, som du uundgåeligt vil støde på i dit liv, sker dette oftere.
Således var et af formålene med denne præsentation af informationsteori, udover at demonstrere dens anvendelighed, at advare dig om denne fare, eller at vise dig præcis, hvordan du bruger den til at opnå det ønskede resultat. Det har længe været bemærket, at indledende definitioner bestemmer, hvad du finder i sidste ende, i langt højere grad end det ser ud til. Indledende definitioner kræver meget opmærksomhed fra dig, ikke kun i enhver ny situation, men også på områder, som du har arbejdet med i lang tid. Dette vil give dig mulighed for at forstå, i hvilket omfang de opnåede resultater er en tautologi og ikke noget nyttigt.
Den berømte historie om Eddington fortæller om folk, der fiskede i havet med et net. Efter at have studeret størrelsen på de fisk, de fangede, bestemte de minimumsstørrelsen af fisk, der findes i havet! Deres konklusion var drevet af det anvendte instrument, ikke af virkeligheden.
Fortsættes ...
Hvem vil hjælpe med oversættelse, layout og udgivelse af bogen - skriv i en personlig besked eller mail [e-mail beskyttet]
Vi har i øvrigt også lanceret oversættelsen af endnu en fed bog - )
Vi søger især dem, der vil hjælpe med at oversætte . (transfer i 10 minutter, er de første 20 allerede taget)
Bogens indhold og oversatte kapitler
- Introduktion til The Art of Doing Science and Engineering: Learning to Learn (28. marts 1995)
- "Fundament of the Digital (Discrete) Revolution" (30. marts 1995)
- "History of Computers - Hardware" (31. marts 1995)
- "History of Computers - Software" (4. april 1995)
- "History of Computers - Applications" (6. april 1995)
- "Kunstig intelligens - del I" (7. april 1995)
- "Kunstig intelligens - del II" (11. april 1995)
- "Kunstig intelligens III" (13. april 1995)
- "n-Dimensional Space" (14. april 1995)
- "Coding Theory - The Representation of Information, Part I" (18. april 1995)
- "Coding Theory - The Representation of Information, Part II" (20. april 1995)
- "Fejlkorrigerende koder" (21. april 1995)
- "Informationsteori" (25. april 1995)
- "Digitale filtre, del I" (27. april 1995)
- "Digitale filtre, del II" (28. april 1995)
- "Digitale filtre, del III" (2. maj 1995)
- "Digitale filtre, 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). Oversættelse:
- "Eksperter" (25. maj 1995)
- "Upålidelige data" (26. maj 1995)
- "Systems Engineering" (30. maj 1995)
- "Du får hvad du måler" (1. juni 1995)
- (Juni 2, 1995) oversætte i 10 minutters bidder
- Hamming, "Du og din forskning" (6. juni 1995).
Hvem vil hjælpe med oversættelse, layout og udgivelse af bogen - skriv i en personlig besked eller mail [e-mail beskyttet]
Kilde: www.habr.com