Técnicas de sincronización / delimitación de protocolos en serie

24

Como la comunicación serial asíncrona se extiende ampliamente entre los dispositivos electrónicos, incluso hoy en día, creo que muchos de nosotros hemos encontrado esa pregunta de vez en cuando. Considere un dispositivo electrónico Dy una computadora PCconectada con una línea serie (RS-232 o similar) y que se requiera para intercambiar información continuamente . Es decir, PCenvía un marco de comando cada uno X msy Dresponde con un informe de estado / marco de telemetría cada uno Y ms(el informe se puede enviar como respuesta a las solicitudes o de forma independiente, realmente no importa aquí). Las tramas de comunicación pueden contener datos binarios arbitrarios . Suponiendo que las tramas de comunicación son paquetes de longitud fija.

El problema:

Como el protocolo es continuo, el lado receptor puede perder la sincronización o simplemente "unirse" en medio de una trama enviada, por lo que simplemente no sabrá dónde está el inicio de la trama (SOF). A los datos tienen un significado diferente en función de su posición en relación con el SOF, los datos recibidos se corromperán, potencialmente para siempre.

La solución requerida

Esquema confiable de delimitación / sincronización para detectar el SOF con un tiempo de recuperación corto (es decir, no debería tomar más de, por ejemplo, 1 cuadro para resincronizar).

Las técnicas existentes que conozco (y uso algunas) de:

1) Encabezado / suma de comprobación : SOF como valor de byte predefinido. Suma de comprobación al final del marco.

  • Pros: simple.
  • Contras: no es confiable. Tiempo de recuperación desconocido.

2) Relleno de bytes:

  • Pros: recuperación confiable y rápida, se puede utilizar con cualquier hardware
  • Contras: no es adecuado para la comunicación basada en tramas de tamaño fijo

3) Marca de noveno bit : anteponga cada byte con bit adicional, mientras que SOF se marca con 1y los bytes de datos se marcan con 0:

  • Pros: recuperación rápida y confiable
  • Contras: Requiere soporte de hardware. No es directamente compatible con la mayoría del PChardware y software.

4) Marca de octavo bit : tipo de emulación de lo anterior, mientras se usa el octavo bit en lugar del noveno, lo que deja solo 7 bits para cada palabra de datos.

  • Pros: recuperación confiable y rápida, se puede utilizar con cualquier hardware.
  • Contras: Requiere un esquema de codificación / decodificación de / a la representación convencional de 8 bits a / de la representación de 7 bits. Un poco despilfarrador.

5) Basado en tiempo de espera : asuma el SOF como el primer byte que viene después de un tiempo inactivo definido.

  • Pros: sin sobrecarga de datos, simple.
  • Contras: no es tan confiable. No funcionará bien con sistemas de sincronización deficientes como, por ejemplo, PC con Windows. Rendimiento potencial sobrecarga.

Pregunta: ¿Cuáles son las otras posibles técnicas / soluciones para abordar el problema? ¿Puede señalar los inconvenientes en la lista anterior que pueden solucionarse fácilmente y eliminarlos? ¿Cómo diseña (o diseñaría) el protocolo de sus sistemas?

Eugene Sh.
fuente
4 es solo 1/8 más derrochador que 3.
Nick Johnson
@NickJohnson De acuerdo, pero solo sugiere que agregue la cosa "Derrochadora" también en (3) :)
Eugene Sh.
No creo que haya explicado completamente sus suposiciones sobre los errores de comunicación. ¿Asume que la comunicación es "perfecta", es decir, sin errores, o "lo suficientemente perfecta" para que el hardware de comunicación detecte e identifique todos los errores (por ejemplo, las comunicaciones utilizan paridad y son solo errores de un solo bit)?
Gbulmer
Beceiver puede unirse en medio de un byte y puede interpretar el bit 8 como el bit 4, por ejemplo. Por lo tanto, el marcado de 9 bits no es confiable.
Timothy Baldwin
@gbulmer La suposición original es que el canal es perfecto y que el problema puede surgir solo debido a la falta de sincronización inicial. Según estos supuestos, la "fiabilidad" a la que me refería está relacionada únicamente con la resincronización. En la lista anterior, todas estas técnicas garantizan el 100% de éxito, excepto la primera. Pero probablemente el esquema de comprobación de errores y el encuadre no se separen de esta manera.
Eugene Sh.

Respuestas:

15

¿Cómo diseña (o diseñaría) el protocolo de sus sistemas?

En mi experiencia, todos pasan mucho más tiempo depurando los sistemas de comunicación de lo que esperaban. Por lo tanto, le sugiero encarecidamente que siempre que necesite elegir un protocolo de comunicación, elija la opción que haga que el sistema sea más fácil de depurar si es posible.

Te animo a jugar con el diseño de algunos protocolos personalizados: es divertido y muy educativo. Sin embargo, también lo aliento a mirar los protocolos preexistentes. Si tuviera que comunicar datos de un lugar a otro, me esforzaría mucho por utilizar algún protocolo preexistente que otra persona ya haya pasado mucho tiempo depurando.

Es muy probable que escribir su propio protocolo de comunicación desde cero contra muchos de los mismos problemas comunes que todos tienen cuando escriben un nuevo protocolo.

Hay una docena de protocolos de sistemas integrados enumerados en los buenos protocolos basados en RS232 para comunicación integrada en la computadora : ¿cuál es el más cercano a sus requisitos?

Incluso si alguna circunstancia imposibilitara el uso exacto de cualquier protocolo preexistente, es más probable que haga que algo funcione más rápidamente comenzando con algún protocolo que casi cumpla con los requisitos y luego ajustándolo.

malas noticias

Como he dicho antes :

Desafortunadamente, es imposible que cualquier protocolo de comunicación tenga todas estas características agradables:

  • transparencia: la comunicación de datos es transparente y está "limpia en 8 bits": (a) cualquier archivo de datos posible puede transmitirse, (b) las secuencias de bytes en el archivo siempre se manejan como datos y nunca se interpretan erróneamente como algo más, y ) el destino recibe el archivo de datos completo sin error, sin adiciones ni eliminaciones.
  • copia simple: la formación de paquetes es más fácil si simplemente copiamos ciegamente los datos de la fuente al campo de datos del paquete sin cambios.
  • inicio único: el símbolo de inicio de paquete es fácil de reconocer, porque es un byte constante conocido que nunca aparece en ningún otro lugar en los encabezados, el encabezado CRC, la carga útil de datos o el CRC de datos.
  • 8 bits: solo utiliza bytes de 8 bits.

Me sorprendería y encantaría si hubiera alguna forma de que un protocolo de comunicación tuviera todas estas características.

buenas noticias

¿Cuáles son las otras técnicas / soluciones posibles que existen para abordar el problema?

A menudo, la depuración es mucho, mucho más fácil si un humano en un terminal de texto puede reemplazar cualquiera de los dispositivos de comunicación. Esto requiere que el protocolo esté diseñado para ser relativamente independiente del tiempo (no se agota el tiempo de espera durante las pausas relativamente largas entre las pulsaciones de teclas escritas por un humano). Además, dichos protocolos están limitados a los tipos de bytes que son fáciles de escribir para un humano y luego leerlos en la pantalla.

Algunos protocolos permiten enviar mensajes en modo "texto" o "binario" (y requieren que todos los mensajes binarios posibles tengan algún mensaje de texto "equivalente" que signifique lo mismo). Esto puede ayudar a que la depuración sea mucho más fácil.

Algunas personas parecen pensar que limitar un protocolo para usar solo los caracteres imprimibles es "un desperdicio", pero los ahorros en tiempo de depuración a menudo hacen que valga la pena.

Como ya mencionó, si permite que el campo de datos contenga algún byte arbitrario, incluidos los bytes de inicio de encabezado y final de encabezado, cuando un receptor se enciende por primera vez, es probable que el receptor se sincronice mal en lo que parece un byte de inicio de encabezado (SOH) en el campo de datos en el medio de un paquete. Por lo general, el receptor obtendrá una suma de comprobación no coincidente al final de ese pseudo-paquete (que generalmente está a la mitad de un segundo paquete real). Es muy tentador simplemente descartar todo el pseudo-mensaje (incluida la primera mitad de ese segundo paquete) antes de buscar el siguiente SOH, con la consecuencia de que el receptor podría estar fuera de sincronización para muchos mensajes.

Como señaló alex.forencich, un enfoque mucho mejor es que el receptor descarte bytes al comienzo del búfer hasta el siguiente SOH. Esto permite que el receptor (después de trabajar posiblemente a través de varios bytes SOH en ese paquete de datos) se sincronice inmediatamente en el segundo paquete.

¿Puede señalar los inconvenientes en la lista anterior que pueden solucionarse fácilmente y eliminarlos?

Como lo señaló Nicholas Clark, el relleno de bytes de sobrecarga constante (COBS) tiene una sobrecarga fija que funciona bien con marcos de tamaño fijo.

Una técnica que a menudo se pasa por alto es un byte marcador de fin de cuadro dedicado. Cuando el receptor se enciende en medio de una transmisión, un byte marcador de fin de cuadro ayuda al receptor a sincronizarse más rápido.

Cuando se enciende un receptor en medio de un paquete, y el campo de datos de un paquete contiene bytes que parecen ser un inicio de paquete (el comienzo de un pseudo-paquete), el transmisor puede insertar una serie de bytes de marcador de fin de trama después de ese paquete, por lo que dichos bytes de pseudo inicio del paquete en el campo de datos no interfieren con la sincronización inmediata y la decodificación correcta del siguiente paquete, incluso cuando tiene mucha mala suerte y la suma de verificación de ese pseudo-paquete parece correcto.

Buena suerte.

davidcary
fuente
Vale la pena reconsiderar esta respuesta aceptada anteriormente (lo siento, @DaveTweed), y el artículo vinculado es sin duda una lectura obligada sobre el tema. Gracias por tomarse el tiempo y escribirlo.
Eugene Sh.
1
es bueno que señales COBS, así que no tengo que escribir una respuesta :-)
Nils Pipenbrinck
11

Los esquemas de relleno de bytes me han funcionado bien a lo largo de los años. Son agradables porque son fáciles de implementar en software o hardware, puede usar un cable USB a UART estándar para enviar paquetes de datos, y tiene la garantía de obtener marcos de buena calidad sin tener que preocuparse por tiempos de espera, intercambio en caliente o cualquier otra cosa como esa.

Yo recomendaría un método de relleno de bytes combinado con un byte de longitud (módulo de longitud de paquete 256) y un CRC a nivel de paquete, y luego usar UART con un bit de paridad. El byte de longitud garantiza la detección de byte descartado, que funciona bien con el bit de paridad (porque la mayoría de los UART eliminarán cualquier byte que falle en la paridad). Luego, el CRC a nivel de paquete le brinda seguridad adicional.

En cuanto a la sobrecarga del relleno de bytes, ¿has mirado el protocolo COBS? Es una forma genial de rellenar bytes con una sobrecarga fija de 1 byte por cada 254 transmitidos (más su encuadre, CRC, LEN, etc.).

https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing

Nicholas Clark
fuente
Esta es una excelente manera de evitar que el relleno de bytes explote en 2 veces los datos en el peor de los casos. He usado esquemas similares pero más específicos de la aplicación, pero es genial ver esto descrito de una manera estándar. Voy a usar COBS a partir de ahora ...
wjl
1
Gracias de mí también por señalar COBS, un pequeño algoritmo muy ordenado.
Nick Johnson
6

Su opción n. ° 1, suma de comprobación SOH plus, ES confiable y se recupera en el siguiente marco sin corrupción.

Supongo que ya conoce la longitud de un mensaje o que la longitud está codificada en el byte (s) inmediatamente después de SOH. Los bytes de verificación aparecen al final del mensaje. También necesita un búfer del lado de recepción para los datos que sea al menos tan largo como su mensaje más largo.

Cada vez que ve un byte SOH en la parte superior del búfer, es potencialmente el comienzo de un mensaje. Examina el búfer para calcular el valor de verificación de ese mensaje y ver si coincide con los bytes de verificación en el búfer. Si es así, ya terminaste; de lo contrario, descarta los datos del búfer hasta llegar al siguiente byte SOH.

Tenga en cuenta que si un mensaje en realidad TIENE errores de datos, este algoritmo lo descartará, pero probablemente lo haría de todos modos. Si su algoritmo de verificación incluye corrección de errores de reenvío, puede verificar cada posible alineación de mensajes para errores corregibles.

Si los mensajes tienen una longitud fija, puede prescindir del byte SOH por completo, solo pruebe CADA posición de inicio posible para obtener un valor de verificación válido.

También puede prescindir del algoritmo de verificación y mantener solo el byte SOH, pero esto hace que el algoritmo sea menos determinista. La idea es que para las alineaciones válidas de mensajes, el SOH siempre aparecerá al comienzo de un mensaje. Si tiene una alineación incorrecta, es poco probable que el siguiente byte en el flujo de datos sea ​​otro SOH (depende de la frecuencia con que aparezca SOH en los datos del mensaje). Puede elegir los bytes SOH válidos solo sobre esta base. (Así es básicamente cómo funciona el encuadre en servicios de telecomunicaciones síncronos como T1 y E1).

Dave Tweed
fuente
¿Supongo que la fiabilidad es algo probabilística? Dependiendo de la fuerza del código de comprobación / corrección de errores que podemos encontrar cuadros que parecen correctas en un flujo de bytes aleatoria / arbitrario.
Eugene Sh.
Claro, eso es posible. Pero en la práctica, es relativamente fácil elegir un algoritmo de verificación que sea lo suficientemente fuerte.
Dave Tweed
Si tiene una tasa de errores de datos distinta de cero, siempre existe la posibilidad de que acepte un mensaje no válido de todos modos.
Nick Johnson
@NickJohnson Suponiendo un canal perfectamente limpio, todavía habrá (teóricamente) desajustes con este enfoque. Por supuesto, su probabilidad puede ser insignificante.
Eugene Sh.
1
Sé que ya lo sabes, y ya lo mencionaste de pasada, pero la versión en la que no almacenas un mensaje completo, o simplemente eres flojo sobre cómo decodificar, es menos confiable. Si vuelve a sincronizar en el siguiente byte SOH después de la suma de comprobación no coincidente, en lugar del siguiente byte SOH después del SOH "falso", tiene una muy buena posibilidad de descartar el inicio del mensaje real y permanecer fuera de sincronización para muchos mensajes o, en el peor de los casos, para siempre.
hobbs
5

Una opción no mencionada pero que se usa ampliamente (especialmente en Internet) es la codificación ASCII / texto (en realidad, la mayoría de las implementaciones modernas suponen UTF-8). En mi experiencia, los expertos en hardware odian hacer esto, pero la gente de software tiende a preferir esto a casi cualquier otra cosa (principalmente por la tradición de Unix de hacer que todo esté basado en texto).

La ventaja de la codificación de texto es que puede usar caracteres no imprimibles para enmarcar. Por ejemplo, lo más simple sería usar algo como 0x00indicar el inicio del cuadro y el 0xfffinal del cuadro.

He visto dos formas principales en que los datos se codifican como texto:

  1. Cuando se le pide a un tipo de hardware / ensamblaje que haga esto, lo más probable es que se implemente como codificación hexadecimal. Esto es simplemente convertir los bytes a sus valores hexadecimales en ASCII. La sobrecarga es grande. Básicamente, transmitirá dos bytes por cada byte de datos real.

  2. Cuando se le pide a un chico de software que haga esto, entonces probablemente se implementará como codificación base64. Esta es la codificación de facto de Internet. Se usa para todo, desde archivos adjuntos MIME de correo electrónico hasta codificación de datos URL. La sobrecarga es exactamente el 33%. Mucho mejor que la simple codificación hexadecimal.

Alternativamente, puede abandonar completamente los datos binarios y transmitir texto. En este caso, la técnica más común es delimitar datos con nueva línea (ya sea solo "\n"o "\r\n"). NMEA (GPS), los comandos Modem AT y los sensores ADventech ADAM son algunos de los ejemplos más comunes de esto.

Todos estos protocolos / marcos basados ​​en texto tienen los siguientes pros y contras:

Pro:

  • Fácil de depurar
  • Fácil de implementar en un lenguaje de script
  • El hardware simplemente se puede probar usando Hyperterminal / minicom
  • Fácil de implementar en el hardware (a menos que sea un micro realmente pequeño como un PIC)
  • Puede ser un marco de tamaño fijo o de tamaño variable.
  • Encuadre predecible y tiempo de recuperación de sincronización rápida (se recupera al final del cuadro actual)

Estafa:

  • Sobrecarga muy grande en comparación con la transmisión binaria pura (de nuevo, la E / S de texto también puede "comprimir" números como enviar un byte "0"(0x30) en lugar de cuatro bytes 0x00000000)
  • No es tan limpio de implementar en micros muy pequeños como el PIC (a menos que su biblioteca incluya una sprintf()función)

Personalmente para mí, los profesionales superan en gran medida a los contras. La facilidad de depuración solo cuenta como 5 puntos (por lo que ese solo punto ya supera los dos inconvenientes).


Luego, existen soluciones no tan cuidadosamente pensadas que a menudo provienen de expertos en software: envíe datos codificados sin pensar en el encuadre.

Tuve que interactuar con hardware que envió XML sin formato en el pasado. El XML fue todo el marco que había. Afortunadamente, es bastante fácil determinar los límites del marco mediante las <xml></xml>etiquetas. La gran desventaja para mí es que usa más de un byte para enmarcar. Además, el encuadre en sí mismo puede no ser reparado ya que la etiqueta puede contener atributos: <tag foo="bar"></tag>por lo tanto, tendría que almacenar en el búfer para el peor de los casos para encontrar el inicio del marco.

Recientemente he visto a personas comenzar a enviar JSON fuera de los puertos seriales. Con JSON, el encuadre es, en el mejor de los casos, una suposición. Solo tiene el carácter "{"(o "[") para detectar el marco, pero también están contenidos en los datos. Así que terminas necesitando un analizador de descenso recursivo (o al menos un contador de llaves) para descubrir el marco. Al menos es trivial saber si el marco actual finaliza prematuramente: "}{"o "]["son ilegales en JSON y, por lo tanto, indican que el marco anterior ha finalizado y que ha comenzado un nuevo marco.

slebetman
fuente
Para las codificaciones de texto, también hay base85 , que solo tiene una sobrecarga del 25% en lugar del 33%.
Dave Tweed
Lo consideraría un subconjunto / variación del 4to método.
Eugene Sh.
@EugeneSh .: Técnicamente es un subconjunto de bytestuffing. Por otra parte, dado que lo considera un subconjunto de marcas de bits, puede comprender por qué esta ambigüedad lo convierte en una categoría por derecho propio. Además, no puede considerar la mayoría de las implementaciones de codificación de texto como un subconjunto de marcado de bits porque los bits de marcado nunca se usan (por ejemplo, generalmente uso <y >como delimitadores y creo que el correo electrónico usa nuevas líneas. Nota: sí, el correo electrónico es un formato correctamente enmarcado eso se puede transmitir a través de RS232. Un amigo mío solía ejecutar un servidor de distribución de correo para su casa usando RS232)
slebetman
4

Lo que usted describe como "marca de bits X" puede generalizarse en otros códigos que tienen la propiedad de expandir los datos en una fracción constante, dejando algunas palabras de código libres para ser utilizadas como delimitadores. A menudo, estos códigos proporcionan otros beneficios también; Los CD usan una modulación de ocho a catorce , lo que garantiza una longitud máxima de ejecución de 0 bits entre cada uno. Otros ejemplos incluyen códigos de bloque de corrección de errores hacia adelante , que también usan bits adicionales para codificar la detección de errores y la información de corrección.

Otro sistema que no ha mencionado es utilizar información fuera de banda, como una línea de selección de chip, para delimitar transacciones o paquetes.

Nick Johnson
fuente
Los códigos de corrección de errores están un poco al margen de la pregunta. Deben agregarse a cualquiera de estos esquemas de todos modos. ¿Supongo que la "información fuera de banda" a la que se refiere es la misma que el "control de flujo de hardware"?
Eugene Sh.
@EugeneSh. - En realidad, el uso de bits de verificación de error para el encuadre es perfectamente válido, aunque computacionalmente costoso en el lado de recepción. Simplemente realiza el cálculo de error para cada posible alineación de datos, y el que tiene éxito es una alineación válida en un marco no dañado. Por supuesto, si el marco está dañado, no lo encontrará.
Dave Tweed
@DaveTweed Bueno, es más o menos lo que quise decir con la primera técnica. ¿O te estoy malentendiendo?
Eugene Sh.
No, no estás malentendido; Eso es de lo que estaba hablando. Sin embargo, su "estafa" está mal: es confiable y también puede hacerse robusto con respecto a los errores de transmisión reales.
Dave Tweed
@DaveTweed ¿Qué pasa con el tiempo de recuperación? ¿Tiene algún ejemplo de cómo puede hacerse robusto?
Eugene Sh.
3

Otra opción es lo que se conoce como codificación de línea . La codificación de línea le da a la señal ciertas características eléctricas que hacen que sea más fácil de transmitir (DC balanceado y garantías de longitud máxima de ejecución) y admiten caracteres de control para la trama y la sincronización del reloj. Los códigos de línea se utilizan en todos los protocolos seriales modernos de alta velocidad: 10M, 100M, 1G y 10G Ethernet, ATA serie, FireWire, USB 3, PCIe, etc. Los códigos de línea comunes son 8b / 10b , 64b / 66b y 128b / 130b. También hay códigos de línea más simples que no proporcionan información de trama, solo balance de CC y sincronización de reloj. Ejemplos de estos son Machester y NRZ. Probablemente desee usar 8b / 10b si desea sincronizar rápidamente; los otros códigos de línea no están diseñados para sincronizarse rápidamente. El uso de un código de línea como el que ofrece lo anterior requerirá el uso de hardware personalizado para transmitir y recibir.

En cuanto a su opción 5, se supone que la serie RS232 estándar admite el envío y la recepción de interrupciones donde la línea está inactiva por un par de veces. Sin embargo, esto puede no ser compatible con todos los sistemas.

En general, el método de encuadre más simple y confiable es su opción 1, en combinación con un campo de longitud y una simple CRC o rutina de suma de verificación. La rutina de decodificación es simple: descarte bytes hasta que obtenga un byte de inicio, lea el campo de longitud, espere la trama completa, verifique la suma de verificación, conserve si está bien. Si la suma de comprobación es incorrecta, comience a descartar bytes del búfer hasta que obtenga un byte de inicio y repita. El problema principal con esta técnica es encontrar un inicio de byte de trama que en realidad no sea un inicio de byte de trama. Para aliviar este problema, una técnica es escapar bytes con el mismo valor que el inicio del byte de trama con otro carácter de control, y luego cambiar el byte escapado para que tenga un valor diferente. En este caso, también tendrá que hacer lo mismo con el nuevo byte de control.

alex.forencich
fuente
Esto es lo mismo que la respuesta de Nick Johnson.
Dave Tweed