Corrección de errores
• Los mecanismos explicados detectan errores pero no los corrigen.
• La corrección del error se puede conseguir de dos formas, en la primera, cuando de
descubre un error el receptor puede pedir al emisor que retransmita toda la unidad
de datos, con la segunda, el receptor puede usar un código de corrección de errores
que corrija automáticamente determinados errores.
• En teoría es posible corregir automáticamente cualquier error en un código binario,
sin embargo los códigos de corrección son más sofisticados que los de detección y
necesitan mas bits de redundancia, el número de bits necesarios es tan alto que su
uso no es eficiente, por esa razón la mayoría de la corrección se limita a errores de
tres bits o menos.
Corrección de errores de un único bit
• El concepto de la corrección de errores se puede comprender con el caso
más sencillo: el error de un único bit.
• Un error de un bit supone que un bit ha cambiado de un 0 a un 1 o de un 1
a un 0, para corregir el error, el receptor sólo tiene que invertir el valor del
bit alterado, sin embargo, para hacer eso, el receptor debe saber en qué bit
está el error, por lo que el secreto de la corrección de errores es localizar el
bit o bits inválidos.
• La cuestión es el uso de los bits de redundancia para la corrección.
• Ahora bien ¿cuantos bits de redundancia usar?
Corrección de errores de un único bit
• Para calculas el número de bits de redundancia r necesarios para corregir un
número de bits de datos m, es necesario encontrar una relación entre m y r.
• Si a m de datos bits se le añaden r bits de redundancia, la unidad transmitida es
m+r, los bits de redundancia r deben ser capaces de indicar todas las
posibilidades de error de 1 bit posibles, incluyendo el no error, que en m+r bits
es de m+r+1 posibilidades (no error, error en bit0, error en bit 1, etc), por ello r
debe ser capaz de indicar todas esos estados.
Código Hamming
• Se pueden utilizar los bits de redundancia para corregir errores, pero
¿cómo se manipulan esos bits para descubrir en qué posición se ha
producido el error? R. W. Hamming desarrolló una técnica que
proporciona una solución práctica.
• El código Hamming es un código corrector de errores
• El código Hamming se puede aplicar a unidades de datos de cualquier
longitud y usa la relación de bits de datos y de redundancia
Distancia de Hamming
• La “distancia de Hamming” son los pasos que hay que dar para
convertir algo en otro algo.
• Por ejemplo, para convertir la palabra “Casa” en otra palabra
diferente:
“Casa” en “Masa” ha cambiado una letra (un paso), por lo que la distancia de
Hamming es 1.
“Casa” en “Mapa”, la distancia de Hamming es de 2.
“Casa” en “Mopa”, la distancia de Hamming es de 3.
“Casa” en “Mopx”, la distancia de Hamming es de 4.
• Para binario, la “distancia de Hamming” son los bits que cambian de
un grupo de bits a otro grupo de bits.
Ejercicios
¿ la “Distancia de Hamming” de ir del punto 00 al punto 11?
¿Cual es la distancia de haming para ir del 100 al 011?
Distancia Mínima de Hamming
Da igual que camino escojamos en el grafo, pero lo que
verdaderamente nos interesa es la “Distancia Mínima de Hamming”,
siempre es el camino mínimo entre dos puntos/nodos.
Es decir, la “Distancia Mínima de Hamming” mide el menor número de
sustituciones requeridos para cambiar algo a otro algo (para ir de un
punto a otro).
Peso de Hamming
• “Distancia de Hamming” entre dos puntos A y B, también se conoce
como el “Peso de Hamming” a la diferencia entre dos puntos (A –
B). Es otra forma de determinar la longitud del camino (la cantidad
de aristas) entre dos nodos/puntos. Pero es lo mismo, da como
resultado la “Distancia de Hamming”
Reglas para el código de Hamming
1. Se utilizan como bits de redundancia los conocidos como “bits de paridad” para comprobar
si hay errores o no “1” significa “impar”, y “0” significa “par” (el «Bit de Paridad» es la suma
de “1s”; por ejemplo, la cadena de bits “1011” la suma de “1s” es 3, que es impar, por lo
que el bit de paridad es “1”.
2. Cada “bit de paridad” comprobará unos bits determinados, dependiendo de la posición
que ocupe y siguiendo las normas del siguiente ejemplo.
Por ejemplo, la posición es 4, desde está misma posición se seleccionarán 4, luego dejará
4 sin seleccionar, seleccionará los siguientes 4, para luego dejar los siguientes 4 sin
seleccionar, y así hasta el infinito. Lo mismo para todas las posiciones que son potencias
de dos (para la posición 1 es uno sí, uno no, uno sí, uno no, etc; ¿Y para la posición 2?
Dos sí, dos no, dos sí, dos no; ¿Y para los siguientes 8, 16, 32, etc? es muy fácil).
3. De las anteriores selecciones el “bit de paridad” es de lo seleccionado la posición de número
más pequeña (evidentemente, porque si el bit de paridad dice si es par o impar la suma de
los “1s”, si se comprobara a sí mismo, entraríamos en un bucle infinito sin sentido), el resto
son los bits que comprueba (que serán los que se sumen para saber si es par o impar).
Matriz de comprobación de paridad
Los bits de paridad son las potencias de dos: 1, 2, 4, 8, 16, etc., Al “bit
de paridad” en sí, se identifica en la imagen “P” seguido de la posición
que ocupa (por ejemplo, el que ocupa la posición 4, es “P4”).
No hay que confundir con las filas de bits que comprueba cada “bit de
paridad” e incluyéndose así mismo; a cada fila de éstas la he
denominado en la imagen como “fP” seguido de la posición en la que
empieza (como “fP4”, que es la fila que comprueba el “bit de paridad”
llamado “P4” e incluyéndose así mismo).
Hamming mas típico “Hamming (7,4)”.
• Aunque existen infinitos, pero siempre siguiendo las normas, otros
podrían ser el:
• Hamming(3,1)
• Hamming(15,11): en la matriz de la anterior imagen llegaría justo
hasta antes de la posición 16
• Hamming(31,26): llegaría justo hasta la posición anterior a la 32
• etc…
• que quiere decir que por cada 7 bits que representan datos hay 4
que son bits de Datos y los (7 – 4 =) 3 restantes son “bits paridad”.
• A estos datos de 4 bits se le añaden 3 bits más que servirían para
comprobar los datos (los “bits de paridad”).
• Para ello los ubicamos reservando los huecos para los “bits de
paridad” de las posiciones 1, 2 y 4
• Completamos las filas con
• fP1 o Verde: con el “bit de paridad” P1, y las posiciones de datos 3, 5 y 7
• fP2 o Rojo: con el “bit de paridad” P2, y las posiciones de datos 3, 6 y 7
• fP4 o Azul: con el “bit de paridad” P4, y las posiciones de datos 5, 6 y 7
• Para calcular los bits de paridad sumamos los “1” en cada fila y se
completa el bit de paridad.
• Esto es lo que se envía al receptor
Buscar errores y corregirlos
• Supongamos que nos llega por Internet la siguiente cadena de bits, con bits
de datos y “bits de paridad”.
• Tenemos que comprobar que esté bien el dato antes de utilizarlo; no vaya a
ser que por Internet debido a alguna interferencia se haya cambiado algún
bit.
• No sabemos si tiene algún error o no, puede que esté correcto, puede que
tenga algunos bits cambiados; tampoco sabemos si los que están mal son
los bits que corresponden con los datos o los propios “bits de paridad”
Que tenemos que hacer?
1.Hacer la matrix, sin llenar los bits de paridad
• Al igual que hicimos anteriormente calculamos los “bits de paridad”.
Una vez calculados comprobamos con los que ya tenía la cadena
entera, miramos si coinciden
• En el ejemplo podemos comprobar que hay 2 “bits de paridad” que
no coinciden en las filas “fP2” (rojo) y “fP4” (azul), con lo que hay algo
mal seguro.
• Pero, ¿qué bit está mal? Con lo que deducimos que el bit erróneo
debe pertenecer a ambas filas (en este juego de deducción, con las
pruebas hemos logrado reconocer al malo).
• Por lo que, si no es “0” el bit erróneo, debe ser “1” y lo corregimos.
Ejercicios, resuelvelos en tu casuderno
• Supóngase que se transmite una palabra de código y se recibe una
palabra que no pertenece al código y que es 1110101 . Cuál fue la
palabra correcta transmitida.
• Determinar la distancia entre X y Y en:
• a) X = 1100010 y Y = 1010001
• b) X = 0100110 y Y = 0110010
c) X = 00111001, y Y = 10101001
• Encontrar los bits de paridad para el siguiente mensaje a enviar
0110101
Resultado
