Bit, entropie informationnelle de Shannon et code de Hamming. Comment mesurer une information et la transférer sans perte

Espace événementiel aléatoire

En 1946, le statisticien américain John Tukey propose le nom de BIT.

(BIT, BInary digit - « nombre binaire » -Le « high-tech ») est l’un des concepts majeurs du XXe siècle. Tukey a choisi un bit pour désigner un chiffre binaire capable de prendre la valeur 0 ou 1. Claude Shannon, dans son article fondateur « Théorie mathématique de la communication », a proposé de mesurer la quantité d'informations en bits. Mais ce n’est pas le seul concept introduit et exploré par Shannon dans son article.

Imaginez un espace d'événements aléatoiresqui consiste à lancer une fausse pièce, sur les deux côtés de laquelle est un aigle. Quand tombe un aigle? Il est clair que toujours. Nous le savons d'avance, car notre espace est ainsi aménagé. La chute d'un aigle est un événement fiable, c'est-à-dire que sa probabilité est égale à 1. Allons-nous donner beaucoup d'informations si nous parlons d'un aigle tombé? Non La quantité d'informations contenue dans un tel message sera considérée comme égale à 0.

Maintenant, tirons la juste pièce :d'un côté, c'est face, et de l'autre, face, comme il se doit. Atterrir face ou face sera deux événements différents qui constitueront notre espace d’événements aléatoires. Si nous rapportons le résultat d’un tirage au sort, ce sera effectivement une nouvelle information. Si c'est face, nous rapporterons 0, et si c'est face, c'est 1. Pour rapporter cette information, nous n'avons besoin que de 1 bit.

Qu'est ce qui a changé?L'incertitude est apparue dans notre espace événementiel. Nous avons quelque chose à dire à quelqu’un qui ne lance pas lui-même une pièce et ne voit pas le résultat du tirage au sort. Mais pour bien comprendre notre message, il doit savoir exactement ce que nous faisons et ce que signifient les 0 et les 1.Nos espaces événementiels doivent correspondre, et le processus de décodage consiste uniquement à restaurer le résultat du lancer.Si l'espace événementiel de l'émetteur et du récepteur ne coïncide pas ou s'il n'y a aucune possibilité de décodage sans ambiguïté du message, l'information ne restera que du bruit dans le canal de communication.

Si vous en lancez deux indépendamment et simultanémentpièces de monnaie, alors il y aura quatre résultats différents également probables : pile-face, pile-face, pile-face et pile-face. Pour transmettre des informations, nous aurons besoin de 2 bits, et nos messages seront les suivants : 00, 01, 10 et 11. Il y a deux fois plus d'informations. Cela s’est produit parce que l’incertitude a augmenté. Si nous essayons de deviner le résultat d’un tel tirage au sort, nous avons deux fois plus de chances de nous tromper.

Plus l'incertitude de l'espace des événements est grande, plus le message sur son état contient d'informations.

Compliquons un peu notre espace événementiel.Jusqu’à présent, tous les événements survenus étaient également probables. Mais dans les espaces réels, tous les événements n’ont pas la même probabilité. Disons que la probabilité que le corbeau que nous voyons soit noir est proche de 1. La probabilité que le premier passant que nous rencontrons dans la rue soit un homme est d'environ 0,5. Mais rencontrer un crocodile dans les rues de Moscou est presque impossible. Intuitivement, nous comprenons qu'un rapport sur une rencontre avec un crocodile a une valeur informative bien plus grande que sur un corbeau noir.Plus la probabilité d'un événement est faible, plus le message contenant un tel événement contient d'informations.

Que l’espace événementiel ne soit pas si exotique. Nous restons à la fenêtre et regardons les voitures qui passent. Des voitures de quatre couleurs passent, que nous devons signaler. Pour ce faire, nous encodons les couleurs: noir - 00, blanc - 01, rouge - 10, bleu - 11. Pour signaler exactement quelle voiture a conduit, il nous suffit de transférer 2 bits d’information.

Mais pendant assez longtemps à regarder les voitures,Nous notons que la couleur des voitures est inégalement répartie: noir - 50% (chaque seconde), blanc - 25% (tous les quatre), rouge et bleu - 12,5% (chaque huitième). Ensuite, vous pouvez optimiser les informations transmises.

La plupart des voitures sont noires, doncnotons le noir - 0 - le code le plus court, et laissons le code de tout le reste commencer par 1. De la moitié restante, le blanc - 10 et les couleurs restantes commencent par 11. Enfin, notons le rouge - 110 et le bleu - 111.

Maintenant, en passant des informations sur la couleur de la voiture, nous pouvons l’encoder de plus près.

Shannon Entropie

Soit notre espace événementiel composé de ndifférents événements. Lorsque l'on lance une pièce avec deux têtes, il y a exactement un événement de ce type, lorsque l'on lance une pièce équitable, il y en a exactement 2, lorsque l'on lance deux pièces ou que l'on regarde les voitures, il y en a exactement 4. Chaque événement a une probabilité de se produire. Lorsque l'on lance une pièce avec deux faces, il y a un événement (chute des faces) et sa probabilité est p1 = 1. Lorsque l'on lance une pièce juste, il y a deux événements, ils sont également probables et la probabilité de chacun est de 0,5 : p1 = 0,5, p2 = 0,5. Lorsque l'on lance deux pièces équitables, il y a quatre événements, ils sont tous également probables et la probabilité de chacun est de 0,25 : p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Lors de l'observation des voitures, il y a quatre événements, et ils ont des probabilités différentes : noir - 0,5, blanc - 0,25, rouge - 0,125, bleu - 0,125 : p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.

Ce n'est pas une coïncidence.Shannon a choisi l'entropie (une mesure d'incertitude dans l'espace événementiel) pour que trois conditions soient remplies:

  • 1L'entropie d'un événement fiable, dont la probabilité est 1, est égale à 0.
  • L'entropie de deux événements indépendants est égale à la somme des entropies de ces événements.
  • L'entropie est maximale si tous les événements sont également probables.

Toutes ces exigences sont pleinement cohérentes avec notredes idées sur l’incertitude de l’espace événementiel. S’il n’y a qu’un seul événement (le premier exemple), il n’y a pas d’incertitude. Si les événements sont indépendants – l’incertitude de la somme est égale à la somme des incertitudes – ils s’additionnent simplement (exemple du lancer de deux pièces). Et enfin, si tous les événements sont également probables, alors le degré d'incertitude du système est maximum. Comme dans le cas du lancer de deux pièces, les quatre événements sont également probables et l'entropie est de 2, elle est plus grande que dans le cas des voitures, où il y a aussi quatre événements, mais ils ont des probabilités différentes - dans ce cas l'entropie est 1,75.

La quantité H joue un rôle central dans la théorie de l'information en tant que mesure de l'information, du choix et de l'incertitude.

Claude Shannon

Claude Elwood Shannon- Ingénieur américain, cryptanalyste etmathématicien. Considéré comme le « père de l’ère de l’information ». Fondateur de la théorie de l’information, qui a trouvé des applications dans les systèmes de communication modernes de haute technologie. Fourni des concepts fondamentaux, des idées et leurs formulations mathématiques qui constituent actuellement la base des technologies de communication modernes.

En 1948, a proposé d'utiliser le mot "bit"pour indiquer la plus petite unité d'information. Il a également démontré que l'entropie entrée par lui équivaut à l'incertitude des informations contenues dans le message transmis. Les articles de Shannon "Théorie mathématique de la communication" et "Théorie de la communication dans les systèmes secrets" sont considérés comme fondamentaux pour la théorie de l'information et la cryptographie.

Pendant la Seconde Guerre mondiale, Shannon a travaillé aux laboratoires Bell pour développer des systèmes cryptographiques, ce qui l'a ensuite aidé à découvrir des méthodes de codage de correction d'erreurs.

Shannon a apporté une contribution essentielle à la théorie des schémas probabilistes, de la théorie des jeux, de la théorie des automates et de la théorie des systèmes de contrôle - domaines de la science faisant partie du concept de cybernétique.

Codage

Et les pièces jetées, et les voitures qui passent ne sont passont similaires aux nombres 0 et 1. Pour signaler des événements se produisant dans des espaces, vous devez penser à un moyen de décrire ces événements. Cette description s'appelle le codage.

Les messages peuvent être codés d’une infinité de manières différentes. Mais Shannon a montré que le code le plus court ne peut pas être plus petit en bits que l'entropie.

C'est pourquoi l'entropie d'un message est une mesureinformations dans le message. Puisque dans tous les cas considérés le nombre de bits lors du codage est égal à l'entropie, cela signifie que le codage était optimal. Bref, il n'est plus possible d'encoder des messages sur les événements de nos espaces.

Avec un codage optimal, vous ne pouvez pas perdre oudéformer un seul bit transmis dans le message. Si ne serait-ce qu’un bit est perdu, les informations seront déformées. Mais tous les canaux de communication réels ne garantissent pas à 100 % que tous les éléments du message parviendront au destinataire sans distorsion.

Pour résoudre ce problème, vous devez fairele code n'est pas optimal, mais redondant. Par exemple, transmettez avec le message sa somme de contrôle - une valeur spécialement calculée obtenue lors de la conversion du code du message, et qui peut être vérifiée en recalculant à la réception du message. Si la somme de contrôle transmise correspond à celle calculée, la probabilité que la transmission se soit déroulée sans erreur sera assez élevée. Et si la somme de contrôle ne correspond pas, alors une retransmission doit être demandée. C’est à peu près ainsi que fonctionnent aujourd’hui la plupart des canaux de communication, par exemple lors de la transmission de paquets d’informations sur Internet.

Messages en langage naturel

Considérez l'espace événementiel qui consisteà partir de messages en langage naturel. C'est un cas particulier, mais l'un des plus importants. Les événements ici seront les caractères transmis (lettres d'un alphabet fixe). Ces caractères se retrouvent dans la langue avec des probabilités différentes.

Le symbole le plus fréquent (c.-à-d. Un symbole quise trouve le plus souvent dans tous les textes en russe) est un espace: sur mille caractères, un espace moyen est trouvé 175 fois. Le deuxième en fréquence est le symbole "o" - 90, suivi d'autres voyelles: "e" (ou "e" - nous ne les distinguerons pas) - 72, "a" - 62, et i - 62, et seulement plus loin la première consonne "t" - 53. Et le plus rare "f" - ce symbole ne se trouve que deux fois par mille caractères.

Nous allons utiliser l'alphabet de 31 lettres du russelangue (il ne diffère pas de "e" et "e", ainsi que "" et "ь"). Si toutes les lettres étaient rencontrées dans le langage avec la même probabilité, alors l'entropie par symbole serait H = 5 bits, mais si nous prenons en compte les fréquences réelles des symboles, l'entropie sera inférieure à: H = 4,35 bits. (C'est presque deux fois moins qu'avec le codage traditionnel, lorsqu'un caractère est transmis sous forme d'octet - 8 bits).

Mais l'entropie du personnage dans la langue est encore plus basse. La probabilité d'apparition du caractère suivant n'est pas complètement prédéterminée par la fréquence moyenne du caractère dans tous les textes. Le caractère qui va suivre dépend des caractères déjà transférés. Par exemple, en russe moderne après le symbole "" ne peut pas suivre le son de la consonne. Après deux voyelles consécutives "e", la troisième voyelle "e" suit extrêmement rarement, sauf dans le mot "à long cou". C'est-à-dire que le caractère suivant est dans une certaine mesure prédéterminé. Si nous prenons en compte un tel caractère prédéterminé du symbole suivant, l'incertitude (c'est-à-dire l'information) du symbole suivant sera même inférieure à 4,35. Selon certaines estimations, le symbole suivant en russe est prédéterminé par la structure de la langue de plus de 50%. En d'autres termes, avec un codage optimal, toutes les informations peuvent être transmises en supprimant la moitié des lettres du message.

Une autre chose est que toutes les lettres ne peuvent pas être supprimées en toute sécurité. Le "o" haute fréquence (et généralement les voyelles), par exemple, est facile à rayer, mais les rares "f" ou "e" sont assez problématiques.

Le langage naturel dans lequel nous communiquons entre nous est très redondant, et donc fiable ; si nous avons mal entendu quelque chose, ce n’est pas grave, l’information sera quand même transmise.

Mais tant que Shannon n’a pas introduit la mesure de l’information, nous ne pouvions pas comprendre que la langue est redondante et dans quelle mesure nous pouvons compresser les messages (et pourquoi les fichiers texte sont si bien compressés par l’archiveur).

Redondance du langage naturel

Dans l'article "Comment nous sommes vorpsimanie tektkt"(Le nom sonne exactement comme ça!) Un fragment du roman Noble Nest d'Ivan Tourgueniev a été saisi et soumis à une transformation: 34% des lettres ont été supprimées du fragment, mais pas au hasard. Les premières et dernières lettres des mots sont restées, seules les voyelles ont été supprimées, pas toutes. L’objectif était non seulement d’obtenir la possibilité de récupérer toutes les informations sur le texte converti, mais également de s’assurer que la personne qui lit ce texte n’éprouve aucune difficulté particulière en raison de lettres manquantes.

Pourquoi est-il relativement facile de lire ceci corromputexte? Il contient en fait les informations nécessaires pour reconstruire des mots entiers. Un locuteur natif du russe dispose d'un certain ensemble d'événements (mots et phrases entières) qu'il utilise pour la reconnaissance. De plus, le locuteur dispose également de structures linguistiques standards qui l'aident à récupérer des informations. Par exemple,"Elle est blae blee"- avec une forte probabilité peut être lu comme"Elle était plus sensible.". Mais pris séparément"Elle est plus bla", sera plutôt restauré comme"Elle était plus blanche". Puisque dans la communication quotidienne nous traitonsavec des canaux dans lesquels il y a du bruit et des interférences, nous sommes assez doués pour restituer des informations, mais uniquement celles que nous connaissons déjà à l'avance. Par exemple, l'expression"Ses traits ne sont pas du tout agréables, htya nmngo rspkhli et splash"se lit bien sauf le dernier mot"Splash" - "rallié". Ce mot ne figure pas dans le lexique moderne. Lorsque vous lisez un mot rapidement"Splash"se lit plutôt comme « collé ensemble » ; lorsqu’il est lent, il déroute tout simplement.

Numérisation du signal

Le son, ou oscillations acoustiques, est une sinusoïde. Cela peut être vu, par exemple, sur l'écran de l'éditeur de son. Pour transmettre le son avec précision, vous aurez besoin d’un nombre infini de valeurs - l’onde sinusoïdale complète. Ceci est possible avec une connexion analogique. Il chante - vous écoutez, le contact n'est pas interrompu tant que la chanson dure.

Dans la communication numérique sur un canal, nous ne pouvons transmettre qu'un nombre fini de valeurs. Cela signifie-t-il que le son ne peut pas être reproduit avec précision ? Il s'avère que non.

Différents sons sont une onde sinusoïdale modulée différemment.Nous ne transmettons que des valeurs discrètes (fréquences et amplitudes), et l’onde sinusoïdale n’a pas besoin d’être transmise, elle est générée par le dispositif de réception.Il génère une sinusoïde et se superpose à celle-cimodulation créée à partir de valeurs transmises sur un canal de communication. Il existe des principes exacts selon lesquels les valeurs discrètes doivent être transmises pour que le son à l'entrée du canal de communication coïncide avec le son à la sortie, où ces valeurs se superposent à une sinusoïde standard (c'est ce qu'est le théorème de Kotelnikov à propos de).

Le théorème de Kotelnikov (dans la littérature de langue anglaise - le théorème de Nyquist-Shannon, le théorème de lecture)- un énoncé fondamental dans le domaine du numériquetraitement du signal, connectant des signaux continus et discrets et déclarant que « toute fonction F(t), composée de fréquences de 0 à f1, peut être transmise en continu avec n'importe quelle précision en utilisant des nombres se succédant pendant 1/(2*f1) secondes

Codage anti-interférence. Codes de Hamming

Si sur un canal peu fiable pour transmettreLe texte codé d'Ivan Tourgueniev, bien que comportant quelques erreurs, donnera un texte assez significatif. Mais si nous devons tout transférer un peu, la tâche sera non résolue: nous ne savons pas quels bits sont erronés, car l'erreur est aléatoire. Même la somme de contrôle ne sauve pas toujours.

C’est pourquoi aujourd’hui, lors de la transmission de données surLes réseaux ne sont pas tant axés sur le codage optimal, dans lequel le maximum d’informations peut être inséré dans le canal, mais plutôt sur un codage (évidemment redondant) dans lequel les erreurs peuvent être récupérées, comme lorsque nous lisons les mots du fragment d’Ivan Tourgueniev.

Il existe des codes spéciaux de correction d'erreur qui vous permettent de récupérer des informations après une panne. L'un d'eux est le code de Hamming.Disons que notre langue entière se compose de trois mots :111000, 001110, 100011. La source du message et le destinataire connaissent ces mots. Et nous savons que des erreurs se produisent dans un canal de communication, mais lors de la transmission d'un mot, pas plus d'un bit d'information n'est déformé.

Supposons que nous passions d'abord le mot 111000. En conséquence, pas plus d'une erreur (nous avons identifié l'erreur) peut se transformer en l'un des mots suivants:

1) 111 000,011 000, 101000, 110000, 111100 111010, 111001.

Lors de la transmission du mot 001110, n'importe lequel des mots peut être obtenu:

2) 001110,101110, 011110, 000110, 001010, 001100, 001111.

Enfin, pour 100011, nous pouvons obtenir à la réception:

3) 100011,000011, 110011, 101011, 100111, 100001, 100010.

Notez que les trois listes ne sont pas paires.intersecter. En d'autres termes, si un mot de la liste 1 apparaît à l'autre bout du canal de communication, le destinataire sait que le mot 111000 lui a été transmis et, si un mot de la liste 2 apparaît, le mot 001110 et le mot 100011 de la liste 3. Ils disent que notre code corrige une erreur.

La correction s'est produite en raison de deux facteurs.Tout d’abord, le destinataire connaît l’ensemble du «dictionnaire»c’est-à-dire que l’espace événementiel du destinataire du message coïncide avec celui de celui qui a transmis le message. Lorsque le code a été transmis avec une seule erreur, un mot est sorti, mais il ne figurait pas dans le dictionnaire.

Deuxièmement, les mots du dictionnaire ont été choisis de manière particulière.Même si une erreur survenait, le destinataire ne pourrait pasconfondre un mot avec un autre. Par exemple, si le dictionnaire se compose des mots « fille », « point », « bosse » et que lors de la transmission le résultat était « vochka », alors le destinataire, sachant qu'un tel mot n'existe pas, ne pourrait pas corrigez l'erreur - n'importe lequel des trois mots peut s'avérer correct. Si le dictionnaire inclut « point », « daw », « branche » et que nous savons qu'une seule erreur est autorisée, alors « vochka » est définitivement un « point » et non un « daw ». Dans les codes correcteurs d’erreurs, les mots sont choisis précisément pour qu’ils soient « reconnaissables » même après une erreur. La seule différence est que le code « alphabet » n'a que deux lettres - zéro et un.

La redondance de ce type de codage est très grande et le nombre de mots que nous pouvons ainsi transmettre est relativement petit.Nous devons exclure n'importe quel mot du dictionnaire,qui, en cas d'erreur, peut coïncider avec la liste complète correspondant aux mots transmis (par exemple, les mots « fille » et « point » ne peuvent pas être dans le dictionnaire). Mais la transmission précise des messages est si importante que de gros efforts sont consacrés à la recherche de codes résistants aux erreurs.

Sensation

Notions d'entropie (ou d'incertitude etimprévisibilité) du message et la redondance (ou prédétermination et prévisibilité) correspondent très naturellement à nos idées intuitives sur la mesure de l'information. Plus le message est imprévisible (plus son entropie est grande car il y a moins de probabilité), plus il transporte d'informations. Une sensation (par exemple, une rencontre avec un crocodile sur Tverskaya) est un événement rare, sa prévisibilité est très faible et, par conséquent, la valeur de l'information est élevée. Souvent, les informations sont appelées informations - des informations sur des événements qui viennent de se produire et dont nous ne savons toujours rien. Mais s'ils nous parlent des mêmes mots à la deuxième et à la troisième fois, la redondance du message sera grande, son imprévisibilité tombera à zéro et nous n'écouterons tout simplement pas. Nous écarterons les propos du locuteur avec les mots "Je sais, je sais." Par conséquent, les médias s'efforcent d'être les premiers. Cette correspondance avec le sens intuitif de la nouveauté, qui donne lieu à une information vraiment inattendue, a joué un rôle majeur dans le fait que l’article de Shannon, qui n’était pas destiné au lecteur, a fait sensation et a été repris par la presse comme clé universelle de la connaissance de la nature. - des linguistes et des critiques littéraires aux biologistes.

MaisConcept d'information de Shannon - théorie mathématique rigoureuseet son application en dehors de la théorie de la communication est très peu fiable. Mais dans la théorie de la communication elle-même, elle joue un rôle central.

Information sémantique

Shannon, introduisant le concept d'entropie comme mesureinformations, j'ai eu l'opportunité de travailler avec des informations - tout d'abord, de les mesurer et d'évaluer des caractéristiques telles que la capacité du canal ou le codage optimal. Mais l'hypothèse principale qui a permis à Shannon de fonctionner avec succès avec l'information était l'hypothèse selon laquelle la génération d'informations est un processus aléatoire qui peut être décrit avec succès en termes de théorie des probabilités.Si le processus est non aléatoire, c'est-à-dire qu'il obéit aux lois (en outre, il n'est pas toujours clair, comme cela se passe en langage naturel), le raisonnement de Shannon ne lui est pas applicable.Rien de ce que dit Shannon n’a à voir avec le sens de l’information.

Alors que nous parlons de caractères (ou lettres de l'alphabet),nous pouvons bien discuter en termes d'événements aléatoires, mais dès que nous en arriverons aux mots de la langue, la situation changera radicalement. La parole est un processus spécialement organisé. La structure du message n’est pas moins importante que les caractères qui le transmettent.

Récemment encore, il semblait que nous ne pouvions rien faire.fait pour se rapprocher au moins d’une manière ou d’une autre de la mesure de la signification du texte, mais ces dernières années, la situation a commencé à changer. Et cela est principalement dû à l'application de réseaux de neurones artificiels aux tâches de traduction automatique, de résumé automatique de textes, d'extraction d'informations à partir de textes et de génération de rapports en langage naturel. Toutes ces tâches impliquent la transformation, l’encodage et le décodage d’informations significatives contenues dans le langage naturel. Et progressivement, une idée se forme sur les pertes d'informations lors de telles transformations, et donc sur l'étendue des informations significatives. Mais aujourd’hui, la clarté et la précision de la théorie de l’information de Shannon ne sont pas encore disponibles dans ces problèmes difficiles.