Código Hamming: detección y corrección de errores con ejemplos

¿Qué es un error?

Los datos transmitidos pueden dañarse durante la comunicación. Es probable que se vea afectado por ruidos externos u otras fallas físicas. En tal situación, los datos de entrada no pueden ser los mismos que los datos de salida. Esta discrepancia se conoce como "Error".

Los errores de datos pueden provocar la pérdida de datos importantes o seguros. La mayor parte de la transferencia de datos en los sistemas digitales se realizará en forma de "transferencia de bits". Incluso un pequeño cambio puede afectar el rendimiento de todo el sistema. En una secuencia de datos, si 1 se cambia a 0 o 0 se cambia a 1, se denomina "error de bit".

Tipos de errores

Existen principalmente tres tipos de errores de bit que ocurren en la transmisión de datos del remitente al receptor.

• Errores de un solo bit
• Errores de varios bits
• Errores de ráfaga

Errores de un solo bit

El cambio que se produce en un bit de toda la secuencia de datos se conoce como “error de un solo bit”. Sin embargo, la aparición de un error de un solo bit no es tan común. Además, este error solo ocurre en un sistema de comunicación en paralelo porque los datos se transfieren bit a bit en una sola línea. Por lo tanto, hay más posibilidades de que una sola línea sea ruidosa.

Errores de bits múltiples

En la secuencia de datos, si hay un cambio en dos o más bits de una secuencia de datos de un transmisor a un receptor, se conoce como "errores de bits múltiples".

Este tipo de error ocurre principalmente en redes de comunicación de datos de tipo serie y paralelo.

Errores de ráfaga

El cambio del conjunto de bits en la secuencia de datos se conoce como "error de ráfaga". Este tipo de error de datos se calcula desde el cambio del primer bit hasta el último cambio de bit.

¿Qué es la detección y corrección de errores?

En el sistema de comunicación digital, el error se transferirá de un sistema de comunicación a otro. Si estos errores no se detectan y corrigen, los datos se perderán. Para una comunicación eficaz, los datos del sistema deben transferirse con alta precisión. Esto se hará identificando primero los errores y corrigiéndolos.

La detección de errores es un método para detectar los errores que están presentes en los datos transmitidos de un transmisor a un receptor en un sistema de comunicación de datos.

Aquí, puede utilizar códigos de redundancia para encontrar estos errores, agregándolos a los datos cuando se transmiten desde la fuente. Estos códigos se denominan "códigos de detección de errores".

Tres tipos de códigos de detección de errores son:

• Comprobación de paridad
• Comprobación de redundancia cíclica (CRC)
• Verificación de redundancia longitudinal (LRC)

Comprobación de paridad

• También se le conoce como control de paridad.
• Tiene un mecanismo rentable para la detección de errores.
• En esta técnica, el bit redundante se conoce como bit de paridad. Se adjunta para cada unidad de datos. El número total de unos en la unidad debe ser par, lo que se conoce como bit de paridad.

Comprobación de redundancia longitudinal

En esta técnica de detección de errores, un bloque de bits se organiza en formato tabular. El método LRC le ayuda a calcular el bit de paridad para cada columna. El conjunto de esta paridad también se envía junto con los datos originales. El bloque de paridad le ayuda a comprobar la redundancia.

Verificación de redundancia cíclica

La verificación de redundancia cíclica es una secuencia de redundancia que debe agregarse al final de la unidad. Es por eso que la unidad de datos resultante debería ser divisible por un segundo número binario predeterminado.

En el destino, los datos entrantes deben dividirse por el mismo número. En caso de que no haya resto, se asume que la unidad de datos es correcta y se acepta. De lo contrario, indica que la unidad de datos está dañada durante la transmisión y, por lo tanto, debe rechazarse.

En el código Hamming, la fuente codifica el mensaje agregando bits redundantes en el mensaje. Estos bits redundantes se insertan y generan principalmente en ciertas posiciones del mensaje para realizar el proceso de detección y corrección de errores.

Historia del código Hamming

• El código Hamming es una técnica creada por R.W.Hamming para detectar errores.
• El código Hamming debe aplicarse a unidades de datos de cualquier longitud y utiliza la relación entre los datos y los bits de redundancia.
• Trabajó en el problema del método de corrección de errores y desarrolló un conjunto de algoritmos cada vez más potente llamado código Hamming.
• En 1950, publicó el Código Hamming, que hoy se utiliza ampliamente en aplicaciones como la memoria ECC.

Aplicación del código Hamming

A continuación se muestran algunas aplicaciones comunes del uso del código Hamming:

• Satélites
• Memoria del ordenador
• Módems
• PlasmaCAM
• Conectores abiertos
• Cable de blindaje
• Procesador integrado

Ventajas del código Hamming

• El método del código Hamming es eficaz en redes donde los flujos de datos se proporcionan para errores de un solo bit.
• El código Hamming no solo proporciona la detección de un error de bit, sino que también le ayuda a sangrar el error que contiene el bit para que pueda corregirse.
• La facilidad de uso de los códigos Hamming los hace más adecuados para su uso en la memoria de la computadora y para la corrección de un solo error.

Desventajas del código Hamming

• Código de detección y corrección de errores de un solo bit. Sin embargo, si se encuentran errores en varios bits, el resultado puede resultar en otro bit que debería ser correcto para cambiarse. Esto puede provocar que los datos presenten más errores.
• El algoritmo de código Hamming solo puede resolver problemas de un solo bit.

Cómo codificar un mensaje en código Hamming

El proceso utilizado por el remitente para codificar el mensaje incluye los tres pasos siguientes:

• Cálculo del número total de bits redundantes.
• Comprobación de la posición de los bits redundantes.
• Por último, calcular los valores de estos bits redundantes.

Cuando los bits redundantes anteriores están incrustados en el mensaje, se envía al usuario.

Paso 1) Cálculo del número total de bits redundantes.

Supongamos que el mensaje contiene:

• n– número de bits de datos
• p – número de bits redundantes que se le añaden de modo que np pueda indicar al menos (n + p + 1) estados diferentes.

Aquí, (n + p) representa la ubicación de un error en cada una de las posiciones de bits (n + p) y un estado adicional indica que no hay error. Como p bits pueden indicar 2^p estados, 2^p tiene que ser al menos igual a (n + p + 1).

Paso 2) Colocar los bits redundantes en su posición correcta.

Los bits redundantes deben colocarse en posiciones de bits de potencias de 2. Por ejemplo, 1, 2, 4, 8, 16, etc. Se denominan p.₁ (en la posición 1), p₂ (en la posición 2), p₃ (en la posición 4), etc.

Paso 3) Cálculo de los valores del bit redundante.

Los bits redundantes deben ser bits de paridad, lo que hace que el número de unos sea par o impar.

Los dos tipos de paridad son ?

• La cantidad total de bits en el mensaje se hace par, lo que se denomina paridad par.
• El número total de bits del mensaje que se vuelve impar se denomina paridad impar.

Aquí, todo el bit redundante, p1, se debe calcular como paridad. Debe cubrir todas las posiciones de bits cuya representación binaria debe incluir un 1 en la primera posición excluyendo la posición de p1.

P1 es el bit de paridad para cada bit de datos en posiciones cuya representación binaria incluye un 1 en la posición menos importante sin incluir 1 como (3, 5, 7, 9,….)

P2 es el bit de paridad para cada bit de datos en posiciones cuya representación binaria incluye 1 en la posición 2 desde la derecha, sin incluir 2 como (3, 6, 7, 10, 11,…)

P3 es el bit de paridad para cada bit en posiciones cuya representación binaria incluye un 1 en la posición 3 desde la derecha no incluye 4 Como (5-7, 12-15,…)

Descifrar un mensaje en código Hamming

El receptor recibe mensajes entrantes que requieren realizar nuevos cálculos para encontrar y corregir errores.

El proceso de recálculo se realiza en los siguientes pasos:

• Contando el número de bits redundantes.
• Correcto posicionamiento de todos los bits redundantes.
• Comprobación de paridad

Paso 1) Contando el número de bits redundantes

Puede utilizar la misma fórmula para codificar, el número de bits redundantes

2^p ? norte + p + 1

Aquí, el número de bits de datos yp es el número de bits redundantes.

Paso 2) Posicionar correctamente todos los bits redundantes.

Aquí, p es un bit redundante que se encuentra en posiciones de bits de potencias de 2, por ejemplo, 1, 2, 4, 8, etc.

Paso 3) Comprobación de paridad

Los bits de paridad deben calcularse en función de los bits de datos y los bits redundantes.

p1 = paridad(1, 3, 5, 7, 9, 11…)

p2 = paridad(2, 3, 6, 7, 10, 11…)

p3 = paridad(4-7, 12-15, 20-23…)

Resum

• Los datos transmitidos pueden dañarse durante la comunicación.
• Tres tipos de errores de bits son 1) Errores de un solo bit 2) Errores de bits múltiples 3) Errores de bits en ráfaga
• El cambio realizado en un bit en toda la secuencia de datos se conoce como "error de un solo bit".
• En la secuencia de datos, si hay un cambio en dos o más bits de una secuencia de datos de un transmisor a un receptor, se conoce como "errores de bits múltiples".
• El cambio del conjunto de bits en la secuencia de datos se conoce como "error de ráfaga".
• La detección de errores es un método para detectar los errores que están presentes en los datos transmitidos de un transmisor a un receptor en un sistema de comunicación de datos.
• Tres tipos de códigos de detección de errores son 1) Verificación de paridad 2) Verificación de redundancia cíclica (CRC) 3) Verificación de redundancia longitudinal (LRC)
• El código Hamming es un código lineal que resulta útil para la detección de errores de hasta dos bits inmediatos. Es capaz de cometer errores de un solo bit.
• El código Hamming es una técnica creada por R.W.Hamming para detectar errores.
• Las aplicaciones comunes del uso del código Hamming son la memoria de computadora de satélites, módems, procesadores integrados, etc.
• El mayor beneficio del método del código Hamming es efectivo en redes donde los flujos de datos se proporcionan para errores de un solo bit.
• El mayor inconveniente del método del código Hamming es que sólo puede resolver problemas de un solo bit.
• Podemos realizar el proceso de cifrar y decodificar el mensaje con la ayuda del código Hamming.