Techniques de délimitation / synchronisation de protocole série

24

Comme la communication série asynchrone est largement répandue parmi les appareils électroniques, même de nos jours, je pense que beaucoup d'entre nous ont rencontré une telle question de temps en temps. Considérez un appareil électronique Det un ordinateur PCconnecté à une ligne série (RS-232 ou similaire) et requis pour échanger des informations en continu . C'est-à-dire qu'il PCenvoie un cadre de commande chacun X mset Drépond avec un rapport d'état / un cadre de télémétrie chacun Y ms(le rapport peut être envoyé en réponse à des demandes ou indépendamment - peu importe ici). Les trames de communication peuvent contenir toutes les données binaires arbitraires . En supposant que les trames de communication sont des paquets de longueur fixe.

Le problème:

Comme le protocole est continu, le côté récepteur peut perdre la synchronisation ou simplement «se joindre» au milieu d'une trame envoyée en cours, il ne saura donc pas où se trouve le début de la trame (SOF). Si les données ont une signification différente en fonction de leur position par rapport au SOF, les données reçues seront corrompues, potentiellement pour toujours.

La solution recherchée

Schéma de délimitation / synchronisation fiable pour détecter le SOF avec un temps de récupération court (c'est-à-dire qu'il ne faut pas plus de, disons 1 trame pour se resynchroniser).

Les techniques existantes que je connais (et en utilise):

1) En-tête / somme de contrôle - SOF comme valeur d'octet prédéfinie. Somme de contrôle à la fin du cadre.

  • Avantages: Simple.
  • Inconvénients: pas fiable. Temps de récupération inconnu.

2) Remplissage d'octets:

  • Avantages: récupération fiable et rapide, peut être utilisée avec n'importe quel matériel
  • Inconvénients: pas adapté à la communication basée sur une trame de taille fixe

3) Marquage du 9e bit - ajoutez chaque octet au bit supplémentaire, tandis que SOF marqué avec 1et les octets de données sont marqués avec 0:

  • Avantages: récupération fiable et rapide
  • Inconvénients: nécessite un support matériel. Non directement pris en charge par la plupart du PCmatériel et des logiciels.

4) Marquage du 8e bit - sorte d'émulation de ce qui précède, tout en utilisant le 8e bit au lieu du 9e, ce qui ne laisse que 7 bits pour chaque mot de données.

  • Avantages: Récupération fiable et rapide, peut être utilisée avec n'importe quel matériel.
  • Inconvénients: nécessite un schéma de codage / décodage de / vers la représentation conventionnelle 8 bits vers / depuis la représentation 7 bits. Un peu de gaspillage.

5) Timeout based - supposez le SOF comme le premier octet après un certain temps d'inactivité défini.

  • Avantages: Pas de surcharge de données, simple.
  • Inconvénients: pas si fiable. Ne fonctionnera pas bien avec des systèmes de synchronisation médiocres comme, par exemple, un PC Windows. Surdébit potentiel de débit.

Question: Quelles sont les autres techniques / solutions possibles pour résoudre le problème? Pouvez-vous indiquer les inconvénients dans la liste ci-dessus qui peuvent être facilement contournés, les supprimant ainsi? Comment concevez-vous (ou voulez-vous) concevoir votre protocole système?

Eugene Sh.
la source
4 n'est que 1/8 de plus de gaspillage que 3.
Nick Johnson
@NickJohnson D'accord, mais cela ne fait que suggérer que j'ajoute la chose "Gaspillage" dans (3) aussi :)
Eugene Sh.
Je ne pense pas que vous ayez expliqué en détail vos hypothèses sur les erreurs de communication. Supposez-vous que la communication est «parfaite», c'est-à-dire sans erreur, ou «suffisamment parfaite» pour que toutes les erreurs soient détectées et identifiées par le matériel de communication (par exemple, les communications utilisent la parité, et ce ne sont que des erreurs à un seul bit)?
gbulmer
Beceiver peut se joindre au milieu d'un octet et peut interpréter le bit 8 comme le bit 4 par exemple. Le marquage au 9ème bit n'est donc pas fiable.
Timothy Baldwin du
@gbulmer L'hypothèse d'origine est que le canal est parfait et que le problème ne peut survenir qu'en raison d'une mauvaise synchronisation initiale. Dans ces hypothèses, la «fiabilité» à laquelle je faisais référence est liée à la resynchronisation uniquement. Dans la liste ci-dessus, toutes ces techniques garantissent un succès à 100%, sauf la première. Mais le schéma de vérification des erreurs et le cadrage ne devraient probablement pas être séparés comme ceci.
Eugene Sh.

Réponses:

15

Comment concevez-vous (ou voulez-vous) concevoir votre protocole système?

D'après mon expérience, tout le monde passe beaucoup plus de temps à déboguer des systèmes de communication que ce à quoi ils s'attendaient. Et donc je suggère fortement que chaque fois que vous devez faire un choix pour un protocole de communication, vous choisissez l'option qui rend le système plus facile à déboguer si possible.

Je vous encourage à jouer avec la conception de quelques protocoles personnalisés - c'est amusant et très éducatif. Cependant, je vous encourage également à regarder les protocoles préexistants. Si j'avais besoin de communiquer des données d'un endroit à un autre, j'essaierais très fort d'utiliser un protocole préexistant que quelqu'un d'autre a déjà passé beaucoup de temps à déboguer.

L'écriture de votre propre protocole de communication à partir de zéro est très susceptible de se heurter à bon nombre des mêmes problèmes courants que tout le monde a lorsqu'ils écrivent un nouveau protocole.

Il existe une douzaine de protocoles de systèmes intégrés répertoriés dans les bons protocoles basés sur RS232 pour les communications intégrées à l'ordinateur - lequel est le plus proche de vos besoins?

Même si certaines circonstances ont rendu impossible l'utilisation d'un protocole préexistant exactement, je suis plus susceptible de faire fonctionner quelque chose plus rapidement en commençant par un protocole qui correspond presque aux exigences, puis en le peaufinant.

mauvaises nouvelles

Comme je l'ai déjà dit :

Malheureusement, il est impossible pour un protocole de communication d'avoir toutes ces fonctionnalités intéressantes:

  • transparence: la communication des données est transparente et "8 bits propre" - (a) tout fichier de données possible peut être transmis, (b) les séquences d'octets dans le fichier sont toujours traitées comme des données, et jamais mal interprétées comme autre chose, et (c ), la destination reçoit l'intégralité du fichier de données sans erreur, sans ajout ni suppression.
  • copie simple: la formation de paquets est plus facile si nous copions simplement à l'aveugle des données de la source vers le champ de données du paquet sans changement.
  • début unique: le symbole de début de paquet est facile à reconnaître, car il s'agit d'un octet constant connu qui ne se produit jamais ailleurs dans les en-têtes, le CRC d'en-tête, la charge utile de données ou le CRC de données.
  • 8 bits: utilise uniquement des octets 8 bits.

Je serais surpris et ravi s'il existait un moyen pour un protocole de communication d'avoir toutes ces fonctionnalités.

bonnes nouvelles

Quelles sont les autres techniques / solutions possibles pour résoudre le problème?

Souvent, cela rend le débogage beaucoup, beaucoup plus facile si un humain sur un terminal de texte peut remplacer l'un des périphériques communicants. Cela nécessite que le protocole soit conçu pour être relativement indépendant du temps (il n'expire pas pendant les pauses relativement longues entre les frappes tapées par un humain). En outre, ces protocoles sont limités aux types d'octets faciles à saisir et à lire à l'écran par un humain.

Certains protocoles permettent d'envoyer des messages en mode "texte" ou "binaire" (et exigent que tous les messages binaires possibles aient un message texte "équivalent" qui signifie la même chose). Cela peut faciliter le débogage.

Certaines personnes semblent penser que limiter un protocole pour n'utiliser que les caractères imprimables est «inutile», mais les économies de temps de débogage en valent souvent la peine.

Comme vous l'avez déjà mentionné, si vous autorisez le champ de données à contenir tout octet arbitraire, y compris les octets de début et de fin d'en-tête, lorsqu'un récepteur est allumé pour la première fois, il est probable que le récepteur se synchronise mal sur ce qui ressemble à un octet de début d'en-tête (SOH) dans le champ de données au milieu d'un paquet. Habituellement, le récepteur recevra une somme de contrôle non appariée à la fin de ce pseudo-paquet (qui est généralement à mi-chemin d'un deuxième vrai paquet). Il est très tentant de simplement supprimer l'intégralité du pseudo-message (y compris la première moitié de ce deuxième paquet) avant de rechercher le prochain SOH - avec pour conséquence que le récepteur pourrait rester hors de synchronisation pour de nombreux messages.

Comme l'a fait remarquer alex.forencich, une bien meilleure approche consiste à ce que le récepteur rejette les octets au début du tampon jusqu'au prochain SOH. Cela permet au récepteur (après avoir éventuellement travaillé sur plusieurs octets SOH dans ce paquet de données) de se synchroniser immédiatement sur le deuxième paquet.

Pouvez-vous indiquer les inconvénients dans la liste ci-dessus qui peuvent être facilement contournés, les supprimant ainsi?

Comme l'a souligné Nicholas Clark, le bourrage d'octets de surcharge cohérente (COBS) a une surcharge fixe qui fonctionne bien avec des trames de taille fixe.

Une technique qui est souvent négligée est un octet de marqueur de fin de trame dédié. Lorsque le récepteur est mis sous tension au milieu d'une transmission, un octet de marqueur de fin de trame dédié aide le récepteur à se synchroniser plus rapidement.

Lorsqu'un récepteur est activé au milieu d'un paquet, et que le champ de données d'un paquet contient des octets qui semblent être un début de paquet (le début d'un pseudo-paquet), l'émetteur peut insérer une série d'octets de marqueur de fin de trame après ce paquet afin que de tels octets de pseudo-début de paquet dans le champ de données n'interfèrent pas avec la synchronisation immédiate et le décodage correct du paquet suivant - même lorsque vous êtes extrêmement malchanceux et que la somme de contrôle de ce pseudo-paquet semble correct.

Bonne chance.

davidcary
la source
Cette réponse vaut la peine de reconsidérer la réponse précédemment acceptée (désolé, @DaveTweed), et l'article lié est certainement un sujet de discussion sur le sujet. Merci d'avoir pris le temps de l'écrire.
Eugene Sh.
1
Ravi que vous signaliez COBS, donc je n'ai pas à écrire de réponse :-)
Nils Pipenbrinck
11

Les programmes de bourrage d'octets ont très bien fonctionné pour moi au fil des ans. Ils sont agréables car ils sont faciles à implémenter dans le logiciel ou dans le matériel, vous pouvez utiliser un câble USB vers UART standard pour envoyer des paquets de données, et vous êtes assuré d'obtenir un cadrage de bonne qualité sans avoir à vous soucier de dépassements de délai, remplacement à chaud ou autre chose du genre.

Je préconiserais une méthode de bourrage d'octets combinée avec un octet de longueur (modulo 256 de longueur de paquet) et un CRC au niveau des paquets, puis j'utiliserais UART avec un bit de parité. L'octet de longueur garantit la détection des octets supprimés, ce qui fonctionne bien avec le bit de parité (car la plupart des UART suppriment tous les octets qui échouent à la parité). Ensuite, le CRC au niveau des paquets vous offre une sécurité supplémentaire.

En ce qui concerne les frais généraux du bourrage d'octets, avez-vous examiné le protocole COBS? C'est une façon géniale de faire du bourrage d'octets avec un surdébit fixe de 1 octet pour chaque 254 transmis (plus votre cadrage, CRC, LEN, etc.).

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

Nicholas Clark
la source
C'est un excellent moyen d'éviter que le bourrage d'octets n'explose dans 2x les données dans le pire des cas. J'ai utilisé des schémas similaires mais plus spécifiques à l'application, mais c'est formidable de voir cela décrit de manière standard. Je vais utiliser COBS à partir de maintenant ...
wjl
1
Merci aussi de moi d'avoir signalé COBS - un petit algorithme très soigné.
Nick Johnson
6

Votre option n ° 1, SOH plus la somme de contrôle, est fiable et récupère sur la trame suivante non corrompue.

Je suppose que vous connaissez déjà la longueur d'un message ou que la longueur est codée dans les octets immédiatement après SOH. Les octets de contrôle apparaissent à la fin du message. Vous avez également besoin d'un tampon côté réception pour les données qui est au moins aussi long que votre message le plus long.

Chaque fois que vous voyez un octet SOH en tête du tampon, c'est potentiellement le début d'un message. Vous parcourez le tampon pour calculer la valeur de contrôle de ce message et voyez s'il correspond aux octets de contrôle dans le tampon. Si oui, vous avez terminé; sinon, vous supprimez les données du tampon jusqu'à ce que vous arriviez au prochain octet SOH.

Notez que si un message contient réellement des erreurs de données, cet algorithme le supprimera - mais vous alliez probablement le faire de toute façon. Si votre algorithme de vérification inclut une correction d'erreur directe, vous pouvez vérifier chaque alignement de message potentiel pour les erreurs corrigibles.

Si les messages sont de longueur fixe, vous pouvez vous passer de l'octet SOH - testez CHAQUE position de départ possible pour une valeur de contrôle valide.

Vous pouvez également vous dispenser de l'algorithme de vérification et conserver uniquement l'octet SOH, mais cela rend l'algorithme moins déterministe. L'idée est que pour les alignements de messages valides, le SOH apparaîtra toujours au début d'un message. Si vous avez un alignement incorrect, l'octet suivant dans le flux de données est peu susceptible d'être un autre SOH (dépend de la fréquence à laquelle SOH apparaît dans les données du message). Vous pouvez sélectionner les octets SOH valides sur cette seule base. (C'est essentiellement ainsi que fonctionne le cadrage sur les services de télécommunications synchrones comme T1 et E1.)

Dave Tweed
la source
Je suppose que la fiabilité est quelque peu probabiliste? En fonction de la force de la vérification des erreurs / code de correction que nous pouvons rencontrer des images qui semblent correctes dans un flux d'octets aléatoire / arbitraire.
Eugene Sh.
Bien sûr, c'est possible. Mais en pratique, il est relativement facile de choisir un algorithme de vérification suffisamment puissant.
Dave Tweed
Si vous avez un taux d'erreurs de données différent de zéro, il y a toujours une chance que vous acceptiez un message non valide de toute façon.
Nick Johnson
@NickJohnson En supposant un canal parfaitement propre, il y aura toujours (théoriquement) des décalages avec cette approche. Bien sûr, leur probabilité peut être négligeable.
Eugene Sh.
1
Je sais que vous le savez déjà et que vous l'avez déjà mentionné en passant, mais la version où vous ne mettez pas en tampon un message entier, ou êtes simplement paresseux sur la façon de décoder, est moins fiable. Si vous resynchronisez au prochain octet SOH après la somme de contrôle non appariée, au lieu du prochain octet SOH après le "faux" SOH, vous avez une très bonne chance de rejeter le début réel du message et de rester hors de synchronisation pour de nombreux messages ou, dans le pire des cas, pour toujours.
hobbs
5

Une option non mentionnée mais largement utilisée (en particulier sur Internet) est le codage ASCII / texte (en fait, la plupart des implémentations modernes supposent UTF-8). D'après mon expérience, les gars du matériel détestent faire cela, mais les gens du logiciel ont tendance à préférer cela à presque tout le reste (cela vient principalement de la tradition Unix de faire tout ce qui est basé sur du texte).

L'avantage de l'encodage de texte est que vous pouvez utiliser des caractères non imprimables pour le cadrage. Par exemple, le plus simple serait d'utiliser quelque chose comme 0x00pour indiquer le début de la trame et 0xffpour la fin de la trame.

J'ai vu deux façons principales de coder les données sous forme de texte:

  1. Lorsqu'un type de matériel / assemblage est invité à le faire, il sera très probablement implémenté en tant que codage hexadécimal. Il s'agit simplement de convertir les octets en leurs valeurs hexadécimales en ASCII. Les frais généraux sont importants. Fondamentalement, vous transmettez deux octets pour chaque octet de données réel.

  2. Lorsqu'un logiciel est invité à le faire, il sera probablement implémenté en tant qu'encodage base64. Il s'agit de l'encodage de facto d'Internet. Utilisé pour tout, des pièces jointes MIME par e-mail au codage des données URL. Les frais généraux sont exactement de 33%. Beaucoup mieux qu'un simple encodage hexadécimal.

Alternativement, vous pouvez complètement abandonner les données binaires et transmettre du texte. Dans ce cas, la technique la plus courante consiste à délimiter les données avec une nouvelle ligne (juste "\n"ou "\r\n"). Les commandes NMEA (GPS), Modem AT et les capteurs Adventech ADAM sont quelques-uns des exemples les plus courants.

Tous ces protocoles / cadres textuels présentent les avantages et les inconvénients suivants:

Pro:

  • Facile à déboguer
  • Facile à implémenter dans un langage de script
  • Le matériel peut simplement être testé en utilisant Hyperterminal / minicom
  • Facile à implémenter sur le matériel (sauf s'il s'agit d'un très petit micro comme un PIC)
  • Peut être un cadre de taille fixe ou une taille variable.
  • Cadrage prévisible et temps de récupération de synchronisation rapide (récupère à la fin de la trame actuelle)

Con:

  • Très grande surcharge par rapport à la transmission binaire pure (là encore, les E / S texte peuvent également "compresser" des nombres comme l'envoi d'un octet "0"(0x30) au lieu de quatre octets 0x00000000)
  • Pas si propre à implémenter sur de très petits micros comme le PIC (sauf si votre bibliothèque inclut une sprintf()fonction)

Personnellement, les avantages l'emportent largement sur les inconvénients. La facilité de débogage seule compte pour 5 points (de sorte qu'un seul point l'emporte déjà sur les deux inconvénients).


Ensuite, il y a des solutions pas si soigneusement pensées qui viennent souvent des logiciels: envoyez des données encodées sans penser au cadrage.

J'ai dû interfacer avec du matériel qui a envoyé du XML brut dans le passé. Le XML était tout le cadrage. Heureusement, il est assez facile de déterminer les limites du cadre par les <xml></xml>balises. Le gros inconvénient pour moi, c'est qu'il utilise plus d'un octet pour le cadrage. En outre, le cadrage lui-même peut ne pas être fixé car la balise peut contenir des attributs: <tag foo="bar"></tag>vous devrez donc mettre en mémoire tampon pour le pire des cas pour trouver le début de la trame.

Récemment, j'ai vu des gens commencer à envoyer du JSON hors des ports série. Avec le cadrage JSON, c'est au mieux une supposition. Vous ne disposez que du caractère "{"(ou "[") pour détecter la trame mais ils sont également contenus dans les données. Vous finissez donc par avoir besoin d'un analyseur de descente récursif (ou au moins un compteur d'accolades) pour comprendre le cadre. Au moins, il est trivial de savoir si la trame actuelle se termine prématurément: "}{"ou "]["sont illégales dans JSON et indiquent donc que l'ancienne trame est terminée et qu'une nouvelle trame a commencé.

Slebetman
la source
Pour les encodages de texte, il y a aussi la base85 , qui n'a que 25% de surcharge au lieu de 33%.
Dave Tweed
Je le considérerais comme un sous-ensemble / variation de la 4ème méthode.
Eugene Sh.
@EugeneSh.: Techniquement, il s'agit d'un sous-ensemble de bourrage secondaire. Ensuite, puisque vous le considérez comme un sous-ensemble de marquage de bits, vous pouvez comprendre pourquoi cette ambiguïté en fait une catégorie à part entière. De plus, vous ne pouvez pas considérer la plupart des implémentations de l'encodage de texte comme un sous-ensemble de marquage de bits car les bits de marquage ne sont jamais utilisés (par exemple, j'utilise habituellement <et >comme délimiteurs et je pense que le courrier électronique utilise des sauts de ligne. Remarque: oui, le courrier électronique est un format correctement encadré qui peut être transmis via RS232. Un de mes amis dirigeait un serveur de distribution de courrier pour sa maison en utilisant RS232)
slebetman
4

Ce que vous décrivez comme le "marquage au Xème bit" peut être généralisé dans d'autres codes qui ont la propriété d'étendre les données d'une fraction constante, laissant certains mots de code libres d'être utilisés comme délimiteurs. Souvent, ces codes offrent également d'autres avantages; Les CD utilisent une modulation de huit à quatorze , ce qui garantit une longueur maximale de 0 bit entre chaque 1. D'autres exemples incluent les codes de bloc de correction d'erreur directe , qui utilisent également des bits supplémentaires pour coder les informations de détection et de correction des erreurs.

Un autre système que vous n'avez pas mentionné consiste à utiliser des informations hors bande, telles qu'une ligne de sélection de puce, pour délimiter des transactions ou des paquets.

Nick Johnson
la source
Les codes de correction d'erreur sont un peu à l'écart de la question. Ils devraient de toute façon être ajoutés à l'un de ces programmes. Les "informations hors bande" auxquelles vous faites référence sont les mêmes que le "contrôle de flux matériel", je suppose?
Eugene Sh.
@EugeneSh. - En fait, l'utilisation de bits de contrôle d'erreur pour le tramage est parfaitement valide, bien que coûteuse en termes de calcul côté réception. Vous effectuez simplement le calcul d'erreur pour chaque alignement de données possible, et celui qui réussit est un alignement valide sur une trame non corrompue. Bien sûr, si le cadre est corrompu, vous ne le trouverez pas.
Dave Tweed
@DaveTweed Eh bien, c'est à peu près ce que je voulais dire par la première technique. Ou je vous comprends mal?
Eugene Sh.
Non, vous ne vous méprenez pas; c'est de cela que je parlais. Cependant, votre "con" est faux - il est fiable, et il peut également être rendu robuste par rapport aux erreurs de transmission réelles.
Dave Tweed
@DaveTweed Qu'en est-il du temps de récupération? Avez-vous des exemples de comment le rendre robuste?
Eugene Sh.
3

Une autre option est ce que l'on appelle le codage de ligne . Le codage de ligne confère au signal certaines caractéristiques électriques qui le rendent plus facile à transmettre (DC équilibré et garanties de durée de fonctionnement maximale) et il prend en charge les caractères de contrôle pour le cadrage et la synchronisation d'horloge. Les codes de ligne sont utilisés dans tous les protocoles série haute vitesse modernes - 10M, 100M, 1G et 10G Ethernet, ATA série, FireWire, USB 3, PCIe, etc. Les codes de ligne courants sont 8b / 10b , 64b / 66b et 128b / 130b. Il existe également des codes de ligne plus simples qui ne fournissent pas d'informations de cadrage, uniquement l'équilibre DC et la synchronisation d'horloge. Machester et NRZ en sont des exemples. Vous voudrez probablement utiliser 8b / 10b si vous voulez synchroniser rapidement; les autres codes de ligne ne sont pas conçus pour se synchroniser rapidement. L'utilisation d'un code de ligne comme celui qui offre ce qui précède nécessitera l'utilisation d'un matériel personnalisé pour transmettre et recevoir.

En ce qui concerne votre option 5, la série RS232 standard est censée prendre en charge l'envoi et la réception de pauses lorsque la ligne est inactive pendant quelques octets. Cependant, cela peut ne pas être pris en charge sur tous les systèmes.

Généralement, la méthode de cadrage la plus simple et la plus fiable est votre option 1, en combinaison avec un champ de longueur et une routine de CRC ou de somme de contrôle simple. La routine de décodage est simple: jetez les octets jusqu'à ce que vous obteniez un octet de début, lisez le champ de longueur, attendez la trame entière, vérifiez la somme de contrôle, conservez-la si elle est bonne. Si la somme de contrôle est mauvaise, commencez à rejeter les octets du tampon jusqu'à ce que vous obteniez un octet de démarrage et répétez. Le problème principal avec cette technique est de trouver un début d'octet de trame qui n'est pas réellement un début d'octet de trame. Pour résoudre ce problème, une technique consiste à échapper les octets avec la même valeur que le début de l'octet de trame avec un autre caractère de contrôle, puis à modifier l'octet échappé afin qu'il ait une valeur différente. Dans ce cas, vous devrez également faire la même chose avec le nouvel octet de contrôle.

alex.forencich
la source
C'est la même chose que la réponse de Nick Johnson.
Dave Tweed