Le filtre conçu est évidemment adaptatif étant donné que les signaux sonores sont non stationnaires; l’algorithme sert donc à l’adaptation des coefficients du filtre jusqu’à ce qu’il devienne utilisable dans l’enceinte considérée (en peu de temps et chaque fois que c’est nécessaire).
C’est ainsi que nous misons particulièrement sur le filtrage adaptatif bien adapté aux signaux évoluant dans le temps, ce qui est évidemment le 7  CHAPITRE 1.
Ce qui induit une dualité temps-fréquence, le passage de l’un des domaines à l’autre étant réalisable par symétrie vu que la transformée inverse de Fourier est donnée par: s(t) = ∫ +∞ −∞ S(f).e j2πft df(1.12) Intérêt de la transformation ainsi définie On démontre que l’une des conditions pour qu’une fonctionf(t)soit développable en série de fonctions orthogonales trigonométriques (série de Fourier) est qu’elle soit périodique, et pourtant dans la majorité des situations ce n’est pas le cas.
La densité spectrale de raies sera alors donnée par, suite à la relation 1.10: S 1 n f 1 =T.S 1 n = ∫ T 2 −T 2 s 1 (t).e −j2πnf 1 t dt(1.14) Ainsi donc, les raies deviennent de plus en plus rapprochées à mesure queTcroît et à l’infini, la somme donnée en 1.9 se transforme en une intégrale etf 1 devient infinitésimale, ce qui fait que: s(t) =   lim T→+∞ s 1 (t) =   lim T→+∞ { +∞ ∑ n=−∞ 1 T .[ ∫ T 2 − T 2 (s 1 (t).e −j2πnf 1 t dt)].e j2πnf 1 t } = ∫ +∞ −∞ df.[ ∫ +∞ −∞ s(t).e −j2πft dt)].e j2πft = ∫ +∞ −∞ S(f).e j2πft df Ceci  exprime  très  clairement  qu’un  signal  s(t)  quelconque  peut  être  vu  comme  la  transformée inverse  de  sa  transformée  de  Fourier.
BASES THÉORIQUES DU TRAITEMENT DU SIGNAL est évidemment donnée par: S d (f) = N−1 ∑ n=0 s(nT e ).e −i 2πn N f (1.24) Cela veut dire que la transformée inverse pour le cas des signaux discrets finis sera donnée par: s(nT e ) = 1 N N−1 ∑ k=0 S d (f).e i 2πk N n (1.25) Cette nouvelle définition( faite en 1.24) permet d’introduire en substance un algorithme de calcul rapidede  la  transformée  de  Fourier.
Cela  dit,  il  est  tout  à  fait  clair  quec’est  plus  intéressant  d’exprimer  tout  signal  comme  somme d’exponentielles  complexes  pour  faciliter  les  calculs  en  cas  de  filtrage,  vu  que  ce  dernier  est exprimé  par  un  opérateur  dont  les  vecteurs  propres  sont  des  exponentielles.
Une  solution  plus  pratique  serait  d’aborder  le  problème  de  manière  globale,  en  considérant plutôt l’enceinte comme un système dont il suffirait juste d’étudier le comportement, grâce à un modèle équivalant, qui faciliterait le traitement par des algorithmes de calcul et diminuerait ainsi le nombre de paramètres pris en compte.
Nous n’allons plus nous intéresser à l’adaptation des coefficients du filtre à chaque itération comme dans  les  paragraphes  précédents  car  cela  représente  une  charge  assez  importante  en  terme  de calcul et de mémoire.L’algorithme sera plutôt modifié de manière à l’optimiser au maximum tout en  conservant  les  traitements  appliqués  aux  données  (séquences).
UNIVERSITE LIBRE DES PAYS DES GRANDS LACS ULPGL-GOMA B.P368GOMA /WWW.ULPGL.NET FACULTÉ DESSCIENCES ETTECHNOLOGIESAPPLIQUÉES Département de Génie Électrique et Informatique CONCEPTION D’UN FILTRE ANNULATEUR D’ECHO SONORE MIXTE Travail de fin de cycle présenté en vue de l’obtention du diplôme de Graduat en Sciences Appliquées. Présenté par :KRAME KADURHA DAVID Directeur : DI.Dr.Tech. ALAINAKWIR NKIEDIEL Encadreur : Ass2.Ing. DIEUDONNÉMUSONGYA BISIMWA Année académique2019−2020    DÉDICACES A Ma mère Charlotte, mon oncle Aciza et ma petite Joëlle dont respectivement le courage, l’humilité et l’innocence sont toujours une source d’inspiration. i    REMERCIEMENTS En  premier  lieu,  nous  remercions  Dieu  pour  nous  avoir  caché  les  choses  tout  en  nous  rendant capables de les trouver par nous mêmes. C’est à la fois un bonheur et un honneur. Nos remerciements particuliers à notre directeur, DI.Dr.Tech. Alain AKWIR NKIEDIEL, et notre encadreur, Ass2.Ing. Dieudonné MUSONGYA BISIMWA, pour le suivi humble, patient et attentif qu’ils nous ont accordé durant l’élaboration de ce document. Nous remercions aussi tous ceux dont l’existence contribue énormément à notre bien-être.  Nous pensons particulièrement à notre mère BALIBUNO NZIGIRE Charlotte, Joëlle ANSIMA, Aciza CUBAKA, Daniel KADURHA, Emmanuella MUSIMWA, Florence CINAMA, Generose ABEKA, Alohn SHETEBO, Carine SHETEBO, Sr Catherine, Christian RUBONEKA, Bijoux NAMWESI et Bernardin BWIRABUCIZA. Nos remerciements les plus reconnaissants à Juvénal BALIBUNO, Marcellin BALIBUNO, Bakondjo MUHUBAO, Charles BISIMWA, Akonkwa BALIBUNO, Irène IRAGI, Georgette, Eka BIGABWA, Labii KADURHA, Déo KADURHA, Yvette BUBAKA, Ciza BUBAKA, Ludwine BALIBUNO ,etc. A nos chers grand-parents BALIBUNO Richard et François KADURHA dont respectivement la perspicacité et l’érudition ne cesseront de nous inspirer et de nous guider. Nous remercions enfin nos amis et camarades, pensant nommément à Wen KAMUNTU, Bruno KAMOLE, Patricia OLINABABO, Yvan KAHASHI, Naomi MASASI, Chrispin CIRHULWIRE, Divin KUBIYA, Patient KUBUYA, Pierre MABILI, Styve EBASOMBA, Jacques NDAVARO et tous les gens bienveillants. Recevez nos remerciements les plus sincères. KRAME KADURHADAVID iii    RÉSUMÉ Ce travail consiste à concevoir un filtre numérique destiné à un système annulateur d’écho sonore. Pour y parvenir, on commence par passer en revu les notions générales de la théorie de traitement du signal directement utiles à cette fin.  Après cela, une analyse détaillée des algorithmes élaborés pour l’identification des systèmes est réalisée pour finalement déboucher sur deux choses: l’étude des techniques permettant d’optimiser au maximum les algorithmes et le choix d’un algorithme particulièrement  adapté  aux  systèmes  annulateurs  d’écho  (on  a  choisi  leBPNLMS++).   Ici  le système à identifier est le chemin d’écho.  L’algorithme choisi et amélioré est écrit et testé sous Matlabpour en vérifier la validité (le test de validation est réalisé dans une situation où l’on sait déjà le résultat prévu par la théorie et on simule l’algorithme pour le valider ou l’invalider).  La validation ayant réussi, le filtre est prêt à être implémenté comme tel sur une plateforme d’annulation d’écho.  Le filtre conçu est évidemment adaptatif étant donné que les signaux sonores sont non stationnaires; l’algorithme sert donc à l’adaptation des coefficients du filtre jusqu’à ce qu’il devienne utilisable dans l’enceinte considérée (en peu de temps et chaque fois que c’est nécessaire).  Donc ces coefficients sont figés pendant le filtrage. Ainsi, on peut facilement, grâce à ce filtre, modéliser l’écho  d’un  signal  en  entrée,  et  le  soustraire  du  signal  global  à  transmettre  comme  réponse  à l’émetteur, pour que ce dernier ne puisse pas recevoir une réplique du signal qu’il a émis (l’écho est ainsi supprimé). Le travail est effectivement clos par la validation de l’algorithme qui implémente le filtre adaptatif conçu, ainsi que par un essai d’annulation d’écho. v    SIGLES ET ABRÉVIATIONS ADC: Analog to Digital Converter; BLMS: Block Least Mean Square; BNLMS: Block Normalized Least Mean Square; BPNLMS++: Block Proportionnate Normalized Least Mean Square amélioré; CAN: Convertisseur Analogique-Numérique; CNA: Convertisseur Numérique-Analogique; DAC: Digital to Analog Converter; DSP: Digital Signal Processing; FFT: Fast Fourier Transform; FNT: Fermat Number Transform; GF: Galois Field; GPS: Global Positionning System; LMS: Least Mean Square; NLMS: Normalized Least Mean Square; NNT: Natural Number Transform; PNLMS: Porportionnate Normalized Least Mean Square; PNLMS++: PNLMS amélioré; RLS: Recursive Least Square; SNR: Signal-to-Noise Ratio. vii    Table des matières DÉDICACESi REMERCIEMENTSiii RÉSUMÉv SIGLES ET ABRÉVIATIONSvii INTRODUCTION GÉNÉRALE1 0.1Contexte .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .1 0.2Problématique .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .2 0.3Formulation des hypothèses    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .2 0.4Objectifs du travail   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .3 0.4.1Objectif général .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .3 0.4.2Objectifs spécifiques   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .3 0.5Choix et intérêt du sujet .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .3 0.6Méthodologie de recherche et délimitation du travail    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .4 0.7Subdivision du travail  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .4 1    GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL7 1.1Introduction partielle   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .7 1.2Bases théoriques du traitement du signal  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .8 1.2.1Fondement de l’analyse des signaux[4]   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .8 1.2.2Signaux déterministes    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .10 ix  TABLE DES MATIÈRES 1.2.3Signaux aléatoires    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .12 1.2.4Cas des signaux discrets   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .14 1.3Filtrage   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .18 1.3.1Introduction .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .18 1.3.2Prélude au filtrage adaptatif    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .20 1.4Traitement du signal audio   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .22 1.5Conclusion partielle .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .23 2    ÉTUDE THÉORIQUE DU FILTRAGE DU SON25 2.1Introduction partielle   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .25 2.2Quelques algorithmes de filtrage adaptatif   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .26 2.2.1Algorithme du gradient déterministe  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .26 2.2.2Algorithme du gradient stochastique(LMS)[1] .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .28 2.2.3Algorithme des Moindres Carrés Récursif [1]&[14] .  .  .  .  .  .  .  .  .  .  .  .  .28 2.2.4Algorithme LMS Normalisé (NLMS) [1]&[6] .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .29 2.2.5Algorithme Proportionné Normalisé (PNLMS)[1] .  .  .  .  .  .  .  .  .  .  .  .  .  .30 2.2.6Algorithme PNLMS++ [1]  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .31 2.3Transformée en nombres entiers (NNT) [1]    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .32 2.3.1Choix des paramètres de la transformation et Transformée en nombres de Fermat (FNT) .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .33 2.3.2Transformation en nombres de Fermat et arithmétique binaire   .  .  .  .  .  .  .33 2.3.3Version rapide de la FNT  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .35 2.3.4La convolution rapide    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .36 2.3.5Multiplication optimale des matrices [8]  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .37 2.4Traitement par bloc des algorithmes d’annulation d’écho   .  .  .  .  .  .  .  .  .  .  .  .  .  .38 2.4.1Introduction .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .38 2.4.2Algorithmes proprement-dits [1]  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .40 2.5Conclusion partielle .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .42 3    CONCEPTION DU FILTRE MIXTE ADAPTÉ43 3.1Introduction partielle   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .43 x sur 84  TABLE DES MATIÈRES 3.2Structure globale du système  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .43 3.2.1Filtre anti-repliement  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .44 3.2.2Convertisseurs Analogique-Numérique et Numérique-Analogique   .  .  .  .  .46 3.2.3Filtre de lissage  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .48 3.2.4Traitement    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .49 3.3Élaboration de l’algorithme et présentation du système   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .50 3.3.1Élaboration de l’algorithme d’apprentissage  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .51 3.3.2Présentation du système réel  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .54 3.4Implémentation de l’algorithme et simulations  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .55 3.4.1Traitement brut des données   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .55 3.4.2Traitement par bloc des données  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .57 3.4.3Essais comparés    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .59 3.5Analyse des résultats et explication de l’implantation sur DSP    .  .  .  .  .  .  .  .  .  .  .65 3.5.1Analyse des résultats  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .65 3.5.2Explication de l’implantation sur DSP  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .66 3.6Annulation d’écho    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .66 3.7Conclusion partielle .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .68 CONCLUSION GÉNÉRALE69 ANNEXES73 .1Algorithme de traitement brut    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .75 .2Algorithme de traitement par blocs  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .78 xi sur 84    Liste des figures 1.1Visualisation d’un signal de parole sur une durée de 1/16 de seconde  .  .  .  .  .  .  .  .13 3.1Chaîne typique de traitements du signal   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .44 3.2Absence de repliement[7] .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .45 3.3Présence de repliement[7] .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .45 3.4Echantillonnage-Quantification-Codage[18]  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .47 3.5Positionnement du filtre de lissage   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .48 3.6Processus complet de conversion N/A (signaux associés)   .  .  .  .  .  .  .  .  .  .  .  .  .  .48 3.7Signal d’entrée utilisé  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .56 3.8Valeurs des64coefficients du filtre  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .57 3.9Les64coefficients du filtre 2  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .58 3.10  Les64coefficients du filtre 2 non formatés .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .59 3.11  Coefficients du filtre 1 pour 10000 itérations  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .60 3.12  Coefficients du filtre 2 pour 10000 itérations  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .60 3.13  Coefficients du filtre 1 pour 1000 itérations    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .61 3.14  Coefficients du filtre 2 pour 1000 itérations    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .61 3.15  Coefficients du filtre 1 pour 100 itérations   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .62 3.16  Coefficients du filtre 2 pour 100 itérations   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .62 3.17  Coefficients du filtre 1 pour 10 itérations  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .63 3.18  Coefficients du filtre 2 pour 10 itérations  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .63 3.19  Coefficients du filtre 1 pour 4370 itérations    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .64 3.20  Coefficients du filtre 2 pour 400 itérations   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .64 3.21  Démonstration de l’annulation d’écho   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .67 xiii    INTRODUCTION GÉNÉRALE 0.1    Contexte La  communication  est  un  facteur  clé  dans  l’émergence  d’une  société.   Ce  fait  se  démontre  par le  développement  assez  important  survenant  après que  l’homme  ait  développé  les  méthodes  de traitement, manipulation et interprétation des signaux. Il existe plusieurs types de signaux, mais nous nous focaliserons dans ce travail, sur les signaux sonores. L’onde sonore résulte d’une perturbation du milieu de propagation considéré. En effet, le milieu de propagation 1 est complètement connu si en chacun de ses points et à chaque instant on a la valeur de la vitesse, la pression et celle de la densité. Quantitativement, cela revient à définir les fonctions donnant ces grandeurs. Sous l’effet de la perturbation des dites grandeurs (avec l’approximation acoustique[5], ces perturbations sont très négligeables par rapport à la valeur au repos de la grandeur perturbée), on constate une variation qui respecte l’équation des ondes.  Cela traduit le fait que le son est une onde, ce qui veut dire que son comportement est bel et bien analogue à tout type d’onde. De ce fait, il subira tous les traitements réservés aux grandeurs ondulatoires. Il peut donc subir la diffraction, la réfraction, l’interférence,...  exactement comme tout type d’onde.  On peut aussi en étudier le phénomène de réflexion et cela nous amène immédiatement à l’étude de l’écho lui associé, c’est ce qui va particulièrement nous préoccuper dans ce travail. L’écho acoustique en tant que phénomène physique, n’est en aucune manière problématique ni dérangeant. Il peut néanmoins s’avérer indésirable lors d’une communication par exemple. C’est ainsi qu’il est parfois impératif de trouver une solution à la nuisance apportée par des 1 Nous traiterons dans ce document, uniquement de la propagation du son dans les fluides et particulièrement dans les gaz; que nous supposerons évidemmentparfaits. 1  LISTE DES FIGURES échos acoustiques 2 non désirés. 0.2    Problématique Il  arrive  que,  suite  à  un  mauvais  couplage  du  microphone  avec  le  haut-parleur,  nous  puissions entendre notre voix résonner via l’ordinateur portable et les hauts-parleurs de la salle de réunion, via les écouteurs lors d’une vidéo-conférence, lors d’un appel téléphonique(surtout en mode mains libres)... Le phénomène peut ne pas durer assez longtemps mais il devient très vite gênant surtout quand il est perceptible. Toutefois,  même  quand  l’écho  n’est  pas  perceptible,  il  rend  moins  bonnes  l’optimisation  de  la mémoire ainsi que la compression des données. La qualité du son lors d’une communication est très importante, surtout en application civile, et l’optimisation de l’espace de stockage en cas de besoin ne peut être que bénéfique. Cela fait à ce qu’il soit impérieux de focaliser notre recherche sur les moyens efficaces et rentables au point de vu économique, pour remédier au dit problème. De cette ambition naissent quelques questions auxquelles nous auront répondu à l’issu de ce travail, à savoir: 1.  Le filtrage peut-il remédier complètement au problème de la présence indésirée d’écho sonore? 2.  Un filtrage analogique peut-il suffire sans problème? 3.  Sans mémorisation dynamique du signal, est-il possible de mieux annuler l’écho? 0.3    Formulation des hypothèses Nous estimons qu’un filtre résoudrait bel et bien le problème de la présence indésirée de l’écho acoustique dans les signaux sonores. Nous croyons également qu’un filtre purement analogique serait moins rentable pour réaliser de façon satisfaisante l’annulation de l’écho d’un signal sonore. 2 L’utilisation abusive du termeécho acoustiqueen lieu et place d’écho sonoren’est pas à considérer avec toute la rigueur 2 sur 84  0.4.  OBJECTIFS DU TRAVAIL C’est pour cette raison que nous anticipons qu’un filtre mixte, allié à une mémorisation dynamique et optimisée du signal réaliserait amplement l’extraction du signal de base sans écho. 0.4    Objectifs du travail 0.4.1    Objectif général Notre travail consiste à concevoir un filtre annulateur d’écho acoustique. 0.4.2    Objectifs spécifiques Pour arriver à mettre conceptuellement sur pieds un filtre annulateur d’écho adapté, nous comptons: 1.  Etudier la génération d’écho acoustique et circonscrire le problème; 2.  Choisir l’approche adaptée pour modéliser la réponse d’une enceinte à l’onde sonore; 3.  Évaluer la possibilité d’un traitement par filtrage adaptatif; 4.  Etudier et adapter le filtrage numérique de l’écho; 5.  Concevoir, étudier et tester les algorithmes d’annulation d’écho; 6.  Proposer les éléments et paradigmes adaptés pour une perspective d’implantation du filtre. 0.5    Choix et intérêt du sujet Le filtrage des signaux est assez puissant pour résoudre tout problème consistant à séparer le signal utile d’avec le bruit.   Nous avons donc songé à appliquer ce type de traitement au son juste en ce qui concerne l’annulation de l’écho, sans nous préoccuper des autres signaux indésirables qui brouilleraient le signal utile. La conception d’algorithmes de filtrage du son serait rendue plus efficace sur un grand nombre des points si le problème de l’écho se trouvait préalablement résolu. Ainsi, ce sont d’autres parasites qui seraient pris en compte et l’écho deviendrait secondaire. 3 sur 84  LISTE DES FIGURES Sur le plan social, il est évidemment important d’augmenter le confort lors d’une communication par exemple en annulant l’écho quand cela s’avère nécessaire mais également, d’optimiser l’utilisation d’un espace mémoire en cas de stockage des données. 0.6    Méthodologie de recherche et délimitation du travail Nous  procéderons  par  analyse  et  expérimentation  (notamment  grâce  au  logicielMatlab)  avec comme techniques, l’analyse du contenu et la documentation. Notre travail se focalise uniquement sur l’onde sonore, principalement sur le filtrage ainsi que l’annulation de l’écho généré 3 . Nous réaliserons donc le filtrage dudit signal dans un contexte plus général (indépendamment de l’enceinte, considérant juste la modélisation de la réponse de l’enceinte, ou du lieu en général, à l’onde sonore). Cela  nous  conduira  à  élaborer  un  filtre  adapté  avec  optimisation  des  apports  respectifs  des parties numériques et analogiques. Il faut également noter que le milieu de propagation considéré dans le présent travail est le gaz parfait. Aussi, nonobstant le fait que certains résultats trouvés soient applicables pour tout type de fluide, nous ne les appliquons qu’au cas des gaz parfaits. 0.7    Subdivision du travail Excepté l’introduction et la conclusion générales, nous avons dans ce travail: •  AuChapitre  1,Les  généralités  sur  le  traitement  du  signal,  nous  nous  focalisons  sur  les aspects du traitement des signaux qui seront utiles à notre projet (particulièrement le traitement du signal audio). •  AuChapitre 2,Etude théorique du filtrage du son, nous traitons particulièrement du filtrage de l’onde sonore en vu d’annuler un écho éventuel. Nous y parlons également des différentes 3 On  ne  traitera  par  exemple  pas  de  l’écho  électrique  dû  aux  caractéristiques  des  éléments  intervenant  dans  le traitement et la transmission du signal. 4 sur 84  0.7.  SUBDIVISION DU TRAVAIL méthodes d’annulation d’écho et particulièrement des algorithmes existant. •  AuChapitre 3,Conception d’un filtre mixte adapté, nous concevons, étape par étape, le filtre recherché en nous basant sur les algorithmes du chapitre précédent, tout en les complétant et en les améliorant en cas de besoin.  Nous y donnons également des lumières utiles pour l’embarcation du système. 5 sur 84    Chapitre 1 GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL 1.1    Introduction partielle L’un des moyens permettant de se faciliter la tâche de manipulation du son, consiste à le voir comme une fonction mathématique (bien que non modélisable comme tel de manière rigoureuse).  Ainsi on voit le son comme la variation d’une quantité (l’énergie de pression transmise par exemple) en fonction du temps. Cela nous permet de le traiter comme un signal parmi tant d’autres et ainsi avoir le droit d’y appliquer des résultats élaborés pour cet effet dans le cadre d’une discipline nommée traitement du signal. Le traitement du signal est en effet une discipline qui est axée sur le traitement, l’interprétation et l’analyse des signaux. Un signal peut être contrôlé, filtré, comprimé, transmis, débruité, déconvolué, identifié, classifié... C’est donc une discipline dont l’objet central d’étude est le signal (concept qui regroupe nombreux phénomènes bien particuliers comme le son, l’image,...). Dans ce premier chapitre, nous abordons particulièrement les notions de base du traitement des signaux tout en orientant notre exposé dans le sens du traitement du signal qui nous concerne. Tout converge vers un traitement particulièrement utile pour notre étude, le filtrage.  Nous nous focalisons  sur  le  traitement  numérique  du  signal  vu  que  c’est  ce  qui  facilite  la  manipulation  et l’élaboration des systèmes de traitement des signaux. C’est ainsi que nous misons particulièrement sur le filtrage adaptatif bien adapté aux signaux évoluant dans le temps, ce qui est évidemment le 7  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL cas de la majorité des signaux sonores. 1.2    Bases théoriques du traitement du signal 1.2.1    Fondement de l’analyse des signaux[4] Un  signals(t)peut  être  vu  approximativement  comme  une  combinaison  linéaire  des  fonctions simples et connues formant la base d’un espace vectoriel à dimensionnqui est infini à la limite. Cela  étant,  on  associera  à  chaque  fonctionf i (t)constituant  la  base  dudit  espace  vectoriel  un coefficientα i . Ce qui donne: s(t) = n ∑ i=1 α i f i (t)(1.1) Cette représentation des signaux est très capitale car elle facilite l’analyse du signal ainsi représenté et permet d’aborder le traitement numérique du signal. En effet, le traitement numérique d’un signal ne peut être envisagé que s’il est discrétisé or, la manière donts(t)est écrit en 1.1 suggère qu’il peut se voir comme un vecteur dont les composantes sont lesα i , ce qui le rend en fait discret. Nous venons de former un espace vectoriel des fonctions, isomorphe àR n ou àC n selon que le signal est modélisé sous la forme réelle ou complexe. On remarque ques(t)peut être représenté par un vecteur dont les composantes changent en fonction de la famille desf i (t)choisie. Le choix de cette famille est également primordial car c’est de lui que dépend la facilité d’analyse du signal considéré. La représentation des signaux par des vecteurs est très féconde etpermet par exemple d’évaluer le degré de ressemblance des signauxgrâce à la notion de distance.  Pour cela, on définit une norme ‖.‖sur l’espace des fonctions introduit tel que pour tout signals(t)on ait que: ‖s(t)‖ 2 = √ √ √ √ n ∑ i=1 (α i ) 2 (1.2) 8 sur 84  1.2.  BASES THÉORIQUES DU TRAITEMENT DU SIGNAL Par analogie on a que la norme de s(t) est sur une périodeτ: ‖s(t)‖ 2 = √ ∫ τ |s(t)| 2 dt(1.3) L’expression  1.3  signifie  que  les  signaux  doivent  être  à  carré  intégrable.   Le  sens  physique  est que les signaux doivent avoir une énergie finie.  Ce qui précède est évident pour un signal réel et constitue une condition supplémentaire à imposer à l’espace des signaux. Soients(t)  =  (α 1 ,...,α n )etu(t)  =  (β,...,β n )deux signaux,  la  distance entre les deux signaux sera donnée par la distance usuelle découlant de la norme définie en 1.2. Soit que: d(s,u)   =‖s−u‖ 2 (1.4) = √ √ √ √ n ∑ i=1 (α i −β i ) 2 (1.5) Notez que par analogie on peut également définir, en vertu de 1.3, la distance entre les signaux par: d(s(t),u(t)) = √ ∫ τ |s(t)−u(t)| 2 dt(1.6) La norme,  telle que définie en 1.2,  dérive 1 évidemment d’un produit scalaire[9];  ce produit est donné par: 〈s,u〉= n ∑ i=1 (α i .β ? i )(1.7) Avecβ ? i le complexe conjugué deβ i pour être plus général. Comme habituellement nous pouvons aussi définir ce produit pour les signaux non discrétisés sur une période de tempsτpar: 〈s(t),u(t)〉= ∫ τ (s(t).u ? (t))dt(1.8) Le produit scalaire de deux vecteurs est proportionnel à la projection de l’un sur l’autre.   Il est 1 Car on a que‖s‖= √ 〈s,s〉 9 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL maximum, en valeur absolue, lorsque les deux vecteurs ont la même orientation et nul lorsqu’ils sont orthogonaux.  Il peut donc être considéré comme une mesure de la similitude d’orientation des vecteurs. En d’autres termes, le rapprochement des signaux dans leur évolution (similitude des formes). L’espace vectoriel des fonctions ainsi défini et muni de ce produit scalaire qui y induit une norme estcomplet[9] et constitueun espace de Hilbert.   La connaissance de cette structure est cruciale car elle permet de traiter tous les éléments de cet espace des signaux en utilisant juste les résultats connus sur les espaces de Hilbert. Ce qui vient d’être démontré justifie que les signaux soient développables en série des fonctions orthogonales et non liées.   D’où la possibilité de les développer ensérie de Fourierou bien en considérant les autres familles des fonctions orthogonales selon les besoins et la commodité.  Le développement en série de Fourier est en fait d’une importance capitale en théorie du signal. 1.2.2    Signaux déterministes Les signaux déterministes sont ceux représentables par une fonction analytique. Suite à ce qui vient d’être montré à la sous-section précédente, nous allons reconsidérer la transformée de Fourier dans cette partie et en aborder les aspects utiles à notre travail.  La transformation de Fourier est vue comme une généralisation du développement en série des fonctions orthogonales de Fourier tel que présenté dans la partie qui précède. Le développement en série Fourier est donnée par [13]: s(t) = +∞ ∑ n=−∞ [S n .e j2πnft ](1.9) Cette équation constitue donc, à quelques changements de variable près, un cas particulier de 1.1. Avec les coefficientsS n donnés par: S n = 1 T . ∫ T 2 −T 2 s(t).e −j2πnft dt(1.10) 10 sur 84  1.2.  BASES THÉORIQUES DU TRAITEMENT DU SIGNAL Définition [4] Soits(t)un signal déterministe, sa transformée de FourierSest définie par: S(f) = ∫ +∞ −∞ s(t).e −j2πft dt(1.11) Avectla variabletempsetflafréquence. Ce qui induit une dualité temps-fréquence, le passage de l’un des domaines à l’autre étant réalisable par symétrie vu que la transformée inverse de Fourier est donnée par: s(t) = ∫ +∞ −∞ S(f).e j2πft df(1.12) Intérêt de la transformation ainsi définie On démontre que l’une des conditions pour qu’une fonctionf(t)soit développable en série de fonctions orthogonales trigonométriques (série de Fourier) est qu’elle soit périodique, et pourtant dans la majorité des situations ce n’est pas le cas. Ici nous comptons montrer qu’à une fonction quelconque correspondra unetransformée de Fourier 2 . Pour cela, considérons un signal quelconques(t)et ciblons-y une région simple dont on connait l’expression analytique.  Supposons ensuite un signals 1 (t)qui serait une réplique à l’infini de la partie ciblée.s 1 (t)est par cela périodique de périodet f −t i avect f l’instant final de la partie ciblée ett i son instant initial. Suite à cette définition des 1 (t), il est évident qu’en prenantT(c’est-à-diret f −t i )infinie, cela revient à prendres(t). D’où: s(t) =   lim T→+∞ s 1 (t)(1.13) Nous savons pourtant que le développement des 1 (t)en série de Fourier existe car elle est périodique. Il sera donné mutatus mutandi par les rélations 1.9 en prenant en compte 1.10.  Par conséquent,la représentation fréquentielle des 1 (t)est un spectre des raies et la distance entre raies adjacentes vaut f 1 = 1 T étant donné que le développement en série de Fourier suggère que toutes les fréquences, 2 Évidemment, si ladite fonction est à carré sommable, c’est-à-dire si son carré a une intégrale finie. 11 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL dans le développement des 1 (t), sont multiples def 1 . La densité spectrale de raies sera alors donnée par, suite à la relation 1.10: S 1 n f 1 =T.S 1 n = ∫ T 2 −T 2 s 1 (t).e −j2πnf 1 t dt(1.14) Ainsi donc, les raies deviennent de plus en plus rapprochées à mesure queTcroît et à l’infini, la somme donnée en 1.9 se transforme en une intégrale etf 1 devient infinitésimale, ce qui fait que: s(t) =   lim T→+∞ s 1 (t) =   lim T→+∞ { +∞ ∑ n=−∞ 1 T .[ ∫ T 2 − T 2 (s 1 (t).e −j2πnf 1 t dt)].e j2πnf 1 t } = ∫ +∞ −∞ df.[ ∫ +∞ −∞ s(t).e −j2πft dt)].e j2πft = ∫ +∞ −∞ S(f).e j2πft df Ceci  exprime  très  clairement  qu’un  signal  s(t)  quelconque  peut  être  vu  comme  la  transformée inverse  de  sa  transformée  de  Fourier.   Cela  prouve  qu’il  existe,  sous  certaines  hypothèses(voir la note de bas de page précédente), une fonction fréquentielleS(f)exprimant le signals(t)dans le domaine des fréquences. C’est évidemment clair étant données les relations 1.11 et 1.12. Nous en déduisons que la transformée de Fourier représente,  à la limite,  la densité spectrale de raies telle que définie en 1.14.  D’où l’intérêt de cette transformée, généralisant le développement en série de Fourier, grâce à l’extension aux fonctions non périodiques. 1.2.3    Signaux aléatoires Les signaux déterministes, sont, comme nous venons de le voir, des fonctions telles que, à chaque instant, on dispose d’une règle permettant d’en évaluer la valeur.  Cette règle peut être spécifiée sous  forme  d’une  expression  mathématique,ou  d’une  équation  récurrente  ou  tout  autre  procédé de construction.  Les fonctions déterministes forment la base de l’analyse mathématique, mais la plupart de phénomènes que nous aurons à modéliser ne sont pas de cette nature. 12 sur 84  1.2.  BASES THÉORIQUES DU TRAITEMENT DU SIGNAL Figure 1.1: Visualisation d’un signal de parole sur une durée de 1/16 de seconde Considérons  le  signal  de  parole  représenté  à  la  figure  1.1.   Il  est  clair,  à  la  vue  de  ce  graphe, que l’on ne peut réduire ces observations à une fonction déterministe du temps.  Nous pourrions peut-être trouver une fonction déterministe qui approxime correctement les valeurs observées sur un  intervalle  de  temps[0,T],  mais  cette  fonction  ne  serait  pas  une  approximation  valable  de l’observation à l’extérieur de cet intervalle, et cette propriété perdurerait indépendamment de la durée[0,T]de l’observation.  Le graphe 1.1 contient un très grand nombre d’irrégularités et ces irrégularités ne semblent pas respecter une évolution prédictible. Les observations ont un caractère aléatoire, dans le sens où nous ne savons pas déterminer, pour un instant donné, quelle sera la valeur précise de la mesure.  Par contre, il est envisageable d’indiquer un intervalle de valeurs possibles et éventuellement de préciser comment ces valeurs sont distribuées à partir d’une certaine loi de probabilité. La bonne façon de décrire le comportement du phénomène est donc de spécifier, à chaque instant, une distribution de probabilité, permettant de décrire la vraisemblance de chaque observation. Dans le  langage  des  probabilités,  la  valeur  observée  sur  le  capteur  à  chaque  instant  est  une  variable aléatoire et son évolution au cours du temps, un processus aléatoire.  Cet exemple est le prototype d’une large classe de phénomènes qui conduit à adopter, pour les modéliser, la prise en compte de l’indéterminisme.[11] 13 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL Les signaux aléatoires sont donc en bref des signaux dont la valeur instantanée est imprévisible, ce qui implique qu’ils n’ont pas de représentation analytique.  Ces signaux seront étudiés grâce à certains paramètres statistiques qui leur sont associés.  C’est en fait ces types de signaux qui sont rencontrés dans notre contexte et nous en reparlerons de manière plus approfondie, mais implicite, dans les parties qui vont suivre. 1.2.4    Cas des signaux discrets Nous aborderons ici les signaux discrets de manière secondaire. C’est-à-dire, en les prenant comme le résultat de l’échantillonnaged’un signal continu, vu que c’est cet aspect qui nous intéressera dans le présent travail. Echantillonnage Echantillonner 3 un signal consiste à prélever,  à intervalle de temps régulier le plus souvent,  les valeurs prises par le signal.  Cela permet ainsi de voir le signal comme une suite de nombres et en permet le traitement par un ordinateur ou tout autre système de traitement des données.  C’est en fait le processus deconversion analogique-numérique. De manière formelle donc, si on prélève les valeurs du signal avec une périodeT e , on aura une suite des nombres valant{s(nT e )} n∈Z 4 qui constitue les échantillons du signal.  Par ce fait même, on est amené à songer au problème de reconstitution du signal à partir de ses échantillons.  Avant de considérer ce problème, définissons l’impulsion de Dirac qui nous sera très utile pour la suite du travail même si elle n’est pas physiquement réalisable de manière parfaite car elle est idéale. Impulsion de Dirac[10] :Un Diracδ(t)est par définitionune distributiondont le support (domaine non nul) est réduit au pointt= 0et d’intégrale valant 1. Formellement, il est défini par: ∫ +∞ −∞ δ(t)dt= 1(1.15) 3 C’est l’une de manières les plus simples de discrétiser un signal 4 De manière tout à fait générale, sans prendre en compte dans un premier temps la causalité (c’est-à-dire le fait selon lequel le temps doit uniquement être pris positif) 14 sur 84  1.2.  BASES THÉORIQUES DU TRAITEMENT DU SIGNAL Ce qui veut dire que cela correspond à un signal de durée nulle et de surface1.  C’est en fait une limite définie pratiquement par [3]: δ(t) = lim T→0      1 T pour| t T |< 1 2 0pour| t T |> 1 2 (1.16) De cela on peut montrer que: ∫ +∞ −∞ s(t).δ(t)dt=s(0)(1.17) Commeδ(t−τ)représente une impulsion de Dirac localisée plutôt enτ, on aura que: ∫ +∞ −∞ s(t).δ(t−τ)dt=s(τ)(1.18) On remarque que cette manipulation permet de prélever des valeurs des(t)en des instantsτbien précis. Plus généralement, introduisons un opérateur complet d’échantillonnage nommépeigne de Dirac(plusieurs Dirac étendus sur toute la droite des réels et espacés chaque fois deτsecondes). Il sera donné par: c(t) = +∞ ∑ n=−∞ δ(t−nτ)(1.19) c(t)permet de réaliser complètement l’échantillonnage d’un signals(t)car avec lui on prélève à intervalle de temps régulierτ(période d’échantillonnage), la valeur correspondante du signal.  En effet, le signal échantillonné est alors donné parla distribution: s e (t) = ∑ +∞ n=−∞ s(nT e )δ(t−nT e ) = ∑ +∞ n=−∞ s(t)δ(t−nT e ) =s(t) ∑ +∞ n=−∞ δ(t−nT e ) En bref, au vu du développement qui vient d’être fait, on a: s e (t) =s(nT e ) =s(nT e ).c(t) =s(t).c(t)(1.20) Echantillonner un signal revient donc juste à le multiplier par le peigne de Dirac. 15 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL Condition d’échantillonnage correct:La reconstitution du signal à partir de ses échantillons n’est  réalisable  que  sous  certains  critères  dont  lethéorème  d’échantillonnageditthéorème  de Nyquist-Shannon.    Ce  théorème  donne  une  condition  sur  le  support  du  spectre  (donné  par  la transformée de Fourier) du signals(t)pour reconstituers(t)à partir de ses échantillonss(nT e ). Ce théorème est ainsi énoncé: Théorème 1 (Nyquist-Shannon)Soits(t)un signal dont la transformée de FourierS(ω) 5 est à support dans[− π T e , π T e ]. Alorss(t)peut être reconstruit en interpolant sur ses échantillons s(t) = +∞ ∑ n=−∞ s(nT e ).h T e (t−nT e )(1.21) Avec h T =sinc( πt T ) = sin πt T πt T (1.22) Le théorème nous donne une condition surωpour que la reconstitution du signal à partir de ses échantillons soit possible.  Cette condition est en effet|ω| ≤ π T e ce qui veut dire que la fréquence devra vérifierf max ≤ f e 2 ⇒f e ≥2.f max .  En bref, le théorème 1 nous dit quela reconstitution du signal à partir de ses échantillons n’est possible que si la fréquence d’échantillonnagef e est supérieure ou égale au double de la fréquence maximale du spectre associé au signal. Transformée de Fourier Pour un signal discrets(nT e ), la transformée de Fourier est définie par[10]: S d (f) = +∞ ∑ n=−∞ s(nT e ).e −i.2πf.n (1.23) C’est au fait la transformée de Fourier de sa représentation sous forme de distribution telle que donnée par 1.20. On  sait  pourtant  qu’à  un  point  de  vu  réel  on  n’a  qu’un  nombre  finiNd’échantillons.   Pour prendre cela en compte, on définit la transformée de Fourier pour le cas dessignaux finis.  Elle 5 ωreprésentant la pulsation du signal, avecω= 2.π.f 16 sur 84  1.2.  BASES THÉORIQUES DU TRAITEMENT DU SIGNAL est évidemment donnée par: S d (f) = N−1 ∑ n=0 s(nT e ).e −i 2πn N f (1.24) Cela veut dire que la transformée inverse pour le cas des signaux discrets finis sera donnée par: s(nT e ) = 1 N N−1 ∑ k=0 S d (f).e i 2πk N n (1.25) Cette nouvelle définition( faite en 1.24) permet d’introduire en substance un algorithme de calcul rapidede  la  transformée  de  Fourier.   Cet  algorithme  est  largement  utilisé  par  les  processeurs spécialisés dans le traitement du signal. Transformée de Fourier Rapide:On parle souvent d’algorithme FFT. 6 C’est  une  méthode  pour  calculer  la  transformée  de  Fourier  discrète  d’un  signal  permettant  de réduire le temps de calcul.  Pour cela, on calcule la transformée sur une moitié de l’échantillon puis sur l’autre, réduisant ainsi la complexité de l’algorithme de recherche de la transformée. Plus précisément, cet algorithme réduit le nombre d’opérations nécessaires au calcul de latransformée de Fourier DiscrètedeN 2 avec la méthode ordinaire àNlog 2 Nopérations en utilisant la FFT.[3] Comme montré précédemment, c’est utilisé pour le cas de signaux discrets périodiques (signaux discrets finis périodisés comme va le montrer clairement l’explication de l’expression 1.30).  Ici nous n’en donnons qu’une vue sommaire étant donné que dans la suite du travail nous en reparlerons de manière plus claire quoi qu’implicite (voir le point 2.3.3). 6 Fast Fourier Transform (FFT) 17 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL 1.3    Filtrage 1.3.1    Introduction Introduisons juste une opération qui nous sera très utile dans la suite.  Filtrer un signal c’est lui faire  subir  une  transformation  bien  particulière  impliquant  l’extraction  d’une  partie  qu’on  juge utile.  En effet, la fonction d’un filtre est de modifier le contenu fréquentiel du signal d’entrée en transmettant intégralement le spectre du signal d’entrée sur certaines gammes de fréquences,  et en bloquant le signal d’entrée pour les autres fréquences.  Approximons un filtre par un système linéaire, homogène, invariant et stable[10]. Au point de vu formel ,le passage d’un signal à travers un filtre implique à ce qu’on lui fasse subir l’action d’un opérateur linéaire, homogène, invariant et stable. De ce fait,  considérons un filtre représenté par un opérateur linéaireL.   Au vu de ce que nous suggère  la  définition  de  l’impulsion  de  Dirac,  se  référant  plus  précisément  à  l’expression  1.18, nous voyons que: s(t) = ∫ +∞ −∞ s(u).δ(u−t)du(1.26) En lui appliquant l’opérateurlinéaireL, ce qui équivaut à le faire passer à travers un filtre,sans ignorer queδ(t) =δ(−t), on trouve: L(s(t)) =L{ ∫ +∞ −∞ s(u).δ(t−u)du}= ∫ +∞ −∞ s(u).L{δ(t−u)}du(1.27) Etant donné queLest aussi homogène en temps, on a que, siL{δ(t)}=h(t)alorsL{δ(t−u)}= h(t−u).  Nous voyons évidemment queh(t)représentela réponse du système considéré à une impulsion de Dirac 7 . C’est ainsi que 1.27 donne: L(s(t)) = ∫ +∞ −∞ s(u).h(t−u)du(1.28) 7 C’est-à-dire le signal observé à la sortie du système en ayant appliqué une impulsion de Dirac en entrée. 18 sur 84  1.3.  FILTRAGE C’est la définition duproduit de convolutiondu signal par la réponse impulsionnelle du filtre.  En bref, faire passer un signal à travers un filtre linéaire et homogène consiste à faire le produit de convolution du signal par la réponse du filtre à une impulsion.  Soit dit en passant, le produit de convolution des(t)parh(t)est donné par: s(t)? h(t) = ∫ +∞ −∞ s(u).h(t−u)du= ∫ +∞ −∞ s(t−u).h(u)du(1.29) La convolution discrète est définie de façon analogue (c’est-à-dire en remplaçant les signaux continus par les correspondants échantillonnés et les intégrales par des sommations discrètes).  Toutefois, pour  le  cas  des  signaux  finis,  on  définit  plutôtla  convolution  circulairecar  l’application  de  la relation précédente comme telle impliquerait la prise en compte des échantillons précédant le début de l’échantillonnage (valeur négative du temps). Pour cela, on considère que l’échantillon observé se répète à l’infini (périodisation des données récoltées). Donc, siNest le nombre d’échantillons, on devra faire tous les calculs surZ N . D’où la définition[10] de la convolution circulaire 8 : En posant ̇n=n modulo Ncar nous travaillons dansZ N , s(nT e )~h(nT e ) = N−1 ∑ p=0 s(  ̇pT e ).h[  ̇ ̂ (n−p).T e ](1.30) La définition du produit de convolution ainsi donnée nous permet de donner un complement fondamental au paragraphe 1.2.2.  Nous constatons en fait que les exponentiellese i2πft sont des vecteurs propresdes opérateurs de convolution qui sont sans doute des opérateurs linéaire (Lselon notre notation). En effet, appelonsL(•)l’opérateur de convolution défini parL(•)  =h(t)?•.  Nous aurons, à la lumière de la définition donnée par l’expression 1.29 alliée à la définition de la transformée de Fourier donnée en 1.11: L(e i2πft ) = ∫ +∞ −∞ h(u).e i2πf(t−u) du= (e i2πft ).H(f)(1.31) AvecH(f)la transformée de Fourier de la réponse impulsionnelleh(t)du filtreL.  On le nomme fonction  de  transfert  du  filtre  L.  En  toute  évidence,  les  exponentiellese i2πft sont  les  vecteurs 8 La seule qui soit utilisable en pratique car définie pour les signaux finis. 19 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL propres de l’opérateur linéaireLet les fonctions de transfert associées sont lesvaleurs propres correspondantes. Cela  dit,  il  est  tout  à  fait  clair  quec’est  plus  intéressant  d’exprimer  tout  signal  comme  somme d’exponentielles  complexes  pour  faciliter  les  calculs  en  cas  de  filtrage,  vu  que  ce  dernier  est exprimé  par  un  opérateur  dont  les  vecteurs  propres  sont  des  exponentielles.   D’où  l’intérêt  de la série de Fourier et par ricochet, la transformée de Fourier. 1.3.2    Prélude au filtrage adaptatif Nous ne traiterons pas du filtrage classique ni dans un cadre discret ni dans un cadre continu vu que ce ne sera vraiment pas utile.  Nous parlerons néanmoins dufiltrage adaptatifdont les concepts nous seront d’une grande utilité dans le cadre du présent travail. Pour cela, introduisons d’abord un filtrage particulier qui permettra d’aborder le filtrage adaptatif. Filtrage de Wiener[6] Ce type de filtrage est conçu pour séparer le signal d’avec le bruit comme tout autre type de filtrage. C’est-à-dire, séparer deux signaux à caractéristiques statistiques différentes. Soients(nT e )le  signal  d’excitation  que  nous  noterons  justes(n)par  commodité(comme  pour tous les autres signaux échantillonnés considérés dans ce paragraphe),y(n)signal qu’on voudrait obtenir à la sortie du système (entaché de bruit normalement),e(n)le bruit inconnu,y w (n)le signal modélisé à l’aide des paramètres du filtre,ε(n)l’écart entrey(n)ety w (n). Considérant que le signal passe par un système linéaire et homogène, nous aurons à la sortie un signal obtenu par convolution discrète du signal d’entrée avec la réponse impulsionnelle du filtre constituant le système considéré. Il existe donc les coefficientsw k tel que: y w (n) = p−1 ∑ k=0 w k .s(n−k)(1.32) Ce filtre est à réponse impulsionnelle finie de longueurp. Notez  que,  bien  que  non  mentionné,  cette  convolution  est  faite  avec  les  mêmes  considérations que  celles  mentionnées  pour  laconvolution  circulairedonnée  en  1.30  sauf  qu’ici,  nous  faisons abstraction  desmodulospour  ne  pas  alourdir  l’écriture.   Le  problème  ici  consiste  à  minimiser 20 sur 84  1.3.  FILTRAGE l’erreur d’estimation approximativeε(n) 9 . Nous allons utiliser les notations matricielles pour être général(en  ce  qui  concerne  le  nombre  de  coefficients  du  filtre  en  particulier).   La  relation  1.32 devient: y w (n) = p−1 ∑ k=0 w k .s(n−k) =W T .S(n) =S(n) T .W(1.33) AvecW= ( w 0 w 1 ···w p−1 ) T ; S(n) = ( s(n)s(n−1)···s(n−p+ 1) ) T et l’exposantTsur les vecteurs indique qu’on a fait la transposition. De là on tire: ε 2 (n) = [y(n)−S(n) T .W] 2 =y(n) 2 −2y(n)S(n) T W+W T S(n)S(n) T W(1.34) AppelonsΓ(W)la valeur moyenne des erreurs commises (avecμl’opérateur indiquant qu’on fait une moyenne).   C’est elle qu’il nous faudra chercher à minimiser pour espérer trouver un filtre optimal. Au vu du développement précédent nous aurons: Γ(W) =μ{y(n) 2 }−μ{2y(n)S(n) T W}+μ{W T S(n)S(n) T W}(1.35) DérivonsΓ(W)par rapport àW(ce qui correspond plus précisément à la recherche du gradient), ça donne: d[Γ(W)] dW =−2μ{y(n)S(n) T }+ 2μ{S(n)S(n) T }.W(1.36) Notons queμ{y(n)S(n) T }=          1 N ∑ N−1 n=0 y(n).s(n) 1 N ∑ N−1 n=0 y(n).s(n−1) . . . 1 N ∑ N−1 n=0 y(n).s(n−p+ 1)          avecNle nombre d’échantillons (Idem pour les autres moyennes, sachant que la moyenne d’une 9 On ditapproximativecar la sortie voulue n’est connue qu’à travers un transducteur (qui introduit également un bruit de fond). On minimise plutôt le carré de cette erreur pour des raisons tout à fait pratiques et calculatoires[14]. 21 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL matrice consiste à faire l’opération pour tous ses termes). Rappelons que: •μ{y(n)S(n) T }est un vecteur de dimensionp(vu quey(n)est un simple scalaire à chaque fois),on le nommevecteur d’intercorrélationet nous le noteronsR sy . •μ{S(n)S(n) T }est une matricep×pnomméematrice d’autocorrélationet nous la noterons R ss . Par conséquent, comme le minimum se retrouve en annulant le gradient, de l’expression 1.36 on tire l’équation donnant les coefficientsw k lorsque la dérivée est nulle, donc le filtre optimalW opt . On a: R ss .W=R sy ⇒W opt =R −1 ss .R sy (1.37) C’est l’équation normaledite deWiener-Hopf. On remarque évidemment qu’implémenter ce système aura un certain nombre de lacunes dont par exemple le temps de calcul des matrices ainsi que l’espace mémoire nécessaire surtout pour l’inversion de la matriceR ss .   Le problème le plus pertinent est quesi les signaux ne sont pas stationnaires,  ce  qui  est  pourtant  plus  fréquemment  le  cas  pour  les  signaux  réels,R ss etR sy évoluent au cours du temps. Cela veut dire qu’il faudra chaque fois résoudre à nouveau l’équation de Wiener-Hopf. Ce qui vient d’être montré justifie qu’il est impérieux de trouver un moyen efficace pour pouvoir résoudre récursivement et plus rapidement l’équation de Wiener-Hopf. Le filtrage adaptatif apporte une solution efficace à ce problème. 1.4    Traitement du signal audio Le traitement du signal audio est un domaine très vaste qu’on ne peut espérer aborder de manière exhaustive  dans  ce  document.   Premièrement,  cela  serait  une  perte  d’énergie  et  deuxièmement c’est une entreprise utopique.  Le son peut en fait subir divers traitements dont le filtrage.  Nous nous intéressons juste au filtrage ayant pour finalité l’annulation d’un écho présent dans le fichier 22 sur 84  1.5.  CONCLUSION PARTIELLE sonore. L’annulation d’écho est ardue si on l’étudie de manière détaillée, c’est-à-dire en voulant considérer tous les paramètres qui entrent en jeu.  En effet, pour annuler l’écho, il faut connaître précisément le milieu de propagation du son qu’on veut débarrasser de la perturbation en question. Le problème est qu’en premier,  une telle étude serait irréalisable car cela prendrait en compte un très grand nombre de paramètres.  En second lieu, les paramètres varieraient continuellement dans le temps (considérer pour cela le fait que, dans une enceinte, le changement de positon de l’un des éléments a une influence significative sur le comportement de ladite enceinte par rapport au signal à considérer; par exemple, le déplacement du microphone modifie directement la réponse de l’enceinte au signal et change par là même les calculs à faire pour annuler au mieux l’écho,...)  et cela rendrait juste l’entreprise irréaliste. Une  solution  plus  pratique  serait  d’aborder  le  problème  de  manière  globale,  en  considérant plutôt l’enceinte comme un système dont il suffirait juste d’étudier le comportement, grâce à un modèle équivalant, qui faciliterait le traitement par des algorithmes de calcul et diminuerait ainsi le nombre de paramètres pris en compte. Cela rendrait l’étude systématique réalisable en pratique. Au vu de ce dont nous avons parlé dans les sections précédentes, la solution est d’étudier la fonction de transfert associée à l’enceinte considérée et de recourir au filtrage adaptatif pour une prise en compte efficace de l’évolution temporelle du système. La stratégie d’annulation d’écho acoustique repose sur une estimation du canal acoustique de l’écho en identifiant la réponse impulsionnelle du bouclage acoustique qui est retranchée finalement du signal. Le filtrage étant adaptatif, les coefficient du filtre sont adaptés en fonction de l’erreur commise à chaque itération.  La réponse impulsionnelle du filtre varie au cours du temps et dépend du signal en entrée, de la séquence d’apprentissage et de l’algorithme d’optimisation choisi[1]. 1.5    Conclusion partielle Dans  ce  premier  chapitre,  nous  avons  premièrement  justifié  le  bien  fondé  de  l’application  de l’analyse  de  Fourier  au  traitement  du  signal  tout  en  pointant  les  résultats  intéressants  de  cette dernière discipline. Deuxièmement, nous avons montré de manière implicite à quel point le traitement numérique du 23 sur 84  CHAPITRE 1.  GÉNÉRALITÉS SUR LE TRAITEMENT DU SIGNAL signal est fécond et intéressant.  En effet, il facilite les manipulations à effectuer sur les signaux, en facilite l’étude théorique et surtout,  est plus adaptable aux divers systèmes de traitement des données existant, tout en étant moins sensible aux caprices de la nature (insensibilité du signal, dès qu’il est numérisé, aux perturbations de l’appareillage). Nous y avons également traité du filtrage adaptatif.  Pour cela, le concept a été illustré par le filtre de Wiener (filtre en général non utilisable pour le son car restreint aux signaux stationnaires), très crucial pour le développement du filtrage adaptatif proprement-dit qui est abordé dans le chapitre qui suit. 24 sur 84  Chapitre 2 ÉTUDE THÉORIQUE DU FILTRAGE DU SON 2.1    Introduction partielle Le traitement du signal sonore doit être minutieusement réalisé car les effets d’un mauvais traitement sont facilement perceptibles.  Un traitement particulier, le filtrage, avec comme objectif d’annuler l’écho  éventuel  du  signal  sonore,  fait  l’objet  de  ce  chapitre.   Nous  avons  principalement  opté pour  un  traitement  numérique  du  signal  à  cause  des  avantages  que  cela  procure  (allant  de  la facilité de traitement à la facilité de réplique des manipulations effectuées en passant par la grande disponibilité des concepts élaborés du domaine). C’est ainsi que nous présentons, en premier lieu, divers algorithmes de filtrage conçus principalement avec comme objectif d’aboutir à une possibilité d’annuler l’écho d’un signal sonore. En second lieu, nous abordons un type de transformation numérique particulier, la transformée en nombres de Fermat, qui constitue un substitut valable à la transformation de Fourier discrète dans des situations où il est impérieux de réduire la complexité de calcul des algorithmes élaborés. En  troisième  et  dernier  lieu,  nous  y  présentons  un  paradigme  très  essentiel  pour  une  réduction encore plus grande de la complexité des algorithmes élaborés pour le traitement des signaux.  Il s’agit du traitement par bloc des séquences numériques. 25  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON 2.2    Quelques algorithmes de filtrage adaptatif Le filtrage adaptatif a été introduit à la fin du premier chapitre.  En gros, ça consiste à réaliser le filtrage avec un filtre numérique qui change et s’adapte à l’enceinte selon un critère bien défini (un critère de minimisation du carré de l’erreur d’estimation par exemple). Pour cela nous avons parlé du filtre de Wiener qui, bien que n’étant utilisable qu’en cas des signaux stationnaires, nous permet d’aborder de manière claire et succincte le filtrage adaptatif. Ces algorithmes ont donc pour raison d’être l’approximation du filtre optimal de Wiener en cas des signaux non stationnaires. Il s’agit dufiltrage adaptatif proprement-dit. 2.2.1    Algorithme du gradient déterministe L’équation de Wiener-Hopf vue à la fin du précédent chapitre permet de retrouver le filtre optimal en résolvant un système depéquations àpinconnues. Cet algorithme permet de résoudre le système de manière itérative. Cela est fait en deux étapes: •  Choix du vecteurW 0 (Winitial). •  Obtention, à partir deW k , deW k+1 par incrémentation deW k dans la direction opposée au gradient de la fonction moyenne des erreursΓ(W)introduite en 1.35. Ainsi on aura[14]: W k+1 =W k − 1 2 λ∇[Γ(W)](2.1) Et pourtant on sait que, selon les notations adoptées, et suite à l’égalité 1.36 on a: −−→ gradΓ(W)≡∇[Γ(W)] = d[Γ(W)] dW =−2R sy + 2R ss W k (2.2) Par conséquent, l’algorithme du gradient déterministeest donné par[1]: W k+1 =W k +λ(R sy −R ss .W k )(2.3) 26 sur 84  2.2.  QUELQUES ALGORITHMES DE FILTRAGE ADAPTATIF La stabilité de cet algorithme est contrôlée par lepas d’adaptationλ, elle dépend également de la matrice d’autocorrélation du vecteur d’entrée[1]. En effet, si on nommeE k l’écart entreW k etW opt aprèskitérations, on aura: E k =W k −W opt (2.4) or selon l’équation de Wiener-Hopf, R ss W opt =R sy (2.5) Et selon l’algorithme du gradient déterministe on aura: W k+1 =W k +λ.(R ss .W opt −R ss .W k )(2.6) =W k +λR ss .(W opt −W k )(2.7) =W k −λR ss .E k (2.8) De ce qui précède on tire que E k+1 =W k+1 −W opt =E k −λR ss .E k (2.9) Ce qui montre de manière évidente de quelle façon la convergence de l’algorithme dépend du pas d’adaptation et de la matrice d’autocorrélation du vecteur d’entrée. La convergence de l’algorithmeest assurée par la contrainte[14]: 0λ 2 λ pro max (2.10) Avecλ pro représentant  une  quelconque  valeur  propre  de  la  matrice  d’autocorrélation  du  signal d’entrée etλ pro max la plus grande valeur propre de cette matrice. Notons  que  pour  des  faibles  valeurs  deλ(pas  d’adaptation),  le  temps  de  convergence  lui  est inversement proportionnel. Le choix deλest trop délicat et sa fixité ne garantit pas une vitesse de convergence optimale de l’algorithme. Par conséquent, il est nécessaire d’y trouver une solution. 27 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON 2.2.2    Algorithme du gradient stochastique(LMS)[1] Cet algorithme dit des moindres carrés ou LMS (Least Mean Square) consiste à minimiser l’erreur quadratique moyenne. C’est-à-dire en considérant son gradient au lieu de celui de la moyenne des carrés des erreurs (que nous avons nomméΓ(W)).  Cela résout approximativement le problème évoqué au paragraphe précédent pour l’algorithme du gradient déterministe,  problème de faible vitesse de convergence pour des très faibles valeurs du pas d’adaptation. Au fait, c’est plus adapté en pratique car on a très rarement∇[Γ(W)]. Ainsi, comme∇[ε 2 (n)] =∇[ε 2 k ] = 2ε k . ∂ε k ∂W =−2.ε k .S k 1 , on aura l’algorithme LMS donné par: W k+1 =W k − 1 2 λ∇[ε 2 (n)] =W k +λS k ε k (2.11) L’adaptation qui assure la convergence en moyenne quadratique la plus rapide est donnée par 2 : λ opt = 2 p.σ 2 (s) (2.12) Avecσ 2 (s)lavariance du signal d’entrée. On remarque que la convergence de l’algorithme LMS dépend de la statistique du signal d’entrée. Pour les signaux non stationnaires, il est difficile de suivre les variations du signal d’entrée avec l’adaptation du filtre par l’algorithme LMS et cela donne une convergence lente. D’où l’algorithme des moindres carrés récursif. 2.2.3    Algorithme des Moindres Carrés Récursif [1]&[14] Cet algorithme, leRecursive Least SquaresRLS, permet de suivre les signaux non stationnaires tout en ayant une vitesse de convergence convenable. Ici, au lieu de minimiser un critère statistique établi sur l’erreur commise en estimant un signal, on minimise, à chaque itération la somme des carrés des erreurs commises depuis l’instant initial. Dans ce cas,Γ(W)serait donné par 1 S k représente le vecteurS(n)à lak ieme itération etε k l’erreur(c’est un scalaire)ε(n)après le même nombre d’itérations. 2 Avec l’hypothèse d’unbruit blancen entrée 28 sur 84  2.2.  QUELQUES ALGORITHMES DE FILTRAGE ADAPTATIF Γ(W) = 1 k ∑ k n=0 ε 2 (n)mais vu que cela n’affecte pas le critère de minimisation, on prendra plutôt: Γ(W) = k ∑ n=0 ε 2 (n)(2.13) La  réponseWdu  filtre  adaptatifest  donc  fonction  des  échantillons  disponibles  et  non  d’une moyenne statistique générale.  Cela est très capital et constitue le noyau de cet algorithme.  Par analogie avec le filtre de Wiener on aura les relations 3 : R ss k W k =R sy k (2.14) AvecR ss k = ∑ k n=0 S n .S T n etR sy k = ∑ k n=0 S n .y(n). La réponse impulsionnelle du filtre sera donc modifiée à chaque itération.  Pour limiter le nombre des calculs, l’équation à utiliser, et qui constitue l’algorithme RLS, est la suivante: W k+1 =W k +R −1 ss k S k ε k (2.15) Et dans cette formule, le calcul deR −1 ss k se fait par: R −1 ss k = 1 δ [R −1 ss k−1 − R −1 ss k−1 .S T k .R −1 ss k−1 δ+S T k .R −1 ss k−1 .S k ](2.16) AvecR ss 0 = 1 δ .I p avecI p matrice unité de dimensionp×p,δ∈]0,1[etW 0 ≡vecteur nul de dimensionp. Cet algorithme converge plus vite que le LMS mais est plus difficile à mettre au point. Un palliatif à cette difficulté de mise en application est l’algorithme dit NLMS. 2.2.4    Algorithme LMS Normalisé (NLMS) [1]&[6] LeNormalized Least Mean Squaredit NLMS pallie à la complexité du RLS et, de manière directe et plus globale, à l’inadaptation du coefficient d’adaptation de l’algorithme LMS (Problème soulevé à la fin du paragraphe sur l’algorithme LMS). Cet algorithme consiste à normaliser le coefficient 3 C’est logique car les développements sontformellementidentiques 29 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON d’adaptationλdu LMS en prenant en compte l’énergie du signal d’entrée, ce qui réduit au minimum l’effet de l’influence de la variation de la puissance du signal. Cela rend la vitesse de convergence plus  ou  moins  uniforme  en  passant  d’une  itération  à  l’autre.   Donc  on  aura  la  même  formule d’itération que celle donnée pour l’algorithme LMS par l’équation 2.11, à la différence près que le coefficient d’adaptation est ainsi normalisé: λ k = λ S T k .S k +β (2.17) Par conséquent, l’algorithme NLMS est donné par l’équation: W k+1 =W k + λ S T k .S k +β .S k ε k (2.18) βest un facteur permettant de suivre rapidement les variations de l’énergie dans le signal d’entrée. La convergence de cet algorithme est garantie siλ k ∈]0, 2 λ pro max [.  L’intérêt de cet algorithme par rapport au LMS est qu’il est indépendant à la variance du signal d’entrée. Il faudra toutefois noter qu’ici aussi il y a dépendance de la convergence de l’algorithme à la statistique du signal d’entrée car la distribution des valeurs propres de la matrice d’autocorrélation du signal n’est pas modifiée. Pour les signaux stationnaires (lebruit blancpar exemple) ou non-stationnaires (signal deparole par exemple), le NLMS apporte une amélioration significative du taux de convergence suite à la normalisation. En ce qui concerne la mise en œuvre, cet algorithme est plus complexe que le LMS mais en pratique il fait partie des plus simples et plus efficaces algorithmes d’adaptation. 2.2.5    Algorithme Proportionné Normalisé (PNLMS)[1] Cet algorithme, le PNLMS, spécialement adapté à l’annulation d’écho, fait l’adaptation avec un taux  de  convergence  variable.   Il  a  plus  d’opérations  que  le  NLMS  mais  converge  plus  vite;  il découle du NLMS en remplaçant leλ k par: λ k = λG k S T k .G k .S k +β (2.19) 30 sur 84  2.2.  QUELQUES ALGORITHMES DE FILTRAGE ADAPTATIF AvecG k =diag[g k (0),···,g k (p−1)]qui est une matrice diagonale de typep×p. Et chaque fois,g k (n) = γ k (n) 1 p ∑ p−1 m=0 γ k (m) oùγ k (n) = max{ρν k ,|w k (n)|},n∈ {0,···,p−1}et ν k = max{δ,|w k (0)|,···,|w k (p−1)|}. Les termesρetδvalent respectivement 5 p et10 −2 . Donc l’algorithme PNLMS est donné par: W k+1 =W k + λG k S T k .G k .S k +β ·S k ε k (2.20) Néanmoins,  sous  certaines  conditions  dont  ladispersivité  de  la  réponse  du  filtre  adaptatif,  le PNLMS  devient  moins  rapide  que  le  NLMS.  La  solution  à  ce  problème  est  la  combinaison  de ces deux algorithmes. D’où l’algorithme nomméPNLMS++. 2.2.6    Algorithme PNLMS++ [1] Cet algorithme est moins sensible aux variations de la réponses impulsionnelle du filtre. Il consiste à combiner les deux précédent comme suit: •  Pour les itérations de numéro impair (kimpair), utilisation du PNLMS. •  Pour les itérations paires, on utilise le NLMS. Puis en fin de compte on mélange les résultats pour retrouver le filtre optimal. L’algorithme  ainsi  défini  est  celui  que  nous  utiliserons.   Toutefois,  il  subira  un  certain  nombre de modifications pour pouvoir devenir plus manipulable et plus optimal. Ces manipulations seront effectuées en faisant en sorte que les calculs puissent s’effectuer sur un processeur de traitement numérique des signaux sans oublier de prendre en compte le coût, la rapidité et la minimisation d’erreurs.   Ainsi,  nous devons chercher comment réaliser les opérations voulues en utilisant un processeur à virgule fixe,  pour ne pas avoir à gérer les erreurs d’arrondissement introduites par une manipulation maladroite duprocesseur à virgule flottante, tout en réduisant le coût d’achat du matériel (le premier processeur étant moins cher que le second).  Pour cela,  une transformation tout  à  fait  particulière  nous  sera  utile;  il  faudra  juste  qu’elle  ait  les  mêmes  propriétés  qu’une transformation de Fourier (surtout en ce qui concerne la convolution) et qu’elle rende les calculs 31 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON (le traitement) plus optimisé.  On le réalise grâce à la transformation qui fait l’objet de la section qui suit. 2.3    Transformée en nombres entiers (NNT) [1] La transformée en nombres entiers a la même forme que la transformée de Fourier discrète mais la supplante en ce sens que la partie imaginaire n’existe plus dans cette nouvelle transformation. La racine primitive considérée dans cette dernière (l’exponentiel complexe) étant remplacée par la racineM ieme de l’unité dans le corps de Galois[2] 4 considéré. Soitαcette racine. Nous avons donc que 〈α M = 1〉 q (2.21) Avec〈·〉 q signifiant que le calcul est faitmodulo q, c’est-à-dire dans un corps de Galois d’ordreq. La formule précédente est celle qui sera chaque fois utilisée pour retrouver la racine primitiveαdès queMetqsont choisis. La transformée en nombres entiers de chaque termex n d’une séquence de longueurMest alors donnée par: X k =〈 M−1 ∑ n=0 x n α nk 〉 q (2.22) Si la longueur de la transforméeMet l’ordreqdu corps fini (sachant que tout corps fini est corps de Galois)[15]GF(q)sont premiers entre eux, il existe alors(M −1 ) 5 tel que〈M.M −1 ≡1〉 q (ceci signifie queM.M −1 est congru à1moduloq) et là l’inverse de la transformée existe siM|(q−1) (ça veut dire queMdiviseq−1), elle est donnée par: x n =〈M −1 M−1 ∑ k=0 X k α −nk 〉 q (2.23) La transformée en nombres entiers n’existe pas toujours; les conditions de son existence sont les suivantes: 4 Chaque fois le corps de Galois d’ordreqsera notéGF(q)selon la notation anglaise standard. 5 Des algorithmes de calcul rapide de l’inverse d’un nombre dans un corps fini existent et seront présentés dès que nécessaire. 32 sur 84  2.3.  TRANSFORMÉE EN NOMBRES ENTIERS (NNT) [?] •  On doit avoir quepgcd(α,q) =pgcd(M,q) = 1ce qui implique que〈α M = 1〉 q (existence de la racine primitiveα). •  Siqest premier, il faut nécessairement queM|(q−1). Sinonq= ∏ k i=0 p m i i etM|pgcd(p i −1,p j −1)∀(i,j)∈ {1,2,...} 2 .  Aveci6=jetq= ∏ k i=0 p m i i représentant exactement la décomposition deqen facteurs premiers. •  Il faut quepgcd((α i −1),q) = 1siiest un diviseur deM,∀i∈{1,2,...,M−1} 2.3.1    Choix des paramètres de la transformation et Transformée en nombres de Fermat (FNT) De même que pour la transformée de Fourier discrète, la transformée en nombres entiers demanderait un  ordre  deM 2 multiplications  etM(M−1)additions.   L’opération  la  plus  complexe  ici  est évidemment  la  multiplication  par  des  puissances  de  la  racine  unitéα.   De  cela  découle  qu’il est  impérieux  de  faire  un  choix  judicieux  de  cette  racine  pour  réduire  la  charge  de  calcul  des processeurs à utiliser (il est ainsi plus malin de choisirαpuissance de 2 pour remplacer toutes les multiplications par des décalages de bit).  Le choix de l’ordreqdu corps de Galois dans lequel on  choisit  de  travailler  est  aussi  important  pour  une  programmation  plus  optimale.   Il  est  plus avantageux  de  prendre  un  ordreqégal  àun  nombre  de  Fermat.   C’est-à-dire  un  nombre  de  la forme2 b + 1avecbune  puissance  de  2  car  cela  rend  l’algorithme  très  optimal.   On  parle  de latransformation en nombres de Fermat.   Il s’agit d’une transformée en nombres entiers dans un corps d’ordre égal à un nombre de Fermat (il faut noter en passant que, seuls les 5 premiers nombres de Fermat sont premiers).  Ainsi on a queq= 2 2 t + 1avect∈N.  Cette transformée est celle que nous utiliserons vu qu’elle rend nos algorithmes plus optimisés. 2.3.2    Transformation en nombres de Fermat et arithmétique binaire Nous devons analyser la transformation sous cet angle (sous l’angle de l’arithmétique binaire) car cela permet de rester dans notre contexte vu que nos calculs seront exécutés par un processeur numérique fonctionnant sous le même principe. Une  FNT  (Fermat  Number  Transform)  de  longueur  quelconqueM=  2 t+1 a  juste M 2 log 2 M 33 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON multiplications etMlog 2 Madditions.   Nous voyons à quel point il est intéressant de travailler dans un corps de Galois ayant un ordreqégal à un nombre de FermatF t .  Le terme générateurα étant aussi essentiel à la réduction de la complexité de calcul, le choix d’unαdifférent d’une racine primitive (contrairement aux indications du début) mais égal à une puissance de2est intéressant en arithmétique binaire pour réduire la charge de calcul en cas de multiplication.  Les longueurs possibles sont alors données parM= 2 t+1−i et〈α= 2 2 i 〉 F t avec évidemment(i,t)∈N 2 tel que 06i < t.La longueur de séquence étant égale à une puissance de 2,〈M −1 =−2 2 t −1−(t−i) 〉 F t car en effet, 〈F t −1 = 2 2 t ≡−1〉 F t 〈2 2 t ·2 −(t−i+1) ≡−2 −(t−i+1) 〉 F t 〈M −1 = 2 −(t+1−i) ≡−2 2 t −1−(t−i) 〉 F t (2.24) D’où les formules de transformation seront données, à la lumière des relations 2.22 et 2.23, par: X k =〈 2 t+1−i −1 ∑ n=0 x n ·2 〈2 i nk〉 M 〉 F t x n =〈−2 2 t −1−(t−i) 2 t+1−i −1 ∑ k=0 X k ·2 〈−2 i nk〉 M 〉 F t (2.25) On peut doubler la longueur des séquences tout en conservant unαpuissance de2.  Pour cela il suffit de poser quei=−1. Ainsi la racineαest solution de la relation de congruence〈α 2 = 2〉 F t . Donc, α 2 =〈2 = (−1)·2·(−1) =−2·(−1)〉 F t =〈−2·2 2 t = 2 2 t−1 (1−1−2·2 2 t−1 )〉 F t =〈(2 2 t−2 ) 2 ((2 2 t−1 ) 2 −2·2 2 t−1 + 1 2 )〉 F t =〈(2 2 t−2 (2 2 t−1 −1)) 2 〉 F t 34 sur 84  2.3.  TRANSFORMÉE EN NOMBRES ENTIERS (NNT) [?] Par  conséquent,α≡ √ 2a  un  sens  et  existe  dans  le  corps  de  GaloisGF(q)≡GF(F t )si  et seulement sit≥2car du développement précédent on tire clairement que: 〈α≡ √ 2 = 2 2 t−2 ·(2 2 t−1 −1)〉 F t (2.26) Donc,( √ 2 n ) =    〈2 n 2 〉 F t pournpair 〈2 n−1 2 ·2 2 t−2 (2 2 t−1 −1)〉 F t sinon . Commecette transformation admet que la transformée du produit de convolution de deux séquences est égale au produit simple(terme à terme) des transformées des séquences convoluées, elle requiert Mlog 2 Mopérations simples (décalage de bit, additions) etaucune multiplication. Cela est génial vu que comparativement, la transformée de Fourier discrète requiert, hormis les opérations simples, un nombre de multiplications complexes de l’ordre de M 2 log 2 M 2 . 2.3.3    Version rapide de la FNT De même qu’il existe une version rapide de la transformée de Fourier (la FFT comme dit au premier chapitre), il en existe aussi une pour la transformée en nombres de Fermat. Le principe est le même etc’est la même chose du point de vu formel. Il consiste à diviser la séquence en 2 séquences plus petites, ce qui réduit la complexité des calculs. L’implantation de cet algorithme sur un processeur de calcul porte le nom d’implantation Butterfly. Une transformée en nombres de Fermat de dimensionM=  2 n avec0≤n≤b=  2 t peut être calculée en utilisant le principe de l’algorithme FFT de la manière suivante: 〈X k = M−1 ∑ n=0 x n α nk = M 2 −1 ∑ n=0 x 2n α 2nk + M 2 −1 ∑ n=0 x 2n+1 α (2n+1)k 〉 F t 〈X k = M 2 −1 ∑ n=0 x 2n α 2nk +α k M 2 −1 ∑ n=0 x 2n+1 α 2nk =G k +α k H k 〉 F t (2.27) Avec évidemmentG k etH k des vecteurs représentant respectivement les transformées en nombres de Fermat des séquences{x 2n } M 2 −1 n=0 et{x 2n+1 } M 2 −1 n=0 de longueur M 2 . Comme〈α M = 1〉 F t ⇒〈α k+ M 2 =−α k 〉 F t car〈α M = 1 = (−1) 2 = (α M 2 ) 2 〉 F t . 35 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON En fin de compte,    X k =G k +α k H k X k+ M 2 =G k −α k H k k∈[0, M 2 −1]⊂N. Ce découpage de la séquence en 2 parties égales peut être repété pour décomposer la transformée de longueurM= 2 b en{4,8,···, M 2 parties. Toute FNT peut ainsi être calculée grâce àlog 2 (2 b ) =b décompositions. Comme Mb 2 transformées de longueur de séquenceM= 2. Il faudra à chaque étape 2 opérations simples et une multiplication. D’où le total exigeraMlog 2 M additions et M 2 log 2 Mmultiplications pour réaliser une FNT. 2.3.4    La convolution rapide Le calcul de convolution de deux séquences deMéchantillons exige l’application de3transformées en nombre entiers de longueur2M, les séquences étant étendues par des zéros. Soit deux séquences de longueurMchacune donnée par{x(n)} M−1 n=0 et{h(n)} M−1 n=0 , la convolution de ces deux séquences par le principe de la convolution rapide consiste à procéder de la manière suivante: Algorithme 1 (Convolution rapide par NNT)•  Formation de deux séquencesx 1 etx 2 à partir de la séquence{x(n)} M−1 n=0 par:                x 1 (n)   =    x(n)0≤n < M 2 0 M 2 ≤n < M x 2 (n)   =    0M≤n < M 2 x(n) M 2 ≤n < M •  Définirh 1 eth 2 de manière identique. •  Calculer les transformées en nombres de Fermat des séquences ainsi construites. SoientX 1 ,X 2 ,H 1 etH 2 les transformées correspondant respectivement aux séquences construites ci-haut. Ne pas oublier que: X(k) =〈X 1 (k) +X 2 (k)〉 F t et idem pourH(k)(2.28) •  Former trois nouvelles séquences notées{U},{V}et{W}de la manière suivante: 36 sur 84  2.3.  TRANSFORMÉE EN NOMBRES ENTIERS (NNT) [?]          U(k)=〈H(k)•X(k)〉 F t V(k)=〈H 1 (k)•X 1 (k)〉 F t W(k)   =〈H 2 (k)•X 2 (k)〉 F t avec le•représentant une multiplication terme à terme des séquences. •  Calculer les transformées inverses de ces dernières séquences.  Elles seront notées:u(n), v(n)etw(n)respectivement. •  Soity=x∗hle résultat de la convolution des séquencesxeth. On aura enfin que: y(n) =                v(n)pour0≤n < M 2 〈u(n)−w(n)〉 F t pour M 2 ≤n < M 〈u(n−M)−v(n−M)〉 F t pourM≤n < 3M 2 w(n)pour 3M 2 ≤n <2M A la différence du calcul de convolution usuel qui demande dans le pire des cas 3 transformées en nombres entiers de longueur2M, cet algorithme exige plutôt7transformées de longueurM et  cela  est  plus  avantageux  en  terme  de  minimisation  du  nombre  d’opérations  complexes  (les multiplications). 2.3.5    Multiplication optimale des matrices [8] Le produit de deux matrices représente le plus souvent une charge de calcul assez importante. Une méthode  qui  a  des  performances  nettement  supérieures  à  celles  de  la  méthode  usuelle,  surtout pour  des  matrices  de  grande  dimension,  existe  et  consiste  à  transformer  la  multiplication  des matrices en un produit de convolution (convolution des séquences composées des coefficients des deux matrices).   Ce dernier pouvant finalement être rapidement et facilement calculé grâce aux algorithmes de calcul rapide du produit de convolution dont celui présenté à la section précédente, après une FNT calculée suivant ce qui est montré à la section 2.3.3. Algorithme 2 (Multiplication rapide des matrices)SoientA(a ij )etB(b ij )deux matrices carrées de dimensionM. Leur produitC(c ij )peut s’écrire sous forme polynomialeR(x) =P(x)Q(x), les coefficients dePetQétant trouvés respectivement par: 37 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON    p i+jM =a ij q M(M−1−i+jM) =b ij Avec0≤i,j < Met tous les coefficients non définis égaux à0. Et par multiplication simple des polynômes ou par convolution 6 des séquences qui sont constituées respectivement par les coefficients dePetQon trouveR(x). Les coefficients du produit deAetB sont alors donnés par: c ij =r M 2 −M+i+jM 2 Une convolution faite après FNT tout en appliquant les méthodes rapides et optimales mentionnées dans les parties précédentes permet de réaliser le produit des matrices avec moins deM 3 opérations complexes (multiplications) comme c’est le cas pour une multiplication par la méthode classique. Cette manière de faire sera très utile pour la suite car, avec ce qui est introduit à la section suivante on se rend copte qu’on aura plus besoin de manipuler régulièrement des matrices et des produits de convolution. 2.4    Traitement par bloc des algorithmes d’annulation d’écho 2.4.1    Introduction L’annulation d’écho sera réalisée par un filtre adaptatif.  Le filtre à utiliser se doit d’être le plus rapide (vitesse de convergence) et le moins complexe (complexité de calcul) possible.  Le filtre PNLMS++tel que présenté précédemment est le candidat idéal à ces deux exigences. Nous n’allons plus nous intéresser à l’adaptation des coefficients du filtre à chaque itération comme dans  les  paragraphes  précédents  car  cela  représente  une  charge  assez  importante  en  terme  de calcul et de mémoire.L’algorithme sera plutôt modifié de manière à l’optimiser au maximum tout en  conservant  les  traitements  appliqués  aux  données  (séquences).   Pour  cela,  l’adaptation  sera effectuée plutôt chaque aprèsNtermes de la séquence considérée. Il faudra néanmoins noter que, bien que cette méthode est très avantageuse quant à la réduction 6 Une  multiplication  des  polynômes  est  équivalente  à  un  produit  de  convolution  des  séquences  formées  par  les coefficients des dits polynômes rangés selon le degré croissant. 38 sur 84  2.4.  TRAITEMENT PAR BLOC DES ALGORITHMES D’ANNULATION D’ÉCHO du nombre de multiplications, elle a le défaut d’accroître considérablement le nombre d’opérations simples (les additions et les décalages de bit). Pour palier à cet inconvénient et rendre les algorithmes encore  plus  efficaces,  on  applique  une  méthode  dite  dusliding  généraliséqui  permet  d’éviter plus  particulièrement  certaines  redondances  dans  les  calculs,  rendant  ainsi  les  algorithmes  plus optimisés (cela pourra être pris en compte lors de l’implantation des algorithmes et non au cours de cette présentation théorique). Prenant toujours référence à la section sur les filtres adaptatifs, nous devons définir certains concepts vu  que  les  quantités  qui  étaient  auparavant  des  scalaires  à  chaque  adaptation  deviennent  alors des  vecteurs.   Etant  donné  que  l’adaptation  survient  chaque  aprèsNéléments  de  la  séquence considérée, tous les blocs (sauf éventuellement le dernier) contiennentNtermes pris dans l’intervalle [kN,kN+N−1]aveckdésignant le numéro du bloc (de l’itération).  Les termes de bloc sont donc les suivants: y k = ( y(kN)y(kN+ 1)···y(kN+N−1) ) T y w k = ( (y w (kN)y w (kN+ 1)···y w (kN+N−1) ) T ε k =y k −y w k = ( ε(kN)ε(kN+ 1)···ε(kN+N−1) ) T S k = ( s(kN)s(kN+ 1)···s(kN+N−1) ) T . La définition que nous venons de donner pourS k est plus valable si on se base sur une compréhension brute du concept des blocs. Néanmoins, une manière plus pratique de la définir est de poser qu’elle vaut :S k = ( s(kN−p+ 1)s(kN−p+ 2)···s(kN+N−1) ) T , ainsi on prend également en compte la longueur du filtre (pour notre cas, le filtre est de longueurp). La sortie qui est obtenue par convolution du signal en entréeS(n)par la réponse impulsionnelle du filtre sera finalement écrite de manière globale sur le bloc comme suit: y w k =         s(kN)s(kN−1)···s(kN−p+ 1) s(kN+ 1)s(kN)···s(kN−p+ 2) . . . . . . . . . s(kN+N−1)s(kN+N−2)···s(kN+N−p)                 w k (0) w k (1) . . . w k (p−1)         =R k W k 39 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON AvecR k unematrice  de  Toeplitzde  taillep×Netpla  longueur  du  filtre  comme  mentionné au premier chapitre.  Tout en considérant qu’un terme notéw k (n)correspond, à la lumière de la notation du premier chapitre, au coefficientw n du filtre à lak ieme itération. 2.4.2    Algorithmes proprement-dits [1] Pour  le  cas  le  plus  simple,algorithme  LMS  par  blocsnotéBLMS(Bloc  Least  Mean  Squares), l’erreur  quadratique  calculée  sur  un  bloc  de  données  sera  donnée  par:ε T k ε k au  lieu  deε 2 (n) comme c’était le cas auparavant.  Ce qui est évident vu que c’est une généralisation de la fonction élévation au carré. Sachant queS(j)répond à sa définition donnée à la fin du premier chapitre, les coefficients du filtre seront mis à jour grâce à: W k+1 =W k − 1 2 λ∇(ε T k ε k ) =W k − 1 2 λ ∂(ε T k ε k ) ∂W k =W k − 1 2 λ ∂( ∑ (k+1)N−1 j=kN (ε(j)) 2 ) ∂W k =W k − 1 2 λ ∂( ∑ (k+1)N−1 j=kN (y(j)−S(j) T W k ) 2 ) ∂W k =W k − 1 2 λ{−2 (k+1)N−1 ∑ j=kN (y(j)−S(j) T W k )(S(j) T )} =W k − 1 2 λ{−2 (k+1)N−1 ∑ j=kN S(j)ε(j)} =W k +λR T k ε k Et la formule ainsi obtenue peut être réécrite sous la forme d’une convolution car: R T k ε k = (k+1)N−1 ∑ j=kN S(j)ε(j)} ⇒(R T k ε k ) i = (k+1)N−1 ∑ j=kN ε(j)s(j−i) =ε(i)∗s(−i) 40 sur 84  2.4.  TRAITEMENT PAR BLOC DES ALGORITHMES D’ANNULATION D’ÉCHO Avec0≤i≤(p−1)pour ne pas dépasser la longueur du filtre et∗le produit de convolution discrète. Les éléments du vecteur d’erreurε k de longueurN, lesε(kN+m)avec0≤m≤N−1peuvent également être exprimés sous forme d’une convolution car on sait que: ε(kN+m) =y(kN+m)−y w k (kN+m) =y(kN+m)− p−1 ∑ i=0 w k (i)s(kN+m−i) =y(kN+m)−w k (m)∗s k (m) Avecs k (m)désignant le terme numéromdans le bloc numérokdu signal d’entrée. Dans ce qui précède il faut remarquer que normalement la convolution a été arrêtée à la longueur du filtre (p). Les deux manipulations qui précèdent seront perpétuées partout où cela sera possible, pour transformer les expressions sous la forme de produit de convolution afin d’appliquer toutes les belles propriétés de la convolution discrète, en terme de réduction du temps de calcul principalement, par utilisation de la transformée rapide (en nombres de Fermat pour notre cas). Grâce au même raisonnement, nous pouvons obtenir les formules de mise à jour des coefficients du filtre pour tous les autres algorithmes. L’algorithme qui nous intéresse étant lePNLMS++, à cause de ses propriétés présentées au premier chapitre, la version par blocs (le BPNLMS++) sera donnée par: •  Pour la partie paire (correspondant auBNLMS), W k+1 =W k + λ R ss (k) +β (ε k ∗S −k )(2.29) AvecR ss (k)la fonction d’autocorrélation du signal, soitS k ∗S −k . •  Pour la partie impaire (correspondant auBPNLMS), W k+1 =W k + λG k G k R ss (k) +β (ε k ∗S −k )(2.30) AvecS −k = ( s(kN+N−1)s(kN+N−2)···s(kN−p+ 1) ) T 41 sur 84  CHAPITRE 2.  ÉTUDE THÉORIQUE DU FILTRAGE DU SON Dans la mise en oeuvre pratique de ces algorithmes, tous les éléments seront adaptés de manière à avoir des formes correctes (par ajout des zéros aux vecteurs le nécessitant et suppression de l’erreur ainsi introduite, à la fin des calculs). REMARQUES: Il faudra impérativement noter que les formules ici mentionnées, qui de toute évidence correspondent respectivement au processus de mise à jour des coefficients du filtre dans le cadre duBNLMSet duBPNLMS, ne sont que formelles.En effet, au sens mathématique strict elles ne seront pas valables au vu des dimensions des termes (pour s’en convaincre, il faut noter qu’après formatage des résultats,R ss (k)est de taillep×1,on ne prend que sespderniers termes, donc on ne peut pas l’additionner àβqui est un scalaire mais aussiG k étant une matrice de taillep×p, on aura aussi queG k R ss (k)est de taillep×1et donc même conclusion).Cette notation formelle signifie juste que, pour chaque itération, on calculer le vecteur de taillepdu numérateur et l’autre du dénominateur et le termew k (i)correspondra au résultat obtenu en appliquant la formule mais ayant considéré uniquement les termes numéroide chaque vecteur présent (au numérateur et au dénominateur).Nous y revenons plus clairement lors de l’élaboration de l’algorithme. 2.5    Conclusion partielle Ce chapitre a abordé le processus de filtrage numérique de manière à converger vers un filtre bien adapté à l’annulation d’écho sonore. L’algorithme choisi et adapté pour cet effet est lePNLMS++ qui est comme une synthèse des avantages de divers algorithmes conçus pour la cause précisée. Néanmoins, envisager une implantation plus optimale sur les processeurs de traitement du signal, nous permet de remarquer l’utilité d’introduire la transformée en nombres de Fermat, qui permet de réduire la consommation en ressources qui serait inutilement énorme en cas d’un traitement numérique  classique.   Le  traitement  dans  le  domaine  de  Fermat,  allié  à  une  manipulation  des séquences par bloc de données, permet de réduire de manière assez sensible la complexité de calcul des algorithmes mis au point.   L’introduction de la transformation en nombres entiers,  nous est d’une importance capitale car c’est sur base d’elle que seront écrits, en langage de programmation dédié, nos algorithmes, si on veut les embarquer. 42 sur 84  Chapitre 3 CONCEPTION DU FILTRE MIXTE ADAPTÉ 3.1    Introduction partielle Ce chapitre vient clore notre travail.  Nous envisageons y présenter sommairement les éléments qu’il serait normalement nécessaire de concevoir pour réaliser un système de traitement numérique complet du signal.  Toutefois, étant donné que notre travail consiste juste à élaboré le filtre, nous nous limiterons, pour les autres blocs de traitement du signal, à la description du minimum nécessaire pour comprendre l’ensemble.  Ça veut dire que nous ne concevrons pas les autres parties, sinon nous nous serons totalement écarté du cadre de ce travail.   Nous allons considérer que le reste est un acquis à ajuster seulement à la partie concernant le traitement que nous allons élaborer et implémenter sousMatlab. 3.2    Structure globale du système Notre système fonctionne selon la procédure classique de traitement du signal.  De ce fait, il sera constitué des blocs habituels. C’est ainsi que la structure globale du système est telle que représenté sur la figure qui suit: 43  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Figure 3.1: Chaîne typique de traitements du signal On y remarque que minimalement, un système de traitement complet devra contenir des éléments qui réalisent ces5étapes.  A l’arrivée du signal il sera d’abord adapté au système, d’où le filtre anti-repliement.  Ensuite, comme le traitement est numérique, il sera converti sous forme binaire par le Convertisseur Analogique-Numérique.  Par après il subira un traitement adéquat (le filtrage numérique  pour  notre  cas),  puis  la  reconversion  sous  forme  analogique  grâce  au  convertisseur Numérique-Analogique. Finalement, on terminera la mise en forme du signal en le lissant grâce au filtre de lissage. 3.2.1    Filtre anti-repliement Le filtre anti-repliement est nécessaire pour faire respecter le théorème de Shannon, il évite le repliement de spectre auquel on assiste normalement si la condition de Nyquist-Shannon est violée par sous-échantillonnage (c’est-à-dire si la fréquence d’échantillonnage est inférieure au double de la fréquence maximale du signal échantillonné).  Ce phénomène est pourtant de règle et n’est en rien une exception vu que normalement, les signaux réels ne sont jamais, stricto sensu, à support fréquentiel borné. Donc, les spectres réels s’étendent toujours jusqu’à l’infini (l’amplitude du signal tendant bien sûr vers0sans jamais s’annuler).  Par conséquent, la condition de Nyquist-Shannon ne peut jamais être strictement respectée pour un signal réel.  D’où l’importance d’un filtre anti- repliement. Le filtre n’est en effet qu’un passe-bas permettant de limiter la fréquence maximale prise par le signal à traiter pour que nous soyons sûr de choisir une fréquence d’échantillonnage valable (valeur non infinie). 44 sur 84  3.2.  STRUCTURE GLOBALE DU SYSTÈME Figure 3.2: Absence de repliement[7] Figure 3.3: Présence de repliement[7] Il est donc indispensable d’intercaler un filtre anti-repliement avant le convertisseur permettant le passage de l’analogique au numérique.   C’est un filtre analogique passe-bas de fréquence de coupureFe/2(dans l’idéal). En pratique, le filtre passe-bas parfait n’existe pas et le repliement du filtre numériquef > Fe 2 est partiellement éliminé.  La qualité se paie par l’utilisation d’un filtre anti-repliement élaboré (ordre élevé).[16] Ce filtre passe-bas doit avoir les caractéristiques suivantes: [12] 45 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ -  Fréquence de coupure égale àF max ; -  Variations de gain minimales dans la bande passante ; -  Pente la plus raide possible après la coupure (Ordre élevé); -  Atténuation hors bande passante adaptée au nombre de bitsnde la numérisation. En  effet,  les  signaux  parasites  au-delà  deF max vont  être  atténués  par  le  filtre  anti-repliement et se retrouver dans la bande du signal.   Pour que ces parasites repliés ne soient pas gênant,  il suffit que leur niveau soit suffisamment faible c’est à dire d’un niveau inférieur à la résolution du convertisseur analogique-numérique. En conclusion, le filtre anti-repliement ne supprime pas le phénomène de repliement, mais atténue le signal replié au point de le rendre négligeable. 3.2.2    Convertisseurs Analogique-Numérique et Numérique-Analogique Depuis une trentaine d’années, le traitement numérique des données prend le pas sur les approches purement analogiques. Le recours au numérique permet en effet un stockage aisé de l’information, une excellente reproductibilité des traitements, la possibilité de développer relativement aisément des fonctionnalités complexes, une réduction des coûts de production, etc. L’interface nécessaire entre le monde analogique et un traitement numérique donné est réalisé par des  convertisseurs  analogique–numérique  (CAN,  ouADCpourAnalog  to  Digital  Converteren anglais) et numérique–analogique (CNA, ouDACpourDigital to Analog Converter). Le rôle d’un CANest  de  convertir  un  signal  analogique  en  un  signal  numérique  pouvant  être  traité  par  une logique numérique, et le rôle d’unCNAest de reconvertir le signal numérique une fois traité en un signal analogique.[18] Pour réaliser laconversion analogique-numérique, trois opérations sont nécessaires.  Il s’agit, par ordre d’apparition, de l’échantillonnage, de la quantification et du codage.  L’échantillonnage du signal doit être fait en tâchant de respecter le théorème de Shannon.Le processus est clairement illustré grâce à la figure qui suit: 46 sur 84  3.2.  STRUCTURE GLOBALE DU SYSTÈME Figure 3.4: Echantillonnage-Quantification-Codage[18] On distingue deux grandes familles de CAN basées sur deux approches différentes du processus d’échantillonnage : lesCAN classiquesdont la fréquence d’échantillonnage est telle que le spectre du signal converti occupe quasiment toute la bande de Nyquist (Nyquist Rate ADC) et les CAN à sur-échantillonnage (Oversampling ADC) dont seule une partie réduite du bruit de quantification (erreur de quantification) affecte le signal converti.[18] Si la fréquence d’échantillonnage est bien choisie, la seule erreur introduite au cours du processus de numérisation résulte de l’approximation faite en codant un nombre infini de valeurs analogiques par  un  nombre  fini2 n de  niveaux  binaires.   Le  numérique  n’est  donc  évidemment  pas  parfait, seulement on peut, en augmentant le nombre de bitsn, diminuer autant qu’on veut l’erreur introduite par la numérisation.  Avec , comme objectif, de maintenir l’erreur de quantification en dessous du seuil de sensibilité de l’oreille humaine. Plus le nombre de bits augmente, plus le rapport signal sur bruitSNRs’améliore.[12] Après cette transformation, les données se dirigent vers un processeur de traitement numérique. Un traitement fait en virgule fixe est de toute évidence la plus indiquée pour être plus optimal.  Il doit être considéré en cas d’implantation des algorithmes sur DSP vu que les ressources sont limitées. Le convertisseur numérique-analogique permet de communiquer d’un système numérique vers un système analogique. Il convertit donc un nombre binaire en une tension (ou un courant) qui lui est proportionnel. L’entrée est numérique et se note formellementN= (b n−1 ...b 1 b 0 ) 2 avec lesb i ∈{0,1},Nl’entrée numérique  etnla  résolution  numérique  (nombre  de  bits).   La  sortie  est  analogique  et  dans  un premier temps, la conversion analogique-numérique se fait simplement paru S =Nq+u S min avec u S la tension à la sortie du convertisseur etqlequantum ou résolution analogique(en Volts).[17] 47 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Par ce qui précède on aura de toute évidence une sortie discrète du fait que les conversions sont réalisées à chaque arrivée d’un échantillon.  Pour pallier à cela, le CNA a un système permettant le maintient de la tensionu S en sa sortie, jusqu’à l’arrivée d’un nouvel échantillon.  On obtient alors en sortie, unsignal analogique en escalier.  Il a ainsi un spectre fréquentiel comportant des fréquences supérieures à la fréquence maximale du signal de base.  Cela est dû aux changements brusques observées pour une forme en escaliers. Il est par conséquent important delisserce signal en supprimant les composantes de fréquence élevée pour obtenir finalement un signal à variations majoritairement moins brusques et/ou plus proche du signal analogique désiré. 3.2.3    Filtre de lissage C’est le dernier élément de la chaîne de traitement du signal. Comme dit dans la section précédente, il permet de lisser le signal en escalier qu’on obtient à la sortie du CNA. Le lissage se fait par suppression des fréquences supérieures à la fréquence maximale du signal d’entrée (moitié de la fréquence d’échantillonnage). Il s’agira donc d’un filtre passe-bas comme pour le premier élément de la chaîne (filtre anti-repliement). On en illustre l’importance grâce aux figures qui suivent [18] : Figure 3.5: Positionnement du filtre de lissage Figure 3.6: Processus complet de conversion N/A (signaux associés) 48 sur 84  3.2.  STRUCTURE GLOBALE DU SYSTÈME 3.2.4    Traitement Une  fois  les  données  numérisées,  elles  sont  finalement  traitées.   Le  traitement  se  passe  dans un processeur de traitement numérique.  Il existe une multitude de processeurs, et également un grand nombre d’architectures utilisées.   Néanmoins,  certains processeurs sont optimisés pour le traitement du signal.  Il s’agit desDSP(Digital Signal Procesing) dont on a sommairement parlé dans les parties précédentes. LeDSPest un microprocesseur optimisé pour exécuter des applications de traitement numérique du signal (filtrage, extraction des signaux, etc.)  le plus rapidement possible.  Ils sont utilisés dans la plupart des applications du traitement numérique du signal en temps réel.  On les retrouve ainsi dans les modems, les téléphones mobiles, les appareils multimédia, les récepteurs GPS, les chaînes de traitement de son,... En bref, partout où l’on reçoit un signal complexe que l’on doit modifier à l’aide du filtrage. UnDSPfournit des instructions usuelles comme la multiplication, l’addition, la soustraction, etc. Mais son jeu d’instructions est élaboré de manière à exécuter des opérations très courantes dans des algorithmes de traitement du signal les plus usuels. Des nombreux algorithmes de traitement du signal ont par exemple besoin d’effectuer rapidement des multiplications suivies d’une addition. LesDSPaccélèrent ces genres de calcul en fournissant des instructions capables de multiplier deux nombres et d’en additionner un troisième en une seule fois (en un cycle d’horloge). CertainsDSParrivent même à réaliser plusieurs opérations complexes de ce genre en un seul cycle d’horloge. La majorité desDSPcalculent exclusivement avec des nombres à virgule fixe.  L’absence d’unité en nombre flottant rend le composant meilleur marché tout en permettant une grande vitesse de traitement des données. CertainsDSPpossèdent cependant des unités de calcul en virgule flottante pour des applications exigeant une large dynamique des valeurs ou une grande précision relative des résultats.   Ils peuvent être combinés avec d’autres composants dans le même boîtier.   C’est ainsi par exemple qu’on a, dans un même, leDSPet les convertisseurs (Convertisseur Analogique- NumériqueetNumérique-Analogique).Dans un appareil équipé d’un DSP, la vitesse d’exécution des calculs dans ce dernier est généralement la partie déterminante de la vitesse d’exécution du travail effectué par la machine.[19] 49 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Au vu de ce que nous venons de montrer dans le paragraphe précédent, leDSPest la solution indiquée pour un système embarqué complet.   Pour notre cas,  sachant que nos ordinateurs sont équipés des processeurs assez rapides qui arrivent à réaliser le traitement des données avec une vitesse suffisante pour que nous testions de fonctionnement réel de notre système, nous réaliserons dans un premier tempsnotre système en nous servant de l’ordinateur. Les caractéristiques utiles de ce dernier sont précisées dans la section traitant de l’élaboration de l’algorithme. Il s’avère alors indubitable que,  comme le traitement que nous mettons au point est un filtrage, avec comme objectif l’annulation d’écho sonore,  cette partie (le traitement) suffit pour tirer des conclusions pertinentes sur le système et pour envisager (projet à long terme selon la demande ou le besoin) finalement une production du matériel conçu selon ce travail.  Donc, le filtre anti- repliement et autres éléments de la chaîne de traitement du signal ne seront pas conçus par nous mais nous nous servirons de ceux de la carte son de l’ordinateur (pour le test du fonctionnement) et ceux qui seraient couplés au boîtier du DSP (en cas de production matérielle). 3.3    Élaboration de l’algorithme et présentation du système Nous allons réaliser l’annulation d’écho par utilisation de l’algorithmeBPNLMS++, les coefficients seront donc réinitialisés selon le principe illustré par les formules 2.29 et 2.30 AvecS k etS −k définis respectivement par S k = ( s(kN−p+ 1)s(kN−p+ 2)···s(kN+N−1) ) T et S −k = ( s(kN+N−1)s(kN+N−2)···s(kN−p+ 1) ) T . Les deux sont tous de longueurN+p−1prenant directement en compte la longueurpdu filtre ainsi que la tailleNdes blocs d’échantillons. Ce qui précède nous fait immédiatement remarquer que les deux vecteurs ont les mêmes termes mais arrangés en ordre inverse.   Mathématiquement,  ça correspond à dire queS −k s’obtient en multipliantS k par une matrice carrée de dimensions adéquates et dont tous les termes sont nuls sauf la diagonale secondaire qui sera totalement constituée des1. 50 sur 84  3.3.  ÉLABORATION DE L’ALGORITHME ET PRÉSENTATION DU SYSTÈME 3.3.1    Élaboration de l’algorithme d’apprentissage Soit à utiliser un processeur à16bits, ce qui correspond au dernier nombre premier de Fermat, le cinquième pour être exact.  En effet, si nous choisissonsb=  16, ça veut dire que dans la forme canonique des nombres de Fermat introduits à la sous-section 2.3.1 nous avons quet= 4, soit donc que le nombre de Fermat en question est2 2 4 + 1 = 2 16 + 1 = 65537 =F 4 . Ce choix est judicieux vu que nous comptons faciliter les calculs par transformée en nombres de Fermat (FNT), car là on a bel et bien un nombre de Fermat valable (un nombre premier en l’occurrence et en plus le plus grand nombre premier de Fermat connu). Aussi, étant donné ce que nous avons considéré à la sous-section 2.3.2, entre autres les définitions selon lesquellesM=  2 t+1−i et〈α=  2 2 i 〉 F t , en choisissant par exemplei=−2on obtient une longueur de transformationM= 128et〈α= 4 √ 2〉 F 4 = 4938. Voulant conserver le fait selon lequel on ne peut pas transformer une séquence de longueur supérieure à la longueurMde la transformée,  nous devons faire remarquer que vu queS k etS −k sont de longueurN+p−1, on doit impérativement respecter la conditionM≥N+p−1ou alors prendre N+p−1< Mpour le compléter ensuite jusqu’à la longueurM. Alors, pour choix on peut prendre par exempleN= 64etp= 64(deux moitiés deM).  Sur base de cela, nous aurons les étapes de l’algorithme : 1°)Acquisition et préparation du signal à manipuler; 2°)Écriture des fonctions qui réalisent la FNT et son inverse Après extraction du signal, nous pourrons être amenés à effectuer une transformée en nombres de Fermat sur le vecteur constitué des échantillons.  Pour cela, nous devons réaliser ce qui suit: 1.  Fonction réalisant la transformée de la séquence de longueur fixéeM; 2.  Fonction réalisant la transformée inverse d’une séquence de longueur identique; 3°)Écriture d’une boucle devant réaliser l’apprentissage (adaptation du filtre) : 1.  Fenêtrage d’un bloc de64échantillons du signal d’entrée; 51 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ 2.  Construction  globale  du  signal  d’entrée  à  considérerS k en  faisant  précéder  les64 échantillons dep−1derniers échantillons provenant du signalS k−1 ; 3.  Vu qu’ainsi on aS k de longueurM= 128termes en le complétant, calcul de sa FNT par appel de la procédure correspondante; 4.  Initialisation des coefficients du filtre (comme notre filtre est de longueurp= 64, nous prendrons pour filtre initial, un filtre dont tous les64termes sont tous nuls); 5.  Complément des coefficients du filtre par des 0 par ajout deM−ptermes nuls pour obtenir un vecteur pouvant subir une FNT de longueurM; 6.  Calcul de la FNT du vecteur ainsi formé par appel de la procédure correspondante; 7.  Calcul du produit terme à terme de ces deux FNT précédemment obtenus (Transformée deW k complété multipliée par la transformée deS k ; 8.  Calcul  de  la  FNT  inverse  du  produit  obtenu  par  appel  de  la  procédure  dédiée  (cela donne le produit de convolution des coefficients du filtre par le signal d’entrée.  Donc on obtienty w k dont seuls lesNderniers termes correspondent auxNvrais échantillons formanty w k ; 9.  Formatage dey w k par élimination desM−Npremiers termes inutiles.  Pour cela, on multiplie une matrice de tailleN×Mdont lesM−Npremiers termes de chaque ligne sont tous nuls et l’autre partie est semblable à une matrice unitaire de tailleN(c’est-à- dire que tous ses termes diagonaux sont égaux à1) par le vecteury w k obtenu après la transformation inverse de l’étape précédente ; on obtient après cette multiplication, une matriceN×1qui correspond effectivement au vrai vecteury w k recherché; 10.  Calcul du vecteur d’erreur par comparaison (une différence) de la valeur trouvéey w k avec la valeur désiréey k ; 11.  Complément de ce vecteur par des 0 jusqu’à obtenir un vecteur de longueurMcar c’est bien cela la longueur de la transformée que nous avons choisi d’utiliser (on aura ajouté alorsM−Ntermes nuls); 12.  Calcul de la FNT du vecteur d’erreur ainsi complété; 52 sur 84  3.3.  ÉLABORATION DE L’ALGORITHME ET PRÉSENTATION DU SYSTÈME 13.  Construction du vecteur imageS −k en multipliant le vecteurS k déjà bien formaté et complété par une matrice de tailleM(matrice carrée donc) dont tous les termes sont nuls à part ceux de la diagonale secondaire qui sont tous égaux à1.  La multiplication de cette dernière matrice parS k a donc pour effet de renverser l’ordre de ses termes; 14.  Calcul de la FNT de ce vecteur image; 15.  Calcul du produit terme à terme de ce vecteur image transformé avec le vecteur d’erreur transformé; 16.  Calcul  de  la  transformée  inverse  du  résultat  ainsi  obtenu  (la  réponse  correspond  au vecteurε k ∗S −k dont seuls lespderniers termes forment le vrai vecteur recherché; 17.  Formatage du résultat obtenu en lui appliquant une matrice que nous nommonsE, de dimensionp×Mpour obtenir au final un vecteur de taillep. Pour cela on multiplie la matrice construiteEpar le résultat obtenu à l’étape précédente. Cette matrice en est en fait une dont lesM−ppremiers termes de chaque ligne sont nuls et l’autre partie est comme une matrice carré de taillep×pdont les termes de la diagonale principale sont tous égaux à1et les autres sont tous nuls (matrice unitaire de taillep); 18.  Calcul du produit terme à terme du vecteur d’entréeS k transformé avec son vecteur imageS −k aussi transformé; 19.  Calcul de la transformée inverse du précédent produit (cela nous permet d’obtenir la fonction d’autocorrélation du signal d’entréeR ss (k) =S k ∗S −k qui est aussi réduit à sespderniers termes en lui appliquant la matriceEcomme cela a été fait à l’étape17; 20.  Construction de la matrice diagonaleG k de taillep×ptel qu’elle fut définie à la sous- section 2.2.5; 21.  Calcul des vecteursG k .(ε k ∗S −k )etG k .R ss (k); 22.  Réinitialisation des coefficients du filtre en appliquant l’algorithmeBNLMS(tout en tenant compte de la dernière remarque de sur l’état formel des formules duBNLMSet duBPNLMS). On appliquera donc précisément 53 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ W k+1 (i) =W k (i) + λ [R ss (k)](i)+β [(ε k ∗S −k )](i) ; 23.  Réinitialisation des coefficients du filtre en appliquant l’algorithmeBPNLMSen tenant également compte du fait que la formule s’exprime réellement par : W k+1 (i) =W k (i) + λ [G k R ss (k)](i)+β [G k (ε k ∗S −k )](i) ; 24.  Construction du vrai vecteur des coefficients du filtre en prenant tous les termes impairs égaux aux termes impaires correspondants du vecteur trouvé à l’étape précédente et les termes pairs aux termes pairs correspondant du vecteur trouvé à l’étape22(ainsi on vient de réinitialiser le filtre en appliquant leBPNLMS++); 25.  Relance de la boucle jusqu’au nombre d’itérations voulu. 4°)Fin de la boucle, renvoi des valeurs figées des coefficients du filtre en les formatant si nécessaire 3.3.2    Présentation du système réel Après cette étape d’apprentissage, on obtiendra les coefficients du filtre qui modélisent au mieux la réponse impulsionnelle de l’enceinte considérée. Ainsi, comme mentionné à la sous-section 1.3.1, le signal d’écho obtenu dans l’enceinte considérée peut bel et bien aussi s’obtenir,dans les mêmes conditions, par convolution du signal d’entrée avec le vecteur formé des coefficients du filtre ainsi construit.  Cette solution est cruciale et déterminante pour l’efficacité et la rapidité 1 des systèmes de communication. En effet, annuler directement l’écho grâce à un modèle numérique équivalent à l’enceinte utilisée, nous permet : •  De ne pas avoir à empêcher un locuteur de parler lorsque l’autre parle; 1 Sans ignorer les autres avantage d’un système d’annulation d’écho tout court. 54 sur 84  3.4.  IMPLÉMENTATION DE L’ALGORITHME ET SIMULATIONS •  De simuler l’écho venant de n’importe quelle source (sélectionner un signal en particulier dont on veut extraire l’écho) pour ensuite le soustraire du signal qu’on compte transmettre. Ce qui serait carrément impossible sans cette modélisation de la réponse de la salle. Le système se résume donc ainsi : Deux interlocuteurs ayant chacun un combiné de communication,  équipés chacun d’un système d’annulation d’écho,  sont dans deux enceintes différentes (et dans la même enceinte à la limite ;  mais c’est sans intérêt).  On procède premièrement à une phase d’apprentissage où, un son de quelques  secondes  est  émis  par  le  haut-parleur  des  combinés  de  chaque  locuteur  et  le  filtre  de chaque combiné est mis à jour. Ensuite s’établit la communication entre les deux interlocuteurs où, chaque fois que l’une des sources émet un signal, on en soustrait la modélisation de l’écho du signal venant de l’autre. Ainsi, aucun des deux ne peut réentendre sa voix à travers son haut-parleur. Cela résout le problème d’écho acoustique associé au système de communication considéré. Dans  la  suite  (pour  les  essais)  nous  n’allons  considérer  qu’un  interlocuteur.Pour  cela,  le  signal venant de l’autre sera juste appelésignal lointainet celui qui vient du locuteur présent dans la salle d’expérimentation sera ditsignal local. Cela nous permettra de réaliser l’adaptation du filtre et de vérifier si le filtre obtenu modélise bel et bien l’enceinte prototype. 3.4    Implémentation de l’algorithme et simulations Dans cette section, nous allons écrire l’algorithme élaboré dans la section précédente en langage Matlab (qui a évidemment une syntaxe proche duCet qui nous permettra aumoins de réaliser des expérimentations de manière moins complexe). Utilisant un processeur à virgule flottante (celui de l’ordinateur), nous n’allons pas nous cramponner sur le formatage du signal d’entrée.  Par conséquent, la transformation de Fourier va suffire pour avoir un aperçu de l’algorithme global. 3.4.1    Traitement brut des données Ce traitement revient à réaliser l’adaptation des coefficients du filtre à la manière dont la théorie a été élaborée au début du second chapitre. Donc sans optimiser le temps de calcul avec un traitement 55 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ par blocs. Nous allons donc réaliser un algorithme d’adaptation évoluant échantillon par échantillon et non par blocs.  Ceci est utile pour remarquer la précision de ce traitement malgré le manque de robustesse et la charge de calcul.  L’algorithme élaboré pour cet effet est ,sousMatlab, donné par l’annexe .1 . La compilation de ce code a duré12.424632secondes(valeur donnée par le chronomètre intégré à Matlab en excluant la prise du son) pour un signal d’entrée pris enregistré sur40secondes(voir la ligne12de ce code) pour pouvoir pousser très loin l’adaptation (jusqu’à20850tours de boucle principaux comme on le voit à la ligne43de ce code). Le signal d’entrée était: Figure 3.7: Signal d’entrée utilisé Pouri= 20850tours de boucles (voir la ligne43du code), nous avons obtenu les coefficients du filtre représentés en fonction des numéros d’échantillons par: 56 sur 84  3.4.  IMPLÉMENTATION DE L’ALGORITHME ET SIMULATIONS Figure 3.8: Valeurs des64coefficients du filtre Sous cette forme,  on a remarqué que la convergence du filtre est relativement lente bien que le résultat soit plus parfait. On va le montrer clairement dans les sections suivantes. 3.4.2    Traitement par bloc des données L’algorithme utilisé et qui suit les étapes décrites précédemment (à la section 3.3.1 qui concerne l’élaboration de l’algorithme conseillé pour un implantation sur DSP) est donné à l’annexe .2 . Il est très important de signaler que bien que les étapes décrites lors de l’élaboration textuelle de l’algorithme soient faites pour le cas d’un traitement par FNT etpour un processeur à virgule fixe fonctionnant sous16bits, le fait que nous ayons utilisé un processeur sous64bitset la transformée de Fourier est tout à fait admissible.  L’algorithme textuel a juste été élaboré pour considérer le cas le plus général et pour nous guider dans l’implémentation, surtout que cela permet également d’optimiser à la fois les coûts et l’exploitation des ressources. On remarque des simplifications drastiques en ce qui concerne le formatage des vecteurs.  C’est ainsi qu’à la ligne73de ce code (annexe .2 ), on remarque qu’au lieu de multiplier le vecteur à128 57 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ termes par une matrice particulièreE(comme nous le suggère le point3en son étape17de la sous- section 3.3.1 sur les étapes de l’algorithme),Matlabnous permet d’extraire très simplement ces derniers termes. C’est le cas également aux lignes62et77(annexe .2 toujours) où les manipulations sont grandement simplifiées par rapport à ce que nous proposions au préalable.  Ces propositions ont tout de même le mérite d’être plus générales comme méthode et donc utilisables même quand le langage ne permet pas une manipulation très simple des matrices. La compilation de ce code a duré8.219884secondes(valeur donnée par le chronomètre intégré à Matlab en excluant la prise du son) pour le même signal d’entrée que précédemment (voir la ligne 12de ce code et la figure 3.7) pour pouvoir pousser très loin l’adaptation. Ainsi on a obtenu en fonction des numéros d’échantillons le filtre suivant: Figure 3.9: Les64coefficients du filtre 2 Le filtre obtenu ici par contre est moins précis mais s’obtient plus vite à cause de la grande vitesse de convergence des algorithmes de traitement par bloc. Normalement, suite aux manipulations des vecteurs, on obtient unfiltre renversé et décalécomme on le voit sur cette figure: 58 sur 84  3.4.  IMPLÉMENTATION DE L’ALGORITHME ET SIMULATIONS Figure 3.10: Les64coefficients du filtre 2 non formatés De cela on obtient très aisément la courbe recherchée trouvée à la figure 3.9 grâce au formatage des coefficients, réalisé avec le bout de code de la ligne112(annexe .2 ) donné par: w=((ones(1,64)) * (mean(w))-(w))/(mean(w)); Pour réaliser ce formatage, il suffit de détecter la valeur moyenne (on écritmean(w)).  Pour notre signal d’entrée, le filtre non formaté avait pour moyenne(13.5)(voir la figure 3.10). 3.4.3    Essais comparés Essayons, pour le même signal d’entrée (figure 3.7), de trouver les coefficients du filtre pour les deux cas en considérant différentes valeurs dei(nombre d’itérations qu’on voit aux lignes43des codes qu’on a aux annexes .1 et .2 ) et observons l’évolution des coefficients. Nous prendrons des valeurs inférieures à20850car pour une boucle allant trop au delà, nous risquons de dépasser la longueur maximale des vecteurs. Notons que le signal d’entrée formaté sous forme vectorielle était de taille1764352échantillons. 1°)  Pouri= 10000on obtient: 59 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Figure 3.11: Coefficients du filtre 1 pour 10000 itérations Coefficients  du  filtre,  obtenus  aprèsi=  10000itérations  par  l’algorithme  de  traitement échantillon par échantillon (ce qui a duré6.073958secondes).   On a pratiquement le bon filtre. Figure 3.12: Coefficients du filtre 2 pour 10000 itérations Coefficients du filtre, obtenus aprèsi= 10000itérations par l’algorithme de traitement par blocs d’échantillons (ce qui a duré3.920202secondes, presque la moitié du temps nécessaire au traitement brut précédent).  C’est pratiquement les mêmes coefficients que ceux obtenus pour le cas où le nombre d’itérations était20850. 2°)  Pouri= 1000on obtient: 60 sur 84  3.4.  IMPLÉMENTATION DE L’ALGORITHME ET SIMULATIONS Figure 3.13: Coefficients du filtre 1 pour 1000 itérations Coefficients du filtre, obtenus aprèsi= 1000itérations par l’algorithme de traitement échantillon par échantillon (a duré0.658588secondes).  Malgré que la forme est bonne, les coefficients sont très faibles. Figure 3.14: Coefficients du filtre 2 pour 1000 itérations Coefficients du filtre, obtenus aprèsi=  1000itérations par l’algorithme de traitement par blocs  d’échantillons  (pour  un  temps  de  calcul  de0.426955secondes).   Malgré  un  léger décalage vers le haut, on a obtenu pratiquement le filtre final. 3°)  Pouri= 100on obtient: 61 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Figure 3.15: Coefficients du filtre 1 pour 100 itérations Coefficients, obtenus aprèsi= 100itérations par l’algorithme de traitement échantillon par échantillon (durée de compilation de0.079877secondes).  Malgré que la forme commence déjà à se dessiner, les coefficients sont très faibles (c’est un filtre à coefficients quasi nuls). Figure 3.16: Coefficients du filtre 2 pour 100 itérations Coefficients du filtre,  obtenus aprèsi=  100itérations par l’algorithme de traitement par blocs  d’échantillons  (ce  qui  a  duré0.057885secondes).   La  forme  commence  déjà  à  se dessiner mais les coefficients sont encore trop décalés vers le haut. 4°)  Pouri= 10on obtient: 62 sur 84  3.4.  IMPLÉMENTATION DE L’ALGORITHME ET SIMULATIONS Figure 3.17: Coefficients du filtre 1 pour 10 itérations Au début de l’adaptation du filtre , les coefficients sont très mauvais. Cette figure représente l’adaptation du filtre échantillon par échantillon après10itérations. Figure 3.18: Coefficients du filtre 2 pour 10 itérations Au début de l’adaptation du filtre, les coefficients sont très mauvais. Pour10itérations, avec le traitement par blocs, on n’a toujours pas même l’esquisse des valeurs souhaitées. 4°)  Il y a également deux valeurs particulières pour les deux implémentations, les valeurs dei auxquels les filtres auront presque complètement atteint les coefficients escomptés.  Après plusieurs essais on obtient: •i= 4370pour le filtre en traitement brut (filtre 1) 63 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Figure 3.19: Coefficients du filtre 1 pour 4370 itérations L’algorithme de traitement échantillon par échantillon donne des très bons coefficients mais après beaucoup d’itérations (i= 4370) et trop de temps (3.296686secondespour notre cas). •i= 400pour celui du traitement par blocs (filtre 2) Figure 3.20: Coefficients du filtre 2 pour 400 itérations L’algorithme de traitement par bloc permet d’obtenir après seulement0.173829secondes, des coefficients très proches des bonnes valeurs (bien que n’étant pas très affinés, ils 64 sur 84  3.5.  ANALYSE DES RÉSULTATS ET EXPLICATION DE L’IMPLANTATION SUR DSP sont assez bons pour que le passage du signal à travers un filtre ayant des telles valeurs nous donne presqu’exactement la sortie souhaitée). 3.5    Analyse  des  résultats  et  explication  de  l’implantation  sur DSP 3.5.1    Analyse des résultats Ce que nous venons d’obtenir à la sous-section 3.4.3 est très crucial pour remarquer la puissance du traitement par blocs.  On remarque très bien que le filtre élaboré par un traitement échantillon par échantillon n’évolue pas très vite vers les vraies valeurs, et se dégrade très vite avec la réduction du nombre d’itérations, tandis que le traitement par blocs est à la fois rapide (en terme de temps de calcul) et converge plus vite vers le filtre optimal. Dans le code , à la ligne61pour le premier (annexe .1 ) et64(annexe .2 ) pour le second, on a spécifié que le résultat attendu à la sortie du filtre devait être, pour tester le fonctionnement de notre algorithme, le même signal mis à l’entrée (donc l’erreur est minimisée de manière à ce que le signal d’entrée soit le même que celui obtenu après avoir traversé le filtre). Or nous savons très bien que pour avoir une sortie identique à l’entrée, la réponse impulsionnelle du filtre doit être une impulsion toujours.  Et évidemment, le filtre optimal que nous avons obtenu s’approche d’une impulsion comme on le voit très bien aux figures 3.8 et 3.9.Le premier est évidemment plus proche d’une impulsion que le second bien qu’obtenu grâce à un algorithme moins robuste. En effet, le premier algorithme, qui nous permet d’obtenir des meilleurs coefficients, converge très lentement et se dégrade très vite quand on diminue le nombre d’itérations; en plus il prend trop de temps pour donner les résultats. Pour s’en convaincre, voir les figures 3.11 puis 3.13 ensuite 3.15 et finalement 3.17, on remarque très bien dans peu de temps que l’amplitude des coefficients du filtre se dégrade très vite et que les coefficients eux aussi deviennent de plus en plus écartés des bonnes valeurs jusqu’à la dégradation complète à la dernière figure, la figure 3.17). Le second, celui obtenu grâce à l’algorithme de traitement par blocs et dont l’évolution des coefficients est représentée en ordre par les figures 3.12 puis 3.14 ensuite 3.16 et finalement 3.18, est moins précis mais nettement plus robuste que le premier. En effet, il demande peu de temps de calcul et se dégrade très lentement 65 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ quand on diminue le nombre d’itérations.Malheureusement, il nécessite d’importantes corrections d’erreurs. En bref, la comparaison des résultats représentés par les figures 3.19 et 3.20 nous montre nettement la supériorité du traitement par blocs par rapport au traitement échantillon par échantillon.   On remarque  très  clairement  la  nécessité  d’une  implantation  par  blocs  pour  avoir  un  traitement  en temps réel (voir les commentaires afférentes aux deux figures précédentes). 3.5.2    Explication de l’implantation sur DSP L’implantation sur DSP à virgule fixe et sous16bitsexige l’adaptation de l’algorithme élaboré (celui de l’annexe .2 ) de manière à ce qu’on puisse réaliser le même traitement. Pour cela, on n’a que deux choses particulières à réaliser: •  Formater le signal d’entrée de manière à l’adapter au processeur si nécessaire et •  Ecrire une fonction qui réalise la transformée en nombres de Fermat tel qu’on l’a décrite et opltimisé dans les parties précédentes ainsi que son inverse.  En utilisant juste les formules données. Après  avoir  réalisé  cela,  le  code  sera  exactement  le  même  que  celui  qui  a  été  élaboré  pour  le traitement par blocs en se basant sur l’esquisse qui a été faite de l’algorithme au point 3.3.1.  Le formatage quant à lui, quand il est nécessaire, se réalise facilement par des manipulations simples (multiplications suivies des arrondissements).  Cette dernière méthode introduit évidemment une erreur mais dès qu’on envisage de l’utiliser, on peutétudier la technique adaptée pour la réduction de  l’erreur  qui  serait  introduite  à  la  fois  par  ce  formatage  et  celui  réalisé  durant  le  filtrage. Après avoir ainsi adapté l’algorithme, il faudra alors l’écrire enassembleurpour adapter le code à l’architecture du DSP choisi ou carrément en langageC, laissant au compilateur le soin d’optimiser le code en l’adaptant au DSP (C’est la solution la plus simple en fait). 3.6    Annulation d’écho Notre travail a consisté principalement à élaborer le filtre qui peut s’utiliser pour annuler l’écho dans un système de communication. Nous allons montrer la meilleure annulation que nous avons pu 66 sur 84  3.6.  ANNULATION D’ÉCHO obtenir avec les filtres conçus. Il s’agit de l’annulation grâce au filtre implémenté par l’algorithme en annexe .1 qui est le plus précis (l’autre est le plus indiqué en cas d’embarquement mais nécessite d’astucieuses corrections d’erreurs).  Les coefficients de ce filtre sont donnés par la figure 3.8, il correspond presqu’exactement à une impulsion. On obtient d’abord la sortie et l’annulation par le codeMatlabsuivant 2 : 1-sortie=conv(w,myrecordings); 2-echoTransmis=(sortie(1:1608500))-(myrecordings(1:1608500)); Ce bout de code a été exécuté à part, mais après l’exécution de celui d’adaptation pour pouvoir utiliser  les  mêmes  variables.   Il  réalise  en  sa  première  ligne,  la  convolution  du  vecteur  formé par  les  coefficients  du  filtre  avec  le  signal  d’entrée  (c’est  le  filtrage  si  on  pose  que  le  filtre  est approximativement  linéaire).   A  la  deuxième  ligne  on  réalise  alors  la  suppression  d’écho  pour le cas où le signal n’est pas trop modifié par l’enceinte (comme nous l’avons posé pour tester la validité de nos codes). On a considéré1608500échantillons pour ne pas risquer de dépasser la taille totale des vecteurs car le signal en entrée avait environs1700000échantillons.  Dans cette figure (a) Echo résiduel après filtrage. (b) Echo sans filtrage. Figure 3.21: Démonstration de l’annulation d’écho (la figure 3.21),  nous comparons l’écho reçu après filtrage du signal à envoyer à l’interlocuteur lointain, avec l’écho qu’il recevrait si le filtage n’était pas préalablement réalisé. Plus précisément, 2 Se référer à l’annexe .1 pour remarquer quemyrecordingreprésente le signal en entrée 67 sur 84  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ on réalise un filtrage pour modéliser l’écho, puis on le soustrait du signal à transmettre pour que l’interlocuteur lointain ne perçoive pas sa voix dans le signal qu’il recevra. Ainsi, en observant très bien les échelles des axes de ces figures, on remarque une atténuation très importante de l’écho. En effet, l’écho qui persiste après filtrage (voir la figure 3.21a) est environ ledixièmede celui qui est perçu lorsqu’aucun filtrage n’est réalisé 3.21b.  Et on y voit très bien que pour ce dernier cas (absence de filtrage) l’interlocuteur lointain va entendre exactement son signal lui revenir. D’où la nécessité du filtrage. 3.7    Conclusion partielle Dans  cette  dernière  partie,  nous  avons  tout  d’abord  décrit  les  éléments  principaux  nécessaires à  l’élaboration  d’un  système  annulateur  d’écho  sans  prendre  en  compte  le  fait  qu’il  peut  être incorporé à un système déjà mis en place.  C’est ainsi que nous avons vu en passant la chaîne de traitement du signal et finalement nous nous sommes focalisé sur la partie concernant le traitement proprement-dit par filtrage. Cela nous a conduit à élaborer l’algorithme d’adaptation des coefficients du filtre de manière détaillée sousMatlaben vu d’en évaluer le fonctionnement et l’adéquation aux résultats attendus. Et bien évidemment, nous nous attendions à un filtre semblable à une impulsion et nous l’avions obtenu de très près comme le prévoit la théorie.  Nous avons finalement terminé par une illustration de l’annulation d’écho et une explication de l’implantation de l’algorithme sur DSP en système indépendant. 68 sur 84  CONCLUSION GÉNÉRALE Au début de ce travail, nous pensions devoir considérer en profondeur les phénomènes physiques sous-jacents à la propagation des ondes sonores. Au cours des recherches, nous nous sommes rendu bien compte qu’il était plus rapide et rentable de modéliser juste l’ensemble, pour pouvoir mener à bien le travail à un coût dérisoire. Il est en effet plus optimal de traiter les phénomènes complexes, comme les phénomènes de propagation du son en dehors des conditions de laboratoire, de manière approximative mais globale au lieu de les voir en détail. Comme cela a bien été souligné, l’approche détaillée est utopique vu que le coût de calcul est immensément énorme. En introduction, nous avons posé comme hypothèse, que le filtrage est une solution à la présence indésirée  d’écho  dans  un  système  de  communication,  et  ce  travail  vient  évidemment  de  nous conforter dans cette affirmation. Nous avons également supposé qu’un filtrage purement analogique serait moins rentable mais nous nous sommes rendu compte au fil du travail que, cette proposition doit être bien nuancée. En effet, durant ce travail, nous avons montré que nous ne pouvons, si nous considérons le système dans son ensemble (et non seulement la partie qui concerne le traitement algorithmique), nous passer d’une partie de traitement analogique du signal (penser au filtre anti- repliement par exemple).  Néanmoins, en nous basant uniquement sur le filtrage du signal reçu, sans trop nous fier au formatage et à la correction du rapport signal sur bruit, nous pouvons sans doute nous fier uniquement à un traitement purement numérique.  Finalement, au vu du processus mis en œuvre pour l’adaptation du filtre annulateur d’écho, nous confirmons la troisième hypothèse lancée  en  introduction  et  affirmant  qu’on  ne  peut  se  passer  d’une  mémorisation  dynamique  du signal durant une partie du traitement pour pouvoir mener à bien l’annulation de l’écho sonore lié au système de communication. 69  CHAPITRE 3.  CONCEPTION DU FILTRE MIXTE ADAPTÉ Ce travail a pointé du doigt la puissance de la théorie mathématique de traitement du signal. C’est ainsi qu’il a pu déboucher sur le filtrage numérique et en premier lieu sur le filtrage de Wiener qui est évidemment un prélude inévitable pour aborder le filtrage adaptatif. Le filtrage adaptatif car, comme cela a été plusieurs fois mentionné, c’est le moyen par excellence pour pouvoir modéliser un système non stationnaire comme c’est le cas pour les systèmes sonores. Notre travail a donc consisté à élaborer un filtre numérique modélisant l’enceinte dans laquelle le son va se propager,  de telle sorte qu’il ne puisse pas y avoir une grande différence entre le son perçu à la sortie du filtre et celui qui serait perçu après avoir parcouru la salle. Cela revient donc à modéliser le chemin d’écho.  Pour cela, les coefficients du filtre élaboré doivent correspondre à la réponse impulsionnelle de l’enceinte (à l’endroit où l’on se tient pour la mesurer). Toutefois, les signaux sonores étant très instationnaires, il est impérieux d’adapter ces coefficients au fur et à mesure de la réception du signal.  D’où la nécessité des filtres adaptatifs comme on l’a tantôt montré.  Nous avons développé les algorithmes du filtrage adaptatif en nous focalisant sur les plus indiqués pour l’identification des système (le chemin d’écho pour notre cas).  Cela nous a conduit à considérer un algorithme nomméPNLMS++qui est très indiqué dans des tels systèmes pour sa grande vitesse de convergence et sa robustesse. L’objectif visé est qu’en cas de besoin, les théories abordées dans ce travail puissent être exploitées directement pour élaborer des systèmes devant équiper des appareils de communication habituels pour  l’annulation  d’échos  sonores  éventuels.   C’est  pour  cette  raison  qu’il  nous  a  semblé  très important de montrer de quelle manière on pourrait réduire toujours plus fortement la charge de calcul  des  processeurs  numériques  à  utiliser  ainsi  que  le  coût  (d’un  point  de  vu  pécuniaire)  de l’ensemble.  De toute évidence, les processeurs à virgule fixe sont les plus adaptés à l’élaboration des plate-formes à faible prix tout en gardant une efficacité admissible quand ils sont programmés en conséquence.  Ils allient en fait la rentabilité financière à la précision en ce qui concerne notre projet.  Ce qui précède justifie le choix d’un traitement tout à fait particulier des données pour les rendre adaptées le plus fortement possible aux processeurs à virgule fixe (il s’agit du traitement par transformation en nombres de Fermat en lieu et place de la transformation de Fourier).  Cette nouvelle transformation a toutes les propriétés nécessaires pour développer et optimiser la majorité des processus d’annulation d’écho dès qu’on décide de les implanter sur un processeur à virgule fixe. 70 sur 84  3.7.  CONCLUSION PARTIELLE Au préalable, nous prévoyions réaliser les algorithmes en langage C mais nous étant rendu compte du fait que cela serait sans intérêt( en première approximation), nous avons choisi de développer le système sous Matlab sachant que si on envisageait une implantation sur DSP, l’adaptation du code serait simple étant donné la similarité des syntaxes de ces deux langages. C’est sous cet angle que nous avons mis au point sous Matlab un algorithme complet d’adaptation des coefficient du filtre destiné à l’annulateur d’écho. Aux  futurs  chercheurs,  nous  suggérons  l’étude  complète  de  l’incorporation  des  algorithmes  ici conçus, aux systèmes de communication complets ainsi que, la correction des erreurs introduites dans le filtre obtenu en cas de traitement par blocs,  pour améliorer encore plus l’atténuation de l’écho par cette méthode vu que ce dernier traitement est le mieux adapté au fonctionnement en temps réel. 71 sur 84    ANNEXES 73    .1.  ALGORITHME DE TRAITEMENT BRUT .1    Algorithme de traitement brut 1  -%Récupération du son 2  - 3  -%Définition de la période d’échantillonnage 4  -fs=44100; 5  -%Définition du nombre de voies d’enregistrement 6  -noc=1; 7  -%Définition du nombre de bits 8  -nob=16; 9  -%Enregistrement du signal audio 10 -recObj=audiorecorder(fs,nob,noc); 11 -record(recObj); 12 -pause(40); 13 -stop(recObj); 14 -%Lancement du signal enregistré 15 -play(recObj); 16 -%Formatage du signal enregistré sous forme vectoriel 17 -myrecordings=getaudiodata(recObj); 18 -%Représentation du signal enregistré 19 -plot(myrecordings); 20 -%Fin de la partie prise de son 21 - 22 -%Début de l’algorithme et lancement du chronométrage 23 -tic; 24 -%Initialisations et déclaration des constantes 25 - 26 -yk=ones(1,64); 27 -%Déclaration des constantes "beta", "delta", "rho" et "mu". 28 -b=100; 75 sur 84  29 -D=(1/64); 30 -rho=0.01; 31 -mu=0.8; 32 -%Initialisation des W pour NLMS puis PNLMS. 33 -w1=(ones(1,64))’; 34 -w2=(ones(1,64))’; 35 -%Initialisation des vecteurs utiles au calcul de Gk. 36 -gam=zeros(1,64); 37 -gk=zeros(1,64); 38 -%Initialisation des vecteurs d’erreur et de W. 39 -err=(1:64000); 40 -w=zeros(1:64); 41 - 42 -%Début du traitement 43 -for i=1:20850 44 -    %Récupération du vecteur d’entrée à chaque étape i 45 -    sign=(myrecordings((64+(i-1)):-1:(1+(i-1))))’; 46 - 47 -    %Calcul d’un paramètre utile pour trouver le vecteur Gk 48 -    Vk=max([D,abs(w)]); 49 -    %Calcul du vecteur Gk 50 -    for k=1:64 51 -        gam(k)=max(((rho) * Vk),(abs(w(k)))); 52 -    end 53 -    for M=1:64 54 -        gk(M)=((gam(M))/(mean(gam))); 55 -    end 56 -    Gk=1 * diag(gk); 57 -    %Calcul des éléments du vecteur d’erreur en gérant le début 58 -    for s=1+(i-1):64+(i-1) 76 sur 84  .1.  ALGORITHME DE TRAITEMENT BRUT 59 -        sign2=(myrecordings((64+(s-1)):-1:(1+(s-1))))’; 60 -        yk(s) = (sign2) * w’; 61 -        err(s+63)=((yk(s)-myrecordings(64+(s-1)))); 62 -    end 63 - 64 -    %Début du processus de réinitialisation du filtre 65 - 66 -    %Algorithme PNLMS (Calcul du vecteur W1) 67 -        w1=(w’+(mu * Gk * ((sign)’) * err(i+63))/(sign * Gk * (sign)’+b))); 68 -    %Algorithme NLMS (Calcul du vecteur W2) 69 -        w2=(w’+((mu * ((sign)’) * err(i+63))/(((sign) * ((sign)’)+b)))); 70 - 71 - 72 -    %Réinitialisation des coefficients du filtre par PNLMS++ 73 - 74 -    for k=1:64 75 -        %Coefficients impairs par PNLMS 76 -        if mod(k,2)==1 77 -          w(k)=w1(k); 78 -        %Coefficients pairs par NLMS 79 -        elseif mod(k,2)==0 80 -            w(k)=w2(k); 81 -        end 82 -    end 83 -end 84 -%Fin du chronométrage 85 -toc; Revenir dans le texte en cliquant 3.4.1. 77 sur 84  .2    Algorithme de traitement par blocs 1   -%Récupération du son 2   - 3   -%Définition de la période d’échantillonnage en respectant Shannon 4   -fs=44100; 5   -%Définition du nombre de voies d’enregistrement 6   -noc=1; 7   -%Définition du nombre de bits 8   -nob=16; 9   -%Enregistrement du signal audio 10  -recObj=audiorecorder(fs,nob,noc); 11  -record(recObj); 12  -pause(40); 13  -stop(recObj); 14  -%Lancement du signal enregistré 15  -play(recObj); 16  -%Formatage du signal enregistré sous forme vectoriel 17  -myrecordings=getaudiodata(recObj); 18  -%Représentation du signal enregistré 19  -plot(myrecordings); 20  -%Fin de la partie prise de son 21  - 22  -%Début de l’algorithme et lancement du chronométrage 23  -tic; 24  -%Initialisations et déclaration des constantes 25  - 26  -w=zeros(1,64); 27  -zero=zeros(1,64); 28  -%Complément de W par des zeros pour atteindre la longueur réquise 78 sur 84  .2.  ALGORITHME DE TRAITEMENT PAR BLOCS 29  -wk=[w,zero]’; 30  -%Déclaration des constantes "beta", "delta", "rho" et "mu". 31  -b=100; 32  -D=(1/64); 33  -rho=(10^(-2)); 34  -mu=(0.8); 35  -%Initialisation des W pour BNLMS puis BPNLMS. 36  -w1=(ones(1,64))’; 37  -w2=(ones(1,64))’; 38  -%Initialisation des vecteurs utiles au calcul de Gk. 39  -gam=zeros(1,64); 40  -gk=zeros(1,64); 41  - 42  -%Début du traitement 43  -for i=1:20850 44  -    %Sélection particulier du premier bloc d’échantillons 45  -    if i==1 46  -        sign=(myrecordings(1:128))’; 47  -        sign2=(myrecordings(128:-1:1)); 48  -    %Sélection général de tous les blocs 49  -    elseif i>=2 50  -        sign=(myrecordings(65+64 * (i-2):192+64 * (i-2)))’; 51  -        sign2=(myrecordings((192+64 * (i-2)):-1:(65+64 * (i-2)))); 52  -    end 53  - 54  -    %Transformation du signal d’entrée et du vecteur W 55  -    SIG=fft(sign); 56  -    W=(fft(wk))’; 57  -    %Calcul du produit terme à terme des deux vecteurs 58  -    Y=SIG. * W; 79 sur 84  59  -    %Transformation inverse pour retrouver le produit de convolution 60  -    YW=ifft(Y); 61  -    %Sélection des termes utiles recherchés 62  -    yw=YW(65:128); 63  -    %Calcul du vecteur d’erreurs 64  -    err=(myrecordings(1+64 * (i-1):64 * i))’-(yw); 65  -    %Complément du vecteur par des zeros puis transformation 66  -    ERR=[err,zero]; 67  -    errF=fft(ERR); 68  -    %Transformation du vecteur image 69  -    SIG2=fft(sign2); 70  -    %Réalisation de l’étape 3°) points 15, 16 et 17 de l’algorithme 71  -    ERsign=(errF)’. * (SIG2); 72  -    erSIGN=ifft(ERsign); 73  -    es=erSIGN(65:128); 74  -    %Réalisation de l’étape 3°) points 18 et 19 (autocorrélation) 75  -    RSS=SIG2. * (SIG)’; 76  -    RSs=ifft(RSS); 77  -    Rss=RSs(65:128); 78  - 79  -    %Calcul d’un paramètre utile pour trouver le vecteur Gk 80  -    Vk=max([D,abs(w)]); 81  -    %Calcul du vecteur Gk 82  -    for k=1:64 83  -        gam(k)=max(((rho) * Vk),(abs(w(k)))); 84  -    end 85  -    for M=1:64 86  -        gk(M)=((gam(M))/(mean(gam))); 87  -    end 88  -    Gk=diag(gk); 80 sur 84  .2.  ALGORITHME DE TRAITEMENT PAR BLOCS 89  -    %Réalisation de l’étape 3°) point 21 90  -    GkRss=Gk * (Rss); 91  - 92  -    GkEsi2=Gk * es; 93  - 94  -    %Réinitialisation des coefficients du filtre 95  - 96  -    for j=1:64 97  -        %Algorithme BPNLMS 98  -        w1(j)=(w(j)+((mu * GkEsi2(j))/(GkRss(j)+b))); 99  -        %Algorithme BNLMS 100 -        w2(j)=(w(j)+((mu * es(j))/(Rss(j)+b))); 101 - 102 -        %Réinitialisation des coefficients du filtre par BPNLMS++ 103 -        %Coefficients impairs par BPNLMS 104 -        if mod(j,2)==1 105 -            w(j)=w1(j); 106 -        %Coefficients pairs par BNLMS 107 -        elseif mod(j,2)==0 108 -            w(j)=w2(j); 109 -        end 110 -    end 111 -end 112 -w=((ones(1,64)) * (13.5)-(w))/(13.5); 113 -%Fin du chronométrage 114 -toc; Revenir dans le texte en cliquant 3.4.2. 81 sur 84    Bibliographie [1]  ALAEDDINE,  H.Application  de  la  transformée  en  nombres  entiers  à  la  conception d’algorithmes  de  faible  complexité  pour  l’annulation  d’échos  acoustiques.PhD  thesis, Université de Bretagne Occidentale, Juillet 2007. Investigations théoriques. [2]  CALAIS,  J.Extensions  de  corps  _  Théorie  de  Galois,  ellipses  ed.    Mathématiques  à l’Université, 2006. [3]  CARIOLARO, G.Unified Signal Theory. Springer, University of Padova, Italy, 2011. [4]DECOULON,  F.Théorie et traitement des signaux,  vol. VI.   Presses polytechniques et universitaires romandes, CH-1015 Lausanne, 1996. Fondements du traitement des signaux. [5]  DESMORAT,  R.   Cours  d’acoustique  physique.   Ecole  Normale  Supérieure  (ENS  Paris- Saclay), Mai 2017. [6]  Introduction au filtrage adaptatif. fmy, 2005. [7]  GARNIER,  H.   Rappels  sur  la  théorie  de  l’échantillonnagede  l’analogique  au  numérique. Université de Lorraine, Polytech NANCY.hugues.garnier@univ-lorraine.fr. [8]  HENRI, A. J. . L.Méthodes matricielles _ Introduction à la complexité algébrique. arXiv math, avril 2012, ch. 7. [9]  HIRIART-URRUTY, J.-B.  Topologie et analyse hilbertienne: Une introduction pragmatique. Notes de cours, Université Paul Sabatier de Toulouse. [10]  MALLAT, S.  Traitement du signal.  Notes de cours, Ecole Normale Supérieure - DÉPARTEMENT DE MATHÉMATIQUES / ENSEIGNEMENT, 45 rue d’Ulm 75230 Paris Cedex 05 - Tél :  01 44 32 31 72 -education@math.ens.fr, 2015. 83  BIBLIOGRAPHIE [11]  MAURICECHARBIT, G. B. Traitement du signal audio-numérique. ATIAM: Parcours multi-mentions du master Sciences et Technologies, Septembre 2012.  Université Pierre et Marie Curie - Paris 6 en collaboration avec TELECOM ParisTech et l’IRCAM. [12]  MULLER, J.-P.  Le traitement numérique du signal audio.www.ponge.biz, Juille 2001. [13]  PISKOUNOV, N.Calcul différentiel et intégral, editions mir ed., vol. II. Juin 1993. [14]  P.JARDIN, J.-F. B. .  Introduction au filtrage adaptatif. ESIEE Paris, 2003. [15]  PONTON, L.  Groupes, anneaux, corps et théorie de galois. Papiers personnels _ lionelponton.fr. [16]  SINCÈRE,  F.   Filtrage  numérique  d’un  signal  d’évolution  lente  avec  un  microcontrôleur.   IUT  de Nancy-Brabois.http://perso.orange.fr/fabrice.sincere,Version 1.2.2. [17]  SINCÈRE, F. Module d’electronique, troisième partie : Conversion de données. IUT de Nancy-Brabois. http://perso.orange.fr/fabrice.sincere,Version 3.0.1. [18]  TERTRE,  D.Conception  avancée  des  circuits  intégrés  analogiques.convertisseurs  a/n  et  n/a. Ecole  nationale  supérieure  des  Mines  de  Saint-Etienne,  2009.www.emse.fr/~dutertre/ enseignement.html. [19]  WIKIPÉDIA. Processeur de signal numérique, 2021. 84 sur 84