Teoria de los codigos
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 delas comunicaciones a partir de la segunda mitad del siglo XX motivó un fuerte desarrollo de la teoría de códigos.
Códigos correctores de errores
El modelo general de un sistema de protección contra los errores producidos en el almacenamiento o la transmisión
de información a través de un canal discreto sin memoria sometido a ruido comprende los siguientes elementos:
1. Una fuente deinformación que genera una cadena o palabra de longitud k con símbolos o letras en un alfabetoL.
2. Un proceso de codificación que transforma unívocamente el mensaje anterior en otro de longitud n > k,
sobre el mismo alfabeto u otro diferente, y al que se ha añadido información redundante suficiente como para poder detectar
y corregir un número razonable de errores que puedieran producirse duranteel proceso de almacenamiento o de transmisión.
3. Un canal a través del cual se transmite el mensaje anteriormente codificado o en el cual se almacena dicha información,
la cual puede sufrir algunos errores debidos al ruido existente en dicho canal, o al deterioro del mismo en el caso de
almacenamiento en un soporte digital.
4. Un proceso de decodificación que asigna al mensajedistorsionado por el canal otro mensaje que, en caso de haberse
producido pocos errores, es el mensaje introducido inicialmente en el canal, permitiéndonos así recuperar la información
transmitida o almacenada, según el caso.
El proceso anteriormente descrito puede ser ilustrado mediante el siguiente esquema:
FORMALIZACION MATEMATICA
De forma más precisa, la codificación es una aplicacióninyectiva
C : Lk ----> G n
y se llama código a la imagen C de dicha aplicación.
En el conjunto G n se define la distancia de Hamming entre dos palabras x,y como
d(x,y):=#{xi != yi | i=1,...,n}
y mide el número de errores cometidos en la transmisión cuando se recibe x en lugar de y,
dando lugar a una estructura de espacio métrico sobre G n. Podemos definir entonces la cantidad
d := d(C):= mín {d(x,y) | x,y en C, x != y}
llamada distancia mínima del código C, y que representa el mínimo número de coordenadas diferentes
entre dos palabras distintas cualesquiera de C.
La distancia mínima d está ligada a la capacidad correctora del código C: éste detecta cualquier configuración
de hasta d-1 errores, siendo capaz de corregir (teóricamente) cualquierconfiguración de hasta (d-1)/2 errores.
El caso que consideraremos en adelante es aquél en que L=G=Fq es un cuerpo finito de cardinal q,
y la codificación C es una aplicación Fq-lineal, en cuyo caso diremos que C es un código lineal de
longitud n y dimensión k, que junto con la distancia d constituyen sus parámetros fundamentales.
Se dice entonces que C es de tipo [n,k,d]q .
Asimismo, sellaman parámetros asintóticos de C al par [R,d], donde R := k/n se llama tasa de transmisión y
representa simultáneamente el coste y la velocidad de transmisión, y donde d := d/n se llama distancia relativa y
mide la capacidad correctora en relación a su longitud. Finalmente, se llama redundancia a la diferencia n-k.
Ejemplos:
* El código de repetición (a,b,c,d) ---> (a,b,c,d,a,b,c,d) es de tipo[8,4,2]q ;
por tanto, detecta 1 error, aunque no lo pueda corregir.
* El código de repetición (a,b,c,d) ---> (a,b,c,d,a,b,c,d,a,b,c,d) es de tipo [12,4,3]q ;
por tanto, detecta 2 errores y corrige 1 error.
* El código de Hamming binario con matriz de control
0001111
0110011
1010101
es de tipo [7,4,3]2 ; por tanto, también detecta 2 errores y corrige 1, pero con mejor tasa de transmisión....
Regístrate para leer el documento completo.