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 editar

Cronoloxía[1]
Añu -----

align="left" bgcolor="#f0f5fa"

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 editar

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?[3] 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 editar

Desigualdá de McMillan editar

Referencies editar

Notes editar

  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

Bibliografía editar

Ver tamién editar