INSTITUTO TECNOLOGICO SUPERIOR DE URUAPAN
Codificacin Hamming Codificacin CRC
Redes de Computadoras
Rosa Idalia Rodrguez Barajas
6A
Cdigo Hamming
Es un cdigo que se utiliza en la deteccin y correccin de errores que se producen en la transmisin de cdigos binarios, la palabra de cdigo se conforma por los bits de comprobacin y los bits de informacin. Para poder continuar con el desarrollo del cdigo es necesario tener en cuenta algunas generalidades y conceptos bsicos: Cdigo binario: Es una representacin unvoca de las cantidades, de tal forma que a cada una de stas se le asigna una combinacin de smbolos binarios. Distancia entre dos combinaciones binarias: Viene dada por el nmero de bits que hay que cambiar en una de ellas para obtener la otra. Distancia mnima de un cdigo: Es la menor de las distancias entre dos combinaciones binarias cualesquiera pertenecientes a dicho cdigo.
El cdigo Hamming se genera a partir de una distancia mnima de 3, ya que una distancia de 1 o 2 es inconveniente para poder generar un cdigo para detectar un error. La distancia mnima de Hamming est dada por la siguiente ecuacin: Dm= 2X+1 Donde Dm es la distancia mnima de un cdigo para permitir la correccin de datos y X es las lneas de datos. Si se tuviese una distancia de 1 no tendramos valores para saber si hay o no un error. Si se tienen una distancia de 2 se podra lograr un sistema de correccin de error con un bit de paridad pero el problema que esto lleva es que un sistema con distancia 2 puede tener datos errneos que pueden pasar como datos correctos. Con la distancia de 3 se tiene que los cdigos no van a tener datos o resultados similares por ende se puede detectar el error y se puede desarrollar un sistema para su correccin como el Hamming.
Para la generacin del cdigo Hamming se deben tener en cuenta tres variables: n: nmero de bits del cdigo original que se pretende transmitir. p: nmero de bits de paridad par generados en el transmisor, o sea, nmero de lneas que aadimos al cdigo inicial. c: nmero de bits detectores de paridad par generados por el receptor.
El valor de p = c, ya que los bits de paridad generados tanto en el transmisor como en el receptor debe ser la misma. El nmero de combinaciones que se pueden formar con los c bits detectores de paridad tiene que ser mayor o igual que el nmero de lneas del cdigo original (n) ms el nmero de lneas de paridad aadidas (p) ms uno, este ltimo para contemplar el caso de no error. 2c>=n+p+1 Esta ecuacin nos muestra que existen unas combinaciones, estas no pueden ser asignadas de forma aleatoria a un evento, para asignar estas combinaciones a un evento especfico este debe estar en uno de los tres grupos diferenciados. 1. Combinacin asignada a la situacin en que no haya error en la transmisin. 2. Combinaciones asignadas a los bits de paridad generados en el transmisor. 3. Combinaciones asignadas a los bits de datos del cdigo original. Podemos tener un manejo de esta ecuacin para poder obtener la cantidad mnima de bits de informacin que nosotros podemos enviar. Si se despeja n n=2c-c-1 Teniendo en cuenta que p =c Si contamos con los valores de bits de paridad podemos encontrar los bits de informacin que se pueden manejar. Para obtener el nmero de bits total de la cadena del mensaje (s) se debe realizar la siguiente operacin: s=2c-1
Codificacin de redundancia cclica (CRC)
Los CRC se caracterizan por los siguientes trminos: Uso del lgebra lineal
La estructura de un Cdigo CRC est dada por C=(n,k)
Dnde: k n C es el nmero de bits en una palabra codificada es el nmero total de bits en una palabra codificada se le denomina as al cdigo.
La paridad que implementan es polinomial y se construye por medio de un polinomio primo o generador <g(x)>. Los polinomios generadores pueden ser de grado 0, 1, 2, etc. El grado de este polinomio depende del nmero de errores que se desean corregir. [g(x)]N 2t-1; donde es el nmero de errores que se desean corregir.
Ejemplo: Codificador CRC (7,4) Se tienen los siguientes polinomios g(x) =1+x2+x3 (pol. generador) x3 indica que son 3 FF d(x)=x+x3 (datos=0101)
Proceso de Codificacin 1. Se introduce el primer bit de informacin en el codificador:
2. Se introduce el segundo bit de informacin en el codificador:
3. Se introduce el tercer bit de informacin en el codificador:
4. Se introduce el cuarto bit de informacin en el codificador:
Finalmente se toma la paridad de los FF, misma que se adiciona a la informacin para terminar el proceso.
