Determinación de constantes de comando para el diseño de protocolos en serie

La palabra es Distancia de Hamming , que es el número de símbolos diferentes entre dos códigos cualesquiera. Si usara cualquier combinación posible de un código de 8 bits, su distancia de Hamming es 1: un cambio de solo 1 bit le dará un nuevo código válido. Eso significa que incluso los errores de 1 bit no se pueden detectar y menos corregir.

Ahora toma el cubo de Hamming:

Aquí solo hay 2 códigos válidos de 3 bits: 000y 111. La distancia de Hamming es 3, lo que significa que se pueden detectar menos de 3 bits de error. Los errores de un solo bit pueden incluso corregirse: si el código debe ser 000y usted tiene 001, eso es un solo bit. Si mide la distancia en el cubo a los dos códigos válidos, tendrá que seguir 2 aristas para llegar a 111, pero solo 1 arista para 000. Entonces, es un error de un solo bit, y luego puede corregirlo, o un error de varios bits, que puede detectar (porque no es un código válido) pero no corregir (no sabe si debería ser 000o 111).

Hace mucho tiempo, vi un programa de la Universidad Abierta de la BBC sobre codificación donde explicaban cómo una matriz de Hadamard proporciona una lista de códigos con una distancia de Hamming de n para un 2$^n$ $\times$2$^n$matriz. La construcción de una matriz de Hadamard es interesante en sí misma y un buen ejercicio de programación. Comience con un solo bit:

1

ahora haces una matriz de 2 por 2 bits, siguiendo esta regla: copia 1en todos los cuadrantes, excepto en el inferior derecho, donde colocas la inversa:

1 1
1 0

El siguiente nivel (este es un algoritmo recursivo) aplica la misma regla a la matriz de 2 por 2, de modo que obtiene una matriz de 4 por 4. En cada cuadrante copias la matriz anterior, excepto en el inferior derecho donde la inviertes:

1 1   1 1
1 0   1 0

1 1   0 0
1 0   0 1 

Etcétera. En el siguiente nivel tendremos 8 códigos (líneas) con una Distancia de Hamming de 3:

1 1 1 1   1 1 1 1
1 0 1 0   1 0 1 0
1 1 0 0   1 1 0 0
1 0 0 1   1 0 0 1

1 1 1 1   0 0 0 0
1 0 1 0   0 1 0 1
1 1 0 0   0 0 1 1
1 0 0 1   0 1 1 0

Puede extender Hadamard Matrix tanto como desee. Si desea detectar errores de hasta 6 bits, tendrá una matriz de 64 por 64. Este tipo de codificación de errores hacia adelante se utiliza, por ejemplo, en comunicaciones espaciales, donde la distancia de la nave espacial puede ser tan grande que la señal se vuelve extremadamente ruidosa. El hecho de que solo haya un número limitado de códigos válidos, a pesar de su gran longitud, permite la detección de una señal por debajo del umbral de ruido.

Primero debe decidir contra qué está tratando de protegerse y qué quiere que haga el sistema en caso de error de transmisión. También debe considerar la posibilidad de corrupción de datos y cuáles son los costos si los datos incorrectos se interpretan como datos válidos.

Para la comunicación a bordo, generalmente ignora todo el problema. Es probable que ya esté haciendo muchas suposiciones de que la salida de un chip digital aparecerá correctamente en la entrada de otros en la misma placa. La comunicación en serie entre dos dispositivos en la misma placa no es diferente. El tipo de perturbación que causaría un error en la señalización cableada directa a bordo probablemente también causaría otros problemas o estaría tan fuera de las especificaciones que no es razonable protegerse. Por ejemplo, alguien que arrastra los pies sobre una alfombra y luego aplica 10 kV de electricidad estática a cualquier conductor expuesto en el tablero abierto causará todo tipo de fallas, pero eso también es un abuso que está fuera de las especificaciones.

Si cree que la comunicación en serie tendrá una tasa de error de bits pequeña pero lo suficientemente significativa como para que no pueda ignorarla, entonces el esquema habitual es enviar datos en paquetes con sumas de verificación. El receptor ignora cualquier paquete con suma de verificación no válida. Una suma de verificación diseñada correctamente utilizará menos bits y, por lo tanto, tendrá menos gastos generales que un enfoque torpe como limitar el espacio del código de operación para que no haya dos códigos de operación separados por 1 bit entre sí. Piénselo y verá que básicamente está enviando un código de operación más pequeño y los bits adicionales son una suma de verificación de bajo rendimiento. Solo puede detectar errores de un bit en el código de operación, no puede corregirlo y no ayuda al resto del mensaje. Si la tasa de error de bits es baja, la posibilidad de un error de un solo bit en un paquete completo es baja.

Si es lo suficientemente bueno como para simplemente descartar los comandos incorrectos, entonces puede detenerse allí. Si necesita saber que un comando se recibió correctamente, debe usar algún tipo de esquema de comunicación bidireccional. La forma más simple es que el receptor envía un ACK (adecuadamente envuelto en un paquete de suma de verificación, por supuesto), y el transmisor no envía nada nuevo hasta que se recibe el ACK. Si no se recibe el ACK después de un tiempo de espera, el transmisor envía el último paquete nuevamente. Los protocolos más complicados permiten que el transmisor se adelante al receptor, por lo que generalmente hay un número de secuencia o similar codificado en cada paquete. Hay muchas maneras, y algunas de ellas son bastante elegantes. TCP, por ejemplo, hace esto con un flujo de bytes arbitrario.

Intentaría alguna forma de corrección de errores hacia adelante en cada comando. Si sabemos cuántos comandos distintos necesitamos, entonces podemos elegir un código existente (Hamming, Reed-Solomon, etc.) y usar la forma más redundante que aún quepa en un byte. Una ventaja es que existen algoritmos establecidos para ayudarlo a decodificar los bytes corruptos.