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 proposa le nom de BIT

(BIT, BInary digiT - "nombre binaire" - "High-tech")- Un des concepts principaux du XXème siècle. Tukey a choisi un bit pour désigner un chiffre binaire capable de prendre la valeur 0 ou 1. Dans son article intitulé «Théorie de la communication mathématique», Claude Shannon a suggéré de mesurer la quantité d'informations en bits. Mais ce n’est pas le seul concept présenté 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 jetons la bonne pièce: il a d'un côté un aigle et de l'autre une queue, comme il se doit. La chute d'un aigle ou d'une queue sera deux événements différents qui composent notre espace d'événements aléatoires. Si nous rapportons le résultat d'un seul lancer, ce seront vraiment de nouvelles informations. Quand un aigle tombe, nous signalons 0, et quand il est décisif 1. Pour communiquer cette information, nous n'avons besoin que d'un bit.

Qu'est-ce qui a changé? L'incertitude est apparue dans notre espace d'événements. Nous avons quelque chose à dire à quelqu'un qui ne lance pas de pièce et ne voit pas le résultat du lancement. Mais pour bien comprendre notre message, il doit savoir exactement ce que nous faisons, ce que 0 et 1 signifient. Nos espaces événementiels doivent correspondre, et le processus de décodage consiste uniquement à restaurer le résultat du lancer. Si les événements d'émission et de réception n'ont aucune possibilité de décodage sans ambiguïté du message sans que cela coïncide ou se produit, l'information restera uniquement du bruit dans le canal de communication.

Si indépendamment et simultanément jetant deuxpièces de monnaie, il y aura quatre résultats également probables: aigle-aigle, queues, queues-têtes et queues. Pour transmettre des informations, nous aurons déjà besoin de 2 bits et nos messages seront les suivants: 00, 01, 10 et 11. Les informations sont devenues deux fois plus nombreuses. Cela s'est produit parce que l'incertitude a augmenté. Si nous essayons de deviner le résultat d'un tel lancer par paire, nous avons deux fois la possibilité de nous tromper.

Plus l'incertitude de l'espace des événements est grande, plus l'information contiendra de message sur son état.

Compliquons légèrement 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 ne sont pas également probables. Par exemple, la probabilité que le corbeau que nous voyons soit noir soit proche de 1. La probabilité que le premier passant dans la rue soit un homme est d'environ 0,5. Mais c’est presque incroyable de rencontrer un crocodile dans la rue de Moscou. Intuitivement, nous comprenons que le fait de signaler une rencontre avec un crocodile a une valeur d’information bien supérieure à celle d’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 noires, donclaissez noir - 0 - le code le plus court, et le reste du code commence à 1. De la moitié restante, le blanc correspond à 10, et les couleurs restantes commencent à 11. En conclusion, on note rouge - 110 et bleu - 111.

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

Shannon Entropie

Laissez notre espace événementiel composé de ndifférents événements. Lorsque vous lancez une pièce de monnaie avec deux aigles, un tel événement correspond exactement à un, lorsque vous jetez une pièce correcte - 2, lorsque vous jetez deux pièces de monnaie ou que vous regardez des voitures - 4. Chaque événement correspond à la probabilité de sa survenue. Quand une pièce avec deux aigles est lancée, l'événement (perte de l'aigle) est égal à un et sa probabilité est p1 = 1. Lorsque la pièce correcte est lancée, deux événements ont la même probabilité et la probabilité de chacun est 0,5: p1 = 0,5, p2 = 0,5. Lorsque deux pièces correctes sont lancées, 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 événements automobiles, il y a quatre événements et leurs probabilités sont 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:

  • 1Entropie d'un événement fiable, dont la probabilité est 1, est 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 compatibles avec notreidées sur l'incertitude de l'espace événementiel. Si l'événement est un (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 - elles s’additionnent (exemple de lancer deux pièces). Enfin, si tous les événements sont également probables, le degré d’incertitude du système est maximal. Comme dans le cas du lancement de deux pièces, les quatre événements sont probables et l’entropie est égale à 2, c’est plus que dans le cas des voitures, mais il existe une probabilité différente. Dans ce cas, l’entropie est 1,75.

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

Claude Shannon

Claude Elwood Shannon - ingénieur américain, cryptanalyste etmathématicien. Il est considéré comme le "père de l'ère de l'information". Fondateur de la théorie de l'information, qui a trouvé une application dans les systèmes de communication de pointe modernes. Fourni les concepts fondamentaux, les idées et leurs formulations mathématiques qui forment 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 de Bell Laboratories a travaillé au développement de systèmes cryptographiques. Plus tard, cela lui a permis de découvrir des méthodes de codage avec correction des 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.

Vous pouvez coder les messages de différentes manières. Mais Shannon a montré que le code le plus court ne pouvait pas être moins en bits que l'entropie.

C’est pourquoi l’entropie du message est la mesureinformations dans le message. Puisque dans tous les cas considérés, le nombre de bits dans le codage est égal à l'entropie, cela signifie que le codage a réussi de manière optimale. En bref, il n’est plus possible de coder des messages concernant des événements dans nos espaces.

Avec un codage optimal, vous ne pouvez pas perdre oudéformer un seul bit transmis dans un message. Si au moins un bit est perdu, les informations seront déformées. Mais tous les canaux de communication réels n'offrent pas une certitude absolue que tous les bits du message parviennent au destinataire sans être déformés.

Pour résoudre ce problème, vous devez fairele code n'est pas optimal, mais redondant. Par exemple, pour transmettre avec un message sa somme de contrôle - une valeur spécialement calculée obtenue lors de la conversion d'un code de message et qui peut être vérifiée en recalculant à la réception d'un message. Si la somme de contrôle transférée correspond à celle calculée, la probabilité que la transmission se passe sans erreur sera assez élevée. Et si la somme de contrôle ne correspond pas, vous devez demander une retransmission. C'est ainsi que fonctionnent la plupart des canaux de communication aujourd'hui, 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 les uns avec les autres est hautement redondant et donc fiable si nous n'entendons pas quelque chose - pas de mal, les informations seront toujours transmises.

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 gâchétexte? Il contient vraiment les informations nécessaires pour récupérer des mots entiers. Un locuteur russe a un certain ensemble d'événements (mots et phrases entières) qu'il utilise pour la reconnaissance. En outre, le transporteur dispose également de structures de langage standard lui permettant de récupérer des informations. Par exemple "Elle est blae blee" - peut être lu avec une probabilité élevée que "Elle était plus sensible.". Mais une phrase séparée "Elle est plus bla"il sera plutôt restauré comme "Elle était plus blanche". Puisque nous avons affaire à la communication quotidienneavec les canaux dans lesquels il y a du bruit et des interférences, nous sommes assez bien capables de récupérer des informations, mais seulement celle que nous connaissons déjà Par exemple, la phrase "Ses traits ne sont pas du tout agréables, htya nmngo rspkhli et splash" lisible sauf le dernier mot "Splash" - "rallié". Ce mot n'est pas dans le lexique moderne. Avec une lecture rapide du mot "Splash" se lit plutôt comme "collé ensemble", tandis que lent - juste des chicanes.

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.

Avec la communication numérique sur le canal, nous ne pouvons transmettre qu'un nombre fini de valeurs. Est-ce que cela signifie que le son ne peut pas être transmis avec précision? Il s'avère non.

Différents sons sont sinusoïdes modulés 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 s'y superpose.modulation créée par les valeurs transmises sur le canal de communication. Il existe des principes précis sur les valeurs discrètes qui doivent être transmises, de sorte que le son à l'entrée du canal de communication coïncide avec le son à la sortie, où ces valeurs sont superposées à une sinusoïde standard (c'est le théorème de Kotelnikov).

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) - déclaration fondamentale dans le domaine du numériquetraitement du signal, connexion de signaux continus et discrets et indiquant que «toute fonction F (t) composée de fréquences de 0 à f1 peut être transmise en continu avec une précision quelconque, à l’aide de nombres qui se suivent après 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. Supposons que notre langue entière se compose de trois mots: 111000, 001110, 100011. Ces mots connaissent à la fois la source du message et le destinataire. Et nous savons que des erreurs se produisent dans le canal de communication, mais pas plus d'un bit d'information n'est déformé lors de la transmission d'un mot.

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 est due à 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 lorsqu'une erreur survient, le destinataire ne peut pasconfondre un mot avec un autre. Par exemple, si le dictionnaire se compose des mots «fille», «point», «bosse» et s’il s’est avéré «petit», le destinataire, sachant qu’il n’existe pas de mot, ne peut pas corriger l’erreur. correct Si le dictionnaire inclut “point”, “jackdaw”, “branch” et que nous savons qu'une seule erreur est autorisée, alors “petit peu” est évidemment un “point” et non “daw”. Dans les codes de correction d'erreur, les mots sont choisis de manière à être «reconnaissables» même après une erreur. La seule différence est que dans le code "alphabet", il n’ya 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 figurer dans le dictionnaire). Mais la transmission exacte du message est si importante que des efforts importants sont consacrés à l’étude des codes résistant au bruit.

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.

Mais Concept 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 mesureinformation, a eu l’occasion de travailler avec l’information - tout d’abord, de la mesurer et d’évaluer des caractéristiques telles que la capacité des canaux ou l’optimalité du codage. Mais la principale hypothèse qui a permis à Shannon d’opérer avec succès avec l’information était celle voulant que la génération d’informations soit un processus aléatoire pouvant être décrit avec succès en termes de théorie de la probabilité. 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. Tout ce que dit Shannon n'a rien à voir avec la signification 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.

Plus récemment, il semblait que nous ne pouvons pasfaire quelque chose pour se rapprocher de la mesure du sens du texte, mais la situation a commencé à changer ces dernières années. Et ceci est principalement dû à l'utilisation de réseaux de neurones artificiels pour les tâches de traduction automatique, de synthèse automatique de texte, d'extraction d'informations à partir de textes, de génération de rapports en langage naturel. Dans toutes ces tâches, la transformation, l'encodage et le décodage d'informations significatives contenues dans le langage naturel ont lieu. Et petit à petit, l’idée de pertes d’informations dans de telles transformations et, partant, l’étendue d’une information utile prend forme. Mais aujourd'hui, la clarté et la précision de la théorie de l'information de Shannon dans ces tâches difficiles ne sont pas encore disponibles.