communication - pasos - ¿Cómo funciona el código de Hamming?

pasos codigo hamming (6)

Al transmitir datos, el código de Hamming aparentemente le permite recrear los datos que se han dañado a través del cable (un código de corrección de errores).

¿Cómo funciona esto y cuáles son sus limitaciones, si las hay?

¿Hay alguna solución mejor para la corrección de errores (a diferencia de la retransmisión)? ¿Hay circunstancias en las que la retransmisión es mejor?

Aquí está la descripción general de alto nivel.

Suppose that every time I send a message, I send thrie copies of the text. Suppose that every time I send z message, I send three copies of the teyt. Suppose that every tyme I send a message, I send three copies if the tezt.

Al comparar personajes y obtener un voto de mayoría simple en cada posición, puede corregir los caracteres erróneos individuales. Sin embargo, el costo de este esquema (cantidad de datos que deben enviarse) es alto y no detecta el caso poco probable pero posible de dos errores en las posiciones correspondientes de copias diferentes (como en la última palabra del ejemplo anterior). )

Los códigos Hamming (y otros tipos de códigos de corrección de errores, como Reed-Solomon) se basan en fórmulas que calculan los datos adicionales (en lugar de la simple duplicación). Los bits añadidos dependen de las combinaciones de los bits de datos de forma que los errores en la copia crean patrones de cambios detectables cuando el cálculo se repite en el extremo receptor.

En aras de la ilustración, comencemos con la paridad impar simple, agregando un solo bit para asegurar que la cantidad total de bits en un mensaje sea impar. Entonces, el mensaje 10110110 convierte en 101101100 (cinco 1s, no se necesita 1 adicional) y el mensaje 10010110 convierte en 100101101 (cuatro 1s, se necesita 1 adicional). Si recibe un mensaje de 101101101 y ve que hay seis 1s, sabe que hay un error, pero no sabe dónde. Supongamos que agregamos más bits de paridad, cada uno dependiendo solo de una parte del mensaje, como se ilustra a continuación, copiando los bits considerados y usando ''-'' para los bits ignorados:

10110110 1-1-0-1- => 0 -0-1-1-0 => 1 10--01-- => 1 --11--10 => 0 1011---- => 0 ----0110 => 1

entonces el mensaje completo es 10110110011001 . Ahora suponga que un error de transmisión cambia el tercer bit en el mensaje, por lo que lee 10010110011001 . Cuando el receptor vuelve a ejecutar el cálculo de comprobación de errores, no coincide:

10010110 1-0-0-1- => 1* -0-1-1-0 => 1 10--01-- => 1 --01--10 => 1* 1001---- => 1* ----0110 => 1

y los bits de verificación que no coinciden son exactamente los afectados por el tercer bit de datos. Este no es un esquema real y robusto de corrección de errores; es solo un boceto para ilustrar cómo construir en redundancia puede ayudar a identificar la naturaleza exacta de un error.

El código Hamming es un truco matemático para corregir hasta 4 bits perdidos en una transmisión en serie. También se usa a favor del "bit de paridad" en los chips de memoria modernos.

Las limitaciones están en el número de bits que se pueden restaurar, que no es más que 4. Si se pierden más de 4 bits, se requiere la retransmisión.

Diferentes situaciones requieren diferentes técnicas de corrección de errores. Algunas de estas técnicas se enumeran en las otras publicaciones aquí.

Encontrará detalles sobre la forma en que funciona aquí

Aquí encontrará más información general sobre códigos de error de coreografía

La información sobre el código de Hamming está disponible aquí y aquí .

En cuanto a la idoneidad, esto explica por qué:

Los códigos de corrección de errores como Hamming son adecuados para canales simples donde no se puede solicitar la retransmisión.
La detección de errores más la retransmisión a menudo se prefiere porque es más eficiente.

Para la comparación, considere un canal con tasa de error de por bit. Deje que el tamaño del bloque sea 1000 bits.

Para corregir un solo error (por código Hamming), se necesitan 10 bits de verificación por bloque. Para transmitir 1000 bloques, se requieren 10.000 bits de verificación (sobrecarga). Para detectar un solo error, un solo bit de paridad por bloque será suficiente. Para transmitir 1000 bloques, solo se tendrá que retransmitir un bloque externo (debido a la tasa de error de cada bit), lo que da una sobrecarga de solo 2001 (= 1000 + 1001) bits.

Tratemos de explicarlo un poco:

Tenemos un número de 3 bits. Las posibilidades se pueden presentar como un cubo donde cada bit representa un eje. Las ocho posibilidades están en las esquinas.

000 --------001 | / | / | 100---------101 | | | | | | | | 010-|-------011 | /| /| 110---------111

Cada defecto (por ejemplo, 101 se lee como 100) da como resultado un desplazamiento en una línea del cubo.

Si usamos dos bits para los datos y el tercero para una verificación de paridad (por ejemplo, paridad par). Perdemos 4 puntos de datos. Pero tiene la ventaja de que podemos detectar una falla de un solo bit (que transforma un conteo par de 1 en un recuento impar de unos). Los números impares están marcados con un *. Y vemos que cada palabra extraña (transmitida erróneamente) está acorralada por palabras pares (transmitidas por derecho). Entonces, si recibimos 100, podemos estar seguros de que está mal.

Pero (con una falla de un solo bit) la representación correcta podría haber sido 000, 101 o 110. Así que podemos detectar que algo ha estado mal pero no podemos detectar lo que estaba mal:

000 -------*001 | / | / |*100---------101 | | | | | | | | *010-|-------011 | /| /| 110--------*111

Esto se llama código de detección de error de un bit.

Si utilizamos otro bit para verificarlo, eliminamos uno para los datos. Nos quedan 1 bit de datos y 2 "bits de verificación". En este caso, supongamos que 000 y 111 son representaciones de datos válidas y las otras seis no. Ahora tenemos una situación interesante si un bit se destroza durante el transporte. Si enviamos 000 y recibimos 010, vemos que 010 tiene un vecino válido (000) y dos inválidos (110 y 011). Entonces, ahora sabemos que tenemos la intención de enviar 000 y podemos corregir eso:

000 -------*001 | / | / |*100--------*101 | | | | | | | | *010-|------*011 | /| /| *110---------111

Esto se llama código de corrección de errores de un bit.

Tenga en cuenta que un código de corrección de errores de un bit también es un código de detección de errores de dos bits.

Y para decirlo de manera más general.

Si tiene n bits de verificación, tiene un código de detección de error de bit. Si tiene 2n bits de verificación, tiene un código de corrección de error de bit.

Por supuesto, debe solicitar los códigos "válidos" para que no se encuentren entre ellos.

@GameCat y qué pasa con el código de detección de errores de 2 bits.

En este caso, digamos que 111 ha cambiado a 100. Entonces podemos estar seguros de que hay 2 bits erróneos y lo sabemos porque la distancia entre 111 y 100 es de 2 bits, y la distancia de 000 y 100 es de 1 bit. Entonces, si sabemos que hay un error de 2 bits, podemos estar seguros de cuál es el valor correcto.