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)
- Quelle est la probabilité que 0,1,2,...,ou 4 des ces 5 bits
sont changés lors de la transmission?
- Quelle est la probabilité que l'erreur
de transmission soit détectée ?
- Quelle est la probabilité que l'erreur soit transmise sans être détectée ?
- Coder le message suivant : 01110
- Décoder le message suivant : 00100111110001011001
- 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.
- Quel est le taux de transmission d'un tel code ?
- Quelle est la probabilité de faire 5 erreurs ?
- 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).
- 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é
- Combien d'erreurs peuvent-elles être détectées grâce à un
contrôle simple de parité? Est-il possible de corriger ces erreurs ?
- Coder les messages suivants à l'aide d'un parity bit :
- 1101011001
- 100
- 11111000111001111
- 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é.
- 0101000
- 1110010
- 1100011
- 1011011
- 1101011
- 1000011
Exercice 8-4 : Code de Hamming
On considère un code de Hamming(7,4).
- Coder le message suivant : 010110010111
- Décoder le message suivant : 010001110010101101001
- 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).
- Combien de parity bits sont-ils utilisés ?
- Combien de possibilités existe-t-il de faire 0,1,2,...,k erreurs ?
- Combien d'erreurs ce code peut-il détecter ?
- 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é.
- Quel est le taux de transmission ?
- Quelle est la probabilité que le décodage soit incorrect ?
- Combien des 10,000 bits du message ne sont pas
correctement transmis ?
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.
- Quel est le taux de transmission ?
- Combien de configurations différentes des bits de contrôle existe-il ?
- Combien y a-t-il de configuration possible de 0 , 1 , ou 2
erreurs dans un tel paquet de 9 bits ?
- Supposons qu'il existe un codage tel que les 6 bits de
contrôle puissent localiser toutes les configurations jusqu'à deux
erreurs. Quelle est alors la probabilité qu'un tel paquet de 9 bits ne
soit pas décodé correctement ?
- Combien des 10,000 bits du message ne sont pas
transmis correctement ?
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