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

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.

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?
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:

Dellos tipos de codificaciones interesantes son:
* Una codificación ye **[[Códigu unívocamente descodificable|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

### 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