Teoria de còdics

La teoria de còdics és una especialitat matemàtica que tracta de les lleis de la codificació de l'informació. A grans traces, codificar és transformar una informació en una senyal convinguda per a la seua comunicació. Decodificar seria el procés invers i complementari de l'anterior pel qual la senyal comunicada és transformada en l'informació original. L'auge de les comunicacions a partir de la segona mitat de el XX va motivar un fort desenroll de la teoria de còdics.

Introducció i història

**Cronologia**^[1]
Any	Acontenyiment
55 a. C.	Juliol César, en invadir Gran Bretanya, utilisa còdics per a enviar mensages als seus generals.
1750 d. C.	Leonhard Euler senta les bases de la criptografia de clau pública en la seua teorema.
1844	Samuel Morse transmet el seu primer mensage utilisant el seu còdic.
Década de 1920	Es desenrolla la màquina Enigma.
1950	Richard Hamming publica un artícul fonamental per a crear còdics que detecten i corrigen errors.
Década de 1970	Desenroll de la criptografia de clau pública.

ya que els còdics s'usen per a comunicar informació, un dels problemes als que tot còdic s'enfronta és l'error sistemàtic i, també, el fortuït. La redundància és l'únic mig de previndre l'error. Els llenguages humans tenen una gran redundància que els dona flexibilitat a costa, això sí, d'eficàcia. Els còdics matemàtics utilisen una redundància més racional.

Hi ha còdics cridats de detecció d'errors, que permeten detectar alteracions en un mensage codificat. S'utilisen sobretot en entorns a on el mensage pot ser reenviat tantes voltes com es necessite. Els protocols d'Internet, per eixemple, estan formats per un anidamiento de #codificació des del nivell de transport fins al nivell físic, tenint cada nivell el seu propi sistema de detecció d'errors.

Este tipo de còdics resulta inadequat en entorns a on la comunicació no es pot repetir i es necessita assegurar fins a cert punt que es va a rebre l'informació correcta. Un eixemple típic i vistós és quan s'envia una nau espacial als confines del sistema solar i des d'allí deu enviar una série de fotografies ans que se li acaben, digam, les piles. Es tracta d'una situació delicada, perque si les ones electromagnètiques que porten l'informació apleguen distorsionades tota la missió fracassa. Un còdic que solament detectara que l'informació és incorrecta no serviria per a res. És necessari alguna cosa més, un còdic no sol detector sino corrector d'errors.

Per eixemple, el sistema de codificació més senzill pot consistir que un "0" es representa un "no" i en un "1" un sí. En este cas, si vullc transmetre un "si", i es comet un error en transmetre un "0" en lloc de el "1", el receptor del mensage farà lo opost a lo demanat. Pero si en canvi es convé que "00" siga "no" i "11" siga "sí", llavors, si es comet un error en un dígit, i per eixemple el receptor rep un "01", detectarà que va haver un error, encara que no sabrà com és el mensage correcte. En canvi si la convenció és que "000" és "no" i "111" un sí, i se sabera que en transmetre un mensage solament és possible, per la metodologia utilisada, cometre un sol error de dígit, llavors, si en rebre un "001", el receptor sabrà que es tracta d'un "no". Aixina seguint, si transmetem un bloc de zeros, o un bloc d'uns, encara que es cometen alguns errors en la transmissió d'alguns dígits, es tindrà la casi certea d'cual és l'error comés en el mensage rebut, i corregir-ho.^[2]

En l'actualitat, els alvanços que s'estan produint en esta disciplina estan encaminats cap a l'utilisació de les bases de Groebner com a ferramenta per a la codificació i decodificación en els còdics detectors d'errors.

El problema de la codificació eficient

Un dels principals problemes de la teoria de còdics és el següent. Supongam que tenim una font d'informació que emet o transmet "símbols" de cert conjunt $W = {w_{1}, \dots, w_{n}}$ que per propòsits pedagògics cridarem simplement "paraules", de manera que la provabilitat d'emissió d'una paraula siga independent del símbol anterior $P (w^{(t)}) = w_{k} | w^{(t - 1)} = w_{j} = P (w = w_{k})$ , sent $p_{i} = P (w = w_{i})$ . Si $Σ$ és un alfabet de D "lletres", ¿quin còdic deu assignar-se-li a la paraula $w_{i}$ usant "lletres" de l'alfabet de tal manera que es conseguixca una codificació tan econòmica com siga possible?^[3] Formalment una codificació és una aplicació $E : W \to 𝒫_{0} (Σ)$ del conjunt de "paraules" en el conjunt de seqüències finitas de "lletres" de l'alfabet. Un mensage és una seqüència finita de paraules, $m = w_{i_{1}} \dots w_{i_{n}}$ , si es dispon d'una codificació de paraules, esta s'estén immediatament a mensages per mig de concatenació:

Alguns tipos de #codificació interessants són:

Una codificació és unívocamente descifrable si qualsevol seqüència finita de $𝒫_{0} (Σ)$ és l'image de com molt un mensage, és dir, quan l'aplicació I és inyectiva.
Una codificació és instantàneament descifrable, o de tipo prefixe, si no existixen dos paraules diferents $w_{i}$ i $w_{j}$ tal que $E (w_{i})$ és una seqüència inicial de $E (w_{j})$ .

Desigualtat de Kraft

Artícul principal → Desigualtat de Kraft.

Desigualtat de McMillan

Artícul principal → Desigualtat de McMillan.

Codificació criptográfica

Artícul principal → Criptografia.

La criptografia o codificació criptográfica és la pràctica i l'estudi de tècniques de comunicació segura en presència de tercers (cridats adversaris).^[4] En térmens més generals, es tracta de construir i analisar protocols que bloquegen als adversaris;^[5] diversos aspectes de la seguritat de l'informació, com la confidencialitat, l'integritat de les senyes, l'autenticació i el no repudie^[6] són fonamentals per a la criptografia moderna. La criptografia moderna existix en l'intersecció de les disciplines de matemàtiques, informàtica i ingenieria elèctrica. Les aplicacions de la criptografia inclouen targetes de caixer automàtic, contrasenyes d'ordenador i comerç electrònic.

La criptografia abans de l'era moderna era efectivament sinònim de sifrat, la conversió d'informació d'un estat llegible a aparents nonsense. L'autor d'un mensage sifrat va compartir la tècnica de decodificación necessària per a recuperar l'informació original solament en els destinataris prevists, evitant aixina que persones no desijades feren lo mateix. Des de la Primera Guerra Mundial i el advenimiento del ordenador, els métodos utilisats per a portar a terme la criptología s'han tornat cada volta més complexos i la seua aplicació més estesa.

La criptografia moderna es basa en gran mida en la teoria matemàtica i la pràctica informàtica; Els algoritmes criptográficos estan dissenyats entorn a suposicions de durea computacional, lo que fa que dits algoritmes siguen difícils de trencar en la pràctica per part de qualsevol adversari. En teoria, és possible trencar un sistema d'este tipo, pero no és factible fer-ho per cap mig pràctic conegut. Per lo tant, estos esquemes es denominen computacionalment segurs; Els alvanços teòrics, per eixemple, les millores en els algoritmes de factorización de sancers i la tecnologia informàtica més ràpida requerixen que estes solucions s'adapten contínuament. Existixen esquemes de seguritat teòrica de l'informació que provablement no es poden dessifrar ni tan sols en un poder de còmput illimitat; un eixemple és la llibreta d'un sol us, pero estos esquemes són més difícils d'implementar que els millors mecanismes teòricament rompibles pero computacionalment segurs.

Codificació en llínea

Artícul principal → Còdics en llínea.

Un còdic de llínea (també cridat modulació de banda base digital o método de transmissió de banda base digital) és un còdic elegit per al seu us dins d'un sistema de comunicacions per a propòsits de transmissió de banda base. La codificació de llínea s'utilisa a sovint per al transport de senyes digitals.

La codificació de llínea consistix en representar la senyal digital per a ser transportada per una senyal discreta d'amplitut i temps que està sintonizada de manera òptima per a les propietats específiques del canal físic (i de l'equipe receptor). El patró deforma d'ona de voltage o corrent que s'utilisa per a representar els 1 i 0 de senyes digitals en un enllaç de transmissió es denomina "codificació de llínea". Els tipos comuns de codificació de llínea són unipolar, polar, bipolar i Codificació Manchester.

Atres aplicacions de la teoria de la codificació

Una atra preocupació de la teoria de la codificació és dissenyar còdics que ajuden a la sincronisació. Es pot dissenyar un còdic per a que un canvi de fase es puga detectar i corregir fàcilment i que es puguen enviar múltiples senyals en el mateix canal.

Una atra aplicació de còdics, utilisada en alguns sistemes de telefonia mòvil, és l'accés múltiple per divisió de còdic (CDMA). A cada teléfon se li assigna una seqüència de còdic que no té correlació en els còdics d'atres teléfons. En transmetre, la paraula clau s'utilisa per a modular els bits de senyes que representen el mensage de veu. En el receptor es realisa un procés de demodulación per a recuperar les senyes. Les propietats d'esta classe de còdics permeten que molts usuaris (en diferents còdics) utilisen el mateix canal de ràdio al mateix temps. Per al receptor, les senyals d'atres usuaris apareixeran en el demodulador sol com un soroll de baix nivell.

Una atra classe general de còdics són els còdics de solicitut de repetició automàtica (ARQ). En estos còdics, el remitent agrega redundància a cada mensage per a verificar errors, generalment agregant bits de verificació. Si els bits de verificació no són consistents en el restant del mensage quan aplega, el receptor li demanarà al remitent que retransmeta el mensage. Tots els protocols de ret d'àrea àmplia llevat els més simples utilisen ARQ. Els protocols comuns inclouen SDLC (IBM), TCP (Internet), X.25 (Internacional) i molts uns atres. Existix un ampli camp d'investigació sobre este tema pel problema de fer coincidir un paquet rebujat en un paquet nou. Normalment s'utilisen esquemes de numeració, com en TCP.^[7]

Proves en grup

Per a les proves en grup s'usa còdics d'una manera diferent. Cal considerar un gran grup d'artículs en els que molt pocs són diferents d'una manera particular (per eixemple, productes defectuosos o subjectes de prova infectats). L'idea de les proves grupales és determinar qué elements són "diferents" utilisant la menor cantitat de proves possible. L'orige del problema té les seues raïls en la Segona Guerra Mundial quan les Forces Aérees de l'Eixèrcit dels Estats Units necessitaven examinar als seus soldats per a detectar #sífilis.^[8]

Codificació analògica

L'informació es codifica de manera anàloga en les rets neuronals dels cervells, en el processament de senyals analògiques i l'electrònica analògica. Els aspectes de la codificació analògica inclouen la correcció d'errors analògics,^[9] compressió de senyes analògiques i sifrat analògic.^[10]

Codificació neuronal

La codificació neuronal és un camp relacionat en la neurociencia que s'ocupa de cóm l'informació sensorial i d'atres tipos es representa en el cervell per mig de rets de neurones. L'objectiu principal d'estudiar la codificació neuronal és caracterisar la relació entre l'estímul i les respostes neuronals individuals o grupales i la relació entre l'activitat elèctrica de les neurones en el conjunt.^[11] Es creu que les neurones poden codificar informació tant digital com analògica,^[12] i que les neurones seguixen els principis de la teoria de l'informació i comprimixen l'informació,^[13] i detectar i corregir errors en les senyals que s'envien per tot el cervell i el sistema nerviós més ampli.

Usos en l'anàlisis de texts

L'anàlisis de còdic és útil per a intentar decodificar text sifrat, si el còdic de protecció utilisat és dèbil (per eixemple, el còdic Caesar o Vigenère). La detecció de les característiques estadístiques d'un text també permet verificar, inclús sense entendre el seu llenguage, si un text ha tingut més d'un autor (pot dir-se que l'encara indescifrado Manuscrit Voynich tenia dos autors distints). També permet analisar els texts de Víctor Hugo i, per estes característiques estadístiques, detectar la década de la seua escritura. El Centre Científic d'IBM (IBM La Gaude, França) també va estudiar els discursos de Charres de Gaulle i va mostrar que estos discursos es varen estendre en el temps, a excepció d'alguns discursos «crítics» (com el del 30 de maig de 1968). l'Universitat de Stanford també va comparar els vocabularis respectius de Marcel Proust i Paul Valéry. L'ingenier Jean-Jacques Walter també va portar a terme este anàlisis sobre el text del Corán i va defendre una tesis segons la qual li va atribuir vàries dotzenes d'autors (a lo manco 30 autors diferents, provablement 50, com a màxim 100), inicialment en varis idiomes, durant un periodo de doscents anys.^[14]Plantilla:,.^[15]

Referències

Notes

↑ Basat en "50 coses que cal saber sobre matemàtiques", de Tony Crilly.
↑ Eixemple obtingut en el llibre de "50 coses que cal saber sobre matemàtiques", de Tony Crilly
↑ Dominic Welsh, 1988, p. 15
↑ Rivest, Ronald L. (1990). «Cryptology», J. Van Leeuwen (ed.). Handbook of Theoretical Computer Science (vol. 1), Elsevier.
↑ «Introduction», Introduction to Modern Cryptography, p. 10.
↑ (1997) Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0.
↑ «RFC793». RFCs. Internet Engineering Task Force (IETF).
↑ “The detection of defective members of large populations” . Annals of Mathematical Statistics 14 (4): 436–440. doi:10.1214/aoms/1177731363.
↑ “Analog Error-Correcting Codes Based on Chaotic Dynamical Systems” . IEEE Transactions on Communications 46 (7): 881–890. doi:10.1109/26.701312.
↑ “Cryptanalyzing an Encryption Scheme Based on Blind Source Separation” . IEEE Transactions on Circuits and Systems I 55 (4): 1055–63. doi:10.1109/TCSI.2008.916540.
↑ “Multiple neural spike train data analysis: state-of-the-art and future challenges” . Nature Neuroscience 7 (5): 456–461. doi:10.1038/nn1228. PMID 15114358.
↑ Thorpe, S.J. (1990). «Spike arrival claves: A highly efficient coding scheme for neural networks», Parallel processing in neural systems and computers (PDFPDF), North-Holland, pp. 91–94. ISBN 978-0-444-88390-2.
↑ “Information Distortion and Neural Coding” . Canadian Applied Mathematics Quarterly 10 (1): 10.
↑ Entrevista a Jean-Jacques Walter 8/10/2013 en el programa "Li Grand témoin"
↑ Anàlisis estadístic del Corán.

Bibliografia

Tony Crilly (2011). 50 coses que cal saber sobre matemàtiques, Ed. Ariel.
Dominic Welsh (1988): Codes and Cryptography, Clarendon Press, Oxford, ISBN 0-19-853287-3

Vore també

Teoria de l'informació

Referències

Este artícul conté una traducció derivada de «Teoría de códigos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Basat en "50 coses que cal saber sobre matemàtiques", de Tony Crilly.

[2] Eixemple obtingut en el llibre de "50 coses que cal saber sobre matemàtiques", de Tony Crilly

[3] Dominic Welsh, 1988, p. 15

[rivest90-4] Rivest, Ronald L. (1990). «Cryptology», J. Van Leeuwen (ed.). Handbook of Theoretical Computer Science (vol. 1), Elsevier.

[modern-crypto-5] «Introduction», Introduction to Modern Cryptography, p. 10.

[hac-6] (1997) Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0.

[7] «RFC793». RFCs. Internet Engineering Task Force (IETF).

[8] “The detection of defective members of large populations” . Annals of Mathematical Statistics 14 (4): 436–440. doi:10.1214/aoms/1177731363.

[9] “Analog Error-Correcting Codes Based on Chaotic Dynamical Systems” . IEEE Transactions on Communications 46 (7): 881–890. doi:10.1109/26.701312.

[10] “Cryptanalyzing an Encryption Scheme Based on Blind Source Separation” . IEEE Transactions on Circuits and Systems I 55 (4): 1055–63. doi:10.1109/TCSI.2008.916540.

[Brown-11] “Multiple neural spike train data analysis: state-of-the-art and future challenges” . Nature Neuroscience 7 (5): 456–461. doi:10.1038/nn1228. PMID 15114358.

[12] Thorpe, S.J. (1990). «Spike arrival claves: A highly efficient coding scheme for neural networks», Parallel processing in neural systems and computers (PDFPDF), North-Holland, pp. 91–94. ISBN 978-0-444-88390-2.

[13] “Information Distortion and Neural Coding” . Canadian Applied Mathematics Quarterly 10 (1): 10.

[14] Entrevista a Jean-Jacques Walter 8/10/2013 en el programa "Li Grand témoin"

[15] Anàlisis estadístic del Corán.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]