Theorie de l'information et Codage Recherche avancée

• Preparation pour l'examen (12 Exercices)
  • 1
    Contexte global : On considère une source de symboles discrète sans mémoire émettant des symboles issus d’un alphabet fini. On souhaite concevoir des codes de source optimaux (codes de Huffman ou de Shannon-Fano), calculer les entropies, les redondances et comparer les performances théoriques et pratiques. On s’intéresse d’abord à une source binaire biaisée, puis à une source à 4 symboles, et enfin à une source de symboles corrélés de second ordre. L’objectif est de relier les résultats aux bornes de Shannon pour le codage de source sans perte. Questions intégrées : Q1 : Une source binaire émet des symboles $\{0,1\}$...→
  • 2
    Session 1 - - Contexte : Un système de transmission numérique utilise une source binaire suivie d'un codage de source Huffman, puis d'un code correcteur de Hamming, transmis sur un canal binaire symétrique (BSC). On souhaite analyser les performances complètes de cette chaîne de communication. Question 1 (4 points) - Entropie de source : Une source discrète sans mémoire émet des symboles de l'alphabet $\mathcal{A} = \{A, B, C, D, E\}$ avec les probabilités suivantes : Symbole A B C D E Probabilité 0.35 0.25 0.20 0.12 0.08 a) Calculer l'entropie $H(S)$ de la source en bits/symbole. b) Quelle est l'entropie maximale possible pour un alphabet...→
  • 3
    Session 2 - - Contexte : On étudie un système de communication utilisant un code cyclique CRC pour la détection d'erreurs, suivi d'un protocole ARQ (Automatic Repeat Request). Le canal de transmission est modélisé par un canal à effacement binaire (BEC). Question 1 (4 points) - Source et codage conjoint : Une source émet des symboles de l'alphabet $\mathcal{A} = \{s_1, s_2, s_3, s_4, s_5, s_6\}$ avec les probabilités : $P = (0.30, 0.25, 0.20, 0.10, 0.10, 0.05)$ a) Calculer l'entropie de la source $H(S)$ . b) Construire le code de Shannon-Fano pour cette source. c) Comparer avec le code de Huffman et déterminer lequel est le plus efficace. d) Calculer la redondance du...→
  • 4
    Examen n°2 : Codage de source et compression d’information Partie 2 : Analyse et optimisation d’un schéma de compression numérique d’une source discrète Une source émet 5 symboles avec probabilités {0,31, 0,23, 0,16, 0,13, 0,17}. On souhaite optimiser le codage et la transmission. Q1. Calculez l’entropie de la source et l’efficacité d’un codage de Huffman optimal. Q2. Déterminez la longueur moyenne des codes binaires générés par Huffman et évaluez le taux de compression obtenu. Q3. Concevez un schéma de codage arithmétique pour cette source avec transmission sur 12 bits et calculez la probabilité d’occurrence d’une séquence donnée. Q4. Analysez la...→
  • 5
    On considère un système de transmission numérique binaire sur un canal discret sans mémoire de type BSC (Binary Symmetric Channel) puis sur un canal gaussien bande limitée. On souhaite dimensionner la chaîne de transmission et le codage canal pour atteindre un débit donné avec une probabilité d’erreur cible. Les paramètres sont : — Canal binaire symétrique BSC de probabilité de transition $p = 10^{-3}$ . — Source binaire équiprobable. — Système 1 : transmission directe sans codage, débit binaire $R_b = 1\,Mbit/s$ . — Système 2 : codage bloc linéaire (7,4) de Hamming parfait sur le même canal. — Système 3 : transmission sur...→
  • 6
    On considère une chaîne de transmission numérique sur canal binaire symétrique de probabilité d’erreur $p = 5\times 10^{-2}$ . Pour améliorer la fiabilité, on étudie successivement : — Un code bloc linéaire (n,k) binaire avec matrice génératrice donnée. — Un code convolutif de taux $R = 1/2$ et mémoire 2 (longueur de contrainte 3). Les données sont : — Code bloc (n=6, k=3) défini par la matrice génératrice : $G = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$ (opérations sur $\mathbb{F}_2$ ). — Code convolutif de polynômes générateurs : $g_1(D) = 1 + D + D^2$ , $g_2(D) = 1 + D^2$ (avec $D$ l’opérateur de retard). On veut comparer les performances en probabilité d’erreur. 1. Pour le code bloc (6,3) : déterminez...→
  • 7
    EXAMEN CODAGE ET THÉORIE DE L'INFORMATION – SUJET 1 Contexte : Un système de transmission numérique transmet des données sur un canal binaire symétrique (BSC) avec probabilité d'erreur p = 0.01. La source émet des symboles binaires avec probabilités P(0) = 0.7 et P(1) = 0.3. On utilise un codage de source suivi d'un codage canal pour optimiser la transmission. Question 1 : Calculer l'entropie de la source binaire H(S). Déterminer le débit binaire minimal théorique nécessaire pour représenter cette source (théorème de Shannon sur le codage de source). Si la source émet 1000 symboles/seconde, quel est le débit minimal...→
  • 8
    | | Contexte général : On étudie un système de transmission numérique complet comprenant un codeur de source, un codeur de canal et une transmission sur un canal bruité. L'objectif est d'analyser les performances théoriques et pratiques du système en termes d'entropie, de capacité et de correction d'erreurs. Question 1 (6 points) : Une source discrète sans mémoire émet 4 symboles $\{A, B, C, D\}$ avec les probabilités respectives $P(A) = 0.5$ , $P(B) = 0.25$ , $P(C) = 0.125$ , $P(D) = 0.125$ . a) Calculer l'entropie de la source $H(S) = -\sum_{i} p_i \log_2(p_i)$ . b) Déterminer le code de Huffman optimal pour cette source et calculer la longueur moyenne du code. c)...→
  • 9
    | | Contexte général : On étudie un système de transmission pour une application IoT (Internet des Objets). Les capteurs transmettent des données de mesure via un canal radio bruité. L'analyse porte sur l'optimisation du codage source par quantification et le choix du codage canal adapté. Question 1 (6 points) : Un capteur de température mesure des valeurs dans l'intervalle [0°C, 100°C]. La température suit une loi uniforme. On souhaite transmettre ces mesures avec une précision de 0.5°C. a) Calculer le nombre de niveaux de quantification nécessaires et le nombre de bits requis par mesure. b) Calculer l'entropie maximale de...→
  • 10
    Système de Transmission Numérique avec Codage de Source et Canal On étudie un système de transmission numérique complet comprenant un codage de source, un codage canal et un canal de transmission bruité. L'objectif est d'analyser les performances théoriques et pratiques de ce système. Contexte du système : Source discrète à 5 symboles : $\mathcal{S} = \{s_1, s_2, s_3, s_4, s_5\}$ Probabilités d'apparition : $P(s_1) = 0.35, P(s_2) = 0.25, P(s_3) = 0.20, P(s_4) = 0.12, P(s_5) = 0.08$ Canal binaire symétrique (BSC) avec probabilité d'erreur $p = 0.01$ Débit binaire du canal : $D = 10 \text{ Mbits/s}$ Question 1 (4 points) : Calculez l'entropie de la source $H(S)$ en bits par symbole. Déterminez la quantité d'information propre (auto-information) de chaque symbole et identifiez le symbole...→
  • 11
    Canal Gaussien et Codage Cyclique pour Transmission Satellite On étudie une liaison satellite utilisant un canal à bruit blanc additif gaussien (AWGN) avec un système de codage correcteur d'erreurs cyclique. L'analyse porte sur la capacité du canal, le dimensionnement du codage et les performances de correction. Caractéristiques du système : Bande passante du canal : $W = 36 \text{ MHz}$ Puissance du signal reçu : $P_s = 10 \text{ mW}$ Densité spectrale de bruit : $N_0 = 10^{-12} \text{ W/Hz}$ Modulation QPSK avec efficacité spectrale $\eta_s = 2 \text{ bits/s/Hz}$ Code cyclique de polynôme générateur $g(x) = x^3 + x + 1$ Question 1 (4 points) : Calculez le rapport signal sur bruit $SNR$ en décibels. Appliquez la formule de Shannon-Hartley pour...→
  • 12
    Session 1 : Entropie, Codage de Source et Compression | | On considère une source discrète sans mémoire $S$ émettant des symboles d'un alphabet $\mathcal{A} = \{a, b, c, d, e\}$ avec les probabilités suivantes : Symbole a b c d e Probabilité 0.40 0.25 0.15 0.12 0.08 Question 1 (4 points) - Entropie de la source : a) Calculer l'entropie $H(S)$ de la source en bits par symbole. b) Quelle est la quantité d'information propre $I(a)$ apportée par le symbole $a$ ? Comparer avec l'entropie moyenne et interpréter. c) Calculer le débit d'information $D_S$ si la source émet 1000 symboles par seconde. Question 2 (5...→
• Codage de source (31 Exercices)
  • 1
    Une source discrète sans mémoire produit trois symboles {X, Y, Z} avec les probabilités : $P(X) = 0.5, P(Y) = 0.3, P(Z) = 0.2$ . On souhaite coder cette source en utilisant l'algorithme de Shannon-Fanno. 1. Calculez l'entropie $H(S)$ de cette source. 2. Construisez le code de Shannon-Fanno et déterminez la longueur moyenne $L_{SF}$ du code obtenu. 3. Comparez l'efficacité du code Shannon-Fanno avec la limite théorique en calculant le coefficient d'efficacité $\eta = \frac{H(S)}{L_{SF}}$ .→
  • 2
    Une source numérique produit une séquence de symboles {a, b, c, d} avec les fréquences d'apparition observées : a apparaît 40 fois, b apparaît 30 fois, c apparaît 20 fois, et d apparaît 10 fois dans un message de 100 symboles. 1. Calculez les probabilités empiriques $P(a), P(b), P(c), P(d)$ et l'entropie empirique $H_{emp}$ de cette source. 2. Déterminez la longueur moyenne du code arithmétique basique $L_{arith}$ pour coder une séquence de 1000 symboles suivant ces probabilités, sachant que la précision arithmétique permet de réduire la longueur de $\log_2 H_{emp}$ bits en moyenne. 3. Comparez la performance entre le code arithmétique et un code...→
  • 3
    Exercice 1 : Analyse Complète du Codage de Huffman pour une Source Discrète Une source discrète génère cinq symboles $\{A, B, C, D, E\}$ avec les probabilités d'occurrence suivantes : $P(A) = 0.35$ , $P(B) = 0.25$ , $P(C) = 0.20$ , $P(D) = 0.15$ , $P(E) = 0.05$ . Ces symboles représentent les caractères d'un message transmis sur un canal de communication. Question 1 : En utilisant l'algorithme de Huffman, construire l'arbre de codage complet en montrant toutes les étapes d'agglomération des nœuds. Déterminer les longueurs de code $l_i$ pour chaque symbole et calculer la longueur moyenne du code $L_{moy}$ définie par $L_{moy} = \sum_{i=1}^{5} P(i) \cdot l_i$ . Comparer ensuite avec l'entropie de Shannon $H = -\sum_{i=1}^{5} P(i) \log_2 P(i)$ . Question...→
  • 4
    Exercice 2 : Analyse Comparative du Codage Shannon-Fanno et Huffman Une source génère quatre symboles $\{S_1, S_2, S_3, S_4\}$ avec les probabilités respectives $P(S_1) = 0.40$ , $P(S_2) = 0.30$ , $P(S_3) = 0.20$ , $P(S_4) = 0.10$ . On souhaite comparer les performances du codage Shannon-Fanno avec le codage de Huffman pour évaluer l'impact de la stratégie de codage sur l'efficacité de compression. Question 1 : Appliquer l'algorithme Shannon-Fanno pour coder les quatre symboles. Diviser récursivement l'ensemble de symboles en deux groupes ayant une probabilité totale aussi équilibrée que possible. Déterminer les codes obtenus et calculer la longueur moyenne $L_{SF}$ du code Shannon-Fanno. Comparer avec la longueur moyenne de Huffman...→
  • 5
    Exercice 1 : Codage de source et entropie Soit une source discrète S émettant les symboles {A, B, C, D} avec les probabilités respectives $P(A) = 0.40$ , $P(B) = 0.30$ , $P(C) = 0.20$ , $P(D) = 0.10$ . Question 1 : Calculer l’entropie de la source S en bits/symbole. Question 2 : Construire le code de Shannon-Fano correspondant et déterminer la longueur moyenne du code. Question 3 : Calculer l’efficacité du codage et l’économie réalisée par rapport à un codage fixe sur deux bits.→
  • 6
    Exercice 2 : Algorithme de Huffman et codage optimal Considérons une source discrète X produisant les symboles {E, F, G, H, I} avec les probabilités $P(E) = 0.35$ , $P(F) = 0.25$ , $P(G) = 0.20$ , $P(H) = 0.15$ , $P(I) = 0.05$ . Question 1 : Construire l’arbre et le code de Huffman pour cette source. Question 2 : Calculer la longueur moyenne du code de Huffman obtenu. Question 3 : Calculer l’entropie de la source et l’efficacité du code de Huffman. Comparer à un codage binaire fixe sur trois bits.→
  • 7
    Exercice 3 : Codage arithmétique et Lempel-Ziv On considère une source S3 qui émet une séquence de 5 symboles {J, K, L} selon les probabilités stationnaires $P(J) = 0.5$ , $P(K) = 0.3$ , $P(L) = 0.2$ . La séquence observée est : J K J L K. Question 1 : Effectuer le codage arithmétique de cette séquence, étapes intermédiaires incluses. Donner le nombre décimal obtenu et l’intervalle final. Question 2 : Appliquer l’algorithme Lempel-Ziv (version LZ77, fenètre de 3) à cette même séquence. Détaillez tous les couples (distance, longueur, prochain symbole) générés. Question 3 : Calculer la longueur totale du codage par chaque algorithme. Déduire...→
  • 8
    Exercice 1 : Codage de Shannon-Fanno et compression de source On considère une source discrète émettant 5 symboles avec les probabilités suivantes : $P(a_1) = 0.35$ , $P(a_2) = 0.25$ , $P(a_3) = 0.20$ , $P(a_4) = 0.15$ , $P(a_5) = 0.05$ . Une séquence de $N = 10000$ symboles est transmise via ce code. 1. Construisez le code de Shannon-Fanno pour cette source et déterminez la longueur moyenne du code $L_{\text{SF}}$ . 2. Calculez l'entropie $H$ de cette source et comparez-la à la longueur moyenne obtenue. 3. Évaluez le taux de compression $\tau$ et estimez le nombre de bits économisés lors de la transmission des $10000$ symboles par rapport à un...→
  • 9
    Exercice 2 : Algorithme de Huffman et décodage de séquence compressée Une source discrète génère 6 symboles avec les fréquences suivantes : $f(x_1) = 45$ , $f(x_2) = 30$ , $f(x_3) = 20$ , $f(x_4) = 15$ , $f(x_5) = 8$ , $f(x_6) = 2$ . Le nombre total de symboles est $N_{\text{total}} = 120$ . 1. Construisez l'arbre de Huffman pour cette source, puis déduisez le code binaire de chaque symbole. 2. Calculez la longueur moyenne du code $L_{\text{Huffman}}$ et l'efficacité de codage $\eta$ . 3. Une séquence compressée contient $M = 385$ bits. Estimez le nombre de symboles source dans cette séquence et comparez avec une compression par Shannon-Fanno.→
  • 10
    Exercice 3 : Compression Lempel-Ziv et codage arithmétique comparé Un texte source de $N = 5000$ caractères est composé de 8 symboles distincts. La distribution de fréquences est : $f(s_1) = 2500, f(s_2) = 1200, f(s_3) = 800, f(s_4) = 400, f(s_5) = 60, f(s_6) = 20, f(s_7) = 15, f(s_8) = 5$ . 1. Appliquez l'algorithme LZ77 avec une fenêtre de recherche de $W = 128\ \text{octets}$ et une fenêtre de prévision de $L = 64\ \text{octets}$ . Estimez le nombre de triplets (position, longueur, symbole) générés et la taille comprimée. 2. Comparez avec un codage arithmétique : calculez la longueur moyenne d'un mot-code arithmétique $L_{\text{arith}}$ et la taille comprimée correspondante. 3. Évaluez le gain de compression $G$ entre LZ77 et le codage arithmétique, et identifiez la meilleure méthode pour...→
  • 11
    Exercice 1 : Codage de Huffman pour une source d'information textuelle Une source discrète produit des symboles selon les probabilités suivantes : $P(A) = 0.35$ , $P(B) = 0.25$ , $P(C) = 0.20$ , $P(D) = 0.12$ , $P(E) = 0.08$ . On souhaite coder ces symboles en utilisant l'algorithme de Huffman afin de transmettre un message contenant 1000 symboles. Question 1 : Construire l'arbre de codage de Huffman en détaillant toutes les étapes de fusion des nœuds. Déterminer les mots de code binaires pour chaque symbole (codes de longueur variable). Calculer ensuite la longueur moyenne du code $L_{moy}$ définie par $L_{moy} = \sum_{i} P(x_i) \times l_i$ où $l_i$ est la longueur du code binaire...→
  • 12
    Exercice 2 : Codage arithmétique et comparaison avec Shannon-Fano Une source produit une séquence de trois symboles X, Y, Z avec les probabilités : $P(X) = 0.50$ , $P(Y) = 0.30$ , $P(Z) = 0.20$ . On désire coder la séquence "XYZ" en utilisant le codage arithmétique et comparer les performances avec un codage Shannon-Fano. Question 1 : Construire le code Shannon-Fano en organisant les symboles de manière hiérarchique. Déterminer les mots de code pour chaque symbole et calculer la longueur moyenne $L_{moy}^{SF}$ du code Shannon-Fano. Vérifier que cette longueur moyenne satisfait $H(X) \leq L_{moy}^{SF} Question 2 : Appliquer l'algorithme de codage arithmétique pour encoder la séquence "XYZ". Établir l'intervalle initial $ [L_0, H_0) = [0, 1) $, puis calculer les intervalles successifs $ [L_k, H_k) $ après traitement de chaque symbole (k = 1, 2, 3). Déterminer le nombre minimum de bits nécessaires pour représenter le code arithmétique final, défini par $ N_{arith} = \lceil \log_2\left(\frac{1}{H_3...→
  • 13
    Exercice 3 : Algorithme LZ77 et compression de source adaptée On considère une source générant une chaîne de caractères : "ABRACADABRA CADABRA ABRACADABRA". On désire appliquer l'algorithme de Lempel-Ziv LZ77 pour compresser cette source. L'algorithme LZ77 utilise une fenêtre glissante avec un buffer historique (dictionnaire) de taille $W_h = 32$ caractères et un buffer de prédiction de taille $W_p = 18$ caractères. Question 1 : Appliquer manuellement les trois premières itérations de l'algorithme LZ77. Pour chaque itération, identifier le motif le plus long dans le buffer historique qui correspond au début du buffer de prédiction. Générer les triplets (décalage, longueur, caractère suivant) $(d, l, c)$ pour...→
  • 14
    Exercice 1 : Codage de source et algorithme de Huffman Soit une source discrète émettant les symboles A , B , C , D avec les probabilités suivantes : $P(A) = 0,4$ , $P(B) = 0,3$ , $P(C) = 0,2$ , $P(D) = 0,1$ . Question 1 : Calculer l'entropie de la source en bits/symbole. Question 2 : Construire l'arbre de codage binaire optimal selon l'algorithme de Huffman pour cette source et déterminer le code de chaque symbole. Question 3 : Calculer la longueur moyenne du code obtenu et comparer au cas du codage naïf à longueur fixe. Quelle est l'efficacité du code de Huffman obtenu ?→
  • 15
    Exercice 2 : Codage de Shannon-Fano et compression Une source discrète numérique produit les symboles 0,1,2,3,4 selon les probabilités : $p_0=0,35$ , $p_1=0,25$ , $p_2=0,20$ , $p_3=0,15$ , $p_4=0,05$ . Question 1 : Utiliser la méthode de codage de Shannon-Fano pour définir les codes binaires de chaque symbole, et dresser le tableau code/symbole. Question 2 : Calculer la longueur moyenne du code obtenu et son efficacité par rapport à l’entropie. Question 3 : On code un message de 1000 symboles issus de cette source en utilisant le code trouvé à la question 1. Calculer la longueur totale du message comprimé...→
  • 16
    Exercice 3 : Codage arithmétique et algorithme de Lempel-Ziv Une source génère les lettres X et Y avec les probabilités : $P(X) = 0,7$ , $P(Y) = 0,3$ . Considérons le mot "XYXYXXY" à coder. Question 1 : Réaliser le codage arithmétique du message "XYXYXXY" et donner l’intervalle final obtenu avec ce codage. Question 2 : En déterminant la longueur binaire idéale pour transmettre ce message, comparer avec le cas du codage naïf à longueur fixe sur 2 symboles. Question 3 : En utilisant Lempel-Ziv (LZ77, dictionnaire dynamique), coder la séquence "ABABBABABABA" (avec A , B deux symboles) en détaillant chaque étape, et calculer...→
  • 17
    Exercice 2 : Algorithme Shannon-Fanno et comparaison avec Huffman On considère une source discrète sans mémoire générant des caractères d'un alphabet $\mathcal{A} = \{x_1, x_2, x_3, x_4, x_5, x_6\}$ avec les probabilités : $P(x_1) = 0.30$ , $P(x_2) = 0.25$ , $P(x_3) = 0.20$ , $P(x_4) = 0.12$ , $P(x_5) = 0.08$ , $P(x_6) = 0.05$ . Question 1 : Construire le code Shannon-Fanno pour cette source en appliquant récursivement l'algorithme de division bipartite. À chaque étape, diviser l'ensemble des symboles en deux sous-ensembles tels que la somme des probabilités soit aussi proche que possible de 0.5. Déterminer les codes binaires pour chaque symbole et calculer la longueur moyenne du code Shannon-Fanno : $L_{SF}$ . Question 2 : Pour...→
  • 18
    Exercice 1 : Codage de Shannon-Fano sur une source discrète On considère une source discrète S émettant cinq symboles $a_1$ , $a_2$ , $a_3$ , $a_4$ , $a_5$ de probabilités respectives $P(a_1) = 0{,}4$ , $P(a_2) = 0{,}2$ , $P(a_3) = 0{,}2$ , $P(a_4) = 0{,}1$ , $P(a_5) = 0{,}1$ . On souhaite appliquer le codage de Shannon-Fano à cette source. Question 1 : Construire l'arbre de Shannon-Fano et indiquer les codes binaires associés à chaque symbole. Question 2 : Calculer la longueur moyenne du code obtenu $L_c$ et comparer-la à l'entropie $H(S)$ de la source. Donner l'efficacité du code. Question 3 : On suppose que les messages émis sont...→
  • 19
    Exercice 2 : Compression par codage de Huffman Considérons une source discrète émettant les symboles $X={x_1, x_2, x_3, x_4}$ avec les probabilités $P(x_1)=0{,}5$ , $P(x_2)=0{,}25$ , $P(x_3)=0{,}15$ , $P(x_4)=0{,}1$ . Question 1 : Construire l’arbre de Huffman pour cette source et donner le code binaire associé à chaque symbole. Question 2 : Calculer la longueur moyenne du code obtenu et la comparer à l’entropie $H(X)$ . Calculer l’efficacité du code. Question 3 : La source émet une séquence de 8 symboles transmit : $x_1 x_2 x_3 x_2 x_1 x_4 x_1 x_1$ . Donner la séquence binaire émise et calculer le rapport de compression obtenu par rapport au codage binaire fixe...→
  • 20
    Exercice 3 : Algorithme arithmétique et codage Lempel-Ziv On considère une source binaire émettant les symboles $0$ et $1$ avec probabilités $P(0) = 0{,}7$ et $P(1) = 0{,}3$ . On transmet le message M = 10010. Question 1 : Encoder le message M en utilisant l’algorithme arithmétique. Donner l’intervalle numérique final obtenu et le code retenu pour représenter le message. Question 2 : Déterminer la longueur minimale du code binaire si on utilise directement des blocs de longueur 5 (sans compression). Comparer ce résultat à la quantité d’information portée par le message (entropie). Question 3 : Pour la même séquence M, appliquer le schéma Lempel-Ziv (LZ77, fenêtré,...→
  • 21
    Exercice 1 : Codage de Shannon-Fanno et analyse d'une source discrète On considère une source discrète générant un alphabet de 5 symboles $\{s_1, s_2, s_3, s_4, s_5\}$ avec les probabilités respectives : $P(s_1) = 0.40$ , $P(s_2) = 0.25$ , $P(s_3) = 0.15$ , $P(s_4) = 0.12$ , $P(s_5) = 0.08$ . Cette source génère une séquence de $N = 1000$ symboles. Question 1 : Calculer l'entropie $H$ de cette source discrète en bits par symbole. Ensuite, calculer la longueur moyenne du code de Shannon-Fanno $L_{SF}$ que vous allez construire en appliquant l'algorithme de Shannon-Fanno. Vérifier que $H \leq L_{SF} Question 2 : Pour cette même source, déterminer les codes binaires assignés à chaque symbole en utilisant l'algorithme de Shannon-Fanno. Calculer ensuite la longueur moyenne pondérée $ L_{moy} $ des codewords et déterminer l'efficacité du code $ \eta = \frac{H}{L_{moy}} $ en pourcentage. Interpréter le résultat obtenu. Question 3 : Supposons que la source transmet une séquence encodée contenant $ n_1 = 400 $ symboles $ s_1 $, $ n_2 = 250 $ symboles $ s_2 $, $ n_3...→
  • 22
    Exercice 2 : Algorithme de Huffman et optimisation du codage Une source discrète génère un alphabet de 6 symboles $\{a, b, c, d, e, f\}$ avec les probabilités suivantes : $P(a) = 0.30$ , $P(b) = 0.25$ , $P(c) = 0.20$ , $P(d) = 0.12$ , $P(e) = 0.08$ , $P(f) = 0.05$ . Cette source transmet un message de $M = 2000$ symboles. Question 1 : En utilisant l'algorithme de Huffman, construire l'arbre binaire de codage et déterminer les codes binaires assignés à chaque symbole. Calculer ensuite la longueur moyenne du code Huffman $L_H$ en bits par symbole. Vérifier que cette longueur moyenne est inférieure ou égale à celle du code Shannon-Fanno de l'exercice précédent. Question 2 :...→
  • 23
    Exercice 3 : Codage arithmétique et algorithme Lempel-Zip comparés Une source discrète génère des symboles d'un alphabet $\{x, y, z\}$ avec les probabilités $P(x) = 0.50$ , $P(y) = 0.35$ , $P(z) = 0.15$ . On souhaite encoder une séquence de 500 symboles. Question 1 : Calculer l'entropie $H$ de cette source. Ensuite, appliquer le codage arithmétique pour encoder la séquence $\mathbf{xyzx}$ (4 symboles). Déterminer l'intervalle $[L_0, U_0)$ initial, puis calculer les intervalles après chaque symbole : $[L_1, U_1)$ , $[L_2, U_2)$ , $[L_3, U_3)$ , $[L_4, U_4)$ . Quelle est la longueur finale de l'intervalle $\Delta L_4$ ? Question 2 : À partir de l'intervalle final $[L_4, U_4)$ obtenu à la question 1, déterminer...→
  • 24
    Exercice 1 : Codage de Huffman et analyse d'une source discrète On considère une source discrète émettant $5$ symboles différents : $\{A, B, C, D, E\}$ avec les probabilités d'émission suivantes : $P(A) = 0.35$ $P(B) = 0.25$ $P(C) = 0.20$ $P(D) = 0.12$ $P(E) = 0.08$ Question 1 : Calculer l'entropie de la source $H(X)$ en bits, puis déterminer la longueur moyenne théorique minimale selon le codage optimal (borne inférieure de Kraft). Vérifier si la source satisfait les conditions nécessaires pour un codage sans perte. Question 2 : Construire un code de Huffman pour cette source en détaillant chaque étape de fusion des symboles. Calculer la longueur moyenne $L$ du code obtenu en...→
  • 25
    Exercice 2 : Algorithme de Lempel-Ziv et compression de séquences On considère une séquence binaire produite par un processus stationnaire aléatoire : Séquence : 011010011010011010100110101001101 (35 bits) ...→
  • 26
    Exercice 3 : Codage de Shannon-Fanno et analyse d'efficacité Une source discrète produit une séquence d'information avec les symboles suivants et leurs probabilités associées : ...→
  • 27
    Exercice 1 : Codage Shannon-Fano d'une source discrète Une source discrète émet les symboles $A$ , $B$ , $C$ , $D$ et $E$ avec les probabilités respectives $P(A) = 0.3$ , $P(B) = 0.25$ , $P(C) = 0.2$ , $P(D) = 0.15$ , $P(E) = 0.1$ . Question 1 : Déterminez l'entropie de la source en utilisant $H = - \sum_{i=1}^{n} p_i \log_2(p_i)$ et donnez le résultat en bits/symbole. Question 2 : Construisez le code de Shannon-Fano pour cette source. Indiquez la longueur de chaque code et calculez la longueur moyenne du code $L_{mf}$ selon $L_{mf} = \sum_{i=1}^n p_i l_i$ , où $l_i$ est la longueur du code du symbole $i$ . Question 3 : Calculez l'efficacité du code...→
  • 28
    Exercice 2 : Algorithme de Huffman et source discrète On considère une source discrète avec les symboles $X_1$ , $X_2$ , $X_3$ , $X_4$ de probabilités respectives $p_1 = 0.4$ , $p_2 = 0.3$ , $p_3 = 0.2$ , $p_4 = 0.1$ . Question 1 : Calculez l'entropie de la source avec la formule $H = -\sum_{i=1}^{4} p_i \log_2(p_i)$ . Question 2 : Construisez l'arbre et le code de Huffman pour cette source, déduisez la longueur de chaque code, et calculez la longueur moyenne $L_{mf}$ . Question 3 : Calculez le taux de redondance du code de Huffman obtenu, puis comparez l'efficacité du code Huffman avec celle du codage Shannon-Fano (prenez la...→
  • 29
    Codage d'une source discrète par la méthode de Shannon-Fano Une source discrète sans mémoire émet 5 symboles $S = \{s_1, s_2, s_3, s_4, s_5\}$ avec les probabilités suivantes : $P(s_1) = 0.40$ $P(s_2) = 0.25$ $P(s_3) = 0.15$ $P(s_4) = 0.12$ $P(s_5) = 0.08$ Question 1 : Calculez l'entropie $H(S)$ de cette source en bits par symbole. Interprétez le résultat obtenu dans le contexte de la théorie de l'information. Question 2 : Appliquez l'algorithme de Shannon-Fano pour construire un code binaire pour cette source. Détaillez chaque étape de partitionnement et déterminez les mots de code pour chaque symbole. Calculez ensuite la longueur moyenne $L_{SF}$ du code obtenu. Question 3 : Calculez l'efficacité $\eta$ et la redondance...→
  • 30
    Construction et analyse d'un code de Huffman optimal Une source d'information transmet 6 symboles $S = \{A, B, C, D, E, F\}$ avec les probabilités d'émission suivantes : $P(A) = 0.30$ $P(B) = 0.25$ $P(C) = 0.20$ $P(D) = 0.12$ $P(E) = 0.08$ $P(F) = 0.05$ Question 1 : Construisez l'arbre de Huffman pour cette source en détaillant chaque étape de fusion. Déterminez les mots de code binaires pour chaque symbole et vérifiez que le code obtenu satisfait la propriété de préfixe. Calculez la longueur moyenne $L_H$ du code de Huffman. Question 2 : Calculez l'entropie $H(S)$ de la source, puis déterminez l'efficacité $\eta_H$ du code de Huffman et sa variance de longueur $\sigma^2$ . La variance est donnée...→
  • 31
    Codage arithmétique d'une séquence de symboles Soit une source discrète émettant 4 symboles $S = \{s_1, s_2, s_3, s_4\}$ avec les probabilités suivantes : $P(s_1) = 0.50$ $P(s_2) = 0.30$ $P(s_3) = 0.15$ $P(s_4) = 0.05$ Question 1 : Construisez la table des intervalles cumulatifs pour le codage arithmétique. Pour chaque symbole $s_i$ , déterminez son intervalle $[L_i, H_i)$ où $L_i$ est la borne inférieure (cumul des probabilités précédentes) et $H_i$ est la borne supérieure. Vérifiez que la somme des largeurs d'intervalles égale $1$ . Question 2 : Utilisez l'algorithme de codage arithmétique pour encoder la séquence $\text{"} s_2 s_1 s_3 \text{"}$ . Pour chaque symbole de la séquence, calculez l'intervalle résultant $[L, H)$ en appliquant les formules de...→
• Canal de transmission (34 Exercices)
  • 1
    Exercice 1 : Analyse d'un canal discret symétrique (BSC) avec calcul de capacité Un système de transmission numérique utilise un canal discret symétrique (Binary Symmetric Channel - BSC) pour transmettre des données binaires. Le canal possède une probabilité d'erreur (probabilité de transition) $p = 0.15$ pour chaque bit transmis. L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ et l'alphabet de sortie est $\mathcal{Y} = \{0, 1\}$ . On suppose une distribution de probabilité à l'entrée du canal $P(X) = (0.6, 0.4)$ pour les symboles $0$ et $1$ respectivement. Le canal transmet $N = 10000$ bits par seconde. Question 1 : Construire la matrice de transition $P(Y|X)$ du canal BSC, puis calculer la distribution de...→
  • 2
    Exercice 2 : Analyse d'un canal à effacement ternaire avec optimisation de capacité Un canal à effacement (Erasure Channel) ternaire transmet des symboles ternaires $X \in \{0, 1, 2\}$ vers une sortie $Y \in \{0, 1, 2, E\}$ où $E$ représente un effacement. Avec probabilité $1-\epsilon$ , le symbole est transmis correctement, et avec probabilité $\epsilon$ , il est effacé. On considère deux scénarios : Scénario A avec $\epsilon_A = 0.20$ et Scénario B avec $\epsilon_B = 0.10$ . On analyse deux distributions d'entrée : Distribution uniforme $P(X) = (1/3, 1/3, 1/3)$ et Distribution optimale à déterminer. Question 1 : Pour le Scénario A ( $\epsilon_A = 0.20$ ), construire la matrice de transition $P(Y|X)$ du canal à effacement...→
  • 3
    Exercice 3 : Analyse comparative de canaux discrets sans mémoire et optimisation de décodage Un système de transmission numérique utilise trois canaux distincts pour la transmission parallèle de données : Canal 1 (BEC - Binary Erasure Channel) avec $\epsilon_1 = 0.25$ , Canal 2 (BSC - Binary Symmetric Channel) avec $p_2 = 0.10$ , et Canal 3 (Quantization Channel) où la sortie est quantifiée à $n = 2$ bits avec probabilités $P(Y=0|X=0) = 0.95$ , $P(Y=1|X=0) = 0.05$ , $P(Y=0|X=1) = 0.05$ , $P(Y=1|X=1) = 0.95$ . Le système transmet des symboles binaires avec distribution uniforme $P(X) = (0.5, 0.5)$ à un débit total de $R = 1$ Mbps sur les trois canaux. Question 1 : Calculer la capacité...→
  • 4
    Exercice 1 : Analyse d'un canal discret symétrique (BSC) et calcul de sa capacité Un système de communication numérique utilise un canal discret symétrique pour transmettre des messages binaires. Le canal a une probabilité d'erreur de transmission $p = 0.1$ sur chaque bit transmis. L'alphabet source est $\mathcal{X} = \{0, 1\}$ et l'alphabet de réception est $\mathcal{Y} = \{0, 1\}$ . On suppose que les symboles d'entrée sont équiprobables. Les paramètres du canal sont : Probabilité d'erreur (probabilité d'inversion de bit) : $p = 0.1$ Probabilité de transmission correcte : $1 - p = 0.9$ Distribution d'entrée (uniforme) : $P(X=0) = P(X=1) = 0.5$ Vitesse de transmission : $R = 1000 bits/s$ Question 1 : Construire la matrice de transition du...→
  • 5
    Exercice 2 : Analyse d'un canal à effacement et calcul de capacité Un canal à effacement (erasure channel) est utilisé pour transmettre des données numériques. Dans ce type de canal, la sortie peut être soit le symbole d'entrée exact, soit un symbole d'effacement spécial « ? » indiquant que le symbole a été perdu. L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ et l'alphabet de sortie est $\mathcal{Y} = \{0, 1, ?\}$ . Les paramètres du canal sont : Probabilité d'effacement (perte du symbole) : $\epsilon = 0.2$ Probabilité de transmission correcte : $1 - \epsilon = 0.8$ Distribution d'entrée (uniforme) : $P(X=0) = P(X=1) = 0.5$ Nombre de symboles transmis par seconde : $N = 2000 symboles/s$ Longueur du bloc...→
  • 6
    Exercice 3 : Canal causal avec bruit additif gaussien et calcul de capacité de Shannon Un système de communication sans fil transmet des signaux sur un canal causal avec bruit blanc additif gaussien (AWGN). Le canal est modélisé comme un système linéaire invariant dans le temps. Les paramètres du système sont : Puissance d'émission : $P = 10 W$ Puissance de bruit (variance) : $\sigma^2 = N = 0.5 W$ Bande passante du canal : $B = 1000 Hz$ Gain du canal (sans perte) : $G = 1$ Durée de transmission : $T = 1 s$ Fréquence d'échantillonnage : $f_s = 2B = 2000 Hz$ (théorème de Nyquist) Question 1 : Calculer le rapport signal-sur-bruit (SNR) en valeur linéaire et en...→
  • 7
    Exercice 1 : Analyse d'un canal de transmission discret symétrique (BSC) Un système de communication numérique transmet des données binaires à travers un canal de transmission discret sans mémoire. Le canal est modélisé comme un canal discret symétrique (BSC - Binary Symmetric Channel) avec une probabilité d'erreur $p = 0.1$ . Le débit binaire d'entrée du canal est $R_{in} = 1\text{ Mbps}$ et le système utilise un code de redondance simple. L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ avec des probabilités d'émission uniformes : $P(X=0) = P(X=1) = 0.5$ . Le canal peut causer des erreurs de transmission telles que le bit $0$ devient $1$ avec probabilité $p$ , et le bit...→
  • 8
    Exercice 2 : Analyse d'un canal à effacement binaire (BEC) Un nouveau système de transmission utilise un canal à effacement binaire (BEC - Binary Erasure Channel) où les symboles reçus peuvent être soit correctement décodés, soit effacés (perdus). Le canal transmet des symboles binaires depuis l'ensemble $\mathcal{X} = \{0, 1\}$ vers l'ensemble de sortie $\mathcal{Y} = \{0, 1, ?\}$ où le symbole « ? » représente un effacement. La probabilité d'effacement du canal est $\varepsilon = 0.2$ . Quand un symbole n'est pas effacé (probabilité $1 - \varepsilon = 0.8$ ), il est reçu correctement. Les symboles d'entrée sont équiprobables : $P(X=0) = P(X=1) = 0.5$ . Le débit d'information du système est $R = 800\text{ kbps}$ et la fréquence...→
  • 9
    Exercice 1 : Analyse Complète d'un Canal de Transmission Discret Symétrique On considère un canal de transmission discret sans mémoire et symétrique (BSC - Binary Symmetric Channel) utilisé pour la transmission de données numériques. Ce canal transmet des symboles binaires (0 ou 1) avec une probabilité d'erreur symétrique de $p = 0.1$ . L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ et l'alphabet de sortie est $\mathcal{Y} = \{0, 1\}$ . La distribution de probabilité à l'entrée du canal est supposée uniforme : $P(X=0) = P(X=1) = 0.5$ . Le canal a une largeur de bande de $B = 1 \text{ MHz}$ et fonctionne à un débit binaire de $R = 100 \text{ kbits/s}$ . Question 1 : Écrivez la matrice...→
  • 10
    Exercice 2 : Analyse d'un Canal de Transmission à Effacement (Erasure Channel) On considère un canal de transmission discret à effacement (Erasure Channel) qui modélise les phénomènes de perte de paquets dans les réseaux de communication. Ce canal reçoit des symboles binaires (0 ou 1) et peut soit les transmettre correctement, soit effacer le symbole (remplacé par un symbole '?'). La probabilité d'effacement est $\epsilon = 0.2$ . L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ , l'alphabet de sortie est $\mathcal{Y} = \{0, 1, ?\}$ , où '?' représente un effacement. La distribution de probabilité à l'entrée est uniforme : $P(X=0) = P(X=1) = 0.5$ . Le canal opère à un débit de...→
  • 11
    Exercice 3 : Analyse d'un Canal de Transmission Causal avec Mémoire (Markovien) On considère un canal de transmission discret causal avec mémoire modélisé comme une chaîne de Markov à deux états : État CORRECT (C) et État ERREUR (E). Le canal commence toujours dans l'état CORRECT. Les probabilités de transition d'état sont données par une matrice stochastique : $P_{\text{état}} = \begin{pmatrix} 0.95 & 0.05 \ 0.1 & 0.9 \end{pmatrix}$ où la première ligne correspond à l'état C et la deuxième ligne à l'état E. Les entrées représentent les probabilités de rester ou passer à l'autre état. Lorsque le canal est dans l'état CORRECT, les symboles binaires sont transmis correctement. Lorsqu'il...→
  • 12
    Exercice 1 : Canal discret symétrique et capacité d'un système de communication binaire Un système de communication utilise un canal discret sans mémoire de type canal discret symétrique (BSC - Binary Symmetric Channel) pour transmettre des données binaires. La probabilité d'erreur lors de la transmission d'un bit est $p_e = 0.01$ (soit 1% d'erreur). Le système transmet des blocs de $n = 1000$ bits à un débit de $R = 1$ Mbps. La source d'information produit un flux de symboles binaires équiprobables (probabilité $P(0) = P(1) = 0.5$ ). On souhaite évaluer la fiabilité du système et son efficacité spectrale. Question 1 : Calculer la matrice de transition $\mathbf{P}$ du...→
  • 13
    Exercice 2 : Canal à effacement (Erasure Channel) et comparaison avec le canal symétrique On considère un canal à effacement (EC - Erasure Channel) destiné à la transmission de données numériques en environnement bruyant. Chaque symbole d'entrée binaire (0 ou 1) peut être transmis correctement, ou être effacé (marqué comme indéterminé, noté $\epsilon$ ) avec une probabilité $p_e = 0.1$ . Lorsqu'un symbole n'est pas effacé, il est reçu sans erreur. Le canal est utilisé pour transmettre $n = 500$ bits à un débit $R = 2$ Mbps. La source produit des symboles uniformément distribués. Question 1 : Écrire la matrice de transition $\mathbf{P}_{EC}$ du canal...→
  • 14
    Exercice 3 : Analyse comparative de canaux et calcul de capacités multiples On dispose d'une infrastructure de communication composée de trois canaux distincts fonctionnant en parallèle sur la même bande de fréquence. Le premier canal est un canal discret symétrique (BSC) avec probabilité d'erreur $p_1 = 0.02$ . Le deuxième canal est un canal à effacement avec probabilité d'effacement $p_2 = 0.05$ . Le troisième canal est un canal discret sans mémoire avec une matrice de transition asymétrique : $\mathbf{P}_3 = \begin{pmatrix} 0.95 & 0.05 \ 0.10 & 0.90 \end{pmatrix}$ Tous les canaux utilisent une source d'information avec distribution uniforme (symboles équiprobables). On souhaite optimiser l'allocation de puissance entre ces trois canaux pour maximiser...→
  • 15
    Exercice 1 : Analyse d'un canal discret symétrique avec codage Un système de communication numérique utilise un canal de transmission discret sans mémoire modélisé comme un canal discret symétrique (BEC pour Binary Erasure Channel) avec probabilité d'effacement $p_e = 0,15$ . L'alphabet d'entrée du canal est $X = \{0, 1\}$ avec probabilités uniformes $P(X=0) = P(X=1) = 0,5$ . L'alphabet de sortie est $Y = \{0, 1, e\}$ où $e$ représente une transmission effacée. Une source génère des messages binaires à un débit $R_s = 10^6$ bits/seconde. Question 1 : Construisez la matrice de transition du canal $P(Y|X)$ et calculez les probabilités marginales $P(Y=0), P(Y=1), P(Y=e)$ . Question 2 : Calculez l'entropie mutuelle $I(X;Y)$ entre l'entrée et...→
  • 16
    Exercice 2 : Canal discret symétrique binaire (BSC) avec codage correcteur Un système de communication utilise un canal discret symétrique binaire (Binary Symmetric Channel - BSC) où chaque bit est transmis de manière indépendante avec une probabilité d'erreur $p = 0,05$ . L'entrée $X \in \{0, 1\}$ est distribuée uniformément. Une source génère des blocs de données de longueur $N = 100$ bits à un débit $D_s = 2 \times 10^6$ bits/seconde. Un codeur de canal ajoute $M = 50$ bits de parité pour former des mots de code de longueur $n = 150$ bits. Question 1 : Construisez la matrice de transition du canal BSC et calculez l'entropie de l'alphabet d'entrée $H(X)$ ainsi que...→
  • 17
    Exercice 3 : Canal à bruit blanc gaussien additif (AWGN) et limite de Shannon-Hartley Un système de communication exploite un canal à bruit blanc gaussien additif (Additive White Gaussian Noise - AWGN) avec une bande passante $B = 10\text{ MHz}$ . La puissance du signal transmis est $P_s = 10\text{ W}$ et la densité spectrale de puissance du bruit est $N_0/2 = 2 \times 10^{-12}\text{ W/Hz}$ . Le système utilise une modulation numérique sur une largeur de bande $W = 8\text{ MHz}$ occupée au sein de $B$ . Question 1 : Calculez le rapport signal-sur-bruit (SNR) en décibels et la puissance du bruit $P_n$ dans la bande passante du système. Question 2 : En...→
  • 18
    Exercice 1 : Analyse d'un canal discret symétrique avec probabilités d'erreur variables Un système de transmission numérique utilise un canal discret sans mémoire de type symétrique binaire (BSC - Binary Symmetric Channel). Le canal a un alphabet d'entrée $\mathcal{X} = \{0, 1\}$ et un alphabet de sortie $\mathcal{Y} = \{0, 1\}$ . La probabilité d'erreur de transmission est $p_e = 0.15$ . Un message binaire est transmis avec une fréquence d'horloge $f = 1\text{ Mbit/s}$ . On considère deux scénarios : le premier avec 1000 bits à transmettre, le second avec une durée de transmission $T = 2\text{ s}$ . Question 1 : Construire la matrice de transition $P$ du canal BSC. Calculer l'entropie...→
  • 19
    Exercice 2 : Analyse d'un canal à effacement avec probabilité variable Un canal de transmission numérique fonctionne selon le modèle d'effacement (erasure channel). Le canal a un alphabet d'entrée $\mathcal{X} = \{0, 1\}$ et un alphabet de sortie $\mathcal{Y} = \{0, 1, e\}$ où $e$ représente un symbole effacé (non reçu). La probabilité d'effacement est $p_e = 0.20$ . Le système transmet des paquets de taille fixe $L = 128\text{ octets}$ (soit 1024 bits par paquet) à une fréquence $f = 100\text{ kbit/s}$ . On observe une transmission de $N_{\text{paq}} = 50$ paquets consécutifs. La distribution des symboles d'entrée est uniforme. Question 1 : Construire la matrice de transition $P$ du canal à effacement. Calculer l'entropie de...→
  • 20
    Exercice 3 : Canal causal avec atténuation progressive et calcul de capacité Un canal de transmission causal fonctionne selon un modèle d'atténuation logarithmique en fonction du temps. Le canal relie un émetteur à un récepteur distants de $d = 50\text{ m}$ . L'atténuation en dB est modélisée par $A(t) = 20 + 10 \log_{10}(t/t_0)$ où $t_0 = 1\text{ ms}$ et $t$ est le temps d'observation en ms. La puissance d'émission est $P_{\text{tx}} = 30\text{ dBm}$ . Le bruit blanc additif gaussien (AWGN) a une densité spectrale de puissance $N_0 = 10^{-10}\text{ W/Hz}$ . La largeur de bande du canal est $B = 1\text{ MHz}$ . On considère deux intervalles de temps : $t_1 = 10\text{ ms}$ et $t_2 = 100\text{ ms}$ . Question 1 : Calculer...→
  • 21
    Exercice 1 : Canal discret symétrique (BSC) et calcul de capacité Un système de communication numérique utilise un canal de transmission discret symétrique (BSC - Binary Symmetric Channel) pour transmettre des données binaires. Le canal possède les caractéristiques suivantes : Probabilité d'erreur de transmission (probabilité de retournement de bit) : $p = 0.02$ Alphabet d'entrée : $\mathcal{X} = \{0, 1\}$ Alphabet de sortie : $\mathcal{Y} = \{0, 1\}$ La source génère des bits équiprobables : $P(X = 0) = P(X = 1) = 0.5$ Puissance de transmission moyenne : $P_{moy} = 1 \text{ Watt}$ Le canal obéit à la matrice de transition suivante : lorsqu'on envoie un bit 0, il arrive en tant que 0 avec probabilité $1-p$ et en...→
  • 22
    Exercice 2 : Canal à effacement (Erasure Channel) et calcul de capacité Un système de communication utilise un canal à effacement binaire (BEC - Binary Erasure Channel) pour la transmission de données. Ce type de canal est utilisé dans les systèmes de communication souterrains et les transmissions sur fibre optique avec détection insuffisante. Alphabet d'entrée : $\mathcal{X} = \{0, 1\}$ Alphabet de sortie : $\mathcal{Y} = \{0, 1, ?\}$ où le symbole $?$ représente l'effacement Probabilité d'effacement : $\epsilon = 0.1$ Lorsqu'un bit est transmis, il arrive soit correctement (probabilité $1 - \epsilon$ ), soit effacé (probabilité $\epsilon$ ) Les bits non effacés sont toujours reçus correctement (pas d'erreur de transmission)...→
  • 23
    Exercice 3 : Canal AWGN (Additive White Gaussian Noise) et capacité en hyperfréquences Un système de communication numérique utilise un canal continu de transmission en hyperfréquences affecté par un bruit blanc gaussien additif (AWGN - Additive White Gaussian Noise). Ce type de canal modélise les communications satellitaires, radios et fibres optiques avec bruit thermique. Bande passante du canal : $B = 20 \text{ MHz}$ Puissance moyenne de transmission : $P = 10 \text{ W}$ Densité spectrale de puissance de bruit : $N_0 / 2 = 1 \times 10^{-12} \text{ W/Hz}$ Puissance de bruit total : $P_N = N_0 \times B = 2 \times 10^{-12} \times B$ Le signal et le bruit sont indépendants et gaussiens La modulation utilisée est à bande limitée Question 1 : Calculer...→
  • 24
    Exercice 1 : Analyse d'un canal discret symétrique avec calcul de capacité Un système de transmission numérique utilise un canal de transmission modélisé comme un canal discret symétrique (BSC - Binary Symmetric Channel). Le canal possède les caractéristiques suivantes : Alphabet d'entrée : $\mathcal{X} = \{0, 1\}$ Alphabet de sortie : $\mathcal{Y} = \{0, 1\}$ Probabilité d'erreur par bit : $p = 0.1$ Probabilité de transmission correcte : $1 - p = 0.9$ Distribution d'entrée uniforme : $P(X=0) = P(X=1) = 0.5$ Nombre de symboles transmis par seconde : $R_{sym} = 10^6$ symboles/s Question 1 : Construisez la matrice de transition $P(Y|X)$ du canal BSC, puis calculez l'entropie conditionnelle $H(Y|X)$ en bits par symbole. Interprétez le sens physique...→
  • 25
    Exercice 2 : Analyse d'un canal à effacement (erasure channel) et calcul de la capacité Un canal de transmission à effacement (erasure channel) est utilisé pour modéliser une liaison satellites défaillante. Ce canal possède les caractéristiques suivantes : Alphabet d'entrée : $\mathcal{X} = \{0, 1\}$ Alphabet de sortie : $\mathcal{Y} = \{0, 1, ?\}$ (où ? représente un effacement) Probabilité d'effacement : $\epsilon = 0.2$ Probabilité de transmission correcte : $1 - \epsilon = 0.8$ Pas de probabilité d'erreur (flip) : les symboles transmis sont soit reçus correctement, soit effacés Longueur du bloc de données : $N = 1000$ symboles Taux d'information souhaité : $R = 0.6$ bits par symbole Question 1 : Construisez la matrice de...→
  • 26
    Exercice 3 : Analyse d'un canal causal avec bruit blanc et calcul de la capacité water-filling Un canal de transmission causal (avec mémoire) est modélisé comme un canal à bande passante limitée avec du bruit blanc additif gaussien (AWGN). Le système fonctionne sur plusieurs intervalles de temps (bins de fréquence) avec les caractéristiques suivantes : Nombre de bins de fréquence indépendants : $K = 4$ Puissance de signal disponible (totale) : $P_{total} = 10$ W Gains de canal pour chaque bin : $h_1 = 1.0, h_2 = 0.8, h_3 = 0.5, h_4 = 0.3$ Puissances de bruit pour chaque bin : $\sigma_1^2 = 0.1, \sigma_2^2 = 0.2, \sigma_3^2 = 0.3, \sigma_4^2 = 0.4$ W Largeur de bande totale : $B = 1$ MHz Largeur de bande par bin...→
  • 27
    Exercice 1 : Analyse d'un canal discret symétrique binaire avec caractérisation progressive Un système de transmission numérique utilise un canal discret symétrique binaire (BSC) pour transmettre des données d'une source vers un récepteur. Le canal possède une probabilité d'erreur symétrique $p = 0.15$ . L'alphabet d'entrée et de sortie du canal est $\mathcal{X} = \mathcal{Y} = \{0, 1\}$ . Une première expérience considère une distribution d'entrée uniforme où $P(X=0) = P(X=1) = 0.5$ . Question 1 : Construire la matrice de transition $P(Y|X)$ du canal BSC avec $p = 0.15$ . Calculer les probabilités conjointes $P(X,Y)$ et les probabilités marginales $P(Y)$ pour la distribution d'entrée uniforme. Vérifier que la somme des probabilités marginales...→
  • 28
    Exercice 2 : Analyse d'un canal à effacement quaternaire avec capacité variable Un système de transmission utilise un canal à effacement (erasure channel) quaternaire où chaque symbole d'entrée peut être reçu correctement avec probabilité $1 - \epsilon$ , ou être effacé (erasure) avec probabilité $\epsilon$ . L'alphabet d'entrée compte quatre symboles $\mathcal{X} = \{0, 1, 2, 3\}$ et l'alphabet de sortie comprend ces quatre symboles plus un symbole d'effacement noté $?$ , soit $\mathcal{Y} = \{0, 1, 2, 3, ?\}$ . La probabilité d'effacement est $\epsilon = 0.25$ . Une source produit une séquence de symboles uniformément distribués. Question 1 : Construire la matrice de transition $P(Y|X)$ du canal à effacement quaternaire avec $\epsilon = 0.25$ ....→
  • 29
    Exercice 1 : Analyse d'un canal de transmission symétrique BSC avec code de correction Un système de transmission numérique utilise un canal discret symétrique binaire (BSC - Binary Symmetric Channel) pour transmettre des données. Le canal a une probabilité d'erreur par bit $p_e = 0.15$ . L'alphabet d'entrée est binaire : $\mathcal{X} = \{0, 1\}$ et l'alphabet de sortie est également binaire : $\mathcal{Y} = \{0, 1\}$ . On transmet des messages de longueur $n = 1000$ bits. La matrice de transition du canal est définie par les probabilités conditionnelles $P(Y|X)$ . Le codeur utilise un code répétition-3 (chaque bit est répété 3 fois) pour améliorer la fiabilité. La capacité...→
  • 30
    Exercice 2 : Analyse du canal à effacement (Erasure Channel) avec correction d'erreurs Un système de communication par satellite utilise un canal à effacement binaire (BEC - Binary Erasure Channel). Ce canal transmet les bits sans erreur, mais avec une probabilité $p_{eff} = 0.25$ , il efface le bit (le récepteur ne sait pas si le bit était 0 ou 1). L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ et l'alphabet de sortie est $\mathcal{Y} = \{0, 1, ?\}$ où ? représente l'effacement. Une séquence de $N = 100$ bits est transmise. Pour corriger les effacements, on utilise une parité simple : on transmet $k = 5$ bits d'information, suivi de $m = 1$ bit de...→
  • 31
    Exercice 3 : Canal asymétrique avec probabilités d'erreur différentes et distribution optimale d'entrée Un système de transmission utilise un canal discret asymétrique où les probabilités d'erreur dépendent de l'entrée. L'alphabet d'entrée est binaire $\mathcal{X} = \{0, 1\}$ , l'alphabet de sortie est aussi binaire $\mathcal{Y} = \{0, 1\}$ . Le canal est défini par les probabilités : $P(Y = 1 | X = 0) = 0.1$ (probabilité d'erreur si on envoie 0), et $P(Y = 0 | X = 1) = 0.3$ (probabilité d'erreur si on envoie 1). Une séquence de $N = 1000$ bits informatifs doit être transmise. On souhaite trouver la distribution d'entrée optimale qui maximise la capacité du canal et calculer le nombre de bits d'information que l'on peut transmettre de...→
  • 32
    Exercice 1 : Canal discret symétrique avec bruit additif Un système de transmission numérique utilise un canal de transmission binaire symétrique (BSC - Binary Symmetric Channel) avec une probabilité d'erreur par bit $p = 0.1$ . Le canal opère selon un modèle discret sans mémoire, ce qui signifie que chaque bit transmis est affecté indépendamment par le bruit. L'alphabet d'entrée et de sortie sont tous deux $\mathcal{X} = \mathcal{Y} = \{0, 1\}$ . La source émet des bits avec les probabilités $P(X=0) = 0.6$ et $P(X=1) = 0.4$ . Question 1 : Construire la matrice de transition $P(Y|X)$ du canal binaire symétrique (BSC). Cette matrice de transition décrit les probabilités conditionnelles...→
  • 33
    Exercice 2 : Canal à effacement avec source d'information Un système de communication utilise un canal à effacement binaire (BEC - Binary Erasure Channel) pour transmettre des informations. Le canal à effacement est caractérisé par une probabilité d'effacement $p_e = 0.2$ , ce qui signifie que chaque symbole transmis a une probabilité 0.2 d'être effacé (ni 0 ni 1, mais un symbole d'effacement noté '?'), et une probabilité 0.8 de transiter correctement. L'alphabet d'entrée est $\mathcal{X} = \{0, 1\}$ et l'alphabet de sortie est $\mathcal{Y} = \{0, 1, ?\}$ . La source émettrice a une distribution de probabilité $P(X=0) = 0.3$ et $P(X=1) = 0.7$ . Question 1 : Construire la matrice de...→
  • 34
    Exercice 3 : Canal gaussien discret avec codage et calculateur de SNIR Un système de communication utilise un canal gaussien discret sans mémoire pour transmettre des symboles d'une constellation $M$ -aire. Le signal reçu en sortie du canal est donné par : $Y = X + Z$ où $X$ est le symbole transmis, $Z$ est le bruit gaussien additif blanc (BBAG) avec une variance $\sigma^2 = N_0 / 2$ . On considère une modulation M-PSK avec $M = 4$ (QPSK) et une puissance du signal transmis $P_X = 1$ . La densité spectrale de puissance du bruit unilatérale est $N_0 = 0.1$ W/Hz. L'intervalle de temps d'un symbole est $T_s = 1 \text{ seconde}$ . La bande passante...→
• Codage correcteur d’erreur (28 Exercices)
  • 1
    On considère un code linéaire binaire $C(7,4)$ capable de corriger les erreurs de transmission. Ce code est défini par la matrice génératrice suivante : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ 1. Calculez la matrice de parité $H$ du code $C(7,4)$ et déduisez le syndrome pour le vecteur reçu $r = (1,0,1,1,0,1,0)$ . 2. Déterminez la distance de Hamming minimale $d_{min}$ du code en analysant tous les mots du code générés par les vecteurs d'information non nuls. 3. Calculez la probabilité d'erreur non détectée $P_{e,nd}$ si la probabilité d'erreur binaire du canal est $p = 0.01$ .→
  • 2
    Un système de communication utilise un code de Hamming $C(15,11)$ pour protéger une transmission sur un canal binaire symétrique. On considère deux mots de code transmis : $c_1 = (1,1,0,1,0,1,0,1,0,1,0,1,0,1,1)$ et $c_2 = (0,1,0,0,1,0,1,0,1,1,0,1,1,0,1)$ . 1. Calculez la distance de Hamming $d_H(c_1, c_2)$ entre les deux mots de code et vérifiez si ceux-ci appartiennent au même espace code linéaire. 2. Déterminez la capacité de correction d'erreur $t$ et la capacité de détection $e$ de ce code de Hamming $C(15,11)$ , puis évaluez le nombre d'erreurs correables et détectables. 3. Pour un mot reçu $r = (1,0,0,1,0,1,0,1,0,1,0,1,0,1,1)$ contenant possiblement une erreur, calculez le syndrome de Hamming et identifiez...→
  • 3
    Exercice 1 : Analyse Complète d'un Code Linéaire (7,4) de Hamming Un code linéaire binaire $C(7,4)$ est utilisé pour corriger les erreurs de transmission sur un canal bruyant. Ce code encode 4 bits d'information en 7 bits en ajoutant 3 bits de parité. La matrice génératrice du code est définie par : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : Encoder le message d'information $\mathbf{u} = [1, 0, 1, 1]$ en utilisant la matrice génératrice pour obtenir le mot de code $\mathbf{c} = \mathbf{u} \cdot G$ . Vérifier que le mot de code obtenu appartient à l'espace du code en calculant le produit $\mathbf{c} \cdot H^T = \mathbf{0}$ où $H$ est la matrice de contrôle de parité...→
  • 4
    Exercice 2 : Étude Comparative de Codes Linéaires : Rendement et Capacité de Détection On considère trois codes linéaires différents pour la transmission de données numériques sur un canal bruyant : Code A : Code (5,2) avec matrice génératrice $G_A = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \end{pmatrix}$ Code B : Code (7,4) de Hamming (voir Exercice 1) Code C : Code (15,11) pour transmission haut débit Question 1 : Pour le Code A, déterminer la matrice de contrôle de parité $H_A$ et calculer la distance minimale $d_{min,A}$ en énumérant tous les mots de code non-nuls. Encoder les deux messages d'information $\mathbf{u}_1 = [1, 0]$ et $\mathbf{u}_2 = [1, 1]$ , puis vérifier l'appartenance...→
  • 5
    Exercice 1 : Code linéaire (7,4) et distance de Hamming Soit un code linéaire C(7,4) défini par la matrice génératrice : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : Calculer tous les mots de code générés par cette matrice génératrice (16 mots au total). Exprimer explicitement les codewords pour les messages d'entrée suivants : $\mathbf{m}_1 = [0,0,0,1]$ , $\mathbf{m}_2 = [1,0,1,0]$ et $\mathbf{m}_3 = [1,1,1,1]$ . Question 2 : Déterminer la distance de Hamming minimale $d_{min}$ du code en examinant tous les poids de Hamming des codewords générés. Question 3 : Calculer le nombre d'erreurs corrigeables $t$ et le nombre d'erreurs détectables $e$ par ce code. En déduire la capacité...→
  • 6
    Exercice 2 : Matrice de parité et syndrome de décodage On considère le même code linéaire (7,4) de l'exercice 1 avec matrice génératrice G. La matrice de parité H est construite telle que $G \cdot H^T = 0$ . Question 1 : Déterminer la matrice de parité H de dimension $(3 \times 7)$ et vérifier la relation $G \cdot H^T = 0$ . Question 2 : Un mot reçu corrompu est $\mathbf{r} = [1,0,1,1,0,1,1]$ . Calculer le syndrome $\mathbf{s} = \mathbf{r} \cdot H^T$ et déduire la position de l'erreur. Quel était le codeword original transmis ? Question 3 : Pour une séquence de 10 bits d'information encodée avec ce code (7,4), calculer le taux de codage...→
  • 7
    Exercice 2 : Matrice génératrice et code linéaire [n, k] On considère un code linéaire binaire $[7, 4]$ avec la matrice génératrice suivante : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Soit un mot d'information $m = (1, 0, 1, 1)$ . 1. Calculez le mot de code $c$ généré par $c = m \cdot G$ . Vérifiez que la distance de Hamming entre ce mot et le vecteur nul est égale à la distance minimale du code. 2. Déterminez la matrice de parité $H$ du code et calculez le syndrome $s$ pour un mot reçu $r = (1, 0, 0, 1, 1, 1, 0)$ . Identifiez la position de l'erreur. 3. Estimez le nombre de mots de code distincts, la taille de l'espace...→
  • 8
    Exercice 1 : Code linéaire systématique et distance de Hamming On considère un code linéaire binaire (7,4) défini par la matrice génératrice suivante : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Ce code permet de coder des messages de 4 bits en mots de code de 7 bits. Pour ce code, la matrice de parité est : $H = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \ 0 & 1 & 1 & 1 & 0 & 1 & 0 \ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}$ Question 1 : Coder les messages suivants $m_1 = (1,0,1,0)$ et $m_2 = (1,1,1,1)$ en utilisant la matrice génératrice. Calculer ensuite la distance de Hamming $d_H(c_1, c_2)$ entre les deux mots de code obtenus. Rappel : la distance de Hamming entre deux mots binaires est le nombre de positions où les bits diffèrent....→
  • 9
    Exercice 2 : Code de Hamming [7,4] et capacité du canal de Shannon Un canal de transmission binaire symétrique (BSC - Binary Symmetric Channel) a une probabilité d'erreur par bit $p_e = 0.01$ . On souhaite transmettre des messages de 4 bits à travers ce canal en utilisant le code de Hamming [7,4] présenté à l'exercice précédent. La capacité du canal de Shannon est donnée par : $C = 1 - H_b(p_e)$ où $H_b(p_e) = -p_e \log_2(p_e) - (1 - p_e) \log_2(1 - p_e)$ est l'entropie binaire. Question 1 : Calculer la capacité du canal $C$ en bits/transmission. Déterminer le taux de codage du code Hamming [7,4] défini par $R = \frac{k}{n}$ où $k = 4$ et $n = 7$ . Vérifier...→
  • 10
    Exercice 3 : Code en blocs systématique et décodage par syndrome On considère un code linéaire binaire systématique $(n, k) = (10, 5)$ défini par la matrice génératrice sous forme systématique : $G = [I_5 | P]$ où $I_5$ est la matrice identité 5×5 et $P$ est une matrice 5×5 de bits de parité : $P = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 \ 0 & 1 & 1 & 0 & 0 \ 1 & 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 1 & 1 \ 1 & 0 & 0 & 1 & 1 \end{pmatrix}$ La matrice de parité de ce code est $H = [P^T | I_5]$ où $P^T$ est la transposée de $P$ . Question 1 : Pour les messages $m_1 = (1, 0, 1, 0, 1)$ et $m_2 = (0, 1, 1, 1, 0)$ , coder ces messages en utilisant le code (10, 5) et calculer les mots de code $c_1$ et $c_2$ . Calculer ensuite la distance de Hamming...→
  • 11
    Exercice 1 : Code linéaire en blocs et distance de Hamming On considère un code linéaire C défini par la matrice génératrice suivante : $G = \begin{pmatrix} 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 1 \end{pmatrix}$ Ce code transforme les mots de source de dimension $k = 2$ en mots codés de dimension $n = 4$ (code $[4,2]$ ). Question 1 : Énumérer tous les mots de code possibles en effectuant le produit $\mathbf{m} \cdot G$ pour chaque vecteur source $\mathbf{m}$ . Construire la table complète des 4 mots de code. Question 2 : Déterminer la distance de Hamming minimale $d_{min}$ du code en calculant les distances entre tous les couples de mots de code. Quel est...→
  • 12
    Exercice 2 : Code de Hamming [7,4] et correction d'erreur Le code de Hamming [7,4] est un code linéaire qui transforme 4 bits de donnée en 7 bits codés avec 3 bits de parité. La matrice génératrice est : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ La matrice de contrôle de parité est : $H^T = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : Coder les deux mots source suivants avec la matrice $G$ : $\mathbf{m}_1 = [1,0,1,0]$ et $\mathbf{m}_2 = [1,1,0,1]$ . Déterminer les mots codés complets. Question 2 : On reçoit le mot $\mathbf{r} = [1,1,1,0,1,0,1]$ qui contient potentiellement une erreur. Calculer le syndrome $\mathbf{s} = \mathbf{r} \cdot H^T$ et identifier la position de l'erreur. Question 3 : Après correction...→
  • 13
    Exercice 3 : Code linéaire en treillis et capacité de canal On considère un code convolutif (treillis) binaire simple avec les paramètres suivants : longueur de contrainte $K = 3$ , taux de code $R = 1/2$ , polynômes générateurs $G_1(D) = 1 + D^2$ et $G_2(D) = 1 + D + D^2$ (représentation polynomiale). Question 1 : Pour la séquence d'entrée binaire $\mathbf{u} = [1, 0, 1]$ , calculer la séquence de sortie encodée $\mathbf{c}$ en utilisant les polynômes générateurs. Tracer le diagramme d'état du treillis correspondant. Question 2 : On reçoit le mot reçu $\mathbf{r} = [1,1,0,0,1,0]$ (séquence de 6 bits après encodage d'une entrée de 3 bits). Utiliser l'algorithme de Viterbi pour décoder et retrouver la séquence...→
  • 14
    Exercice 1 : Code linéaire systématique (7,4) et distance de Hamming On considère un code linéaire binaire systématique $(n, k) = (7, 4)$ utilisé pour la transmission de données sur un canal bruyant. Ce code possède une matrice génératrice sous forme systématique : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 0 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$ Question 1 : Calculer les mots de code correspondant aux deux mots d'information suivants : $\mathbf{u}_1 = (1, 0, 1, 0)$ et $\mathbf{u}_2 = (1, 1, 0, 1)$ . Déterminer le nombre total de mots de code pour ce code et justifier pourquoi ce code peut corriger jusqu'à combien d'erreurs en déterminant sa distance minimale par calcul exhaustif de toutes les distances de Hamming entre paires de mots de code...→
  • 15
    Exercice 2 : Code de Hamming (15,11) et capacité du canal de Shannon On étudie un code de Hamming étendu $(15, 11)$ pour la transmission de données sur un canal binaire symétrique (BSC) avec probabilité d'erreur $p$ . Ce code corrige 1 erreur et détecte 2 erreurs. On considère l'envoi de $M = 2^{11} = 2048$ messages distincts, chacun encodé en $2^{15}$ mots de code possibles. Question 1 : Déterminer les paramètres du code (15,11) : la distance minimale $d_{min}$ , la redondance $r = n - k$ , la longueur d'un mot de code, le nombre de mots de code, et la capacité théorique de correction d'erreur $t$ ....→
  • 16
    Exercice 3 : Code LDPC et décodage itératif avec analyse de treillis On considère un code de contrôle de parité peu dense (LDPC) défini par une matrice de contrôle de parité $H$ de dimension $(8 \times 15)$ avec une structure spécifique : chaque ligne a exactement 3 uns (degré de ligne = 3) et chaque colonne a exactement 2 uns (degré de colonne = 2), excepté 4 colonnes qui ont un seul 1 chacune. La matrice génératrice implicite crée un code $(15, 7)$ avec $2^7 = 128$ mots de code possibles. Question 1 : Déterminer la matrice génératrice $G$ du code LDPC $(15, 7)$ en utilisant...→
  • 17
    Exercice 1 : Analyse d'un code linéaire et distance de Hamming On considère un code linéaire binaire $\mathcal{C}$ de dimension $k = 3$ et de longueur $n = 6$ . La matrice génératrice du code est : $G = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$ Un message information est $\mathbf{u} = (1, 0, 1)$ . Question 1 : Calculer le mot de code $\mathbf{c} = \mathbf{u} \cdot G$ correspondant au message $\mathbf{u}$ . Question 2 : Déterminer la distance minimale $d_{min}$ du code $\mathcal{C}$ en énumérant tous les mots de code non nuls et leurs poids de Hamming respectifs. Question 3 : On reçoit un mot reçu $\mathbf{r} = (1, 0, 1, 1, 0, 0)$ . Calculer le syndrome $\mathbf{s}$ et déterminer si le mot reçu...→
  • 18
    Exercice 2 : Code de Hamming [7,4] et capacité de canal de Shannon On considère le code de Hamming [7,4] avec la matrice génératrice : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ On émet un mot de code $\mathbf{c}_{transmis} = (0, 1, 1, 0, 1, 0, 0)$ sur un canal binaire symétrique de probabilité d'erreur $p = 0{,}1$ . Question 1 : Vérifier que le mot $\mathbf{c}_{transmis}$ est un mot de code valide du [7,4]. Calculer son poids de Hamming. Question 2 : Calculer la probabilité qu'exactement 1 erreur se produise lors de la transmission du mot de code sur le canal. Calculer la probabilité qu'aucune erreur ne se produise. Question 3 : Calculer la capacité...→
  • 19
    Exercice 1 : Distance de Hamming et code linéaire (7,4) On considère un code linéaire en bloc (7,4) de Hamming utilisé pour protéger les transmissions numériques. Ce code ajoute 3 bits de parité à 4 bits d'information pour créer des mots de code de longueur 7. La matrice génératrice du code est : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : Calculer les 4 premiers mots de code (correspondant aux vecteurs d'information $\mathbf{u}_1 = [1,0,0,0]$ , $\mathbf{u}_2 = [0,1,0,0]$ , $\mathbf{u}_3 = [0,0,1,0]$ , $\mathbf{u}_4 = [0,0,0,1]$ ) en effectuant les multiplications matricielles $\mathbf{c} = \mathbf{u} \cdot G$ (opérations en arithmétique modulo 2). Lister tous les 4 mots de code générés. Question 2 : À partir...→
  • 20
    Exercice 2 : Limite de Shannon et capacité de canal Un canal de transmission binaire symétrique (BSC) transmet des données numériques avec une probabilité d'erreur bit (BER) de $p = 0.01$ . On utilise un code correcteur pour améliorer la transmission d'une source discrète générant des symboles avec une entropie $H(X) = 0.8\text{ bits/symbole}$ . Le débit binaire du canal est $R_b = 1\text{ Mbps}$ . Question 1 : Calculer la capacité du canal binaire symétrique $C_{BSC}$ en bits par utilisation du canal en utilisant la formule $C = 1 - H(p)$ , où $H(p) = -p \log_2(p) - (1-p) \log_2(1-p)$ est la fonction d'entropie binaire. Déterminer ensuite le débit maximal sans erreur $R_{max} = C_{BSC} \times R_b$ . Question 2 :...→
  • 21
    Exercice 3 : Code linéaire (15,11) et paramètres d'un code On considère un code linéaire systématique (15,11) utilisé dans les normes de télécommunications. Ce code ajoute 4 bits de contrôle de parité à 11 bits d'information. La matrice génératrice réduite du code est en forme systématique : $G = [I_{11} | P]$ , où $P$ est une matrice $11 \times 4$ . Question 1 : Soit un vecteur d'information $\mathbf{u} = [1,1,0,1,0,1,1,0,1,1,0]$ . Calculer le mot de code correspondant $\mathbf{c} = [\mathbf{u} | \mathbf{p}]$ où $\mathbf{p} = \mathbf{u} \cdot P \pmod{2}$ . Supposons que la matrice P est donnée de sorte que les bits de parité résultants sont $\mathbf{p} = [1,0,1,0]$ . Calculer le poids de Hamming $w(\mathbf{c})$ du...→
  • 22
    Exercice 1 : Distance de Hamming et capacité du canal de Shannon On considère un code linéaire binaire $C$ de longueur $n = 7$ et de dimension $k = 4$ . Le code est généré par la matrice génératrice : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : Calculez la distance de Hamming entre les deux mots-codes $c_1 = (1,0,1,0,0,1,1)$ et $c_2 = (0,1,0,1,1,0,0)$ . Puis, déterminez le poids de Hamming de chaque mot-code. Question 2 : En supposant que le poids minimal du code est $d_{min} = 3$ , calculez la capacité de correction d'erreur et la capacité de détection d'erreur. Donnez aussi le nombre d'erreurs corrigeables $t$ selon la formule $t = \lfloor \frac{d_{min} - 1}{2} \rfloor$ ....→
  • 23
    Exercice 2 : Code linéaire et matrice de contrôle de parité Considérons un code linéaire $[7,4]$ (code de Hamming) avec la matrice génératrice : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : À partir de la matrice génératrice $G$ , dérivez la matrice de contrôle de parité $H$ de dimension $3 \times 7$ , sachant que $H$ doit satisfaire $G \cdot H^T = 0$ . Question 2 : Encodez le message d'information $m = (1,0,1,1)$ en multipliant par $G$ pour obtenir le mot-code $c$ . Vérifiez ensuite que $c \cdot H^T = 0$ . Question 3 : Pour un mot reçu $r = (1,0,1,1,0,1,0)$ potentiellement entaché d'erreur, calculez le syndrome $s = r \cdot H^T$ . Déterminez si une erreur a été...→
  • 24
    Exercice 3 : Codage en treillis et probabilité d'erreur On considère un code convolutif de rendement $R = 1/2$ avec une longueur de contrainte $K = 3$ . Les polynômes générateurs sont $g^{(1)}(D) = 1 + D + D^2$ et $g^{(2)}(D) = 1 + D^2$ . On transmet une séquence d'information $u = (1,0,1)$ . Question 1 : Calculez la séquence de sortie codée $c$ en utilisant les polynômes générateurs. Donnez les deux séquences de sortie $c^{(1)}$ et $c^{(2)}$ . Question 2 : Déterminez la distance de Hamming minimale $d_{min}$ du code en comparant tous les chemins du treillis partant d'un état initial. Supposez que le poids minimal d'une séquence codée non triviale est $d_{min} = 5$ ....→
  • 25
    Paramètres d’un code et détection d’erreur : exemple d’un [7, 4] On considère le code linéaire binaire systématique de paramètres [7,4]. Voici sa matrice génératrice : $G = \begin{pmatrix}1 & 0 & 0 & 0 & 1 & 0 & 1\\0 & 1 & 0 & 0 & 1 & 1 & 0\\0 & 0 & 1 & 0 & 0 & 1 & 1\\0 & 0 & 0 & 1 & 1 & 1 & 1\end{pmatrix}$ Déterminez le nombre total de mots de code et la fraction du taux de codage. Cherchez la distance minimale du code en listant les poids Hamming des mots non nuls. Pour le mot reçu $r = (1,1,0,1,0,1,0)$ , précisez si une erreur est détectable et corrigeable en utilisant la matrice de contrôle $H$ (à construire explicitement).→
  • 26
    Exercice 1 : Code linéaire systématique et distance de Hamming On considère un code linéaire binaire $C$ défini par la matrice génératrice suivante : $G = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}$ Ce code transforme des mots d'information de $k = 3$ bits en des mots de code de $n = 6$ bits. Les trois dernières colonnes correspondent aux bits de parité. Question 1 : Déterminer la matrice de contrôle de parité $H$ pour ce code linéaire. Vérifier que $G \times H^T = 0$ , puis calculer la distance de Hamming $d_H$ entre les mots de code $c_1 = 101010$ et $c_2 = 110011$ . Question 2 : Encoder le message d'information $m = 110$ en utilisant la matrice génératrice $G$ ....→
  • 27
    Exercice 2 : Code de Hamming et théorème de Shannon On considère un canal de transmission binaire symétrique avec une probabilité d'erreur $p = 0.01$ . On utilise un code de Hamming $[7, 4]$ pour protéger les données transmises. Données : Capacité du canal : $C = 1 - H_b(p)$ où $H_b(p) = -p \log_2(p) - (1-p)\log_2(1-p)$ Probabilité d'erreur par bit : $p = 0.01$ Code de Hamming [7,4] : $n = 7, k = 4, d_{min} = 3$ Taux de code : $R = k/n = 4/7$ Question 1 : Calculer la capacité du canal de Shannon $C$ en bits. Vérifier que le taux de code $R$ satisfait l'inégalité $R Question 2 : Calculer la probabilité d'erreur non corrigée après décodage du code de Hamming. Supposons que le décodeur corrige une erreur unique ($ d_{min} = 3 $) mais échoue avec 2 erreurs ou plus. Évaluer la probabilité $ P_e $ qu'une séquence de 7 bits transmise contienne au least une erreur non corrigée. Question 3 : Comparer la performance du code de Hamming avec un système sans codage. Calculer le taux d'erreur symbole (SER) pour une transmission de $ N = 10000 $ symboles sans codage et avec le code de Hamming. Déterminer l'amélioration en dB du rapport signal-à-bruit effectif (SNR) grâce au codage correcteur.→
  • 28
    Exercice 3 : Code de Hamming étendu et matrice génératrice On considère une extension du code de Hamming standard appelée code de Hamming étendu $[8, 4]$ . Ce code ajoute un bit de parité global au code de Hamming $[7, 4]$ standard pour augmenter la distance minimale à $d_{min} = 4$ . Données : Code de Hamming étendu [8,4] avec matrice génératrice $G_{ext}$ Paramètres : $n = 8, k = 4, d_{min} = 4$ Capacité de correction : jusqu'à 1 erreur simple ou détection de 2 erreurs (SECDED) Redondance : $n - k = 4$ bits de parité Question 1 : Construire la matrice génératrice $G_{ext}$ pour le code de Hamming étendu [8,4]. Déterminer la matrice...→
• codage canal (33 Exercices)
  • 1
    Exercice 1 : Codage de Hamming et correction d'erreurs simples Un système de communication numérique utilise un code de Hamming $(7,4)$ pour la transmission de données sur un canal bruité. Le code de Hamming $(7,4)$ encode $k = 4$ bits d'information en $n = 7$ bits de code en ajoutant $r = 3$ bits de parité. La matrice génératrice du code est : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ La matrice de contrôle de parité est : $H = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \ 1 & 0 & 1 & 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}$ Un message d'information $m = (1, 0, 1, 1)$ doit être transmis. En transmission, le codeword reçu est $r = (1, 0, 1, 1, 1, 0, 0)$ (vecteur ligne). Question 1 : Calculer le codeword transmis $c$ en effectuant l'opération $c = m \cdot G$ (multiplication matricielle sur $\mathbb{F}_2$ )....→
  • 2
    Exercice 2 : Codage convolutif et diagramme en treillis Un encodeur convolutif binaire de longueur de contrainte $K = 3$ utilise deux polynômes générateurs : $g_1(D) = 1 + D^2$ et $g_2(D) = 1 + D + D^2$ . Cet encodeur produit 2 bits de sortie pour chaque bit d'entrée (code de rendement $R_c = 1/2$ ). L'état de l'encodeur est représenté par deux bits de mémoire. Un message d'information $u = (1, 0, 1)$ doit être transmis, suivi de deux bits terminaux (pad bits) $(0, 0)$ pour ramener l'encodeur à l'état zéro. L'équation de récurrence pour les sorties est : $y_{1,t} = u_t + u_{t-2} \pmod{2}$ $y_{2,t} = u_t + u_{t-1} + u_{t-2} \pmod{2}$ Question 1 : Tracer le diagramme d'états de l'encodeur convolutif avec $K = 3$ et identifier les transitions...→
  • 3
    Exercice 3 : Codage LDPC et décodage par propagation de croyance Un code LDPC (Low-Density Parity-Check) est défini par une matrice de parité $H$ de dimension $m \times n = 4 \times 8$ avec structure régulière $(d_v, d_c) = (2, 4)$ , où $d_v = 2$ est le poids des colonnes (variables) et $d_c = 4$ est le poids des lignes (équations de parité). La matrice de parité est : $H = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}$ Un codeword reçu $r = (1, 0, 1, 0, 1, 1, 0, 1)$ est décodé. Les probabilités a priori (canal) pour chaque bit reçu sont supposées tirées d'un canal AWGN avec LLR (Log-Likelihood Ratio) : $L(r_i) = \frac{2 r_i}{\sigma^2}$ où $\sigma^2 = 1.0$ est la variance du bruit. Question 1 : Calculer les LLR initiaux $L(r_i)$ pour...→
  • 4
    Exercice 1 : Conception et performance d'un code de Hamming (7,4) pour correction d'erreur Un système de communication numérique utilise un code de Hamming (7,4) pour la transmission de données sur un canal bruyant. Ce code peut corriger une erreur simple et détecter des erreurs doubles. On considère un bloc de $m = 4$ bits d'information à encoder en $n = 7$ bits codés. Les paramètres du système sont : Nombre de bits d'information : $m = 4$ Nombre de bits de code : $n = 7$ Nombre de bits de parité : $r = 3$ Distance minimale du code : $d_{min} = 3$ Probabilité d'erreur au bit (BER) du canal :...→
  • 5
    Exercice 2 : Analyse d'un code de Golay (23,12) et calcul de la capacité effective Un système de communication utilise un code de Golay (23,12) pour améliorer la transmission de données sur un canal AWGN. Ce code est très performant et peut corriger jusqu'à 3 erreurs. Les paramètres du système sont : Longueur du code : $n = 23$ bits Nombre de bits d'information : $k = 12$ bits Distance minimale : $d_{min} = 7$ Capacité de correction : $t = 3$ erreurs Nombre de bits de parité : $r = 11$ Probabilité d'erreur par bit sur le canal : $p_b = 0.001$ Débit brut du canal : $R_{brut} = 100 kbits/s$ Nombre de mots...→
  • 6
    Exercice 3 : Conception d'un code de convolution rate-1/2 pour transmission vidéo Un système de transmission vidéo utilise un code de convolution de taux $R = 1/2$ (un bit d'information produit deux bits codés) avec un polynôme générateur $G(D) = [1+D^2, 1+D+D^2]$ . Ce code répète essentiellement chaque bit d'information, ce qui améliore la performance du système. Les paramètres du système sont : Taux de code : $R = 1/2$ Longueur de contrainte : $K = 3$ Distance libre du code : $d_f = 5$ Polynôme générateur 1 : $G_1(D) = 1 + D^2$ Polynôme générateur 2 : $G_2(D) = 1 + D + D^2$ Débit brut vidéo (avant codage) : $R_{video} = 40 Mbits/s$ Probabilité d'erreur par bit du canal : $p_b = 0.01$ Nombre...→
  • 7
    Exercice 1 : Conception et analyse d'un code de Hamming(7,4) Un système de transmission de données utilise un code de Hamming(7,4) pour la correction d'erreurs. Ce code encode 4 bits de données en 7 bits de code au total, avec 3 bits de parité. La matrice génératrice du code est : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ La matrice de parité est : $H = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \ 1 & 0 & 1 & 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}$ Un vecteur de données d'entrée est $\mathbf{d} = (1, 0, 1, 1)$ . Ce vecteur est transmis par un canal bruyant qui introduit une erreur simple à la position 5 (numérotation à partir de 1). Question 1 : Calculer le mot de code $\mathbf{c}$ généré en...→
  • 8
    Exercice 2 : Code convolutif de débit 1/2 et décodage par l'algorithme de Viterbi Un système de codage convolutif utilise un code (2, 1, 3) avec débit de code $R = 1/2$ et longueur de contrainte $K = 3$ . Les polynômes générateurs sont : $G_1(D) = 1 + D^2$ $G_2(D) = 1 + D + D^2$ où $D$ représente l'opérateur de retard d'une unité temporelle. La séquence de bits d'entrée à coder est $\mathbf{u} = (1, 0, 1, 0, 0)$ suivi d'au moins $K-1 = 2$ bits de vidage (flush bits) pour ramener le registre à décalage à l'état zéro. Question 1 : Construire le diagramme d'état du code convolutif et tracer le chemin complet dans le diagramme de trellis pour...→
  • 9
    Exercice 3 : Code LDPC régulier et décodage itératif par passage de messages Un code LDPC (Low-Density Parity-Check) régulier $(n, k, d_v, d_c)$ est défini avec les paramètres suivants : • Longueur du code : $n = 12$ • Dimension : $k = 6$ • Degré des variables (colonne) : $d_v = 3$ • Degré des contraintes (ligne) : $d_c = 2$ La matrice de parité creuse $H$ est définie en notation compacte (Parity-Check Matrix) où chaque ligne représente une contrainte de parité et chaque colonne un symbole de code : $H = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$ Un mot de code valide est transmis et reçu avec la séquence $\mathbf{r} = (1.2, -0.8, 0.3, 1.5, -1.1, 0.9, -0.7, 1.3, 0.2, -0.5, -1.2, 0.8)$ (valeurs de fiabilité en log-vraisemblance). Question...→
  • 10
    Exercice 1 : Conception et Décodage d'un Code de Hamming (7,4) On considère un système de transmission de données utilisant un code de Hamming (7,4) pour la correction d'erreurs simples. Ce code encode 4 bits d'information en 7 bits de code. Le message à transmettre est $m = (m_1, m_2, m_3, m_4) = (1, 0, 1, 1)$ . Les bits de parité sont calculés selon les équations linéaires suivantes : $p_1 = m_1 \oplus m_2 \oplus m_4$ $p_2 = m_1 \oplus m_3 \oplus m_4$ $p_4 = m_2 \oplus m_3 \oplus m_4$ où $\oplus$ représente l'opération XOR (addition modulo 2). Le codeword transmis est arrangé comme $c = (p_1, p_2, m_1, p_4, m_2, m_3, m_4)$ aux positions 1 à 7. Question 1 : Calculez les trois bits de parité $p_1$ , $p_2$ , et $p_4$ pour le...→
  • 11
    Exercice 2 : Codage par Convolution et Analyse du Treillis On considère un encodeur de convolution binaire avec un taux de codage $R = \frac{1}{2}$ , une longueur de contrainte $K = 3$ , et les polynômes générateurs suivants : $g^{(1)} = (1, 0, 1)_{\text{octal}} = 5_8$ (sortie 1) $g^{(2)} = (1, 1, 1)_{\text{octal}} = 7_8$ (sortie 2) L'encodeur reçoit une séquence d'entrée $m = (1, 0, 1)$ (3 bits d'information). Pour chaque bit d'entrée, deux bits de sortie sont générés par convolution avec les polynômes générateurs. L'état initial de l'encodeur est $s_0 = 00$ (registre à décalage vide). Question 1 : Tracez le diagramme d'état (ou treillis) de l'encodeur de convolution. Calculez manuellement les bits de sortie pour chaque bit d'entrée...→
  • 12
    Exercice 3 : Code LDPC Régulier et Performance de Décodage On considère un code LDPC (Low-Density Parity-Check) régulier défini par une matrice de parité $H$ de dimension $(n-k) \times n = 8 \times 16$ . Le code est régulier avec les paramètres $(d_v, d_c)$ où $d_v = 3$ est le poids de colonne (nombre de 1 par colonne) et $d_c = 6$ est le poids de ligne (nombre de 1 par ligne). La matrice $H$ est creuse : elle contient environ 3% de 1 et 97% de 0. Un message source de $k = 8$ bits est encodé en un codeword de longueur $n = 16$ . Le codeword est transmis sur un canal symétrique...→
  • 13
    Exercice 1 : Code de Hamming et détection/correction d'erreurs Un système de transmission numérique utilise un code de Hamming (7,4) pour la correction d'erreurs simples. Ce code encode 4 bits d'information en 7 bits de données. Les bits d'information sont $d_1, d_2, d_3, d_4$ et les bits de parité sont $p_1, p_2, p_4$ positionnés aux positions puissances de 2. La matrice génératrice est : $\mathbf{G} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Un message d'information transmis est $\mathbf{d} = [1, 0, 1, 1]$ . Pendant la transmission, le mot de code reçu est $\mathbf{r} = [1, 0, 1, 1, 0, 1, 1]$ , ce qui diffère du mot de code envoyé par exactement un bit en position 5. Question 1 : En utilisant la matrice...→
  • 14
    Exercice 2 : Code de Répétition et Code BCH pour correction d'erreurs multiples Un système de communication utilise d'abord un code de répétition simple (3,1) puis on envisage de le remplacer par un code BCH. Le code de répétition (3,1) encode chaque bit 1 en trois copies identiques : 1→111 et 0→000. Ce code peut corriger jusqu'à 1 erreur par bloc de 3 bits. Une séquence de 12 bits d'information $\mathbf{d} = [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0]$ doit être transmise. Après codage en répétition, le vecteur reçu sur le canal présente des erreurs aléatoires. On considère aussi un code BCH(15,11) qui peut corriger jusqu'à $t = 2$ erreurs....→
  • 15
    Exercice 3 : Code Convolutif et Décoding Viterbi Un codeur convolutif binaire utilise 2 registres à décalage avec un taux de codage $R = 1/2$ , ce qui signifie qu'un bit d'entrée produit 2 bits de sortie. Le polynôme générateur en retour est $G(D) = (1 + D, 1 + D^2)$ (forme octal : (3, 5)). La mémoire de codage est $K = 3$ . Un message d'information $\mathbf{m} = [1, 0, 1]$ doit être codé, puis transmis sur un canal bruyant. Le mot de code reçu présente une erreur : $\mathbf{r} = [1, 0, 0, 0, 1, 1]$ au lieu du mot correct. Question 1 : Calculer le mot de code complet générée par le codeur convolutif pour l'entrée $\mathbf{m} = [1, 0, 1]$ ....→
  • 16
    Exercice 1 : Code de Hamming (7,4) pour correction d'erreurs Un système de communication utilise un code de Hamming (7,4) pour détecter et corriger les erreurs de transmission. Ce code ajoute 3 bits de parité à 4 bits d'information, formant des mots de code de 7 bits. La matrice génératrice du code est donnée par : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Un message d'information de 4 bits est transmis : $\mathbf{m} = [1, 0, 1, 1]$ . Pendant la transmission sur un canal bruyant, le mot de code reçu présente une erreur simple (un seul bit erroné) : $\mathbf{r} = [1, 0, 1, 1, 0, 0, 1]$ . Question 1 : Calculez le mot de code émis...→
  • 17
    Exercice 2 : Code de Hamming étendu (8,4) avec parité globale On considère un code de Hamming étendu (8,4) qui ajoute un bit de parité globale au code Hamming (7,4) pour détecter les erreurs doubles. La matrice génératrice étendue est : $G_{ext} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \end{pmatrix}$ Un message m = [1, 1, 0, 1] est encodé et transmis sur un canal AWGN. Après transmission, deux mots reçus différents sont observés : • Cas 1 (une erreur) : $\mathbf{r}_1 = [1, 1, 0, 1, 0, 1, 1, 1]$ • Cas 2 (deux erreurs) : $\mathbf{r}_2 = [1, 1, 0, 1, 1, 0, 0, 1]$ Question 1 : Calculez le mot de code émis $\mathbf{c}_{ext} = \mathbf{m} \cdot G_{ext}$ (modulo 2). Question 2 : Pour le mot reçu...→
  • 18
    Exercice 3 : Code LDPC (Low-Density Parity-Check) simplifié pour codage canal Un code LDPC binaire simplifié est défini par une matrice de contrôle de parité H de dimensions 4×8 : $H = \begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}$ Ce code produit des mots de code de longueur $n = 8$ bits à partir de $k = 4$ bits d'information. Le taux du code est $R = k/n = 0,5$ . Trois mots reçus différents sont testés : • Mot 1 (sans erreur) : $\mathbf{r}_1 = [1, 0, 1, 0, 1, 1, 0, 0]$ • Mot 2 (une erreur) : $\mathbf{r}_2 = [1, 0, 1, 0, 1, 1, 0, 1]$ • Mot 3 (deux erreurs) : $\mathbf{r}_3 = [1, 0, 1, 1, 1, 1, 1, 0]$ Question 1 : Pour le mot reçu $\mathbf{r}_1$ , calculez les syndromes de parité pour chaque équation...→
  • 19
    Exercice 1 : Codage de Hamming pour correction d'erreurs simples Un système de communication utilise un code de Hamming [7,4] pour protéger les données transmises sur un canal bruyant. Ce code ajoute 3 bits de parité pour protéger 4 bits d'information. La matrice génératrice du code est $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ et la matrice de parité est $H = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \ 1 & 0 & 1 & 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}$ . Un message d'information $m = [1, 0, 1, 1]$ est à transmettre. Le canal introduit une erreur aléatoire sur un seul bit de la séquence codée. Question 1 : Encoder le message $m$ en utilisant le code de Hamming. Calculer le mot-code $c = m \cdot G$ (en arithmétique modulo 2). Vérifier que...→
  • 20
    Exercice 2 : Code de Repetition et décodage par vote majoritaire Un système de transmission utilise un code de répétition (repetition code) pour améliorer la fiabilité. Chaque bit d'information est répété $N = 3$ fois. Le code transforme donc un message de $k$ bits en un message codé de $n = 3k$ bits. Le canal est un canal symétrique binaire avec probabilité d'erreur $p = 0.1$ . Le décodage utilise la règle du vote majoritaire : si au moins 2 bits sur 3 sont identiques, la valeur de la majorité est décodée. Un message original $m = [1, 0, 1]$ est codé, transmis et reçu avec $r = [1, 0, 1, 1, 0, 0, 1, 1, 0]$ . Question 1...→
  • 21
    Exercice 1 : Codage Hamming (7,4) - Détection et correction d'erreurs Un système de transmission numérique utilise le code de Hamming (7,4) pour protéger l'information contre les erreurs de transmission. Ce code permet de transmettre 4 bits d'information en encodant 7 bits au total. Les bits de parité sont calculés selon les relations suivantes : Bit de parité $p_1$ : couvre les positions 1, 3, 5, 7 (binaire : bit 0 = 1) Bit de parité $p_2$ : couvre les positions 2, 3, 6, 7 (binaire : bit 1 = 1) Bit de parité $p_3$ : couvre les positions 4,...→
  • 22
    Exercice 2 : Code Convolutif (3,1,3) - Analyse de performance et décodage Viterbi Un code convolutif $(3, 1, 3)$ est utilisé pour un système de transmission fiable. Ce code a une longueur de contrainte $K = 3$ , accepte 1 bit à la fois et produit 3 bits codés (rendement R = 1/3). La séquence génératrice est définie par : Générateur G1 : $g_1 = [1, 1, 1]$ (polynôme : $1 + D + D^2$ ) Générateur G2 : $g_2 = [1, 0, 1]$ (polynôme : $1 + D^2$ ) Générateur G3 : $g_3 = [1, 1, 0]$ (polynôme : $1 + D$ ) Message à encoder : $1001$ (4 bits) État initial du registre à décalage : $00$ Taux d'erreur binaire du canal...→
  • 23
    Exercice 3 : Code BCH (31,16) - Construction et propriétés de correction d'erreurs Un code BCH (Bose-Chaudhuri-Hocquenghem) (31, 16) est utilisé pour un système de transmission robuste. Ce code est capable de corriger jusqu'à $t = 3$ erreurs. Les paramètres du code sont : Longueur du codeword : $n = 31$ bits Longueur de l'information : $k = 16$ bits Nombre de bits de parité : $m = n - k = 15$ bits Capacité de correction : $t = 3$ erreurs Distance minimale : $d_{min} = 2t + 1 = 7$ Polynôme générateur du BCH : $g(x) = (x^{15} + x + 1)(x^{15} + x^4 + x^3 + x^2 + 1)$ Message à encoder : $1101001011010010$ (16 bits) Taux d'erreur binaire du canal : $BER = 5 \times 10^{-2}$ Question 1 : Encodez le message 16 bits...→
  • 24
    Exercice 1 : Codage Hamming (7,4) et détection d'erreurs Un système de communication utilise un code Hamming (7,4) pour transmettre des messages sur un canal bruité. Le code Hamming (7,4) encode 4 bits d'information en 7 bits de code. Une séquence d'information est $\mathbf{d} = (1, 0, 1, 1)$ . La matrice génératrice est : $\mathbf{G} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ Question 1 : Calculer le mot de code $\mathbf{c} = \mathbf{d} \cdot \mathbf{G}$ (multiplication en arithmétique modulo 2). Question 2 : Supposons qu'une erreur simple survient et que le mot reçu est $\mathbf{r} = (1, 1, 1, 1, 0, 1, 0)$ . Calculer le syndrome $\mathbf{s} = \mathbf{r} \cdot \mathbf{H}^T$ où $\mathbf{H}$ est la matrice de parité. Question 3 : Déterminer la position de l'erreur...→
  • 25
    Exercice 2 : Code de répétition et probabilité d'erreur par bloc Un système de communication utilise un code de répétition simple : chaque bit d'information est transmis 3 fois (code (3,1)). Le canal de transmission est binaire symétrique avec probabilité d'erreur par bit $p_b = 0{,}1$ . Un bloc d'information de 2 bits $\mathbf{d} = (1, 0)$ est codé puis transmis. Question 1 : Écrire le mot de code complet pour les 2 bits d'information (6 bits transmis au total), puis calculer la probabilité qu'aucune erreur ne survienne durant la transmission du bloc entier. Question 2 : À la réception, le décodeur utilise un décodage...→
  • 26
    Exercice 3 : Code LDPC simple et décodage itératif Un code LDPC simplifié (Low-Density Parity-Check) a une matrice de parité H de taille 4×8 (4 équations de parité, 8 bits de code). La matrice est : $\mathbf{H} = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}$ Question 1 : Vérifier qu'un mot de code $\mathbf{c} = (1, 1, 0, 0, 1, 0, 1, 1)$ satisfait toutes les équations de parité ( $\mathbf{c} \cdot \mathbf{H}^T \equiv \mathbf{0} \pmod{2}$ ). Question 2 : Un mot erroné $\mathbf{r} = (1, 1, 0, 1, 1, 0, 1, 1)$ est reçu (erreur au bit 4). Calculer le syndrome $\mathbf{s} = \mathbf{r} \cdot \mathbf{H}^T \pmod{2}$ et identifier les équations de parité violées. Question 3 : En utilisant la propriété de parcimonie de la matrice H, calculer le taux de rendement $R = \frac{k}{n}$ du code...→
  • 27
    Exercice 1 : Codage de Hamming (7,4) avec détection et correction d'erreurs Un système de transmission utilise le code de Hamming (7,4) pour la correction d'erreurs simples. Ce code encode 4 bits d'information en 7 bits de code. La matrice génératrice du code est : $G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$ La matrice de contrôle de parité est : $H = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \ 1 & 0 & 1 & 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}$ Un message d'information de 4 bits $m = [m_1, m_2, m_3, m_4] = [1, 0, 1, 1]$ doit être transmis. Question 1 : Calculer le mot de code $c = m \cdot G$ en effectuant la multiplication matricielle modulo 2. Vérifier que le mot de code satisfait la condition $c \cdot H^T \equiv 0 \pmod{2}$ (parité correcte). Question 2 : Supposons qu'une erreur simple...→
  • 28
    Exercice 2 : Codage convolutif avec diagramme en treillis et viterbi Un code convolutif (3,2) avec longueur de contrainte $K = 3$ est défini par les polynômes générateurs : $G_1(D) = 1 + D + D^2$ $G_2(D) = 1 + D^2$ Où D représente l'opérateur de retard unitaire. À chaque pas de temps, 2 bits d'entrée ( $u_1$ et $u_2$ ) produisent 3 bits de sortie. L'état de l'encodeur est représenté par les deux derniers bits d'entrée stockés. Une séquence d'information de 3 pas de temps doit être transmise : $u^{(1)} = [1, 0]$ , $u^{(2)} = [0, 1]$ , $u^{(3)} = [1, 1]$ . Question 1 : Déterminer les états possibles de l'encodeur et tracer le diagramme d'état complet. Pour...→
  • 29
    Exercice 1 : Codage de Hamming (7,4) pour transmission de données avec correction automatique Un système de transmission de données par satellite utilise un code de Hamming (7,4) pour corriger les erreurs de transmission. Ce code encode 4 bits d'information en 7 bits (4 bits informatifs + 3 bits de parité). La matrice génératrice du code est notée $G$ et la matrice de contrôle est notée $H$ . Pour un mot d'information $\mathbf{m} = [m_1, m_2, m_3, m_4]^T$ , le mot de code transmis est $\mathbf{c} = G \cdot \mathbf{m}$ . Un mot reçu $\mathbf{r}$ peut contenir une erreur. Le syndrome du code est calculé par $\mathbf{s} = H \cdot \mathbf{r}^T$ . Si...→
  • 30
    Exercice 2 : Code de parité simple avec analyse de détection Un système de transmission utilise un code de parité simple pour détecter (mais non corriger) les erreurs. Pour chaque bloc de $k = 7$ bits de données, on ajoute 1 bit de parité (bit de redondance) pour former un mot de code de longueur $n = 8$ bits. La parité choisie est la parité paire (un nombre pair de '1' dans le mot de code complet). Le message à transmettre est $d = (1, 1, 0, 1, 0, 1, 0)$ . Question 1 : Calculer le bit de parité $p$ pour le message donné. Construire le mot de code complet $c$...→
  • 31
    Exercice 3 : Code convolutif avec algorithme de Viterbi Un code convolutif avec un facteur de contrainte (constraint length) de $K = 3$ et un taux (rate) de $R = 1/2$ est utilisé pour le codage canal. Le polynôme générateur est défini par deux polynômes en notation octale : $G_1 = (7)_8 = (111)_2$ et $G_2 = (5)_8 = (101)_2$ . L'entrée du codeur est une séquence de données $u = (1, 0, 1)$ (3 bits), suivie de 2 bits de queue pour terminer le treillis (state = 0). Question 1 : Construire la table des états et les transitions du treillis du code convolutif. Calculer la séquence de sortie codée $c$ pour la séquence d'entrée...→
  • 32
    Exercice 1 : Code de Hamming (7,4) pour correction d'erreur simple Un système de communication numérique utilise un code de Hamming (7,4) pour la correction automatique d'erreur lors de la transmission de données binaires. Ce code peut corriger une erreur simple dans chaque bloc de 7 bits transmis. Nombre de bits d'information : $k = 4$ Nombre total de bits du code : $n = 7$ Nombre de bits de parité : $m = n - k = 3$ Matrice génératrice du code : $G = [I_4 | P]$ où $I_4$ est la matrice identité $4 \times 4$ et $P$ est la matrice de parité Message d'information à encoder : $\mathbf{u} = [1, 0, 1, 1]$ Un bit d'erreur est introduit...→
  • 33
    Exercice 3 : Code LDPC (Low-Density Parity-Check) et décodage itératif Un système de communication exploite un code LDPC (Low-Density Parity-Check) pour la correction d'erreurs avec décodage itératif en graphe bipartite. Les codes LDPC modernes approchent la limite de Shannon. Longueur du code : $n = 12$ bits Nombre d'équations de parité : $m = 6$ Nombre de bits d'information : $k = n - m = 6$ bits Taux de code : $R = k / n = 0.5$ Matrice de parité $H$ : régulière avec degré des variable $d_v = 2$ et degré des check $d_c = 2$ Mot de code transmis : $\mathbf{c} = [1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1]$ Séquence reçue avec $E_b/N_0 = 5 \text{ dB}$ : $\mathbf{r} = [0.8, -0.2, 0.9, 0.1, -0.6, 0.8, -0.1, -0.2, 0.9, 0.8, -0.3, 0.7]$ (valeurs de log-vraisemblance) Question 1 : Construire la matrice...→
resume de Theorie de l'information TD 1 corrige Theorie de l'information TD 2 corrige Theorie de l'information TD 3 corrige Theorie de l'information TD 4 corrige Theorie de l'information autre TD 4 corrige Theorie de l'information Des TD corriges Theorie de l'information examen corrige Theorie de l'information autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige Codage autre examen corrige codage autre examen corrige codage autre examen corrige codage autre examen corrige codage autre examen corrige codage autre examen corrige codage

Exercice

💡

Astuce

Appui long sur le contenu pour voir rapidement le corrigé sans changer d'onglet !

💡 Corrigé (appui long)

❓ Question (appui long)

📊 Schéma

100%

Pincez pour zoomer • Double-cliquez pour réinitialiser • Échap pour fermer