Cours de Rseaux Partie 1

IUT de Villetaneuse R&T 1re anne

Auteure : Laure Petrucci Responsable du cours : Giulio Manzonetto 7 septembre 2012

Table des matires

1 Concepts de base 1.1 Gnralits . . . . . . . . . . . . . . . . 1.2 Reprsentation de linformation . . . . . 1.2.1 Quelle information reprsenter ? . 1.2.2 Reprsentation des donnes . . . 1.2.3 Units utilises . . . . . . . . . . 1.3 Mesures de performance . . . . . . . . . 1.3.1 Dbit . . . . . . . . . . . . . . . 1.3.2 Dlais . . . . . . . . . . . . . . . 1.4 Classication des rseaux . . . . . . . . 1.5 Topologies de rseaux . . . . . . . . . . 1.5.1 Composants . . . . . . . . . . . . 1.5.2 Architectures des rseaux . . . . 2 Modle de rfrence 2.1 Normalisation . . . . . . . . . . . . . . 2.1.1 Quest-ce et pourquoi ? . . . . . 2.1.2 Organismes de normalisation . 2.2 Modle de rfrence OSI . . . . . . . . 2.2.1 Principes de la structuration en 2.2.2 Couches du modle OSI . . . . 2.3 Interactions entre couches . . . . . . . 2.3.1 Protocoles et Services . . . . . 2.3.2 Encapsulation, PDU et SDU . 2.3.3 Primitives de service . . . . . . 2.4 Types de connexion . . . . . . . . . . 2.5 Reprsentation des tats et messages . 2.5.1 Automates . . . . . . . . . . . 2.5.2 Chronogrammes . . . . . . . . 3 3 3 3 4 4 5 5 5 5 6 6 6 8 8 8 8 8 9 9 10 10 10 11 11 12 12 12 14 14 14 14 15 15 16 17 17 17 18 18

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . couches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

3 La couche physique 3.1 Transmission du signal . . . . . . . . . . . . . . . . 3.1.1 Obtention dun signal carr . . . . . . . . . 3.1.2 Bande passante . . . . . . . . . . . . . . . . 3.1.3 Thorme de Shannon . . . . . . . . . . . . 3.1.4 Signaux et modulation . . . . . . . . . . . . 3.1.5 Rapidit de modulation . . . . . . . . . . . 3.2 Codage en bande de base . . . . . . . . . . . . . . 3.2.1 Phases du codage . . . . . . . . . . . . . . . 3.2.2 Codage NRZ (No Return to Zero) . . . . . 3.2.3 Codage NRZI (No Return to Zero Inverted) 3.2.4 Codage Manchester . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

3.3

3.2.5 Codage Manchester direntiel . . . . . 3.2.6 Codage biplaire . . . . . . . . . . . . . 3.2.7 Codage 4b/5b . . . . . . . . . . . . . . . Modulation/dmodulation (codage large bande) 3.3.1 Modulation damplitude . . . . . . . . . 3.3.2 Modulation de frquence . . . . . . . . . 3.3.3 Modulation de phase . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

18 19 19 20 20 21 21 22 22 22 22 23 23 24 25 26 26

4 Dtection et Correction derreurs 4.1 Gnralits . . . . . . . . . . . . . . . . . . . 4.1.1 Un code simple : la rptition . . . . . 4.1.2 Inconvnients et problmes rencontrs 4.2 Dtection derreurs . . . . . . . . . . . . . . . 4.2.1 Codes contrle de parit . . . . . . . 4.2.2 Codes polynmiaux . . . . . . . . . . 4.3 Correction derreurs . . . . . . . . . . . . . . 4.3.1 Code de Hamming . . . . . . . . . . . 4.3.2 Demande de retransmission . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

Rseaux Partie 1

IUT R&T Villetaneuse

Chapitre 1

Concepts de base
1.1 Gnralits

Le terme informatique provient dinformation et dautomatique, linformatique tant le traitement automatique de linformation. Un rseau est une organisation de voies de communication entre direntes entits. Cette dnition est gnrale et peut sappliquer par exemple aux rseaux routiers, ferroviaires, de tlcommunications, . . . Les entits qui communiquent au sein dun rseau informatique sont des ressources informatiques dont on distingue deux types : les ressources matrielles : ordinateur, imprimante, scanner, . . . qui sont des composants de traitement, les modems, cartes rseaux, commutateurs, routeurs, cbles, . . . qui sont des composants de transmission. les ressources logicielles : applications informatiques, jeux, bases de donnes, . . . Un rseau informatique est constitu des moyens la fois matriels et logiciels mis en uvre pour assurer les communications entre des ressources informatiques. Un rseau informatique permet aux entits relies de partager des informations, les rsultats de traitements, les ressources, par exemple pour que plusieurs utilisateurs travaillant sur des ordinateurs dirents puissent utiliser la mme imprimante.

1.2
1.2.1

Reprsentation de linformation
Quelle information reprsenter ?

Supposons quune machine doive envoyer limage de la Figure 1.1 une autre, aprs avoir convenu de la taille de cette image et de lordre denvoi des lments la constituant. La description se fera, par exemple, carr par carr, ligne par ligne, en commenant en haut gauche, pour nir en bas droite. Il est en eet impossible denvoyer limage telle quelle sans la coder. La squence de couleurs envoyer est donc (en notant blanc B et noir N) : NNNNN NBBBN NBNBN NBBBN NNNNN

Figure 1.1 Une image transmettre

Une manire de coder la couleur de chaque carr consiste associer une valeur chaque couleur possible, par exemple 1 B (le pixel sur lcran est allum) et 0 N (le pixel est teint). La suite de chires codant limage est alors : 00000 01110 01010 01110 00000

1.2.2

Reprsentation des donnes

Les donnes informatiques sont reprsentes par des suites de nombres. Ces nombres sont crits en binaire (cest--dire en base 2). En base 2, on nutilise que les chires 0 et 1. Lutilisation de la base 2 garantit de pouvoir reprsenter un tat stable dun systme physique, par exemple : circuit lectrique ouvert/ferm carte perfore avec un trou/sans trou ... Par consquent, sur un systme informatique, les donnes sont reprsentes par une suite de chires 0 et 1 correspondant des tats dirents sur le support physique. Ces tats peuvent tre des tensions direntes (voir Chapitre 3).

1.2.3

Units utilises

Dnition 1 (bit) Un symbole binaire (donc en base 2) est appel un bit (binary digit). 1 bit permet de coder 2 tats : 0 et 1 ; 2 bits permettent de coder 4 tats : 00, 01, 10 et 11 ; 3 bits permettent de coder 8 tats : 000, 001, 010, 011, 100, 101, 110 et 111 ; ... n bits permettent de coder 2n tats. Dnition 2 (octet) Une suite de 8 bits est appele un octet. Attention, en anglais le bit est appel bit, alors que loctet est appel byte ! Les units multiples des bits et des octets sont dcrites dans les Tableaux 1.1 et 1.2 : Unit kilo-bit mga-bit giga-bit tra-bit Symbole Kb Mb Gb Tb Valeur (bits) 103 = 1 000 106 = 1 000 000 109 = 1 000 000 000 12 10 = 1 000 000 000 000

Table 1.1 Units multiples des bits

Unit kibi-octet mbi-octet gibi-octet tbi-octet

Symbole Kio Mio Gio Tio

Valeur (octets) 210 = 1 024 220 230 240

Table 1.2 Units multiples des octets

Rseaux Partie 1

IUT R&T Villetaneuse

Traditionnellement, lorsque les prxes kilo, mga, giga et tera sont appliqus aux octets, ils ne reprsentent pas une puissance de 10, mais une puissance de 2. Cet usage reste largement en vigueur chez les professionnels comme le grand public. Cependant cette tradition viole les normes en vigueur qui imposent dutiliser les prxes kibi, mbi, gibi, tbi pour les puissances de 2.

1.3
1.3.1

Mesures de performance
Dbit

Dnition 3 (dbit) Le dbit dun rseau mesure la quantit dinformation que le rseau peut transmettre par unit de temps : dbit = quantit dinformation temps

Lunit est par consquent le bit par seconde, not b/s ou b.s1 . Les rseaux actuels ayant un dbit assez lev, on utilise plus souvent des mga-bits par secondes, nots M b/s ou M b.s1 . Dnition 4 (dbits nominal et utile) Le dbit nominal dun rseau est la quantit thorique maximale dinformation pouvant tre transmise par unit de temps. Le dbit utile est la quantit dinformation eectivement transmise par unit de temps. Dnition 5 (taux dutilisation) Le taux dutilisation du rseau est donc le rapport du dbit utile au dbit nominal : dbit utile taux dutilisation = dbit nominal Le taux dutilisation est infrieur 100%. Ceci est d entre autres aux pertes sur la voie de communication et lintervalle de temps laiss entre lenvoi de deux messages.

1.3.2

Dlais

Dnition 6 (dlai) Le dlai total dacheminement dun message se compose de deux parties : le dlai de transmission est le temps mis pour transmettre la quantit dinformation du message, cest--dire :
dlaitransmission = quantit information dbit

le dlai de propagation est le temps mis pour que le signal se propage sur le matriel. Les quipements traverss peuvent introduire des retards.
dlaipropagation = distance parcourue vitesse

+ retards

On a donc :
dlaitotal = dlaitransmission + dlaipropagation

1.4

Classication des rseaux

Les rseaux sont caractriss non seulement par leur dbit, mais galement par le rayon de couverture gographique quils permettent datteindre. Les direntes caractristiques sont prsents dans le Tableau 1.3. Le PAN est utilis chez un particulier, le LAN dans un btiment (ou plusieurs btiments proches) dune entreprise, le MAN interconnecte dirents sites lchelle dune agglomration, et le WAN stend sur un pays.

Rseaux Partie 1

IUT R&T Villetaneuse

Sigle PAN LAN MAN WAN

Nom Personal Area Network Local Area Network Metropolitan Area Network Wide Area Network

Distance quelques mtres jusqu 2km jusqu 100km milliers de km

Dbit 1M b/s de 10M b/s 1Gb/s environ 100M b/s quelques M b/s

Table 1.3 Caractrisation des rseaux

1.5
1.5.1

Topologies de rseaux
Composants

Les composants des rseaux se rpartissent selon deux types : les composants de traitement sont les entits produisant et/ou consommant les informations qui circulent sur le rseau (par exemple les ordinateurs) ; les composants de routage assurent la transition et la circulation des informations changes entre les composants de traitement (par exemple, les cbles, commutateurs).

1.5.2

Architectures des rseaux

Larchitecture dun rseau comprend 3 parties : Larchitecture physique dnit la topologie physique dinterconnection des composants du rseau. Larchitecture logique dnit la topologie de circulation de linformation. Elle peut tre dirente de larchitecture physique. Larchitecture logicielle dnit les logiciels assurant lacheminement des donnes. Le Tableau 1.4 montre les architectures physiques et logiques les plus classiques.

Rseaux Partie 1

IUT R&T Villetaneuse

A A B C D

Bus

Arbre

B D A E

toile
D C

Graphe
B C

Anneau
D C

Complte

E D

Table 1.4 Topologies classiques

Rseaux Partie 1

IUT R&T Villetaneuse

Chapitre 2

Modle de rfrence
2.1
2.1.1

Normalisation
Quest-ce et pourquoi ?

Ltablissement de normes permet davoir une structure homogne pour faire communiquer dirents quipements. La conformit une norme garantit la satisfaction de rgles prcises. Ainsi, des matriels dirents, fabriqus par diverses entreprises, peuvent communiquer car la norme ore un cadre compatible entre ces entits htrognes. La norme permet galement dassurer un niveau minimum de qualit.

2.1.2

Organismes de normalisation

La normalisation est eectue par des organismes comptents au sein desquels les dirents acteurs du domaine sont reprsents. Trois organismes internationaux sont concerns par la normalisation dans le domaine des rseaux : UIT (Union Internationale des Tlcommunications) est linstitution spcialise de lONU (Organisation des Nations Unies) dans le domaine des tlcommunications. Elle comprend deux branches : lUIT-T charge de la normalisation dans le domaine des tlcommunications et lUIT-R qui soccupe du domaine des radiocommunications. IEC (International Electrotechnic Commission), fonde en 1906, est charge de coordonner et dunier les normes dans le domaine de llectricit. ISO (International Standards Organisation) est une organisation prive charge de la normalisation dans tous les domaines sauf llectricit et llectronique. Ces organismes regroupent des reprsentants dorganismes nationaux. En France, les normes sont gres par lAFNOR (Association Franaise de NORmalisation).

2.2

Modle de rfrence OSI

Le modle de rfrence dni par lISO est lOSI (Open System Interconnection ). Il permet des systmes htrognes de sinterconnecter et dchanger des informations. Il est par consquent indpendant de la structure et de la technologie des matriels employs. Ce modle ore un cadre permettant dassurer une compatibilit maximum entre les entits communicantes tout en minimisant les contraintes permettant de les raliser. La complexit de conception, de ralisation et de maintenance des logiciels et de larchitecture des rseaux, est matrise grce une organisation en couches, chaque couche tant btie sur la prcdente.

2.2.1

Principes de la structuration en couches

Le modle OSI est compos de sept couches. Chaque couche peut interagir uniquement avec les deux couches adjacentes. Une couche N est constitue dun ensemble dentits formant un sous-systme de niveau N . Elle ne peut dialoguer quavec une couche de mme niveau N sur une autre machine. Les communications se font donc entre entits homologues. La communication entre deux entits homologues de niveau N obit un ensemble de rgles et formats, syntaxiques et smantiques, prdnis pour les entits de niveau N . Ces rgles et formats dnissent le protocole de niveau N . Une couche de niveau N fournit des services pour la couche de niveau N + 1. La couche de niveau N + 1 communique la couche N les caractristiques du service attendu. Les services fournis par une couche N sont identis par des SAP (Service Access Point) ou ports.

2.2.2

Couches du modle OSI

Les sept couches sont organises comme indiqu dans le Tableau 2.1. Niveau 7 6 5 4 3 2 1 Couche application prsentation session transport rseau liaison de donnes physique

Table 2.1 Les sept couches du modle OSI Chaque couche a un rle spcique : 7. La couche application ore aux utilisateurs des services normaliss pour la conception de leurs applications. 6. La couche prsentation ralise la compression, le cryptage et vrie la syntaxe des donnes changes. 5. La couche session contrle le dialogue entre les machines qui communiquent. Elle gre en particulier la synchronisation du dialogue et la reprise aprs interruption. 4. La couche transport assure le transport de bout en bout, cest--dire entre les deux stations qui communiquent. Elle garantit que le message est achemin entre les deux stations avec la qualit de service demande. Le terme qualit de service dsigne un ensemble de proprits que le demandeur du service exige du prestataire, telles que la garantie dun dbit minimum, le respect dune borne maximum de temps de livraison de messages, . . . 3. La couche rseau assure lacheminement des blocs dinformation travers le sous-rseau. Elle choisit le meilleur chemin entre les deux commutateurs dentre-sortie du sous-rseau. Les blocs dinformation de niveau 3 sont appels paquets. 2. La couche liaison de donnes est responsable de lacheminement sans erreur des blocs dinformation entre les deux machines qui se trouvent aux extrmits dune liaison de donnes. Les blocs dinformation de niveau 2 sont appels trames. 1. La couche physique dnit les moyens mcaniques (connecteurs), lectriques et fonctionnels ncessaires lactivation, au maintien et la dsactivation des connexions physiques destines la transmission des donnes binaires au niveau de la couche liaison de donnes. Elle fournit
Rseaux Partie 1 9 IUT R&T Villetaneuse

donc tous les lments matriels et logiciels ncessaires au transport correct des donnes binaires, comme : les interfaces de connexion des quipements informatiques au support de transmission, appeles jonctions ; les supports de transmission ; les cartes rseaux ; les modems ; les multiplexeurs, qui concentrent plusieurs communications sur une ligne de transmission unique.

2.3
2.3.1

Interactions entre couches

Protocoles et Services

Les notions de protocole et de service sont fondamentales. Un protocole est un ensemble de rgles et formats, syntaxiques et smantiques prdnis pour les entits dun mme niveau N de deux machines direntes. Un service est fourni par une couche de niveau N la couche de niveau N + 1 dune mme machine. La Figure 2.1 dcrit la communication entre les 7 niveaux de couches de deux entits communicantes A et B .
Machine A 7. 6. 5. 4. 3. 2. 1. Application Prsentation Session Transport Rseau Liaison de donnes Physique Machine B Application Prsentation Session Transport Rseau Liaison de donnes Physique 7. 6. 5. 4. 3. 2. 1.

Figure 2.1 Communication entre couches

2.3.2

Encapsulation, PDU et SDU

Les messages changs par un protocole de niveau N sont appels des P DUN (Protocol Data Unit de niveau N ). Les messages changs entre la couche N et la couche infrieure N 1 sont appels des SDUN 1 (Service Data Unit de niveau N 1). De plus, un protocole de niveau N ajoute au SDUN quil a reu des informations de contrle visant contrler la bonne excution du protocole. Ces informations de contrle sont appeles
Rseaux Partie 1 10 IUT R&T Villetaneuse

P CIN (Protocol Control Information de niveau N ). On a par consquent : P DUN = SDUN + P CIN SDUN = P DUN +1 On dit alors que le P DUN encapsule le SDUN . Au lieu dindexer le P DU ou le SDU par le numro de la couche, on le fait souvent prcder de la premire lettre du nom de la couche (en anglais). Par exemple, N P DU = P DU3 , o le N indique la couche rseau (network).

2.3.3

Primitives de service

Il existe 4 primitives de service : requte, indication, rponse et conrmation. Une requte est initialement envoye par la couche N la couche N 1 dune mme entit. Ensuite, une indication est transmise de la couche N 1 la couche N de lautre entit communicant. La rponse est envoye par la couche N la couche N 1 de cette seconde entit. Enn, une conrmation est transmise de la couche N 1 la couche N de lentit ayant mis la requte. Ceci est illustr dans la Figure 2.2.
Machine A Application Prsentation 2. Indication 3. Rponse 1. Requte Session Transport Rseau Liaison de donnes Physique 4. Conrmation Machine B Application Prsentation Session Transport Rseau Liaison de donnes Physique

Figure 2.2 Primitives de service

2.4

Types de connexion

La communication entre entits homologues de mme niveau passe par ltablissement dune connexion. Ce peut tre une connexion point point qui associe exactement deux entits, ou une connexion multipoints qui en associe plus. Les modes de communication sont simplex, cest--dire dans un seul sens, ou duplex, dans les deux sens. Enn, les protocoles peuvent oprer en mode connect ou en mode dconnect. En mode connect, ltablissement de la connexion comporte trois phases : connexion, transfert, et dconnexion. Le contexte de la communication est prserv. Par contre, en mode dconnect, seule la phase de transfert a lieu, et la communication seectue sans mmoire.

Rseaux Partie 1

11

IUT R&T Villetaneuse

2.5

Reprsentation des tats et messages

Lorsque lon souhaite comprendre quelles informations transitent dans un rseau, et quand elles circulent, il convient de les reprsenter de manire facilement comprhensible, par exemple graphique.

2.5.1

Automates

Un automate permet de reprsenter les dirents tats possibles dun systme, tel quune machine communicant avec une autre, ainsi que les actions lui permettant de passer dun tat un autre. Dnition 7 (automate) Un automate est un triplet E, A, e0 o : E est un ensemble d tats du systme. Un tat e E peut avoir un nom (encore appel tiquette) ; A est un ensemble d actions possibles (galement appeles transitions) a A telles que e1 , e2 E : a = (e1 , e2 ). Laction a peut alors tre eectue si le systme se trouve dans ltat e1 . Une fois que laction a est termine, le systme se trouve dans ltat e2 . Les actions dans A peuvent tre tiquetes (cest--dire avoir un nom) ou tre des envois ou des rceptions de messages. Lenvoi dun message m est not !m et la rception dun message m est note ?m ; e0 E est un tat particulier du systme dit tat initial. Il indique par exemple dans quel tat le systme se trouve lorsquaucune des oprations qui nous intressent na eu lieu. Un automate est reprsent par un graphe dont les nuds sont les tats (cercles ou ellipses contenant le nom de ltat), et les arcs sont les actions. Exemple : Soient une machine A et une machine B communicant entre elles. La machine A envoie un message la machine B , pour que celle-ci eectue un calcul, puis attend le rsultat. La machine B reoit un message, eectue un calcul, renvoie le rsultat, puis attend un nouveau message. . . Les comportements des machines A et B peuvent tre reprsents par des automates, comme indiqu dans la Figure 2.3.
Dbut !message Attente ?rsultat Fin Attente ?message Reu calcule Calcul !rsultat

(a) Machine A

(b) Machine B

Figure 2.3 Automates

2.5.2

Chronogrammes

Un chronogramme permet de reprsenter les changes de messages au cours du temps. Chaque entit prenant part aux changes est reprsente par une ligne verticale. Le temps scoule du haut vers le bas. Un arc entre deux lignes verticales indique quun message a t envoy par lentit la source de larc et est reu par lentit destination de larc. Lorsquun message se perd, larc natteint pas la destination et se termine par une croix (X).

Rseaux Partie 1

12

IUT R&T Villetaneuse

Exemple : Supposons que 2 machines de type A (A1 et A2 ) et une machine de type B communiquent, telles que celles dcrites dans la Figure 2.3. Supposons galement que le message envoy par A2 se perde. Les changes de messages peuvent tre dcrits par le chronogramme de la Figure 2.4.
A1 message message X rsultat B A2

Figure 2.4 Chronogramme

Rseaux Partie 1

13

IUT R&T Villetaneuse

Chapitre 3

La couche physique
3.1 Transmission du signal

La couche physique assure le transfert de linformation. Celle-ci est transmise par la couche suprieure comme une suite de bits. Dans cette couche sont dnis : les signaux, les voies de transmission, les ETCDs (quipement Terminal de Circuit de Donnes), les jonctions et les connecteurs de raccordement des voies de transmission aux ETCDs. Les informations transmettre tant des 0 et 1, on peut imaginer transmettre sur la voie physique un signal carr avec une tension dirente pour les 0 et les 1 : cest le principe du codage NRZ (voir Section 3.2.2). Or le support physique altre facilement les signaux carrs. Tant que le dbit et la distance parcourir sont faibles, on peut utiliser un signal carr, mais on est amen mettre en uvre des techniques plus sophistiques pour amliorer les performances (voir Sections 3.2 et 3.3).

3.1.1

Obtention dun signal carr

Thorme 1 (Fourier) Tout signal priodique de frquence f peut tre dcompos en la somme de signaux sinusodaux dont la frquence est un multiple de f , appels composantes spectrales et ventuellement dune fonction constante appele composante continue. Une composante spectrale est dtermine par son amplitude A, son rang n et sa phase . Elle sexprime sous la forme : S (t) = sin(2nf t + ) Les sinusodes de frquences f , 2f , . . . sont appeles harmoniques. La frquence f est dite frquence fondamentale. Plus il y a de composantes spectrales, plus la fonction obtenue sloigne dune sinusode. Cest ainsi que lon obtient une signal carr.

3.1.2

Bande passante

Le support physique ne peut pas faire circuler des signaux de nimporte quelle frquence sans perte dnergie et par consquent damplitude. Dnition 8 (bande passante) Chaque support admet une frquence de coupure basse, qui indique la frquence minimale pouvant circuler, et une frquence de coupure haute, frquence maximale pouvant circuler. La bande passante est la dirence entre la frquence de coupure haute et la frquence de coupure basse.

14

On tolre un aaiblissement de puissance de 50%, cest--dire que : 1 Psortie Pentre 2 La bande passante diminue avec la longueur du support. Elle dpend galement des conditions physiques (matriau, . . . ). Soit B la bande passante. Les frquences des composantes spectrales tant des multiples entiers de la frquence fondamentale f , le nombre de composantes pouvant tre transmises de faon able est Ns = B f . Au cours de la transmission, le signal est aaibli. De plus ses composantes peuvent acqurir des dphasages distincts. Ceci peut conduire des erreurs lors de la rception : ce qui est reu est dirent de ce qui a t envoy. Pour viter de tels problmes, il est ncessaire dutiliser des codes plus sophistiqus, qui satisfont certaines proprits.

3.1.3

Thorme de Shannon

Pour transformer un signal analogique en signal numrique, on utilise une technique dchantillonnage, qui consiste mesurer lamplitude du signal intervalles de temps rguliers. On eectue ensuite une quantication du signal, cest--dire que lon dnit des subdivisions rgulires de lamplitude du signal, et enn une numrisation du signal, cest--dire que lon transforme le signal en nombres en fonction des hauteurs de quantication. Thorme 2 (Shannon) Il est ncessaire, pour reconstituer un signal propag dans un milieu de bande passante B , que la frquence dchantillonnage soit au moins le double de B : fe 2B .

3.1.4

Signaux et modulation

Transmission en bande de base Ce type de transmission dit en bande de base est principalement rserv aux rseaux locaux. Le codeur en bande de base transforme les bits de donnes en un signal lectrique numrique. Ce signal se prsente comme une suite de niveaux de tension dont les amplitudes sont choisies parmi un nombre ni de possibilits. Proprit 1 Les signaux carrs imposent de vhiculer au moins 6 ou 7 composantes spectrales pour une bonne reconstitution du signal. Les frquences sont alors leves (do une forte consommation de bande passante) et la distance parcourir doit tre faible. On peut augmenter un peu les distances grce lutilisation de rpteurs. Ceux-ci reforment le signal et le rendent nouveau carr. La valence est le nombre de niveaux possibles. Exemple : La Figure 3.1 montre un signal numrique de valence 4, car il y a 4 niveaux possibles de tension : V0 , V1 , V2 et V3 . Chaque niveau de tension a une dure identique . Thorme 3 (Nyquist) Si un signal V niveaux signicatifs est transmis avec une bande passante B , le dbit binaire maximal que lon puisse obtenir est : Dmax = 2Blog2 V .

Rseaux Partie 1

15

IUT R&T Villetaneuse

V (t) V3

V2 t V1

V0

Figure 3.1 Un signal numrique Transmission large bande Lorsque la longueur de la liaison dpasse quelques centaines de mtres, les informations ne peuvent plus tre transmises sur le support de liaison sans transformation du signal numrique en signal analogique. Dans une transmission large bande, les donnes modulent une onde porteuse sinusodale dont la frquence est bien plus leve que le rythme de transmission des donnes. Le codage est alors appel modulation et le dcodage est nomm dmodulation, do le nom de lappareil modem. Proprit 2 La transmission large bande permet de vhiculer une onde non carre, ayant peu de composantes spectrales. La bande des frquences utilises est alors plus faible, les distorsions du signal moins importantes. La distance entre metteur et rcepteur peut donc tre plus leve.

3.1.5

Rapidit de modulation

La rapidit de modulation est le nombre de changements dtats par seconde. Lunit de mesure de la rapidit de modulation R est le baud (du nom de Baudot, inventeur du tlex) : R= 1 bauds

o est lintervalle de temps entre deux changements de niveau, appel intervalle signicatif. Exemple : Supposons que, dans lexemple de la Figure 3.1, V0 code 00, V1 code 01, V2 code 10 et V3 code 11. Le signal reprsent est 10 00 11 10 11 00 01 10. Le dbit est de 2 bits toutes les 2 1 secondes, donc D = bits/s. La rapidit de modulation est R = bauds soit la moiti du dbit binaire. Si un tat transporte n bits, il faut un signal de valence V = 2n . On a alors un dbit D = nR. Comme n = log2 V : D = R log2 V

Rseaux Partie 1

16

IUT R&T Villetaneuse

3.2
3.2.1

Codage en bande de base

Phases du codage

Le codage comporte 2 phases : le codage logique et le codage physique. Le codage logique permet de pallier les dfauts du codage physique. Il transforme la suite de bits envoyer en une nouvelle suite au moins aussi longue. Les bits reus sont groups en paquets de ne bits, puis cods selon une table de transformation en paquets de ns bits, tels que ns ne . Soient De le dbit binaire lentre du codeur, et Ds celui la sortie. On a : Ds = ns De ne

Le codage physique produit les signaux sur la ligne. Il doit tre bien adapt au support de transmission. Proprit 3 Un bon code doit satisfaire au mieux les proprits suivantes : 1. Faible rapidit de modulation : Daprs le thorme de Nyquist (Thorme 3) Dmax = 2B log2 V , et la relation indiquant le dbit D = R log2 V , on obtient R 2B . Cette relation est appele critre de Nyquist. Elle indique que la largeur de bande du support limite la rapidit de modulation et donc le dbit maximal sur la ligne. 2. Limitation de la dsynchronisation : Pour que lhorloge du dcodeur reste synchrone avec celle du codeur, lintervalle de temps entre deux changements de niveau de signal doit tre le plus court possible. 3. Absence de composante continue : Les codeurs et dcodeurs physiques comportent des transformateurs et des amplicateurs qui suppriment la composante continue car elle peut endommager les quipements lectroniques prsents sur le support. 4. Absence de polarisation du support : Si lon utilise des paires torsades, il faut pouvoir croiser les ls sans avoir de consquence sur linformation code. Les Proprits 3(1) 3(4) ne peuvent pas tre satisfaites simultanment. Cest pourquoi un bon code doit faire des compromis.

3.2.2

Codage NRZ (No Return to Zero)

La valence du code NRZ est 2. Un bit 1 est traduit par un niveau v et un bit 0 par le niveau v . Le code NRZ vrie la Proprit 3(1) avec R = D, mais aucune des autres proprits. Cest un codeur physique et non un codeur logique. Exemple : Le codage NRZ de la squence de bits 1110 0001 1011 est reprsent dans la Figure 3.2. horloge 1 v t v Figure 3.2 Un codage NRZ 1 1 0 0 0 0 1 1 0 1 1

Rseaux Partie 1

17

IUT R&T Villetaneuse

3.2.3

Codage NRZI (No Return to Zero Inverted)

La valence du code NRZI est 2. Lorsque lon commence transmettre un bit 1, on change de niveau. Par contre, lorsque lon transmet un bit 0 le niveau prcdent est conserv. Le code NRZI vrie les Proprits 3(1), 3(4), et 3(2) pour les suites de 1. Il est utilis dans le codage 4b/5b (voir Section 3.2.7). Exemple : Le codage NRZI de la squence de bits 1110 0001 1011 est reprsent dans la Figure 3.3, en supposant que le niveau prcdent tait +v . horloge 1 v t v Figure 3.3 Un codage NRZI 1 1 0 0 0 0 1 1 0 1 1

3.2.4

Codage Manchester

Les codes Manchester sont des codes biphase, cest--dire quils associent un codage physique avec un codage logique. Le codage logique transforme 1 bit en 2 bits. Il est dit 1b/2b. La valence du code Manchester est 2. Un bit 1 est transform en deux bits 10, et un bit 0 est transform en 01. Aprs le codage logique, le codage physique NRZ est employ. La combinaison de ces deux codages implique une transition au milieu du bit dentre, comme on peut le constater sur lexemple de la Figure 3.4. La Proprit 3(2) est satisfaite, car lintervalle de temps le plus long entre deux changements 1 de niveau est Tb = D . La Proprit 3(1) est quasiment satisfaite, car le plus court intervalle de 2 b temps entre deux changements de niveau est = T 2 , donc R = Tb . Il ny a pas de composante continue, do la Proprit 3(3). Par contre, la Proprit 3(4) nest pas satisfaite car les bits sont polariss. Exemple : Le codage Manchester de la squence de bits 1110 0001 1011 est reprsent dans la Figure 3.4. horloge 1 v 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 t v Tb 1 1 0 0 0 0 1 1 0 1 1

Figure 3.4 Un codage Manchester

3.2.5

Codage Manchester direntiel

Le codage Manchester direntiel a, comme le codage Manchester, une valence 2 et emploie le codage NRZ comme codage physique. Le codage logique 1b/2b dpend du dernier bit gnr.
Rseaux Partie 1 18 IUT R&T Villetaneuse

Lorsque lon code un bit 1, on gnre 2 bits . Lorsque lon code un bit 0, on gnre 2 bits . La combinaison de ce codage et du NRZ implique une transition au milieu du bit dentre, plus une transition en dbut de bit lorsque lon transmet un 0, comme on peut le constater sur lexemple de la Figure 3.5. Ce code satisfait les quatre proprits requises pour un bon codage physique. Exemple : Le codage Manchester direntiel de la squence de bits 1110 0001 1011 est reprsent dans la Figure 3.5, en supposant que le dernier bit gnr tait = 1. horloge 1 v 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 t v Figure 3.5 Un codage Manchester direntiel 1 1 0 0 0 0 1 1 0 1 1

3.2.6

Codage biplaire

Le code biplaire est le code plusieurs niveaux le plus rpandu. Ces codes utilisent une valence > 2, souvent 3 (avec des niveaux v , 0 et v ) ou une puissance de 2. Le codage biplaire est principalement utilis pour coder la parole. Lors de la transmission dun bit 0 aucune impulsion nest envoye (le niveau reste 0). Lors de la transmission dun bit 1, une impulsion est mise durant la moiti dun bit, avec une polarisation inverse de celle prcdemment utilise, comme illustr sur la Figure 3.6. 2 La rapidit de modulation est T . En fait, les tats importants sont 0 et non-0. Ce code ne b vrie pas la Proprit 3(2). Il peut conduire de longues suites de 0. Il a par consquent t amlior en code biplaire haute densit. Un code biplaire dordre n limite nTb le plus grand intervalle de temps entre deux impulsions. Exemple : Le codage biplaire de la squence de bits 1110 0001 1011 est reprsent dans la Figure 3.6, en supposant que la dernire impulsion envoye tait +v . horloge 1 v t v Figure 3.6 Un codage biplaire 1 1 0 0 0 0 1 1 0 1 1

3.2.7

Codage 4b/5b

Le code 4b/5b est un code par blocs. Ceux-ci sont utiliss dans les rseaux dbit lev. Le codage 4b/5b est compos dun codage logique transformant 4 bits en 5 bits, puis du codage physique NRZI. Le codage logique utilise une table de codage (voir Table 3.1) conue de manire viter les longues suites de 0 (en fait il ny a pas plus de 3 bits 0 conscutifs). 5 La rapidit de modulation est 4T . La Proprit 3(1) est par consquent satisfaite. Pour vrier b 4 la Proprit 3(2), on considre le plus grand intervalle de temps entre deux niveaux : 4 5 Tb . La
Rseaux Partie 1 19 IUT R&T Villetaneuse

plus longue suite de 0 en comportant 3, elle est encadre par deux 1. On a donc la forme 10001, de longueur max = 4. Entre 0000 0001 0010 0011 Sortie 11110 01001 10100 10101 Entre 0100 0101 0110 0111 Sortie 01010 01011 01110 01111 Entre 1000 1001 1010 1011 Sortie 10010 10011 10110 10111 Entre 1100 1101 1110 1111 Sortie 11010 11011 11100 11101

Table 3.1 Table de codage 4b/5b

Exemple : Le codage 4b/5b de la squence de bits 1110 0001 1011 est reprsent dans la Figure 3.7, en supposant que le niveau prcdent tait +v . horloge 1 v 1 v Tb max = 4 Figure 3.7 Un codage 4b/5b =
4Tb 5

1 1 1

1 0

0 0

0 0 1

0 0

0 0

1 1

1 1 0

0 1

1 1

1 1 t

3.3

Modulation/dmodulation (codage large bande)

Le codage en bande de base ne peut pas tre utilis pour la transmission de donnes des vitesses trs leves ou sur de trs grandes distances. Le signal est dform car les hautes frquences sont attnues et les basses frquences altres par les rpteurs. Le bande passante tant rduite, il faut transformer le signal numrique en signal analogique par modulation dune onde porteuse. Les oprations de modulation en mission et de dmodulation en rception sont eectues par un modem (modulateur-dmodulateur). Comme en bande de base, un codage logique peut avoir lieu avant la modulation. Londe porteuse est une sinusode de frquence F0 et damplitude A0 . Il y a 3 principaux types de modulation lis aux 3 paramtres de la sinusode : modulation damplitude ; modulation de frquence ; modulation de phase.

3.3.1

Modulation damplitude

La modulation damplitude (en abrg AM Amplitude Modulation, ou ASK AmplitudeShift Keying) est la plus simple. Elle xe (au moins) 2 niveaux logiques lamplitude de la porteuse : A0 et A1 . Elle nest en gnral pas utilise seule, mais en conjonction avec une des deux autres mthodes de modulation. La Figure 3.8 montre un exemple de modulation damplitude.

Rseaux Partie 1

20

IUT R&T Villetaneuse

A1 A0 t A0 A1

Figure 3.8 Exemple de modulation damplitude

3.3.2

Modulation de frquence

En modulation de frquence (FM Frequency Modulation, ou FSK Frequency-Shift Keying), la porteuse de frquence F0 est module par deux valeurs opposes de frquence f1 et f1 , permettant ainsi la reprsentation de deux niveaux logiques. f1 t f1 1 0 1 Figure 3.9 Exemple de modulation de frquence

3.3.3

Modulation de phase

En modulation de phase (PSK Phase Key Shifting), la porteuse est de la forme A0 sin(2f t + ). Pour moduler la phase, on choisit des valeurs distinctes de . En utilisant des codes binaires dau moins 2 bits, on peut augmenter la rapidit de transmission sans augmenter la rapidit de modulation. Par exemple, pour une modulation sur 2 bits : 00 pour une phase 0, 01 pour une phase 2 , 11 pour une phase 2 et 10 pour une phase . La modulation PSK permet ainsi dobtenir des vitesses de transmission plus leves que la modulation FSK sur le mme support, pour une bande passante similaire.

Rseaux Partie 1

21

IUT R&T Villetaneuse

Chapitre 4

Dtection et Correction derreurs

4.1 Gnralits

Le support matriel utilis par la couche physique nest pas able 100%. Il est par consquent ncessaire de pouvoir dtecter des erreurs parmi la suite de bits reue, et ventuellement les corriger. Pour cela, la couche liaison de donnes de lmetteur ajoute des bits au message transmettre, qui permettent la couche liaison de donnes de lentit rceptrice du message de vrier la cohrence de ce quelle a reu. La couche liaison de donnes construit ainsi des LPDU, encore appeles trames, qui comportent en particulier un FCS (Frame Check Sequence). La problmatique des erreurs comporte 3 aspects : la dtection dune erreur ; la localisation de lerreur dtecte ; la correction de lerreur trouve. Pour rpondre ces problmes, on utilise des codes qui sont appliqus au message transmettre. Ils permettent de dtecter certaines erreurs, mais pas ncessairement toutes, et peu permettent la correction. Ces techniques ne sont donc pas compltement ables, dautant que le FCS, utilis pour vrier et corriger le message, peut lui aussi tre erron.

4.1.1

Un code simple : la rptition

Un approche nave consiste dupliquer (cest--dire rpter) le message transmettre. Supposons que le message eectivement transmis soit le double du message rel. Par exemple, pour envoyer 11100010, on transmet 1110001011100010. La dtection et la localisation des erreurs sont alors simples : on cherche les dirences entre la premire et la seconde moitis du message. Par contre, il est impossible de corriger une erreur dtecte : le bit erron est dirent dans les deux copies, et rien ne permet de dire lequel est le bon. Pour remdier ce problme, on peut envoyer les message en 3 exemplaires au lieu de 2. Dans ce cas, un bit a soit la mme valeur dans toutes les copies, ou la mme valeur dans deux dentre elles et lautre valeur dans la troisime copie. Le bit correct est celui qui apparat en deux exemplaires.

4.1.2

Inconvnients et problmes rencontrs

Le code de rptition est simple, mais prsente de nombreux inconvnients, illustrant ceux que lon peut rencontrer avec un quelconque code : La dtection et la correction derreurs ncessitent lintroduction de redondance dans les messages transmis. La taille du message transmettre peut alors augmenter de manire signicative. Certaines erreurs peuvent ne pas tre dtectes. Cest le cas lorsque lon utilise la redondance, si le mme bit est erron dans toutes les copies du message. 22

 Pour une raison similaire, certaines erreurs dtectes ne peuvent pas tre corriges, voire tre mal corriges. La correction ncessite plus de redondance que la dtection derreurs.

4.2
4.2.1

Dtection derreurs
Codes contrle de parit

Les codes contrle de parit sont de parit soit paire, soit impaire. Dans le premier cas, on va protger une squence de bits en ajoutant un nouveau bit de telle sorte que le nombre de bits ayant la valeur 1 (dans la squence protge plus le bit introduit) soit pair. Dans le second cas, ce nombre doit tre impair. VRC (Vertical Redundancy Check) Cest la technique la plus simple. Un code ASCII tant dni sur 7 bits, on utilise le 8me bit de loctet pour introduire le code vricateur. Exemple : Pour transmettre la chane de caractres IUT, on code chaque lettre en ASCII, puis on ajoute le code de parit. Lettre I U T ASCII 1001001 1010101 1010100 VRC pair 11001001 01010101 11010100 VRC impair 01001001 11010101 01010100

Pour envoyer le message avec un code de parit pair, on transmet (avec lordre denvoi des bits de gauche droite) : 11001001 01010101 11010100
I U T

Ce code permet de dtecter les erreurs en nombre impair sans pouvoir corriger. Il est peu ecace. LRC (Longitudinal Redundancy Check) Le principe est similaire celui du VRC, mais au lieu de protger les caractres un par un, on protge lensemble des bits de mme rang de tous les caractres. On obtient alors un code de protection sur 7 bits. Exemple : Pour protger IUT, on calcule le code : I U T LRC pair LRC impair 1001001 1010101 1010100 1001000 0110111

Pour envoyer le message avec un code de parit pair, on transmet : 1001001 1010101 1010100 1001000
I U T LRC

Lecacit du code LRC dpend fortement du message transmis.

Rseaux Partie 1

23

IUT R&T Villetaneuse

LRC+VRC On peut galement combiner les deux techniques prcdentes. On protge alors chaque caractre par un code VRC et lensemble des bits par un code LRC. On obtient donc un LRC sur 8 bits. La parit des LRC et VRC utiliss est la mme (tous les deux pairs ou tous les deux impairs). Exemple : Pour transmettre la chane de caractres IUT, on code chaque lettre en VRC puis en LRC : I U T LRC 1001001 1010101 1010100 VRC pair 11001001 01010101 11010100 01001000 VRC impair 01001001 11010101 01010100 00110111

Pour envoyer le message avec un code de parit pair, on transmet : 11001001 01010101 11010100 01001000
I U T LRC

4.2.2

Codes polynmiaux

Les codes polynmiaux, encore appels CRC (Cycling Redundancy Code), sont utiliss par la plupart des protocoles actuels. Un code polynmial est bas sur lutilisation dun polynme gnrateur G(x) connu lavance par la fois lmetteur et le rcepteur du message. Les polynmes manipuls sont binaires : tous les coecients sont 0 ou 1. Par consquent, un polynme gnrateur de degr k scrit sous la forme : G(x) = a0 a1 .x a2 .x2 a3 .x3 . . . ak .xk o i {0, . . . , k }, ai {0, 1} Le polynme G(x) est associ une valeur binaire. Exemple : La valeur binaire associe au polynme G(x) = x3 x 1 est 1011. Soit M le message (squence de bits) protger. Un polynme M (x) lui est associ : M = mn . . . m2 m1 m0 M (x) = mn .xn m2 .x2 m1 .x m0 Exemple : Au message M = 1101 est associ le polynme M (x) = x3 x2 1. Le calcul du CRC seectue dans le corps Z/2Z, cest--dire que : 11=0 xx=0 x = x Procdure de codage Soient : G(x) un polynme gnrateur de degr k ; M (x) le polynme associ au message M transmettre. La procdure de codage consiste : calculer P (x) = M (x).xk . Ceci correspond un dcalage de k bits (vers la gauche) du message M . La longueur du CRC calcul sera aussi de k bits. Cette opration de dcalage revient prparer la place ncessaire pour ces k bits de CRC.
Rseaux Partie 1 24 IUT R&T Villetaneuse

 diviser le polynme P (x) par G(x). Soient Q(x) et R(x) les polynmes quotient et reste ainsi obtenus : P (x) = Q(x).G(x) R(x) le CRC est le reste R(x) ainsi calcul. On remarque que le reste est forcment au maximum de degr k 1. le message eectivement transmis est associ au polynme M (x) = P (x) R(x). Il est par consquent compos du message initial M suivi de la squence de k bits correspondant R(x). Exemple : Soient le polynme gnrateur G(x) = x3 x 1 et le message envoyer M = 1101. Le polynme correspondant au message est M (x) = x3 x2 1. Le degr de G(x) est 3. Donc, P (x) = M (x).x3 = x6 x5 x3 . Eectuons la division de P (x) par G(x) : x6 x6 x5 x5 x5 x x4 x x4
4 4

x 3 x 3 x 3 x 3 x3 x3 x 2 x 2 x 2

x3 x 1 x3 x2 x 1

x x x

1 1

Le quotient est donc Q(x) = x3 x2 x 1, et le reste R(x) = 1. Le message transmis a alors pour polynme M (x) = x6 x5 x3 1, do M = 1101001. Caractristiques, dcodage et erreurs Proprit 4 1. Un message M transmis correctement a un polynme M (x) divisible par le polynme gnrateur G(x). 2. Si G(x) comporte au moins 2 termes, les erreurs simples sont dtectables. 3. Si G(x) a un facteur irrductible de 3 termes, les erreurs doubles sont dtectables. 4. Si G(x) est un multiple de x 1, les erreurs en nombre impair sont dtectables. La qualit du codage dpend donc du choix du polynme gnrateur G(x). Lorsque lon reoit un message M , deux cas peuvent se prsenter : M (x) est divisible par G(x) : le CRC ne permet pas de dtecter une erreur. Il y a de fortes chances que le message reu soit correct. M (x) nest pas divisible par G(x) : une erreur est dtecte. Le message initial M est obtenu en ignorant les k derniers bits de M (cest--dire en eectuant un dcalage droite de k bits sur M ). Le code polynmial ne permet pas de corriger les erreurs.

4.3

Correction derreurs

Deux approches permettent de corriger les erreurs : les codes auto-correcteurs, tels que le code de Hamming (voir Section 4.3.1) ; la correction par retransmission (voir Section 4.3.2), qui demande lmetteur de retransmettre le message lorsquune erreur est dtecte.
Rseaux Partie 1 25 IUT R&T Villetaneuse

4.3.1

Code de Hamming

Le code de Hamming est calcul partir dune mesure de dissimilarit entre deux squences de bits de mme longueur, appele distance de Hamming. Dnition 9 (distance de Hamming) La distance de Hamming entre deux squences binaires m1 et m2 de mme taille est le nombre de bits de mme rang par lesquels ces deux squences dirent. Elle est note d(m1 , m2 ). Exemple : d(1100110, 1010110) = 2. Dnition 10 (distance dun code) Soit un code C comportant n squences valides. La distance de Hamming du code C est la distance minimale sparant deux mots valides du code. Elle est note d(C ). Proprit 5 Un code de distance d(C ) dtecte d(C ) 1 erreurs et corrige k =
d(C )1 2

erreurs.

Exemple : Supposons que lon souhaite transmettre des messages pouvant se coder comme lune des squences du code : C = {000000, 001110, 011011, 100011, 101101}. d(C ) = min(c1 ,c2 )C 2 d(c1 , c2 ) = 3. Avec ce code, on peut dtecter au maximum d(C ) 1 = 2 erreurs et en corriger k = d(C2)1 = 1.

4.3.2

Demande de retransmission

Lorsque lon eectue de la correction par demande de retransmission, lmetteur conserve une copie des donnes envoyes. Le rcepteur applique une mthode de dtection des erreurs. Quand il reoit un message, le rcepteur renvoie un paquet lmetteur, contenant un acquittement positif si aucune erreur na t dtecte, et un acquittement ngatif si une erreur a t trouve. Lors de la rception dun acquittement ngatif, lmetteur retransmet le message erron. Un message pouvant tre perdu lors de la transmission, et donc ne jamais tre acquitt, que ce soit positivement ou ngativement, lmetteur utilise un temporisateur qui permet de xer un temps dattente limite pour la rception dun acquittement. Quand le temporisateur arrive expiration, si aucun acquittement na t reu, il est trs probable que soit le message lui-mme a t perdu, soit son acquittement a t perdu. Par consquent, lmetteur renvoie son message. Pour assurer le bon fonctionnement dun tel mcanisme, il est ncessaire didentier les messages transmis, par exemple en les numrotant.

Rseaux Partie 1

26

IUT R&T Villetaneuse