Teoría de códigos

La teoría de códigos es una especialidad matemática que trata de las leyes de la codificación de la información. A grandes rasgos, codificar es transformar una información en una señal convenida para su comunicación. Decodificar sería el proceso inverso y complementario del anterior por el cual la señal comunicada es transformada en la información original. El auge de las comunicaciones a partir de la segunda mitad del siglo XX motivó un fuerte desarrollo de la teoría de códigos.

Puesto que los códigos se usan para comunicar información, uno de los problemas a los que todo código se enfrenta es el error sistemático y, también, el fortuito. La redundancia es el único medio de prevenir el error. Los lenguajes humanos tienen una gran redundancia que les da flexibilidad a costa, eso sí, de eficacia. Los códigos matemáticos utilizan una redundancia más racional.

Hay códigos llamados de detección de errores, que permiten detectar alteraciones en un mensaje codificado. Se utilizan sobre todo en entornos donde el mensaje puede ser reenviado tantas veces como se necesite. Los protocolos de Internet, por ejemplo, están formados por un anidamiento de codificaciones desde el nivel de transporte hasta el nivel físico, teniendo cada nivel su propio sistema de detección de errores.

Este tipo de códigos resulta inadecuado en entornos donde la comunicación no se puede repetir y se necesita asegurar hasta cierto punto que se va a recibir la información correcta. Un ejemplo típico y vistoso es cuando se envía una nave espacial a los confines del sistema solar y desde allí debe enviar una serie de fotografías antes de que se le acaben, digamos, las pilas. Se trata de una situación delicada, porque si las ondas electromagnéticas que portan la información llegan distorsionadas toda la misión fracasa. Un código que solo detectase que la información es incorrecta no serviría para nada. Es necesario algo más, un código no solo detector sino corrector de errores.

Por ejemplo, el sistema de codificación más sencillo puede consistir en que un "0" se representa un "no" y con un "1" un sí. En este caso, si quiero transmitir un "si", y se comete un error al transmitir un "0" en vez del "1", el receptor del mensaje hará lo opuesto a lo pedido. Pero si en cambio se conviene que "00" sea "no" y "11" sea "sí", entonces, si se comete un error en un dígito, y por ejemplo el receptor recibe un "01", detectará que hubo un error, aunque no sabrá cual es el mensaje correcto. En cambio si la convención es que "000" es "no" y "111" un sí, y se supiese que al transmitir un mensaje solo es posible, por la metodología utilizada, cometer un solo error de dígito, entonces, si al recibir un "001", el receptor sabrá que se trata de un "no". Así siguiendo, si transmitimos un bloque de ceros, o un bloque de unos, aunque se cometan algunos errores en la transmisión de algunos dígitos, se tendrá la casi certeza de cual es el error cometido en el mensaje recibido, y corregirlo.^[2]​

En la actualidad, los avances que se están produciendo en esta disciplina están encaminados hacia la utilización de las bases de Groebner como herramienta para la codificación y decodificación en los códigos detectores de errores.

Uno de los principales problemas de la teoría de códigos es el siguiente. Supongamos que tenemos una fuente de información que emite o transmite "símbolos" de cierto conjunto ${displaystyle scriptstyle W={w_{1},dots ,w_{n}}}$ que por propósitos pedagógicos llamaremos simplemente "palabras", de forma que la probabilidad de emisión de una palabra sea independiente del símbolo anterior ${displaystyle scriptstyle P(w^{(t)})=w_{k}|w^{(t-1)}=w_{j}=P(w=w_{k})}$, siendo ${displaystyle scriptstyle p_{i}=P(w=w_{i})}$. Si ${displaystyle scriptstyle Sigma }$ es un alfabeto de D "letras", ¿qué código debe asignársele a la palabra ${displaystyle scriptstyle w_{i}}$ usando "letras" del alfabeto de tal manera que se consiga una codificación tan económica como sea posible?^[3]​ Formalmente una codificación es una aplicación ${displaystyle scriptstyle E:W o {mathcal {P}}_{0}(Sigma )}$ del conjunto de "palabras" en el conjunto de secuencias finitas de "letras" del alfabeto. Un mensaje es una secuencia finita de palabras, ${displaystyle scriptstyle m=w_{i_{1}}dots w_{i_{n}}}$, si se dispone de una codificación de palabras, ésta se extiende inmediatamente a mensajes mediante concatenación:

${displaystyle E(m)=E(w_{i_{1}})dots E(w_{i_{n}})}$

Algunos tipos de codificaciones interesantes son: