L’électronique, l’informatique et le logiciel sont des domaines techniques qui sont loin d’être infaillibles. Ce faisant, les scientifiques et ingénieurs se sont rapidement rendu compte dans les années 1950 que des mécanismes prévenant la corruption et la perte de données stockées ou transmises devaient être mis en place dans nos ordinateurs.

Parmi les différents algorithmes imaginés à cet effet, on distingue notamment les algorithmes de correction d’erreur qui ont pour but de vérifier et corriger des données reçues. Les premiers algorithmes du genre étaient assez basiques : pour simplifier, l’émetteur rajoute des octets redondants dans un message qui, via un calcul simple, permettent de vérifier l’intégrité de ce dernier, et dans le cas d’une corruption de celui-ci, de le corriger. C’est d’ailleurs cette dernière propriété qui distingue ces algorithmes des sommes de contrôle (checksums), uniquement utilisées pour vérifier l’intégrité d’un message.

Ces algorithmes ont un défaut important : l’émetteur doit connaître a priori la fiabilité du moyen de communication utilisé. C’est de cette manière qu’il peut juger combien d’octets redondants sont nécessaires pour être sûr que, malgré une éventuelle corruption, le message original pourra être reconstitué. Malheureusement, dans la pratique, il est souvent impossible de connaître a priori cette donnée.

Par exemple, prenons le cas de nos chers smartphones dont la fiabilité de la connexion varie drastiquement suivant la proximité de l’antenne relais et la puissance de son signal. Afin d’avoir plus de flexibilité, des chercheurs ont inventé au début des années 2000 un codage dit fontaine. L’idée sous-jacente est de générer depuis un message originel un flot continu et potentiellement infini de données, à l’image du flot d’une fontaine. Il suffit alors au récepteur de ne capter qu’une portion de ce flot, d’une longueur légèrement supérieure à celle du message transmis, pour pouvoir entièrement reconstituer celui-ci. Ce type d’algorithme est à l’évidence très avantageux : nul besoin de décider a priori du taux de redondance de l’information, il suffit juste d’envoyer un flux suffisamment long pour que le récepteur reçoive le message avec une grande probabilité. De plus, aucune hypothèse n’est réalisée sur la perte en route : le message peut être reconstitué depuis n’importe quel fragment, pourvu que suffisamment de fragments ont été reçus.

Ce type de solution particulièrement efficace a notamment été intégré à la norme internationale DVB-IPTV, utilisée pour diffuser des programmes de télévision par voie IP.

Les travaux des professeurs Yuval Cassuto and Amin Shokrollahi, membres du département d’ingénierie électrique au Technion, ont porté sur une version plus adaptative des ces méthodes type fontaine. Leur idée est tirée d’un constat : ces algorithmes classiques sont rarement optimaux dans toutes les situations de perte. Par exemple, certains sont efficaces pour la densité d’information lorsque la fiabilité de la connexion est grande, mais le sont moins dans d’autres situations. Ainsi, leur but a été de formaliser et construire un algorithme reprenant les mêmes bases, mais adaptatif en fonction du taux de perte, permettant ainsi d’optimiser en permanence le flux de données transmis. Pour cela, l’émetteur compte sur un retour d’information périodique de la part du récepteur, celui-ci lui donnant les statistiques de perte qui permettent ainsi au premier de s’adapter en conséquence.

A premier vue, une telle amélioration ne paraît pas forcément indispensable ou conséquente. Mais si l’on considère les flux de données transitant actuellement sur nos smartphones via les 3G et 4G, la moindre optimisation permet d’améliorer significativement l’utilisation des infrastructures de télécommunication et le service, et fait ainsi économiser des sommes importantes aux opérateurs télécom.

Rédacteurs : Paul Balança, Volontaire international chercheur au Technion – Israel Institute of Technology