Universit de La Rochelle Master CCI

RseauxTD n 3 : LLC

Exercice 1 :

1. Quelle est la distance de Hamming entre deux mots valides dans le code ASCII ?1, car pour passer d'un mot valide un autre mot valide du code il suffit de modifier un seul bit. End'autres termes : tous les mots possibles sont valides.

2. Quels sont les types derreurs que permet de dceler un tel codage ?Rappel : pour une distance de Hamming donne dist

- on peut dtecter avec certitude n bits, avec n +1 dist

- on peut corriger avec certitude n bits, avec 2n +1 dist

- le but d'un code dtecteur (et ventuellement correcteur) d'erreur est d'augmenter la valeur dedist Dans notre cas, aucune dtection n'est possible : n = 0.

3. On choisit un code trois bits, les mots de code valides sont ceux dont les trois bits sont identiques.Quelle est la distance de Hamming ? Les mots valides sont : 000 et 111. Pour passer d'un mot valide l'autre il faut changer 3 bits. La distancede Hamming est donc de 3.

4. Si une erreur se produit sur un seul bit, quels sont les mots que lon peut obtenir, et par quel mot validechacun peut il tre remplac sans ambigut ?Les mots errons avec 1 seul bit faux sont : 001, 010, 100, 110, 101, 011 Puisque la distance deHamming est 3, on doit pouvoir dtecter au maximume 3-1=2 bits et corriger (3-1)/2 = 1 bit (cf. rappel ci-dessus). La correction consite revenir au mot valide le plus proche du mot erron reu. Ainsi, les 3premiers mots seront remplacs par 000 (car ils ont une distance de 1 avec 000 et une distance de 2avec 111, il est bien sur ncessaire de faire la supposition qu'il n'y a pas eu plus d'une erreur) et les troisderniers par 111 (pour des raisons similaires)

Exercice 2 :

Le CRC (Cyclic Redundancy Check) est un code qui permet de dtecter les erreurs de transmission. Il estobtenu en ajoutant aux donnes transmises (I) les bits de redondance (R) obtenus en divisant C0 par G. C0tant le mot de code obtenu en rajoutant d bits 0 la fin de I, G tant les bits reprsentant le polynmegnrateur et d le degr de G. Le code C envoy est la concatnation de I et de R. larrive, le rcepteurdtecte une erreur si la division de C reu par G ne donne pas un reste nul. Il existe 3 mthodes pour calculer le CRC : la division polynomiale binaire, la division polynomiale symboliqueet les registres dcalage. Nous allons tudier uniquement les deux premires qui sont similaires.

1. Calculez la mthode de la division polynomiale symbolique le bloc de contrle (CRC) correspondant lasuite de bits 1100101010101011 en utilisant le polynme gnrateur G(x) =x4 + x3 + x + 1I = 1100101010101011 , d = 4 C0 = 11001010101010110000

C0(x) = x19+ x18+ x15+ x13+ x11+ x9+ x7+ x5+ x4 G = 11011 G(x) = x4+ x3+ x+1 On effectue la division de C0(x) par G(x) (la division polynomiale symbolique est immdiate voir lexempledu sujet de TD). R(x) = x3 donc R = 1000, on transmet alors C = IR = 11001010101010111000

2. La dtection derreurs utilise le CRC x6 + x4 + x + 1. Le rcepteur reoit la squence binaire suivante101011000110. Le message est-il correct (tester avec la mthode de division polynomiale binaire) ? C = 101011000110 , I = 101011 , R = 000110 , G = 1010011Pour vrifier que le message est correct il faut faire la division de C reu par G. Si le reste est nul (et illest normalement) alors cest bon.

Universit de La Rochelle Master CCI

Exercice 3 :

Dans lalphabet ASCII le mot OSI se code par les 3 caractres de 7 bits suivants :O = 1001111, S = 1010011 et I = 1000011

1. La LRC (Longitudinal Redundancy Check) consiste rajouter un bit de parit la fin dun bloc dedonnes (octet, caractre, suite de bits,). La VRC (Vertical Redundancy Check) consiste calculer lesbits de parit entre plusieurs blocs de donnes en vertical :1 bit de parit pour les bits qui sont la mmeposition dans les diffrents blocs considrs. Donnez la VRC du mot OSI en utilisant une parit pairepour calculer le LRC de chaque caractre.1001111 11010011 01000011 11011111 0 VRC LRC

2. Combien derreurs ce code peut-il dtecter ? Combien peut-il en corriger ?Il peut dtecter jusqu 3 erreurs, s'il y en a quatre, on n'est pas sur de dtecter car on retombe sur uncode valide. Il peut corriger 1 erreur (la position du bit est donne par lintersection de la ligne du bitincorrect dans le VRC avec la colonne du bit incorrect dans le LRC. Lorsqu'il y a plus de 2 erreursl'ambigut empche la correction de l'erreur. Il faut raisonner par lexemple : modifier un bit, puis 2, puis 3puis 4 (par exemple considrer le carr suprieur gauche : 10 sur la premire ligne et 10 sur la seconde).Il est galement possible de dterminer la distance de Hamming, cest un moyen simple et efficace. Onconstate que sur un bit quelconque de donnes il y a trois bits de contrle qui interviennent. Il faut doncchanger 4 bits pour retomber sur quelque chose de valide. La distance est gale 4. Daprs les formulesdonnes en cours on peut dtecter d erreurs tel que d+1 dist et corriger c erreur tel que 2c+1 dist.Pour nous, on trouve d=3 et c=1 (arrondis lentier infrieur).

3. Calculez le CRC du mot OSI en utilisant le polynme gnrateur x8 + 1 et en supposant que le 8e bitde chaque caractre est un bit de parit paire et que le mot dinformation est compos des bits 3caractres la suite.I = 100111111010011010000111 les bits en gras reprsentent la VRC G = 100000001 et d = 8En utilisant la division polynomiale on obtient R = 10111110 (ce qui correspond la LRC de la question1). Donc, la LRC peut tre obtenue par un code cyclique.

Exercice 4 :

1. Comment seffectue la synchronisation dans une procdure HDLC (High level Data Link Control) ?La synchronisation dans HDLC est effectue via le fanion dentte : 01111110. Le codage utilis doitassurer assez de transitions dans le fanion pour que le rcepteur puisse se synchroniser.

2. On dsire transmettre la suite de bits de donnes : 0111111001101110. Quelle est la suite de bits qui estrellement transmise au niveau physique ?Lutilisation du fanion ncessite lutilisation de bits de brouillage (ou de transparence) pour viter detrouver une squence de bits identique au fanion dans les donnes. Dans HDLC, on introduit un bit 0 chaque fois quune squence de 5 bits 1 est rencontre. On garantit ainsi labsence dune squence de6 bits 1 conscutifs et donc on vite lapparition de fanions parmi les donnes. Le rcepteur effectuelopration inverse : chaque fois quil repre une suite de 5 bits 1 il tente de supprimer le zro qui suit.Si le zro est absent, alors on est forcment en train de recevoir un fanion.La suite 0111111001101110 devient lmission 01111101001101110 (bit de transparence en gras)

3. On dsire maintenant transmettre les bits : 011011010011101101111100. Suite une erreur detransmission le rcepteur reoit la squence : 011011010011111101111100. Comment le rcepteurinterprte cette squence de donnes ?Le rcepteur reoit la squence : 011011010011111101111100 Il la dcoupe en : trame1 fanion trame 2 Reconnaissance du fanion au milieu des donnes le rcepteur pense recevoir deux trames.

4. quel niveau peut-on dtecter cette erreur ? Indiquez le type de reprise sur erreur qui sera entrepris ensachant que la taille minimale dune trame est de 4 octets. 2 cas possibles :

Universit de La Rochelle Master CCI

a. la trame 1 ou 2 fait moins de 4 octets (taille minimale dune trame) ou fait un nombre entier doctets (nbde bits nest pas multiple de 8) elle est ignore (car impossible) et cest le mcanisme de TIME-OUT quipermettra de rmettre la trame (puisque le rcepteur naura pas acquitt la trame ni positivement, ningativement) b. la trame 1 ou 2 fait plus que 4 octets et un nombre entier doctets linterprtation des diffrentschamps de la trame, notamment celui du CRC, va montrer que la trame est incomprhensible, donc ellesera rejete et le rejet est signal soit par un acquittement ngatif soit par une trame de rejet. La reprisese fera donc, soit par lenvoi dun rejet, soit par acquittement ngatif, soit par attente de rmission suite lexpiration du temporisateur de lmetteur.

Exercice 5 :

Soit une liaison de donnes entre deux stations A et B utilisant le protocole HDLC (cf. Annexe). La suite ci-dessous arrive la station B.

S = 011111100000001000101001110111110100111110000101011001111100001010

001111110011111100111111000000010100010010010111011111010101111110

1. Quelles sont les trames ?Les trames sont dlimites par des fanions. Lorsquune station met une seule trame cette dernire estdlimite par deux fanions (un devant et un derrire). Lorsquune station envoie plusieurs trames daffileau mme rcepteur elle peut sparer ses trames avec un seul fanion (le fanion de fin dune trame estgalement le fanion de dbut de la suivante) mais elle peut galement envoyer plusieurs fanions afindoccuper le canal et garder la parole (cest le cas ici).S se dcompose en 2 trames : trame 1 : 00000010001010011101111101001111100001010110011111000010100 trame 2 : 000000101000100100101110111110101

2. Quels sont les lments binaires aprs traitement de la transparence binaire ?transparence binaire = rajouter dans les donnes un bit 0 aprs une suite de 5 bits 1.Aprs traitement de la transparence binaire on a (les bits de transparence sont en gras ci-dessus) :trame 1 : 00000010001010011101111110011111000101011001111100010100 trame 2 : 00000010100010010010111011111101

3. Quels sont les champs et leurs signification ?

4. Reprsentez le diagramme correspondant lchange.

trame 1 trame 2 changes

@destinataire : 00000010

commande : 00101001 0----------- trame I -010------- N(s)= 2 ------1----- P = 1 --------001 N(r) = 1donnes :110111111001111100010101FCS : 1001111100010100

@destinataire : 00000010commande : 10001001 10---------- trame S ---00------- type RR -------1----- F = 1 ---------001 N(r) = 1donnes : FCS : 0010111011111101

On constate que dans les deux cas ladresse du destinataire et la mme donc les 2 trames vont dans lemme sens et proviennent du mme metteur (ce qui confirme la remarque de la question 1). Souvent HDLCest utilis en point point, ladresse sert juste identifier la partie qui parle.