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íaBasáu en "50 coses qu'hai que saber sobre matemátiques", de Tony Crilly.  AñuAcontecimientu 55 e.C.  Xuliu César, al invadir Gran Bretaña, utilizacódigos pa unviar mensaxes a los sos xenerales. 1750 d.C.  Leonhard Euler sienta les bases de la criptografíade clave pública col so teorema. 1844 Samuel Morse tresmite'l so primer mensaxeutilizando'l so códigu. Décadade 1920 Desenvuélvese la máquina Enigma. 1950 Richard Hamming publica un artículu fundamentalpa crear códigos que detecten y corrixen errores. Décadade 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.Exemplu llográu nel llibru de "50 coses qu'hai que saber sobre matemátiques", de Tony Crilly

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  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 , siendo . Si  ye un alfabetu de D "lletres", ¿qué códigu tien d'asignáse-y a la pallabra  usando "lletres" del alfabetu de tal manera que se consiga una codificación tan económica como sía posible?Dominic Welsh, 1988, p. 15
Formalmente una codificación ye una aplicación  del conxuntu de "pallabres" nel conxuntu de secuencies finitas de "lletres" del alfabetu. Un mensaxe ye una secuencia finita de pallabres, , si disponer d'una codificación de pallabres, ésta estiéndese darréu a mensaxes por aciu concatenación:

Dellos tipos de codificaciones interesantes son:
 Una codificación ye unívocamente descifrable si cualquier secuencia finita de  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  y  tal que  ye una secuencia inicial de .

 Desigualdá de Kraft 

 Desigualdá de McMillan 

 Referencies 
 Notes 

 Bibliografía 

 Dominic Welsh (1988): Codes and Cryptography, Clarendon Press, Oxford, ISBN 0-19-853287-3

 Ver tamién 
 Teoría de la información

Categoría:Criptografía