Vi gjorde det!
"Hensikten med dette kurset er å forberede deg på din tekniske fremtid."
Hei, Habr. Husk den fantastiske artikkelen (+219, 2588 bokmerker, 429 XNUMX leste)?
Så Hamming (ja, ja, selvovervåking og selvkorrigerende ) det er en helhet , skrevet basert på hans forelesninger. Vi oversetter det, fordi mannen sier sin mening.
Dette er en bok ikke bare om IT, det er en bok om tankestilen til utrolig kule mennesker. «Det er ikke bare et løft av positiv tenkning; den beskriver forholdene som øker sjansene for å gjøre godt arbeid.»
Takk til Andrey Pakhomov for oversettelsen.
Informasjonsteori ble utviklet av C. E. Shannon på slutten av 1940-tallet. Bell Labs-ledelsen insisterte på at han kalte det "kommunikasjonsteori" fordi... dette er et mye mer nøyaktig navn. Av åpenbare grunner har navnet «Information Theory» en mye større innvirkning på publikum, og det er derfor Shannon valgte det, og det er navnet vi kjenner til i dag. Selve navnet antyder at teorien omhandler informasjon, noe som gjør den viktig når vi beveger oss dypere inn i informasjonsalderen. I dette kapittelet vil jeg berøre flere hovedkonklusjoner fra denne teorien, jeg vil gi ikke strenge, men snarere intuitive bevis på noen individuelle bestemmelser i denne teorien, slik at du forstår hva "Informasjonsteori" faktisk er, hvor du kan bruke den og hvor ikke.
Først av alt, hva er "informasjon"? Shannon sidestiller informasjon med usikkerhet. Han valgte den negative logaritmen for sannsynligheten for en hendelse som et kvantitativt mål på informasjonen du mottar når en hendelse med sannsynlighet p inntreffer. For eksempel, hvis jeg forteller deg at været i Los Angeles er tåkete, så er p nær 1, noe som egentlig ikke gir oss mye informasjon. Men hvis jeg sier at det regner i Monterey i juni, vil det være usikkerhet i meldingen og den vil inneholde mer informasjon. En pålitelig hendelse inneholder ingen informasjon, siden log 1 = 0.
La oss se på dette mer detaljert. Shannon mente at det kvantitative målet for informasjon burde være en kontinuerlig funksjon av sannsynligheten for en hendelse p, og for uavhengige hendelser burde det være additivt - mengden informasjon som oppnås som et resultat av forekomsten av to uavhengige hendelser bør være lik mengden informasjon innhentet som et resultat av at en felles hendelse inntraff. For eksempel blir resultatet av et terningkast og et myntkast vanligvis behandlet som uavhengige hendelser. La oss oversette det ovennevnte til matematikkspråket. Hvis I (p) er mengden informasjon som finnes i en hendelse med sannsynlighet p, får vi for en felles hendelse bestående av to uavhengige hendelser x med sannsynlighet p1 og y med sannsynlighet p2
(x og y er uavhengige hendelser)
Dette er den funksjonelle Cauchy-ligningen, sann for alle p1 og p2. For å løse denne funksjonelle ligningen, anta at
p1 = p2 = p,
dette gir
Hvis p1 = p2 og p2 = p da
etc. Ved å utvide denne prosessen ved å bruke standardmetoden for eksponentialer, for alle rasjonelle tall m/n er følgende sant
Fra den antatte kontinuiteten til informasjonsmålet, følger det at den logaritmiske funksjonen er den eneste kontinuerlige løsningen på den funksjonelle Cauchy-ligningen.
I informasjonsteori er det vanlig å ta logaritmegrunnlaget til å være 2, så et binært valg inneholder nøyaktig 1 bit informasjon. Derfor måles informasjon med formelen
La oss ta en pause og forstå hva som skjedde ovenfor. For det første definerte vi ikke konseptet "informasjon", vi definerte ganske enkelt formelen for dets kvantitative mål.
For det andre er dette tiltaket underlagt usikkerhet, og selv om det er rimelig egnet for maskiner – for eksempel telefonsystemer, radio, fjernsyn, datamaskiner osv. – gjenspeiler det ikke normale menneskelige holdninger til informasjon.
For det tredje er dette et relativt mål, det avhenger av den nåværende kunnskapen din. Hvis du ser på en strøm av "tilfeldige tall" fra en tilfeldig tallgenerator, antar du at hvert neste tall er usikkert, men hvis du kjenner formelen for å beregne "tilfeldige tall", vil neste tall være kjent, og vil derfor ikke inneholde informasjon.
Så Shannons definisjon av informasjon er passende for maskiner i mange tilfeller, men ser ikke ut til å passe den menneskelige forståelsen av ordet. Det er av denne grunn at "Informasjonsteori" burde ha blitt kalt "kommunikasjonsteori." Det er imidlertid for sent å endre definisjonene (som ga teorien dens opprinnelige popularitet, og som fortsatt får folk til å tro at denne teorien omhandler "informasjon"), så vi må leve med dem, men samtidig må du forstå tydelig hvor langt Shannons definisjon av informasjon er fra dens ofte brukte betydning. Shannons informasjon omhandler noe helt annet, nemlig usikkerhet.
Her er noe å tenke på når du foreslår terminologi. Hvordan stemmer en foreslått definisjon, som Shannons definisjon av informasjon, med din opprinnelige idé, og hvor forskjellig er den? Det er nesten ikke noe begrep som nøyaktig gjenspeiler din tidligere visjon av et konsept, men til syvende og sist er det terminologien som reflekterer betydningen av konseptet, så formalisering av noe gjennom klare definisjoner introduserer alltid noe støy.
Tenk på et system hvis alfabet består av symboler q med sannsynligheter pi. I dette tilfellet gjennomsnittlig informasjonsmengde i systemet (dets forventede verdi) er lik:
Dette kalles entropien til systemet med sannsynlighetsfordeling {pi}. Vi bruker begrepet "entropi" fordi den samme matematiske formen dukker opp i termodynamikk og statistisk mekanikk. Dette er grunnen til at begrepet "entropi" skaper en viss aura av betydning rundt seg selv, som til syvende og sist ikke er berettiget. Den samme matematiske formen for notasjon innebærer ikke den samme tolkningen av symboler!
Entropien til sannsynlighetsfordelingen spiller en stor rolle i kodingsteorien. Gibbs-ulikheten for to forskjellige sannsynlighetsfordelinger pi og qi er en av de viktige konsekvensene av denne teorien. Så det må vi bevise
Beviset er basert på en åpenbar graf, fig. 13.I, som viser det
og likhet oppnås bare når x = 1. La oss bruke ulikheten på hvert ledd av summen fra venstre side:
Hvis alfabetet til et kommunikasjonssystem består av q-symboler, tar vi sannsynligheten for overføring av hvert symbol qi = 1/q og erstatter q, får vi fra Gibbs-ulikheten
Figur 13.I
Dette betyr at hvis sannsynligheten for å sende alle q-symboler er den samme og lik - 1 / q, så er den maksimale entropien lik ln q, ellers gjelder ulikheten.
Når det gjelder en unik dekodbar kode, har vi Krafts ulikhet
Nå hvis vi definerer pseudo-sannsynligheter
hvor selvfølgelig = 1, som følger av Gibbs ulikhet,
og bruk litt algebra (husk at K ≤ 1, så vi kan droppe det logaritmiske leddet, og kanskje styrke ulikheten senere), får vi
hvor L er den gjennomsnittlige kodelengden.
Dermed er entropi minimumsgrensen for enhver tegn-for-symbol-kode med en gjennomsnittlig kodeordlengde L. Dette er Shannons teorem for en interferensfri kanal.
Vurder nå hovedteoremet om begrensningene til kommunikasjonssystemer der informasjon overføres som en strøm av uavhengige biter og støy er tilstede. Det er forstått at sannsynligheten for riktig overføring av en bit er P > 1/2, og sannsynligheten for at bitverdien vil bli invertert under overføring (en feil vil oppstå) er lik Q = 1 - P. For enkelhets skyld har vi anta at feilene er uavhengige og sannsynligheten for en feil er den samme for hver sendte bit - det vil si at det er "hvit støy" i kommunikasjonskanalen.
Måten vi har en lang strøm av n bits kodet inn i én melding er den n-dimensjonale utvidelsen av en-bits koden. Vi vil bestemme verdien av n senere. Betrakt en melding som består av n-biter som et punkt i n-dimensjonalt rom. Siden vi har et n-dimensjonalt rom - og for enkelhets skyld vil vi anta at hver melding har samme sannsynlighet for å inntreffe - er det M mulige meldinger (M vil også bli definert senere), derfor er sannsynligheten for en melding sendt
(avsender)
Tidsplan 13.II
Vurder deretter ideen om kanalkapasitet. Uten å gå i detaljer, er kanalkapasitet definert som den maksimale informasjonsmengden som kan overføres pålitelig over en kommunikasjonskanal, tatt i betraktning bruken av den mest effektive kodingen. Det er ingen argumentasjon for at mer informasjon kan overføres gjennom en kommunikasjonskanal enn dens kapasitet. Dette kan bevises for en binær symmetrisk kanal (som vi bruker i vårt tilfelle). Kanalkapasiteten, når du sender biter, er spesifisert som
hvor, som før, P er sannsynligheten for ingen feil i noen sendt bit. Ved sending av n uavhengige biter er kanalkapasiteten gitt av
Hvis vi er nær kanalkapasiteten, må vi sende nesten denne mengden informasjon for hvert av symbolene ai, i = 1, ..., M. Med tanke på at sannsynligheten for forekomst av hvert symbol ai er 1 / M, vi får
når vi sender noen av M like sannsynlige meldinger ai, har vi
Når n biter sendes, forventer vi at nQ-feil oppstår. I praksis vil vi for en melding som består av n-bits ha omtrent nQ feil i den mottatte meldingen. For stor n, relativ variasjon (variasjon = distribusjonsbredde, )
fordelingen av antall feil vil bli stadig smalere ettersom n øker.
Så fra sendersiden tar jeg meldingen ai for å sende og tegner en kule rundt den med en radius
som er litt større med et beløp lik e2 enn forventet antall feil Q, (Figur 13.II). Hvis n er stor nok, så er det en vilkårlig liten sannsynlighet for at et meldingspunkt bj dukker opp på mottakersiden som strekker seg utover denne sfæren. La oss skissere situasjonen slik jeg ser den fra senderens synspunkt: vi har noen radier fra den overførte meldingen ai til den mottatte meldingen bj med en feilsannsynlighet lik (eller nesten lik) normalfordelingen, og når et maksimum av nQ. For en gitt e2 er det en n så stor at sannsynligheten for at det resulterende punktet bj er utenfor min sfære er så liten som du vil.
La oss nå se på den samme situasjonen fra din side (fig. 13.III). På mottakersiden er det en sfære S(r) med samme radius r rundt det mottatte punktet bj i n-dimensjonalt rom, slik at hvis den mottatte meldingen bj er innenfor min sfære, så er meldingen ai sendt av meg inne i din sfære.
Hvordan kan en feil oppstå? Feilen kan oppstå i tilfellene beskrevet i tabellen nedenfor:
Figur 13.III
Her ser vi at hvis det i sfæren bygget rundt det mottatte punktet er minst ett punkt til som tilsvarer en mulig sendt ukodet melding, så oppsto det en feil under overføringen, siden du ikke kan bestemme hvilken av disse meldingene som ble overført. Den sendte meldingen er feilfri bare hvis punktet som tilsvarer den er i sfæren, og det ikke er andre mulige punkter i den gitte koden som er i samme sfære.
Vi har en matematisk ligning for sannsynligheten for feil Pe hvis melding ai ble sendt
Vi kan kaste ut den første faktoren i andre termin, ta den som 1. Dermed får vi ulikheten
Selvfølgelig, det
derfor
søke på nytt til siste termin til høyre
Tar n stort nok, kan det første leddet tas så lite som ønsket, si mindre enn et tall d. Derfor har vi
La oss nå se på hvordan vi kan konstruere en enkel substitusjonskode for å kode M meldinger som består av n biter. Siden han ikke hadde noen anelse om nøyaktig hvordan man konstruerer en kode (feilkorrigerende koder var ennå ikke oppfunnet), valgte Shannon tilfeldig koding. Vend en mynt for hver av de n bitene i meldingen og gjenta prosessen for M meldinger. Totalt må det lages nM myntflip, så det er mulig
kodeordbøker med samme sannsynlighet ½nM. Selvfølgelig betyr den tilfeldige prosessen med å lage en kodebok at det er mulighet for duplikater, samt kodepunkter som vil være nær hverandre og derfor være en kilde til sannsynlige feil. Man må bevise at dersom dette ikke skjer med en sannsynlighet større enn et hvilket som helst lite valgt feilnivå, så er den gitte n stor nok.
Det avgjørende poenget er at Shannon gjennomsnitt alle mulige kodebøker for å finne gjennomsnittsfeilen! Vi vil bruke symbolet Av[.] for å angi gjennomsnittsverdien over settet av alle mulige tilfeldige kodebøker. Gjennomsnitt over en konstant d gir selvfølgelig en konstant, siden for gjennomsnittsberegning er hvert ledd det samme som alle andre ledd i summen,
som kan økes (M–1 går til M)
For en gitt melding, når gjennomsnittsberegning på tvers av alle kodebøker, går kodingen gjennom alle mulige verdier, så den gjennomsnittlige sannsynligheten for at et punkt er i en sfære er forholdet mellom volumet av sfæren og det totale volumet av plass. Volumet av kulen er
der s=Q+e2 <1/2 og ns må være et heltall.
Den siste terminen til høyre er størst i denne summen. La oss først anslå verdien ved å bruke Stirling-formelen for faktorialer. Vi vil da se på den avtagende koeffisienten til begrepet foran det, merk at denne koeffisienten øker når vi beveger oss til venstre, og så kan vi: (1) begrense verdien av summen til summen av den geometriske progresjonen med denne innledende koeffisienten, (2) utvide den geometriske progresjonen fra ns ledd til et uendelig antall ledd, (3) beregne summen av en uendelig geometrisk progresjon (standard algebra, ikke noe signifikant) og til slutt oppnå grenseverdien (for en tilstrekkelig stor n):
Legg merke til hvordan entropien H(s) dukket opp i den binomiale identiteten. Legg merke til at Taylor-seriens ekspansjon H(s)=H(Q+e2) gir et estimat oppnådd med bare den første deriverte og ignorerer alle andre. La oss nå sette sammen det endelige uttrykket:
der
Alt vi trenger å gjøre er å velge e2 slik at e3 < e1, og da blir siste ledd vilkårlig liten, så lenge n er stor nok. Følgelig kan den gjennomsnittlige PE-feilen oppnås så liten som ønsket med kanalkapasiteten vilkårlig nær C.
Hvis gjennomsnittet av alle koder har en liten nok feil, må minst én kode være passende, derfor er det minst ett passende kodesystem. Dette er et viktig resultat oppnådd av Shannon - "Shannons teorem for en støyende kanal", selv om det skal bemerkes at han beviste dette for et mye mer generelt tilfelle enn for den enkle binære symmetriske kanalen som jeg brukte. For det generelle tilfellet er de matematiske beregningene mye mer kompliserte, men ideene er ikke så forskjellige, så veldig ofte, ved å bruke eksemplet på et bestemt tilfelle, kan du avsløre den sanne betydningen av teoremet.
La oss kritisere resultatet. Vi har gjentatte ganger gjentatt: "For tilstrekkelig stor n." Men hvor stor er n? Veldig, veldig stort hvis du virkelig vil være både nær kanalkapasiteten og være sikker på riktig dataoverføring! Faktisk så stor at du må vente veldig lenge for å samle en melding med nok biter til å kode den senere. I dette tilfellet vil størrelsen på den tilfeldige kodeordboken ganske enkelt være enorm (tross alt kan en slik ordbok ikke representeres i en kortere form enn en fullstendig liste over alle Mn-biter, til tross for at n og M er veldig store)!
Feilkorrigerende koder unngår å vente på en veldig lang melding og deretter kode og dekode den gjennom veldig store kodebøker fordi de unngår kodebøker selv og bruker vanlig beregning i stedet. I enkel teori har slike koder en tendens til å miste evnen til å nærme seg kanalkapasiteten og fortsatt opprettholde en lav feilrate, men når koden korrigerer et stort antall feil, presterer de bra. Med andre ord, hvis du allokerer noe kanalkapasitet til feilretting, så må du bruke feilrettingsevnen mesteparten av tiden, dvs. et stort antall feil må korrigeres i hver melding som sendes, ellers kaster du bort denne kapasiteten.
Samtidig er teoremet bevist ovenfor fortsatt ikke meningsløst! Det viser at effektive overføringssystemer må bruke smarte kodingsskjemaer for svært lange bitstrenger. Et eksempel er satellitter som har fløyet utover de ytre planetene; Etter hvert som de beveger seg bort fra Jorden og Solen, blir de tvunget til å rette opp flere og flere feil i datablokken: Noen satellitter bruker solcellepaneler, som gir omtrent 5 W, andre bruker atomkraftkilder, som gir omtrent samme kraft. Den lave effekten til strømforsyningen, den lille størrelsen på senderskålene og den begrensede størrelsen på mottakerretter på jorden, den enorme avstanden som signalet må reise - alt dette krever bruk av koder med et høyt nivå av feilretting for å bygge en effektivt kommunikasjonssystem.
La oss gå tilbake til det n-dimensjonale rommet vi brukte i beviset ovenfor. Når vi diskuterte det, viste vi at nesten hele volumet av kulen er konsentrert nær den ytre overflaten - dermed er det nesten sikkert at det sendte signalet vil være lokalisert nær overflaten av kulen bygget rundt det mottatte signalet, selv med en relativt liten radius av en slik kule. Derfor er det ikke overraskende at det mottatte signalet, etter å ha korrigert et vilkårlig stort antall feil, nQ, viser seg å være vilkårlig nær et signal uten feil. Koblingskapasiteten vi diskuterte tidligere er nøkkelen til å forstå dette fenomenet. Merk at lignende sfærer konstruert for feilkorrigerende Hamming-koder ikke overlapper hverandre. Det store antallet nesten ortogonale dimensjoner i n-dimensjonalt rom viser hvorfor vi kan passe M kuler i rommet med liten overlapping. Hvis vi tillater en liten, vilkårlig liten overlapping, som kan føre til bare et lite antall feil under dekoding, kan vi oppnå en tett plassering av kuler i rommet. Hamming garanterte et visst nivå av feilretting, Shannon - lav sannsynlighet for feil, men samtidig opprettholde den faktiske gjennomstrømningen vilkårlig nær kapasiteten til kommunikasjonskanalen, noe Hamming-koder ikke kan gjøre.
Informasjonsteori forteller oss ikke hvordan vi skal designe et effektivt system, men det viser vei mot effektive kommunikasjonssystemer. Det er et verdifullt verktøy for å bygge maskin-til-maskin kommunikasjonssystemer, men som nevnt tidligere har det liten relevans for hvordan mennesker kommuniserer med hverandre. I hvilken grad biologisk arv er som tekniske kommunikasjonssystemer er rett og slett ukjent, så det er foreløpig ikke klart hvordan informasjonsteori gjelder gener. Vi har ikke noe annet valg enn å prøve, og hvis suksessen viser oss den maskinlignende naturen til dette fenomenet, vil feilen peke på andre viktige aspekter ved informasjonens natur.
La oss ikke gå for mye bort. Vi har sett at alle originale definisjoner, i større eller mindre grad, må uttrykke essensen av vår opprinnelige tro, men de er preget av en viss grad av forvrengning og er derfor ikke anvendelige. Det er tradisjonelt akseptert at til syvende og sist, definisjonen vi bruker faktisk definerer essensen; men dette forteller oss bare hvordan vi skal behandle ting og gir oss på ingen måte noen mening. Den postulasjonsmessige tilnærmingen, som er så sterkt favorisert i matematiske kretser, etterlater mye å være ønsket i praksis.
Nå skal vi se på et eksempel på IQ-tester der definisjonen er så sirkulær som du vil ha den og som et resultat villedende. Det lages en test som skal måle intelligens. Deretter revideres den for å gjøre den så konsistent som mulig, og deretter publiseres den og på en enkel måte kalibreres slik at den målte "intelligensen" viser seg å være normalfordelt (på en kalibreringskurve, selvfølgelig). Alle definisjoner må kontrolleres på nytt, ikke bare når de først foreslås, men også mye senere når de brukes i konklusjonene som trekkes. I hvilken grad er definisjonsgrensene hensiktsmessige for problemet som løses? Hvor ofte blir definisjoner gitt i en setting brukt i ganske forskjellige settinger? Dette skjer ganske ofte! I humaniora, som du uunngåelig vil møte i livet ditt, skjer dette oftere.
Derfor var en av hensiktene med denne presentasjonen av informasjonsteori, i tillegg til å demonstrere dens nytte, å advare deg om denne faren, eller å vise deg nøyaktig hvordan du bruker den for å oppnå ønsket resultat. Det har lenge vært bemerket at innledende definisjoner bestemmer hva du finner til slutt, i mye større grad enn det ser ut til. Innledende definisjoner krever mye oppmerksomhet fra deg, ikke bare i enhver ny situasjon, men også på områder du har jobbet med lenge. Dette vil tillate deg å forstå i hvilken grad de oppnådde resultatene er en tautologi og ikke noe nyttig.
Den berømte historien om Eddington forteller om folk som fisket i havet med garn. Etter å ha studert størrelsen på fisken de fanget, bestemte de minimumsstørrelsen på fisken som finnes i havet! Konklusjonen deres var drevet av instrumentet som ble brukt, ikke av virkeligheten.
To be continued ...
Hvem ønsker å hjelpe til med oversettelse, layout og utgivelse av boken – skriv i en personlig melding eller e-post [e-postbeskyttet]
Vi har forresten også lansert oversettelsen av nok en kul bok - )
Vi er spesielt ute etter de som kan hjelpe til med å oversette . (overføring i 10 minutter, de første 20 er allerede tatt)
Innhold i boken og oversatte kapitler
- Introduksjon til 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)
- "Kunstig intelligens - del I" (7. april 1995)
- "Kunstig intelligens - del II" (11. april 1995)
- "Kunstig intelligens III" (13. april 1995)
- "n-dimensjonalt rom" (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)
- "Feilkorrigerende koder" (21. april 1995)
- "Information Theory" (25. april 1995)
- "Digitale filtre, del I" (27. april 1995)
- "Digitale filtre, del II" (28. april 1995)
- "Digitale filtre, del III" (2. mai 1995)
- "Digitale filtre, del IV" (4. mai 1995)
- "Simulering, del I" (5. mai 1995)
- "Simulering, del II" (9. mai 1995)
- "Simulering, del III" (11. mai 1995)
- "Fiber Optics" (12. mai 1995)
- "Computer Aided Instruction" (16. mai 1995)
- "Matematikk" (18. mai 1995)
- "Quantum Mechanics" (19. mai 1995)
- "Kreativitet" (23. mai 1995). Oversettelse:
- "Eksperter" (25. mai 1995)
- "Upålitelige data" (26. mai 1995)
- "Systems Engineering" (30. mai 1995)
- "Du får det du måler" (1. juni 1995)
- (Juni 2, 1995) oversett i 10-minutters biter
- Hamming, "Du og din forskning" (6. juni 1995).
Hvem ønsker å hjelpe til med oversettelse, layout og utgivelse av boken – skriv i en personlig melding eller e-post [e-postbeskyttet]
Kilde: www.habr.com