Ho hem fet!
"L'objectiu d'aquest curs és preparar-te per al teu futur tècnic".
Hola, Habr. Recordeu l'article fantàstic (+219, 2588 adreces d'interès, 429 k lectures)?
Així Hamming (sí, sí, autocontrol i autocorrecció ) hi ha un tot , escrit a partir de les seves conferències. Ho traduïm, perquè l'home diu el que pensa.
Aquest és un llibre no només sobre TI, és un llibre sobre l'estil de pensament de persones increïblement interessants. “No és només un impuls del pensament positiu; descriu les condicions que augmenten les possibilitats de fer un gran treball".
Gràcies a Andrey Pakhomov per la traducció.
La teoria de la informació va ser desenvolupada per C. E. Shannon a finals de la dècada de 1940. La direcció de Bell Labs va insistir que l'anomenava "Teoria de la comunicació" perquè... aquest és un nom molt més precís. Per raons òbvies, el nom "Teoria de la informació" té un impacte molt més gran en el públic, per això Shannon el va triar, i és el nom que coneixem fins avui. El propi nom suggereix que la teoria tracta de la informació, cosa que la fa important a mesura que ens aprofundim en l'era de la informació. En aquest capítol, tocaré diverses conclusions principals d'aquesta teoria, proporcionaré proves no estrictes, sinó més aviat intuïtives d'algunes disposicions individuals d'aquesta teoria, de manera que entenguis què és realment la "teoria de la informació", on la pots aplicar. i on no.
En primer lloc, què és la "informació"? Shannon equipara la informació amb la incertesa. Va triar el logaritme negatiu de la probabilitat d'un esdeveniment com a mesura quantitativa de la informació que rebeu quan es produeix un esdeveniment amb probabilitat p. Per exemple, si us dic que el temps a Los Angeles és boirós, aleshores p s'aproxima a 1, la qual cosa realment no ens dóna molta informació. Però si dic que a Monterey plou al juny, hi haurà incertesa en el missatge i contindrà més informació. Un esdeveniment fiable no conté cap informació, ja que el registre 1 = 0.
Vegem-ho amb més detall. Shannon creia que la mesura quantitativa de la informació hauria de ser una funció contínua de la probabilitat d'un esdeveniment p, i per als esdeveniments independents hauria de ser additiva: la quantitat d'informació obtinguda com a resultat de l'ocurrència de dos esdeveniments independents hauria de ser igual a la quantitat d'informació obtinguda com a conseqüència de l'ocurrència d'un esdeveniment conjunt. Per exemple, el resultat d'una tirada de daus i una tirada de monedes solen tractar-se com a esdeveniments independents. Traduïm l'anterior al llenguatge de les matemàtiques. Si I (p) és la quantitat d'informació continguda en un esdeveniment amb probabilitat p, llavors per a un esdeveniment conjunt format per dos esdeveniments independents x amb probabilitat p1 i y amb probabilitat p2 obtenim
(x i y són esdeveniments independents)
Aquesta és l'equació funcional de Cauchy, certa per a tots els p1 i p2. Per resoldre aquesta equació funcional, suposa que
p1 = p2 = p,
això dóna
Si p1 = p2 i p2 = p aleshores
etc. Ampliant aquest procés utilitzant el mètode estàndard per a exponencials, per a tots els nombres racionals m/n és cert el següent
De l'assumpte continuïtat de la mesura d'informació, es dedueix que la funció logarítmica és l'única solució contínua de l'equació funcional de Cauchy.
En teoria de la informació, és comú prendre la base del logaritme com a 2, de manera que una opció binària conté exactament 1 bit d'informació. Per tant, la informació es mesura mitjançant la fórmula
Fem una pausa i entenem què va passar a dalt. En primer lloc, no hem definit el concepte d'“informació”, simplement hem definit la fórmula per a la seva mesura quantitativa.
En segon lloc, aquesta mesura està subjecta a incertesa i, tot i que és raonablement adequada per a màquines —per exemple, sistemes telefònics, ràdio, televisió, ordinadors, etc.—, no reflecteix les actituds humanes normals davant la informació.
En tercer lloc, aquesta és una mesura relativa, depèn de l'estat actual dels vostres coneixements. Si mireu un flux de "nombres aleatoris" d'un generador de números aleatoris, suposeu que cada número següent és incert, però si coneixeu la fórmula per calcular "nombres aleatoris", es coneixerà el següent nombre i, per tant, no es coneixerà. contenir informació.
Per tant, la definició d'informació de Shannon és adequada per a les màquines en molts casos, però no sembla encaixar amb la comprensió humana de la paraula. És per aquest motiu que la "teoria de la informació" hauria d'haver-se anomenat "teoria de la comunicació". No obstant això, és massa tard per canviar les definicions (que van donar a la teoria la seva popularitat inicial, i que encara fan pensar que aquesta teoria tracta de la “informació”), així que cal conviure amb elles, però al mateix temps cal entendre clarament fins a quin punt la definició d'informació de Shannon està del seu significat d'ús habitual. La informació de Shannon tracta d'una cosa completament diferent, és a dir, la incertesa.
Aquí hi ha alguna cosa en què pensar quan proposeu qualsevol terminologia. Com concorda una definició proposada, com ara la definició d'informació de Shannon, amb la teva idea original i com de diferent és? Gairebé no hi ha cap terme que reflecteixi exactament la teva visió anterior d'un concepte, però en última instància, és la terminologia utilitzada la que reflecteix el significat del concepte, de manera que formalitzar alguna cosa mitjançant definicions clares sempre introdueix una mica de soroll.
Considereu un sistema l'alfabet del qual consta de símbols q amb probabilitats pi. En aquest cas quantitat mitjana d'informació al sistema (el seu valor esperat) és igual a:
Això s'anomena entropia del sistema amb distribució de probabilitat {pi}. Utilitzem el terme "entropia" perquè la mateixa forma matemàtica apareix en termodinàmica i mecànica estadística. És per això que el terme "entropia" crea una certa aura d'importància al seu voltant, que finalment no es justifica. La mateixa forma matemàtica de notació no implica la mateixa interpretació dels símbols!
L'entropia de la distribució de probabilitat té un paper important en la teoria de codificació. La desigualtat de Gibbs per a dues distribucions de probabilitat diferents pi i qi és una de les conseqüències importants d'aquesta teoria. Així que ho hem de demostrar
La demostració es basa en un gràfic evident, Fig. 13.I, que demostra que
i la igualtat només s'aconsegueix quan x = 1. Apliquem la desigualtat a cada terme de la suma del costat esquerre:
Si l'alfabet d'un sistema de comunicació consta de q símbols, prenent la probabilitat de transmissió de cada símbol qi = 1/q i substituint q, obtenim de la desigualtat de Gibbs
Figura 13.I
Això vol dir que si la probabilitat de transmetre tots els símbols q és igual i igual a - 1 / q, aleshores l'entropia màxima és igual a ln q, en cas contrari la desigualtat es manté.
En el cas d'un codi descodificable únicament, tenim la desigualtat de Kraft
Ara si definim pseudo-probabilitats
on és clar = 1, que es desprèn de la desigualtat de Gibbs,
i apliqueu una mica d'àlgebra (recordeu que K ≤ 1, de manera que podem eliminar el terme logarítmic, i potser reforçar la desigualtat més tard), obtenim
on L és la longitud mitjana del codi.
Així, l'entropia és el límit mínim per a qualsevol codi caràcter per símbol amb una longitud mitjana de paraula de codi L. Aquest és el teorema de Shannon per a un canal lliure d'interferències.
Considereu ara el teorema principal sobre les limitacions dels sistemes de comunicació en què la informació es transmet com un flux de bits independents i hi ha soroll. S'entén que la probabilitat de transmissió correcta d'un bit és P > 1/2, i la probabilitat que el valor del bit s'inverteixi durant la transmissió (es produirà un error) és igual a Q = 1 - P. Per comoditat, Suposem que els errors són independents i que la probabilitat d'un error és la mateixa per a cada bit enviat, és a dir, hi ha "soroll blanc" al canal de comunicació.
La manera com tenim un llarg flux de n bits codificats en un missatge és l'extensió n-dimensional del codi d'un bit. El valor de n el determinarem més endavant. Considereu un missatge format per n bits com un punt de l'espai n-dimensional. Com que tenim un espai n-dimensional -i per senzillesa suposarem que cada missatge té la mateixa probabilitat d'ocurrència- hi ha M missatges possibles (M també es definirà més endavant), per tant, la probabilitat de qualsevol missatge enviat és
(emissor)
Annex 13.II
A continuació, considereu la idea de la capacitat del canal. Sense entrar en detalls, la capacitat del canal es defineix com la quantitat màxima d'informació que es pot transmetre de manera fiable a través d'un canal de comunicació, tenint en compte l'ús de la codificació més eficient. No hi ha cap argument que a través d'un canal de comunicació es pugui transmetre més informació que la seva capacitat. Això es pot demostrar per a un canal simètric binari (que fem servir en el nostre cas). La capacitat del canal, quan s'envia bits, s'especifica com
on, com abans, P és la probabilitat que no hi hagi error en cap bit enviat. Quan s'envia n bits independents, la capacitat del canal ve donada per
Si estem a prop de la capacitat del canal, llavors haurem d'enviar gairebé aquesta quantitat d'informació per a cadascun dels símbols ai, i = 1, ..., M. Tenint en compte que la probabilitat d'ocurrència de cada símbol ai és 1 / M, obtenim
quan enviem qualsevol de M missatges igualment probables ai, tenim
Quan s'envien n bits, esperem que es produeixin nQ errors. A la pràctica, per a un missatge format per n bits, tindrem aproximadament nQ errors en el missatge rebut. Per a n gran, variació relativa (variació = amplada de distribució, )
la distribució del nombre d'errors serà cada cop més estreta a mesura que n augmenta.
Per tant, des del costat del transmissor, agafo el missatge ai per enviar i dibuixo una esfera al seu voltant amb un radi
que és lleugerament més gran en una quantitat igual a e2 que el nombre esperat d'errors Q, (Figura 13.II). Si n és prou gran, llavors hi ha una probabilitat arbitràriament petita que aparegui un punt de missatge bj al costat del receptor que s'estén més enllà d'aquesta esfera. Esbossem la situació tal com la veig jo des del punt de vista de l'emissor: tenim qualsevol radi des del missatge transmès ai fins al missatge rebut bj amb una probabilitat d'error igual (o gairebé igual) a la distribució normal, arribant a un màxim. de nQ. Per a qualsevol e2 donat, hi ha una n tan gran que la probabilitat que el punt resultant bj estigui fora de la meva esfera és tan petita com vulgueu.
Ara mirem la mateixa situació des del vostre costat (Fig. 13.III). Al costat del receptor hi ha una esfera S(r) del mateix radi r al voltant del punt rebut bj a l'espai n-dimensional, de manera que si el missatge rebut bj es troba dins de la meva esfera, aleshores el missatge ai enviat per mi està dins del vostre esfera.
Com es pot produir un error? L'error es pot produir en els casos descrits a la taula següent:
Figura 13.III
Aquí veiem que si a l'esfera construïda al voltant del punt rebut hi ha almenys un punt més corresponent a un possible missatge enviat sense codificar, s'ha produït un error durant la transmissió, ja que no es pot determinar quin d'aquests missatges s'ha transmès. El missatge enviat només està lliure d'errors si el punt que li correspon es troba a l'esfera i no hi ha altres punts possibles en el codi donat que estiguin a la mateixa esfera.
Tenim una equació matemàtica per a la probabilitat d'error Pe si s'ha enviat el missatge ai
Podem descartar el primer factor en el segon terme, prenent-lo com a 1. Així obtenim la desigualtat
És obvi que
per tant
torneu a aplicar a l'últim terme de la dreta
Prenent n prou gran, el primer terme es pot prendre tan petit com es desitgi, per exemple, menys que algun nombre d. Per tant tenim
Vegem ara com podem construir un codi de substitució senzill per codificar missatges M formats per n bits. No tenint ni idea de com construir exactament un codi (encara no s'havien inventat els codis de correcció d'errors), Shannon va triar la codificació aleatòria. Llança una moneda per a cadascun dels n bits del missatge i repeteix el procés per als missatges M. En total, cal fer voltes de monedes nM, de manera que és possible
diccionaris de codi amb la mateixa probabilitat ½ nM. Per descomptat, el procés aleatori de creació d'un llibre de codis significa que hi ha la possibilitat de duplicats, així com punts de codi que estaran a prop els uns dels altres i, per tant, seran una font d'errors probables. S'ha de demostrar que si això no passa amb una probabilitat superior a qualsevol petit nivell d'error escollit, aleshores la n donada és prou gran.
El punt crucial és que Shannon va fer una mitjana de tots els llibres de codis possibles per trobar l'error mitjà! Utilitzarem el símbol Av[.] per indicar el valor mitjà sobre el conjunt de tots els possibles llibres de codis aleatoris. La mitjana sobre una constant d, per descomptat, dóna una constant, ja que per fer la mitjana cada terme és el mateix que tots els altres termes de la suma,
que es pot augmentar (M–1 passa a M)
Per a qualsevol missatge donat, quan es fa la mitjana entre tots els llibres de codis, la codificació passa per tots els valors possibles, de manera que la probabilitat mitjana que un punt estigui en una esfera és la relació entre el volum de l'esfera i el volum total d'espai. El volum de l'esfera és
on s=Q+e2 <1/2 i ns ha de ser un nombre enter.
L'últim terme de la dreta és el més gran d'aquesta suma. Primer, estimem el seu valor utilitzant la fórmula de Stirling per a factorials. A continuació, veurem el coeficient decreixent del terme que hi ha davant, observem que aquest coeficient augmenta a mesura que ens movem cap a l'esquerra, i així podem: (1) restringir el valor de la suma a la suma de la progressió geomètrica amb aquest coeficient inicial, (2) ampliar la progressió geomètrica des de ns termes a un nombre infinit de termes, (3) calcular la suma d'una progressió geomètrica infinita (àlgebra estàndard, res significatiu) i finalment obtenir el valor límit (per a un nombre prou gran). n):
Observeu com va aparèixer l'entropia H(s) a la identitat binomial. Observeu que l'expansió de la sèrie de Taylor H(s)=H(Q+e2) dóna una estimació obtinguda tenint en compte només la primera derivada i ignorant totes les altres. Ara posem l'expressió final:
on
Tot el que hem de fer és triar e2 de manera que e3 < e1, i aleshores l'últim terme serà arbitràriament petit, sempre que n sigui prou gran. En conseqüència, l'error PE mitjà es pot obtenir tan petit com es desitgi amb la capacitat del canal arbitràriament propera a C.
Si la mitjana de tots els codis té un error prou petit, llavors almenys un codi ha de ser adequat, per tant, hi ha almenys un sistema de codificació adequat. Aquest és un resultat important obtingut per Shannon: "Teorema de Shannon per a un canal sorollós", tot i que cal assenyalar que ho va demostrar per a un cas molt més general que per al simple canal binari simètric que vaig utilitzar. Per al cas general, els càlculs matemàtics són molt més complicats, però les idees no són tan diferents, de manera que molt sovint, utilitzant l'exemple d'un cas particular, podeu revelar el veritable significat del teorema.
Critiquem el resultat. Hem repetit repetidament: "Per a n prou gran". Però quina mida és n? Molt, molt gran si realment voleu estar a prop de la capacitat del canal i estar segur de la transferència de dades correcta! Tan gran, de fet, que hauràs d'esperar molt de temps per acumular un missatge de bits suficients per codificar-lo més tard. En aquest cas, la mida del diccionari de codi aleatori serà senzillament enorme (després de tot, aquest diccionari no es pot representar en una forma més curta que una llista completa de tots els bits Mn, malgrat que n i M són molt grans)!
Els codis de correcció d'errors eviten esperar un missatge molt llarg i després codificar-lo i descodificar-lo a través de llibres de codis molt grans perquè eviten els llibres de codis i utilitzen el càlcul normal. En teoria simple, aquests codis tendeixen a perdre la capacitat d'apropar-se a la capacitat del canal i encara mantenen una taxa d'error baixa, però quan el codi corregeix un gran nombre d'errors, funcionen bé. En altres paraules, si assigneu una mica de capacitat del canal a la correcció d'errors, haureu d'utilitzar la capacitat de correcció d'errors la major part del temps, és a dir, s'han de corregir un gran nombre d'errors en cada missatge enviat, en cas contrari, malbareu aquesta capacitat.
Al mateix temps, el teorema demostrat anteriorment encara no té sentit! Mostra que els sistemes de transmissió eficients han d'utilitzar esquemes de codificació intel·ligents per a cadenes de bits molt llargues. Un exemple són els satèl·lits que han volat més enllà dels planetes exteriors; A mesura que s'allunyen de la Terra i del Sol, es veuen obligats a corregir cada cop més errors en el bloc de dades: alguns satèl·lits utilitzen plaques solars, que proporcionen uns 5 W, altres utilitzen fonts d'energia nuclear, que proporcionen aproximadament la mateixa potència. La baixa potència de la font d'alimentació, la petita mida de les antenes transmissores i la mida limitada de les antenes receptores a la Terra, l'enorme distància que ha de recórrer el senyal, tot això requereix l'ús de codis amb un alt nivell de correcció d'errors per construir un sistema de comunicació eficaç.
Tornem a l'espai n-dimensional que hem utilitzat a la demostració anterior. En parlar-ne, vam demostrar que gairebé tot el volum de l'esfera es concentra a prop de la superfície exterior; per tant, és gairebé segur que el senyal enviat estarà situat a prop de la superfície de l'esfera construïda al voltant del senyal rebut, fins i tot amb un petit radi d'aquesta esfera. Per tant, no és d'estranyar que el senyal rebut, després de corregir un nombre arbitràriament gran d'errors, nQ, resulti arbitràriament proper a un senyal sense errors. La capacitat d'enllaç que hem comentat anteriorment és la clau per entendre aquest fenomen. Tingueu en compte que les esferes similars construïdes per a la correcció d'errors dels codis Hamming no es superposen entre si. El gran nombre de dimensions gairebé ortogonals a l'espai n-dimensional mostra per què podem ajustar esferes M a l'espai amb poca superposició. Si permetem una superposició petita, arbitràriament petita, que només pot provocar un petit nombre d'errors durant la descodificació, podem obtenir una col·locació densa d'esferes a l'espai. Hamming va garantir un cert nivell de correcció d'errors, Shannon: una baixa probabilitat d'error, però al mateix temps mantenint el rendiment real arbitràriament a prop de la capacitat del canal de comunicació, cosa que els codis Hamming no poden fer.
La teoria de la informació no ens diu com dissenyar un sistema eficient, però sí que indica el camí cap a sistemes de comunicació eficients. És una eina valuosa per construir sistemes de comunicació màquina a màquina, però, com s'ha assenyalat anteriorment, té poca rellevància en la manera com els humans es comuniquen entre ells. Simplement es desconeix fins a quin punt l'herència biològica és com els sistemes de comunicació tècnics, de manera que actualment no està clar com s'aplica la teoria de la informació als gens. No tenim més remei que intentar-ho, i si l'èxit ens mostra la naturalesa de màquina d'aquest fenomen, aleshores el fracàs indicarà altres aspectes significatius de la naturalesa de la informació.
No ens divaguem massa. Hem vist que totes les definicions originals, en major o menor mesura, han d'expressar l'essència de les nostres creences originals, però es caracteritzen per un cert grau de distorsió i, per tant, no són aplicables. Tradicionalment s'accepta que, en definitiva, la definició que fem servir en defineix realment l'essència; però, això només ens indica com processem les coses i de cap manera ens transmet cap significat. L'enfocament postulacional, tan afavorit en els cercles matemàtics, deixa molt a desitjar a la pràctica.
Ara veurem un exemple de proves de coeficient intel·lectual on la definició és tan circular com vulgueu que sigui i, com a resultat, enganyosa. Es crea una prova que se suposa que mesura la intel·ligència. Després es revisa per fer-la el més coherent possible, i després es publica i, amb un mètode senzill, es calibra perquè la “intel·ligència” mesurada es distribueixi normalment (en una corba de calibratge, és clar). Cal tornar a revisar totes les definicions, no només quan es proposen per primera vegada, sinó també molt més tard, quan s'utilitzen en les conclusions extretes. Fins a quin punt els límits de definició són adequats per al problema que es resol? Amb quina freqüència les definicions donades en un entorn s'apliquen en entorns força diferents? Això passa força sovint! En les humanitats, que inevitablement trobareu a la vostra vida, això passa més sovint.
Així, una de les finalitats d'aquesta presentació de la teoria de la informació, a més de demostrar la seva utilitat, era advertir-vos d'aquest perill, o mostrar-vos exactament com utilitzar-la per obtenir el resultat desitjat. Fa temps que s'observa que les definicions inicials determinen el que es troba al final, en una mesura molt més gran del que sembla. Les definicions inicials requereixen molta atenció per part teva, no només en qualsevol situació nova, sinó també en àmbits amb els quals estàs treballant des de fa molt de temps. Això permetrà entendre fins a quin punt els resultats obtinguts són una tautologia i no una cosa útil.
La famosa història d'Eddington parla de persones que pescaven al mar amb una xarxa. Després d'estudiar la mida dels peixos que capturaven, van determinar la mida mínima de peix que es troba al mar! La seva conclusió va ser impulsada per l'instrument utilitzat, no per la realitat.
Continuar ...
Qui vulgui ajudar amb la traducció, la maquetació i la publicació del llibre: escriu un missatge personal o un correu electrònic [protegit per correu electrònic]
Per cert, també hem llançat la traducció d'un altre llibre genial: )
Estem buscant especialment els que ajudaran a traduir . (transferència durant 10 minuts, ja s'han pres els 20 primers)
Continguts del llibre i capítols traduïts
- Introducció a l'art de fer ciència i enginyeria: aprendre a aprendre (28 de març de 1995)
- "Fons de la revolució digital (discreta)" (30 de març de 1995)
- "History of Computers - Hardware" (31 de març de 1995)
- "History of Computers - Software" (4 d'abril de 1995)
- "History of Computers - Applications" (6 d'abril de 1995)
- "Intel·ligència artificial - Part I" (7 d'abril de 1995)
- "Intel·ligència artificial - Part II" (11 d'abril de 1995)
- "Intel·ligència artificial III" (13 d'abril de 1995)
- "Espai n-dimensional" (14 d'abril de 1995)
- "Teoria de la codificació: la representació de la informació, part I" (18 d'abril de 1995)
- "Teoria de la codificació: la representació de la informació, part II" (20 d'abril de 1995)
- "Codis de correcció d'errors" (21 d'abril de 1995)
- "Teoria de la informació" (25 d'abril de 1995)
- "Filtres digitals, part I" (27 d'abril de 1995)
- "Filtres digitals, part II" (28 d'abril de 1995)
- "Filtres digitals, part III" (2 de maig de 1995)
- "Filtres digitals, part IV" (4 de maig de 1995)
- "Simulació, part I" (5 de maig de 1995)
- "Simulation, Part II" (9 de maig de 1995)
- "Simulació, part III" (11 de maig de 1995)
- "Fibra òptica" (12 de maig de 1995)
- "Instrucció assistida per ordinador" (16 de maig de 1995)
- "Matemàtiques" (18 de maig de 1995)
- "Quantum Mechanics" (19 de maig de 1995)
- "Creativitat" (23 de maig de 1995). Traducció:
- "Experts" (25 de maig de 1995)
- "Dades poc fiables" (26 de maig de 1995)
- "Enginyeria de sistemes" (30 de maig de 1995)
- "Tu aconsegueixes el que mesures" (1 de juny de 1995)
- (Juny 2, 1995) traduir en fragments de 10 minuts
- Hamming, "You and Your Research" (6 de juny de 1995).
Qui vulgui ajudar amb la traducció, la maquetació i la publicació del llibre: escriu un missatge personal o un correu electrònic [protegit per correu electrònic]
Font: www.habr.com