Allocation de ressources efficace en codage numérique

Approches suivant le domaine considéré

Approche taux-distorsion Le problème d’allocation de ressources sous contrainte est, en codage de source, un problème classique depuis longtemps mis en évidence et étudié. Initialement, Huang et Schultheiss [HS63] l’abordèrent dans le cadre de leurs travaux prouvant l’optimalité de la transformée de KarhunenLoeve, et depuis, le problème a été abondamment traité, sous différentes formes et hypothèses, dans des conditions diverses. De par la définition que nous avons faite du problème d’allocation de ressources, inspirée du monde du codage de source, l’ensemble des éléments théoriques et des méthodes de cette thèse s’appliquent pratiquement de manière directe. Nous avons essayé de rendre l’écriture des algorithmes présentés la plus générale possible en gardant un contexte et des notations unifiés.
Approche taux-puissance Les systèmes de modulation discrète multi-tons, Discrete Multi-Tone modulation (DMT) en anglais, furent les premiers à introduire cette notion d’allocation de ressources en codage de canal. C’est Hughes-Hartogs [Huga] qui, au travers d’un patent, mis le premier en œuvre ce genre de méthode. Plus généralement, les systèmes de modulation multi-porteuses sont aujourd’hui à l’origine d’une conséquente bibliographie sur le problème d’allouer une puissance (ou un taux) sous une contrainte de budget. Cela est essentiellement dû au succès du domaine d’application : systèmes de communication xDSL et systèmes de transmission sans fil sont en développement constant et représentent des enjeux commerciaux considérables. Il est important de noter que le taux a été très souvent considéré comme entier (on y fait référence comme des bits). Cela n’est pourtant pas une obligation. Cette hypothèse permet de grandement simplifier les méthodes de résolution du problème d’allocation de ressource mais elle n’est pas forcément exclusive. D’autre part, les fonctions considérées sont toujours implicitement supposées convexes. Si cette hypothèse paraît vraisemblable, elle ne suffit pas à elle seule à garantir l’optimalité de certaines méthodes.
Autres approches Nous avons essentiellement étudié les problèmes issus des communications numériques. Il existe toutefois des articles plus généraux [Eve63, Fox66] ou provenant de domaines différents qui tentent de résoudre le même problème. On l’utilise ainsi pour modéliser des situations (quelquefois en tant que sous-problème) telles que :
– dans des systèmes d’aide à la gestion de portefeuille : on souhaite alors équilibrer sélectivité et diversification afin de trouver le meilleur rapport entre rendement et risque pour un capital placé sur plusieurs actifs financiers ;
– dans le chargement de bateau ou d’avion : tous les bagages à destination doivent être amenés, sans être en surcharge ;
– dans la découpe de matériaux : pour minimiser les chutes lors de la découpe de sections de longueurs diverses dans des barres en fer ;
– …
Autant de problèmes plus ou moins originaux qui, de par leur modélisation, se ramènent à la description faite dans ce manuscrit du problème d’allocation de ressource. Une autre raison de s’intéresser à ce type de problème d’allocation est son apparition dans certaines utilisations de méthodes de génération de colonnes (ainsi pour le problème de « bin packing »). Les variables ont alors une réalité toute autre, et les contraintes de fonctions sont parfois différentes. Nous citerons à titre d’exemple le problème bien connu du sac à dos à variables binaires qui est un cas particulier de notre étude pour laquelle les Mi = 2 (N quelconque) et où les fonctions employées sont de taux régulièrement espacés à trous. Nous pourrons de toute manière toujours ramener ces problèmes à la définition initiale faite au premier chapitre du problème d’allocation de ressources.

Principes de recherche de points optimaux

   De la découverte d’un point optimal dans un triangle ∇h par la relation ≺ découle une modification de la zone de recherche des points optimaux. En effet si on trouve par la relation d’ordre un point P1 = (R1, D1) dans le triangle caché, il est alors optimal (par le théorème 4.2.2). Dans ce cas, tout point P = (R, D) appartenant à la région rectangulaire entre P1 et Q0 ne peut être optimal, puisque R1 < R et D1 < D. Ce résultat permet de réduire grandement la zone de recherche de points optimaux cachés. En effet, la zone de recherche exclut désormais la partie hachurée dans 4.1 (car déjà étudiée) et le rectangle entre Q0 et P1. Celle-ci se résume à la réunion de deux triangles rectangles. Ces traingles sont illustrés figure 4.2 et sont définis à partir des points Q1 et Q2 déduits de P1. Ces deux nouveaux points fictifs Q1 et Q2 reprennent le rôle de Q0 dans leur triangle respectif. Ainsi, si Q0 = (R0, D0) et P1 = (R1, D1), les valeurs de ces points sont : Q1 = (R1, D0) et Q2 = (R0, D1). Les points cachés recherchés dans le triangle associé à Q1 seront donc majorés (au sens de la relation d’ordre ≺) par Q1 et les points cachés recherchés dans le triangle associé à Q2 majorés par Q2. Nous noterons que la caractérisation du triangle initial de recherche de points optimaux {D <D0, R < R0, P ≺ (R0, D0)} peut simplement s’adapter à la caractérisation d’un des deux triangles en remplaçant R0 par R1 pour le triangle de Q1 et et D0 par D1 pour le triangle de triangle de Q2. Ainsi nous avons un procédé d’implémentation particulièrement simple et efficace. Au fur et à mesure que nous trouverons des points cachés {P1, P2, . . . , Pj, . . .}, nous définirons autant de nouveaux couples de points fictifs dont les taux et distortions dépendront  des {Rj} et {Dj} et de leurs positions respectives. Nous aurons alors autant de triangles à étudier, la recherche se finissant lorsque le dernier triangle étudié est complètement parcouru. Ainsi décrit, nous noterons que le principe de tri peut s’appliquer à la recherche de tous les points optimaux. Les zones de recherche sont alors les triangles cachés ∇h successifs, caractérisés par des multiplicateurs critiques qui nous sont donnés par l’algorithme D. L’ensemble des points trouvés au final permet de résoudre le problème de la courbe optimale R-D.

Algorithme A

   L’algorithme RDPO n’est pas un algorithme pour résoudre le problème d’allocation de ressource à proprement parler, mais celui-ci intervient dans certains algorithmes. Nous allons donc calculer le nombre d’opérations nécessaires à son exécution sur un nuage de points de cardinal C. Nous ne calculerons pas la taille mémoire nécessaire à l’algorithme car celui-ci correspond à la taille mémoire nécessaire aux données initiales, c’est à dire C. Nous faisons un tri initial par ordre croissant sur les C points, cela demande donc Clog(C) comparaisons. Ensuite, pour trouver les points optimaux, nous faisons au total C comparaisons pour trouver le point succédant le point courant. Au final, à partir d’un nuage de C points, nous avons réalisé la recherche des points optimaux112 C. Calculs de complexité et de coût mémoire d’algorithmes en O(Clog(C)) opérations. Nous avons donc un nombre d’opérations en O(log(C)) opérations par points du nuage.

Table des matières

Introduction
1 Le problème d’allocation de ressources 
1.1 Introduction
1.2 Présentation du problème 
1.3 Problèmes duaux 
1.4 Applications
1.4.1 Codage de source par transformée
1.4.2 Codage multi-canaux
1.5 Définitions et propriétés fondamentales
1.5.1 Points optimaux
1.5.2 Points d’enveloppe
1.5.3 Considérations autour des alignements
1.5.4 L’opération élémentaire ∆~
1.5.5 Points cachés
1.6 Corpus de test
1.7 Critères de comparaison 
1.7.1 Critères théoriques
Complexité
Coût mémoire
1.7.2 Critères expérimentaux
Temps de calcul moyen
Pourcentage de points optimaux
Perte en distorsion moyenne
1.8 Conclusions 
2 L’état de l’art 
2.1 Introduction
2.2 Approches envisagées 
2.2.1 Approches suivant le domaine considéré
Approche taux-distorsion
Approche taux-puissance
Autres approches
2.2.2 Approches suivant la méthode considérée
Approche continue
Approche lagrangienne
Autres approches
2.3 Méthodes de recherche de points d’enveloppe du plan global 
2.4 Méthodes de recherche de points cachés du plan global 
2.5 Performances 
2.6 Conclusions
3 Recherche optimale par chemins convexes 
3.1 Introduction 
3.2 Définition du concept de chemin convexe
3.3 Mise en place d’un critère de recherche efficace
3.4 Description d’un algorithme optimal de recherche par chemins convexes 
3.5 Performances
3.6 Conclusions
4 Recherche optimale par ordonnancement 
4.1 Introduction
4.2 Définition d’une nouvelle relation d’ordre 
4.3 Principes de recherche de points optimaux 
4.4 Méthode efficace de parcours des points ordonnés du plan global
4.5 Description d’un algorithme optimal de recherche par ordonnancement
4.6 Performances
4.7 Conclusions 
5 Recherche sous-optimale par omission d’index 
5.1 Introduction 
5.2 Définition de l’opération d’omission d’index 
5.3 Nouvelle enveloppe convexe par omission d’index
5.4 Description d’un algorithme sous-optimal de recherche par omission d’index 
5.5 Performances 
5.6 Conclusions 
6 Recherche sous-optimale par chemins convexes 
6.1 Introduction 
6.2 Considérations pratiques d’adaptation de la recherche par chemins convexes 
6.3 Description d’un algorithme sous-optimal de recherche par chemins convexes 
6.4 Performances
6.5 Conclusions
Conclusions et perspectives
A Equivalence des courbes optimales réciproques
B Corpus de test
C Calculs de complexité et de coût mémoire d’algorithmes
C.1 Algorithme A
C.2 Algorithme B
C.3 Algorithme D
C.4 Algorithme E
C.5 Algorithme G
C.6 Algorithme H
Bibliographie

Télécharger le rapport complet