C’est super de créer des images, de télécharger des musiques, d’écrire ses mémoires sur son ordinateur. On a du coup beaucoup d’informations qui nous sont précieuses, et on voudrait les préserver. Seulement une mémoire informatique n’est pas totalement infaillible. Et oui, avec le temps un DVD peut s’abîmer, une partie d’un disque dur se dégrader… Et quand on envoie un message ce n’est pas mieux. Entre la ligne téléphonique qui peut avoir une mauvaise réception et les infos sur le net qui transitent par de nombreuses machines avant d’arriver à destination, le message peut s’abîmer.
Du coup, pour se protéger contre ce problème, on peut être amené à rajouter un peu d’information en plus du message qu’on voulait envoyer. Cette information supplémentaire n’appartient pas au message d’origine, mais va permettre, quand on reçoit un message, de voir si celui-ci a été dégradé, voire même encore mieux, de “réparer” le message dans certains cas. Cela s’appelle la redondance.
C’est bien joli tout ça mais vous ne croyez pas que vous abusez un peu là ? Dans les chapitres précédents on vient d’apprendre comment compresser les données et maintenant vous voulez qu’on en rajoute ? Ce n’est pas logique !!
Oui d’accord au premier abord ça semble contradictoire, mais au fond rien n’empêche de faire les deux : on compresse son texte, ce qui nous fait gagner 40% de place, puis on le transmet/stocke avec un peu de redondance pour se protéger contre la perte d’informations. Et au final il y a même moyen d’avoir un texte qui est protégé contre la perte d’information et qui prend moins de place que le texte d’origine. Pas mal, non ?
Si je vous ai bien convaincu, voyons donc comment cela fonctionne !
Comprendre en faisant… un tour de magie
Pour vous expliquer la redondance, vous allez apprendre à faire un tour de magie ! Vous êtes prêts ?
Déroulement du tour
Alors si on récapitule, le tour c’est ça : l’assistant·e du magicien (qui fait tout le boulot en fait), Marie dans la vidéo, donne 25 cartes à un membre du public qui les dispose en 5 lignes de 5 cartes, en choisissant pour chaque carte la face à montrer. Ensuite le ou la magicien·ne, Adrien dans la vidéo, vient mémoriser les cartes pendant un nombre de secondes choisi par le public (30 c’est ennuyeux car long, moins de 5 il faut refuser en général). Il se retourne de nouveau pendant que son assistante rajoute une ligne et une colonne de cartes, comme elle le veut. Ensuite, sans que le magicien ne regarde, un membre du public cache le trésor sous une carte et retourne la carte. Puis le magicien revient et retrouve le trésor. Bluffant non ? Et ça l’est encore plus quand on sait que le rôle d’Adrien, un peu lent sous la pression du public, peut être joué par... un élève de fin de CP !
Le truc du magicien
Alors réfléchissez un peu, essayez de trouver le truc, et quand vous avez trouvé (ou que vous n’en pouvez plus devant tant de suspense), visionnez l’explication.
Le tour demande un peu d’entraînement car c’est à vous de jouer l’assistant·e, de mettre les cartes en plus de façon naturelle, pour que personne ne remarque que vous comptez au fur et à mesure. Mais cela vaut le coup. Le public est complètement acquis à votre cause, et boit vos paroles jusqu’à avoir la solution. Ah oui et au fait, les 5 secondes de mémorisation au début ne servent absolument à rien pour le tour, le magicien doit juste avoir confiance en son assistante qui ajoute des cartes et met en place le truc. C’est juste un peu de poudre aux yeux, inutile en théorie mais indispensable en pratique dans tout bon tour de magie.
Détecter ou corriger les erreurs ?
Quand on utilise de la redondance, il faut faire la distinction entre détection et correction d’erreurs. Certains algorithmes permettent juste de détecter des erreurs. C’est souvent suffisant, par exemple si la transmission d’un message n’est pas trop longue, on peut juste regarder s’il y a une (ou plusieurs) erreur(s) et si oui demander à ce que le message soit renvoyé. Dans un disque de stockage, savoir que ce qu’on a stocké est invalide ne nous aide pas vraiment si on n’a pas moyen de retrouver la vraie information. Il faut donc dans ce cas permettre de corriger la/les erreurs. Et un même algorithme peut parfois permettre de faire les deux. Dans notre tour de magie, on est sûr de détecter un problème quand il y a jusque 3 erreurs, mais on ne peut en corriger qu’une, comme on peut le voir dans l’extrait ci-dessous.
Un autre cas de redondance : le code barre
Si le tour de magie est une façon garantie pour présenter un concept informatique en impressionnant tout le monde, c’est bien loin d’en être la seule utilité. Beaucoup de codes utilisent de la redondance pour détecter des erreurs.
On peut citer la clé d’un numéro de sécurité sociale, l’identifiant des livres – le numéro ISBN – ou ce bon vieux code barre.
Un code barre standard se compose de deux choses : des barres verticales plus ou moins épaisses, et leur traduction en 13 chiffres. Si les barres sont faites pour être lues par un lecteur optique, les chiffres servent en cas de problème à être saisis directement par des humains. Seulement un code barre peut être abîmé, ou collé sur un sac plastique, et se replier un peu sur lui même. Et quand on achète un kilo de légumes, on n’a pas envie que le lecteur se trompe et nous facture la dernière console à la mode.
Et bien justement, les concepteurs du code barre y ont pensé, et il se trouve que seuls les 12 premiers chiffres servent à coder le type de produit. Le treizième, lui, sert à détecter les erreurs. Il est donc calculé en fonction des autres.
Pour trouver ce dernier chiffre (ici le 4) il faut, avec les 12 premiers :
prendre un chiffre sur deux en partant du premier, et en faire la somme,
ici 5 + 4 + 0 + 0 + 4 + 6 = 19prendre un chiffre sur deux en partant du deuxième, en faire la somme et multiplier le résultat par 3,
ici 4 + 9 + 0 + 0 + 5 + 1 = 19 et 19 * 3 = 57faire la somme des deux résultats obtenus,
ici 19 + 57 = 76ne garder que le chiffre des unités,
ici 6puis retirer ce chiffre à 10.
ici 10 - 6 = 4
Du coup si le code barre est plié/dégradé, il y a au moins 9 chances sur 10 de tomber sur un code qui n’existe pas. Encore mieux : si un seul des chiffres est changé, il est tout bonnement impossible de tomber sur un code valide et on est sûr de détecter que le code a été mal lu...
La redondance, une solution universelle ?
Si on avait une solution magique à tous les problèmes ça se saurait. Tout d’abord, il faut savoir que plus on veut de fiabilité, plus il faut de redondance, et donc plus ça prend du temps (à écrire tout ça, ou à le transmettre) et de la place (pour stocker 15 fois la même information). Du coup il faut faire un compromis en fonction :
de l’importance de l’information : plus elle est cruciale plus il faut de précautions,
du coût de stockage : si on fournit un service super fiable mais que personne ne peut s’offrir c’est moyennement utile,
de l’espace mémoire disponible : on ne peut pas se permettre de stocker une seule image par disque dur,
et du temps nécessaire à stocker/récupérer une information : regarder un film nécessite de lire 24 images par seconde. Si avec la redondance on ne peut en récupérer que 10 par seconde, ce n’est pas possible.
Et puis l’erreur peut venir d’ailleurs, comme on va le voir avec l’échec du lancement de la fusée Ariane V en 1996. Pourtant elle utilisait de la redondance. Le calculateur de vitesse avait été dupliqué, pour se protéger contre une défaillance matérielle. Seulement ces calculateurs avaient été mal conçus/vérifiés, et ils calculaient tous les deux… exactement la même erreur ! Du coup la fusée s’est mise à pencher de plus en plus, jusqu’à ce casser en deux et exploser en vol.
Et quelle était donc cette erreur ?
Et bien vous vous souvenez de la partie précédente où je vous disais qu’il fallait donner un type à chaque variable ? Là justement le programme essayait de ranger un nombre trop grand dans une variable du mauvais type, qui était trop petite. Du coup le pilote automatique n’a pas su comment interpréter les résultats, et a fait n’importe quoi. Eh oui, le type d’une variable c’est tellement important que ça peut faire exploser une fusée !
Comme quoi, même avec de la redondance, il y a encore du boulot pour les créateurs de bons algorithmes. Car sans un algorithme correct, on peut bien mettre toute la redondance que l’on veut, ça ne sert strictement à rien !
En résumé
La redondance consiste à rajouter de l’information supplémentaire pour permettre de détecter voire de corriger des erreurs.
On peut illustrer son intérêt en réalisant un tour de magie.
La redondance est utilisée dans de nombreux domaines, depuis les codes barres jusqu’à la conquête de l’espace.
La redondance est utile mais ne peut rien faire contre un programme buggé/mal conçu.
En fonction des usages, il faut faire un compromis entre le niveau de protection contre la perte d’information, et le temps/surcoût qu’engendre la redondance.
