Français
Menu

Bases de la théorie de l'information et du codage

Apprenez la théorie de l'information et le codage avec des QCM centrés sur le calcul : quantité d'information et entropie, information mutuelle, redondance, codes de longueur fixe et de longueur variable, codes préfixes et inégalité de Kraft, longueur moyenne de code et efficacité des codes de Huffman, codage par plages, méthode LZ77, compression sans perte et avec perte, parité et parité verticale et horizontale, sommes de contrôle, calcul d'un CRC, distance de Hamming et capacité de détection et de correction d'erreurs, codes de Hamming et SECDED, rendement du code, entrelacement, ARQ et FEC, capacité du canal binaire symétrique, théorème du codage de canal et conversion du code de Gray.

S'entraîner sur 10 questionsQuestions aléatoires de ce thème · environ 5 minutes S'entraîner sur ce thèmeToutes les questions de ce thème dans un ordre aléatoire Questions à revoirNe refaire que les questions manquées lors de la dernière tentative

Bases de la théorie de l'information et du codage : points clés

« Combien de bits vaut cette information ? » « Jusqu'où peut-on réduire ces données ? » « Comment trouver et corriger les bits altérés par le bruit ? » La théorie de l'information et la théorie des codes, fondées par Shannon, répondent à ce genre de questions. Elles sont à l'œuvre partout dans les ordinateurs et les communications : compression de fichiers, ECC des mémoires, correction d'erreurs sur les canaux de communication, CRC des dispositifs de stockage, etc.

Ce thème vérifie par le calcul la quantité d'information −log₂ p et l'entropie, la condition pour laquelle l'entropie est maximale, l'entropie conditionnelle et l'information mutuelle, la redondance et le nombre de bits nécessaire pour distinguer des éléments. Il aborde ensuite les codes de longueur fixe et de longueur variable, les codes préfixes et l'inégalité de Kraft, la construction d'un code de Huffman et sa longueur moyenne de code, l'efficacité par rapport à l'entropie, l'effet du codage des symboles par groupes, le codage par plages et la méthode LZ77, ainsi que le choix entre compression sans perte et compression avec perte. La seconde partie traite de la parité et de la parité verticale et horizontale, de la faiblesse des sommes de contrôle, du calcul des bits de contrôle d'un CRC et de la détection des erreurs en rafale, de la distance de Hamming et du nombre de bits erronés détectables et corrigibles, de la localisation d'une erreur par le syndrome du code de Hamming (7, 4), du nombre de bits de contrôle du SECDED, du rendement du code, de l'entrelacement, de l'ARQ et de la FEC, ainsi que de la capacité du canal binaire symétrique et du théorème du codage de canal, et se termine par la conversion du code de Gray. Il aide aussi à préparer la partie théorie de base (théorie de l'information et théorie des communications) des examens de certification informatique. Les valeurs des questions de calcul, y compris celles des choix erronés et les arbres de Huffman, ont été vérifiées par un calcul en Python. Les nombres binaires et la virgule flottante sont traités dans « Arithmétique des ordinateurs », le calcul d'un bit de parité et les propriétés du code de Gray dans « Circuits logiques », la conversion du binaire en code de Gray dans « Analyse temporelle et CDC », la probabilité des erreurs que la parité laisse passer dans « Probabilités, statistiques et files d'attente », la capacité du canal selon le théorème de Shannon-Hartley dans « Bases des communications sans fil », l'ECC des mémoires dans « DRAM », le codage 8b/10b et le CRC de PCI Express dans « Interfaces d'E/S et bus », Base64 et gzip dans « Bases des technologies web », l'entropie croisée dans « Bases de l'apprentissage automatique », et les fonctions de hachage et la cryptographie dans « Bases de la sécurité de l'information ».

Toutes les questions sur Bases de la théorie de l'information et du codage (40)
  1. Soit −log₂ p bits la quantité d'information obtenue lorsqu'on apprend qu'un événement de probabilité p s'est produit. Quelle est la quantité d'information obtenue lorsqu'on apprend qu'un événement de probabilité 1/8 s'est produit ?
  2. Quelle propriété de la quantité d'information (−log₂ p lorsqu'on apprend qu'un événement de probabilité p s'est produit) est correcte ?
  3. Une source émet les symboles A, B, C et D indépendamment les uns des autres avec les probabilités 1/2, 1/4, 1/8 et 1/8. Quelle est l'entropie (quantité d'information moyenne par symbole) de cette source ?
  4. Quelle association entre l'entropie maximale d'une source qui émet 8 sortes de symboles et la condition dans laquelle ce maximum est atteint est correcte ?
  5. Une source binaire émet 0 avec la probabilité 0,9 et 1 avec la probabilité 0,1, indépendamment. On prend log₂ 0,9 ≈ −0,152 et log₂ 0,1 ≈ −3,32. Quelle valeur est la plus proche de l'entropie de cette source ?
  6. Une source qui émet 8 sortes de symboles a une entropie de 2,4 bits. Si l'on définit la redondance comme 1 − (entropie ÷ entropie maximale), quelle est la redondance de cette source ?
  7. Pour deux variables aléatoires X et Y, quelle description de l'entropie conditionnelle H(X|Y) et de l'information mutuelle I(X;Y) est correcte ?
  8. Deux variables aléatoires X (valeur 0 ou 1) et Y (valeur a, b ou c) ont les probabilités conjointes P(0, a) = P(0, b) = P(1, b) = P(1, c) = 1/4, et toute autre combinaison a la probabilité 0. Quelle est l'information mutuelle I(X;Y) ?
  9. Les 36 caractères formés des 26 lettres majuscules et des 10 chiffres doivent être distingués par des suites de bits toutes de même longueur (un code de longueur fixe). Quel est le nombre minimal de bits nécessaire par caractère ?
  10. Par rapport à un code de longueur fixe, quelle description d'un code de longueur variable est correcte ?
  11. Parmi les ensembles de mots de code suivants, attribués à quatre symboles, lequel est un code préfixe (code dans lequel aucun mot de code n'est le début d'un autre mot de code) ?
  12. Un code préfixe attribue les mots de code A = 0, B = 10, C = 110 et D = 111 aux symboles A, B, C et D. Quel est le résultat du décodage de la suite de bits 110100111 depuis le début ?
  13. On veut construire un code préfixe binaire en attribuant aux quatre symboles A à D des mots de code des longueurs (nombres de bits) suivantes. Quelle combinaison de longueurs de code le permet ?
  14. On construit un code préfixe binaire dans lequel les mots de code 00 et 01, de longueur 2, sont déjà utilisés. Quel est le nombre maximal de mots de code de longueur 3 que l'on peut ajouter en conservant la condition de préfixe ?
  15. Une source émet les symboles A, B, C et D indépendamment avec les probabilités 0,4 ; 0,3 ; 0,2 et 0,1, et on la code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole ?
  16. Une source émet les symboles A à E indépendamment avec les probabilités 0,3 ; 0,25 ; 0,2 ; 0,15 et 0,1, et on la code avec un code de Huffman. Les mots de code peuvent changer selon celle de deux probabilités égales que l'on choisit en premier, mais pas la longueur moyenne de code. Quelle est la longueur moyenne de code par symbole ?
  17. Une source émet les symboles A, B et C indépendamment avec les probabilités 0,6 ; 0,3 et 0,1, et son entropie vaut environ 1,30 bit. Quelle valeur est la plus proche de l'efficacité (entropie ÷ longueur moyenne de code) lorsque cette source est codée avec un code de Huffman ?
  18. Une source binaire émet 0 avec la probabilité 0,8 et 1 avec la probabilité 0,2, indépendamment. On regroupe les symboles deux par deux, on traite chacun des quatre couples 00, 01, 10 et 11 comme un seul symbole, et on les code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole d'origine ?
  19. Quelle description de la relation entre la compression sans perte et l'entropie d'une source est correcte ?
  20. La chaîne de 40 caractères AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 A, 4 B, 20 C et 4 D) est compressée avec le codage par plages, qui représente chaque suite d'un même caractère par un couple « caractère (1 octet) et nombre (1 octet) ». La chaîne d'origine utilise 1 octet par caractère. Si l'on définit le taux de compression comme « taille après compression ÷ taille avant compression », quel est le taux de compression ?
  21. Quelles données le codage par plages a-t-il le plus de chances de rendre les plus petites ?
  22. Quelle description de l'idée de la méthode LZ77, utilisée dans ZIP, gzip et des outils similaires, est correcte ?
  23. On veut restaurer des données compressées par la méthode LZ77. Les données se composent, dans cet ordre, de « caractère A », « caractère B » et « (distance 2, longueur 5) ». (distance d, longueur L) signifie répéter L fois, un caractère à la fois, l'opération « copier à la fin de la chaîne restaurée le caractère situé d caractères avant sa fin ». Quelle est la chaîne restaurée ?
  24. Lors de la compression de données, dans lequel des cas suivants faut-il utiliser une compression sans perte plutôt qu'une compression avec perte ?
  25. On ajoute à une suite de bits de données un seul bit de parité paire, de sorte que le nombre de 1 soit pair, et le récepteur vérifie le nombre de 1. Quelle description de ce contrôle est correcte ?
  26. Quatre lignes de 4 bits de données ont été envoyées avec, à l'extrémité droite de chaque ligne, un bit de parité paire pour cette ligne, puis une dernière ligne de bits de parité paire pour chaque colonne (parité verticale et horizontale). Les bits reçus étaient ligne 1 : 1011 1, ligne 2 : 0100 0, ligne 3 : 1100 0, ligne 4 : 0101 0 et ligne de parité : 0100 (le bit le plus à droite de chaque ligne est la parité de cette ligne). Si exactement un bit est erroné, quelle est sa position ?
  27. On additionne les données octet par octet et on envoie avec elles les 8 bits de poids faible de la somme comme valeur de contrôle (somme de contrôle). Laquelle des erreurs suivantes ce contrôle ne peut-il pas détecter ?
  28. On veut ajouter aux données 1101 les 3 bits de contrôle d'un CRC de polynôme générateur x³ + x + 1 (suite de bits 1011). Les bits de contrôle sont le reste de la division de 1101000, les données suivies de trois 0, par 1011, en utilisant le OU exclusif au lieu de la soustraction dans la division. Quels sont les bits de contrôle ?
  29. Quelle description d'un CRC dont le polynôme générateur est de degré r (r bits de contrôle) et a un terme constant égal à 1 est correcte ?
  30. Quelle est la distance de Hamming entre les deux mots de code de 7 bits 1011010 et 0110011 ?
  31. La distance de Hamming minimale d'un code (la plus petite distance de Hamming entre deux mots de code quelconques) vaut 5. On envisage de l'utiliser uniquement pour la détection d'erreurs, ou uniquement pour la correction d'erreurs. Quelle association entre le nombre de bits erronés toujours détectables et le nombre de bits erronés toujours corrigibles est correcte ?
  32. Quelle association entre la distance de Hamming minimale du code formé des quatre mots de code 00000, 01011, 10101 et 11110 et le nombre de bits erronés qu'il peut toujours corriger est correcte ?
  33. Quelle valeur est la plus proche du rendement du code de Hamming (7, 4), qui ajoute 3 bits de contrôle à 4 bits de données pour former un mot de code de 7 bits ?
  34. Dans un code de Hamming (7, 4), les sept bits sont numérotés de 1 à 7 à partir de la gauche, et les bits 1, 2 et 4 sont les bits de contrôle. Ils sont fixés de sorte que le nombre de 1 soit pair dans les bits 1, 3, 5 et 7 (contrôle 1), dans les bits 2, 3, 6 et 7 (contrôle 2) et dans les bits 4, 5, 6 et 7 (contrôle 4). Si le mot reçu 0110001 contient une erreur sur 1 bit, quel est le bit erroné ?
  35. On ajoute à 32 bits de données un code SECDED, qui corrige les erreurs sur 1 bit et détecte les erreurs sur 2 bits. Le nombre r de bits de contrôle d'un code de Hamming est la plus petite valeur qui satisfait 2^r ≥ nombre de bits de données + r + 1, et le SECDED y ajoute 1 bit de parité globale. Combien de bits de contrôle faut-il ?
  36. Cinq mots de code du code de Hamming (7, 4) sont alignés et envoyés dans l'ordre suivant : le bit 1 de chacun des cinq mots de code, puis le bit 2 de chacun, et ainsi de suite (entrelacement de profondeur 5). Le récepteur rétablit l'ordre d'origine puis corrige une erreur sur 1 bit dans chaque mot de code. Quelle est la longueur maximale d'une erreur en rafale, concentrée sur des bits consécutifs, qui peut toujours être corrigée ?
  37. Quelle description de l'ARQ (demande de répétition automatique) et de la FEC (correction d'erreurs directe), méthodes de traitement des erreurs dans les communications, est correcte ?
  38. Dans un canal binaire symétrique, on envoie des 0 et des 1, et chaque bit s'inverse indépendamment avec la probabilité 0,1. Avec l'entropie binaire H(p) = −p log₂ p − (1 − p) log₂(1 − p), on a H(0,1) ≈ 0,469. Quelle valeur est la plus proche de la capacité du canal par transmission ?
  39. Quel énoncé du théorème du codage de canal de Shannon est correct ?
  40. Pour convertir un code de Gray en nombre binaire ordinaire, on garde tel quel le bit de poids fort, et chaque bit de rang inférieur s'obtient comme le OU exclusif du bit binaire déjà trouvé au rang immédiatement supérieur et du bit du code de Gray au même rang. Quel est le code de Gray de 4 bits 1101 converti en binaire ?

Autres thèmes de Systèmes informatiques