Alors que depuis maintenant une trentaine d’années la planète subit une crise mondiale énergétique liée à l’épuisement progressif de ressources très convoitées, le problème de la répartition de ces ressources s’impose clairement aux yeux du grand public comme un défi majeur. De même, le processus croissant de mondialisation et la globalisation des marchés internationaux engendrent une nouvelle approche de la distribution des ressources, certains y voyant un prétexte à une disparité grandissante. Plus social mais tout autant d’actualité en France, la réforme du régime des retraites par répartition représente un exemple concret de tentative de résolution d’un problème où le besoin s’accroît alors que la ressource s’amenuise.

Quel que soit le domaine d’étude, le problème reste toujours le même : « Comment répartir efficacement une ressource limitée ? ». Chacun prend aujourd’hui conscience de la fragilité d’un système où le partage des ressources serait mal établi. Une ressource, par essence (sans jeu de mot facile) limitée, demande à être distribuée avec parcimonie, partagée avec efficacité, repartie à moindre coût.

Le terme d’allocation de ressources est bien connu du monde des économiciens. Il s’agit d’un concept relatif à l’utilisation des ressources rares et notamment aux facteurs de production (travail, capital, matières premières) pour satisfaire à court et long terme les besoins de consommation de la population. D’autre part, les informaticiens emploient couramment le terme d’allocation de ressources afin de définir la mise à disposition de mémoire pour une utilisation au profit de variables. Ces deux concepts, issus de mondes bien différents, s’approchent du problème que nous allons traiter dans ce manuscrit. Nous allons toutefois l’aborder de manière quelque peu plus spécifique en établissant les fondements d’une étude relative au domaine du traitement du signal, et plus particulièrement dans le cadre de systèmes de codage numérique.

La littérature originellement concernée par l’application de notre problème mentionne celui-ci sous les termes anglo-saxons rate loading, bit loading, power loading, power allocation, etc. Ces termes reflètent la notion d’attribution d’une ressource de taux ou de puissance donnée dans un système de codage (de source ou de canal). En effet, le système est décomposé de telle manière que la ressource peut être attribuée suivant plusieurs composantes, chacune ayant ses spécificités.

Par contre, ces appellations ne font pas mention de la seconde variable qui donne tout son sens au problème d’allocation : la fonction de coût associée à la ressource. C’est cette fonction de coût qui va nous permettre de déterminer la répartition optimale répondant au problème d’allocation de ressources. En effet, la ressource, couplée à cette fonction dont les caractéristiques dépendent de l’origine du problème considéré, est contrainte à ne pas dépasser un certain budget. Cette limitation nécessite par conséquent la recherche du point de fonctionnement optimal répondant au mieux au critère imposé, c’est à dire à la dépense minimale.

L’optimalité possède dans notre vocabulaire un sens double, sens qui dépendra du terme auquel on le rattache. Nous parlerons ainsi de solution optimale lorsque celle ci est la meilleure solution au problème d’allocation de ressources pour un budget particulier. Il s’agit alors de caractériser un point dans un ensemble global. Ce point sera qualifié d’optimal indépendamment d’une quelconque méthode de résolution, l’optimalité étant alors considérée comme une caractéristique absolue du point.

Cependant nous parlerons aussi d’algorithme optimal. Un algorithme optimal n’est pas seulement un algorithme qui trouve des points optimaux, mais surtout un algorithme trouvant à chaque fois la solution optimale au problème d’allocation de ressource quel que soit le budget. Nous caractérisons alors l’optimalité d’une méthode par les solutions qu’elle propose. L’optimalité d’un algorithme est reliée au problème pour lequel il s’applique, c’est à dire qu’elle est relative aux caractéristiques des fonctions considérées. A contrario, nous nous référerons aux procédures trouvant des points non-optimaux sous le terme de méthodes sous-optimales.

Remarquons que l’optimalité n’est toutefois pas l’unique critère de performance pour les procédures d’allocation de ressources. Une des préoccupations essentielles de tout algorithme est l’efficacité de celui-ci en terme de complexité. Un algorithme efficace se doit de résoudre le problème d’allocation le plus rapidement possible afin de répondre aux contraintes pratiques d’implémentation. À l’heure actuelle, le compromis entre optimalité et complexité est un enjeu fondamental, d’autant plus qu’il n’a été que difficilement maîtrisé par les algorithmes développés jusqu’à présent. L’optimalité de certaines méthodes est atteinte au prix d’une complexité excessive, inadaptée aux contraintes spécifiques du domaine du codage en communications numériques. On utilisera donc exclusivement le terme d’efficacité lorsque l’on souhaitera évoquer la complexité de ces algorithmes.

L’un des principaux moyens pour réduire la complexité consiste à sélectionner des points sousoptimaux possédant des propriétés particulières facilement exploitables. De telles propriétés permettent ainsi de calculer ces points à moindre coût. Les méthodes efficaces actuelles se basent essentiellement sur des propriétés de linéarité et de convexité afin d’atteindre une complexité raisonnable. Toute la finesse de la méthode réside alors dans la proximité de ces points sous-optimaux à la solution optimale, ce qui dépend largement des caractéristiques des fonctions mises en jeu.

La proximité est ici une notion subjective dont il nous faudra fixer une méthode de mesure plus formelle. D’une telle mesure découlera un critère de comparaison capable de classifier les méthodes sous-optimales autrement que par leur complexité. Nous établirons dans ce manuscrit un critère positif, appelé par la suite perte en distortion, et sa minimisation sera un de nos objectifs, celui-ci s’annulant pour des méthodes optimales.