Travaux Dirigs de rseau no1 e e
Cours darchitecture des rseaux e Master dinformatique
Codage
Les exercices prsentent quelques notions lmentaires de codage. e ee
Exercice 1. Codage et dbit e Lobjectif de lexercice est de calculer le dbit thorique maximal dune ligne e e tlphonique. Les lectroniciens expriment en dcibels (dB) la part de bruit dans un ee e e signal reu (rapport S/B). Les dcibels sont une unit logarithmique : quand x croit c e e exponentiellement, (x)dB (en dcibel) croit linairement. Cette conversion dune valeur e e sans unit en dcibel est ralise en appliquant la formule (x)dB = 10 log10 (x). e e e e Sachant que dans le cas dune ligne tlphonique (S/B)dB = 30dB , quelle est la ee part du bruit dans le signal reu ? c Nyquist puis Shanon ont tudis dans la premi`re moiti du 20e si`cle le dbit de e e e e e e transmission des supports bruits. La formule Dbits/s = FHz log2 (1+S/B) donne le dbit e e binaire maximal dun canal bruit. Dans cette formule, F dsigne la bande passante e e en Hertz utilisable dans le canal. Les frquences audibles par un tre humain varient e e de 20 a 20000Hz. Cependant dans une transmission tlphonique seules les frquences ` ee e allant de 300 a 3400Hz sont conserves. Calculez le dbit maximal thorique dune ` e e e ligne tlphonique. ee Comparez le dbit obtenu avec le dbit de 56kbits/s, ach par les modems actuels. e e e Essayez dexpliquer. Exercice 2. Codage binaire On veut faire communiquer deux machines lectroniques par lintermdiaire dun l e e lectrique. On dispose pour cela dun peu de matriel : des composants pouvant fournir e e une tension de plus ou moins T volts et une horloge de frquence f . Les deux machines e doivent senvoyer des suites binaires. Proposer des codages de ces suites en fonction des proprits du canal et du matriel fourni. ee e Dans la vie relle les composants lectronique ne peuvent fournir une tension donne e e e que pendant un temps limit (court). e
Quels sont les probl`mes que cela pose pour le codage ? e Comment les rsoudre ? e Un autre probl`me appara lorsque lhorloge nest pas transmise sur un canal e t spar : les horloges nont pas toutes exactement la mme frquence. Quels sont les e e e e probl`mes que cela pose pour le codage ? Comment les rsoudre ? e e Exercice 3. Codes Les ensembles de mots {1, 00, 01, 10}, {00, 01, 11, 101, 1001, 1000} sont-ils des codes ?
{0000, 0011, 1100, 1111}
et
Exercice 4. Dtection derreurs avec code de taille xe e Quelle est la distance de Hamming du code {0000, 0011, 1100, 1111} ? Supposons que lon dispose dun canal bruit dont on sait que sur n bits certains e peuvent comporter des erreurs (valeur change) a cause du bruit sur le canal. e ` Donner une mthode qui, si exactement une erreur sest produite pendant la transe mission de n bits, permet au rcepteur de la dtecter. e e Quelle est la distance de Hamming de votre code ? Combien y a-t-il de mots dans votre code ? Que se passe-t-il sil y a plus dune erreur ? Les erreurs proviennent de perturbations du canal et sont rarement isoles. Les e erreurs surviennent donc par rafales. Une rafale derreur de longueur k est une suite de k bits dont certains peuvent ventuellement tre faux. Donner une mthode utilisant e e e les bits de parit pour transmettre des suites de n bits avec possibilit de dtecter des e e e rafales de k erreurs. Quelle doit tre la distance de Hamming minimale dun code dtecteur de k ere e reurs ? Exercice 5. Code de Redondance Cyclique On utilise pour une transmission avec dtection derreurs un Code de Redondance e Cyclique (CRC) de polynme gnrateur x4 + x + 1. Lmetteur veut mettre la suite o e e e e 1101011011. Quelle suite va eectivement tre mise dans le canal ? e Prouvez que si la factorisation du polynme gnrateur dun CRC comporte x + 1 o e e alors le CRC dtecte un nombre impair derreurs. e Exercice 6. Codes correcteurs de taille xe Lorsquune erreur survient au cours de la transmission dune suite de bits, si la transmission utilise un code dit correcteur, le destinataire a la possibilit de corriger luie mme lerreur sans redemander la retransmission de la suite a lmetteur. Donner des e ` e
exemples dutilisation o` on prfrera des codes correcteurs aux codes dtecteurs ou u ee e inversement. Proposez un code permettant de corriger une erreur de transmission dun groupe de bits disposs en matrice. On pensera a utiliser des bits de parit. e ` e Quelle doit tre la distance de Hamming minimale dun code correcteur de k ere reurs ? Discutez les proprits de dtection derreur dun tel code. ee e On veut transmettre dans un canal bruit des suites de m bits en utilisant un code e permettant de corriger k erreurs. En comparant le nombre le nombre derreurs sur chaque code au nombre de valeurs qui peuvent tre codes par un suite de n bits, e e donner une ingalit que doit respecter le nombre de bits de contrle ? e e o Thoriquement, combien faut-il ajouter, au minimum, de bits de contrle pour e o transmettre 7 bits dinformation utile avec une capacit de correction de 1 bit ? e Exercice 7. Code correcteur de Hamming Le code correcteur de Hamming le plus courant utilise des bits de contrle aux positions o 2i (1, 2, 4, etc.). Dans ce code, si r est le nombre de bits de contrle, la valeur du bit de o r1 contrle a la position 2i est gale a la somme des bits dont la position scrit j=0 bj 2j , o ` e ` e avec bi = 1 et bj=i {0, 1}. Par exemple, pour le bit de contrle 2 = 21 (i = 1), si o r = 3 alors la valeur du bit a la position 2 est gal a la somme des bits aux positions ` e ` 3 = 1 20 + 1 21 , 6 = 1 21 + 1 22 et 7 = 1 20 + 1 21 + 1 22 . On utilise un tel code correcteur de Hamming 7/4 (on transmet 7 bits utiles avec 4 bits de contrle) pour transmettre 1100001. Quelle est la suite eectivement transmise ? o Sachant que la valeur reue : 10110001001, contient une seule erreur, retrouver o` c u elle a eu lieu et la suite de bits initialement transmise.