Théorèmes de Shannon sur le codage d'un canal de transmission d'informations. Théorème direct de Shannon pour une source de forme générale

10.04.2019

Pour toute performance de la source de message H, inférieure à la capacité du canal C, il existe une méthode de codage qui permet la transmission de toutes les informations créées par la source de message avec une probabilité d'erreur arbitrairement faible.

Bien que la preuve de ce théorème proposée par Shannon ait ensuite été soumise à une représentation mathématique plus profonde et plus rigoureuse, son idée est restée inchangée. Seule l'existence de la méthode de codage souhaitée est prouvée en trouvant la probabilité d'erreur moyenne sur toutes les méthodes de codage possibles et en montrant qu'elle peut être inférieure à une valeur e arbitrairement petite. De plus, il existe au moins une méthode de codage pour laquelle la probabilité d'erreur est inférieure à la moyenne.

Preuve du théorème. Laisser H(x) Et H(x|y) – Entropie a priori et a posteriori par symbole (depuis l'extrémité réceptrice) pour un système implémentant le débit AVEC canal. En raison de la propriété E pendant une durée suffisamment longue ( n symboles), toutes les transmissions possibles d'un ensemble quelconque se répartissent en groupes hautement probables et improbables ; Dans ce cas, les déclarations suivantes peuvent être faites sur le nombre de signaux dans les groupes correspondants :

a) Un groupe de signaux transmis hautement probables contient environ 2 pN(x) séquences.

b) Un groupe de signaux reçus hautement probables contient environ 2 pN(y) séquences.

c) Chaque signal reçu hautement probable pourrait (avec des probabilités à peu près égales) provenir d'environ 2 pN(x | y) signaux transmis d’un groupe à haute probabilité.

d) Chaque signal envoyé par un groupe à haute probabilité peut (avec des probabilités approximativement égales) correspondre à environ 2 pN(y | x) reçu des signaux à haute probabilité.

En raison de la propriété E entropie des processus discrets, avec une augmentation n tous les e et d correspondants tendront vers zéro.

Supposons maintenant que les informations soient transmises sur le même canal avec une vitesse d'entrée égale à N< С. Dans ce cas, le nombre de signaux hautement probables envoyés d'une longueur de n les caractères seront égaux à 2 PN< 2pN(x). Comme déjà noté, le problème du choix d'un code spécifique est d'indiquer lequel des 2 pN(x) les séquences possibles sont sélectionnées comme 2 PN autorisés à l'expédition et comment ils sont divisés en 2 PN sous-groupes 2 pN(y) séquences de sortie. Considérons la classe de tous les codes possibles qui seront obtenus si 2 PN séquences autorisées à publier au hasard parmi 2 pN(x) signaux possibles d'un groupe à haute probabilité ; Trouvons la probabilité d'erreur moyenne pour ces codes.

Laisse un signal être reçu à k. La probabilité d'erreur est égale à la probabilité qu'un signal donné puisse provenir de plus d'un des 2 PN signaux autorisés. Puisque le code est obtenu par sélection aléatoire (également probable) 2 PN séquences de 2 pN(x), alors la probabilité qu'un signal donné à l'entrée du canal soit parmi ceux autorisés est égale à

Signal reçu ouais correspond à 2 pN(x | y)éventuellement envoyé des signaux. D'où la probabilité moyenne qu'aucun des 2 pN(x | y) les signaux (sauf celui réellement envoyé) ne sont pas autorisés, est égal à (négliger l'unité par rapport à pN(x|y))

Il s'agit de la probabilité moyenne d'une réception sans erreur. Ensuite, puisque N< С = Н(х) – Н(х| у), Que

N – N(x) = - N(x| y) - h , (8.23)

Où h > 0. En remplaçant (8.23) dans (8.22), nous obtenons

On peut montrer que

ceux. que par un codage aléatoire en blocs suffisamment longs, la probabilité moyenne d'erreur peut être rendue arbitrairement petite. L'affirmation selon laquelle il existe au moins un code ayant une probabilité d'erreur inférieure à la moyenne complète la preuve.

Notez que l’égalité (8.25) est valable pour tout h positif, aussi petit soit-il. Cela signifie que le théorème admet la condition N £ S.

Cela donne une signification particulière au concept de débit : le débit n'est pas seulement la vitesse maximale possible de transfert d'informations, mais la vitesse maximale à laquelle la transmission est encore possible avec une probabilité d'erreur arbitrairement faible.

Deuxième théorème de Shannon sur le codage en présence de bruit. Pour assurer une immunité au bruit suffisante, il est nécessaire d'introduire une redondance dans le signal transmis, réduisant ainsi la vitesse de transmission des informations. Il est tout à fait naturel de craindre qu'à mesure que les restrictions sur la petitesse de la probabilité d'erreur se renforcent, la redondance requise augmente, réduisant progressivement la vitesse de transfert de l'information, peut-être jusqu'à zéro. Cependant, tous les doutes sont levés par le deuxième théorème de codage de Shannon pour les canaux bruyants, qui peut être formulé comme suit :

Théorème.Sous la condition H £ C, parmi les codes qui fournissent (selon le premier théorème) une probabilité d'erreur arbitrairement petite, il existe un code dans lequel le taux de transmission d'informations R est arbitrairement proche du taux de génération d'informations H.

Le taux de transfert d'informations (par symbole) est défini comme

R = H – H(x|y), (8.26)

Où H(x|y) – l'entropie postérieure du signal envoyé par symbole, ou dispersion des informations dans le canal.

La preuve du théorème (voir ) commence par l'affirmation selon laquelle la redondance minimale requise par symbole est égale à H(x|y) caractères supplémentaires. Ils montrent en outre que le code peut être choisi de telle sorte que H(x|y)était arbitrairement petit.

Discussion des théorèmes. Tout d’abord, notons le caractère fondamental des résultats obtenus. Le théorème établit une limite théorique à l'efficacité possible du système lors de la transmission fiable d'informations. L'idée qui semblait intuitivement correcte a été réfutée : obtenir une probabilité d'erreur arbitrairement faible dans le cas de la transmission d'informations sur un canal avec du bruit n'est possible qu'en introduisant une redondance infiniment grande, c'est-à-dire lorsque la vitesse de transmission est réduite à zéro. Il résulte des théorèmes que les interférences dans le canal n'imposent aucune restriction sur la précision de la transmission. La limitation est imposée uniquement sur la vitesse de transmission à laquelle une fiabilité de transmission arbitrairement élevée peut être obtenue.

Les théorèmes sont non constructifs dans le sens où ils n'abordent pas la question des moyens de construire des codes garantissant la transmission idéale spécifiée. Cependant, après avoir démontré la possibilité fondamentale d’un tel codage, ils ont mobilisé les efforts des scientifiques pour développer des codes spécifiques.

Il convient de noter qu'à tout débit de transmission d'informations fini jusqu'au débit, une probabilité d'erreur arbitrairement faible n'est obtenue qu'avec une augmentation illimitée de la durée des séquences de caractères codées. Ainsi, une transmission sans erreur en présence d’interférences n’est possible que théoriquement.

Assurer la transmission d'informations avec une très faible probabilité d'erreur et une efficacité assez élevée est possible lors du codage de séquences de caractères extrêmement longues. En pratique, le degré de fiabilité et d'efficacité est limité par deux facteurs : la taille et le coût des équipements de codage et de décodage et le temps de retard du message transmis. Actuellement, des méthodes de codage relativement simples sont utilisées, qui ne mettent pas en œuvre les capacités spécifiées par la théorie. Cependant, les exigences toujours croissantes en matière de fiabilité de transmission et les progrès de la technologie des circuits intégrés à grande échelle conduisent à l’introduction d’équipements de plus en plus sophistiqués à ces fins.

Il convient cependant de garder à l’esprit que les théorèmes pour les canaux discrets avec bruit, comme le théorème 2 pour les canaux sans bruit, n’indiquent pas que le codage de longues séquences de messages est la seule méthode de codage efficace. Le sens de ces théorèmes est d'affirmer l'existence de méthodes de codage efficaces et d'établir des limites quantitatives à la vitesse maximale possible de transmission de l'information. À cet égard, les énoncés non seulement directs mais aussi inverses de ces théorèmes sont importants. De la preuve des théorèmes, il s'ensuit seulement qu'en codant des séquences de messages suffisamment longues, vous pouvez toujours vous rapprocher autant que vous le souhaitez du taux de transmission de messages maximum possible (avec une probabilité d'erreur minimale pour les canaux avec du bruit). Cela ne signifie toutefois pas qu’il ne peut exister d’autres méthodes de codage efficaces. Au contraire, à l’aide d’un certain nombre d’exemples précis, on peut démontrer que de telles méthodes existent.

Malheureusement, à l'heure actuelle, aucune méthode générale n'a été trouvée pour construire des codes efficaces pour les canaux avec du bruit qui satisfassent à diverses exigences pratiques. Mais peu à peu, de telles méthodes sont identifiées. Une affirmation très intéressante et importante est le théorème selon lequel dans un canal bruyant avec un manque de fiabilité arbitrairement faible de la transmission des messages ( →0), le taux de transmission des informations peut être arbitrairement proche de C C . Auparavant, l'opinion dominante, basée sur des considérations intuitives, était que, sous ces exigences, la vitesse de transmission des informations devrait diminuer indéfiniment.

L'importance fondamentale des théorèmes est qu'ils permettent, connaissant les valeurs limites (théoriques) du taux de transfert d'informations C C , évaluer l’efficacité des méthodes de codage utilisées.

Ainsi, les théorèmes donnés sont des théorèmes d’existence.

De la preuve de ces théorèmes, il ne ressort pas comment construire un code et effectuer un décodage de telle sorte que la probabilité d'erreur soit aussi faible que souhaité et que la vitesse de transmission soit aussi proche que souhaité de la capacité de la ligne de communication. Les théorèmes sont de nature asymptotique, c'est-à-dire ne sont pas constructifs. Cependant, la connaissance même des capacités potentielles est d'une grande importance : comparer les caractéristiques des systèmes réels avec les limites théoriques permet de juger du niveau atteint et de la faisabilité de coûts supplémentaires pour l'augmenter. Les questions appliquées sont examinées dans une section spéciale de la théorie de l'information - la théorie du codage, qui étudie les méthodes de construction de codes spécifiques et leurs propriétés, en particulier les dépendances exactes ou limites des probabilités d'erreur sur les paramètres du code.

Théorème de Shannon inverse pour les canaux bruyants. Le théorème inverse précise les conditions qui surviennent lorsque des informations sont transmises sur un canal bruyant à une vitesse dépassant sa capacité.

Théorème.Si le taux de création d’informations H est supérieur au débit du canal C, alors aucun code ne peut rendre la probabilité d’erreur aussi faible que souhaité. La dispersion minimale des informations par symbole réalisable à H > C est égale à H – C ; aucun code ne peut fournir moins de dispersion d’informations.

La preuve du théorème inverse de Shannon peut être trouvée dans.

Le théorème inverse stipule que lorsque H > C une transmission sans erreur n'est pas possible ; De plus, plus le rapport CAROLINE DU NORD, plus l'incertitude résiduelle est grande H(x|y). Cette dernière est associée à la probabilité d'erreur lors de la réception. La question se pose naturellement de savoir comment la probabilité d'erreur minimale obtenue avec le meilleur codage est liée au rapport N/S. Pour un canal binaire, la solution est donnée. À k = N/C< 1 вероятность ошибки e(À) = 0 selon le premier théorème. À À® ¥ e( À) ® 0,5, ce qui signifie que la part des informations transmises sur l'ensemble des informations arrivant à l'entrée du canal tend vers zéro lorsque À® ¥ ; Plus la transmission est rapide, moins d’informations sont transférées.

Questions de sécurité

1. Justifiez la nécessité d’introduire une redondance lors du codage dans un canal bruité.

2. Comment la quantité moyenne d'informations (par symbole) transmise sur un canal discret avec bruit est-elle déterminée ?

3. Comment la vitesse de transmission et la capacité d’un canal bruyant sont-elles déterminées ?

4. Formuler et expliquer les théorèmes de codage direct et inverse de Shannon pour un canal bruyant.

5. Quelles relations découlent du théorème sur l'équiprobabilité asymptotique de chaînes typiques suffisamment longues pour les canaux stationnaires avec bruit ?

6. Quelle est la raison du codage de longues séquences de caractères ?

7. Quelle formule détermine la capacité d'un canal symétrique binaire sans mémoire, dans quelles conditions la capacité de ce canal disparaît-elle ?

Théorème direct de Shannon pour une source de forme générale A ne pas confondre avec d'autres théorèmes de Shannon.

Théorèmes de Shannon pour une source générale décrire les possibilités de codage d'une source générale à l'aide de codes séparables. En d’autres termes, les capacités maximales de codage sans perte réalisables sont décrites.

Théorème direct

Appliqué au codage lettre par lettre, le théorème direct peut être formulé comme suit :

Pour prouver le théorème, les caractéristiques du code de Shannon-Fano sont examinées. Ce code satisfait aux conditions du théorème et possède les propriétés spécifiées.

Théorème inverse

Le théorème inverse limite le taux de compression maximal réalisable avec un codage sans perte. Lorsqu'il est appliqué au codage lettre par lettre, décrit la limite de la longueur moyenne du mot de passe pour tout code séparable.

Pour tout code séparable avec des longueurs w 1 ,w 2 ,...,w K la longueur moyenne du message est supérieure ou égale à l'entropie source U, normalisé au logarithme binaire du nombre de lettres D dans l'alphabet de l'encodeur :

Littérature

Gabidulin, E.M., Pilipchuk, N.I.§3.4 Théorèmes de Shannon pour la source // Cours sur la théorie de l'information. - M. : MIPT, 2007. - pp. - 214 p. -ISBN5-7417-0197-3

Fondation Wikimédia.

2010.

Voyez ce qu’est le « théorème direct de Shannon pour une source de forme générale » dans d’autres dictionnaires :

A ne pas confondre avec d'autres théorèmes de Shannon. Les théorèmes de Shannon pour une source générale décrivent les possibilités de coder une source générale à l'aide de codes séparables. En d'autres termes, les possibilités maximales réalisables sont décrites... ... Wikipédia

Wikipédia contient des articles sur d'autres personnes portant ce nom de famille, voir Shannon. Claude Elwood Shannon Claude Elwood Shannon ... Wikipédia

- (Anglais Claude Elwood Shannon ; né le 30 avril 1916, Petoskey, Michigan, Michigan, USA, décédé le 24 février 2001, Medford, Massachusetts, USA) Mathématicien et ingénieur électricien américain, l'un des créateurs de la théorie mathématique de l'information, en . .. ... Wikipédia

Wikipédia contient des articles sur d'autres personnes portant ce nom de famille, voir Shannon. Claude Elwood Shannon Claude Elwood Shannon ... Wikipédia

Informations d'encodage

Concepts de base

Les théorèmes de Shannon sur le codage des messages ont été mentionnés ci-dessus. Intuitivement, le codage est l'opération de conversion d'informations sous la forme nécessaire à un traitement ultérieur (transmission sur un canal de communication, stockage dans la mémoire d'un système informatique, utilisation pour la prise de décision, etc.). Il est également clair que lors de la construction d'un système d'information, il est impossible de se passer du codage : toute présentation d'informations implique l'utilisation d'une sorte de codes. Par conséquent, nous analyserons ensuite en détail les fondements théoriques du codage de l’information.

Laisser UN– alphabet arbitraire. Éléments alphabétiques UN sont appelées lettres (ou symboles), et les séquences finies constituées de lettres sont appelées mots dans UN. On pense que dans tout alphabet, il existe un mot vide qui ne contient pas de lettres.

Mot α 1 est appelé le début (préfixe) d'un mot α , si le mot existe α 2, tel que α = α 1 α 2 ; en même temps le mot α 1 est appelé le début propre d'un mot α , Si α 2 n’est pas un vain mot. La longueur du mot est le nombre de lettres du mot (un mot vide a une longueur de 0). Enregistrer α 1 α 2 désigne la connexion (concaténation) de mots α 1 et α 2. Mot α 2 est appelé la terminaison (suffixe) d'un mot α , si le mot existe α 1, tel que α = α 1 α 2 ; en même temps le mot α 2 est appelé la fin propre d'un mot α , Si α 1 n’est pas un vain mot. Un mot vide est par définition considéré comme le début et la fin de n'importe quel mot. α .

Considérez l'alphabet B = {0, 1, …, D– 1), où D≥ 2, et un ensemble arbitraire C. Affichage arbitraire d'un ensemble C en plusieurs mots de l'alphabet B appelé D-ary ensemble d'encodage C(à D= 2 l'encodage sera binaire). Le mappage inverse est appelé décodage. Donnons des exemples d'encodages.

1. Codage de l'ensemble des nombres naturels dans lequel le nombre n= 0 correspond au mot e(0) = 0, et le nombre n≥ 1 mot binaire

e(n) = b 1 b 2 … b l (n)

la plus petite longueur qui satisfait à la condition

C'est évident que b 1 = 1, 2je (n) – 1 ≤ n < 2je (n) et donc

je(n) = + 1 = ]log( n + 1)[,

Où [ x] Et ] x[ désigne le plus grand entier ne dépassant pas x, et le plus petit entier supérieur à x. Mot e(n) est appelée la notation binaire d'un nombre n, et cet encodage est une représentation des nombres dans le système de nombres binaires. Cet encodage est un à un car lorsque n 1 ≠ n 2 mots e(n 1) et e(n 2) différent. Le tableau 5.1 montre la représentation des 16 premiers nombres naturels dans le système de nombres binaires.

Tableau 5.1

Codage e(n)

n	e(n)	n	e(n)	n	e(n)	n	e(n)

2. Encodage des 2 premiers k nombres naturels, pour lesquels chaque nombre n (0 ≤ n < 2k) correspond au mot

e k(n) = 0k – je (n) e(n),

où entrée 0 k – je (n) désigne un mot composé de k – je(n) des zéros, e(n) – représentation d’un nombre n dans le système de nombres binaires discuté ci-dessus. Cet encodage concerne les 16 premiers nombres naturels ( k= 4) est donné dans le tableau 5.2.

Tableau 5.2

Codage e k(n)

n	e k(n)	n	e k(n)	n	e k(n)	n	e k(n)

Laisser UN = {un je, je= 1, 2, ...) est un alphabet fini ou dénombrable dont les lettres sont numérotées avec des nombres naturels. Dans ce cas, l'encodage des lettres de l'alphabet UN peut être spécifié par séquence D-mots littéraux V = {v je, je= 1, 2, …), où v je il y a une image d'une lettre un je. De telles séquences de mots (de l'ensemble V) sont appelés codes (de l'alphabet UN). Si le code est donné V alphabet UN, puis l'encodage des mots, dans lequel chaque mot un je 1 un je 2 …un ik correspond au mot v je 1 v je 2 …vik, est appelé codage lettre par lettre.

Lors du passage du codage un à un des lettres de l'alphabet au codage lettre par lettre des mots de l'alphabet, la propriété du caractère un à un peut ne pas être préservée. Par exemple, le codage e(n) ne conserve pas cette propriété, mais le codage e k(n) le sauvegarde. La propriété un-à-un est préservée par des codes séparables. Code V = {v je, je= 1, 2, …) est dit séparable si de chaque égalité de la forme

v je 1 v je 2 …vik = vj 1 vj 2 …vjl

il s'ensuit que je = k Et v je 1 = vj 1 , v je 2 = vj 2 , … , vik = vjl. Les codes séparables sont également appelés codes à décodage unique.

Les codes préfixes appartiennent à la classe des codes séparables. Code V = {v je, je= 1, 2, …) est appelé préfixe si aucun mot vk n'est le début (préfixe) d'aucun mot vl, je ≠ k. Si chaque mot d'un code préfixe est remplacé par son plus petit début, qui n'est pas le début d'autres mots de code, alors le code résultant sera également un préfixe. Cette opération est appelée troncature du code de préfixe.

Pour le code arbitraire V composé de différents mots, vous pouvez créer une arborescence de codes. Il s'agit d'un graphe orienté qui ne contient pas de cycles, dans lequel le sommet β 1 connecté au sommet β 2 bords dirigés depuis β 1 à β 2 si et seulement si β 2 = β 1 b, Où b Î B = {0, 1, …, D – 1}, D≥ 2. Pour les codes préfixes (et uniquement pour eux), l'ensemble des mots de code coïncide avec l'ensemble des sommets terminaux (sommets dont aucune arête ne provient) de l'arbre de codes.

Théorèmes de codage de base

Les propriétés des codes utiles pour leur application pratique sont déterminées par les théorèmes de codage de base.

Théorème 5.1. L'inégalité de Kraft. Pour l'existence d'un code (séparable) uniquement décodable contenant N mots de code dans l'ensemble (0, 1, D– 1) avec des longueurs n 1 , n 2 , …, nN, il est nécessaire et suffisant que l’inégalité perdure

Preuve. Imaginons que nous ayons une arborescence de codes pour un code de préfixe. La racine de l'arbre de codes forme le niveau 0, les sommets associés à la racine forment le niveau 1, etc. Nombre possible de sommets par k-ème niveau que nous désignons par Ne sait pas. Chaque sommet k le niveau apparaît exactement Dn – k pics n-ème niveau.

n 1 ≤ n 2 ≤…≤ nN = n.

Évidemment, le mot de code de longueur k interdit exactement Dn – k sommets d'extrémité possibles (sommets du dernier niveau). Ensuite, tous les mots de code du code préfixe interdisent les sommets d'extrémité. Puisque le nombre total de sommets d’extrémité est Dn, alors l'inégalité est vraie

d'où il résulte que

Ainsi, l'inégalité de Kraft est prouvée.

À la suite de la preuve du théorème 5.1, on conclut qu'il existe au moins des codes de préfixe qui sont des codes décodables de manière unique avec des longueurs de mots de code. n 1 , n 2 , …, nN, satisfaisant l'inégalité de Kraft. Le théorème suivant, appelé énoncé de McMillan, généralise cette dérivation à tous les codes uniquement décodables.

Théorème 5.2. L'inégalité de McMillan. Chaque code décodable de manière unique satisfait l'inégalité de Kraft.

Preuve.Élevons la somme à une puissance L:

. (5.1)

Laisser Un k– nombre de combinaisons contenant L mots de passe avec longueur totale k. Alors l’expression (6.1) peut être représentée par

Où L max – longueur maximale d'un message contenant L mots de code. Si le code est décodable de manière unique, alors toutes les séquences de L mots de code de longueur totale k sont différents. Puisqu'il n'y a que Ne sait pas séquences possibles, alors Un k ≤ Ne sait pas et puis

Parce que L est le nombre de mots de code indépendants utilisés pour construire toutes les séquences possibles d'une longueur n'excédant pas L maximum. C'est pourquoi L ≤ L maximum et . Et il en résulte que

Puisque le raisonnement ci-dessus est valable pour chaque code décodable de manière unique, et pas seulement pour les codes de préfixe, la déclaration de McMillan est prouvée.

Les théorèmes suivants relient l'entropie d'une source de message et la longueur moyenne d'un mot de code.

Théorème 5.3. Théorème de codage source I. Pour toute source discrète sans mémoire X avec alphabet fini et entropie H(X) existe D-code de préfixe aire dans lequel la longueur moyenne du mot de code satisfait l'inégalité

. (5.2)

Preuve. Tout d'abord, expliquons qu'une source discrète sans mémoire est décrite par un modèle qui ne prend pas en compte les connexions entre symboles de message. Nous prouvons maintenant le côté gauche de l’inégalité (6.2) :

Pour ce faire, nous utilisons la définition de l’entropie et l’inégalité de Kraft :

Pour prouver le membre droit de l’inégalité (6.2), nous réécrivons l’inégalité de Kraft sous la forme suivante :

Ensuite on choisit pour chaque terme le plus petit entier n je, à laquelle

Puisque l'inégalité de Kraft reste la même avec ce choix, nous pouvons construire le code préfixe correspondant. Parce que n je est le plus petit entier, alors pour n je– 1 est juste

Ainsi, le théorème de codage source I est prouvé. Il détermine que la longueur moyenne d'un mot de code ne peut être inférieure à l'entropie de la source du message. Notez que la preuve du théorème a utilisé la même notation que pour l’inégalité de Kraft.

Théorème 5.4. Théorème de codage source II. Pour la longueur du bloc L existe D-code de préfixe aire dans lequel la longueur moyenne d'un mot de code par caractère satisfait l'inégalité

Où .

Preuve. Ici, des blocs de personnages et H(X 1 , X 2 , …, X L) est l'entropie de la source du message par bloc de L personnages. Pour prouver le théorème, vous pouvez utiliser le théorème de codage source I :

De plus, puisque la longueur minimale réalisable d'un mot de code par symbole est la valeur , alors lorsque D= 2 redondances de codes peuvent être déterminées par la formule .

1 | | L'œuvre a été ajoutée au site Internet du site : 2016-03-30

;color:#000000" xml:lang="fr-FR" lang="fr-FR">5. Codage des informations

;color:#000000" xml:lang="fr-FR" lang="fr-FR">5.1. Concepts de base

Les théorèmes de Shannon sur le codage des messages ont été mentionnés ci-dessus. Il est intuitivement clair que le codage est l'opération de conversion d'informations sous la forme requise pour un traitement ultérieur (transmission sur un canal de communication, stockage dans la mémoire d'un système informatique, utilisation pour la prise de décision, etc.). Il est également clair que lors de la construction d'un système d'information, il est impossible de se passer du codage : toute présentation d'informations implique l'utilisation d'une sorte de codes. Par conséquent, nous analyserons ensuite en détail les fondements théoriques du codage de l’information.

Laissez A n’importe quel alphabet. Éléments alphabétiques UN sont appelées lettres (ou symboles), et les séquences finies constituées de lettres sont appelées mots dans UN . On pense que dans tout alphabet, il existe un mot vide qui ne contient pas de lettres.

Mot α 1 appelé le début (préfixe) d'un motα , si le mot existeα 2 tel que α = α 1 α 2 ; dans ce cas le mot α 1 appelé le début approprié d'un motα si α 2 n'est pas un vain mot. La longueur du mot est le nombre de lettres du mot (un mot vide a une longueur de 0). Enregistrerα 1 α 2 désigne une connexion (concaténation) de motsα1 et α2. Mot α 2 appelé la terminaison (suffixe) d'un motα , si le mot existeα 1 tel que α = α 1 α 2 ; dans ce cas le mot α 2 appelé la fin propre d'un motα si α 1 n'est pas un vain mot. Un mot vide est par définition considéré comme le début et la fin de n'importe quel mot.α .

Considérez l'alphabet B = (0, 1, …, D 1), où D ≥ 2, et un ensemble arbitraire C . Affichage arbitraire d'un ensemble C en plusieurs mots de l'alphabet B s'appelle D -ary ensemble d'encodage C (en D = 2 l'encodage sera binaire). Le mappage inverse est appelé décodage. Donnons des exemples d'encodages.

1. Codage de l'ensemble des nombres naturels dans lequel le nombre n = 0 correspond au mot e (0) = 0, et nombre n ≥ 1 mot binaire

e (n) = b 1 b 2 … b l (n)

la plus petite longueur qui satisfait à la condition

Il est évident que b 1 = 1, 2 l (n) 1 ≤ n< 2 l (n ) et donc

l(n) = + 1 = ]log(n + 1)[,

où [ x ] et ] x [ désigne le plus grand entier ne dépassant pas x , et le plus petit entier supérieur à X. Mot e(n ) est appelée la notation binaire d'un nombre n , et ce codage est une représentation des nombres dans le système de nombres binaires. Cet encodage est un à un car lorsque n 1 ≠ n 2 mots e (n 1 ) et e (n 2 ) sont différents. Le tableau 5.1 montre la représentation des 16 premiers nombres naturels dans le système de nombres binaires.

" xml:lang="fr-FR" lang="fr-FR">Tableau 5.1

" xml:lang="fr-FR" lang="fr-FR"> Codage" xml:lang="en-US" lang="en-US">e" xml:lang="fr-FR" lang="fr-FR">(" xml:lang="en-US" lang="en-US">n" xml:lang="fr-FR" lang="fr-FR">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)
" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR">4	" xml:lang="fr-FR" lang="fr-FR">100	" xml:lang="fr-FR" lang="fr-FR">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="fr-FR" lang="fr-FR">12	" xml:lang="fr-FR" lang="fr-FR">1100
" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">5	" xml:lang="fr-FR" lang="fr-FR">101	" xml:lang="fr-FR" lang="fr-FR">9	" xml:lang="fr-FR" lang="fr-FR">1001	" xml:lang="fr-FR" lang="fr-FR">13	" xml:lang="fr-FR" lang="fr-FR">1101
" xml:lang="fr-FR" lang="fr-FR">2	" xml:lang="fr-FR" lang="fr-FR">10	" xml:lang="fr-FR" lang="fr-FR">6	" xml:lang="fr-FR" lang="fr-FR">110	" xml:lang="fr-FR" lang="fr-FR">10	" xml:lang="fr-FR" lang="fr-FR">1010	" xml:lang="fr-FR" lang="fr-FR">14	" xml:lang="fr-FR" lang="fr-FR">1110
" xml:lang="fr-FR" lang="fr-FR">3	" xml:lang="fr-FR" lang="fr-FR">11	" xml:lang="fr-FR" lang="fr-FR">7	" xml:lang="fr-FR" lang="fr-FR">111	" xml:lang="fr-FR" lang="fr-FR">11	" xml:lang="fr-FR" lang="fr-FR">1011	" xml:lang="fr-FR" lang="fr-FR">15	" xml:lang="fr-FR" lang="fr-FR">1111

2. Encodage des 2 premiers k nombres naturels, pour lesquels chaque nombre n (0 ≤ n< 2 k ) correspond au mot

e k (n) = 0 k l (n) e (n),

où l'entrée est 0 k l (n) désigne un mot composé de k l (n) zéros, e (n ) représentation numérique n dans le système de nombres binaires discuté ci-dessus. Cet encodage concerne les 16 premiers nombres naturels ( k = 4) est donné dans le tableau 5.2.

" xml:lang="fr-FR" lang="fr-FR">Tableau 5." xml:lang="fr-FR" lang="fr-FR">2

" xml:lang="fr-FR" lang="fr-FR"> Codage" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="fr-FR" lang="fr-FR">(" xml:lang="en-US" lang="en-US">n" xml:lang="fr-FR" lang="fr-FR">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)
" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="en-US" lang="en-US">0000	" xml:lang="fr-FR" lang="fr-FR">4	" xml:lang="en-US" lang="en-US">0100	" xml:lang="fr-FR" lang="fr-FR">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="fr-FR" lang="fr-FR">12	" xml:lang="fr-FR" lang="fr-FR">1100
" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="en-US" lang="en-US">0001	" xml:lang="fr-FR" lang="fr-FR">5	" xml:lang="en-US" lang="en-US">0101	" xml:lang="fr-FR" lang="fr-FR">9	" xml:lang="fr-FR" lang="fr-FR">1001	" xml:lang="fr-FR" lang="fr-FR">13	" xml:lang="fr-FR" lang="fr-FR">1101
" xml:lang="fr-FR" lang="fr-FR">2	" xml:lang="en-US" lang="en-US">0010	" xml:lang="fr-FR" lang="fr-FR">6	" xml:lang="en-US" lang="en-US">0110	" xml:lang="fr-FR" lang="fr-FR">10	" xml:lang="fr-FR" lang="fr-FR">1010	" xml:lang="fr-FR" lang="fr-FR">14	" xml:lang="fr-FR" lang="fr-FR">1110
" xml:lang="fr-FR" lang="fr-FR">3	" xml:lang="en-US" lang="en-US">0011	" xml:lang="fr-FR" lang="fr-FR">7	" xml:lang="en-US" lang="en-US">0111	" xml:lang="fr-FR" lang="fr-FR">11	" xml:lang="fr-FR" lang="fr-FR">1011	" xml:lang="fr-FR" lang="fr-FR">15	" xml:lang="fr-FR" lang="fr-FR">1111

Soit A = ( a i , i = 1, 2, ...) un alphabet fini ou dénombrable dont les lettres sont numérotées avec des nombres naturels. Dans ce cas, l'encodage des lettres de l'alphabet UN peut être spécifié par séquence Mots ré-aires V = (v i, i = 1, 2, …), où v i il y a une image d'une lettre un je . De telles séquences de mots (de l'ensemble V ) sont appelés codes (de l'alphabet UN ). Si le code V de l'alphabet A est donné , puis l'encodage des mots, dans lequel chaque mot une je 1 une je 2 … une ik correspond au mot v je 1 v je 2 … vi ik , est appelé codage lettre par lettre.

Lors du passage du codage un à un des lettres de l'alphabet au codage lettre par lettre des mots de l'alphabet, la propriété du caractère un à un peut ne pas être préservée. Par exemple, le codage e(n ) ne conserve pas cette propriété, mais le codage e k (n ) le sauvegarde. La propriété un-à-un est préservée par des codes séparables. Code V = ( v je , je = 1, 2, …) est dit séparable si de chaque égalité de la forme

v je 1 v je 2 … vi ik = v j 1 v j 2 … v jl

il s'ensuit que l = k et v i 1 = v j 1, v i 2 = v j 2, …, vi ik = v jl . Les codes séparables sont également appelés codes à décodage unique.

Les codes préfixes appartiennent à la classe des codes séparables. Code V = ( v je , je = 1, 2, …) est appelé préfixe si aucun mot vk n'est le début (préfixe) d'aucun mot v l , l ≠ k . Si chaque mot d'un code préfixe est remplacé par son plus petit début, qui n'est pas le début d'autres mots de code, alors le code résultant sera également un préfixe. Cette opération est appelée troncature du code de préfixe.

Pour le code arbitraire V composé de différents mots, vous pouvez créer une arborescence de codes. Il s'agit d'un graphe orienté qui ne contient pas de cycles, dans lequel le sommetβ1 connecté au sommetβ2 bord dirigé à l’opposé deβ 1 à β 2 , si et seulement siβ 2 = β 1 b, où b  B = (0, 1, …, D 1), D ≥ 2. Pour les codes préfixes (et uniquement pour eux), l'ensemble des mots de code coïncide avec l'ensemble des sommets terminaux (sommets dont aucune arête ne provient) de l'arbre de codes.

5.2. Théorèmes de codage de base

Les propriétés des codes utiles pour leur application pratique sont déterminées par les théorèmes de codage de base.

Théorème 5.1. L'inégalité de Kraft.Pour l'existence d'un code (séparable) uniquement décodable contenant N mots de code dans l'ensemble (0, 1, D 1) avec des longueurs n 1, n 2, …, n N , il est nécessaire et suffisant que l’inégalité perdure

Preuve. Imaginons que nous ayons une arborescence de codes pour un code de préfixe. La racine de l'arbre de codes forme le niveau 0, les sommets associés à la racine forment le niveau 1, etc. Nombre possible de sommets par k -ème niveau que nous désignons par Ne sais pas. Chaque sommet k le niveau apparaît exactement D n k sommets du nième niveau.

n 1 ≤ n 2 ≤…≤ n N = n .

Évidemment, le mot de code de longueur k interdit exactement D n k sommets d'extrémité possibles (sommets du dernier niveau). Ensuite, tous les mots de code du code préfixe interdisent les sommets d'extrémité. Puisque le nombre total de sommets d’extrémité est Dn , alors l'inégalité est vraie

d'où il résulte que

Ainsi, l'inégalité de Kraft est prouvée.

À la suite de la preuve du théorème 5.1, on conclut qu'il existe au moins des codes de préfixe qui sont des codes décodables de manière unique avec des longueurs de mots de code. n 1, n 2, …, n N , satisfaisant l'inégalité de Kraft. Le théorème suivant, appelé énoncé de McMillan, généralise cette dérivation à tous les codes uniquement décodables.

Théorème 5.2. L'inégalité de McMillan.Chaque code décodable de manière unique satisfait l'inégalité de Kraft.

Preuve. Élevons la somme à une puissance L :

. (5.1)

Soit A k nombre de combinaisons contenant L mots de passe avec longueur totale k . Alors l’expression (6.1) peut être représentée par

où Lmax longueur maximale d'un message contenant L mots de code. Si le code est décodable de manière unique, alors toutes les séquences de L mots de code de longueur totale k sont différents. Puisqu'il n'y a que Ne sait pas séquences possibles, alors A k ≤ D k et alors

Depuis L c'est le nombre de mots de code indépendants qui sont utilisés pour construire toutes les séquences possibles d'une longueur n'excédant pas Lmax. Donc L ≤ L max Et. Et il en résulte que

Puisque le raisonnement ci-dessus est valable pour chaque code décodable de manière unique, et pas seulement pour les codes de préfixe, la déclaration de McMillan est prouvée.

Les théorèmes suivants relient l'entropie d'une source de message et la longueur moyenne d'un mot de code.

Théorème 5.3. Théorème du codage source JE. Pour toute source discrète sans mémoire X avec alphabet fini et entropie H(X) existe D -code de préfixe aire dans lequel la longueur moyenne du mot de code satisfait l'inégalité

. (5.2)

Pour ce faire, nous utilisons la définition de l’entropie et l’inégalité de Kraft :

Pour prouver le membre droit de l’inégalité (6.2), nous réécrivons l’inégalité de Kraft sous la forme suivante :

Ensuite on choisit pour chaque terme le plus petit entier n i , à quel moment

Puisque l'inégalité de Kraft reste la même avec ce choix, nous pouvons construire le code préfixe correspondant. Parce que n je est le plus petit entier, alors pour n i 1 vrai

Alors

Ainsi, le théorème du codage source je éprouvé. Il détermine que la longueur moyenne d'un mot de code ne peut être inférieure à l'entropie de la source du message. Notez que la preuve du théorème a utilisé la même notation que pour l’inégalité de Kraft.

Théorème 5.4. Théorème du codage source II. Pour un bloc de longueur L il y a D

-code de préfixe aire dans lequel la longueur moyenne d'un mot de code par caractère satisfait l'inégalité

Preuve. Où. Ici, des blocs de personnages et H (X 1, X 2, …, XL L ) est l'entropie de la source du message par bloc de personnages. Pour prouver le théorème, vous pouvez utiliser le théorème du codage source

JE: Théorème du codage source II nous permet d'affirmer qu'il existe de telles méthodes de codage pour un message suffisamment long pour que la longueur moyenne du mot de code puisse être arbitrairement proche de la valeur. En effet, quand L  ∞, H L (X )  H , où H

, (5.3)

entropie de la source du message par caractère, l'inégalité suivante est vraie :ε Où. Cela peut également être interprété comme suit : pour tout nombre arbitrairement petit

, il existe une méthode de codage de blocs contenant des symboles dans laquelle l'inégalité (5.3) est valable pour la longueur moyenne du mot de code par symbole. D De plus, puisque la longueur minimale réalisable d'un mot de code par symbole est la valeur, alors lorsque

= 2 la redondance des codes peut être déterminée par la formule.

;color:#000000" xml:lang="fr-FR" lang="fr-FR">5.3. Encodage optimal n 1, n 2, …, n N Le problème de la construction d'un code optimal est de trouver des entiers positifs

Lors de la construction de codes dans le cas d'un alphabet UNE = ( une je , je = 1, 2, …, N ) avec une distribution de probabilité connue P = ( p je , je = 1, 2, …, N ) sans perte de généralité on peut supposer que les lettres de l'alphabet UN sont numérotés par ordre décroissant de leurs probabilités, c'est-à-dire p 1 ≥ p 2 ≥ … ≥ pN . De plus, nous ne considérerons que les codes binaires.

Il existe deux méthodes connues (Fano et Shannon) pour construire des codes proches de l'optimal. La méthode de Fano est la suivante. La liste des lettres, classées par ordre décroissant de probabilités, est divisée en deux parties consécutives afin que les sommes des probabilités des lettres qui y sont incluses diffèrent le moins possible les unes des autres. Les lettres de la première partie reçoivent le symbole 0 et les lettres de la deuxième partie reçoivent le symbole 1. Ensuite, la même chose est faite avec chacune des parties résultantes si elle contient au moins deux lettres. Le processus se poursuit jusqu'à ce que la liste entière soit divisée en parties contenant chacune une lettre. Chaque lettre se voit attribuer une séquence de symboles attribués à cette lettre à la suite de ce processus. Il est facile de voir que le code résultant est un préfixe.

La méthode de Shannon n'est applicable que lorsque toutes les probabilités sont positives. Cela consiste dans le fait que la lettre un je , ce qui a une probabilité p je > 0, la séquence de n i = ] log (1/ p i )[ les premiers chiffres après le point fractionnaire de la décomposition d'un nombre en fraction infinie (pour a 1 nous supposons que q 1 = 0). Depuis quand l > k (en raison du fait que p l ≤ p k ) n l ≥ n k et puis le code obtenu de cette manière est un préfixe. Sur la base du code de préfixe reçu, un code de préfixe tronqué est construit, résultat d'un codage utilisant la méthode de Shannon.

Supposons, par exemple, qu'il y ait un ensemble de lettres A = ( une 1 , une 2 , une 3 , une 4 , une 5 , une 6 , une 7 ) avec distribution de probabilité P. = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Encodons les lettres en utilisant la méthode Fano.

1. Divisons la liste en deux parties, afin que les sommes des probabilités des lettres qui y sont incluses diffèrent le moins possible les unes des autres :

UNE 1 = ( une 1 , une 2 , une 3 ), P 1 = (0,2, 0,2, 0,19) ;

A 2 = (a 4, a 5, a 6, a 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Attribuons le symbole 0 aux lettres de la première partie, et le symbole 1 aux lettres de la deuxième partie :

Un 1 = ( un 1 /0, un 2 /0, un 3 /0) ;

Un 2 = (un 4/1, un 5/1, un 6/1, un 7/1).

3. Répétons les étapes indiquées séquentiellement pour chacune des pièces séparément. DANS en conséquence nous obtenons :

Un 1 1 = ( un 1 /00);

Un 121 = (un 2 /010);

Un 122 = (un 3 /011) ;

Un 211 = (un 4/100) ;

Un 212 = (un 5 /101) ;

Un 221 = (un 6 /110) ;

Un 222 = (un 7/111).

Les mots de code obtenus grâce au codage sont donnés pour chaque lettre à droite de la barre oblique. Dans ce cas, l'ordre des indices des listes à une seule lettre résultantes montre la séquence de division de la liste originale de groupes en parties.

Le processus de codage utilisant la méthode Fano est présenté de manière pratique sous la forme d'un tableau. Pour l'exemple considéré, il est présenté dans le tableau 5.3.

" xml:lang="fr-FR" lang="fr-FR">Tableau 5.3

" xml:lang="fr-FR" lang="fr-FR"> Codage selon la méthode Fano

" xml:lang="en-US" lang="en-US">a;alignement vertical:sub" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">0,20	" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR"> 0	" xml:lang="fr-FR" lang="fr-FR"> 00
" xml:lang="en-US" lang="en-US">a;alignement vertical:sub" xml:lang="fr-FR" lang="fr-FR">2	" xml:lang="fr-FR" lang="fr-FR">0,20		" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR">010
" xml:lang="en-US" lang="en-US">a;alignement vertical:sub" xml:lang="fr-FR" lang="fr-FR">3	" xml:lang="fr-FR" lang="fr-FR">0.19			" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">011
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="fr-FR" lang="fr-FR">4	" xml:lang="fr-FR" lang="fr-FR">0.12	" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR">100
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="fr-FR" lang="fr-FR">5	" xml:lang="fr-FR" lang="fr-FR">0.11			" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">101
" xml:lang="en-US" lang="en-US">a;alignement vertical:sub" xml:lang="fr-FR" lang="fr-FR">6	" xml:lang="fr-FR" lang="fr-FR">0,09		" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">0	" xml:lang="fr-FR" lang="fr-FR">110
" xml:lang="en-US" lang="en-US">a;alignement vertical:sub" xml:lang="fr-FR" lang="fr-FR">7	" xml:lang="fr-FR" lang="fr-FR">0,09			" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="fr-FR" lang="fr-FR">111

Déterminons la longueur moyenne du mot de passe :

Faisons maintenant le codage en utilisant la méthode de Shannon. Le processus de codage est présenté dans le tableau 5.4.

" xml:lang="fr-FR" lang="fr-FR">Tableau 5.4

" xml:lang="fr-FR" lang="fr-FR"> Codage selon la méthode Shannon

" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">n;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">q;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="fr-FR" lang="fr-FR">Code" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="fr-FR" lang="fr-FR">Code tronqué" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i
" xml:lang="en-US" lang="en-US">a;alignement vertical:sub" xml:lang="fr-FR" lang="fr-FR">1	" xml:lang="en-US" lang="en-US">]2.321…[ = 3	" xml:lang="fr-FR" lang="fr-FR">0	000	000
a2	]2.321…[ = 3	0.2	001	001
a3	]2,395…[ = 3	0.4	011	01
a4	]3.058…[ = 4	0,59	1001	100
a5	]3.183…[ = 4	0.71	1011	101
a6	]3.472…[ = 4	0.82	1101	110
a7	]3.472…[ = 4	0.91	1110	111

Comme dans le cas précédent, on retrouve la longueur moyenne du mot de code :

Comme vous pouvez le constater, les résultats du codage utilisant les méthodes Fano et Shannon en termes de minimisation de la longueur moyenne du code ont pratiquement coïncidé. Par conséquent, ces méthodes sont souvent considérées comme une seule (dans la formulation de Fano) et appelées méthode Shannon-Fano.

En 1952, David Huffman a proposé une méthode optimale de codage des préfixes pour les sources discrètes, qui, contrairement aux méthodes de Shannon et Fano, est toujours utilisée en pratique. D. Huffman a prouvé que la longueur moyenne d'un mot de code obtenu selon sa méthode sera minime. Le codage de Huffman se fait en trois étapes.

1. Ordre : les lettres sont classées par ordre décroissant de leurs probabilités.

2. Réduction : deux lettres avec les probabilités les plus faibles sont combinées en une seule avec une probabilité totale ; la liste des lettres est réorganisée selon l'étape 1 ; le processus continue jusqu'à ce que toutes les lettres soient combinées en une seule. Dans ce cas, il est possible d'obtenir une égalisation des longueurs des mots de code en utilisant la stratégie suivante : si plusieurs lettres ont les mêmes probabilités, alors les deux d'entre elles qui avaient auparavant le moins de combinaisons sont combinées (bien que cela n'affecte pas la longueur moyenne du code).

3. Codage : à partir de la dernière combinaison, le symbole 0 est attribué séquentiellement à un composant de la lettre composée, et le symbole 1 au second ; le processus se poursuit jusqu'à ce que toutes les lettres originales aient été codées.

Effectuons un codage selon la méthode de Huffman pour l'ensemble considéré dans les exemples d'utilisation des méthodes de Fano et Shannon.

1. Liste initiale des lettresUN = { un1 , un2 , un3 , un4 , un5 , un6 , un7 ) est déjà commandé, puisqueP. = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Combinons les lettresun6 Etun7 en une lettreun1 avec probabilité0.18 Etréorganiserliste:

P.1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, UN1 = { un1 , un2 , un3 , un1 , un4 , un5 }.

3. Répétez l'étape 2 jusqu'à ce qu'il reste une lettre dans la liste :

P.2 = {0.23, 0.2, 0.2, 0.19, 0.18}, UN2 = { un2 , un1 , un2 , un3 , un1 };

P.3 = {0.37, 0.23, 0.2, 0.2}, UN3 = { un3 , un2 , un1 , un2 };

P.4 = {0.4, 0.37, 0.23}, UN4 = { un4 , un3 , un2 };

P.5 = {0.6, 0.4}, UN5 = { un5 , un4 };

P.6 = {1}, UN6 = { un6 }.

4. Approprions-nousbinairecodessymboles:

un6 : un5 = 0, un4 = 1;

un5 : un3 = 00, un2 = 01;

un4 : un1 = 10, un2 = 11;

un3 : un3 = 000, un1 = 001;

un2 : un4 = 010, un5 = 011;

un1 : un6 = 0010, un7 = 0011.

Ainsi, les codes binaires suivants sont attribués aux lettres initiales :un1 = 10, un2 = 11, un3 = 000, un4 = 010, un5 = 011, un6 = 0010, un7 = 0011, ce qui donne une longueur moyenne de code plus petite que dans le cas du codage Fano et Shannon.

Déterminons la redondance des codes reçus. Pour ce faire, trouvons l’entropie de la source du message :

Alors les codes ont la redondance suivante :

Code Fano : ;

Code Shannon : ;

Code Huffman : .

Ainsi, la redondance du code de Huffman est minime.

Pour réduire la redondance, c'est-à-dire Pour réduire la longueur moyenne d'un mot de code d'un symbole, vous pouvez utiliser le codage par blocs, dont la justification est donnée dans le théorème du codage sourceThéorème du codage source. Dans ce cas, il faut obtenir tous les groupes possibles de lettres d'une longueur donnée, trouver les probabilités des groupes comme probabilités d'apparition conjointe des lettres du groupe en même temps, et effectuer un codage en considérant les groupes comme symboles d’un nouvel alphabet.

PAGE 43