:: Enseignements :: Licence :: L3 :: 2008-2009 :: Réseau ::

Codage

Les exercices présentent quelques notions élémentaires de codage.

Exercice 1 - Codage et débit

L'objectif de l'exercice est de calculer le débit théorique maximal d'une ligne téléphonique. Les électroniciens expriment en décibels (dB) la part de bruit dans un signal reçu (rapport $\frac{S}{B}$ ). Les décibels sont une unité logarithmique: quand

croit exponentiellement, $(x)_{dB}$ (en décibel) croit linéairement. Cette conversion d'une valeur sans unité en décibel est réalisée en appliquant la formule $(x)_{dB}=10\log_{10}(x)$ .

Sachant que dans le cas d'une ligne téléphonique $(\frac{S}{B})_{dB}=30\mathit{dB}$ , quelle est la part du bruit dans le signal reçu ?
Nyquist puis Shannon ont étudiés dans la première moitié du siècle le débit de transmission des supports bruités. La formule $D_{bits/s}=F_{Hz}\log_2(1+\frac{S}{B})$ donne le débit binaire maximal d'un canal bruité. Dans cette formule, désigne la bande passante en Hertz utilisable dans le canal. Les fréquences audibles par un être humain varient de à . Cependant dans une transmission téléphonique seules les fréquences allant de à sont conservées. Calculez le débit maximal théorique d'une ligne téléphonique.
Comparez le débit obtenu avec le débit de , affiché par les modems actuels. Essayez d'expliquer.

Exercice 2 - Codage binaire

On veut faire communiquer deux machines électroniques par l'intermédiaire d'un fil électrique. On dispose pour cela d'un peu de matériel: des composants pouvant fournir une tension de plus ou moins

volts et une horloge de fréquence

. Les deux machines doivent s'envoyer des suites binaires.

Proposer des codages de ces suites en fonction des propriétés du canal et du matériel fourni.
Dans la vie réelle les composants électronique ne peuvent fournir une tension donnée que pendant un temps limité (court). Quels sont les problèmes que cela pose pour le codage ?
Comment les résoudre ?
Un autre problème apparaît lorsque l'horloge n'est pas transmise sur un canal séparé: les horloges n'ont pas toutes exactement la même fréquence. Quels sont les problèmes que cela pose pour le codage? Comment les résoudre?

Exercice 3 - Codes

Un code sur un alphabet A est un ensemble de mots C tel qu'aucun mot de A* ne puisse s'écrire de deux façons différentes comme combinaison de mots de C.
Remarque: on ne demande pas que tous les mots de A* soient représentables comme concaténations de mots de C.

Les ensembles de mots $\{1,00,01,10\}$ , $\{0000,0011,1100,1111\}$ et $\{00,01,11,101,1001,1000\}$ sont-ils des codes ?

Exercice 4 - Détection d'erreurs avec code de taille fixe

Quelle est la distance de Hamming du code $\{0000,0011,1100,1111\}$ ?
Supposons que l'on dispose d'un canal bruité dont on sait que sur bits certains peuvent comporter des erreurs (valeur changée) à cause du bruit sur le canal.
Donner une méthode qui, si exactement une erreur s'est produite pendant la transmission de bits, permet au récepteur de la détecter.
Quelle est la distance de Hamming de votre code ?
Combien y a-t-il de mots dans votre code?
Que se passe-t-il s'il y a plus d'une erreur ?
Les erreurs proviennent de perturbations du canal et sont rarement isolées. Les erreurs surviennent donc par rafales. Une rafale d'erreur de longueur est une suite de bits dont certains peuvent éventuellement être faux. Donner une méthode utilisant les bits de parité pour transmettre des suites de bits avec possibilité de détecter des rafales de erreurs.
Quelle doit être la distance de Hamming minimale d'un code détecteur de erreurs ?

Exercice 5 - Code de Redondance Cyclique

On utilise pour une transmission avec détection d'erreurs un Code de Redondance Cyclique (CRC) de polynôme générateur G(x)=x^4+x+1

. L'émetteur veut émettre la suite 1101011011

. Quelle suite va effectivement être mise dans le canal ?

Exercice 6 - Codes correcteurs de taille fixe

Lorsqu'une erreur survient au cours de la transmission d'une suite de bits, si la transmission utilise un code dit correcteur, le destinataire a la possibilité de corriger lui-même l'erreur sans redemander la retransmission de la suite à l'émetteur. Donner des exemples d'utilisation où on préférera des codes correcteurs aux codes détecteurs ou inversement.
Proposez un code permettant de corriger une erreur de transmission d'un groupe de bits disposés en matrice. On pensera à utiliser des bits de parité.
Quelle doit être la distance de Hamming minimale d'un code correcteur de erreurs ?
Discutez les propriétés de détection d'erreur d'un tel code.
On veut transmettre dans un canal bruité des suites de bits en utilisant un code permettant de corriger erreurs. En comparant le nombre d'erreurs sur chaque code au nombre de valeurs qui peuvent être codées par une suite de bits, donner une inégalité que doit respecter le nombre de bits de contrôle?
Théoriquement, combien faut-il ajouter, au minimum, de bits de contrôle pour transmettre 7 bits d'information utile avec une capacité de correction de 1 bit ?