Informatique II

Informatique II - Travaux Pratiques



Série d'exercices no 8

Exercice 8-1 : Code de répétition

On utilise un code de répétition. Les bits sont envoyés 5 fois avec une probabilité p d'être mal transmis.

Dans un tel paquet de 5 bits (c.a.d. 5 répétitions du bit de signal)

  1. Quelle est la probabilité que 0,1,2,...,ou 4 des ces 5 bits sont changés lors de la transmission?
  2. Quelle est la probabilité que l'erreur de transmission soit détectée ?
  3. Quelle est la probabilité que l'erreur soit transmise sans être détectée ?
  4. Coder le message suivant : 01110
  5. Décoder le message suivant : 00100111110001011001
  6. Quel est le taux de transmission d'un tel code ?
Pour améliorer la fiabilité, on décide d'utiliser un code avec 9 répétitions.
  1. Quel est le taux de transmission d'un tel code ?
  2. Quelle est la probabilité de faire 5 erreurs ?
  3. Montrer que pour p=0.001, la probabilité de faire 6 erreurs est beaucoup plus petite que celle de faire 5 erreurs. (C'est pourquoi les cas de faire 6,7,8, ou 9 erreurs ne jouent pas de rôle et peuvent être négligé par rapport au cas de 5 erreurs).
  4. Pour p=0.001, évaluer la probabilité qu'une erreur soit transmise sans être détectée ? Comparer les résultats des codes avec 5 et 9 répétitions.

Exercice 8-2 : Contrôle de parité

  1. Combien d'erreurs peuvent-elles être détectées grâce à un contrôle simple de parité? Est-il possible de corriger ces erreurs ?
  2. Coder les messages suivants à l'aide d'un parity bit :
  3. Quelle sont les taux de transmission des trois messages ci-dessus ?

Exercice 8-3 : Code de Hamming

Lors d'un transfert de données, vous reçevez les messages suivants codés grâce au code Hamming(7,4). Des erreurs s'y sont insérées. Retrouvez-les et et corrigez-les, les erreurs pouvant figurer dans le message aussi bien que dans les bits de parité.

Exercice 8-4 : Code de Hamming

On considère un code de Hamming(7,4).
  1. Coder le message suivant : 010110010111
  2. Décoder le message suivant : 010001110010101101001
  3. Quel est le taux de transmission du code Hamming(7,4) ?

Exercice 8-5 : Code de Hamming

On considère un code de Hamming(7,2).
  1. Combien de parity bits sont-ils utilisés ?
  2. Combien de possibilités existe-t-il de faire 0,1,2,...,k erreurs ?
  3. Combien d'erreurs ce code peut-il détecter ?
  4. Quelles sont les probabilités correspondant à la présence de 0,1,2,...,k erreurs ?

Exercice 8-6: Taille de paquets et taux de transfert (à la maison)

L'objet de cet exercice est de comparer les taux de transmission et la fiabilité d'un code par répétition et un code de Hamming. Le but est de démontrer que dans le cas d'un canal bruité, émettre des paquets longs est plus efficace qu'émettre des paquets courts. On désire transmettre un message de 10,000 bits à travers un canal bruité. On considère un ``flip noise'' de probabilité p = 0.01 .

Codage par répétition

Chaque bit est émis trois fois. Le décodage se fait par un vote à la majorité.

Paquets de 9 bits

On considère un code Hamming(9,3). Le message est envoyé sous forme de paquets de 9 bits, de la forme (s1, s2, s3, t1, t2, t3, t4, t5, t6) . Les trois premiers bits s1, s2, s3 constituent le message original, les six suivants t1, ... , t6 sont les bits de contrôle.

Conclusion Expliquer pourquoi transmettre un message en longs paquets est plus efficace que de le transmettre en paquets courts. Pourquoi la répétition n'est-elle pas une bonne idée ?
retour à la page principale du cours: Informatique II

Saskia Delpretti
Last modified: Wed Mar 10 12:30:44 CET 2004