El lenguaje del código

Dos tareas importantes que ha de cumplir cualquier codificación son la detección y la corrección de errores. Cuando una parte, digamos Alicia, se quiere comunicar con otra, digamos Beto, el canal de transmisión que utilicen podría alterar las cadenas de bits enviadas por Alicia. Además de que sería altamente ineficiente que Beto le devolviera a Alicia, con el propósito de verificar que sean correctas, las cadenas que hubiera ella transmitido, se tendría que en ese viaje de regreso podrían introducirse nuevas alteraciones. Por ello, Alicia y Beto pueden convenir de antemano un lenguaje de código, es decir, un conjunto de cadenas, o palabras, que han de servir como códigos. Así, si Beto recibe una cadena y ésta no está en el lenguaje de código convenido, entonces Beto podrá detectar que hubo un error. Si además Beto puede localizar la palabra de código que se parece más a la recibida, entonces podrá sustituir a la cadena recibida por aquella en el código que más se le parezca y corregir así el error detectado.

El conjunto GF(2) que consta de los valores 0 y 1, o sea el conjunto de bits, posee una estructura algebraica de campo, es decir posee una suma (x + y es 0 sólo cuando x = y) con respecto a la cual es un grupo, y posee una multiplicación (x.y es 1 sólo cuando ambos x e y sean 1) con respecto a la cual los elementos no-nulos forman un grupo (en este caso el grupo multiplicativo trivial que consta sólo del 1), y la multiplicación se distribuye respecto a la suma.⁵ Para cada entero n, el conjunto de cadenas de bits de longitud n forma un espacio vectorial, GF(2,n), de dimensión n, sobre el campo GF(2). Se dota así de una estructura geométrica al conjunto de cadenas de longitud n. Todo subespacio vectorial V puede ser descrito por una base de él y al colocar a los vectores de una base como columnas en un arreglo rectangular se obtiene una matriz generatriz de V. Este espacio tiene un complemento ortogonal, digamos Orto(V), y una generatriz suya se dice ser una matriz de paridad de V. Con todo esto se tiene que una cadena está en V siempre que al multiplicarla por una matriz de paridad se obtiene la palabra nula, es decir aquella de longitud n consistente sólo de valores 0. El peso de una palabra en GF(2,n) es el número de valores distintos de 0 en ella. Dadas dos palabras, la distancia entre ellas es el peso de su suma. GF(2,n) resulta así ser un espacio métrico vectorial, es un objeto matemático en el que se puede desarrollar un análisis geométrico completo.

Pues bien, si se elige como lenguaje de código a un subespacio lineal, la detección de errores se realizará multiplicando cada palabra recibida por una matriz de paridad. Si el resultado, llamado síndrome, no fuese nulo, entonces se detecta un error. Dada una palabra en la que aparezca un error, se calcula aquella palabra en el lenguaje de código que minimice la distancia a esa palabra, con lo cual se la habrá de corregir. Las codificaciones construídas así se llaman códigos lineales. A la fecha se ha reportado una gran variedad de éstos: los de Hamming, los polinomiales, los cíclicos, los de Golay, los de Reed-Muller, los de Reed-Solomon, etc.

Un curso muy descriptivo sobre la Teoría de Códigos es: Fundamentals of error-correcting codes, de Huffman, W. C., AND Pless, V. , editado por la Universidad de Cambridge en 2003; un recuento de tipo histórico, técnico y lógico es: Coding theory and cryptography: From Enigma and Geheimschreiber to quantum theory, de Joyner, D que se encuentra disponible en esta dirección:

http://web.usna.navy.mil/~wdj/papers/cryptoday.html.

Unas prácticas con Mathematica de Gachkov, I. están disponibles en: http://library.wolfram.com/infocenter/MathSource/5085/; y unas notas propias, en estado de desarrollo, aparecen en:http://delta.cs.cinvestav.mx/~gmorales/TeoriaDeCodigos/.