Stereophonic Acoustic Echo Cancellation: Theory and Implementation Peter Eneroth Lund 2001 Departmentof Electroscience LundUniversity Box 118,S-22100 LUND SWEDEN No.22 ISSN 1402-8662 ISBN 91-7874-110-6 (cid:13)c Peter Eneroth2001 Printed in Sweden byKFS AB, Lund. January2001 Abstract The thesis treats theory and implementation aspects for stereophonic acoustic echo cancellation. In Paper I a complete implementation of a stereophonic acoustic echo canceler basedonthetwo-channelfastrecursiveleast-squaresalgorithmispresented. Ananal- ysisofthesystemcalculationcomplexityisalsogiven,inadditiontosimulationresults on recordedreal-lifedata. Paper II presents a comparison between adaptive filters for usage in stereophonic acoustic echo cancellation. The comparisonincludes, in addition to the standard nor- malized least mean square algorithm, the two-channel fast recursive least-squares al- gorithm and a two-channel frequency-domain adaptive algorithm. In the paper, the convergence rate, the calculation complexity, the signal transmission delay, and the memoryusagefor theevaluatedsystemsare shown. Adaptivefiltersappliedinsubbandstructuresmayneedtomodelafewnon-causal taps even if the fullband impulse response is causal. This phenomenon is analyzed in Paper III. Formulas to calculate the number of non-causal taps needed are also presentedin thepaper. Thefundamentalproblemin stereophonicacousticecho cancellationis the signal correlation between the two channels. In Paper IV it is shown how a perceptual au- dio coder may decrease this correlation and thereby increase the performance of the stereophonicacousticechocanceler. Paper V investigatesthe possibilities of using joint subband filterbanks or time to frequency-domaintransformsforecho cancellationandperceptualaudiocoding. The usage of joint filterbanks/transforms not only decreases the computational complex- ity of the system, it also reduces the total signal transmission delay of the system if properlydesigned. iii Contents Abstract iii Contents v Acknowledgment vii General Introduction 1 1 CommunicationSystem . . . . . . . . . . . . . . . . . . . . . . . 1 2 Echo Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 AdaptiveFiltering . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Audio Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5 Outlineof theThesis . . . . . . . . . . . . . . . . . . . . . . . . . 18 I A Real-time Implementation of a Stereophonic Acoustic Echo Canceler 33 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2 Problemsand Solutionsof StereophonicAcousticEchoCancellation 36 3 ProposedStructurefor theStereophonicAcousticEchoCanceler . 39 4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 A Analysis Filterbank . . . . . . . . . . . . . . . . . . . . . . . . . 52 B Synthesis Filterbank . . . . . . . . . . . . . . . . . . . . . . . . . 54 C PrototypeFilter forNon-criticalDownsampling . . . . . . . . . . 56 D PrototypeFilter Construction . . . . . . . . . . . . . . . . . . . . 58 E Real-time Implementation . . . . . . . . . . . . . . . . . . . . . . 63 II Comparison of Different Adaptive Algorithms for Stereo- phonic Acoustic Echo Cancellation 75 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2 AdaptiveAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . 78 3 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 v vi Contents III Analysisof Subband Impulse Responses in Subband Echo Cancelers 91 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 2 System Description . . . . . . . . . . . . . . . . . . . . . . . . . 95 3 Analysis of theSubbandImpulseResponse . . . . . . . . . . . . . 96 4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 A CorrelationCalculations . . . . . . . . . . . . . . . . . . . . . . . 112 IV Influence of Audio Coding on Stereophonic Acoustic Echo Cancellation 121 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 2 Problem Formulation. . . . . . . . . . . . . . . . . . . . . . . . . 123 3 Audio Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4 MeasurementStudies . . . . . . . . . . . . . . . . . . . . . . . . 127 5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 V Joint Filterbanks for Echo Cancellation and Audio Cod- ing 135 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 2 Problem Formulation. . . . . . . . . . . . . . . . . . . . . . . . . 139 3 Modified AudioCoder FilterbankStructuresfor EchoCancelers . . 144 4 FDAF and MDCT Based AudioCoders . . . . . . . . . . . . . . . 151 5 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Acknowledgment Without all the help and encouragement I have received during the last five years, the contents of this thesis would be significantly different, and I am truly grateful to everyonewho has made this work possible. Not only have I been given a lot of help, I have also been given the opportunity to become friends with so many generous, interestingand intelligentpeople. I am without competition most grateful towards my supervisor Tomas Ga¨nsler. I have always felt totally confident with his knowledge and his support to me. He has guidedmetowardsveryinterestingtechnicalproblems,andintimeswhenIhavebeen toocommittedin solvingtheseproblems,hehasforcedmetowrite. Afterleavingthe department,Tomascontinuedbeing fullycommittedas my supervisor. I would also like to thank Go¨ran Salomonsson, now retired from his position at thedepartment. Itwas Go¨ran whoaccepted meas a graduatestudentand who guided mein myearly work. Inspirationis a fundamentalcorner-stonebehindresearch, and much of my inspi- rationhascomefromBell Laboratories. JacobBenesty taughtmeplentyaboutmulti- channel adaptive filtering, and has generously shared everything from knowledge to deep friendship. During the fall of 1998, Steven Gay and I worked on the project presentedin Paper I ofthisthesis. We spentmanyeveningsat thelabs,togetherfight- ing againsttime and software bugs. Also Steve generouslyshared his knowledgeand friendship. Dennis Morganwas always happy to discuss everythingfrom mathemati- cal and technicaldetails to internationalpolitics. Being a perfectionist,he also taught me plenty about technical writing. Finally, I would like to mention the head of the group,GaryElko,whoenthusiasticallypushedtheworkintherightdirection,andev- erybodywhohelpedcreatingsuch a friendlyatmosphereat Bell Laboratories,Lucent Technologies. WhenTomasGa¨nslerandIstartedourworkonstereophonicacousticechocancel- lation,itwasajointprojecttogetherwithTeliaResearchABinHaninge,nowsituated inFarsta. Ourcooperationwasextremelyfruitful,andIwillalwaysbegratefultoOve Till, NiklasJohanssonand BirgitteWikman. Most of the time was of course spent at the Department of Applied Electronics, now the Department of Electroscience. Academic and educational inspiration was given by Leif So¨rnmo and Per Ola Bo¨rjesson, and administrative issues were easily vii viii Acknowledgment resolved with help from Birgitta Holmgren. Clas Angvall has been supportive in di- verse matters and Erik Johnsson has provided me a bullet proof computer system. I’m also grateful to all colleagues at the department, making almost every day at the departmentjoyful. Finally, I would like to thank my wife, Elisabeth Anderberg, my family and my friendsfor encouragement,andfor givingmequalityof life. General Introduction Echo: “the repetitionof a soundcausedbyreflection ofsoundwaves.” Merriam-Webster’sDictionary Historically,echowasprobablyaninterestingandamusingphenomenonthatcould be experienced in rare places, e.g. between mountain walls in the Alps. However, to most people today, echo is also something annoying which can occur, e.g., during a longdistancetelephonecall. Thedefinitionof echois still valid though,it is allabout (delayed)reflectionsof soundwaves. Inthisthesis,methodsforremovingechoincommunicationsystemsareproposed. Whilemostofthetheoriespresentedherecanbeappliedtoreduceechoesintelephone calls, the target application is hands-free communications systems, with dual audio channels. Examples include stereophonic video conferencing systems and desktop conferencingoncomputerswithdualloud-speakers. Thethesiswillbothconsiderthe theoreticalproblemsand implementationaspects. Thispartincludesgeneralbackgroundinformationneededinordertogettheother parts of the thesis in a proper context. Here the underlying application is discussed, together with notes about the historical background. The theoretical problem in echo cancellationisshownandbasicechocancellationmethodsarediscussed. Finally,Sec- tion 5 summarizesthefivepartsof thethesis. 1 Communication System For the purposeof this thesis, a communicationsystem is a system that allows two or more persons, or perhaps one person and one machine, to interact with speech over anartificialchannel,forexampleatelephoneline. Thissystem mayalso deliverother components,suchaspictures,video,documents,oranyothertypeofmedia,butinthis thesis we will only discuss the audio component. The most commonly used system 1 2 GeneralIntroduction in this category is of course the standard telephone system, also called the public switchedtelephonenetwork(PSTN),butinrecentyearsmanyadditionalsystemshave emerged,e.g.,cellular telephones,videoconferencing,anddesktopconferencing. Natural speech signals are analogue signals, and they can be modeled as contin- uous functions, with infinitely high resolution. Such functions are very ill-suited for today’s digital communication and computer systems. Therefore, in the systems un- derconsideration,thespeechsignalsaresampledandquantized. Thisprocessinvolves measuringtheamplitudeofthesignalatgiventimeintervals(sampling)andpartition- ingthesignalamplitudespaninsub-intervals,andrepresentingeachsub-intervalwith a number (quantization). The digitized signal can advantageously be processed with a digital system, e.g., a computer, and be transmitted via a digital communication system,such as a modernPSTN. The quality of the digital signal can be made arbitrarily good, by decreasing the time between successivesamples and by increasing the numberof quantizationinter- vals. Since the bandwidthof the original speech signal is limited, as is the sub-group of audio signals that are audible to humans, it is not controversial to state that high quality sampled audio signals are extremely redundant. That is, it is possible to re- duce the amountof data used to representthe signal without, or with very small, loss of quality. The sampling and quantization of the analog signal can be viewed as one formof datacompression,and later in thethesiswe willsee othercompressionmeth- ods,wheremoremathematicalmethodsareused to reducethe redundancyfurther. Almost everyone who has made an intercontinental telephone call, or a call to a cellular telephone in a poor network, has experienced echoes. This thesis presents methods for how to reduce echoes in communication systems, with the emphasis on echoes due to an acoustic coupling between the loud-speaker and the microphone. Threepapersinthethesisfocusonsystemswithtwoaudiochannels,stereophonicau- dio,describingwhythissituationismorecomplicatedandproposespossiblesolutions for stereophonicacousticecho cancellation. 2 Echo Cancellation Echoes in the PSTN have been a problem since the early days of telephone technol- ogy,when the first transcontinentaltelephonenetworkswere built. The long distance betweenthetwopartiesintroducesatimedelaytotheechosignal. Thisdelayincom- bination with low echo attenuation reducesthe perceptualquality of the system. For- tunately, the development of high speed transmission systems in the 1920’s reduced theproblem[1]. In the 1960’s, satellite communication was introduced, and again the round-trip delay became long enough to cause noticeable echo problems. A device called echo