Codage conjoint source-canal

Table des Matières

Avant-propos

Liste des abréviations

Liste des notations

Chapitre 1 : Principe de base et approches du codage conjoint source-canal
1.1 Système de communication numérique ..
1.2 Fondements de base du codage conjoint source-canal
1.2.1 Principaux théorèmes de codage de Shannon
1.2.2 Problématique du codage conjoint source-canal
1.3 Prémices du codage conjoint source-canal
1.3.1 Protection inégale des données source
1.3.2 Equilibrage des débits
1.4 Approches du codage conjoint source-canal
1.4.1 Assignation d'indice
1.4.2 Quantification optimisée pour un canal bruité
1.4.3 Optimisation conjointe du quantificateur et de l'assignation d'indice
1.4.4 Optimisation conjointe du quantificateur, de l'assignation d'indice et de la modulation
1.5 Résumé

Chapitre 2: Codage de Source : Quantification
2.1 Codage de Source
2.1.1 Définitions
2.1.1.1 Codage de source sans perte
2.1.1.2 Codage de source avec perte
2.1.2 Principe de base du codage de source
2.2 Quantification scalaire
2.2.1 Principe de codage par quantification scalaire
2.2.2 Mesure de performance d’un quantificateur scalaire
2.2.3 Quantificateur scalaire optimal
2.3 Quantification Vectorielle
2.3.1 Principe de la quantification vectorielle
2.3.2 Quantificateur vectoriel optimal
2.3.2.1 Algorithme de Lloyd-Max généralisé
2.3.2.2 Performances du quantificateur vectoriel
2.4 Quantification vectorielle divisée
2.5 Quantification codée par treillis
2.5.1 Théorie débit-distorsion avec contrainte sur l’alphabet
2.5.2 Quantification scalaire codée par treillis
2.5.2.1 Conception d'un quantificateur codée par treillis
2.5.2.1.1 Sélection des treillis
2.5.2.1.2 Alphabet étendu
2.5.2.1.3 Partition d'ensemble
2.5.2.1.4 Etiquetage des branches du treillis
2.5.2.2 Principe de fonctionnement du codeur TCQ
2.5.2.3 Performances de la TCQ
2.5.2.4 Optimisation de la quantification codée par treillis
2.5.3 Quantification vectorielle codée par treillis
2.5.3.1 Performance de la TCVQ
2.5.3.2 Procédure d'optimisation de la TCVQ
2.6 Résumé

Chapitre 3 : Codage de canal redondant
3.1 Principe de base du codage de canal
3.2 Pouvoir de détection/correction des erreurs
3.2.1 Opérations sur les codes
3.2.2 Représentations des codes
3.2.2.1 Poids d'un code
3.2.2.2 Représentation polynomiale
3.2.2.3 Représentation géométrique
3.2.3 Capacité de correction
3.3 Canal de transmission
3.3.1 Capacité du canal
3.3.2 Modèles de canaux
3.3.2.1 Canal binaire symétrique
3.3.2.2 Canal à bruit blanc gaussien additif
3.4 Classes de codes de canal
3.5 Codes en blocs
3.5.1 Codes en blocs linéaires
3.5.1.1 Procédure de codage des codes linéaires
3.5.1.2 Capacité de correction des codes en blocs linéaires
3.5.1.3 Procédure de décodage: détection/correction d'erreur
3.5.1.3.1 Décodage par le tableau standard
3.5.1.3.2 Décodage par syndrome
3.5.1.4 Codes de Hamming
3.5.2 Codes cycliques
3.5.2.1 Construction des codes cycliques
3.5.2.2 Procédure de codage des codes cycliques
3.5.2.3 Procédure de décodage des codes cycliques
3.5.2.4 Classes des codes cycliques
3.6 Codes convolutifs
3.6.1 Principe de base du codage convolutif
3.6.2 Représentation des codeurs convolutifs
3.6.2.1 Diagramme en arbre
3.6.2.2 Diagramme en treillis
3.6.2.3 Diagramme d'état..
3.6.3 Décodage des codes convolutifs
3.6.3.1 Algorithme de Viterbi..
3.6.3.2 Capacité de correction des codes convolutifs
3.7 Résumé

Chapitre 4 : Codage conjoint source-canal: quantification des sources sans mémoire
4.1 Codage conjoint par assignation d'indice
4.1.1 Principe de la méthode d'assignation d'indice
4.1.2 Critère d'erreur : formulations préliminaires
4.1.3 Assignation d'indice par permutation binaire
4.1.3.1 Principe de base ....
4.1.3.2 Formulation du critère d'erreur
4.1.3.3 Algorithme de permutation binaire
4.1.3.3.1 Etape d'initialisation
4.1.3.3.2 Etape de permutation et condition d'acceptation
4.1.3.3.3 Condition d’arrêt
4.1.3.4 Performance de l'IA par BSA
4.1.4 Assignation d'indice par recuit simulé
4.1.4.1 Optimisation combinatoire
4.1.4.2 Méthode du recuit simulé
4.1.4.2.1 Principe de simulation du recuit
4.1.4.2.2 Procédure de base du recuit simulé
4.1.4.3 Critère d'erreur approprié
4.1.4.4 Algorithme du recuit simulé
4.1.4.4.1 Etape d'initialisation
4.1.4.4.2 Procédure de Metropolis
4.1.4.4.3 Etape du recuit
4.1.4.4.4 Conditions d'arrêt
4.1.4.5 Simplification de l'algorithme du recuit simulé
4.1.4.6 Performance de l'IA par RS
4.2 Quantification vectorielle optimisée pour un canal bruité
4.2.1 Principe de conception d'un système à QVOC
4.2.2 Algorithme du système COVQ
4.2.3 Performances du système COVQ
4.2.3.1 Structure géométrique des dictionnaires COVQ
4.2.3.2 Performances du système COVQ
4.2.3.3 Evaluation comparative entre le COVQ et l'IA
4.3 Résumé

Chapitre 5 : Codage conjoint source-canal appliqué à la parole
5.1 Mesures de distorsion
5.1.1 Mesures objectives
5.1.2 Mesures subjectives
5.2 Prédiction linéaire
5.2.1 Estimation des coefficients LPC
5.2.1.1 Méthode d'autocorrélation
5.2.1.2 Méthode de covariance
5.2.2 Fréquences de raies spectrales
5.2.2.1 Calcul des paramètres LSF
5.2.2.2 Principales propriétés des paramètres LSF
5.3 Codage efficace des paramètres LSF: application de la technique OTCVQ
5.3.1 Conception du codeur LSF-OTCVQ
5.3.2 Performance du codeur LSF-OTCVQ
5.4 Codage efficace et robuste des paramètres LSF du standard fédéral FS1016
5.4.1 Robustesse du codeur LSF-OTCVQ: cas des transmissions par canal bruité
5.4.1.1 Conception du LSF-OTCVQ avec CCSC par QVOC
5.4.1.1 Performance du système de codage LSF-COTCVQ
5.4.2 Codeur LSF-COTCVQ avec codage de canal redondant
5.5 Résumé

Annexe A : Théorie de l'information pour codage de source discrète

A.1 Source discrète sans mémoire .... 167 A.2 Entropie d'une source discrète sans mémoire.... 168 A.3 Information mutuelle

A.3.1 Information mutuelle moyenne... 170 A.3.2 Entropies conjointe et conditionnelle 170 A.4 Codage sans perte d'une source discrète.... 171 A.5 Fonction distorsion-débit

Annexe B : Eléments de la théorie de conception des codeurs TCQ/TCVQ

B.1 Codage en treillis... 174 B.1.1 Quantification.. 175 B.1.2 Codage/Décodage ...... 175 B.2 Modulation Codée par Treillis . 176 B.2.1 Structure générale et principe de la TCM .. 177 B.2.2 Codeurs convolutionnels de la TCM 178 B.2.3 Partition d'ensemble de la TCM

Annexe C : Standard Fédéral FS1016 de 4.8 kbits/s

Bibliographie

Avant-propos

Les communications numériques constituent sans aucun doute l'une des plus importantes révolutions de la science et de la technologie. Propulsées par la théorie de l'information, fondée par C. E. Shannon en 1948, le monde des télécommunications ne cesse de basculer vers le numérique. Les radio-mobiles, le multimédia et les communications "globales" font partie maintenant de notre langage quotidien. La société devient de plus en plus complexe et les besoins de communication et de stockage s'accroissent rapidement. Cette croissance pousse les ingénieurs et les chercheurs à la mise en œuvre de techniques de compression de l'information de plus en plus performantes. Par exemple, il suffit de jeter un coup d'œil sur la réduction du débit atteint de nos jours par les codeurs de parole dans les systèmes radio-mobiles où en moins d'une décennie, les débits des codeurs ont été divisés par dix.

Cette course à la compression a été développée, d'une certaine façon, sur des modèles théoriques qui ne suivent pas de près les contraintes réelles au moment de la mise en œuvre des systèmes de transmission. En particulier, les codeurs de source sont souvent conçus sous l'hypothèse de transmission sans erreurs ou à travers des canaux non bruités. Or les performances prévues par ces codeurs se dégradent rapidement lorsqu'il s'agit de transmettre l'information de source à travers un canal réel qui est généralement bruité. Ainsi, dans tous les cas pratiques, la transmission à distance de l'information véhiculée par des signaux de nature quelconque est altérée par des phénomènes parasites tels que les bruits et les interférences. Ces phénomènes se traduisent généralement par une perte d'information. La minimisation de la dégradation des performances, causée par les bruits des canaux, est l'un des problèmes importants de la théorie des communications.

Un des résultats fondamentaux de la théorie de l'information a permis de trouver une solution à ce problème en assurant l'existence de schémas de codage de canal capables d'éliminer les effets néfastes des bruits des canaux de transmission. Selon l'approche établie par Shannon, le problème de codage de source et de canal peut être traité de façon complètement séparée et sans aucune perte d'optimalité à condition d'utiliser des blocs de code de tailles très grandes. Cette approche, connue généralement par "théorème de séparation de Shannon", stipule que dans la mesure d'utiliser des blocs de longueurs croissantes, il n'y aurait aucune perte d'optimalité en mettant en cascade un codeur de source optimisé pour une source donnée et un codeur de canal optimisé pour un canal donné. Afin d'obtenir une transmission efficace et fiable, cette approche séparatrice consiste donc à concevoir un schéma de codage de source capable de réduire au minimum la redondance de la source pour en rajouter de façon contrôlée sous la forme de codage de canal. Ces codes de canal, qui sont conçus d'une manière indépendante du codeur de source, peuvent fournir une bonne protection aux données sensibles aux erreurs du canal. Ils améliorent ainsi les performances de la transmission mais au prix de l'augmentation du débit de transmission et de la complexité du codage et/ou du décodage.

C'est ainsi que pendant plusieurs décennies, les concepteurs des codeurs de source et de canal ont travaillé indépendamment à la recherche de l'optimalité tantôt du côté de source comme du côté canal. La séparation des tâches suggérée par Shannon, a priori bénéfique puisqu'elle permet de décomposer un problème complexe en deux sous-problèmes plus simples, se transforme lentement en un grand problème lors de la mise en œuvre pratique. Ceci est dû principalement aux inconvénients des hypothèses posées dans le théorème de séparation de Shannon qui nécessitent des codeurs très complexes avec des blocs de traitement extrêmement longs, tant au niveau source que canal. En outre, les délais de traitement supposés illimités constituent un vrai problème pour les communications en temps réel. En effet, les considérations pratiques imposent souvent des contraintes sur la complexité, la disponibilité des ressources et les délais de codage. Si ces contraintes entrent en jeu, on ce voit donc forcé de faire des concessions tantôt du côté source, tantôt du côté canal. En quelque sorte, l'optimalité (ou la quasi optimalité) devra être sacrifiée. Ainsi, des systèmes très performants pour coder une source, mais qui imposent un délai de traitement trop important ou une mise en œuvre trop complexe, sont difficilement acceptés voire même rejetés.

Puisque les hypothèses de la conception séparée de Shannon ne sont pas toujours vérifiées en pratique, les chercheurs se sont demandé ainsi s'il existe une solution conjointe au problème d'optimisation des codages de source et de canal de sorte qu’on puisse réduire la complexité des deux côtés, tout en fournissant des performances proches de l’optimum. C’est dans ce contexte qu'ils ont introduit le dit codage conjoint source-canal, dans le quel on se préoccupe de la minimisation de la distorsion totale en considérant simultanément l'impact des erreurs de transmission et de la distorsion du codage de source. La principale motivation qui a poussée les chercheurs à penser au codage conjoint est que, malgré son optimalité prouvée, le codage séparé n'est pas nécessairement la meilleure solution en termes de simplicité. Actuellement, le codage combiné pour la compression des données de source et la protection contre le bruit des canaux est devenu l'un des objectifs essentiels dans la conception des systèmes de transmissions; particulièrement ceux conçus à base de quantificateur.

Cet ouvrage traite particulièrement les domaines de codage de source, de codage de canal et de codage conjoint source-canal (CCSC). Son objectif principal est de présenter en détails le concept de base et les approches du CCSC destiné à la protection implicite des paramètres des systèmes de transmission numériques contre les erreurs de canal. Il s'agit d'éclaircir la problématique du CCSC par rapport à la théorie conventionnelle de la conception source/canal séparée et de montrer, du point de vue théorique et pratique, comment faire intégrer au processus de codage de source les effets du bruit de canal. Des résultats expérimentaux, qui seront présentés tout au long de cet ouvrage, montreront que la cascade traditionnelle d'un codeur de source et d'un codeur de canal peut être remplacée efficacement par un seul bloc codeur source-canal optimisé conjointement.

Dans le passé, plusieurs approches de conception du CCSC ont été développées pour des transmissions de données fiables à travers un canal bruité. Ces approches sont généralement classées en plusieurs catégories dont les intersections sont possibles. Les techniques d'assignation d'indice et de quantification optimisée pour un canal bruité représentent les noyaux de base du CCSC et par conséquent un intérêt particulier a été porté à ces deux classes. L'assignation d'indice (IA) est une sorte de réallocation de bit plus appropriée pour une transmission robuste de séquences binaires source à travers un canal bruité. Dans ce livre, nous présentons deux méthodes de mise en œuvre de la technique d'IA. Il s'agit de la méthode de permutation binaire et de la méthode du recuit simulé. L’autre classe de base du CCSC est relative aux quantificateurs qui sont conçus en tenant compte de l’erreur du canal de transmission. Nous nous sommes intéressés particulièrement à la quantification vectorielle optimisée pour un canal bruité (QVOC). Cette méthode de codage, qui rend le codeur de source plus robuste, se base sur le principe d'optimisation de la quantification en prenant en considération les erreurs de transmission.

Dans un premier temps, les méthodes de CCSC conçues seront appliquées au codage efficace et robuste de sources sans mémoire. Par la suite, nous montrerons comment adapter et appliquer ces approches dans le domaine du codage de la parole à bas débit. En effet, à bas débit où les contraintes en complexité et en délais de traitement sont très sévères, le CCSC offre une alternative appréciable vu son efficacité prouvée dans la protection des données en maintenant un débit constant et une complexité réduite. On s'intéressera particulièrement au codage efficace et robuste des coefficients de prédiction linéaire (LPC) de parole en bande étroite représentés par les fréquences spectrales de raie LSF (Line Spectral Frequencies). En effet, les coefficients LPC jouent un rôle important dans la préservation de la qualité du signal de parole codé sur toute la largeur de bande. Par conséquent, le plus grand défi dans la quantification de ces coefficients est de réaliser un codage efficace avec un débit binaire minimal tout en maintenant la mémoire et la complexité des calculs à un niveau assez bas. Dans le dernier chapitre de cet ouvrage, nous présentons un système de codage optimal à quantification vectorielle codée par treillis développé pour le codage efficace et robuste des paramètres spectraux LSF de parole à bas débits.

Le contenu de ce livre provient de mes différents enseignements dispensés à la faculté d'électronique et d'informatique de l'université USTHB d'Alger. Il est basé aussi sur mes travaux de recherche réalisés au laboratoire de communication parlée et traitement du signal à la même université. Ce livre s'adresse aux chercheurs et ingénieurs travaillant dans le domaine des télécommunications. Il s'adresse aussi aux étudiants de second cycle des universités et écoles d'ingénieurs qui souhaiteraient se familiariser avec les techniques de codage de source et de canal séparé et/ou conjoint.

Ce livre est composé de cinq chapitres, complété par trois annexes.

Dans le chapitre 1, nous décrivons brièvement les fondements de base des systèmes de communication numériques. Nous exposons ensuite les principaux résultats théoriques de Shannon dans le domaine du codage de source et de canal. Après avoir identifié les inconvénients de la conception séparée de ces codages, nous introduisons l'idée de base du codage conjoint source-canal. Les approches de conception du codage conjoint seront ensuite présentées d'une manière sommaire.

Dans le chapitre 2, nous rappelons, tout d'abord, les outils de base fréquemment utilisés dans les systèmes de codage de source. Nous décrivons ensuite les méthodes de codage de source par quantification scalaire et vectorielle. Des algorithmes itératifs de conception seront développés pour réaliser des quantificateurs optimaux. Il s'agit de l'algorithme de Lloyd-Max pour la conception de quantificateurs scalaires optimaux ainsi que sa généralisation au cas vectoriel par l'algorithme LBG. Les étapes de conception de ces quantificateurs seront revues en détails et des résultats seront présentés dans le cas du codage de source sans mémoire. Par la suite, une description détaillée des étapes de conception des systèmes de codage à quantification scalaire/vectorielle codée par treillis (TCQ/TCVQ) sera donnée.

Le chapitre 3 est consacré au codage de canal redondant. Dans un premier temps, nous décrivons les concepts élémentaires du codage de canal. Nous présentons ensuite le modèle mathématique du canal de transmission où un intérêt particulier est porté au canal binaire discret sans mémoire. Par la suite, nous exposons les codes de canal qui sont classés en deux catégories: les codes en blocs et les codes convolutifs. Quelques codes en blocs populaires seront étudiés et implémentés. Il s’agit du code linéaire de Hamming et du code cyclique BCH. Nous terminerons ce chapitre par une présentation du codage convolutif.

Dans le chapitre 4, nous présentons des méthodes d'optimisation du CCSC appliquées au codage robuste de source sans mémoire. Nous exposons d'abord le principe du CCSC par la technique d'IA en donnant les formulations préliminaires de la distorsion des codages de source et de canal. Ces formulations de base seront utilisées dans les définitions des critères d'erreur qui doivent être minimisés dans les procédures de recherche des fonctions d'IA. Par la suite, nous décrivons en détails les méthodes de mise en œuvre de la technique d'IA que nous avons étudiées et implémentées : la permutation binaire et le recuit simulé. Des exemples de résultats de simulation montreront que les méthodes d'IA, appliquées au codage de sources sans mémoire, peuvent contribuer réellement à la protection implicite des systèmes à quantification vectorielle sans avoir recours au codage de canal redondant. La dernière partie de ce chapitre sera consacrée aux systèmes de codage par QVOC où nous exposons le principe de conception de ces systèmes ainsi que les formulations des conditions nécessaires d'optimalité dérivées pour un canal bruité. Les performances de la QVOC, appliquée au codage de sources sans mémoire, seront présentées en fin de paragraphe.

Dans le chapitre 5, nous montrons comment appliquer les méthodes du CCSC dans le domaine du codage de la parole à bas débit. L'étude sera consacrée particulièrement au codage efficace et robuste des coefficients LPC en bande étroite représentés par les paramètres de parole LSF. Au début, le système est développé pour réaliser un codage efficace des paramètres LSF dans le cas des transmissions à travers un canal idéal non-bruité. Il a été conçu à base du quantificateur vectoriel codé par treillis (OTCVQ) et appelé "codeur LSF-OTCVQ". Par la suite, nous appliquons le système LSF-OTCVQ (avec distance pondérée) pour coder les paramètres LSF d'un codeur de parole en bande étroite de la norme FS1016 (US Federal Standard FS1016) opérant à un débit de 4.8 Kbits/s. A des débits plus bas, les résultats des évaluations objective et subjective montreront que notre codeur incorporé peut assurer de meilleures performances comparé au quantificateur scalaire de 34 bits/trame, utilisé à l'origine dans la norme FS1016. Dans une étape ultérieure, nous nous sommes intéressés à l'amélioration de la robustesse de nos codeurs LSF-OTCVQ pour des transmissions réelles à travers un canal bruité. Pour protéger implicitement les indices de transmission des codeurs LSF-OTCVQ, incorporés dans le FS1016, nous avons développé un système de CCSC mis en œuvre par la technique QVOC. Dans le cas des transmissions par un canal bruité, nous montrerons que notre nouveau système de codage, nommé "codeur LSF-COTCVQ", pourra contribuer significativement à l'amélioration des performances du FS1016 en assurant une bonne protection implicite à ses paramètres spectraux LSF.

L'annexe A présente brièvement quelques éléments de base de la théorie de l'information, qui ont un lien direct avec le codage de sources discrètes sans mémoire. Dans l'annexe B, les techniques de codage de source en treillis et de la modulation codée par treillis (TCM) sont rappelées brièvement. Enfin, l'annexe C est consacrée à la présentation succincte du codeur de parole normalisé FS1016 de débit de 4.8 kbits/s.

Abréviations

illustration not visible in this excerpt

Notation

illustration not visible in this excerpt

Chapitre 1 Principe de base et approches du codage conjoint source-canal

Le codage de source (compression) est sensé réduire la redondance d'un signal, afin de diminuer la quantité de donnée à transmettre. D'autre part, le codage de canal rajoute de la redondance au signal pour le rendre plus robuste vis-à-vis des erreurs de transmission. Ces deux domaines sont, depuis des décennies, bien distincts : deux communautés différentes, avec chacune ses propres méthodes, problématiques, conférences et revues. Ainsi, les codeurs de source sont conçus pour un canal idéal (non bruité), alors que les codeurs de canal sont conçus pour réduire au minimum la probabilité moyenne de l'erreur de décodage indépendamment de la source réelle. Afin d'obtenir une transmission fiable de données, les codeurs et les décodeurs résultants sont cascadés comme suggéré par le principe de séparation de Shannon dans sa théorie de l'information. Cependant, avec les contraintes de stockage et de délais de traitement, une conception indépendante du codeur de source et du codeur de canal n’est pas forcement optimale A cet effet, on peut se demander si en faisant les deux actions conjointement, on pourrait en tirer profits. La principale motivation qui a poussée les chercheurs à penser au codage conjoint est que, malgré son optimalité prouvée, le codage séparé n'est pas nécessairement la meilleure solution en termes de simplicité.

Dans ce chapitre, nous décrivons d'abord le principe de base des systèmes de transmission en présentant le modèle classique d'un système de communication numérique. Nous exposerons ensuite les principaux résultats théoriques de Shannon dans le domaine du codage. Après avoir identifié les inconvénients de la conception séparée des codages de source et de canal (c.-à-d., théorème de séparation de Shannon), nous introduirons l'idée de base du codage conjoint sourcecanal. Les approches de conception du codage source-canal conjoint, qui sont généralement classées en plusieurs catégories, seront présentées d'une manière sommaire.

1.1 Système de communication numérique

Le but principal d'un système de communication est de transférer l'information de la source vers un utilisateur (destinataire) à travers un canal de transmission. En général, un système de transmission numérique est représenté par le modèle de base suivant :

illustration not visible in this excerpt

Figure 1.1 : Modèle classique d'un système de communication numérique

Ce modèle (appelé aussi en théorie d'information par paradigme de Shannon) utilise un codeur de source et un codeur de canal complètement indépendants. La figure 1.1 fait apparaître les éléments de base d'un système de communication numérique [1 3] :

Source: tout organe ou dispositif qui produit des signaux numériques constitués de séquences de symboles (bits ou échantillons, par exemple) discrets prenant leurs valeurs dans un alphabet fini. Dans le cas ou la source produit des signaux analogiques (audio, vidéo,...), ces derniers sont convertis en séquence de digits binaire (bits).

- Codeur / Décodeur de source: le codeur de source transforme la sortie de la source en une séquence binaire, contenant des "0" et des "1". Il assigne à chaque bloc de source x de m symboles un indice binaire i représenté sur k bits. Ces indices sont généralement de tailles fixes. Basé sur les règles du codeur de source, le décodeur de source convertit la sortie binaire (indices i ˆ ) du décodeur de canal en une séquence de représentants de m symboles chacun. Dans le cas idéal (canal non bruité), cette séquence est identique à celle générée à la sortie de la source.

- Codeur / Décodeur de canal: le but du codage de canal est d'assurer une communication protégée contre les erreurs de transmission. Selon certaines règles, le codeur de canal transforme la séquence de sortie du codeur de source en une séquence binaire, généralement plus longue. Cette transformation, connue sous le nom de codage de canal, s'effectue en assignant à chaque indice i de k bits un code de canal ou mot-code ic plus long de n bits. Les mots-code sont ensuite émis dans le canal de transmission. A la réception, le décodeur de canal transforme la séquence binaire reçue (généralement différente de celle transmise au canal) en une séquence d'information plus proche de la séquence émise au codeur de canal. Selon les lois du codeur de canal, le décodeur effectue une opération de détection et/ou de correction des erreurs et produit une

- estimation des mots-code transmis au canal. Il récupère ainsi, à partir des mots-code reçus i ˆ c , les indices i ˆ des représentants x ˆ de m symboles que le décodeur de source fournit au destinataire. Lors du décodage, l'indice i ˆ est supposé égal à l'indice i avec une certaine probabilité d'erreur Pe.

Canal de transmission: le canal est un milieu physique, qui assure le lien électrique entre la source et le destinataire. Ce milieu, qui est lié à la nature de l'onde de propagation, est souvent sujet à variété de perturbations aléatoires. Ces perturbations sont généralement issues du milieu de transmission, des équipements électroniques ou des interférences provenant des autres utilisateurs.

- Afin d'éviter toute confusion avec la définition physique du canal de transmission, le mot canal dans cet ouvrage signifie le modèle mathématique du canal situé entre l'émetteur et le récepteur. Ce modèle est généralement décrit par son impact sur l'entrée qui est défini par la probabilité d'erreur (Pe) de transmission, taux d'erreur par bit BER (bit error rate) ou encore par la probabilité conditionnelle (notée P (j / i) ) de recevoir l'indice j sachant que l'indice i a été transmis.

- Destinataire: c'est la personne ou l'appareil qui va exploiter l'information reçue.

Il est important de noter que les descriptions de la figure 1.1 sont très simplifiées; celle du codage de source peut inclure une transformée, une quantification

(scalaire ou vectorielle) et/ou un codeur entropique [4 6]. Par ailleurs, le modèle du canal peut prendre en compte, outre les caractéristiques de la transmission, tout ou une partie des organes d’émission et de réception. Il peut inclure aussi d'autres blocs comme la modulation, etc.

1.2 Fondements de base du codage conjoint source-canal

Dans tous les systèmes de communication numérique, les caractéristiques de conception doivent répondre aux trois conditions suivantes: l'efficacité, la fiabilité et la sûreté. Dans ce livre, on s'intéressera uniquement à l'efficacité et à la fiabilité. La sûreté est importante dans les applications militaires, politiques et autres où l'aspect de sécurité est en jeu.

L'efficacité de la transmission se traduit par l'utilisation la plus restreinte possible des ressources pour émettre un signal. C'est-à-dire, par l'utilisation de peu de bits ou par l'occupation d'une bande de fréquence étroite. Il s'agit donc de minimiser le nombre de bits à transmettre tout en assurant une certaine qualité requise pour le signal à émettre. Les techniques permettant cela sont appelées codage de source.

D'autre part, une transmission fiable est une transmission qui garantit, d'une certaine façon, l'exactitude du signal reconstruit. En général, la contrepartie est une hausse de débit qui va à l'encontre du codage de source. Les techniques permettant d'augmenter la fiabilité de transmission sont communément nommées codage de canal.

Grâce à sa théorie de l'information⁷, Shannon a prouvé l'existence d'une solution optimale pour transmettre un signal donné sur un canal donné en concevant d'une manière séparée le codeur de source et le codeur de canal. Cette approche est souvent désignée par codage source canal en tandem, car l’on conçoit d’abord le codeur de source afin d’atteindre la meilleure performance (débit-distorsion) et seulement après on ajoute un codeur de canal suffisamment performant pour corriger presque toutes les erreurs.

1.2.1 Principaux théorèmes de codage de Shannon

Shannon, dans ses travaux, a donné les limites théorique possibles, tant pour le codage de source [7, 8] que pour le codage de canal⁷.

Son théorème du codage de source affirme qu’il existe un débit binaire R * s (limite théorique R (D)² ), vers lequel on peut tendre, mais en deçà duquel on ne peut comprimer davantage une source d’information. En d’autres termes, il existe un codeur de source dont le débit de source approche arbitrairement la limite R (D) [9, 10] pour une distorsion donnée D, en supposant que le canal est idéal (absence de bruit).

Celui du codage de canal stipule qu'il est possible d'avoir une transmission fiable à travers un canal bruité à condition qu'un certain débit binaire R * c appelé capacit é du canal ne soit pas dépassé. En général, la capacité d’un canal, notée C, représente la quantité maximale d’information que l’on peut transmettre à travers celui-ci. Ainsi, tant que le débit de codage de canal reste inférieur à la capacité du canal (cf. chapitre 3), alors il est toujours possible d'effectué des transmissions avec une probabilité d'erreur de codage arbitrairement faible.

Suivant les notations du modèle du système de communication (figure 1.1), les débits des codages de source et de canal sont, respectivement,

illustration not visible in this excerpt

Les premier et deuxième théorèmes de Shannon affirment donc la possibilité d'une transmission efficace et fiable à condition que: Rs R*s = R(D) et que Rc R*c = C.

Dans ces deux théorèmes, le prix à payer pour s’approcher du débit limite est l’utilisation de blocs de traitement de taille de plus en plus longue, tendant vers l’infini (k, m et n) lorsqu’on s’approche de la limite théorique⁷.

L’un des objectifs poursuivis en télécommunications est d’augmenter la qualité du signal reconstitué en réception, pour un canal et un niveau de bruit donnés. Pour répondre à cet objectif, Shannon suggère, dans un troisième théorème, de concevoir indépendamment les codeurs de source et de canal. Ce troisième théorème de codage de source et de canal est connu généralement par le "théorème de séparation de Shannon". Il stipule que dans la mesure d'utiliser des blocs de longueurs croissantes, il n y'aurait aucune perte d'optimalité en mettant en cascade un codeur de source optimisé pour une source donnée (indépendamment du codeur de canal) et un codeur de canal optimisé pour un canal sans-mémoire (indépendamment du codeur de source). En quelque sorte, ce théorème combine les deux premiers théorèmes en affirmant qu’on peut tendre vers une limite théorique de débit source et canal avec un système où les codages de source et de canal sont s é par é s. Cette approche consiste donc à concevoir séparément les codeurs de source et de canal afin d’atteindre les bornes de débit-distorsion R (D) (pour le codeur de source) et de capacité C (pour le codeur de canal).

Ceci conduit vers la conception d'un codeur à débit global minimal si ces bornes sont atteintes. Afin de comprendre ce théorème, définissons le débit global de transmission par :

illustration not visible in this excerpt

Dans le domaine du codage, le but visé est de transmettre l’information avec un débit globale R minimisé. Cette minimisation du débit global, sous la contrainte d’une distorsion D, revient en effet à minimiser le nombre de symboles envoyés sur le canal pour transmettre l’information avec une distorsion D. Selon les conditions combinées du premier et du deuxième théorème de Shannon, on peut montrer que:

R R (D) /C (1.4)

Cette inégalité représente une borne inférieure sur le débit globale R. Il existe donc un débit théorique en dessous duquel on ne peut transmettre l’information avec une même distorsion. Cette limite représente généralement les performances optimales théoriquement atteignables. Shannon, dans son théorème de séparation, montre que cette limite théorique est valable pour tout type de codeur et de décodeur, même pour le codeur combiné (encadré en pointillés sur la figure

1.1). Ceci nous donne en quelque sorte la borne en d é bit pour le codage conjoint source-canal. Il est alors clair que l’on peut, théoriquement en tout cas, tendre vers cette borne de la manière suivante :

Le codeur de source, quitte à ce qu’il soit très complexe, garantit un débit Rs aussi proche que l’on veut de sa borne R*s = R (D) pour une distorsion D donnée.

Le codeur de canal, quitte à ce qu’il soit très complexe, impose une fiabilité de transmission presque parfaite (Pe 0), tout en garantissant un débit Rc aussi proche que l’on veut de sa borne R*c = C.

De cette façon, on obtient bien un débit global proche de la limite théorique de Shannon : R R (D) /C, avec une distorsion totale D. Ceci constitue le théorème du codage séparé de Shannon qui fournit une solution globalement optimale au problème de codage. Cette solution peut être effectuée en deux étapes: concevoir d'abord le codeur de source afin d’atteindre la meilleure performance débit-distorsion (borne R (D)) et seulement après ajouter un codeur de canal suffisamment performant pour corriger toutes les erreurs (probabilité d'erreur idéalement nulle). Cette approche peut être aussi effectuée d'une manière inverse où l’on s'intéresse d’abord à une protection quasi-parfaite (codage de canal) qui permet de supprimer littéralement toutes les erreurs produites par le canal et ensuite une compression (codage de source) au débit que l'on peut se permettre, après avoir attribué les bits nécessaires à la protection.

1.2.2 Problématique du codage conjoint source-canal

Bien que le codage source et canal séparé soit entré dans les moeurs, comme en témoigne la séparation que l’on observe entre les deux domaines, cependant il présente plusieurs inconvénients dans la pratique. Le codage classique en tandem, décrit précédemment, conduit à un système de communication optimal. Mais, dans la pratique, bien des points ne sont pas aussi simples à réaliser. Ainsi, il ne faut pas se laisser tromper par une simple lecture de ce théorème de séparation de Shannon dont les résultats sont vrais sous les hypothèses asymptotiques de codage parfait, qui ne sont pas toujours vérifiées dans la pratique. En effet, dans l'absence des suppositions de Shannon (c.-à-d., blocs de code très larges) il n y'aurait aucune justification théorique pour la séparation des codeurs de source et de canal.

La toute première difficulté réside dans la condition du théorème de séparation sur les codeurs de source et de canal, à savoir que les bornes R (D) et C soient atteintes. D’une part, ce théorème prouve l'existence d'une solution optimale dont l'obtention est possible de façon séparée, mais ne la fournit pas. C'est-à-dire, il ne propose aucune construction permettant de concevoir les codeurs de source et de canal et ne précise pas si cette solution optimale est facile à réaliser pratiquement. D’autre part, ce théorème ne considère pas la faisabilité de ces codeurs. Aucune contrainte n’est en effet supposée sur les longueurs des codes en bloc utilisés. Autrement dit, une telle solution peut nécessiter une complexité prohibitive. Les longueurs des blocs peuvent donc croître indéfiniment et par conséquent engendrer un délai de transmission ainsi qu’une complexité des codeurs et des décodeurs inacceptables dans la pratique. En outre, les modèles de communication utilisés dans les théorèmes de Shannon ne sont pas paramétriques. Chaque bloc de la figure (1.1) est en effet considéré comme une relation arbitraire entre l'entrée et la sortie, généralement représentée par une distribution de probabilité conditionnelle continue ou discrète. Ce qui conduit vers un modèle difficile à manipuler et à optimiser. En pratique, on préfère généralement travailler avec des modèles paramétriques [11, 12] plus aisés à concevoir et à optimiser. Enfin, le canal est supposé connu parfaitement. Or, dans la pratique, le modèle de canal ne correspond jamais parfaitement à la réalité car les caractéristiques du canal sont généralement variables. En plus, dans certains cas, le modèle conçu est trop complexe pour être utilisé. Dans les deux cas, ceci limite une fois de plus les performances ultimes du codeur.

Ceci constitue les principaux inconvénients de cette théorie de conception séparée des codeurs de source et de canal, qui sont plus détaillés dans¹³ et¹⁴. Puisque d séparé est la seule méthode permettant d'atteindre la solution optimale, alors, on peut logiquement se demander s’il est possible de combiner les codeurs de source et de canal de sorte qu’on puisse réduire la complexité des deux côtés, tout en fournissant des performances proches de l’optimum. C’est dans ce contexte que certains chercheurs ont introduits le dit codage conjoint source-canal, dans le quel on se préoccupe de la minimisation de la distorsion totale en considérant simultanément l'impact des erreurs de transmission et du codage de source sur cette distorsion. En général, les techniques du codage conjoint source-canal (que dénotons par CCSC) n'utilisent pas de bits de redondance. Par conséquent, ils n'induisent aucune augmentation du débit de transmission.

L'origine de la problématique du CCSC remonte vers les toutes premières questions qui ont été posées à propos des avantages et des inconvénients de combiner les fonctions de codage de source et de codage de canal dans une seule unité dite conjointe. Aussi, pour quelles hypothèses et dans quel contexte cette approche peut-elle nous apporter des solutions ?

Nous essayerons dans ce livre de répondre à ce genre de question en montrant comment faire intégrer au processus d'optimisation du codage de source les effets du bruit de canal. Un tel codage qui semble contradictoire avec la philosophie de Shannon, est t-il capable de s’approcher de la borne optimale ? La réponse est oui, comme le montre ces deux petits exemples tirés de [15, 16], que nous présentons ici très brièvement :

Considérons une source binaire symétrique sans mémoire BSS (Binary Symmetric Source) à

transmettre à travers un canal binaire symétrique sans mémoire BSC³ (Binary Symmetric Channel), avec un débit global R = 1. Pour ce type de source, la mesure de distorsion D est donnée par le nombre moyen d’erreurs par bit. La fonction débit-distorsion source est donnée par R*s = R (D) = 1 H 2(D) où H 2(x) = x log2(1/ x) + (1 x) log2(1/1 x) est la fonction d’entropie binaire [17, 18]. Supposons que la probabilité d'erreur par bit du BSC est égale à p, alors sa capacité est R*c = C = 1 H 2(p). Selon la formule (1.4), la limite de Shannon est donnée par l’inégalité :

Rs 1 H 2 (D)

Rc 1 H 2 (p)

R 1, (1.5)

Pour approcher de cette limite, Shannon préconise des codeurs de source et de canal "optimaux" réalisant Rs 1 H 2(D), pour D = p et Rc 1 H 2(p). Cependant une solution évidente consiste simplement à ne faire ni codage de source, ni codage canal (cf. figure 1.1 en éliminant les blocs encadrés en pointillés). On a alors une distorsion totale qui est uniquement due au canal D = p: la limite de Shannon est alors atteinte. Du point de vu complexité, une solution optimale consiste donc à ne faire aucun codage. On ne peut pas imaginer un système plus simple pour R = 1 !

Prenons l'autre exemple de transmission numérique d'une source gaussienne sans mémoire de variance x 2. Supposons que la transmission s'effectue à travers un canal gaussien (qui ajoute un bruit gaussien de variance b 2) et que le débit global est toujours R = 1. Pour une mesure de distorsion de type quadratique, on a alors [15, 17] : R*s = R (D) = 1/2 log2(s) où s= x 2/ D est le rapport signal source sur bruit et R*c = 1/2 log2(1 + c), où c = u 2/ b 2 est le rapport canal sur bruit (u: entrée du canal) . Dans ce cas, la limite de Shannon est donnée par:

illustration not visible in this excerpt

Figure 1.2 : Système de codage source-canal optimal (R = 1) pour source gaussienne.

Les grandeurs et sont des coefficients (gains) d'amplification obtenus par minimisation de

l'expression de la distorsion totale quadratique D:

illustration not visible in this excerpt

Il est facile de vérifier que la limite de Shannon est, là aussi, atteinte par le schéma de la figure

1.2:

illustration not visible in this excerpt

Notons que ces deux exemples, bien que provocants, ne contredisent pas, en fait, les énoncés des théorèmes de Shannon. Ils montrent cependant que l’approche classique (système séparé) n'est pas la seule solution envisageable à l’optimum. D'autres solutions plus simples, notamment celles impliquant un codage conjoint, peuvent réduire la complexité du système global, tout en maintenant un niveau de performance optimale ou proche de l'optimum.

Pour conclure, si l'on pouvait se permettre de prendre des systèmes très complexes, le théorème de séparation de Shannon serait là pour nous donner la solution optimale ! Puisque ce n'est pas toujours le cas, l'utilisation du CCSC ne prend sens que pour satisfaire un objectif très important qui est la simplicité.

1.3 Prémices du codage conjoint source-canal

Plusieurs chercheurs avaient déjà remarqué que se préoccuper de l’impact des erreurs de transmission sur la distorsion totale améliorait l’efficacité globale du système. Ces préoccupations sont apparues de manières sensiblement différentes suivant que les chercheurs étaient du domaine "codage de source" ou "codage de canal ". Bien entendu, les chercheurs dans ce domaine n'ont pas annoncés qu'il est possible d’atteindre la limite de Shannon. Par contre, il semble qu’un système traditionnel (source et canal optimisés séparément) peut s’éloigner très vite de la limite quand le taux d’erreurs augmente, en particulier à cause de contraintes pratiques.

Une première préoccupation était le réglage du codeur de source de sorte que les erreurs de transmission soient moins néfastes au décodage. Par ailleurs, on peut aussi équilibrer les rendements des codeurs de source et de canal afin de prendre en compte les contraintes du système. Ces premiers procédés sont décrits ici très succinctement.

1.3.1 Protection inégale des données source

Les premières idées été de régler les codeurs de source de telle manière que les éventuelles erreurs de transmission aient un impact moins néfaste au décodage, sans forcément utiliser les techniques de codage de canal. Une telle stratégie peut être mise en œuvre dans un contexte hiérarchique, où différents éléments transmis par le codeur de source n’ont pas le même impact dans la reconstitution de la source. En effet, certains éléments contribuent plus que d'autres dans la qualité de reconstitution, mais, en revanche, ils sont plus sensibles aux erreurs de canal. Une idée évidente est de protéger ces éléments "importants" par de meilleurs codes de canal tandis que les éléments "moins importants" sont protégés par de faibles codes de canal. Ce concept est généralement connu sous le nom de protection inégale contre les erreurs de transmission UEP (Unequal Error Protection), où les codeurs de canal prévoient des protections inégales des différents constituants du train binaire émis par le codeur de source.

La protection inégale UEP est considérée parmi les techniques les plus simples et les plus efficaces dans le CCSC. Cette stratégie a été largement utilisée par la suite dans la mise en œuvre de systèmes CCSC; un état de l'art est donné dans¹⁹.

1.3.2 Equilibrage des débits

Il a été observé que la stratégie traditionnelle, consistant à comprimer au maximum la source pour un niveau de distorsion donné, n’améliore pas toujours les performances du système global. Ceci parce qu’elle rend plus sensible le train binaire aux erreurs de transmission. Pour compenser cet effet, il faudrait alors bien protéger le train binaire issu du codeur de source par ajout d'un codeur de canal sophistiqué qui corrige toutes les erreurs de transmission. Cette stratégie n'est pas toujours pratique vu les contraintes de complexité et de délais.

Une meilleure stratégie consiste plutôt à effectuer un équilibrage a posteriori du débit entre les codeurs de source et de canal afin de trouver un point de fonctionnement compatible avec l’application visée. C'est-à-dire, obtenir une meilleure qualité du signal reconstruit pour un canal donné sans augmentation de la largeur de bande. L'idée de base consiste à optimiser séparément les codeurs de source et de canal en effectuant un compromis entre les débits de source et de canal de sorte que les performances du système global soient améliorées dans le cas des transmissions bruitées. Pour un débit de transmission fixe, les performances du codeur global opérant à travers un canal bruité pourront être améliorées en réduisant le débit de source Rs et en augmentant le débit de canal Rc dans la même proportion ou bien l'inverse. En effet, il a été confirmé un peu plus tard dans²⁰ que plus de bits devraient être alloués au codage de canal pour lutter contre les bruits des canaux de faibles SNR. Inversement, plus de bits devraient être alloués au codage de source pour augmenter le débit de transmission de données dans le cas des canaux à SNR élevé en raison des meilleures conditions de canal.

Un réglage conjoint des débits des codeurs de source et de canal peut s’avérer donc utile. Par contre, une meilleure stratégie consisterait à obtenir cet équilibrage entre codeurs de source et de canal par une véritable conception conjointe.

1.4 Approches du codage conjoint source-canal

Selon le modèle de transmission considéré, plusieurs approches du CCSC ont été proposées dans la littérature. Ces techniques de codage conjoint sont généralement classées en quatre catégories conventionnelles, dont les intersections sont possibles. Dans cette partie, nous passerons en revue ces différentes techniques, sans pour autant être exhaustif. Les classes décrites en sous-sections 1.4.1 et 1.4.2, à savoir les techniques d'assignation d'indice et de quantification optimisée pour un canal bruité, présentent un intérêt particulier. En effet, ces deux classes représentent les noyaux de base du CCSC et que les autres catégories ne sont généralement que des dérivations améliorées de ces deux classes.

Mais avant, nous allons reprendre le schéma bloc conventionnel d'un système de transmission numérique en essayant de lui donner une représentation un peu plus générale (figure 1.3).

Sans revoir les blocs définis précédemment, le message de source selon ce modèle passe d'abord par un bloc de transformation afin d'obtenir une séquence de source discrète x. Les techniques de transformation (très utilisées pour les signaux audio et images) ont pour fonction essentielles de chercher à décorréler le signal avant la quantification et à concentrer la puissance du signal dans un nombre réduit de composantes pour lesquelles on réservera une grande partie des ressources binaires disponibles. Une quantification de source est effectuée ensuite afin d’éliminer la redondance; suivie par une assignation d'indice (IA) dont l'objective est d'obtenir une allocation de bit plus appropriée pour une transmission plus fiable à travers un canal bruité. La source codée résultante est ensuite protégée par un codage de canal redondant. Le modulateur transforme les mots-code en formes d'ondes électriques convenables pour une transmission à

illustration not visible in this excerpt

Figure 1.3 : Schéma général d'un système de transmission numérique

travers un canal physique. Un bruit de canal s'ajoute généralement au signal transmis et déforme ainsi une partie des symboles émis. A la réception, les opérations inverses suivantes sont effectuées: décodage de canal, IA inverse, quantification inverse et transformation inverse; afin de retrouver le message original.

Notons que ce modèle général d'une chaine de transmission numérique pourrait être simplifié selon différentes manières. En effet, chaque méthode de conception du CCSC, décrite ci-dessous, utilise ses propres suppositions sur le modèle de transmission et combine quelques blocs de la figure 1.3 en un seul bloc et/ou omet simplement quelques blocs. Ainsi, suivant le modèle de transmission supposé, plusieurs approches peuvent être suivies pour le CCSC. L'état de l'art de ces approches est donné dans ce qui suit.

1.4.1 Assignation d'indice

Une approche de base du CCSC est l'assignation d'indice "IA" (index assignment). Ce genre de technique trouve son intérêt dans le cas où la source est codée par un système à quantification déjà conçu et optimisé selon des suppositions de transmissions idéales (canal non bruité) [21 23]. A l'origine, la technique d'IA est utilisée sans ajout de bits de redondance; par conséquent, les blocs codage/décodage de canal redondant sont éliminés de la chaîne de transmission. Ainsi, cette technique présente l'avantage de n'induire aucune augmentation du débit de transmission. D’où l'intérêt particulier de l'IA lorsqu'il s'agit de protéger les indices d'un quantificateur de source contre d'éventuelles erreurs de canal, tout en maintenant la transmission à un débit fixe.

L'idée, intuitive, de base de la technique d'IA est d'assigner des mots-code binaires, b (i), aux indices des représentants (i) d'un système de codage à quantification afin de réduire la distorsion due au bruit du canal. Dans le cas des transmissions bruitées, plusieurs travaux ont montré que la technique d'IA peut fournir une bonne robustesse contre les erreurs de canal, sans induire ni une augmentation du débit de codage ni une complexité de codage ou de décodage [21 26]. Elle présente aussi l'avantage de n'induire aucune dégradation des performances dans le cas d'absence du bruit de canal. Ainsi, la distorsion due au bruit de canal peut être considérablement réduite par un arrangement judicieux des indices des représentants du quantificateur tel que l'indice bruité engendre un décodage d'un représentant incorrect qui s'approchera en moyenne de l'original.

Une solution générale au problème d'IA est de concevoir d'abord le quantificateur de source optimal et ensuite retrouver l'IA optimale aux représentants du quantificateur de telle sorte que les représentants résultants après assignation deviennent plus robustes contre le bruit du canal. Par conséquent, le choix de la méthode de conception du codeur de source (quantificateur) optimal est de prime dans ce genre d'application. La recherche de la meilleure IA est un travail fastidieux qui demande une complexité de calcul énorme vu la nature combinatoire du problème. Des techniques sous-optimales sont ainsi employées pour résoudre ce type de problème. Ces techniques se basent généralement sur le principe de la minimisation d'un critère d'erreur qui doit être développé selon les suppositions de transmission.

Plusieurs chercheurs se sont intéressés à la résolution du problème d'IA dans différentes applications où des méthodes heuristiques ont été développées assurant des solutions localement ou globalement optimales [21 26]. Dans le chapitre 4, nous présenterons deux méthodes de mise en œuvre de la technique d'IA. Il s'agit de la méthode de permutation binaire "BSA" (Binary Switching Algorithm)²¹ et la méthode du recuit simulé "RS" [27, 28] qui seront développées et appliquées au codage de sources sans mémoire.

Précisant enfin, que dans cette classe, un codeur de canal supplémentaire peut être après inséré avec le bloc d'IA afin de renforcer davantage la protection et obtenir des performances additionnelles. Ceci étant effectué à condition que l'augmentation du débit et de la complexité soit autorisée.

1.4.2 Quantification optimisée pour un canal bruité

Dans cette deuxième approche de base se trouvent les schémas de codage dans lesquels le codeur de source est modifié afin de tenir compte des erreurs de canal. Ainsi, les opérations de codages de source et de canal sont intégrées dans une seule entité. L'intérêt principal de cette classe (connue aussi par codage conjoint avec contraintes) est la conception de système de codage à quantification optimisée pour des transmissions par canal bruité.

Les techniques de cette classe de CCSC conçoivent le quantificateur de source en tenant compte du bruit présent sur le canal de transmission. Le but est alors de minimiser la distorsion moyenne totale entre le signal reconstitué et le signal original, étant donné ce bruit. Par conséquent, l'objectif de ces systèmes n'est pas la correction explicite des erreurs de transmission mais plutôt la diminution de l'impact de ces erreurs dans la reconstitution de la source. Le problème de conception de ce genre de quantificateur réside dans la détermination des conditions d'optimalité nécessaires pour minimiser une distorsion totale modifiée. Cette dernière est formulée en considérant ensemble la distorsion due à la quantification et aux erreurs de canal. Les techniques de quantification optimisée pour un canal bruité sont les méthodes de base de cette classe. Un codage de canal supplémentaire reste toujours possible comme évoqué dans la classe précédente.

Dans le cas scalaire, Farvardin et Vaishampayan ²⁹ ont proposé une technique de quantification scalaire optimisée pour un canal bruité (QSOC). Ils ont formulé les conditions nécessaires pour un quantificateur scalaire optimal à travers un canal bruité et ont proposé un algorithme itératif qui fournit des solutions localement optimales. Une observation intéressante faite dans²⁹ est l'existence d'une protection implicite dans la QSOC.

Dans le cas vectoriel, plusieurs chercheurs ont considéré la conception de systemes de codage à quantification vectorielle optimisée pour un canal bruité (QVOC). Ce genre de quantificateur peut être conçu par une version étendue au cas bruité de l'algorithme LBG³⁰ conventionnel de la quantification vectorielle. Les conditions d'optimalité de la QVOC sont discutées dans [31, 32]. C'est en effet une généralisation de la même méthodologie utilisée dans²⁹ pour concevoir un quantificateur scalaire optimal pour canal bruité. Farvardin et Vaishampayan ont plus tard étudié en détails la QVOC et ont dérivé sa complexité et ses performances³³. En donnant des exemples d'application, ils ont montré que la QVOC apporte aussi un codage de canal implicite dû à la disparition de quelques régions d'encodage créant ainsi des régions vides.

La méthode de conception du codeur à QVOC ainsi que les differentes formulations seront détaillées au chapitre 4. Nous montrerons que la QVOC peut être appliquée avec succès dans le codage robuste de sources sans mémoire ainsi que dans le domaine du codage la parole à bas débit (cf. chapitre 5).

1.4.3 Optimisation conjointe du quantificateur et de l'assignation d'indice

L'approche générale dans cette classe consiste en l'optimisation conjointe des deux blocs d'IA et du quantificateur. La figure 1.4 illustre le schéma bloc simplifié de la chaîne de transmission dans cette classe. Aussi, l'ajout d'un bloc de codage de canal reste toujours possible comme nous l'avons mentionné dans les classes précédentes.

illustration not visible in this excerpt

Figure 1.4: Schéma de CCSC basé sur l'optimisation conjointe du quantificateur et de l'IA

illustration not visible in this excerpt

Notons que cette classe peut être considérée comme une généralisation de la classe précédente en incluant l'IA dans le processus de codage. Ceci peut être facilement effectué en incluant l'IA b (.) dans la formule de la mesure de distorsion modifiée. A cet effet, on retrouve dans cette classe les systèmes de quantification optimisée pour un canal bruité tels la QSOC et la QVOC qui sont combinées avec l'IA. Il s'agit ici de minimiser la mesure de distorsion modifiée du quantificateur qui implique l'erreur de quantification, l'erreur due au bruit du canal et l'IA qui est insérée dans la formule de distorsion.

D'autres travaux peuvent être classés dans cette catégorie. En 1992, Knagenhjelm a proposé un algorithme récursif analogue à la QVOC dans le but d'obtenir des quantificateurs vectoriels robustes³⁴. Une année après, il a proposé une modification de la SOM (self organizing map) de Kohonen³⁵ afin d'obtenir un quantificateur vectoriel plus robuste³⁶. Rappelons que la SOM est un algorithme itératif de conception d'un quantificateur vectoriel qui garde une topologie similaire de l'espace d'entrée (signal) dans l'espace de codage³⁵. Dans³⁶, Knagenhjelm donne une autre description de ces méthodes sous le nom de "quantificateurs vectoriels de redondance-zéro" (zero-redundant vector quantizers). Il affirme que "il y a une tendance en cours vers l'usage de quantificateur vectoriel de redondance-z é ro o ù les bits additionnels utilis é s d'habitude pour le contr ô le d'erreur sont utilis é s plut ô t pour raffiner le quantificateur sans une protection explicite de l'erreur". Il a proposé une mesure de linéarité qui reflète comment un tel codage est linéaire, où il a déduit intuitivement qu'il devrait y avoir une correspondance entre l'espace du signal et l'espace Hamming. En d'autres termes, les mots-code qui sont proches, et de ce fait le plus fréquemment confondus (erronés), devrait représenter des vecteurs de reproduction proches dans l'espace du signal. Dans la même année, une approche similaire à celle de³⁶ a été proposée par Azami et al.³⁷. L'algorithme proposé suit la même idée de la SOM³⁵, avec la propriété spéciale que l'affectation (mapping) est définie dans un espace multidimensionnel, d'où vient le nom de "self organizing hyper cube" (SOHC). Cette technique est developpé avec un algorithme semblable à celui de la SOM de Kohonen avec certaines modifications³⁷.

Enfin, les lecteurs intéressés peuvent consulter les references de base [35 37] pour plus de details sur ces méthodes de conception.

1.4.4 Optimisation conjointe du quantificateur, de l'assignation d'indice et de la modulation

Dans cette classe de CCSC, le modulateur est inclut dans le processus de codage. Encore une fois, le nombre de blocs à optimiser conjointement a été augmenté. L'approche en général concerne non seulement l'optimisation du codage de source et de l'IA, mais aussi celle de la modulation. Des combinaisons entre deux ou trois blocs sont toujours possibles.

Plusieurs travaux peuvent être classés dans cette catégorie comme par exemple, l'optimisation conjointe du codeur de source, du codeur de canal et du modulateur proposé par Vaishampayan et Farvardin dans³⁸. Ils ont considéré le problème de conception des codes de source et d'ensembles de signaux de modulation sous contrainte d'énergie et de bande passante. Pour des décodeurs linéaires, ils ont dérivé les conditions nécessaires d'optimalité pour le codeur, le décodeur et l'ensemble des signaux de modulation et ont développé un algorithme itératif localement optimal qui résout ces conditions nécessaires.

Nous trouvons aussi dans cette classe, la MORVQ (modulation organized vector quantization) proposée par Skinnemoen dans sa thèse de Ph.D.³⁹. Cette méthode utilise un quantificateur qui affecte les vecteurs-code directement dans le plan de la constellation. Il fait un usage efficace de l'algorithme d'apprentissage de Kohonen pour affecter l'espace d'entrée multi-dimensionnel à l'espace signal à deux dimensions, de telle façon que les vecteurs-code proches dans l'espace de modulation sont assignés aux points voisins dans l'espace d'entrée.

Ainsi que d'autres travaux qui peuvent être aussi classés ici, dont nous citons quelques uns rapidement: la modulation hiérarchique⁴⁰, où les points de la constellation sont localisés pour minimiser l'erreur attendue; la modulation codée⁴¹ dans la quelle les blocs de codage de canal et de modulation sont optimisés conjointement.

1.5 Résumé

Dans ce chapitre, nous avons montré brièvement qu’une conception séparée d'un système de codage de source et de canal n'est pas la seule solution optimale. Une autre solution plus simple, impliquant un codage conjoint entre source et canal, peut maintenir un niveau de performance optimale ou proche de l'optimum avec une complexité réduite du système global. Ainsi, l'idée d'un système de codage conjoint ne prend sens que pour satisfaire un objectif très important qui est la simplicité de conception; car si l'on pouvait toujours se permettre d'utiliser des systèmes très complexes, la conception séparée serait là pour nous donner la solution optimale.

Nous avons aussi donné un bref aperçu des principales classes des systèmes de CCSC, où nous avons passé en revue les méthodes de base constituants chaque classe. L'assignation d'indice et la quantification optimisée pour un canal bruité représentent les deux premières classes de base du CCSC. Les autres classes citées ne sont généralement que des versions ou des dérivations améliorées de ces deux premières classes.

Notons, en fin, que d'autres travaux qui ont repris les travaux de base en leur ajoutant certaines améliorations ou en exploitant leurs idées de conception ont donnés naissance à de nouvelles sous-classes de CCSC. Dans¹⁴, une classification des techniques de CCSC a été proposée et qui n’est pas fonction du type de méthode utilisé, mais du contexte dans lequel de telles techniques peuvent être utilisées. Par ailleurs, d'autres systèmes de CCSC assez récents, qui ne sont pas classés dans les quatre principales catégories présentées ci-dessus, ont été développés. Plus de détails sur ces systèmes de CCSC sont donnés dans¹⁹.

Chapitre 2 Codage de Source : Quantification

Le codage de source sert à fournir une représentation "compacte" et efficace des données source tout en préservant l’information essentielle qu’elles portent. Le but est alors de minimiser au maximum les ressources nécessaires à la transmission des données (par exemple: le temps, la puissance, la bande passante, surface de stockage sur disque, …). En général, les méthodes de codage de source sont soit réversibles ou irréversibles. Dans la première catégorie, les messages originaux peuvent être exactement reconstitués après compression; on parle alors du codage sans perte d'information. Dans certaines situations pratiques où le but est d'obtenir un débit de transmission plus faible, la contrainte de reconstruction parfaite peut être supprimée. On accepte alors une certaine distorsion entre les messages originaux et leurs versions reconstituées. Il s'agit du codage irréversible, communément appelée codage avec perte d'information. Dans cet ouvrage, on s'intéressera particulièrement aux méthodes de codage de source avec perte. Ces méthodes sont généralement conçues par des techniques de quantification (scalaire ou vectorielle).

Dans ce chapitre, nous rappelons, tout d'abord, les outils de base fréquemment utilisés dans les systèmes de codage de source, sans pour autant revoir toutes les notions déjà évoquées au chapitre précèdent. Nous décrirons ensuite les méthodes de codage de source avec perte. Dans cette catégorie, nous nous intéresserons particulièrement aux systèmes de codage par quantification scalaire et vectorielle. Basé sur les conditions nécessaires d'optimalité, des algorithmes itératifs de conception ont été développés pour réaliser des quantificateurs (scalaires et vectoriels) optimaux. Il s'agit du célèbre algorithme de Lloyd-Max pour la conception de quantificateurs scalaires optimaux ainsi que sa généralisation au cas vectoriel par l'algorithme LBG. Les étapes de conception de tels quantificateurs sont revues en détails et des résultats de simulation sont présentés dans le cas du codage de source sans mémoire.

Par la suite, nous présentons deux méthodes de quantification structurée, à savoir la quantification vectorielle divisée et la quantification (scalaire/vectorielle) codée par treillis. Un intérêt particulier sera porté à la quantification par treillis.

2.1 Codage de Source

2.1.1 Définitions

Le codage de source (ou compression des données) vise à la concision maximale du message afin de minimiser les ressources nécessaires à la transmission. La théorie de l’information développée par Shannon⁷ fournit des idées fondamentales pour la conception d’un grand nombre de techniques de codage de source. Le schéma général d’un système de codage de source est présenté dans la figure suivante:

illustration not visible in this excerpt

Figure 2.1 : Schéma bloc d'un système de compression numérique.

Où x, i, j et x ˆ sont respectivement de longueur m, k, k et m. Il est supposé que k < m (c.-à-d., i plus "compacte" que x) et que i = j (canal idéal non bruité). Ainsi, le but du codage de source est de reproduire, à la réception, une nouvelle version du message x, notée x ˆ , en utilisant le moins de bits de transmission que possible.

Cette compression peut autoriser ou non la perte d'information. Ainsi, nous avons deux variétés de système de compression de donnée, que nous décrivons dans ce qui suit.

2.1.1.1 Codage de source sans perte

Dans le cas où les données reconstituées à la réception sont identiques aux données source originaux, on dit que le codage est sans perte d'information. Basé sur la stratégie de Shannon⁷, des techniques de codage sans perte d'information ont été conçues. La théorie annonce qu'un tel codage, connu généralement par codage entropique, est réalisable avec un débit binaire minimal proche de l'entropie H de la source. Rappelons que l'entropie de la source est une limite fondamentale du débit de codage au dessous de la quelle on ne peut pas décoder sans distorsion (voir Annexe A). Si pour des raisons diverses, on a besoin d'une réduction du débit plus faible que l'entropie, on sera alors obligé d'accepter une certaine distorsion.

Généralement, le taux de compression réalisé par un tel codage n’est pas suffisant pour la plupart des applications audio ou vidéo. Par ailleurs, pour ces dernières applications, la reconstruction exacte du signal de départ n’est pas indispensable.

2.1.1.2 Codage de source avec perte

Un codage de source est dit avec perte si les données reconstituées à la réception ne peuvent pas être identiques aux données source originales. Dans plusieurs applications, la contrainte de reconstruction parfaite peut être supprimée. On accepte alors une certaine distorsion entre l'original et le reconstruit dans le but d'obtenir un débit de transmission plus bas. Les techniques de codage avec perte les plus utilisées sont celles qui opèrent une quantification des données source. Les données reconstruites ne coïncident pas avec les données source mais sont approximativement proches de celles-ci. La plupart du temps le système obtenu avec ces techniques est à débit fixe. Dans cet ouvrage, nous nous intéresserons seulement aux méthodes de codage de source avec perte qui seront appliquées particulièrement dans les domaines du codage de sources sans mémoire et de la parole à bas débit.

2.1.2 Principe de base du codage de source

Le codage de source consiste à représenter un signal analogique par un signal de type numérique afin de le transmettre (ou de le stocker) avec une distorsion aussi faible que possible. En général, cette opération dite de numérisation est effectuée en deux étapes successives:

La première étape consiste à transformer le signal à temps continu x (t) en une suite d'échantillons x (n) par application d'une procédure d’échantillonnage. Si les hypothèses du théorème d'échantillonnage sont respectées [1, 17], il est alors possible de reconstituer exactement le signal analogique à partir de ces échantillons. La deuxième étape consiste à représenter les échantillons du signal source par des valeurs appartenant à un ensemble fini de taille fixe. Cette opération, dite de quantification, est suivie par une numérisation (ou codage) binaire. Il s'agit de traduire en suite binaire les valeurs de quantification choisies pour représenter les échantillons de source. Le codage de la parole est un exemple d'application fréquent de ce genre de technique où les échantillons du signal de parole reconstruit ne sont pas nécessairement identiques à ceux du signal émis. On peut tolérer un certain degré de distorsion et pourtant on comprend bien le signal reconstruit. Evidemment, la qualité de la reconstruction dépendra du débit de transmission utilisé. Intuitivement, plus le débit est faible plus grande sera la perte introduite dans le processus du codage. On est alors obligé de définir des mesures de distorsion d'un schéma de codage.

En général, il y a deux genres de mesure de distorsion: les mesures objectives qui sont des mesures purement mathématiques et les mesures subjectives qui évaluent la qualité du codage à base de perception humaine (audition pour les signaux audio, parole et vision pour les signaux vidéo, image). Dans certaines applications, des mesures subjectives perceptuelles doivent être réalisées sur le signal décodé pour établir la qualité du codeur de source. Mais du point de vue mathématique, il est très difficile de formuler de telles mesures de distorsion. Une façon assez intuitive d'analyser le décodage est effectuée par l'intermédiaire d'une mesure objective basée sur la différence entre le signal original et le signal reconstruit. Dans ce chapitre, nous considérons seulement les mesures objectives pour évaluer les performances des differentes conceptions qui seront présentées ulterieurement.

La reconstitution d'une séquence de source x par sa version quantifiée x ˆ engendre une distorsion définitive du signal de source. En général, la mesure de distorsion objective est définie par la distorsion moyenne entre le signal original et sa version reconstituée. Cette distorsion moyenne, notée par D, est définie par:

D E (d (x, x)), (2.1)

où E est la moyenne statistique et d (.,.) est une mesure de distance (erreur) entre x et x ˆ . On considère souvent que la mesure de distance est de type Euclidienne quadratique⁴. Selon certaines suppositions, cette distance peut s'écrire de la façon suivante :

illustration not visible in this excerpt

où k est la longueur des séquences x et ˆ .

En général, les méthodes de codage de source par quantification sont classées en deux principales catégories:

- La quantification scalaire,

- La quantification vectorielle.

2.2 Quantification scalaire

La quantification scalaire (QS) est une méthode de codage de source qui quantifie chaque échantillon de source indépendamment des autres. La QS [4, 5, 9] est une fonction de l'ensemble des réels vers un sous-ensemble, prédéterminé, Y. Elle assigne à une valeur d’entrée

(échantillon) x la valeur la plus proche de Y. D’où:

illustration not visible in this excerpt

Le sous-ensemble fini Y est communément appelé alphabet de sortie de taille L. Les L valeurs de sorties yi sont connues par plusieurs appellations: valeurs (ou niveaux) de sortie (ou de quantification) ou encore représentants.

Pour concevoir l'alphabet de sortie, le quantificateur scalaire (SQ: scalar quantizer) partitionne l'espace d'entrée réel x en L intervalles ou classes Ri et associe à chaque classe i un représentant yi. Chaque valeur scalaire d'entrée x appartenant à la classe Ri sera donc représentée par le niveau de quantification yi associé. D'où :

illustration not visible in this excerpt

En général, le nombre des valeurs de sortie est choisi comme puissance de 2; soit L = 2 b. Pour un débit fixe, chaque valeur quantifiée peut être donc représentée par un mot-code de b bits. Le débit du SQ, qui représente le nombre de bits utilisé par échantillon, est donné par :

R = log2(L) (bits/échantillon) (2.5)

2.2.1 Principe de codage par quantification scalaire

La procédure de codage par un SQ consiste à chercher à quel intervalle appartient l'entrée x puis à lui associé un indice i {0, , L 1} du niveau sélectionné yi. Le codeur transmet ensuite la version binaire de l'indice i et non pas la valeur réelle de yi. C'est à ce niveau que la compression des données est produite. A la réception, le décodeur, qui possède un alphabet de sortie identique à celui du codeur, récupère la valeur yi qui correspond à l’indice i reçu.

En général, l’opération de quantification entraîne une perte d’information irréversible qui se traduit par l’introduction d’une erreur e, appelée erreur (ou bruit) de quantification :

e Q (x) x (2.6)

2.2.2 Mesure de performance d’un quantificateur scalaire

La dégradation apportée par l’opération de quantification est évaluée par une certaine mesure de distorsion (ou critère d'erreur). Pour un quantificateur Q quelconque et une variable d’entrée aléatoire (source) X, la distorsion moyenne totale due à la quantification de la source est donnée par la formule générale suivante [4, 9]:

illustration not visible in this excerpt

où fX (x) est la fonction densité de probabilité (pdf) de X et E est l’espérance mathématique.

On considère toujours que la mesure de distance est de type quadratique, donnée selon la norme euclidienne par :

illustration not visible in this excerpt

Spécifiquement, pour un SQ défini par Q = { Ri, yi, i = 0,…, L 1}, la distorsion moyenne totale de quantification aura pour expression [4, 6]:

illustration not visible in this excerpt

Les performances d'un SQ sont souvent évaluées en utilisant la distorsion moyenne totale (Eq.

2.9). Cette mesure de distorsion est choisit habituellement comme critère d’erreur qui doit être minimisé dans le processus de conception du quantificateur. Ainsi, le but est de trouver les représentants yi et les classes Ri de la partition qui minimisent D.

On peut également chercher à maximiser le fameux rapport signal sur bruit (RSB), défini par le rapport de puissance du signal codé sur l'erreur quadratique moyenne:

illustration not visible in this excerpt

[...]

---

¹ Les techniques de codage de source par quantification sont détaillées au chapitre 2.

² Dans le cas du codage de source "sans pertes", la limite théorique de Shannon est donnée par l ’ entropie de la source H (s)¹. Plus généralement, pour un codage de source "avec pertes", cette limite est donnée par la fonction débit-distorsion R (D)⁹. Plus de détails sont donnés en Annexe A.

³ Une source de type BSS¹⁷ est modélisée par une fonction de densité de probabilité (pdf) uniforme. Le "BSC" est un modèle de canal bruité dont l'importance théorique et pratique est grande (cf. chapitre 3).