Section 7 - Codage de source

Introduction¶

Le codage de source vise à améliorer la représentation des données en réduisant leur redondance tout en préservant leur contenu informatif. Cette amélioration est essentielle pour minimiser l’utilisation des ressources de communication, telles que la largeur de bande et l’énergie, tout en garantissant une transmission efficace et fiable. L’objectif principal du codage de source est d’atteindre une compression maximale des données tout en respectant les limites théoriques établies par l’entropie de Shannon (plus d’informations à venir). Ces concepts ont été proposés par Claude Shannon, dans son célèbre article intitulé «A Mathematical Theory of Communication». REF: A Mathematical Theory of Communication

Le codage de source est une technique essentielle pour réduire les besoins en ressources tout en maintenant l’intégrité des données. Les critères de performance clés du codage de source incluent la longueur moyenne des codes, qui doit être proche de l’entropie de la source, ainsi que la variance des longueurs de code, qui reflète la régularité des représentations. Ces métriques permettent d’évaluer l’efficacité d’un algorithme de codage et son adaptabilité aux caractéristiques statistiques des données, garantissant ainsi une transmission améliorée dans des systèmes de communication modernes.

En télécommunications, une source génère des données qui doivent être transmises ou stockées. Ces sources peuvent être classées en sources continues et sources discrètes, selon la nature des données produites. Le codage de source s’applique uniquement aux sources discrètes. Les sources continues, bien qu’importantes dans les communications, nécessitent une étape de numérisation pour être adaptées au codage de source. Cette distinction met en évidence le rôle central des données discrètes dans la conception des systèmes de communication modernes.

Paramètres d’une source discrète¶

Définition: Une source discrète (discrete source) produit des séquences de données distincts, chacun ayant une probabilité d’occurrence. Ces symboles sont générés en fonction des caractéristiques statistiques de la source.

Propriétés :

• L’ensemble des symboles $\mathcal{S}$ représente toutes les valeurs possibles qu’une source discrète peut produire.

• La probabilité d’occurence $p_i$ d’un symbole $s_i$ représente la fréquence relative avec laquelle ce symbole apparaît dans la sortie de la source. Notez que
  $$\sum_{i=1}^{K} p_i = 1,$$

  (1)
  où $K$ est le nombre total de symboles dans l’ensemble $\mathcal{S}$.

Entropie de Shannon¶

Avec sa théorie, Shannon a introduit une technique pour quantifier l’information. Nous les définirons ici.

Définition: L’information

L’information apportée par une donnée $s_i$, en bits, est inversément proportionnelle à sa probabilité d’occurrence. Elle est donnée par :

$$I(s_i) = \log_2 \frac{1}{p_i} = -\log_2 p_i \;\;\;\; \textrm{ bits}$$

(2)

Notez que les symboles fréquents contiennent moins d’information quand $I(s_i)$ est faible, et les symboles rares contiennent plus d’information quand $I(s_i)$ est élevé.

Définition: L’entropie

L’entropie (entropy) de la source $H(\mathcal{S})$ est la quantité moyenne d’information produite par symbole. Elle représente une mesure de l’incertitude ou de la redondance d’une source discrète. Elle est définie par :

$$H(\mathcal{S}) = -\sum_{i=1}^{K} p_i \log_2 p_i \;\;\;\; \textrm{ bits}$$

(3)

Une source avec des symboles équiprobables (tous les symboles ont des probabilités égales), donc $p_i = \frac{1}{K}$ a une entropie maximale $H(\mathcal{S}) = \log_2 K$. Aucune autre source disposant de $K$ données ne peut créer une entropie plus élevée.

$H(\mathcal{S}) = 0$ si un seul symbole a une probabilité de 1 (source déterministe). Cela signifie qu’il n’y a pas d’incertitude associée à cette source.

Codage de source¶

Le codage de source peut être interprété comme une technique d’étiquetage où chaque symbole produit par une source discrète est associé à une séquence binaire unique (un code). Ce processus vise à réduire la longueur moyenne des codes attribués aux symboles, en fonction de leurs probabilités d’occurrence.

L’objectif est d’associer à chaque symbole $s_k$ un mot de (code binaire), exprimé par $\bf{d}_k$ de longueur $l_k$, comme:

Critères de performance d’un codeur de source¶

Pour évaluer son efficacité, plusieurs critères de performance sont pris en compte, comme décrit ci-dessous. Ces critères permettent d’évaluer l’efficacité et l’adéquation des algorithmes de codage de source pour des applications spécifiques. Un bon algorithme doit minimiser la longueur moyenne des codes et la redondance, tout en maximisant l’efficacité de compression, tout cela avec une complexité raisonnable.

• Longueur moyenne des codes ($\bar{l}$) :

  La longueur moyenne des codes est la moyenne pondérée des longueurs des codes attribués aux symboles de la source, calculée comme

  $$\bar{l} = \sum_{i=1}^{K} p_i l_i \;\;\;\; \textrm{ bits}$$

  (6)

  L’objectif est de minimiser $\bar{l}$ tout en garantissant un codage décodable de manière unique. Notez que même si $\bar{l}$ n’est pas un nombre entier, chaque valeur de $l_i$ doit être un nombre entier.

• Variance des Longueurs de Codes ($\sigma_l^2$) :

  La variance mesure la dispersion des longueurs des codes autour de la moyenne

  $$\sigma_l^2 = \sum_{i=1}^{K} p_i (l_i - \bar{l})^2 \hspace{1cm} \text{ bits$^2$}.$$

  (9)

  L’objectif est de réduire la variance pour garantir une régularité dans les longueurs des codes. Une variance faible simplifie la synchronisation et le décodage.

• Redondance : La redondance mesure l’écart entre la longueur moyenne des codes et l’entropie

  $$R = \bar{l} - H(\mathcal{S}) \hspace{1cm} \text{bits}$$

  (11)

  L’objectif est de réduire la redondance pour se rapprocher de l’efficacité optimale ($\bar{l} \approx H(\mathcal{S})$).

• Efficacité de compression : L’efficacité de compression est le rapport entre l’entropie et la longueur moyenne des codes :

  $$\text{Efficacité de compression} = \frac{H(\mathcal{S})}{\bar{l}} \times 100\%.$$

  (14)

  On veut maximiser l’efficacité de compression.

• Taux de Compression

  Pour un fichier, taux de compression mesure la réduction de la taille des données grâce au codage

  $$\text{Taux de compression} = \frac{\text{Taille originale}}{\text{Taille compressée}}.$$

  (16)

  L’objectif est d’obtenir un taux de compression élevé sans perte de données pour le codage sans perte. Dans le cas limite d’un grand nombre de données générées, le taux de compression devient égal à l’efficacité de la compression.

• Complexité de codage et décodage

  La complexité est évaluée par le temps et les ressources nécessaires pour encoder ou décoder les données.

  On veut réduire la complexité tout en maintenant une efficacité élevée.

Codage de Huffman¶

Le codage de Huffman est une méthode de codage de source optimale basée sur les probabilités des symboles. C’est-à-dire que les codes de Huffman donnent la longueur de code moyenne, $\bar{l}$, la plus courte possible. Un codage optimal comme Huffman attribue des codes plus courts aux symboles fréquents pour réduire .

Elle attribue des codes binaires plus courts aux symboles fréquents et des codes plus longs aux symboles rares. Le codage de Huffman, avec ses applications dans le texte, les images et les vidéos, constitue une méthode efficace pour atteindre cet objectif. Cette approche illustre la manière dont les principes mathématiques, tels que l’entropie de Shannon, se traduisent en solutions pratiques pour les défis des télécommunications modernes.

Le codage de source en tant que technique d’étiquetage attribue des séquences binaires aux symboles d’une source discrète, en optimisant la longueur moyenne des codes ($\bar{l}$) pour minimiser la redondance. Cette approche repose sur les probabilités des symboles ($p_k$) et leur relation avec l’information contenue ($I(s_k)$). Le résultat est une représentation efficace des données qui utilise des codes courts pour les symboles fréquents et des codes plus longs pour les symboles rares, respectant les contraintes de décodage unique et d’optimisation de la compression.

Resumé¶

Cette section traite de O7. Choix des techniques de codage de source adaptées à la compression des informations. Elle aborde les techniques visant à réduire la redondance des données, à compresser efficacement l’information et à approcher les limites théoriques fixées par l’entropie de Shannon. Le but est de comprendre comment optimiser la représentation des données pour minimiser l’utilisation des ressources de transmission tout en préservant l’intégrité de l’information.