Définition :Parité (contrôle)

Procédure de détection et correction d'erreurs qui consiste à ajouter à chaque caractère un bit tel que la somme des éléments binaires modulo 2 soit égale à 0 ou 1.

---

Mieux comprendre les techniques de détection et correction d'erreurs

L'infrastructure du réseau téléphonique ne permet pas une transmission sans erreur. Le CCITT donne pour des débits inferieurs à 1200 bps un taux d'erreur de 5 pour 100 000 bits sur une liaison spécialisée et de 1 erreur pour 1000 bits sur le RTC. La qualité de la transmission, est donc insuffisante. Les protocoles permettent d'atténuer ces inconvénients. En aparté, les modems V32 et V32 bis sont trop récents pour avoir donné lieu à une campagne de test. Tout de même, on imagine aisément que le taux d'erreurs ne peut aller qu'en grandissant.

Comment se détecte une erreur ?

La méthode la plus simple est le contrôle de parité. Elle consiste à ajouter à chaque caractère un bit tel que la somme des éléments binaires modulo 2 soit égale à 0 ou 1. A l'arrivée le même contrôle est effectué et le résultat est comparé au bit de parité de l'octet. En cas d'inégalité l'octet est considéré comme erroné. L'insuffisance de ce contrôle est démontré par un contre exemple simple. Lorsque deux bits du même caractère sont erronés, le bit de parité est inhibé. En outre, le bit supplémentaire pénalise le débit utile. Les premiers protocoles élaborés utilisèrent en plus du contrôle de parité, une technique de contrôle appelée "checksum" sur 1 ou 2 caractères. Un checksum de 2 caractères, correspond au 12 bits de poids faible, de la somme arithmétique des valeurs ASCII de chacun des caractères.Ce traitement est effectué à l'émission, puis à la réception
avec un contrôle d'égalité. Avec l'apparition de débit supérieur à 4800 bps, le contrôle checksum est devenu obsolète. La technique la plus utilisée aujourd'hui, se base sur un détection d'erreur au niveau bit. Elle est appelée, contrôle de redondance cyclique (CRC: Cyclic Redundancy Checking) et utilise les polynômes mathématiques. Prenons le cas du contrôle CRC de 16 bits sur 3 caractères, normalisé par le CCITT. Le bloc de données à transmettre est traduit sous la forme d'un polynôme. Chaque bit du bloc constitue un coéfficient du polynôme de degré n-1 (ou n est le nombre de bits du bloc de données), pour donner: n-1
P(x)=c + cx + ... + cx
0 1 n-1

Ce dernier est divisé par le plonynôme générateur de degré 16,de l'appelant. Le reste de cette division, de degré maximum
15, donnera:
15
R(x)=r + rx + ... + rx
0 1 15

Les 16 bits r , r , ...r
0 1 15
vont former les 3 caractères du CRC, zone de détection qui sera ajoutée à la trame.

A la réception, le même algorithme est appliqué à la trame pour reconstituer le polynôme. Celui-ci est également divisée par le même polynôme générateur. Si le reste de cette division est identique à celui indiqué dans la zone CRC, la transmission s'est bien déroulée, dans la négative la trame est retransmise. La technique CRC filtre un grand nombre d'erreurs; Les erreurs qui portent sur un seul ou deux bits, sur des trames ayant un nombre impair de bit erronés, sur toutes les salves d'erreurs inferieures à 16 bits et sur plus de 99,99 % des autres. Cette technique très fiable, a pourtant son talon d'Achille. Si une erreur de transmission s'introduit dans le mot CRC, l'ensemble de la trame sera considérée comme erronée. Voici la primitive "CHK3" en langage C, utilisée par le protocole Kermit décrit plus loin, pour calculer le CRC sur 16 bits d'une chaîne de caractères terminée par "null". Le nombre "magique" 010201 est dérivé du polynôme CRC-CCITT.

Comment s'opère la correction ?

La technique de correction la plus simple, est du type "Envoyer et Attendre", (SW: Send and Wait). La station émettrice envoie une trame, àvec un mot de contrôle CRC et attend un accusé de réception positif (ACK: Acknowledge) ou négatif (NACK: Negative Acknowledge). Le deuxième cas éxige une retransmission. Si l'émetteur ne reçoit rien pendant un temps "T", le timeout, il retransmettra la trame. La retransmission se fait un nombre de fois, déterminé par un compteur, renseigné par l'utilisateur. En cas d'échec après la dernière tentative, la procédure est réinitialisée. L'analyse de cette méthode, amène à critiquer son utilisation, selon le mode de transmission. En mode bidirectionnel à l'alternat (half-duplex), l'usager se heurte à un dilemme. En augmentant, la longueur de la trame au delà du seuil optimum, il accroit le temps d'attente des accusés de réception et le temps de retransmission en cas d'erreurs. Si il diminue la taille de la trame, le nombre d'acusés de reception devient inversement proportionnel. Dans les deux stratégies, le rendement se trouve affaibli. Les protocoles SW utilisés aujourd'hui, arrivent à réduire le temps de transmission par anticipation de l'envoi des trames sur les accusés de reception et regroupement de ces derniers pour une seule émission. Les trames sont alors numérotées, sur 3 bits par exemple et l'anticipation est limitée par une "fenêtre d'anticipation" de 7 trames.

En mode bidirectionnel simultané (full-duplex), les trames et les accusés de réception sont entrelacés. Les protocoles fonctionnent également par anticipation, mais avec des acquittements encapsulés dans les trames d'émission et de réception. Il existe deux types de fenêtre d'anticipation pour deux styles de retransmission. Avec une fenêtre d'anticipation "fixe", lorsqu'une erreur survient, l'emetteur renvoie la trame qui n'a pas été acquitée et toutes les trames postérieures. La retransmission est dite continue. Avec une fenêtre d'anticipation par "glissement", il ne renvoie que la trame erronée. On parle, de retransmission par répétition selective. Paradoxalement, cette seconde méthode est moins utilisée, car l'agorithme d'exploitation est plus compliqué.

Il arrive parfois, que les protocoles SW à fenêtre d'anticipation soient confondus avec ceux en mode flux continu. A juste titre , car ces derniers autorisent également un transfert continu de trames. A la différence, qu'un seul acquittement soit attendu, en fin de transmission. Cette troisième technique est même plus performante. Elle insère un mot CRC par intervalle et renvoie les trames déffectueuses uniquement en fin de transfert. Deux modes de renvoi de trames sont utilisés. Le "mode coupé" consiste à retransmettre toutes les trames si une erreur vient à "couper" le flot des données. Le "mode échelonné", consiste à reduire la taille des trames en cas d'erreur, jusqu'à ce que la liaison s'améliore.

H.M