Accès direct au contenu

ENS Cachan

Version anglaise
Recherche avancée
aide Portail documentaire


Accueil > Recherche > Actualités

Recherche - Valorisation

Autour de l'informatique. Un turbo dans l’algo

le 23 janvier 2017

Dans un nouvel « Entretien autour de l’informatique », Serge Abiteboul et Christine Froidevaux interviewent Claude Berrou, notamment connu pour ses travaux sur les turbocodes, très utilisés en téléphonie mobile.

Cortex © Nicolas Rougier

Cortex © Nicolas Rougier

Claude Berrou est informaticien et électronicien, membre de l'Académie des sciences et professeur à Télécom Bretagne. Sa recherche porte aujourd'hui sur les neurosciences informationnelles.

Cet article est publié en collaboration avec le blog Binaire.

Tu étais électronicien au départ, comment es-tu arrivé à l'informatique ?

Je suis un randonneur des sciences. Après une formation initiale à l'école qui s'appelle aujourd'hui Phelma, j'ai fait un peu de tout : électronique, traitement de signal, architecture de circuits. Puis je suis arrivé à l'informatique... par hasard, avec les codes correcteurs et la théorie de l'information.

Une question que nous adorons poser à Binaire, c'est quoi l'informatique pour toi ?

J'ai un aphorisme : l'informatique est à la science, ce que le langage naturel est à l'intelligence. Avant l'informatique, la science, c'étaient des équations, des formules et des théorèmes. L'informatique a permis de mettre en place des séquences d'opérations, des processus, des procédures, pour pouvoir traiter des problèmes complexes. Du coup, c'est presque synonyme de langage et c'est très comparable au langage naturel qui oblige à structurer. De même qu'on a un langage commun, l'informatique propose des langages compréhensibles par tous.

Tu as travaillé sur les codes correcteurs. Tu peux nous dire à quoi ça sert ?

Quand on transmet de l'information, on veut récupérer le message émis parfaitement. Même si on a beaucoup d'utilisateurs, et une bande passante limitée. Si le message est binaire, à cause du bruit et des interférences qui perturbent la ligne, certains 0 émis vont devenir des 1 reçus, des 1 devenir des 0. Plus le bruit est important par rapport au signal, plus fréquentes sont de telles erreurs.
Le rapport signal sur bruit peut être dégradé, par exemple, par de mauvaises conditions météo ou par des perturbations causées par d'autres communications qui s'exécutent en même temps. Avec autant d'erreurs, la qualité est déplorable.
Pour éviter cela, on code l'information à l'émission en ajoutant de la redondance. Le défi, c'est d'être capable de récupérer relativement bien le message sans avoir à mettre trop de redondance, sans trop faire grossir le message. Nous avons un peu le même problème avec le stockage dans les mémoires de masse. Des bits peuvent permuter, peut-être à cause de l'usure du disque. On introduit aussi de la redondance dans ces systèmes pour pouvoir récupérer l'information.

Tu nous parles de ta super invention, les turbocodes.

Les turbocodes sont nés grâce au Titanic, lorsqu'il a fallu assurer la transmission sans câbles de vidéos pour visualiser cette épave (des travaux d'Alain Glavieux). Je me suis amusé à essayer de diminuer l'effet du bruit dans les transmissions, et j'ai pensé qu'on pourrait introduire dans le décodage, pour le traitement d'erreurs, le principe de contre-réaction, une notion classique en électronique.

Pour moi, l'interdisciplinarité est fondamentale ; l'innovation est souvent à l'interface des disciplines. Vous prenez une idée qui a prouvé qu'elle marchait quelque part dans les sciences, et vous essayez de l'adapter dans un tout autre contexte. L'idée à l'origine des turbocodes, c'est d'importer une technique d'électronique en informatique.

Quand on veut réaliser un amplificateur avec un gain élevé, on en met 2 ou 3 en série. Mais ça donne des trucs instables. Pour stabiliser le montage, on met en œuvre un principe de contre-réaction : renvoyer vers l'entrée de l'amplificateur une fraction de sa sortie, avec le signe « - » , cela atténue les variations intempestives.

Je suis parti d'un algorithme connu : l'algorithme de Viterbi. Il permet de corriger (s'il n'y a pas trop de bruit) les erreurs survenues lors d'une transmission à travers un canal bruité et peut donc être considéré comme un amplificateur de rapport signal sur bruit. Le décodeur de Viterbi connaît la loi algébrique qui a servi à construire la redondance du message codé et l'exploite dans un treillis (l'équivalent déterministe d'une chaîne de Markov) et délivre ainsi le message d'origine le plus probable. J'ai donc mis deux algorithmes de Viterbi en série. Et j'ai ensuite essayé d'implémenter la notion de contre-réaction dans le décodage. C'est délicat et je n'étais pas un expert du codage.

Un problème, c'est que l'algorithme de Viterbi fait des choix binaires : le bit a été permuté ou pas. Nous l'avons adapté, avec un collègue, Patrick Adde, pour qu'il fournisse des décisions probabilistes, ce qui améliore nettement la performance du décodeur qui suit.

Comment ça fonctionne ?

Comme je l'ai expliqué, pour protéger un message, on ajoute de la redondance. Le turbocode réalise le codage sur deux dimensions. Une bonne analogie est une grille de mots croisés avec les dimensions verticale et horizontale. Si les définitions étaient parfaites, une seule dimension suffirait. On pourrait reconstruire la grille, par exemple, juste avec les définitions horizontales. Mais comme on ne sait pas toujours à quoi correspondent les définitions et qu'il peut y avoir des ambiguïtés (à cause du bruit, des effacements, etc.), on donne aussi les définitions verticales.

Le décodage ressemble un peu à ce que peut faire un cruciverbiste. Le décodeur travaille en ligne (il exploite les définitions horizontales), puis passe à la dimension verticale. Comme le cruciverbiste, le décodeur fait plusieurs passes pour reconstruire le message.

Avec tout ça, les turbocodes sont efficaces.

On te croit. Des milliards d'objets utilisent cette technologie !

Oui. Toutes les données médias sur la 3G et la 4G sont protégées par les turbocodes.

Cela nous conduit à un autre Claude : Claude Shannon et la théorie de l'information ?

Oui avec cet algorithme, on est en plein dans la théorie de l'information. J'ai d'ailleurs contribué récemment à l'organisation du colloque de célébration du centième anniversaire de la naissance de Shannon à l'IHP, un colloque passionnant.

Shannon a montré que toute transmission (ou stockage) idéale devait normalement se faire avec deux opérations fondamentales. D'abord, pour diminuer la taille du message, on le compresse pour lui enlever le maximum de redondance inutile. Ensuite, pour se protéger contre les erreurs, on lui ajoute de la redondance intelligente.

Shannon a démontré les limites des codes correcteurs en 1948 ! Les turbocodes atteignent la limite théorique de Shannon, à quelques dixièmes de décibels près !

Et maintenant. Tu as glissé vers les neurosciences...

Ma recherche actuelle porte sur les neurosciences informationnelles. Récemment, vous avez interviewé Olivier Faugeras qui vous a parlé des neurosciences computationnelles, une approche assez différente.

Mon point de départ, c'est encore l'information, cette fois dans le cerveau. Le cortex humain est assimilable à un graphe, avec des milliards de nœuds et des milliers de milliards d'arêtes. Il y a des modules spécifiques, et entre les modules, il y a des liens de communication. Je suis persuadé que l'information mentale, portée par le cortex, est binaire.

Suite dans The Conversation

Type :
Communiqués de presse

Auteurs


Serge Abiteboul (ENS Paris-Saclay)
Christine Froideveaux (Université Paris-Sud)

Recherche d'une actualité

Recherche d'une actualité