Teoría de códigos

La teoría de códigos ye una especialidá matemática que trata de les lleis de la codificación de la información. A les traces, codificar ye tresformar una información nuna señal convenida pa la so comunicación. Decodificar sería'l procesu inverso y complementario del anterior pol cual la señal comunicada ye tresformada na información orixinal. La puxanza de les comunicaciones a partir de la segunda metá del sieglu XX motivó un fuerte desenvolvimientu de la teoría de códigos.

Introducción ya historia

**Cronoloxía**^[1]
Añu	Acontecimientu
55 e.C.	Xuliu César, al invadir Gran Bretaña, utiliza códigos pa unviar mensaxes a los sos xenerales.
1750 d.C.	Leonhard Euler sienta les bases de la criptografía de clave pública col so teorema.
1844	Samuel Morse tresmite'l so primer mensaxe utilizando'l so códigu.
Década de 1920	Desenvuélvese la máquina Enigma.
1950	Richard Hamming publica un artículu fundamental pa crear códigos que detecten y corrixen errores.
Década de 1970	Desenvolvimientu de la criptografía de clave pública.

Yá que los códigos usar pa comunicar información, unu de los problemes a los que tou códigu enfréntase ye l'error sistemáticu y, tamién, el casual. La redundancia ye l'únicu mediu de prevenir l'error. Los llinguaxes humanos tienen una gran redundancia que-yos da flexibilidá a mariña, eso sí, d'eficacia. Los códigos matemáticos utilicen una redundancia más racional.

Hai códigos llamaos de detección d'errores, que dexen detectar alteraciones nun mensaxe codificado. Utilícense sobremanera en redolaes onde'l mensaxe puede ser reenviado tantes vegaes como se precise. Los protocolos d'Internet, por casu, tán formaos por un anidamiento de codificaciones dende'l nivel de tresporte hasta'l nivel físicu, teniendo cada nivel el so propiu sistema de detección d'errores.

Esti tipu de códigos resulta non aparente en redolaes onde la comunicación nun puede repitise y precísase asegurar hasta ciertu puntu que se va a recibir la información correuta. Un exemplu típico y vistoso ye cuando s'unvia una nave espacial a les llendes del sistema solar y dende ellí tien d'unviar una serie de fotografíes primero que se-y acaben, digamos, les piles. Trátase d'una situación delicada, porque si les ondes electromagnétiques que porten la información lleguen aburuyaes tola misión fracasa. Un códigu que namái detectara que la información ye incorreuta nun sirviría pa nada. Ye necesariu daqué más, un códigu non yá detector sinón correutor d'errores.

Por casu, el sistema de codificación más senciellu puede consistir en qu'un "0" represéntase un "non" y con un "1" un sí. Nesti casu, si quiero tresmitir un "si", y cométese un error al tresmitir un "0" en vegada del "1", el receptor del mensaxe va faer lo opuesto a lo pidío. Pero si sicasí conviense que "00" sía "non" y "11" sía "sí", entós, si comete un error nun díxitu, y por casu el receptor recibe un "01", va detectar qu'hubo un error, anque nun va saber cual ye'l mensaxe correutu. Sicasí si la convención ye que "000" ye "non" y "111" un sí, y supiérase que al tresmitir un mensaxe solo ye posible, pola metodoloxía utilizada, cometer un solu error de díxitu, entós, si al recibir un "001", el receptor va saber que se trata d'un "non". Asina siguiendo, si tresmitimos un bloque de ceros, o un bloque d'unos, anque se cometan dellos errores na tresmisión de dellos díxitos, va tenese la casi certidume de cual ye l'error cometíu nel mensaxe recibíu, y correxilo.^[2]

Na actualidá, les meyores que se tán produciendo nesta disciplina tán empuestos escontra l'usu de les bases de Groebner como ferramienta pa la codificación y decodificación nos códigos detectores d'errores.

El problema de la codificación eficiente

Unu de los principales problemes de la teoría de códigos ye'l siguiente. Supongamos que tenemos una fonte d'información qu'emite o tresmite "símbolos" de ciertu conxuntu $\scriptstyle W=\{w_{1},\dots ,w_{n}\}$ que por propósitos pedagóxicos vamos llamar a cencielles "pallabres", de forma que la probabilidá d'emisión d'una pallabra sía independiente del símbolu anterior $\scriptstyle P(w^{(t)})=w_{k}|w^{(t-1)}=w_{j}=P(w=w_{k})$ , siendo $\scriptstyle p_{i}=P(w=w_{i})$ . Si $\scriptstyle \Sigma$ ye un alfabetu de D "lletres", ¿qué códigu tien d'asignáse-y a la pallabra $\scriptstyle w_{i}$ usando "lletres" del alfabetu de tal manera que se consiga una codificación tan económica como sía posible?^[3] Formalmente una codificación ye una aplicación $\scriptstyle Y:W\to {\mathcal {P}}_{0}(\Sigma )$ del conxuntu de "pallabres" nel conxuntu de secuencies finitas de "lletres" del alfabetu. Un mensaxe ye una secuencia finita de pallabres, $\scriptstyle m=w_{i_{1}}\dots w_{i_{n}}$ , si disponer d'una codificación de pallabres, ésta estiéndese darréu a mensaxes por aciu concatenación:

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

Dellos tipos de codificaciones interesantes son:

Una codificación ye unívocamente descifrable si cualquier secuencia finita de $\scriptstyle {\mathcal {P}}_{0}(\Sigma )$ ye la imaxe de como muncho un mensaxe, esto ye, cuando l'aplicación Y ye inyectiva.
Una codificación ye instantáneamente descifrable, o de tipu prefixu, si nun esisten dos pallabres distintos $\scriptstyle w_{i}$ y $\scriptstyle w_{j}$ tal que $\scriptstyle Y(w_{i})$ ye una secuencia inicial de $\scriptstyle Y(w_{j})$ .

Desigualdá de Kraft

Desigualdá de McMillan

Referencies

Notes

↑ Basáu en "50 coses qu'hai que saber sobre matemátiques", de Tony Crilly.
↑ Exemplu llográu nel llibru de "50 coses qu'hai que saber sobre matemátiques", de Tony Crilly
↑ Dominic Welsh, 1988, p. 15

Bibliografía

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

Ver tamién

Teoría de la información

[1] Basáu en "50 coses qu'hai que saber sobre matemátiques", de Tony Crilly.

[2] Exemplu llográu nel llibru de "50 coses qu'hai que saber sobre matemátiques", de Tony Crilly

[3] Dominic Welsh, 1988, p. 15

[1]

[2]

[3]