Axes de Recherche de l'équipe

Algorithmes de très faible complexité pour le codage de source et l’annulation d’échos

I. Contexte

Bien que les progrès technologiques jusqu’à aujourd’hui aient été considérables, la complexité algorithmique a encore un impact direct sur le coût d’un système. Pour développer de nouveaux algorithmes performants ayant une complexité de calcul réduite et un délai algorithmique satisfaisant, nous développons des compétences dans la mise en œuvre de transformées rapides basées sur les propriétés des corps de Galois. Ces transformées permettent le calcul rapide de corrélations, de filtrage numérique et de divers calculs matriciels. Elles présentent d’importants avantages, tels que le fait que tous les calculs intermédiaires se font en nombres entiers, ce qui est particulièrement intéressant pour les implantations sur architectures matérielles, et le fait que la majorité des multiplications est remplacée par de simples décalages. L’originalité des travaux menés dans cet axe est l’exploitation des propriétés des transformées en nombres entiers pour réaliser des implantations de très faible complexité de plusieurs normes et techniques de codage de source et d’annulation d’échos. Malgré leur intérêt, les transformées en nombres entiers sont encore relativement peu utilisées dans la communauté scientifique, l’une des raisons étant probablement la nécessité de posséder de solides connaissances en théorie des nombres pour adapter ces méthodes à une application particulière.

II. Résultats

Les principaux résultats sont obtenus dans le cadre d’une collaboration avec une entreprise spécialisée dans la conception et la fabrication de routeurs. Ils concernent une implantation de très faible complexité du codeur UIT-G.729, pour la compression de la parole et sa transmission sur réseau IP. Une part importante de la complexité du codeur est due au calcul des coefficients LSP (Line Spectrum Pairs). Ce calcul est réalisé en plusieurs étapes et fait appel à une analyse prédictive du signal de parole et à une recherche de zéros de paires de polynômes. Dans ce cadre, nous avons proposé une méthode rapide de calcul des coefficients LSP basée sur la transformée en nombres de Fermat. Ce type de transformée est habituellement désigné par "FNT" (Fermat Number Transform). De la même façon qu’il existe une version rapide de la transformée de Fourier discrète, il existe une version rapide de la FNT.
Nous décomposons la FNT en plusieurs FNT simples, effectuées en parallèle de manière indépendante, le résultat global étant ensuite reconstitué grâce au théorème du reste chinois, l’un des théorèmes fondamentaux de la théorie des nombres.
Le travail théorique mené au laboratoire consiste à généraliser le principe de la NTT (Number Theoretic Transform) pour permettre le calcul direct des coefficients LSP. La suppression des étapes de calcul intermédiaire, et les propriétés de la NTT comme la convolution cyclique permettent une réduction importante de la complexité du codeur. On peut également noter que, bien que l'application choisie soit le codeur G729, l'aspect théorique du travail présente un intérêt en dehors de ce codeur : en effet, plusieurs normes de compression font appel au calcul des coefficients LSP.

II.1. Nouveau modèle de codeur dérivé de celui de la norme G.729

Le codeur G.729 a été modifié pour permettre son implantation sur un processeur à virgule fixe en mettant en œuvre des transformées en nombres de Fermat. Elles ont été appliquées à la modification et à l’amélioration de certaines fonctions pour permettre la réduction de leur complexité de calcul.
C’est dans cette optique qu’une nouvelle technique pour l’analyse de Prédiction Linéaire a été nécessaire. Ainsi, une procédure efficace a été proposée et une implémentation en virgule fixe d’algorithmes nécessaires pour extraire les coefficients d’autocorrélations et de Prédiction Linéaire a été rendue possible par des transformées en nombres de Fermat.
L’accent a été ensuite mis sur la modélisation du signal résiduel d’excitation résultant du filtrage prédictif. Une technique à deux niveaux, qui dissocie les trames de signal voisé ou non, a été développée pour une modélisation robuste du signal d’excitation, ce qui permet une légère réduction du débit de transmission du codeur et de sa complexité pour la détermination des contributions du dictionnaire adaptatif.
Ces deux modèles mettant en œuvre la transformée en nombres de Fermat ont été évalués par des mesures de qualité objectives et subjectives à partir de la programmation en virgule fixe du système de codage G.729 et du nouveau modèle proposé. Le nouveau modèle du codeur G.729 produit des signaux d’assez bonne qualité comparé au signal original.

Les figures ci-dessous illustrent parfaitement l’intérêt que présente l’utilisation de la FNT en terme de réduction du nombre de multiplications. Elles donnent l’ordre de grandeur du nombre d’opérations simples (additions, décalages de bits) et de multiplications, pour deux implantations d’une fonction de filtrage rencontrée dans le codeur G. 729, l’une mettant en œuvre la transformée de Fourier rapide et l’autre la transformée en nombres de Fermat.

Nombres d’opérations requis pour le calcul d’une fonction de filtrage rencontrée dans la partie prétraitement du codeur G. 729 de l’Union Internationale des Télécommunications

II.2. Compression des silences

La généralisation de la voix IP restant confrontée à des problèmes de débit de transmission trop élevé (8kbits/s pour le codeur G.729), il est impératif de réduire au maximum le nombre de bits transmis en utilisant des techniques de compression de silence. Lorsque la parole n’est pas présente dans le signal à coder, le débit peut être optimisé pour libérer le canal à d’autres applications. Cependant, le problème de réduction du débit de transmission d’un codeur par compression des silences contenus dans le flux de parole reste délicat. En effet, l’analyse de parole devra tenir compte des différentes intonations de voix, du bruit et d’une possible dégradation des signaux traités par les échos. Pour obtenir une bonne qualité de compression des silences avec un faible débit de transmission, un modèle de détection d’activité de parole (VAD) robuste est alors essentiel pour extraire les trames vocales inactives.
Pour cela, un nouvel algorithme de VAD, plus efficace que celui conseillé en annexe B de la norme G.729, a été proposé pour une arithmétique à virgule fixe mettant en œuvre la transformée en nombre de Fermat et des simulations numériques ont été conduites pour évaluer ses performances . Une comparaison avec le VAD standard, décrit par la norme G.729 annexe B, a ensuite été réalisée sous différentes conditions d’environnement. Des résultats moyennés, indiquant un taux d’erreur de décision, ont été obtenus en fonction du rapport signal à bruit (SNR) entre le signal traité et un bruit additif (aléatoire, blanc et gaussien), à l’aide d’une simulation de Monte-Carlo. Lors de ses tests, nous avons comparé les différentes décisions prises à une base de données contenant la nature (parole ou silence) théorique des trames. Les deux algorithmes de détection d’activité de parole, l’original de la norme G.729 annexe B ou celui de notre modèle, obtiennent des performances proches pour des signaux faiblement bruités. Cependant, lorsque le SNR diminue, la différence entre les décisions des VAD devient plus prononcée au profit du nouveau détecteur proposé. La mise en œuvre de cette nouvelle procédure du VAD, robuste aux erreurs, a permis une réduction de 3 à 4 kbits/s du débit de transmission.

II.3. Traitement des problèmes d’annulation d’échos

Cette méthode de réduction de complexité a été aussi appliquée au traitement des problèmes de l’annulation d’échos acoustiques. Nous avons ainsi proposé et étudié de nouveaux algorithmes de filtrage adaptatif de faible complexité que nous avons traités par blocs et rendus robustes avant de les implanter au moyen de la transformée en nombres de Fermat.

III. Conclusion et Perspectives

Les résultats obtenus par la mise en œuvre de la transformée en nombres entiers pour le développement de méthodes de réduction de la complexité des systèmes montre que cette approche présente un intérêt important en traitement du signal et en particulier en calcul rapide de corrélations, de filtrage numérique et de divers calculs matriciels. Cette méthode intéresse directement les membres de l’équipe TST qui développent les méthodes d’analyse du train binaire en contexte non coopératif pour les communications numériques.
L’intérêt pour ces méthodes très originales est aussi exprimé par certaines entreprises du secteur des télécommunications et permettra à l’équipe TST d’envisager de nouvelles perspectives.

IV. Publications

G. Madre, E.-H. Baghious, S. Azou, and G. Burel, " Design of a variable rate algorithm for CS-ACELP coder", IEEE International Conference on Communications (ICC 2003), Anchorage, Alaska, USA, May 11-15, 2003.
G. Madre, E.-H. Baghious, S. Azou, and G. Burel,"Linear Predictive Speech Coding using Fermat Number Transform", 4th Eurasip Conference on Video, Image Processing and Multimedia Communications (EC-MC’03), 2-5 July 2003, Zagreb, Croatia.
G. Madre, E.-H. Baghious, S. Azou, and G. Burel, "Fast Pitch Modelling for CS-ACELP Coder using Fermat Number Transforms", IEEE Int. Symp. on Signal Processing and Information Technology (ISSPIT'2003), Darmstadt, Germany, Dec. 14-17, 2003.
E.-H. Baghious, G. Madre, H. Alaeddine, and G. Burel, "Realization of block adaptive filters using Fermat number transforms ", International Symposium On Image/Video Communications over Fixed and Mobile Networks, ISIVC'04, Brest, France, July 7-9, 2004.
H. Alaeddine, E.-H. Baghious, G. Madre, and G. Burel, “Realization of Block Robust Adaptive Filters using Generalized Sliding Fermat Number Transform”, EUSIPCO’2006, 14th European Signal Processing Conference, sept 4-8, 2006, Florence, Italy.