Teoría de códigos

De Wikipedia
Saltar a navegación Saltar a la gueta

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 y hestoria[editar | editar la fonte]

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

align="left" bgcolor="#f0f5fa"

55 e.C. Julio 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 con la so teorema.
1844 Samuel Morse tresmite'l so primer mensaxe
utilizando el 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.

Cuidao 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 non puede repitise y precísase asegurar hasta ciertu puntu que se va a recibir la información correcta. 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 incorrecta nun sirviría pa nada. Ye necesariu daqué más, un códigu non yá detector sinón corrector 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 correctu. 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 | editar la fonte]

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 | editar la fonte]

Artículu principal: Desigualdá de Kraft

Desigualdá de McMillan[editar | editar la fonte]

Artículu principal: Desigualdá de McMillan

Referencies[editar | editar la fonte]

Notes[editar | editar la fonte]

  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 | editar la fonte]

Ver tamién[editar | editar la fonte]


Teoría de códigos