Teoria de codis

La teoria de codis s'ocupa de trobar mètodes, anomenats codis. La seva funció és incrementar l'eficiència i reduir la taxa d'errors en la comunicació de dades^[1] sobre canals sorollosos fins al límit teòric del canal. Aquests codis poden classificar-se en tècniques de compressió de dades i tècniques en correcció d'errors. Un altre tipus de codis són els algorismes criptogràfics.

No tots els sistemes de transmissió satisfan la condició de transmetre el senyal sense distorsió, de manera que la resposta no sempre és una rèplica exacta del senyal d'entrada. Les distorsions poden ser lineals, degut a la característica no ideal, sigui de magnitud, de fase o ambdues, o no lineals.^[2]

Hi ha quatre tipus de codis, compressió de dades, criptografia, codi en línia i detector i corrector d'errors. El funcionament d'aquests codis consisteix en l'enviament, junt amb la informació original, de redundància amb la que es pot deduir el que realment transmès, per exemple enviant dues còpies iguals: si el bit original o alguna de les còpies es rep malament, es pot corregir a partir dels altres dos. Es millora la qualitat de la informació rebuda, però a base de l'augment del cost d'enviament.^[1]

Història

Cronologia^[3]

Any	Esdeveniment
55 aC	Juli Cèsar, en envair Gran Bretanya, utilitza codis per enviar missatges als seus generals.
1750 dC	Leonhard Euler posa les bases de la criptografia de clau pública amb el seu teorema.
1844	Samuel Morse transmet el primer missatge utilitzant el seu codi.
Dècada de 1920	Es desenvolupa la màquina Enigma.
1950	Richard Hamming publica un article fonamental per crear codis que detecten i corregeixen errors.
Dècada de 1970	Desenvolupament de la criptografia de clau pública.

El 1948, Claude Shannon va publicar "A Mathematical Theory of Communication", un article en dues parts als números de juliol i octubre del Bell System Technical Journal, que es centra en el problema de la millor manera de codificar la informació que un emissor vol transmetre. En aquest treball fonamental va utilitzar eines en teoria de la probabilitat, desenvolupades per Norbert Wiener, que estaven en les seves etapes naixents d'aplicar-se a la teoria de la comunicació en aquell moment. Shannon va desenvolupar l'entropia de la informació com a mesura de la incertesa d'un missatge alhora que va inventar essencialment el camp de la teoria de la informació.

El codi binari de Golay es va desenvolupar l'any 1949. És un codi de correcció d'errors capaç de corregir fins a tres errors en cada paraula de 24 bits i detectar-ne una quarta.

Richard Hamming va guanyar el premi Turing el 1968 pel seu treball als laboratoris Bell en mètodes numèrics, sistemes de codificació automàtica i codis de detecció i correcció d'errors. Va inventar els conceptes coneguts com a codis de Hamming, finestres de Hamming, números de Hamming i distància de Hamming.

El 1972, Nasir Ahmed va proposar la transformada discreta del cosinus (DCT), que va desenvolupar amb T. Natarajan i K. R. Rao el 1973. El DCT és l'algorisme de compressió amb pèrdues més utilitzat, la base de formats multimèdia com JPEG, MPEG i MP3.

El problema de la codificació eficient

Un dels principals problemes de la teoria de codis és el següent. Suposem que tenim una font d'informació que emet o transmet "símbols" de cert conjunt ${\displaystyle \scriptstyle W=\{w_{1},\dots ,w_{n}\}}$ que per propòsits pedagògics anomenarem simplement "paraules", de manera que la probabilitat d'emissió d'una paraula sigui independent del símbol anterior ${\displaystyle \scriptstyle P(w^{(t)})=w_{k}|w^{(t-1)}=w_{j}=P(w=w_{k})}$, sent ${\displaystyle \scriptstyle p_{i}=P(w=w_{i})}$. Si ${\displaystyle \scriptstyle \Sigma }$ és un alfabet de D en "lletres", quin codi s'ha d'assignar a la paraula ${\displaystyle \scriptstyle w_{i}}$ usant "lletres" de l'alfabet de tal manera que s'aconsegueixi una codificació tan econòmica com sigui possible?^[4] Formalment una codificació és una aplicació ${\displaystyle \scriptstyle E:W\to {\mathcal {P}}_{0}(\Sigma )}$ del conjunt de "paraules" al conjunt de seqüències finites de "lletres" de l'alfabet. Un missatge és una seqüència finita de paraules, ${\displaystyle \scriptstyle m=w_{i_{1}}\dots w_{i_{n}}}$, si es disposa d'una codificació de paraules, aquesta s'estén immediatament a missatges mitjançant concatenació:

${\displaystyle E(m)=E(w_{i_{1}})\dots E(w_{i_{n}})}$

Alguns tipus de codificacions interessants són:

• Una codificació és unívocament desxifrable si qualsevol seqüència finita de ${\displaystyle \scriptstyle {\mathcal {P}}_{0}(\Sigma )}$ és la imatge de com a molt un missatge, és a dir, quan l'aplicació E és injectiva.
• Una codificació és instantàniament desxifrable, o de tipus prefix, si no hi ha dues paraules diferents ${\displaystyle \scriptstyle w_{i}}$ i ${\displaystyle \scriptstyle w_{j}}$ així que ${\displaystyle \scriptstyle E(w_{i})}$ és una seqüència inicial de ${\displaystyle \scriptstyle E(w_{j})}$.

Desigualtat de Kraft

Article principal: Desigualtat de Kraft

Desigualtat de McMillan

Article principal: Desigualtat de McMillan

Compressió de dades

Article principal: compressió de dades

La compressió de dades ^[5] que consisteix en el procés de codificació de dades utilitzant el mínim nombre possible de bits, o unitats d'informació gràcies a la utilització d'esquemes de codificat (còdecs) i pot ser oompressió sense pèrdua, si les dades abans i després de comprimir-són exactes a la compressió sense pèrdua, o amb un algorisme de compressió amb pèrdua que pot eliminar dades per reduir més la mida, perdent qualitat.^[6]

Criptografia

Article principal: Criptografia

La criptografia son formes de convertir informació des de la seva forma original cap a un codi incomprensible, de forma que sigui incomprensible pels que no coneguin aquesta tècnica. La criptografia clàssica utilitzava substitucions i permutacions relativament senzilles per tal d'amagar els missatges. La criptografia moderna en canvi utilitza àmpliament les disciplines de les matemàtiques, la informàtica i l'electrotècnia. Els xifratges poden ser simètrics o de clau privada, quan es fa servir la mateixa clau per xifrar i desxifrar, o asimètrics quan fa servir claus diferents: una parella composta per una clau pública, que serveix per xifrar, i per una clau privada, que serveix per desxifrar.^[7]

Codi en línia

El codi en línia o codi de línia (modulació a banda base) consisteix a representar el senyal digital transportat respecte a la seva amplitud respecte del temps. El senyal està perfectament sincronitzat gràcies a les propietats específiques de la capa física. La representació de l'ona se sol fer mitjançant un nombre determinat d'impulsos. Aquests impulsos representen els uns i els zeros digitals. Els tipus més comuns de codificació en línia són unipolar, polar, bipolar i Manchester.^[8] Després de la codificació en línia, el senyal s'envia a través de la capa física. De vegades les característiques de dos canals aparentment molt diferents són prou semblants perquè el mateix codi sigui usat per ells.

Altres aplicacions de la teoria de la codificació

Una altra preocupació de la teoria de la codificació és dissenyar codis que ajudin a la sincronització. Es pot dissenyar un codi perquè un canvi de fase es pugui detectar i corregir fàcilment i que es puguin enviar múltiples senyals al mateix canal.

Una altra aplicació de codis, utilitzada en alguns sistemes de telefonia mòbil, és l'accés múltiple per divisió de codi (CDMA). A cada telèfon se us assigna una seqüència de codi que no té correlació amb els codis d'altres telèfons. En transmetre, la paraula clau es fa servir per modular els bits de dades que representen el missatge de veu. Al receptor es realitza un procés de demodulació per recuperar les dades. Les propietats d'aquesta mena de codis permeten que molts usuaris (amb diferents codis) utilitzin el mateix canal de ràdio alhora. Per al receptor, els senyals d'altres usuaris apareixeran al demodulador només com un soroll de baix nivell.

Una altra classe general de codis són els codis de sol·licitud de repetició automàtica (ARQ). En aquests codis, el remitent afegeix redundància a cada missatge per verificar errors, generalment afegint bits de verificació. Si els bits de verificació no són consistents amb la resta del missatge quan arriba, el receptor demanarà al remitent que retransmeti el missatge. Tots els protocols de xarxa d'àrea àmplia excepte els més simples utilitzen ARQ. Els protocols comuns inclouen SDLC (IBM), TCP (Internet), X.25 (Internacional) i molts altres. Hi ha un ampli camp de recerca sobre aquest tema degut al problema de fer coincidir un paquet rebutjat amb un paquet nou. Normalment es fan servir esquemes de numeració, com en TCP.^[9]

Proves en grup

Per a les proves en grup es fan servir codis d'una manera diferent. Cal considerar un gran grup d'articles en què molt pocs són diferents de manera particular (per exemple, productes defectuosos o subjectes de prova infectats). La idea de les proves grupals és determinar quins elements són “diferents” utilitzant la menor quantitat de proves possible. L'origen del problema té les seves arrels en la Segona Guerra Mundial quan les Forces Aèries de l'Exèrcit dels Estats Units necessitaven examinar els seus soldats per detectar sífilis.^[10]

Codificació analògica

La informació es codifica de manera anàloga a les xarxes neuronals dels cervells, al processament de senyals analògics i la electrònica analògica. Els aspectes de la codificació analògica inclouen la correcció d'errors analògics,^[11] compressió de dades analògiques^[12] i xifrat analògic.^[13]

Detecció i correcció d'errors

Article principal: Detector i corrector d'errors

Per netejar els errors de transmissió introduïts per l'atmosfera terrestre (a l'esquerra), els científics de Goddard van aplicar la correcció d'errors Reed-Salomon (dreta), que s'utilitza habitualment en CD i DVD. Els errors típics inclouen píxels que falten (blanc) i senyals falses (negre). La franja blanca indica un període breu quan la transmissió es va aturar.

La detecció i correcció d'errors en informàtica i teoria de la informació és l'ús de mètodes per detectar i corregir errors en la transmissió i emmagatzematge de dades.^[14] En el cas de la transmissió, això també inclou la retransmissió selectiva de segments de dades incorrectes. Els mètodes de detecció i correcció d'errors requereixen l'ús de bits redundants. En general, calen més bits redundants per la correcció que per la detecció d'errors. És una tècnica de codificació basada en la redundància. Està destinada a corregir els errors de transmissió d'una informació (anomenada sovint missatge) sobre un canal de comunicació poc fiable. La teoria de codis correctors no es limita només a les comunicacions clàssiques (ràdio, cable coaxial, fibra òptica, etcètera.) sinó també als suports per a l'emmagatzematge com els discs compactes, la memòria RAM i altres aplicacions on la integritat de les dades és important.

Referències

1. «Teoria de Codis». grup de recerca CRISES. URV. Arxivat de l'original el 13 de desembre 2021. [Consulta: 13 desembre 2021].
2. Herrera Perez, Enrique. Comunicaciones I. Señales, modulacion y transmision (en castellà). Limusa, 2008, p. 266-268. ISBN 9789681857196.
3. Basat en "50 coses que cal saber sobre matemàtiques", de Tony Crilly.
4. Dominic Welsh, 1988, p. 15
5. Wade, Graham. Signal coding and processing (en anglès). 2a ed.. Cambridge University Press, 1994, p. 34. ISBN 978-0-521-42336-6. Arxivat 16 de maig 2024 a Wayback Machine.
6. Talukdar, Asoke K. Mobile Computing (en anglès). 2a. Tata McGraw-Hill Education, 2010, p. 509. ISBN 0070144575. Arxivat 2024-05-16 a Wayback Machine.
7. Rifà, Josep. Seguretat computacional. Servei de Publicacions de la Universitat Autònoma de Barcelona, 1995, p. 18. ISBN 8449004640. Arxivat 2024-05-16 a Wayback Machine.
8. Michael John Ryan, Michael Frater. Communications and Information Systems (en anglès). Argos Press P/L, 2002, p. 317. ISBN 0958023808. Arxivat 2024-05-16 a Wayback Machine.
9. «RFC793». RFCs. Internet Engineering Task Force (IETF), 01-09-1981. Arxivat de l'original el 2009-03-02. [Consulta: 10 maig 2024].
10. Dorfman, Robert «The detection of defective members of large populations». Annals of Mathematical Statistics, vol. 14, 4, 1943, pàg. 436–440. DOI: 10.1214/aoms/1177731363.
11. Chen, Brian; Wornell, Gregory W. «Analog Error-Correcting Codes Based on Chaotic Dynamical Systems». IEEE Transactions on Communications, vol. 46, 7, 7-1998, pàg. 881–890. DOI: 10.1109/26.701312. Arxivat 2001-09-27 at the Library of Congress
12. (1999) "On Analog Signature Analysis".
13. «Cryptanalyzing an Encryption Scheme Based on Blind Source Separation». IEEE Transactions on Circuits and Systems I, vol. 55, 4, 4-2008, pàg. 1055–63. arXiv: cs/0608024. DOI: 10.1109/TCSI.2008.916540. Arxivat 2021-03-28 a Wayback Machine.
14. G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)

Bibliografia

• Tony Crilly. 50 cosas que hay que saber sobre matemáticas. Ed. Ariel, 2011. ISBN 978-987-1496-09-9.
• Dominic Welsh (1988): Codes and Cryptography, Clarendon Press, Oxford, ISBN 0-19-853287-3