1. **Énoncé du problème :** Calculer la probabilité d'occurrence de chaque caractère dans le message "SCIENCES TEC" (sans espace), puis déterminer l'entropie, construire l'arbre de Huffman, coder, calculer la longueur du message codé, comparer avec ASCII, et décoder des séquences binaires. 2. **Calcul des probabilités :** Le message sans espace est "SCIENCESTEC" (10 caractères). Comptons chaque caractère : - S : 2 fois - C : 2 fois - I : 1 fois - E : 3 fois - N : 1 fois - T : 1 fois Probabilités $p(x) = \frac{\text{nombre d'occurrences}}{10}$ : - $p(S) = \frac{2}{10} = 0.2$ - $p(C) = 0.2$ - $p(I) = 0.1$ - $p(E) = 0.3$ - $p(N) = 0.1$ - $p(T) = 0.1$ 3. **Calcul de l'entropie $E$ :** Formule : $$E = -\sum_{x} p(x) \log_2 p(x)$$ Calculons chaque terme : - $-0.3 \log_2 0.3 \approx -0.3 \times (-1.737) = 0.521$ - $-0.2 \log_2 0.2 \approx 0.464$ - $-0.2 \log_2 0.2 \approx 0.464$ - $-0.1 \log_2 0.1 \approx 0.332$ - $-0.1 \log_2 0.1 \approx 0.332$ - $-0.1 \log_2 0.1 \approx 0.332$ Somme : $$E \approx 0.521 + 0.464 + 0.464 + 0.332 + 0.332 + 0.332 = 2.445$$ bits 4. **Construction de l'arbre de Huffman :** - Étape 1 : trier les caractères par probabilité croissante : I(0.1), N(0.1), T(0.1), S(0.2), C(0.2), E(0.3) - Étape 2 : fusionner les deux plus petites probabilités : I(0.1) + N(0.1) = 0.2 - Étape 3 : nouvelle liste : T(0.1), S(0.2), C(0.2), E(0.3), IN(0.2) - Étape 4 : fusionner T(0.1) + IN(0.2) = 0.3 - Étape 5 : nouvelle liste : S(0.2), C(0.2), E(0.3), TIN(0.3) - Étape 6 : fusionner S(0.2) + C(0.2) = 0.4 - Étape 7 : nouvelle liste : E(0.3), TIN(0.3), SC(0.4) - Étape 8 : fusionner E(0.3) + TIN(0.3) = 0.6 - Étape 9 : fusionner SC(0.4) + ETIN(0.6) = 1.0 5. **Codes de Huffman (en assignant 0 à gauche, 1 à droite) :** - SC(0.4) : S=00, C=01 - ETIN(0.6) : E=10, TIN=11 - TIN(0.3) : T=110, IN=111 - IN(0.2) : I=1110, N=1111 Codes finaux : - S : 00 - C : 01 - E : 10 - T : 110 - I : 1110 - N : 1111 6. **Nombre de bits du message codé :** Message : S C I E N C E S T E C Bits par caractère : - S (2 fois) : 2 bits × 2 = 4 - C (3 fois) : 2 bits × 3 = 6 - I (1 fois) : 4 bits × 1 = 4 - E (3 fois) : 2 bits × 3 = 6 - N (1 fois) : 4 bits × 1 = 4 - T (1 fois) : 3 bits × 1 = 3 Total bits = 4 + 6 + 4 + 6 + 4 + 3 = 27 bits 7. **Longueur moyenne du message codé :** $$L = \sum_x p(x) l(x)$$ où $l(x)$ est la longueur du code de $x$ : - $L = 0.2 \times 2 + 0.2 \times 2 + 0.1 \times 4 + 0.3 \times 2 + 0.1 \times 4 + 0.1 \times 3$ - $L = 0.4 + 0.4 + 0.4 + 0.6 + 0.4 + 0.3 = 2.5$ bits 8. **Comparaison avec codage ASCII :** - ASCII utilise 8 bits par caractère - Message de 10 caractères → $10 \times 8 = 80$ bits - Gain en bits : $80 - 27 = 53$ bits 9. **Utilités du code Huffman :** - Réduction significative de la taille du message codé - Optimisation basée sur la fréquence des caractères - Permet une transmission plus efficace 10. **Décodage des séquences binaires :** - a) 0 0 1 0 0 1 0 1 1 Décodage : 00 = S, 10 = E, 01 = C, 011 = erreur (car 011 n'est pas un code valide), mais 0 1 1 peut être 01 (C) puis 1 restant ? Correction : lire bits successifs : 00(S), 10(E), 01(C), 1 reste → 1 seul bit ne suffit, donc erreur ou séquence incomplète. - b) 0 0 1 1 1 0 Lecture : 00(S), 1110(I) - c) 0 1 1 0 0 1 0 1 1 0 1 1 1 Lecture : 01(C), 100(E), 101(??), 110(T), 111(??) Correction : lire bits successifs : 01(C), 10(E), 01(C), 10(E), 111(??) Il faut lire correctement : 0 1 (C), 1 0 (E), 0 1 (C), 1 1 0 (T), 1 1 1 (IN) 1110 = I, 1111 = N Ici 111 est incomplet, donc séquence incomplète ou erreur. --- **Réponse finale :** - Probabilités : $p(S)=0.2$, $p(C)=0.2$, $p(I)=0.1$, $p(E)=0.3$, $p(N)=0.1$, $p(T)=0.1$ - Entropie $E \approx 2.445$ bits - Codes Huffman : S=00, C=01, E=10, T=110, I=1110, N=1111 - Nombre total de bits codés = 27 - Longueur moyenne = 2.5 bits - Gain par rapport à ASCII = 53 bits - Décodage partiel des séquences binaires donné