Determinar las constantes de comando para el diseño de protocolo en serie

La palabra es Distancia de Hamming , que es el número de símbolos diferentes entre los dos códigos. 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, menos corregidos.

Ahora toma el cubo de Hamming:

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

Hace mucho tiempo, vi un programa de BBC Open University sobre codificación en el que explicaban cómo una Matriz de Hadamard proporciona una lista de códigos con una Distancia de Hamming de n para un 2 \ $ ^ n \ $ \ $ \ veces \ $ 2 \ $ ^ n \ $ matriz. La construcción de una matriz de Hadamard es interesante en sí misma, y es un buen ejercicio de programación. Comience con un solo bit:

1

ahora crea una matriz de 2 por 2 bits, siguiendo esta regla: copie el 1 en todos los cuadrantes, excepto la parte inferior derecha, donde coloca el inverso:

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, usted copia la matriz anterior, excepto la esquina inferior derecha donde la invierte:

1 1   1 1
1 0   1 0

1 1   0 0
1 0   0 1 

Y así sucesivamente. 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

Puedes extender la Matriz de Hadamard tanto como quieras. Si desea detectar errores de hasta 6 bits, tendrá una matriz de 64 por 64. Este tipo de codificación de error directo se usa, por ejemplo, en la comunicación espacial, donde la distancia de la nave 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 una longitud de código larga, permite la detección de una señal debajo del piso de ruido.

Primero debe decidir contra qué está tratando de protegerse y qué quiere que haga el sistema en caso de un error de transmisión. También debe considerar la posibilidad de que se dañen los 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 el mismo tablero. 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 causaría otros problemas o quedaría tan fuera de especificaciones que no sería razonable protegerse. Por ejemplo, alguien arrastrando los pies por la alfombra y luego golpeando a cualquier conductor expuesto en la placa abierta con 10 kV de electricidad estática causará todo tipo de fallas, pero eso también es un abuso que está fuera de especificaciones.

Si cree que la comunicación en serie tendrá una tasa de error de bits lo suficientemente pequeña pero significativa que no puede ignorar, el esquema habitual es enviar datos en paquetes con sumas de comprobación. El receptor ignora cualquier paquete con suma de comprobación no válida. Una suma de comprobación diseñada correctamente utilizará menos bits y, por lo tanto, tendrá menos sobrecarga que un enfoque torpe como limitar el espacio del código de operación de modo que no haya dos códigos de operación separados 1 bit uno del otro. Piénselo, y verá que básicamente está enviando un código de operación más pequeño con los bits adicionales como una suma de comprobación de bajo rendimiento. Solo puede detectar errores de un solo 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 solo error de bit en un paquete completo es baja, por lo que cubrir todo el paquete con una suma de comprobación usa menos bits por bit de datos verificados y cubre todos los bits enviados.

Si es lo suficientemente bueno como para simplemente descartar los comandos incorrectos, entonces puedes detenerte 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 (envuelto adecuadamente en un paquete de suma de comprobación, por supuesto), y el transmisor no envía nada nuevo hasta que se recibe el ACK. Si el ACK no se recibe después de un tiempo de espera, entonces el transmisor envía el último paquete nuevamente. Protocolos más complicados permiten al transmisor adelantarse 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 se vuelven muy elegantes. TCP, por ejemplo, hace esto con un flujo de bytes arbitrario. No hay límites de paquetes, ya que se supone que los paquetes de red se pueden dividir o combinar entre el transmisor y el receptor.

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