Optimal and sub-optimal methods for efficient resource allocation in digital coding
Méthodes optimales et sous-optimales d'allocation de ressources efficace en codage numérique
Résumé
The resource allocation problem in digital coding consists in the global cost optimization of a system distributing in several components a resource constrained by a budget. Each component follows a rule linking the resource to the cost it spends. We meet this description in different contexts. We especially deal with two major ones issued from the coding domain in digital communications. In one hand, transform source coding systems, on the other hand, channel coding with multi-carrier modulation systems, corresponds to the same notions of optimization. In digital communications, different solving methods have been studied for forty years. Their performance depends on the studied functions and their validity is usually limited to some non-exhaustive cases. Moreover, complexity and optimality are essential but rarely managed jointly due to modelization techniques and searching methods. One of the major problem comes from the existence of so called "hidden" points. They are not on the convex hull of the global feasible cloud and usually ignored by the current optimisation methods. This thesis proposes to deal with the resource allocation problem in digital communications over a new and global point of view. The complete rewriting of the problem and the underlying concepts allows to state the criterion for the description of four innovative algorithms.
Le problème d'allocation de ressources consiste à optimiser le coût global d'un système en répartissant selon diverses composantes une ressource contrainte par un budget. Chaque composante du système est régie par une loi reliant la ressource au coût qu'elle engendre. Cette description s'applique à de nombreux contextes dont les deux principaux évoqués ici sont issus du codage en communications numériques. Ainsi, les systèmes de codage de source par transformée ou de codage de canal à modulation multi-porteuses intègrent ce problème dans la recherche d'un point de fonctionnement optimal, s'adaptant bien à un formalisme commun. En communications numériques, différentes méthodes de résolution ont été élaborées au cours des quarante dernières années. Leur validité se limite souvent à des cas non-exhaustifs et leurs performances dépendent des caractéristiques des fonctions considérées. De plus, complexité et optimalité revêtent une importance particulière mais sont rarement optimisées de concert en raison des techniques de modélisation et des principes de recherche employés. Un des problèmes majeurs provient en particulier de l'existence de points dit "cachés" n'appartenant pas à l'enveloppe convexe du nuage global et souvent ignorés par les méthodes actuelles d'optimisation. Cette thèse propose d'aborder le problème d'allocation de ressources en communications numériques sous un angle nouveau et global. La reformulation complète du problème et de l'ensemble des concepts sous-jacents permet ainsi d'énoncer des critères propices à la description de quatre algorithmes novateurs.
Domaines
Electronique
Loading...