Choix d’un algorithme en précision finie, pour annuleur d’écho

pp. 305-329 305

Choix d'un algorithme en precision finie, pour annuleur d'6cho

Madeleine B O N N E T * **

Odile M A C C H I **

Analyse

Deux algorithmes pour annuleur du par filtrage adaptatif sont compards f l' aide de plusieurs param~tres : r~sidu d'dcho, complexitd des calculs en precision finie et vitesse de convergence. 1l s'agit de l'algorithme classique du gradient et de Pun de ses d~rivds : l'algorithme du signe de l'erreur. Les auteurs montrent qu'en utilisant un bruit auxiliaire contr&M, l'algorithme du signe a un comportement semblable ?t celui de l'algorithme du gradient en ce qui concerne le rdsidu d'dcho et la longueur des mots binaires. 1l est nettement supdrieur ?l l'algorithme du gradient en ce qui concerne la complexitd globale. Le problbme de la vitesse de convergence plus faible peut s rdsolu par des techniques simples d'initialisation. Des simulations illustrent les r~sultats thdoriques.

Mots elrs : Annuleur ~cho, Algorithme adaptatif, Filtrage adaptatif, Cornplexit6 algorithme, Vitesse convergente, Lon- gueur mot, Efficacitr, Mrthode gradient, Mrthode signe, Signal discret, Simulation numrrique, Bruit additif.

convergence can be solved by means of simple initiali- zation techniques. Theoretical results are illustrated through computer simulations.

Key words : Echo cancellor, Adaptive algorithm, Adaptive filtering, Algorithm complexity, Convergence speed, Word length, Efficiency, Gradient method, Sign method, Discrete signal, Digital simulation, Additive noise.

S o m m a i r e

I. Introduction.

II. Notations.

III. Echo rdsiduel.

IV. Simulations.

V. Prdcision et complexitd.

VI. Vitesse de convergence.

VII. Conclusion.

Annexes.

Bibliographic (26 rdf.).

C H O I C E OF AN E C H O C A N C E L L I N G A L G O R I T H M

W I T H F I N I T E A C C U R A C Y I M P L E M E N T A T I O N

Abstract

The comparison of two different algorithms for adaptive echo cancellers is analyzed by means of the following parameters : residual echo level, complexity of computations in the case of finite computational accuracy and speed of convergence. These algorithms are the well-known gradient algorithm and the one which uses the sign of the error. The authors show that adding a controlled noise in the sign-algorithm makes its residual echo and the length of its binary words behave like those of the gradient algorithm. The sign algorithm total complexity is less than the gradient algorithm one. The problem of the lower speed of

I. I N T R O D U C T I O N

Dans une l ia ison de donnres utilisant un seul support, par exemple dans l 'exploitation en mode bilatrral simultanr, apparait le ph rnomrne d ' r c h o : le rrcepteur, qui doit reconstituer les donnres 6raises par un 6metteur 61oignr, re~oit un 6cho du signal 6mis par son propre 6metteur.

Le problrme de la suppression de cet 6cho apparai t par exemple dans les transmissions numrriques bilatrrales sur des circuits ~t 2 ills, soit dans le rrseau t r l rphonique grnrral, soit dans certains types de rrseaux locaux h haut drbit dont l 'appari t ion tend

se grnrraliser. I1 es t / t noter que nous ne traitons pas ici de l'effet

subjectif drsagrrable pour un locuteur de l ' r cho de

* Institut de Programmation. Universit6 Paris VI, 4. place Jussieu 75230 Paris cedex 05. ** Laboratoire des Signaux et Syst~mes - CNRS - ESE, Plateau du Moulon, 91190 Gif sur Yvette.

1/25 ANN. T~L~COMMUN., 38, n ~ 7-8, 1983

306 M. BONNET. -- ALGORITHME POUR ANNULEUR D'I~CHO

son propre signal. Cet 6cho g~ne le locuteur lui- m~me pour parler et ne pourrai t ~tre supprim6 que par un syst6me d'6galisation, ce qui n 'est pas l 'objet de notre propos. Nous traitons ici de l'effet objectif de l '6cho du signal 6mis, sur la r6ception du signal de la source 61oign6e.

Cet 6cho peut avoir un niveau de puissance tr~s sup6rieur 5. celui des donn6es 61oign6es ; d 'ofi la n6cessit6, pour pouvoir restituer les donn6es envoy6es par la source 61oign6e, de r6duire l '6cho jusqu'h un niveau acceptable. On sait que ceci peut ~tre r6alis6 par la technique dite d 'annulat ion d '6cho : en reconsti- tuant l '6cho par filtrage adaptatif, puis en soustrayant l '6eho ainsi reconstitu6. Plusieurs auteurs ont travaill6 r6cemment sur ce probI6me d 'annula t ion d'6cho [1 ~ 10] (*).

Nous nous int6ressons ici /t deux algorithmes destin6s /~ reeonstituer 1'6cho par filtrage adaptatif. Le premier est l 'algorithme classique du gradient, d6nomm6 (E) par la suite. I1 utilise l '6cart entre l '6cho estim6 et le signal observ6, c'est-h-dire l '6cho addi- tionn6 de bruit et 6ventuellement de donn6es lointaines. Le second algorithme, appel6 (S) par la suite, considSre seulement le signe de cet 6cart ; il est donc de moindre complexit6.

Le but du pr6sent article est de comparer les performances de ces deux algorithmes, mesur6es par le r6sidu d'6cho et par la complexit6 du calcul, et de mettre en 6vidence comment l 'utilisation d 'un pas d ' incr6mentation variable, d6croissant, et l ' introduction d 'un bruit forc6 dans l 'a lgori thme (S) rendent le compor tement de cet algorithme tout /t fait simi- laire au comportement de l 'algori thme (E) et m~me bien meilleur en ce qui concerne la complexit6.

D 'autres auteurs [5, 11] ont d6jh pr6sent6 des comparaisons de ces deux algorithmes dans la litt6- rature ant6rieure (**).

N6anmoins, jusqu'/t ce jour, un critSre 5, notre sens fondamental de la comparaison n ' a pas 6t6 suffi- samment pris en compte, celui de la complexit6 du calcul. Les auteurs notent naturellement la simpli- fication de calcul apport6e par l 'utilisation du signe de l'6eart, mais sans l '6valuer quantitativement. Dans ce but, nous introduisons deux 6tapes.

D 'abord , remarquant que t o u s l e s calculs se font en pr6cision finie, nous 6valuons pour les deux algorithmes la longueur binaire de la repr6sentation en machine des diff6rentes grandeurs trait6es par l 'algorithme, et nous montrons comment cette longueur est fonction des performances souhait6es pour l 'annulation d ' fcho , c'est-h-dire du niveau de r6sidu d'6cho.

(*) RAULT (J. C.), MAITRE (X.), PETIT (J. P.). Diff6rentes structures d'annuleurs d'6cho pour la transmission num6rique 2 ills : th6orie et simulations. Note technique CNET. NT/LAB/ SER/87. (**) I1 est/t noter que ces r6f6rences ne traitent pas le cas de la modulation de deux porteuses en quadrature (donn6es complexes) ot qu'elles utilisent l'hypoth6se que la distribution du r6sidu d'6cho est gaussienne ; nous montrerons dans la suite que cette hypoth6se n'est justifi6e qu'en pr6sence d'un bruit relativement important.

La deuxi6me 6tape pour 6valuer la complexit6 de calcul consiste simplement, une fois connue la longueur des mots binaires, /t calculer le nombre d 'op6rations 616mentaires bit /t bit ~ effectuer pour chaque algorithme.

Certains auteurs [6, 8, 11] ont aussi propos6 l 'introduction d 'un bruit forc6 dans l 'algorithme du signe ; nous expliquons et calculons les effets de ce bruit sur le comportement de l 'algori thme ; nous montrons comment l ' introduction d 'un bruit forc6 de niveau voisin de celui du signal ram~.ne h peu pr6s la longueur binaire des coefficients ~t la m~me valeur pour les deux algorithmes.

Notre 6tude illustre comment les performances de (S) en r6gime statique peuvent &re comparables ou m~me sup6rieures /t celles de (E). N6anmoins, elle souligne le fait (d6jh connu) que le pas d'incr6men- tation, /l r6sidu d '6cho 6gal, est beaucoup plus faible pour (S) que pour (E). Ce fait est /l l 'origine de la faible vitesse de convergence de (S), bien connue des utilisateurs. C'est la raison pour laquelle nous avons introduit dans notre 6tude un pas d' incr6mentation variable, d6croissant par 6tapes et 6ventuellement une phase d'apprentissage initial sans l '6mission de donn6es lointaines. Cette m6thode limite notablement la r6duction de vitesse li6e h (S) et rend tout /t fait acceptable ses performances en r6gime dynamique.

Nous pouvons conclure que l 'algorithme du signe a des performances globales comparables ou sup6- rieures /t celles de l 'algorithme du gradient.

Dans l '6tude qui suit, apr~s avoir rappel6 le con- texte et la structure de l 'annulat ion d '6cho darts le paragraphe 2, nous 6valuons l '6cho r6siduel au paragraphe 3 et commentons les simulations au paragraphe 4. Nous 6tudions au paragraphe 5 la quantification des diff6rents coefficients et la comple- xit6 de calcul et au paragraphe 6 les vitesses de convergence.

H. N O T A T I O N S

Nous commen~ons par rappeler le probl6me de l 'annulation d '6cho afin de d6finir nos notations.

H.1. Structure du syst6me.

Dans un syst6me de communications bilat6rales sur un seul support, le r6cepteur A doit reconstituer la suite des donn6es utiles ark 6mises par l '6met- teur ,?3 en pr6sence d 'un bruit addit if nk et d ' un signal ~r'k dO ~t l '6cho des donn6es locales 0~k. On peut supposer (Fig. I) que ce signal d'dcho a'k est d6duit des donn6es 0~k, 6raises par l '6metteur A, par un filtrage num6rique inconnu ou filtre d'dcho C.

Le tableau I r6sume les principales notations de l'article.

ANN. TI~L~COMMUN.) 38, n ~ 7-8, 1983 2/25

M. BONNET. -- ALGORITHME POUR ANNULEUR D'I~CHO 307

Emetteur

I R~cepteur Yk

FIG. 1. - - R6cept ion en pr6sence d '6cho.

y~ = a~ q- d e -t- n k �9

Reception in the presence o f an echosignal.

vers

(~dk P n k

T A B L . I . - - Principales no ta t ions c o n c e m a n t l ' annula t ion d '6cho

(1) tr~ = C arak

(2) a k = C~ 0t k

(3) Yk = ~ + d e + nk

(4) e k = Y k - - o k

( 5 ) v k = c , - - c

( 6 ) e~k = - - v ' [ =k

A (7) S

R

B

signal d '6cho

6cho estim6

signal observ6

signal d6barrass6 d '6cho ou signal p rop re

diff6rence entre filtre estim6 et filtre d '6cho

6cho r6siduel

puissance des donn6es proches

puissance des donn6es lointaines

puissance du r6sidu d '6cho

puissance du bruit addit if

Les caract6ristiques du filtre d'6cho, qui se r6sument h u n vecteur C (soit N sa longueur), peuvent varier au cours du temps. Le signal d '6cho s'6crit selon (1), oO :

(8) = ~ = ( ~ k , ~ k - , . . . . . ~ - ~ + x ) .

Le signal Yk regu par le r6cepteur A est la somme de ces trois composan tes de , nk et ~r'~, selon (3). Pour supprimer le signal d '6cho ~ 'k , on utilise un filtre num6rique adap ta t i f (Fig. 2), ou annuleur d '6cho

adaptatif , de vecteur :

(9) C~ = ( C ~ , C 2 . . . . . C~).

Ce vecteur est celui des 6chantillons du filtre adap ta t i f la k-6me it6ration ; il change ~t chaque nouvelle

observation Yk �9 Le filtre agit sur la suite (8) qui est effectivement disponible puisque les donn6es ak sont connues du r6cepteur car 6mises localement pa r l '6metteur A.

Les notations utilis6es seront telles que les donn6es puissent ~tre complexes, comme dans le cas de la modula t ion de phase et de la modula t ion de deux porteuses en quadrature.

Le signal d '6cho reconstitu6 ~k - - ou ~cho estim6 - - est donn6 par (2). Nous notons ek, selon (4), le signal

p r o p r e , apr6s annulat ion d '6cho, qui doit ensuite ~tre trait6 par le r6cepteur .& pour en extraire les donn6es 61oign6es dk. Ce signal ek sert ~t pi loter les coefficients de l ' annuleur , il pour ra 6ventuellement, avant l ' adapta t ion, ~tre additionn6 d ' un brui t bk (cf. Fig. 2), dont nous verrons l 'utilit6 au pa rag raphe 3.3.

I1 est h noter que les intervalles d '6chant i l lonnage de 0ok et de d 'une part , et de ek d ' au t re part, ne sont pas n6cessairement les m~mes ; en effet, par suite de la n6cessit6 de synchroniser l ' instant d '6chant i l - lonnage des donn6es lointaines avec le rythme d '6mis- sion de la donn6e proche ~t k , on utilise souvent un sur6chantillonnage du signal propre ek. Ceci condui t ~t l ' emploi de plusieurs sous-annuleurs d '6cho, ainsi

(E k

i '

ek -- Yk -- O'k

T~

Yk

Ligne

[

Emetteur 13

Recepteur/3 I

FIG. 2. - - Syst6me de communica t ions h annu leur d '6cho pour le r6cepteur A . T D : t r ans formateur diff6rentiel ; b k �9 bruit forc6.

Two wire fu l l duplex baseband transmission with echo cancellation.

3/25 ANN. T~L~COMMUN., 38, n ~ 7-R 1983

308 M. BONNET. -- ALGORITHME POUR ANNULEUR D'I~.CHO

qu'il est mentionn6 dans [14, p. 619]. Mais le probl6me th6orique reste le mSme et on l 'analysera en employant, pour chaque sous-annuleur, la m6thode qui va 6tre d6crite dans la suite.

H.2. Description des algorithmes.

Les deux algorithmes 6tudi6s d6rivent de l 'algorithme du gradient qui consiste h minimiser la fonction erreur quadratique moyenne entre la r6f6rence y~ du signal d '6cho et son estimation ~ . L'6tude de ces algorithmes et leurs conditions de convergence se trouvent notamment dans [12, 15].

L 'algori thme (E) du gradient s'6crit :

(E) C~+1 = C~ + ~ ct* e~,

oh ~t* d6signe le nombre complexe conjugu6 de c~ et o/a le param6tre ix, positif, est appel6 coefficient de convergence ou pas d'incr6mentation.

L 'algori thme du signe s'6crit :

(S) Ck+l : C~ + ~t ct* sgn(e~),

o/~ :

(10) sgn(e~) = t + 1 si e~ >~ 0, ( - - 1 si e~ < 0.

Dans le cas complexe, sgn(ek) est un nombre complexe qui vaut par d6finition :

1 (11) a/~ [sgn(Re(ek)) + i sgn(Im(e~))].

Dans le paragraphe suivant, nous d6finissons l '6cho r6siduel et 6tudions son comportement dans chacun des algorithmes pr6c6dents.

HI. I~CHO RI~SIDUEL

Puisque l 'on veut reconstituer le signal d '6cho pour le soustraire du signal re,u, il est impor tant de savoir si l '6cho a bien 6t6 61imin6. L '6cho r6siduel est la diff6rence entre le signal d '6cho et l '6cho estim6 ; il permet de mesurer la qualit6 de l 'annulat ion d'6cho.

Le signal propre donn6 par (4) peut aussi s'6crire :

(12) ek = dk + n~ + erk,

oh er~ est l '6cho r6siduel (6), qui s 'exprime en fonction du vecteur Vk (5), qui est l '6cart entre le filtre d '6cho vrai et le filtre adaptatif.

Certains annuleurs d '6cho s 'autorisent une phase d'apprentissage pendant laquelle il n 'y a pas d'6mis- sion de donn6es lointaines ; d 'autres fonctionnent directement en r6gime permanent, avec mise en ser- vice des deux 6metteurs.

Pour tenir compte de ce choix, nous distinguons deux phases : la phase d'apprentissage, ou phase

ANN. T~L~COMMUN., 38, n ~ 7-8. 1983

(A), dans laquelle l '6metteur ~B n'envoie pas de donn6es, et le r6gime permanent, ou phase (P), lorsque l '6metteur ~ envoie des donndes dk. Nous calculons la valeur du r6sidu d '6cho dans ehacune de ces phases et pour chacun des algorithmes (E) et (S). Nous distinguons done quatre c a s q u e nous notons dans la su i t e : (E-A), (S-A), (E-P) et (S-P).

Hypothbses. Nous supposons que les 6chantillons successifs nk du bruit additif sont centr6s, ind6pen- dants, ind6pendants de la suite {~k} et ind6pendants de la suite {dk} ; en particulier nous avons :

I E(nk) = 0, (13) E(nk n*) = B ~k, ,

o/a 8kt est le symbole de Kronecker , et B la puissance des 6chantillons de bruit. Nous avons aussi :

t E(nk d*) = 0, Vk, vl, (14) E(nk ~*) = 0, V k, V 1.

Nos hypoth6ses entralnent l ' ind6pendance de nk et erk done :

(15) E(nk er*) = O.

Le cas oh les donn6es ~k sont corr616es et oh les 6chantillons du signal requ sont corr616s a 6t6 6tudi6 dans [16] ; nous consid6rons ici le cas oh les donn6es al6atoires {~%} sont ind6pendantes et centr6es. Les suites {~k}, 6mise par A, et {dk}, 6raise par 55, sont suppos6es ind6pendantes.

Nous supposerons de plus, comme la plupart des auteurs, que ek et 0c k sont des variables ind6pendantes, ce qui entralne :

(16) E(e* c%) = 0.

En fait, cette hypoth~se n 'est tout ~t fait satisfaite qu'A la limite, lorsque le vecteur C k a converg6 assez pour que erk soit n6gligeable dans l 'expression (12) de ek.

La d6finition du caract6re n6gligeable de erk est li6e /t la condition de bon fonctionnement de l 'annuleur :

(17) R ,~ S,

de sorte que le r6sidu d '6cho ne g~ne pas la d6tection des donn6es lointaines.

111.1. Valeur th6orique du r6sidu pourl'algorithme (E).

Nous redonnons ici rapidement les calculs connus [14] du r6sidu d '6cho pour l 'algorithme du gradient. L'algorithme (E) peut s'6erire :

(18) Irk+, = Vk + ~ at* ek.

Nous noterons :

(19) ~;k _--__ E(le~]~), la puissance de cet 6cart, qui devient, d'apr6s l 'hypo- th6se (15) d ' ind6pendance :

(20) ~ = E(lerkl 2) + E(In I 2) + E(1412).

4/25

M. B O N N E T . -- A L G O R I T H M E P O U R A N N U L E U R D ' E C H O 309

D'apr6s (18) on a :

(21) IIv +1112 = IIv ll + Re(ek * V~ X ~k)

+ 211 ll leaP. En utilisant l 'hypoth6se (15), on montre que l'esp6-

rance math6matique de (21) v a u t :

(22) E(IIv + iI[ = E(IIv II + 2 E(--ler l + ~" NE(I~,[ ~) g~.

En supposant l 'existence d 'une limite R pour le r~sidu lorsque k --> ~ , on obtient :

(23) R ( 2 - ~t NA) = ~ NA(B + S),

qui devient, lorsque (bt]2) NA ~ 1:

~t NA (B + S). (24) R ~

La valeur du r6sidu en phase (A) est obtenue en remplagant S par 0 dans cette formule.

Que ce soit en phase (A) ou en phase (P), le r6sidu d '6cho d6crolt comme ~ pour l 'algorithme (E).

Cherchons ce que vaut le r6sidu d'6cho lorsque la condition de bon fonct ionnement R ~ S est satisfaite ; d'apr~s l '6quation (24) on a :

bt NA(B + S) < S, (25)

qui donne, dans les cas r6alistes o~ S >> B,

~tNA ~ 1 . (26)

Nous constatons que le param~tre ~ dolt ~tre d 'autant plus petit que le nombre de coefficients de l 'annuleur d '6cho est plus grand, comme il est bien connu des utilisateurs.

HI.2 . Valeurs th6oriques du r~sidu pour l 'algorithme (S).

L'algori thme (S) s'6crit :

(27) Irk+ x = V k -q- [z er* sgn(ek),

d 'oh :

(28) E(IIv § = E(llv ll "-) + 2 [z Re[E(V[ ak sgn(e*))] + ~2 NA.

Les calculs relatifs ~t cet algorithme ne sont pas classiques ; ils n6cessitent une hypoth~se sur les statistiques du r6sidu erk et de la donn6e lointaine dk ; les r6sultats different selon l 'hypoth~se faite. Les deux hypotheses les plus caract6ristiques pour le r6sidu d'~cho sont celles d 'une 10i gaussienne et d 'une loi binaire ; ce sont deux cas extremes, nous verrons que la r6alit6 est interm6diaire entre ces deux hypotheses. Notons que dans la litt6rature ant6rieure, en particulier dans [5] et [11], seule l 'hypoth6se gaussienne est envisag6e ; nous verrons par la suite qu'elle est trop optimiste.

Dans la suite nous appellerons perturbation la partie de l 'observation correspondant ~t (nk -{- dk) et nous envisagerons les cas de perturbations purement binaire, purement gaussienne et de perturbations interm6diaires : avec brouillage intersymbole et binaire arrondie (par l 'addition d 'une petite variable gaussienne).

Ces diff6rents cas sont repr~sent6s par la figure 3.

Pd k +ng

_o_

~ Pdk ~n~

/ ' i \ / I X

----' ' l "- ._ dk+=- n'

b-

t Pdk* ~ Pak'nk

d FIG. 3. - - Diff6rentes hypoth6ses sur la loi de la perturbation.

a) perturbation binaire, b) perturbation gaussienne, c) perturbation avec brouillage, d) perturbation binaire arrondie.

Different statistics for the perturbation. a) binary perturbation, b) gaussian perturbation, c) perturbation with intersymbol interferences, d) smooth-binary perturbation.

Notons respectivement R~, R b , Rba, R, les valeurs des r6sidus d '6cho dans l 'hypoth6se de perturbations gaussienne, binaire, binaire arrondie et avec brouillage intersymbole.

IH.2.1. Hypoth~se er k gaussienne.

Si N est assez grand, nous supposons que les variables al6atoires V r a~ sont gaussiennes en tant que combinaisons lin6aires de variables ind6pendantes.

Ill.2.1.1. Perturbation gaussienne.

Ce cas correspond ~t un bruit nk gaussien et une donn6e lointaine dk gaussienne, si bien que l 'erreur ek est aussi gaussienne. Sous cette hypoth6se gaussienne, il a 6t6 d6montr6, voir [17, 19] q u e :

1 ~ - E(V~ 0t k e*), (29) E(V{ 0tk sgn(e*)) -- So 4 ~

oh So est une constante qui vaut 1 pour des donn6es r6elles et ~/2- pour des donn6es complexes.

L'6galit6 (28) s'6crit a lo r s :

2 ~ / ~ - (3o) E(IIV +,II) =E(IIV II ) + W E(--ler l +

Ix 2 N A ) .

5/25 ANN. T~r.~COMMUN., 38, n ~ 7-8, 1983

310 M. B O N N E T . -- A L G O R I T H M E P O U R A N N U L E U R D ' E C H O

Toujours avec l 'hypoth~se d'existence d 'une limite R 8 pour le r6sidu lorsque k ~ ~ , l '6quation pr6c6- dente donne :

N 2 A a (R~ -~ B q- S). (31) g . = So

A partir de ce r6sultat, on obtient ais6ment la valeur du r6sidu d '6cho en phase (A), c 'est&-dire lorsque S = 0, et la valeur du r6sidu pour une perturbation nulle (S -t- B = 0).

Bien que Claasen et Mecklenbraiiker [11] ne tiennent pas compte du bruit, leur r6sultat (6quation 55) est comparable avec celui que l 'on obtient ici lorsque B = 0 ; le d6veloppement de la comparaison donne deux r6sultats identiques.

111.2.1.2. Perturbation binaire arrondie.

Ce cas correspond/ l des donn6es lointaines dk ayant leurs parties r6elle et imaginaire (dans le cas complexe), form6es chacune de variables binaires, sym6triques, la variable nk 6tant gaussienne. Alors la variable ek n 'est plus gaussienne.

Reprenons la formule (28) et 6valuons le second terme du second membre qui est, au signe pros, l 'intercorr61ation entre erk et sgn(ek) ; nous obtenons le r6sultat suivant dont la d6monstration est donn6e en annexe A :

(32)

r A E ( - - e r ~ s g n ( e * ) ) = - - V / ~ ~ e-Sl2tR~. + ~).

L'6galit6 (28) devient alors :

(33) z(llv +xl[ =) = E(llv ll=)--

2 ~x Rba /"2"-e_Si2(Rba+B)/ So V + NA,

et toujours avec l 'hypoth~se d'existence d 'une limite lorsque k ~ 0% on obtient I '6quation du r6sidu :

7~ N2A 2 (Rb, + B) e slab"+m (34) R 2. = Ix2S2o

En consid6rant un bruit nul, cette formule nous donne la valeur du r6sidu d '6cho pour une perturbation purement binaire, cas particulier 6tudi6 dans [l 1].

Dans les cas usuels, la valeur Rg donn6e par (31) est tr6s inf6rieure /t la valeur Rba donn6e par (34). Ainsi, lorsque d~ est discr6te, consid6rer e~ comme une variable al6atoire gaussienne est une hypoth6se t rop os6e, qui donne une valeur trop optimiste du r6sidu d'6cho.

En fait, la r6alit6 correspond plut6t ~ un cas inter- m6diaire entre celui des perturbations binaire arrondie et gaussienne ; c 'est celui d 'une per turbat ion affect6e de brouillage intersymbole.

III.2.1.3. Perturbation avec brouillage intersymbole.

Si les brouillages affectent n donn6es successives, la variable d~ pourra prendre des niveaux 8j (non tous n6cessairement distincts), j ---- 1, 2 . . . . , 2", avec la probabilit6 1/2" de sorte q u e :

1 2n

2: = s . 2 ~ J= = 1

Alors, toujours en utilisant la mdtbode d6crite en annexe A, le r6sidu d'~cho v a u t :

(35) R~ : IxZ s 2 g N2A2(R, q-B) 22"•

a} -=

[ s~ , exp ( 2(Ri -t- B ) ) ] '

En l 'absence de bruit, ceci nous donne un r6sultat d6jA connu [7].

Nous retrouvons la formule (34) lorsque 4 est binaire et finalement on peut d6montrer la relation suivante entre les valeurs du r6sidu:

(36) R, < Rl < Rb , ,

ce qui montre que les hypotheses gaussienne et binaire arrondie donnent un encadrement du r6sidu d '6cho correspondant au cas r6el.

Les relations (31) et (34) sont illustr6es par la figure 4 qui sera comment6e ult6rieurement.

III.2.1.4. Comportement Hmite du rdsidu d'deho.

Cherchons d ' abord le comportement du r6sidu d'6cho lorsqu'il est grand devant le signal, en supposant que B e s t petit devant S, comme c'est le cas dans la pratique. Si nous utilisons une proc6dure avec un pas d ' incr6mentation variable, comme dans nos simulations (paragraphe 4), il s'agit l~t du d6but de convergence.

Les formules (31), (34) et (35) donnent dans ce cas la m~me valeur de R :

7~ N2A 2 (37) R = IX2 8 .

La d6croissance de R e s t en IXz ; ce r6sultat nouveau est tr~s int6ressant ; pour I 'algorithme (E) la d6crois- sance est en tx tout au long de la convergence.

Puis, lorsque R devient tr&s petit, c'est-~.-dire lorsque ~z d~crolt, cherchons comment se poursuit la d6croissance du r6sidu. Ceci correspond ~ la fin de convergence dans la proc6dure ~ pas d' incr6men- tation variable.

Consid6rons d ' abord la perturbation gaussienne ; la formule (31) d o n n e :

(38) R, = So N a 4S + B,

et Rg d6crolt comme ~t, comme pour l 'a lgori thme (E). Pour une perturbat ion binaire pure, il vient d'apr6s

(34) avec (B = 0 ) :

7~ N 2 A 2 eSlR b (39) Rb = ~x z So 2 ~ �9

D6finissant :

(40) F (Rb , g.') A_ Rb(ln Rb - - 2 In g.') - - S,

avec : /

(41) Ix ' : Ix,/~- N A s o , V o

ANN. T~L[COMMUN., 38, n ~ 7-8, 1983 6/25

M. BONNET. -- ALGORITHME POUR ANNULEUR D ' E C H O 311

1C

- 1 5

- 2 5

-I- R / S en dB

- 5 5

%%

%%N

Ph6nom~e de ~u l l .

! * �9 '%% %'% ~ " ~ . .

~ . - , - \ --.. (o) L "-.

\ ' , " , "-.~ b~ -. .

%%

(d) \

I I I ;C) I I 5 10 '15 25 .~3

- IoQ 2 ,u w,.--

FIG. 4. - - R6sidus d'6cho dans l'hypoth~se oh er~ est gaussienne pour diff6rentes perturbations. binaire arrondie : (a) S/B = 20 dB ; (b) SIB = 10 dB ; (c) S /B = - - 10 dB ; (d) SIB = 0 dB binaire pure gaussienne.

Residual echo with a Gaussian er k for different kinds o f perturbation.

on a d 'apr6s (39) et (40) :

d R b b F ORb

dix' bix' b F "

Ainsi

dRb 2 R 2

d~t ' IX' ( R b -[- S )

Puisque Rb < S, il vient l '6quat ion :

d Rb 2 R~ (42) d IX' ~ IX' S '

dont on v6rifie ais6ment qu 'el le 6quivaut / t :

S (43) Rb ~ 2 In IX' (1 q- k).

Une 6tude analyt ique plus d6taill6e mont re alors que la eonstante k (fonetion de IX') tend vers z6ro quand IX' tend vers z6ro.

La quantit6 (43) d6eroit vers z6ro avee ~, mais la d6croissance est beaueoup plus lente qu 'une d6erois- sance en ix et la tangente ~ la eourbe R(~t) ~ l 'origine est vertieale. S'il n ' y a pas de limitation stricte de Rb au-dessus d ' u n niveau fixe, n6anmoins Rb ne d6passe gu6re une valeur limite que nous appellerons seuil ; ce ph6nom6ne appara l t sur la figure 4.

Ce r6sultat eonfirme la remarque heuristique de Claasen et Meeklenbrai iker [11], signalant que pour des donn6es lointaines de probabilit6 nulle ~t l 'origine (eomme c 'est le eas pour des variables binaires), le r~sidu d '~eho cesse de d6eroitre lorsque IX d~eroit, atteignant une limite inf6rieure de l 'ordre de - - 10 dB

7/25

sous le signal. I1 en est ainsi lorsque sgn(ek) est 6qui- valent h sgn(d~), e'est-b,-dire lorsque er~ devient n6gligeable devant dk.

C 'es t iei que se t rouve l 'or igine du bruit, volontaire- ment ajout6 par certains auteurs dans l ' a lgor i thme, que nous appelons bruit fore6 (cf. paragraphe 3.3.). Ce bruit fore6 a pour effet d'61iminer l 'arr~t de la convergence du r6sidu d '6eho, eomme on va maintenant le voir.

L ' in t roduc t ion d ' u n bruit dans la per turba t ion binaire et done d ' une valeur B ~: 0 dans la fo rmule (34) a pour effet de rendre Rba(ix) d6rivable au voisinage de ~t = 0 et done d'adoucir le eoude situ6 au voisinage de Rba = 0 et qui indiquait le seuil. C ' e s t ainsi que pour R ,~ B, on obtient :

(34') R ~ ~t ~ N A 4r-B e sl2B.

En prenant pa r exemple un bruit forc6 de l ' o rd re de S, la fin de convergence est earact6ris6e pa r un r6sidu d '6cho propor t ionnel ~t IX. Ce r6sultat est semblable ~ eelui t rouv6 en (38) pour une per turbat ion gaussienne. De plus, en comparan t les formules (34') et (38) nous voyons qu'elles sont 6quivalentes pou r un bruit B important , donc pour la strat6gie du brui t fore&

III.2.2. Hypoth~se e r k binaire .

A l 'oppos6 de la loi gaussienne, consid6rons maintenant une loi binaire pour er~, correspondant pa r exemple ~t une r6ponse impulsionnelle tr6s 6troite du filtre d '6cho (chemin d '6cho ~ un seul coefficient).

ANN. TI~LI~COIdMUN., 38, n ~ 7-8, 1983


Ill.2.2.1. Perturbation binaire.

Ce cas correspond ~ l 'absence de bruit en ligne et h une donn6e dk binaire. L'intercorr61ation vaut :

(45) P = dRb-b 2 [sgn(~-~b + ffS) + sgn(ffR-~b-- ffS)].

Cherchons tout de suite le comportement limite du r6sidu.

Dans le cas oil Rb > S, d'aprSs (28), le r6sidu vaut :

l.i, 2 N 2 ..4 2

(46) gb -- 4

Cette d6pendance de R en g2 est un r6sultat remarquable, nous l 'avons d6j~i trouv6 en (37) dans le cas d 'un r6sidu gaussien.

Lorsque Rb < S, l 'intercorr61ation est nulle et l '6quation (28) s'6crit :

(47) E(ilv +,ll 2) = E(llv l?) + NA.

Consid6rons la puissance de l '6cho r6siduel ?t l ' instant k :

(48) Rk = E(ler~[2).

D'apr~s (6), on a :

(48') R~ = E(V * r or* ~t~ Vk).

Bien que les grandeurs Vk et 0ok ne soient pas ind6- pendantes dans la pratique, cette hypothSse donne des r6sultats parfai tement corrects (cf. [20]) en ce qui concerne les performances de l 'algorithme. Ainsi d'aprSs (48'), on a :

Rk = E(V *T E(ot** at) V~),

qui implique, d'apr~s l ' ind6pendance des 0~ successifs :

(49) = E(IIV I[ 2) .4,

et par cons6quent :

( 5 0 ) Rk+l ~ R~ - - [J,2 N A 2 = 0.

D'apr6s (50), R~ ne peut avoir de limite Rb infd- rieure ~t S. Donc le r6sidu d '6cho ne peut jamais devenir inf6rieur ~t S ; ceci est illustr6 par la figure 5. Nous avions d6j~t rencontr6 un ph6nomene semblable de scull en supposant une loi gaussienne pour erk, mais avec l 'hypoth6se pr6sente, le seuil est strict.

III.2.2.2. Perturbation binaire arrondie.

L'intercorr61ation vaut :

(51)

1D = -~---4Rba (r e--u212 du § e-U212du . 242= t

avec :

- - f i B et 13-- f f~ .

On pose :

1 Cx e -u212 (52) I(x) -- ff2~-.~_x du ; I (m) = 1.

Avec cette notat ion et d 'apr6s (28) le r6sidu est : [.I, 2 N 2 .42

(53) Rba = [I(~ + ~) - - 1(13 - - ~)]2,

Notons imm6diatement que ce r6sultat 6finit implicitement une fonction Rbn(b0 qui est continue par rapport fi iz, ce qui 61imine l'effet d6sastreux que l 'on vient de signaler, l 'arr6t de la convergence de Rba autour de la valeur S. Ceci est rigoureusement vrai quelle que soit la valeur de B r 0, ffit-ce la valeur tr6s faible du bruit de ligne.

En outre, il apparai t sur cette formule que, tant que Rbal S et SIB no sont pas tr&s faibles devant 1, le d6nominateur de (53), qui est du meme ordre de

[ = grandeur que 2 1 \ ~ j ] , est pratiquement

ind6pendant de Rua. Ainsi une d6croissance de Run en bt a du mSme type

qu 'en I'absence de bruit (46), se prolonge tant que Rua est sup6rieur ou 6gal /t S, comme il est mis en 6vidence sur la figure 5.

Lorsque R u J S devient tr~s faible, le d6nominateur de (53) devient proport ionnel b. Rb~ ;donc Rba devient proportionnel ~t g.. Si en outre Rba @ B, il est facile de voir que Run s'6crit sous la forme (34') que l 'on avait trouv6e dans l 'hypothSse d 'un r6sidu d '6cho gaussien. A nouveau, la d6croissance du r6sidu est e n g . en fin de convergence.

III.2.2.3. Perturbation gaussienne.

A l'aide de (53), on trouve ais6ment le r6sultat pour dk gaussienne :

- - ~ 1"2 N 2 A 2

(54) Re 4 [ I ( ff~-g ~ 1 2 ,

qui conduit encore it une d6croissance en E, 2 pour les fortes valeurs de R[S.

Une telle fonction Rg(fz ) est parfaitement douce et ne pr6sente aucun coude, mSme pour les tr6s petites valeurs de B.

Pour les tr6s faibles valeurs de RdS, le r6sidu est proportionnel ~t t* selon un d6veloppement analogue au pr6c6dent et on peut voir que R z s'6crit sous la forme (38) d6jh trouv6e dans le cas d 'un r6sidu gaussien.

Comme pour le cas du r6sidu d'6cho gaussien, il est trSs facile de v6rifier que les r6sidus s 'ordonnent comme suit, en fonction de l 'hypoth6se sur la perturbation :

(55) Ra < Rba < R b .

III.2.3. R6capitulation des r6sultats.

N o u s allons comparer les diff6rents cas 6tudi6s en ce qui concerne le d6but et la fin de convergence dans la proc6dure /i pas d ' incr6mentation variable.

111.2.3.1. Le rdsidu d'dcho est grand devant le signal.

Quelles que soient les hypoth6ses sur les lois des variables erk et dk, nous avons vu que lorsque le

ANN. T~LI~COMMUN., 38, n ~ 7-8 1983 8/25

M. B O N N E T . - A L G O R I T H M E P O U R A N N U L E U R D ' I ~ C H O 313

m . D

§ R/S en dB

15\ N I ~ Phenom~ne de $eull s l r i c t

" ~ x x, " . . . ( o )

- 25 ' ~ x(c) ~ ' ~ ' \ "

"~',,(d ) -lO~z l,t I I | I I | I I ~ r

2 5 10 15 20 25 ~0

FIG. 5. - - R6sidus d '6cho dans l 'hypoth~se oh erx est b ina i re pou r dif f6rentes per tu rbat ions .

b ina i re a r rond ie : (a) S/B = 20 dB ; (b) SIB = 10 dB ; (c) SIB = - - l 0 dB ; (d) SIB = 0 dB.

b ina i re pure ;

gaussienne. Residual echo with a binary er~ for different kinds o f perturbations.

r6sidu d '6cho est au moins de l 'ordre de la puissance du signal, donc en d~but de convergence, le r~sidu d'~cho

ddcroft comme [z 2 ; ce r6sultat est r6sum6 dans le tableau II.

TABL. II. - - Valeurs du r6sidu d'6cho pour l'algorithme (S) lorsque Res t grand devant S

Perturbation ""

nulle

gaussienne

binaire arrondie

binaire pure

Gaussienne

2 7~ 2 2 (37) R ~ ~t g N A

Binaire

~t= N2 A 2 (46) R - 4

Pour une per turbat ion nulle, cette d6croissance en ~2 se poursuit 6videmment tout au long de la conver-

gence. I1 est r emarquab le que l 'hypoth~se sur la per turbat ion ne joue aucun r61e et que l 'hypoth6se sur le r6sidu d '~cho donne un simple facteur deux, ce qui est peu impor tant .

111.2.3.2. L e rJsidu d 'Jcho est pe t i t devant le signal.

Les r~sultats relatifs aux petites valeurs du r6sidu d '6cho sont r6sum6s dans le tableau III .

TABL. IIl. - - Valeurs du r6sidu d'6cho pour l'algorithme (S) lorsque Rest petit devant S

Gaussienne Binaire

binaire pure ph6nom~ne scull strict (B = 0) de seuil Rk fluctue autour de S

4~ 4~eSl2~ binaire(B ~arr~ (34') si R ~ B, R ~ ~t ~ NA

gaussienne (38) NA ~/S + B R ~ b t ~

Le ph6nom6ne de seuil est observ6 uniquement en pr6sence de per turbat ion purement binaire ; d6s q u ' u n bruit apparal t , la d6croissance de R se prolonge et cette d~croissance est propor t ionnel le ~t ~.

I1 est remarquable que l 'hypoth6se sur les statistiques du r6sidu d '6cho ne joue plus aucun r61e dans la valeur du r6sidu, tandis que l 'hypoth~se sur la per turba t ion reste un facteur impor tan t (pour les faibles valeurs de B).

Ceci appara i t tr6s clairement sur les figures 4 et 5. I1 s 'agi t d ' une conclusion invers~e par r appor t ~t celle qui pr6vaut lorsque R / S est grand et tout ~ fait conforme ~t l ' intuition.

Nous allons main tenant 6tudier l ' influence d ' u n bruit auxiliaire sur le compor t emen t de R.

9/25 A N N . TI~LI~COMMUN., 3 8 , U ~ 7 - 8 , 1 9 8 4

314 M. BONNET. -- ALGORITHME POUR ANNULEUR D'ECHO

111.3 . S t r a t 6 g i e d u b r u i t f o r e 6 .

L'a lgor i thme (S) est gouvern6 par sgn(ek). Pour que la quantit6 erk soit pr6pond6rante dans l '6valuation de sgn(e~), elle doit ~tre au moins 6gale/ l la valeur dk (en supposant qu ' i l n 'y a pas de bruit en ligne). Lorsque cette condit ion n 'est plus satisfaite, c'est-/t- dire lorsque R ,~ S (bon fonct ionnement) alors, l ' a lgor i thme (S) devient tr~s lent, ainsi qu ' i l a 6t6 explicit6 auparavant . Pour qu 'une correct ion soit effectu6e par l 'a lgori thme, il faut at tendre qu 'un r6sidu d '6cho er~ d6passe la valeur dk. Sans attendre une telle situation, pour que sgn(e~) reste caract6- ristique de sgn(erk), on voit intuit ivement qu ' i l suffit de ramener assez souvent / t z6ro la valeur de dk en lui a joutant un bruit forc6 ind6pendant et de m~me niveau, qui compensera f r6quemment dk.

Pour compenser dk, ce bruit sera ajout6 /l ek juste avant l ' adap ta t ion (ef. Fig. 2) de fa~on /t ne pas per turber la r6ception. Dans la suite, pour simplifier l 'analyse th6orique, nous supposerons que le bruit forc6 suit, comme le bruit de ligne, une loi gaussienne afin de pouvoi r le traiter en mSme temps. Dans la pratique, on peut naturellement utiliser une autre statistique pour ce bruit forc6.

La formule (34') est typique de l ' a lgor i thme (S) q- bruit forc6 ; elle d6crit le compor tement de l 'a lgori thme en fin de convergence (R ,~ S) lorsque R <~ B, c'est-h- dire pour un bruit non n6gligeable devant le signal qui est le bruit forc6. D 'apr6s cette formule, pour que Rba soit minimal , la puissance du bruit forc6 B /t introduire doit sat isfaire:

qui a pour solution B = S. Ce r6sultat est bien conforme au ra isonnement heuristique pr6c6dent.

Dans le tableau IV, nous donnons quelques valeurs du r6sidu R, solution de l '6quat ion (34). Ces valeurs ont servi en particulier g construire la figure 4.

TABL. IV. - - Valeurs th6oriques du r6sidu d'6cho limite, en d6cibels pour l'algorithme (S-P), sous l'hypoth~se er k gaussienne.

\

2-6 2-7 2-s 2-9

20 dB - - 10,8 - - 13,2 - - 14,9 16,2

10 dB - - 10,8 - - 13,4 - - 15,4 17,2

0 dB - - 10,5 - - 13,7 - - 16,8 19,9

10 dB - - 7,5 - - 10,6 - - 13,7 16,8

2-10

- - 17,3

- - 18,8

- - 22,9

- - 19,8

Sur les figures 4 et 5, nous voyons que le ph6nom6ne de seuil appara i t en l 'absence de bruit (perturbat ions purement binaires) ; ce seuil est strict lorsque erk

est binaire, il est un peu moins prononc6 lorsque erk est gaussienne. Pour des perturbations binaires arrondies, c'est-~t-dire avec l ' introduction d 'un bruit forc6, mSme min ime (S /B = 20 dB), le ph6nom6ne de seuil dispara/t . Nous constatons qu ' un coude appara/t , caract6ristique du momen t ofa R passe d 'une d6croissance quadra t ique ~t une d6croissance lin6aire ; ce coude, encore bien marqu6 lorsque S]B = 10 dB, s 'att6nue lorsque la valeur B du bruit augmente.

Quelle que soit l 'hypoth6se sur erk nous observons sur ces figures, comme sur le tableau IV, un op t imum pour des valeurs de B voisines de celles de S. C 'es t bien le r6sultat que nous avions d6duit de l '6quat ion (56) ; dans chaque cas l ' o p t i m u m est atteint par la courbe la plus proche de celle correspondant /t la perturbat ion gaussienne. Ceci confirme le r6sultat que (34') et (38) sont 6quivalentes pour de fortes valeurs de B. Nature l lement il ne peut s 'agir l~t du bruit en ligne, qui empScherait une r6ception correcte, mais du bruit auxiliaire forc6.

Pour de petites valeurs de R/S , l ' introduction d ' u n bruit forc6 entraine une d6croissance lin6aire de R en fonction de [x ; c 'es t ce que nous avions annonc6 dans le tableau I I I .

Dans le cas d ' u n bruit faible, l 'hypoth6se erk gaussienne se mont re plus favorable que l 'bypoth6se binaire. Par contre, l 'hypoth6se sur erk ne joue plus pour de fortes valeurs du bruit fore6 (S]B <~ 10 dB) ; ce r6sultat cor respond /t la formule (34') qui est valable lorsque R ,~ B.

Rappelons que les auteurs de [11] ne consid6rent que l 'hypoth6se er~ gaussienne alors qu'i ls ne t iennent pas compte du b r u i t ; si en pratique le r6sidu erk n'est pas gaussien, leurs r6sultats sont fauss6s.

En conclusion, nous voyons que pour l ' a lgor i thme (S), en d6but de convergence la d6croissance du r6sidu est en [z 2. L ' a lgor i thme (S) plus un bruit forc6 de niveau voisin de celui du signal a un compor tement en ~t en fin de convergence tout /t fait semblable /L celui de l ' a lgor i thme (E) et l ' on peut ainsi s 'expliquer l 'usage du bruit forc6 fait par les praticiens.

Puisque, avec la strat6gie du bruit forc6, les r6sultats selon les deux hypoth6ses sur elk sont tr6s voisines et que la loi de erk est interm6diaire entre une loi binaire et une loi gaussienne, nous conserverons, dans la suite des calculs, l 'hypoth6se er~ gaussienne qui nous don- nera une bonne approx imat ion de la r6alit6 (en pr6- sence de bruit).

IV. S I M U L A T I O N S

I V . 1 . P r 6 s e n t a t i o n d e s s i m u l a t i o n s .

L'analyse qui pr6cade montre que pour R / S fix6, ta valeur du param6t re d ' adap ta t ion de l ' a lgor i thme (E) est ind6pendante de la puissance du signal utile S.

ANN. TI~Lr~COMMUN., 38, n ~ 7-8, 1983 10/25

M. BONNET. -- ALGORITHME POUR ANNULEUR D'ECHO 315

II n ' en est pas de m~me pour l 'a lgori thme (S). En effet, il d6coule de l 'analyse prdc6dente, par exemple de la formule (38), que pour atteindre une qualit6 don- nde R ] S d 'annula t ion d 'dcho, le param6tre doit vdrifier :

/ -g-

(57) = (So) V '

oh [z(S) et [z(So) sont respectivement les param6tres d ' adap ta t ion de l ' a lgor i thme (S) pour des niveaux de signal S e t So �9

Le~ simulations ont dtd faites avec une puissance de signal :

(58) So = 10 -1,

qui est une valeur maximale de S. Pour d 'autres valeurs de S, il faudrai t done diminuer le param6tre d ' adap ta t ion dans l 'a lgori thme (S), conform6ment /t (57).

Si l ' on connal t la valeur de S, en suivant cette r6gle, les conditions des simulations resteront identiques. N6anmoins, la connaissance de la puissance du signal n 'es t pas immddiate de sorte que le choix de ~s pose un probl6me ddlicat aux praticiens. Une stratdgie possible est de choisir une valeur initiale de ~ts assez grande et de diminuer ~t s en fin de convergence si le rdsidu atteint n 'es t pas assez petit (cas d ' un signal de niveau faible).

Les simulations ont 6td faites avec des donndes rdelles. Les donndes ~k sont ~t deux niveaux + 1 et

- - 1, donc la puissance A des donn6es vaut 1. Les donn6es lointaines dk sont aussi A deux niveaux.

Le filtre d '6cho a quatre coefficients:

C T = (0,0281 ; 0,9821 ; - - 0,1961 ; 0,0094).

Sa norme vaut 1 si bien que la puissance d 'dcho P est 6gale /l 1. La puissance de l '6cho n ' in te rvenant dans aucun des r6sultats statiques mais seulement dans la durde de convergence, toutes les conclusions resteraient valables si l ' on consid6rait un 6cho non normalis6.

L 'annuleur d '6cho a 16 coefficients ( N ---- 16). Bien que le param6tre ~s de convergence pour l ' a lgo- r i thme (S) doive &re bien plus petit que le param&tre VtE de l ' a lgor i thme (E) pour atteindre un mSme niveau de r6sidu d '6cho, ces deux param~tres ont 6t6 ini- tialis6s/t la m~me valeur t~o = 2 -6 dans nos simula- t i o n s ; cette valeur correspond / t u n e annula t ion d '6cho R / S = - - 9 dB. Nous verrons en effet, au paragraphe V (Fig. 12), que pour de fortes valeurs de R / S , donc en d6but de convergence, 1'6cart entre t~s et ~E n 'es t pas consid6rable. Cette strat6gie sera justifi6e au pa ragraphe VI par l '6tude de la vitesse de convergence. Au cours des simulations, les param6tres ~s et t~s ont dtd divis6s par 2 toutes les 250 it6rations ou toutes les 500 it6rations, on le pr6cisera sur les courbes.

Pour diff6rentes valeurs du rappor t signal /t bruit , les figures 6 /t 10 donnent les variations du r6sidu d '6cho exprim6 en d6cibels (ou de l 'affaibl issement

- R / S en dB

20

10

~" ~ 1 ~ s s ~ ~

I 4 - - - - ~

.11= 2 - 6 J . l = 2 - 7 J.l - - 2 - 8 .u = 2 - 9 /.I = 2 -10 I I I I

500 1000 1500 2000

FIG. 6. - - Algor i thmcs (E-A) et (S-A).

(a) (E-A), SIB = 20 d B ; (b) (E-A), SIB = 10 d B ; (c) (S-A), SIB = 20 d a ; (d) (S-A), SIB = 10 dB. V-o = 2-6- V- divis6 pa r 2 t o u s l e s 500 pas.

Algorithms (E-A) and (S-A).

(a)

(b)

(c)

(d)

r

11/25 ANN. T~LI~COMMUN., 38, n ~ %8, 1983


20

10

45

- R / $ en d B

# = 2 - 6 Ju = 2 -8 JJ= 2 - I 0

5(

. U = 2 -12 .0 = 2 -~4 I I

FIG. 7. - - Algori thmes (E-A) et (S-A).

- - ( E - A ) - - - ( S - A ) .

(a) SIB = 20 d B ; (b) SIB = 10 da .

~t o = 2-s. ix divis6 par 2 t o u s l e s 250 pas.

Algorithms (E-A) and (S-A).

(a)

I b)

y

BO

15

500 1000 1500

- R e n d B

FIG. 8. - - Algori thmes (S-A) sans bruit . [x o = 2-0.

~. divis6 par 2 tous les 250 pas.

Algorithms (S-A) without noise.

ANN. T~L~COMMtm., 38, n ~ 7-8, 1983 12/25

M. BONNET. - A L G O R I T H M E P O U R A N N U L E U R D' I~CHO 3 1 7

- R e n d B

3G

/

/

.U = 2_ -6 P = 2 -7 I ).1 = 2 -8. }J= 2 - 9 I ~l = ~-10 ,o= 2 -N

1000 2000

FIG. 9. - - C o m p a r a i s o n d e (S -A) . s ans b r u i t - - . - - a v e c BIS = - - 20 d B .

Comparison of (S-A).

- - R / S en d B

20

lO

o

- 5

�9 .,,. , I f ~ l / l ~ I

/~ ~,-- :" ~ /r,.__.---. " " ' - I I ]A / # ~1~i -

I : ' ; ' r s j _ . ,"", , ' -

~, # I ." " ~ . , , " y

, " f ' Z " " / x r " -

~.1 = 2 - 6 ~U = 2 - 8 bl = 2 - 1 0 .U = 2 - ~ i I

~u = 2 - ~

. . . . . ( E - P ) - - ( S - P )

(S -P )

looo

FIG. 10. ~ C o m p a r a i s o r t d e ( E - P ) e t (S-P) . SIB E = 20 d B - - . - - (S-P) SIB s = 0 d B SIBs = 10 dB (S-P) SIBs = - - 10 d B SIB s = 20 d B

Comparison of (E-P) and (S-P).

2 0 0 0

13/25 ANN. TIBLIECOMMUN., 38, n* 7-8, 1983

318 M. BONNET. -- ALGORITHME POUR ANNULEUR D'I~,CHO

puisque la puissance de l '6cho est ici I), en fonction du nombre d'it6rations et du coefficient V-.

Les courbes en escalier repr6sentent les rfsidus th6oHqueS limites obtenus par les formules du paragraphe 3. Les lignes pointilMes indiquent un niveau de r6sidu d '6cho ~t 10 dB sous le bruit, correspondant

la condit ion R ,~ B ; il s'agit l~t d 'une bonne qualit6 d 'annulat ion d'6eho.

IV.2. R6sultats et commentaires.

Les figures 6 ~ 9 sont relatives h la phase A, la figure 10 est relative ~ la phase P.

On voit que le niveau 10 dB sous le bruit (lignes pointilMes sur les courbes) est, pour (E-A) atteint ~t peu pr6s en m~me temps - - c'est-~t-dire pour une m~me valeur de tx et pour un mSme nombre d'it6rations (ici, ~ = 2 -7 apr6s environ 500 it6rations) - - quel que soit le bruit (Fig. 6 et 7). En ee qui eoncerne (S-A), pour que ce niveau soit atteint, il est n6cessaire de diminuer ~ lorsque B diminue.

Pour (S-A), en l'absence de bruit (ce qui correspond notre perturbat ion nulle), nous avons vu th6orique-

ment au paragraphe III que le r6sidu d '6cho est proportionnel ~t ~z 2 tout au long de la convergence. La figure 8 confirme ce r6sultat en montrant une droite de pente 0,6 eorrespondant ~t la formule (37) lorsqu 'on trace loglo R en fonction de loglo~Z.

Sur la figure 9, on observe l'influence du bruit. Au d6but le bruit n 'est pas pr6pond6rant par rappor t au r6sidu d'6cho. Les deux courbes, correspondant respectivement ~t B/S = - - 20 dB et au cas sans bruit, ont la m~me pente. Puis, lorsque le bruit devient important par rappor t au r6sidu, environ apr~s 1 500 it6rations, on voit nettement que la pente diminue pour la courbe en pointill6s larges correspondant ~ la pr6sence de bruit, eonform6ment aux 6tudes th6oriques du paragraphe 3.

Sur les quatre figures 6 h 9, nous observons l ' int6r& qu'il y a ~t utiliser une phase d 'apprentissage ; la d6croissance du r6sidu est tr~s rapide et nous observons de longs paliers lorsque V- n ' a pas diminu6 assez rapidement. Les r6sultats de simulation de (S-A) atteignent le r6sidu th6orique limite (courbe en escalier) m~me lorsque i~ est faible. Pour l 'a lgori thme (E), que ce soit en phase A ou en phase P, le r6sidu limite n'est pas atteint lorsque t~ devient tr~s petit. Ce fair est normal puisque la convergence se ralentit ; on n 'a pas eu le temps d 'a t te indre la valeur limite. Pour (S-P), ces valeurs th6oriques sont atteintes sauf dans le cas d ' un tr~s fort bruit (S[B = - - 10 dB) qui ralentit la convergence. Le niveau de bruit fore6 doit done rester sous la puissance du signal.

Une question se pose lors des simulations : apr~s combien d' i t6rations faut-il diminuer V- ?

En comparan t les figures 6 et 7, on observe qu 'en divisant /.t par 2 plus rapidement - - toutes les 250 it6rations plut6t que toutes les 500 ~ l 'algori thme (E-A) atteint plus vite un faible r6sidu d '6cho et

cela surtout en cas de bruit fort. Pour (S-A), l 'avantage apport6 par la r6duction de V- est d 'autant plus net que le bruit est plus faible.

Sur les courbes examin6es jusqu'h pr6sent, nous constatons que th6orie et simulations s 'aeeordent. Certaines remarques sont h faire au sujet de (S-P).

Le tableau IV ainsi que les figures 4 et 5 du paragraphe 3 font apparal tre pour tout t~ ~< 2 -6 un minimum de l '6cho r6siduel limite lorsque B = S. Ce dernier r6sultat n 'est pas v6rifi6 par l'exp6rienee. Darts les simulations (Fig. 10), pour S[B = 10 dB et S]B = 20 dB, les r6sidus obtenus au bout d 'un temps fini sont plus faibles que celui correspondant

S[B ----- 0 dB ; le r6sidu relatif h S[B = 10 dB 6tant cependant meilleur (plus petit) que celui correspondant

S[B = 20 dB. Cette diff6rence entre Ia th6orie et la pratique est li6e ~t la vitesse de convergence comme nous le verrons plus loin.

L'6tude faite ici avee le bruit en ligne nk peut ~tre utilis6e pour la strat6gie du bruit fore6 qui doit eom- penser la pr6pond6rance du signal par rappor t au r6sidu d'6cho dans l '6valuation de sgn(ek). D'apr~s les courbes repr6sent6es figure 10, le bruit forc6 h introduire est de l 'o rdre du dixi~me de la puissance du signal, c'est-h-dire net tement moins que la valeur th6orique B = S. Nous verrons dans le paragraphe suivant que cette strat6gie est compatible avec la complexit6 des algorithmes.

V. PRI~CISION ET COMPLEXITI~

V.1. Pr6cision des coefficients de l'annuleur d'6cho pour l'op6ration d'adaptation.

Les r6sultats pr6c6dents sont valables pour des calculs effectu6s en pr6cision infinie. Pour qu'ils le restent en pr6cision finie, il faut que les corrections sur les coefficients de l 'annuleur d'6cho soient assez importantes pour 6tre prises en compte par l 'algorithme (cf [21] et [22]).

Si les d6compositions binaires des composantes r6elle et imaginaire d 'un coefficient de C~ s'6erivent sur la base (2 ~ 2 "-1, ..., 2-n), il faut que l '6eart-type des incr6ments des algorithmes soit de l 'ordre du dernier bit de C ' (eomposante r6elle d 'un coefficient de Ck).

! Ecart-type de Re(bt 0t*_ ~ ek) >~ 2 -b pour (E), (59)

Ecart-type de Re(v. ~*- j sgn(ek) ~> 2 -~ pour (S).

Nous appellerons bs (resp. bE) le dernier bit d 'un coefficient de Ck pour l 'algori thme (S) (resp. (E) ) , et nous noterons Q le rappor t de ces deux quantit6s

2-- bs

(60) Q -- 2_bE.

Etudions les diff6rents cas.

ANN. Ti~LIgCOMMUN., 38, n ~ 7-8, 1983 14/25


V.l.1. Phase (A), it r~sidu d'~cho fix6.

L'~cart ek vaut ici erk + n~ ; done, d 'apr~s (59), le plus petit entier b assurant la convergence satisfait :

2 -b = [ z 4 A ~ + B pour (E), (61)

2 -b = fz ~/A pour (S).

D 'apr6s notre 6tude sur les r6sidus, en consid6rant l 'hypoth6se er~ gaussienne, on obtient le tableau V qui donne les valeurs des param6tres V- et b pour une valeur fix6e du r6sidu d'6cho.

D 'apr6s ce tableau, nous avons :

4z (64) a = So ~/-~ ( R I B + 1)"

Que l ' on soit dans le cas r6el (So = 1) ou dans le cas complexe (So = ~/2-), le quotient Q est toujours inf~rieur ~ 1 done bs est plus grand que bE �9 Cherchons la diff6rence entre bs et bE .

Si le pas d ' incr6mentat ion reste le mSme apr6s l 'apprentissage, on a :

(65) (R/B)apprentlssage = (R[S)p . . . . . . . t .

Ce deuxi6me rappor t est tr6s petit par rappor t 1 pour une bonne annulat ion d '6cho d o n c :

(66) Q ~ ~/2-[,v~.

Cette quantit6 6rant comprise entre 1]2 et I, nous voyons que (S) ne demande qu 'un bit de plus que (E) pour atteindre le m~me niveau de r&idu. Ce handicap de (S) par rappor t ~t (E) est minime, il est largement eampens6 par la simplicit6 de l 'a lgori thme (S).

D 'apr6s le tableau V, on a :

(67) --~s ~ ~/2-B__ ~E So x/-~"

Ce rappor t &ant beaucoup plus petit que 1, en cas de faible bruit (eomme pour le cas du bruit de ligne) il est done normal de diviser ~z beaucoup plus souvent dans (S) que dans (E). C'6tai t ee que mon t r a i t la compara ison des figures 6 et 7 au pa rag raphe 4.

V.l .2 . Phase (P), /t r6sidu d ' & h o fix6.

En r6gime permanent , rappelons que :

ek = erk + n~ + ark.

Grace aux relations (61) et aux formules donnan t les valeurs des r6sidus, on obtient le tableau VI.

Ici le r appor t Q est plus difficile /t calculer qu ' i l ne l '6tait en phase (A). Appelons b~ le dernier bit d 'une composan te de C~ sous l 'hypoth~se auxiliaire << ek est une variable al6atoire gaussienne >>. Le rappor t Q est alors le produi t de Qt et Q2 d6finis pa r :

(70) Q~ = 2-b~/2 -ws, Q2 = 2 - b ' s / 2 - b L

SOUS eette hypoth6se gaussienne, nous pouvons appliquer les formules (64) ~ (66) en re.mpla~ant B par B + S ; nous voyons que, puisque ~zENA ~ 1,

(71) Q2 =

Ce r6sultat est le m~me que celui obtenu en phase (A) : Q2 est toujours compris entre 0,5 et 1.

Evaluons main tenant Q , . Sa valeur d6coule de (68) et de l 'expression de b~ :

(72) Q~ = ~/R/B + 1 + SIB ( S/B )" 4 R I B + 1 e x P \ 2 ( R / B + 1)

De ces formules, nous d6duisons la diff6rence des pr6cisions :

(73) bs - - bE ~ 1 - - log2 Q,

TABL. V. - - Valeurs des param~tres ix et ben phase (A) pour chaque algorithme

Algorithmes (S) (E)

iz = fiR)

Dernier bit 2 -b

2 ~/2-R p t s =

s o N A %/~ ~ /R + B

(62) 2-% = 2 ~]2- R _ _ �9 o x 4 - x 4- 4-a+9

(63)

2 R IxE N A B

2 R 4 - ~ + B 2-b~ _

Nx /AB

TABL. VI. - - Valeurs des param6tres ~ et ben phase (P) pour chaque algorithme

Algorithmes (S) (E)

v, = fiR)

Dernier bit 2 -~ (68)

2 ~ / 2 R e -SI2(R+B) i t s - -

s o NA %/~ ~/R-+ B

2_1, s = 2 ~/2" R e -S|2(R+B) �9 o N 4 2 4~- 4 R + B

[LE

(69) 2 -bE =

2 R N A (B + S)

2 R 4 R + B + S N 4 2 ( s + s)

15/25 ANN. T~LfiCOMMUN., 38, n ~ 7-8, 1983

320 M. BONNET. -- A L G O R I T H M E P O U R A N N U L E U R D' I~CHO

et nous remarquons que b s - - b E est ind6pendant de N alors que bE augmente avec N ; donc, plus N e s t grand, plus faible est la diff6rence relative bs-b~ par rapport h bE.

Gr~tce aux formules pr6c6dentes, nous avons repr6- sent6 sur la figure 11, la diff6rence des pr6cisions

b s b E

10

5 1 1

I ' o 20

-RIs en dB.

FIG. 11. -- Dif f6 re r t ce de s p r6c i s ions n6cessa i r e s a u x a l g o r i t h m e s (E ) et (S).

b r u i t d e l i gne S / B = 20 dB - - - - b r u i t f o r c 6 S I B = 10 d B . . . . b r u i t fo rc6 S I B = 0 d B

Difference between the top word sizes for the algorithms (E) and (S) .

b s - bE ; bE est calcul6 pour un bruit de ligne tel que S/B = 20 dB, bs est calcul6 soit pour un bruit de ligne tel que S[B : 20 dB, soit pour un bruit forc6 tel que S]B : 0 dB, ou 10 dB.

La diff6rence bs - - b~ est tr~s grande pour une bonne annulation d '6cho lorsqu'il n ' y a que du bruit de ligne (S/B = 20 dB). Nous voyons clairement, sur cette figure, quel int6r& il y a h introduire un bruit forc6 (S/B = 0 dB) dans l 'a lgori thme (S). Un bruit de ce niveau ram6ne la diff6rence / t u n seul bit. La figure 12 repr6sente les valeurs de Ss n6cessaires pour atteindre une annulation d '6cho R]S. Ces valeurs sont donn6es pour trois niveaux du signal : S = - - 10 dB, S : - - 25 dB et S : - - 40 d B e t pour diff6rents niveaux de bruit forc6 : S]B = 20 dB, S]B : 10 dB et SIB = 0 dB. La courbe de r6f6rence pour l 'algorithme (E) est repr6sent6e pour un bruit de ligne tel que S]B = 20 dB.

Le param6tre ~s d6pend de ~/S ; plus le niveau S du signal est faible, plus faible est ~-s �9 Par exemple, pour un r6sidu d '6cho R]S : 0 dB, si S = - - 40 dB, ~s = 2 -a~ et si S = - - 10 dB, Ss = 2 - 6 . Cette diff6- rence reste constante lorsque R/S diminue.

Lh encore, nous voyons que l ' introduction d 'un bruit forc6 tel que S/B = 0 dB augmente la valeur de i~s qui devient alors comparable ~t celle de ~t~.

I1 est facile de voir d 'apr~s les formules (68) et (69) donnant la pr6cision des deux algorithmes que lorsque S varie :

2 - b, .= 7. s #S--[S~o, 2- b~ = XE # - E / S o ,

ANN. TI~LECOMMUN., 38, n ~ 7-8, 1983

ZC

10

."// ,' / / ,..1

/ ' / / .." ~ (~}

,,,it/ . " .- J / / / . " / / " re)

/ ' .li~ I / / I~. (b) ,, / .-1 Z ; . . , - " /

. , . x - " . / / / 1 / / (-}

..i-.-- ,',7--7 / ......... - _ z

I0 0 10 - R /S en dB

FIG. 12. - - C o m p a r a i s o n d e s p a r a m 6 t r e s ~t E e t ~t s p o u r d i f f 6 r e m e s v a l e u r s d e S.

. . . . S = - - 40 d B (a ) S / B s = 20 d B S = - - 25 d B (b ) S]B s = 10 d B

- - S = - - 10 dB (c) S / B s = 0 dB

Comparison of the parameters ~t E and ~t s for different values orS.

off Zs et Zr sont deux quantit6s ind6pendantes du niveau S de signal utile. Ainsi pour S :~ S o , on obtien- dra les pr6cisions en ajoutant dans les deux algo-

l rithmes, le m~me nombre n = ~ log2(S/So)de bits

aux valeurs relatives au niveau So. La valeur So = 10-1 prise dans les simulations correspond ~t une att6nuation tr6s faible de la ligne et le changement sera toujours en faveur de l 'algorithme du signe.

Ces r6sultats seront utilis6s dans le paragraphe suivant pour 6valuer la complexit6 relative /t chaque algorithme.

Cherchons maintenant la pr6cision n6cessaire sur les coefficients de l 'annuleur pour la mise en oeuvre du filtrage.

V.2. Precision des coefficients de l'annuleur d'~cho pour l'op6ration de filtrage.

Lors du filtrage, soit @q l 'erreur due h la quantification (troncature de bits), dont les composantes sont :

(74) e~ = ( C ~ - - C ~ ) ~ k _ j ; J = 1,..., N,

off C~ est une coordonn6e de l 'annuleur d '6cho r6ellement calcul6.

Appelons bit de filtrage be le dernier bit de C [ . On peut supposer que l 'erreur @, suit une loi uni- forme, les composantes 6tant ind6pendantes. Alors

N (75) E(II JI 2) = ~ So 2 A 2 -2be .

16/25

M. BONNET. - ALGORITHME POUR ANNULEUR D't~CHO 321

Soit p le rappor t acceptable du r6sidu d'6cho R 5. cette erreur :

R (76) tz - - E I I ( o . N = )

Le bit bf devra donc v6rifier :

N (77) P i 2 s2~ A 2 -2bt ~ R.

Par exemple, s i p vaut 4, nous aurons :

1 s 2 N A (78) bf >~ ~ log2 3 R

Evidemment, plus R e s t petit plus bf doit ~tre grand. Dans cette 6valuation de bf nous n 'avons pas fait

intervenir l 'algorithme. Ainsi be a la m~me valeur pour (E) et pour (S).

V . 3 . C o m p l e x i t 6 d e s a l g o r i t h m e s .

Dans les algorithmes 6tudi6s apparaissent des multiplications et des additions. Dans le but de comparer la complexit6 des algorithmes (E) et (S), il serait souhaitable d 'avoi r un seul nombre qui r6sume la complexit6 de l 'ensemble des op6rations de calcul pour chacun des deux algorithmes (E) et (S), et qui tienne compte de la pr6cision n6cessaire sur les coefficients.

M~me en envisageant de d6composer la multiplication en plusieurs additions, un tel but n 'est pas atteint car il faut aussi tenir compte des d6calages n6cessaires pour t ransformer les multiplications en additions. Quelques auteurs [23, 25] ont proc6d6 ainsi en donnant des m6thodes qui tendent ~ simplifier l 'op6ration multiplication. Mais, ils ne d6finissent pas une unit6 de complexit6 puisque l'6quivalence entre multiplication et addit ion varie selon les mat6riels utilis& : longueur des roots en machine, type d'arith- m6tique de la machine, par exemple code binaire utilis6 (compl6ment ~t 1, ~t 2, etc.), type d'unit6 arith- m6tique et logique utilis&

C'est pourquoi nous avons pr6fdr6 d6finir deux op6rations 616mentaires: la multiplication (resp. addition) 616mentaire qui est la multiplication (resp. addition) de deux bits. I1 s'agit en fait d 'une arith- m6tique binaire, relic qu'elle est utilis6e chez Control Data et dans le syst6me Cray 1 [26], extr~mement puissant.

Nous allons done 6valuer la complexit6 des algo- tithmes h l 'aide des deux nombres : nombre de multiplications 616mentaires et nombre d'additions 616mentaires ; dans cette 6valuation, nous devons tenir compte des op6rations de filtrage et d 'adaptation.

Nous supposons que les donn6es sont complexes.

En filtrage, nous avons vu au paragraphe pr6c6dent que les deux algorithmes (E) et (S) demandent la m~me pr6cision, A savoir b f , nombre de bits d 'un coefficient.

Ici, puisque les donn6es ~k valent • 1 • j , le nombre de multiplications 616mentaires et le nombre d 'additions 616mentaires n6cessaires au filtrage sont tous les deux 4 bf par coefficient complexe.

En adaptation, si l 'on suppose que ek s'6crit sur v bits, voyons ce que demande chaque algorithme.

Pour calculer (E) demande (S) demande

~/,* ek

c~f* sgn(ek)

Ck/+l

4 v multiplications 2 ,~ additions

2 b E additions

24 multiplications additions

2 b s additions

(i repr6sente la i-6me composante des vecteurs ot k et Ck+x).

De plus un d6calage binaire est n6cessaire pour (E) comme pour (S) lors de la multiplication par V-, ~t condit ion que V- soit de la forme 2 -p comme c'est le cas en pratique.

La complexit6 en nombre de multiplications 616- mentaires par coefficient complexe s 'exprime par les formules (79) pour (E) et (80) pour (S).

(79) C~ = 4 b e + 4 V,

(80) Cs ~ = 4br + 4.

La complexit6 en nombre d 'addit ions 616mentaires par coefficient eomplexe s 'exprime par les formules (79') pour (E) et (80') pour (S).

(79') C + = 4 b r + 2 , ~ + 2 b E ,

(80') Cs + = 4 b f + 2 + 2 b s .

Le gain en multiplication 6tant important pour (S), on voit alors quelle est la r6duction de complexit6 apport6e par (S). Si de plus les donn6es ~k ne sont pas binaires, 0Ok s'6crira sur plus de 1 bit et la diff6- rence entre C~. et Cs ~ sera encore plus importante.

En attr ibuant le m~me eofit A l 'addit ion et 5. la multiplication 616mentaires, on peut d6finir la com- plexit6 globale selon :

c E = c ~ + c ~ + , (81)

Cs = c ~ + c~-.

La figure 13 montre l 'avantage d'utiliser l 'a lgori thme (S) avec un bruit forc6 de m~me puissance que le signal. La diff6rence relative (CE - - Cs)]CE est repr6- sent6e en fonction de R [ S dans les deux strat6gies :

- - (S) n'utilisant qu 'un bruit de ligne, le m~me que celui de ( E ) ;

- - (S) avee un bruit forc6 de m~me niveau que le signal.

Les courbes sont donn~es pour 3 valeurs du para- m6tre v (longueur binaire du mot e~).

17/25 ANN. T~L~COMMUN., 38, n ~ 7-8, 1983


160

130

100

0,3

q2

0,I

CE

S / B E =

~ (c)

CE-- Cs

CE

I t \ " - (c) "~.~..........

I . / I X~X I I I ~, I

10 \ x 15 18 25 ~.,. 3 0

- - R / S en dB

FtG. 13. - - �9 Complexit6 absolue de E : C E pour diff6rentes valeurs de v.

(a) v = b E (b) v = 7 (c) v = 3. �9 Diff6rence relative des complexit6s (CE-Cs)IC E pour un

bruit de ligne bl ~ S / B = 15 dB - - et un bruit forc6 br /t S I B = 0 dB - - - et pour les mSmes valeurs de v.

(a) v = b E (b) v = 7 (c) v = 3. �9 Absolute complexity o f (E) : C E for different values o f v. �9 Relative difference in complexity with additive noise S I B =

15 dB, - - , and extra-noise SI B = 0 dB, - - - , for different values o f v.

La v a l e u r v ---- 3 bi ts c o r r e s p o n d ~t un cas ex t reme

off l ' e r r e u r s '6cr i t avec ~t pe ine un peu p lus de pr6c is ion

que sgn(ek). Ce sera donc le cas le p lus f a v o r a b l e

l ' a l g o r i t h m e (E). L a va leu r v = bE est u n a u t r e cas

extrSme, le p lus f a v o r a b l e ~t (S), oh ek r equ ie r t a u t a n t

de p r6c i s ion que les coeff icients de l ' a n n u l e u r . Enfin,

la va l eu r i n t e rm6d ia i r e v ---- 7 c o r r e s p o n d ~ l 'u t i l i -

sa t ion d ' u n conve r t i s s eu r 8 bi ts (1 bi t 6 tant r6serv6 au signe) qui est a d a p t 6 au n iveau So = 10 -~ d u signal, dans nos s imula t ions .

N o u s v o y o n s que, m S m e sans bru i t forc6, la c o m - plexit6 d~finie p r ~ c 6 d e m m e n t est ne t t emen t f avo rab l e

l ' a l g o r i t h m e (S), s au f dans le cas extrSme oh v ---- 3 et peu t 8tre auss i en fin de convergence p o u r v ---- 7 bi ts . I1 est 6vident d ' a p r 6 s cet te f igure que l ' i n t r o d u c t i o n d ' u n b ru i t forc6 accen tue encore la diff6rence de complexi t6 en f aveur de (S) ; p a r exemple p o u r un niveau de r6s idu c o m p r i s en t re - - 18 dB et - - 25 dB sous le s ignal , le ga in r e l a t i f en op6ra t ions 616men-

ta i res de (S) p a r r a p p o r t ~t (E) est de 25 ~o lo r sque v ---- 7, il est de 6 ~o l o r sque v = 3 et il a t t e in t 40 lo rsque v = b E .

N o u s r e m a r q u o n s l ' 6 c a r t e m e n t cons t an t des deux courbes (bru i t de l igne, b r u i t forc6) : p o u r une va leu r de R / S donn6e. L a diff6rence p o u r un b ru i t de l igne et p o u r un b r u i t fore6 est la m~me quel le que soi t la va leur du p a r a m 6 t r e v.

Le bu t de la f igure 14 est le cho ix du n iveau de b r u i t forc6. P o u r cela, on t r ava i l l e ~ R ] S fix6 ~ - - 15 dB ; dans ce cas, bE = 10 b i t s et bf ---- 6 bits. Ce t te f igure d o n n e le ga in r e l a t i f en complex i t6 et la complex i t6 abso lue ; elle m o n t r e q u ' u n o p t i m u m de complex i t6 est a t te in t p o u r un n i v e a u de b ru i t forc6 de l ' o r d r e de la pu i ssance d u s ignal . Le m a x i m u m des cou rbes 6tant assez p la t , une l a t i t ude est laiss6e p o u r le con- tr61e de S, qui p e u t va r i e r a p p r o x i m a t i v e m e n t de S ] B = - - 5 dB ~t S ] B = 5 dB. Pou r v = 7, le ga in en op6ra t ions 616mentaires de (S) pa r r a p p o r t ~ (E) est a lors de 30 ~ . Ce t t e va leu r est un ga in i m p o r t a n t .

I1 t au t n o t e r que , p o u r u n s ignal de n iveau S p lus fa ib le que S o , la c o n v e r s i o n a n a l o g i q u e - n u m 6 r i q u e exige plus de bi ts . A i n s i ~ a u g m e n t e et on conse rve le ga in r e l a t i f de 30 ~o en complexi t6 .

L a s t ra t6gie d u b r u i t forc6 est donc conf i rm6e p a r l ' 6 tude de la complex i t6 .

D a n s ce p a r a g r a p h e , nous avons soul ign6 le fa i t que l ' a l g o r i t h m e (S) d e m a n d e un n o m b r e bs de b i t s p lus g r a n d p o u r les coeff ic ients de l ' a n n u l e u r que l ' a l g o r i t h m e (E), avec une diff6rence bs - - b E tr6s for te - m e n t m a r q u 6 e l o r s q u e les cond i t i ons de fonc t i onne - m e n t son t mei l l eures , c ' e s t -h -d i r e que le r a p p o r t signal sur b r u i t de l igne augrnen te et que le r6s idu d ' 6cho d iminue . N o u s avons indiqu6 q u a l i t a t i v e m e n t et q u a n t i t a t i v e m e n t l ' e f fe t f avo rab l e d u b r u i t forc6 sur la r6duc t ion de la l o n g u e u r bs des coeff ic ients en machine . N o u s a v o n s vu c o m m e n t un 6qui l ib re q u a n t i t a t i f peu t s ' 6 t a b l i r en t re les deux a l g o r i t h m e s : si les coeff ic ients d a n s (S) d e m a n d e n t b e a u c o u p p lus de bi ts que d a n s (E), (S) n ' e x ige p o u r t a n t pas p lus d ' o p 6 r a t i o n s 616mentaires p u i s q u ' i l t ra i te le s igne de l ' 6ca r t qui n ' a q u ' u n seul bi t . Ce r6su l ta t ba scu l e m~me tr6s l a r g e m e n t en f aveur de (S) l o r s q u ' o n ut i l i se la t echn ique du b r u i t forc6 p o u r laquel le bs est vo is in de b,~ + 1. Le ga in r e l a t i f en complexi t6 est a lors de 30 ~o env i ron .

ANN. TELECOMMUN., 38, n ~ 7-8, 1983 18/25

M. BONNET. -- ALGORITHME POUR ANNULEUR D'I~.CHO 323

10<3

75

5 0

Z5

CE

Op~rahons el~mentaires

CF

/ /

/

/ . . . . . . . . . . . . . . . . . . . . . . . . . . / _ -___

/ , / "

C$ ..,....,.. J "

- 1 0

",\ \

S/BendB I I "~'. I

1 0 2 0

FIG. 14. - - Diff6rence de complexit6 de (E) et (S) pour RIS = - - 15 dB en fonction de SIB, pour diff6rentes valeurs de v. - - ~ = bE, - - - - v = 7, - - - - v = 3.

Complexity difference between (E) and (S) with RIS = - - 15 dB, versus SIB, and for different values of v.

VI. V I T E S S E D E C O N V E R G E N C E

D a n s les pa ragraphes prdcddents, nous avons considdrd l ' a l g o r i t h m e du signe en rdgime s ta t ionnai re , c'est-~t-dire apr6s la phase t rans i to i re d 'd tab l i s sement de la va leur l imite d u r6sidu. I1 nous faut m a i n t e n a n t considdrer la vitesse h laquel le cette va leur l imite est at teinte.

A l ' a ide de la puissance Rk d 'dcho ids iduel l ' i n s t a n t k (cf. (48) ) , on peut ddfinir la vitesse de convergence pa r :

Rk+ t (83) V~ = - - 10 lOglo ~ en dB par i tdra t ion .

Elle a dtd ealculde p o u r chaque a lgor i thme. N o u s d o n n o n s , en annexe B, les rdsultats du calcul de Vk dans les diffdrents cas, p o u r les formules (B.4), (B.8), (B.12) et (B.13) pa r (E-A), (S-A), (E-P) et (S-P).

19/25 ANN. T~L~COMMtm., 38, n ~ 7-8, 1983

324 M. BONNET. -- A L G O R I T H M E P O U R A N N U L E U R D' I~CHO

L'6tude analytique compara t ive &ant d61icate, nous avons calcul6 num6riquement les valeurs de la vitesse de convergence. Nous savons que pour atteindre un m~me r6sidu d '6cho en fin de convergence, le param6tre ~s est plus petit que [aE �9 Le param6tre [aE &ant choisi pour obtenir une certaine valeur limite (R]S)Hm du rappor t R/S, le pa ram&re [as devrait th6oriquement &re li6 implicitement h [aE par les formules (84), comme il d6coule des tableaux V et VI. Ceci conduit h :

2 ~/2 (RIS)Hra B]S (84) [as t~ = ~/~ N A 4(-t~/8)11m -~- B[S ~/~' phaseA,

2 ~/2 (R/S),m

exp - - 2 ( R / X ) ) l , m + BIS) ' phase P.

Par exemple, pour at teindre en phase P u n r6sidu d '6cho (R[S)Hm -- 15 dB, on obtient d 'aprSs ces formules :

[aE = 2 -8 [Zs ~~ = 2 -25 pour S = - - 10 dB,

[aS (O) = 2 -27,5 pour S = - - 25 dB,

[Zs r176 = 2 -30 pour S = - - 40 dB.

D'auss i petites valeurs de ~ts correspondent au r6gime stationnaire mais ne sont pas n6cessaires tout au long de la convergence. C 'es t pourquoi, nous avons 6tudi6 le compor t emen t de la vitesse de convergence dans deux m6thodes pour lesquelles les paramStres valent respectivement :

(85) [as ~1) = [aE,

(86) [a~z) = [aE ~/S.

Ces deux cas sont justifi6s par les consid6rations suivantes, faites par exemple pour le cas de l 'algo- r i thme r~el.

L ' incr6ment de l ' a lgor i thme (E)

[aE O~k ek ,

peut s)6erire :

(87) [a~ ~ [e, I sgn(e~).

En normalisant les incr6ments de (E) et (S), nous voyons que (87) est exactement l ' incr6ment de l 'algo- r i thme (S) en prenant :

( 8 8 ) [as = [a~le~l.

Si done l ' on pouvai t changer [as assez souvent pour assurer (88), l ' a lgor i thme (S) aurait exactement la m~me vitesse que (E).

La valeur initiale du vecteur Ck est usuellement z6ro. Ainsi, en d6but de convergence, lorsque le r6sidu d '6cho est grand devant le signal (en n6gligeant le bruit), [ek[ fluctue autour de l '6cart- type de l '6cho. Lorsque la puissance P de l '6cho vaut 1, sa valeur maximale, cela justifie la strat6gie donn6e par la formule (85).

En fin de convergence, lorsque le r6sidu d '6cho devient petit devant les donn6es lointaines, la puis-

sance de ek est de l 'o rdre de S si bien que la formule (88) devient pra t iquement 6quivalente h (86). D'a i l - leurs, en consid6rant la formule exacte (84), on retrouve aussi ~t peu prSs (86) en fin de convergence. En effet, lorsque RIS est t r& petit devant B/S, cette formule donne en phase ( A ) :

[Xs ~~ = [aE q ~ 10-1,

valeur assez proche de celle de la m6thode (86). On remarque aussi que cette derni6re m&hode

donne des r6sultats coh6rents avec la strat6gie du bruit forc6.

En effet, d 'aprSs la formule (84), en phase (P), si BIS est trSs faible, d~s qu 'une annulation d '6cho moyenne est atteinte, la valeur [as ~~ donn6e par (84) est n6gligeable devant celle donn6e par la strat6gie (86). La vitesse correspondante est alors tr6s faible. Mais, l ' in t roduct ion d ' un bruit forc~ tel que B]S = 0 dB donne, par cette mEme formule (84) :

[as ~ ~ [aE~/S • 0,96, s i R / S ~ I,

[as t~ = [aE ~/S • 0,8, si R ~ S.

Ces valeurs sont trSs voisines de celles correspondant h la m&hode [as tz) ---- [aE ~/S. L ' in t roduct ion d 'un bruit fore6 de niveau 6gal ~t celui du signal, au mo men t oh R e s t voisin de S, augmente done consid6rablement la vitesse de l ' a lgor i thme (S).

La strat6gie (85) est done justifi6e en ddbut de convergence et (86) l 'es t en fin de convergence.

D 'apr6s les formules donn6es en annexe B, il est facile de voir que la vitesse de l 'a lgori thme (E) est ind6pendante de la puissance S du signal. Pour l 'a lgori thme (S), que ce soit en phase (A) ou en phase (P), la vitesse est fonet ion de [asia/S, RIS et BIS soit :

) S ) "

En utilisant la m&hode li6e ~ la formule (86), nous voyons que [as[~/N est une constante si bien que, dans ce cas, la vitesse Vs est ind6pendante du niveau S de signal. I1 n ' en est 6videmment plus de m~me lorsque [as = [aE; nous &udierons dans ce cas l 'influence de S.

Les figures 15 et 16 repr&entent les valeurs th6o- riques de la vitesse en phase (A) et de la vitesse en phase (B), respectivement, pou r chacune des deux m6thodes correspondant aux formules (85) et (86).

Sur ces figures, nous observons dans tous les cas, une zone de valeurs de RIS, favorable ~t l 'a lgori thme (S) qui dans cette zone est plus rapide que (E). Nous allons profiter de ce ph6nom6ne pour am61iorer consid6rablement la vitesse de l 'a lgor i thme (S) par le choix d ' un [as d6croissant.

La valeur de [an a 6t6 choisie 6gale ~t 2 -8, comme dans l 'exemple pr6c6dent, pour atteindre, en phase (P) l ' annula t ion d '6cho de (RlS)nm ----- - - 15 dB. La vitesse de (E) est alors d ' env i ron 33 dB pour 1 000 it6rations tant que ce seuil de - - 15 dB n 'est pas

ANN. T)~L~COMMUN., 38, n ~ 7-8, 1983 20/25

M. BONNET. - ALGORITHME POUR ANNULEUR D'ECHO 325

V en dB pour 1000 it~raticns Ca } (b}

(c)

100

5 0

/ / /

/ / /

/ /

/ /

/ /

/ /

/ /

/ /

/

11 4 0 - - 3 0 - 2 0 - 1 0 0 ~ 10

\

\

|

I

- R / S en dB

FIG. 15. - - Vitesses de convergence, en dB pour 1 000 it6rations, des algorithmes (E) et (S) en phase (A) pour diff6rentes valeurs de S et pour 2 strat6gies sur t~s.

- - ( S ) , t ~ s = l Z E , ( a ) S = - - 4 0 d B , ( b ) S = - - 2 5 d B , ( c ) S = - - 1 0 d B

. . . . (S), ~s = ~EV g - - . - - (E-A).

Convergence speed of ( E) and ( S) , in dB/1 000 iterations during the learning phase, for different values orS and for two strategies over tXs .

atteint, la vitesse chu tan t p o u r atteindre la valeur 0 au point R / S ---- - - 15 dB (cf. Fig. 10). La figure 9 m o n t r e que, p o u r les deux m6thodes (85) et (86), la vitesse de (S) croi t lorsqu~, R / S diminue, c 'est-h-dire au fur et h mesure que l ' a nnu l a t i on d '6cho s'am61iore.

Pour la m6 thode tZs H ~ = tZE, nous avons represent6 les vitesses p o u r 3 valeurs de la puissance de S :

10 dB, - - 25 dB et - - 40 dB ; la premi6re corres- p o n d a n t & la valeur So ---- 10 -1 de nos simulations. N o u s r emarquons que la vitesse de l ' a lgor i thme (S) croi t lorsque S diminue. L a vitesse de (S) est plus rapide que celle de (E) en d6but de convergence et cela & peu pr6s jusqu '& ce que la valeur (R/S)H,, soit atteinte ; pa r exemple, en phase (A) p o u r : S = - - 25 dB qui est une va leur m oye nne de S, (S) est plus rapide que (E), p o u r R / S allant de q- 22 dB & environ 0 dB. Pa r la m 6 t h o d e ~.L (2) = ~/'E J S , la vitesse de (S) devient sup6rieure & celle de (E) lorsque R devient inf6rieur & S e t cela rant que R / S n 'a t te in t pas sa valeur limite ob t enue d ' apr6s (31) et li6e Fs ~2) = 2 -8 ~/S. D a n s le cas pr6sent, cette limite est de - - 23 dB i n d 6 p e n d a m m e n t de S. Lorsque cette l imite est atteinte, la vitesse est nulle puisque la convergence s 'ar r6te ; a lors p o u r poursuivre la convergence, il faudra i t d iminuer F s -

L '6 tude de la figure 10, en phase permanente ,

pe rmet de tirer des conGlusions similaires & celles de la phase d 'apprent i ssage . P o u r la m6 thod e ~Zs ~1) ---- tZE et pour la valeur So ---- 10-1 de nos simulat ions, la zone favorable & (S) est compr ise entre R / S = -F 5 dB et R / S ---- - - 5 dB, zone qui corres- p o n d /t une annu la t ion d ' f e h o m o y e n n e ; la valeur - - 5 dB est ici le seuil (R/S)l im c o r r e s p o n d a n t pa r (31) & I~s = 2 -8 .

Lo r sque S diminue, cette zone favorable & la vitesse de (S) se d6place vers la gauche (d6but de convergence) en s '61argissant. P o u r S - - 25 dB elle est compr ise entre -F 23 dB et -}- 0,5 dB , elle va de + 38 dB & + 12 dB p o u r S = - - 40 dB.

L a vitesse de (S) est done sup6rieure & celle de (E), dans des zones int6ressantes, c o r r e s p o n d a n t au d6but de convergence.

Les figures 9 et 10 16gitiment le choix du pa ram6t re Fs 6gal & tZE au d6but de la convergence et la p roc6dure de gain var iable adopt6e ensuite p o u r l ' a lgo r i thme (S) de faqon "~ at te indre en fin de convergence une valeur ~ts p roche de celle donn6e pa r la fo rmule exacte (84). Cette proc6dure consis te en fait & d iminuer iZs p o u r rester au vois inage de Ia zone favorab le off (S) est plus rapide que (E). En effet, par exemple sur la figure 9 p o u r S = - - 40 dB, l o r s q u ' o n d6tecte le changemen t de zone off (S) devient mo ins rapide

21/25 ANN. TI~LECOMMUN.) 38, n ~ 7-8, 1983

326 M. B O N N E T . -- A L G O R I T H M E P O U R A N N U L E U R D ' E C H O

1513

1OO

5 0

q en dB pour 1000 iterations (a)

- 4 0 - 2 0 - 10

(c)

I, \ \ , ,

0 10 15 - R / S en d8

FIG. 16. - - Vitesses de convergence, en dB pour 1 000 it6rations, des algorithmes (E) et (S) en phase (P) pour diff6rentes valeurs de Se t pour 2 strat6gies en Yrs.

- - ( S ) , ~ t s = t Z E , ( a ) S = - - 4 0 dB, (b) S = - - 25 dB, (c) S = - - 1 0 d B

. . . . ( s ) , ~ s = ~ E ~ / S - - - ' - - (E) avec ~E = 2-s

Convergence speed of ( E) and ( S) , in dB/1 000 iterations, during the permanent phase, for different values orS and for two strategies over Vts .

que (E) (ici au voisinage de R / S = + 15 dB), en diminuant ~s on passe dans une zone favorable ~t (S) co r r e spondan t / t la courbe suivante de S : - - 25 dB. Cette proc6dure de pas d6croissant ainsi fix6e tout en permet tant la poursuite de la convergence, assure (S) une vitesse sup6rieure h celle de l ' a lgor i thme usuel (E) oh le param6tre ~z E est gard6 fixe. C 'es t pourquoi , nous avons utilis6 dans nos simulations la proc6dure qui consiste ~ diviser le param6tre ~t s par 2 r6guli6re- ment et cela au tan t de fois qu' i l le faut pour atteindre en fin de convergence une valeur adapt6e h ~/S.

Remarque.

Pour ne pas favoriser (S) dans la compara i son des deux algorithmes, nous avons diminu6 dans nos simulations ~E r6guli6rement, exactement comme i~s. I1 est tout /t fait remarquable que malgr6 cela, la vitesse observ6e pour (S) reste tout h fait du m~me ordre que celle de (E).

Vff. C O N C L U S I O N

Deux algori thmes adaptatifs pour annuleur d '6cho ont 6t6 compar6s en tenant compte de la complexit6 :

l 'a lgori thme du gradient et celui du signe de l 'e r reur avec ou sans adjonct ion de bruit fore&

La consid6ration d ' u n bruit en ligne, qui correspond ~t la r~alit6, a permis de montrer l ' impor tance du bruit dans l ' a lgor i thme (S) en compara ison avec l 'a lgori thme (E) et a rendu possible et facile l '6tude quantitative de l ' influence d ' u n bruit fore6 sur la convergence de l ' a lgor i thme (S). En particulier, notre 6tude a montr6 que certains r6sultats ant6rieurs ne sont pas valables sans tenir compte de la pr6sence d 'un bruit.

Not re d6marche a 6t6 de calculer pour toute valeur B du bruit, le r6sidu d '6cho limite, la longueur des mots binaires de l ' annuleur et enfin la complexit6 globale des calculs tout en c o m p a r a n t / t chaque &ape les r6sultats des deux algorithmes (E) et (S).

En appelant d6but (resp. fin) de convergence le cas oh le param~tre V- est assez grand (resp. petit), l '6tude montre que pou r l ' a lgor i thme (E), la d6croissance du r6sidu d '6cho est fonct ion lin6aire du param~tre d ' incr6mentat ion tz tout au long de la convergence. Pour l ' a lgor i thme (S), nous avons d6montr6 qu ' en d~but de convergence la d6croissance du r6sidu est en ix 2, ce qui est un r6sultat remarquable. Mais cette d6croissance s ' a r r&e (ph6nom~ne de seuil) lorsque le r6sidu devient faible devant le signal. Nous met tons

ANN. TI~L]~COMMUN., 38, n ~ 7-8, 1983 22/25


alors en 6vidence par quel mdcanisme le bruit est favorable h l 'algorithme (S), et nous ddmontrons que la ddcroissance du rdsidu d'dcho devient fonction lindaire du param6tre ~t, exactement comme dans l 'algorithme classique (E). C'est ainsi que le bruit dvite Parr& de la convergence ; son niveau optimal est calculable thdoriquement en fonction du signal. Ce niveau est du m~me ordre mais plus faible que celui du signal.

En ce qui concerne la repr6sentation binaire des roots de l 'annuleur, nous avons chiffr6, en fonction du niveau de bruit, l 'al longement dfi ~t l 'algorithme (S) en comparaison avec l 'algorithme (E). Cet allon- gement peut &re considdrable (doublement ou plus) mais se r6duit b. un seul bit avec l ' introduction d 'un bruit forcd de niveau dgal /~ celui du signal.

Malgr6 l 'al longement des mots, l 'algorithme du signe reste un algorithme non complexe de par sa structure m~me.

Sa complexitd globale en opdrations dldmentaires bit h bit est inf6rieure ~ celle de (E). Elle est rdduite de 30 % environ dans le cas du bruit forcd. Le seul inconvdnient de (S) reste sa faible vitesse de convergence que l 'on pallie en utilisant deux techniques simples : une phase d'apprentissage (sans bruit forcd) et un pas d ' incr6mentation variable (ddcroissant) au cours du temps.

Cette &ude est done une analyse quantitative prd- cise de l 'avantage qu'i l y a /~ utiliser l 'algorithme du signe avec un bruit forcd, par rapport h l 'algorithme classique de gradient.

ANNEXE A

I n t e r c o r r ~ l a t i o n entre l ' e r r e u r e t l e r~s idu d ' 4 c h o

Dans cette annexe, nous 6valuons la quantit6 :

(A-l) P : E ( ~ erk sgn(ek)),

qui est l ' intercorrdlation entre - - erk et le signe de ek �9

La ddmonstration suivante est faite dans le cas r6el, la g6ndralisation au cas complexe est immddiate.

Nous reprenons les notations utilisdes dans [17] (voir aussi [I8] ~t [20]). Grfice A l'int6grale de Mellin- Fourier, sgn(ek) s'dcrit sous la reprdsentation uni- verselle :

1 i (el"'k v~ + (i u) + (A-2) sgn(ek) = ~ .~c

e -lue" "t}_(-- iu) du,

oh v~+ et ~]_ sont les transformdes de Laplace des deux parties compldmentaires sgn+(ek) et sgn_(e,) de sgn (ek) :

(A-3) sgn(e~) = sgn+(e~) + sgn_(e~)

et o~ C est le contour d ' intdgration constitud par la

23/25

droite parall61e ~t l 'axe r6el, situde en dessous de ce dernier h une distance suffisante pour assurer la convergence de l'int6grale, par exemple h une distance sup6rieure ~t 1.

I1 vient alors, d'apr6s (12) qui donne l 'expression d e e k :

1 (A-4) r = ~ E

avec :

(A-5)

- - erkf (e I"(~+"~+ak) ~+( iu) + dc

e -l"t~'k+"~+a~) aq_(-- i u ) ) du]

~ + ( i u ) = e - l"~ d x - - , o i u

1 ~ _ ( - - i u ) = i u "

Puisque les variables erk, nk et dk sont supposdes inddpendantes (A-4) s'dcrit :

1 [ I (d?~rk(u) ?,,~(u)%~(u)v}+ (i u) + (A-6) r = ~ , _ . c

3 1

+e~,(-- u) ~ . . ( - - u) ~ ( - - u) ~_ (-- i u) du| , J

o6 : l +er~(U) = E( - - erk elSe'O,

(A-7) ?,~(u) = E(et~"0,

9d~(U) = E(el"a0.

Connaissant les lois des variables erk, nk et dk, nous pouvons calculer les valeurs de (A-7). Adoptons l 'hypoth6se que le r6sidu d 'dcho est gaussien. Ainsi :

Ioo e-erZl2R (A-8) d/~,(u) = - ~ - - er e l~<~~ ~ / ~ d(er),

soit :

(A-9) +er(U) : - - iu R e -"R~I2.

I1 est dvident que :

(A-IO) +er(-- U) : -- +er(U). Le bruit &ant supposd gaussien comme de coutume,

(A-11) 9,(u) = e -u~al2,

oh R et B sont respectivement les variances de erk et nk �9 Enfin, pour la variable diser6te dk, nous avons :

e i"'/~ + e -~4~

(A-12) %(u) = 2

L' intercorrdlat ion U vaut done, ~t cause des sym6- tries :

1 [ 2 1 q b e r ( u ) ~ , ( u ) % ( u ) ~ + ( i u ) d u ] , (A-13) U - - 2 = c

ou encore :

(A-14)

1 S R e -u2RI2 e -u2a12 (e l"4F + e -1"4~-) du.

ANN. T~L~COMMUN., 38, n ~ 7-8, 1983


Posons :

(A-15) O+ = !c et"4g- e-ual2 (R q- B) du,

qS_ = !c e-~"'/~-e-"~12 (R + B) du.

I1 s 'agi t de fonct ions h o l o m o r p h e s 5. int6grer sur C ; nous avons done :

f + (A-16) qb+ = e l"'/g e -u212 (R q- B) du, - - o o

soit

(A-17)

et

(A-18)

N o u s

(A-19)

/ 2re ~+ = R + B

- - e - Sl 2 ( R q- B) ,

obtenons f inalement :

e -sl2 (R + B).

A N N E X E B

Vitesse de convergence des algorithmes 6tudi6s

1. Pour (E-A).

C o m p t e tenu des relat ions (48) et (49), la formule (18) permet d '6crire :

(B-I) R~+I = R ~ , - - Z ~ A R k + ~z 2 NA2(Rk + B).

On peut n6gliger le terme en ~2 si :

~z N A Rk (B-2) 2 ~ Rk + ~ "

II vient alors :

(B-3) V = - - log(1 - - 2 ~A) .

Si (B2) n 'es t pas satisfaite, il vient :

(B-4) V--- - - - log ( 1 - - 2 b ~ A 1 - - ~ N A Rk J / "

2. Pour (S-A).

La formule (30) permet d '6cr i re :

O n peut n6gliger le te rme en ix 2 sous la condi t ion :

(B-6) ~ N A .~ 4"2 Rk 2

I1 vient alors :

( ) (B-7) V = - - l o g 1 - - 2 E x A s o r~(Rk + B ) "

Si (B-6) n ' e s t pas satisfaite, il vient :

V = - - l o g 1 ~/r~(Rk + B ) ( 1 - - ~ k ) , (B-8)

o/J :

~/~:(R~ + B) (B-9) ~k - - 2 ~ / 2 Rk ~z So N A .

3. Pour (E-P).

D ' ap r6s (22), nous avons :

(B-10) R k + I = R k - - 2 ~ t A R k + t x 2 N A 2 ( R k + B + S ) .

On peut n6gliger le te rme en ~x 2 si :

(B-11) ~ N A ~ R k 2 R k + B + S "

La vitesse de convergence est alors donn6e par la formule (B-3). Si (B-11) n 'es t pas satisfaite, il vient :

(B-12)

V = - - I o g 1 - - 2 t x A 1 - - ~ N A Rk "

4. Pour (S-P).

En utilisant (33), nous avons :

V = - - log s 2 ~/2 Ex A So e -sl2(Rk+8) (B-13) + B) x

1 - - 2 ~/2 Rk e -sl2(Rk+B)

Ici encore on peut n6gliger le terme en ~z 2 sous la cond i t ion

N A ~/2 Rk (B-14) 2 "~ e-Sl2tRk+8)

So ~/~ (Rk q- B)

La vitesse de convergence a alors p o u r expression :

( 2~ / , ExA So e_sl2(Rk+B)) (B-15) V = - - l o g 1 --~/Tz(R~ q-- B)

Manuscrit re fu le 18 juin 1982, acceptd le 16 mai 1982.

BIBLIOGRAPHIE

[1] MUELLER (K. H.). A new digital echo canceller for two- wire full-duplex data transmission. IEEE Trans. COM, USA (sep. 1976), 24, n ~ 9, pp. 956-962.

[2] WEINSTEIN (S. B.). A passband data-driven echo canceler for full-duplex transmission on two-wire circuits, IEEE Trans. COM, USA (juil. 1977), 25, n ~ 7, pp. 654-666.

[3] KOLL (V. G.), WEINSTEIN (S. B.). Simulations two-way

data transmission over a two-wire circuit, 1EEE Trans. COM, USA (f6v. 1973), 21, pp. 143-147.

[4] MACCHI (C.). Annuleur d'6cho num6rique adaptatif. GRETSI Nice (1977), pp. 841-846.

[5] DurrWEmER (D. L.). Adaptive filter performance with non-linearities in the correlation multiplier, 1EEE Trans. ASSP, USA (1982), 30, n ~ 4, pp. 578-586.

ANN. T~L~COMMUN., 38, n ~ 7-8, 1983 24/25

M. BONNET. -- ALGORITHME POUR ANNULEUR D'I~CHO 329

[6] HOLTE (N.), STUEFLOTTEN (S.). A new digital echo canceller for two-wire subscriber lines, IEEE Trans. COM, USA (nov. 1981), 29, n ~ 11, pp. 1573-1581.

[7] LEVY (M. Y.). Techniques d'annulation d'6chos : transmission t616phonique et transmission num6rique. Ann. Telecommunic., Fr. (1981), 36, n ~ 11-12, pp. 651-661.

[8] VERHOECKX (N. A. M.), ELZEN Van den (H. C.), SNI.IDERS (F. A. M.), GERWEN Van den (P. J.), Digital echo cancellation for baseband data transmission, IEEE Trans. ASSP, USA (d6c. 1979), 27, pp. 768-781.

[9] JORGENSEN (E.), KJoLAAS (K. O.). Echo cancelling system based on the sign correlation algorithm, Nation. Tele- communic. Conf. 1981-C751-C756.

[10] GUIDOUX (L.). Annuleur d'6cho pour modem duplex 2 ills 2400 bits/s, Ann. Tdldcommunic., Fr. (nov. 1981), 36, n ~ 11-12, pp. 662-668.

[11] CLAASEN (T. A. C .M. ) , MECKLENBRAOKER (W. F. G.). Comparison of the convergence of two algorithms for adaptive F IR digital filters, IEEE Trans. ASSP, USA (juin 1981), 29, n ~ 3, pp. 670-678.

[12] MAccm (C.), JOUANNAUD (J. P.), MACCHI (O.). R6cep- teurs adaptatifs pour transmission de donn6es /t grande vitesse, Ann. Tdldcommunic., Ft. (sept-oct. 1975), 30, n ~ 9-10, pp. 311-330.

[13] MACCHZ (O.). R6solution adaptative de l '6quation de Wiener-Hopf. Cas d 'un canal de donn6es affect6 de gigue. Ann. Institut Henri Poincard, section B, (1978), XIV, n ~ 3, pp. 355-377.

[14] MACCHI (O.). Filtrage adaptatif en communications, Ann. Tdldcommunic., Ft. (nov. 1981), 36, pp. 615-625.

[15] GERSHO (A.). Adaptive filtering with binary reinforcement, Internat Symp. of Information Theory, New-York, (janv. 1969), IEEE Trans. IT, USA. Special issue about linear adaptive filtering, h paraitre mars 1984.

[16] PRABHAKARA RAO (C. B. K.). Analysis of the steady-state

performance in adaptive echo-cancelers with correlated data and correlated received signal, IEEE Trans. ASSP, USA, (d6c. 1981), 29, n ~ 6, pp. 1222-1225.

[17] BONNET (G.). Transformation des signaux al6atoires h travers les syst6mes non lin6aires sans m6moire, Ann. Tdldcommunic., Fr. (1964), 19, pp. 203-220.

[18] MACLOED (C. J.), CIAPALA (E.), JELONEK (Z. J.). Quanti- sation in non recursive equalizers for data transmission, Proceedings lnstn electn. Engrs., GB (oct. 1975), 122, n* 10, pp. 1105-1109.

[19] BLANC-LAPIERRE (A.), PICINBONO (B.). Fonctions al6a- toires, Coll. tech. scient. Tdldcom., Masson, Fr. (1981), 440p.

[20] MAZO (J. E.). On the independence theory of equalizer convergence, BSTJ, USA (1979), 58, n* 5, pp. 963-993.

[21] SARZ (H.), Algorithmes d'6galisatiorL adaptative d 'un canal dispersif, Th6se d'ing6nieur ENST, Fr. (oct. 1980).

[22] GITLIN (R. D.), WEINSTEIN (S. B.). On the required tap- weight precision for digitally implemented, adaptive, mean-squared equalizers, BSTJ, USA, (f6v. 1979), 58, n ~ 2, pp. 301-321.

[23] DESBLACHE (A.). Filtrage h complexit6 r6duite, Ann. Tdldcom., Fr. (nov. 1981), 36, n ~ 11-12, pp. 645-650.

[24] ARIF BIN NUN (M.). Novel implementation method of modulo 2 N multiplication for digital signal processing, First European Signal Processing Conference Lausanne. (sep. 1980) [6dit6 par M. Kunt et F. de Coulon] North- Holland, Amsterdam, pp. 251-256.

[25] DAWOUD (D. S.). Digital filter realization using counters, First European Signal Processing Conference Lausanne (sep. 1980) [6dit6 par M. Kunt et F. de Coulon] North- Holland, Amsterdam, pp. 257-262.

[26] RUSSEL (R. M.). The CRAY-1 computer system, A C M comptg survey, USA (jan. 1981), 21, n ~ 1, pp. 63-72.

25/25 ANN. T~L~COMMUN., 38, n ~ 7-8, 1983

Documents

Choix d’un algorithme en précision finie, pour annuleur d’écho