KATHOLIEKE UNIVERSITEIT LEUVEN FACULTEITTOEGEPASTEWETENSCHAPPEN DEPARTEMENTELEKTROTECHNIEK KasteelparkArenberg10,3001Leuven(Heverlee) A EQUALIZATION AND ECHO CANCELLATION IN DMT–BASED SYSTEMS Jury: Proefschriftvoorgedragentot Prof.dr.ir.P.Verbaeten,voorzitter hetbehalenvanhetdoctoraat Prof.dr.ir.M.Moonen,promotor indetoegepastewetenschappen Prof.dr.ir.B.Preneel door Prof.dr.ir.M.Steyaert Prof.dr.ir.L.Vandendorpe(U.C.L.) Geert YSEBAERT Prof.dr.ir.B.DeMoor Prof.dr.ir.G.Leus(T.U.Delft) Prof.dr.ir.H.Vanhamme U.D.C.621.376 April2004 c Katholieke Universiteit Leuven – Faculteit Toegepaste Wetenschappen (cid:13) Arenbergkasteel, B-3001 Heverlee (Belgium) Alle rechtenvoorbehouden. Niets uit deze uitgave mag vermenigvuldigden/of openbaargemaaktwordendoormiddelvandruk,fotocopie,microfilm,elektro- nisch of op welke andere wijze ook zonder voorafgaande schriftelijke toestem- ming van de uitgever. All rights reserved. No partof the publication may be reproducedin any form byprint,photoprint,microfilmoranyothermeanswithoutwrittenpermission from the publisher. D/2004/7515/13 ISBN 90-5682-475-9 Voorwoord Bij de aanvang van dit doctoraatswerk had ik slechts een vaag vermoeden van watdoctorerenjuist inhield. Gaandewegwerdhetbegrip‘doctoraat’concreter engroeidehetvertrouwen,watuiteindelijk geleidheeft tothetproefschriftdat nuvooruligt. Bijhetbe¨eindigenvanditwerkishettijdomeenaantalmensen te bedanken. AlseersteinderijzouikProf. MarcMoonenwillenbedanken,depromotorvan dit doctoraat. Dankzij Marc kende mijn onderzoekswerk een vliegende start. Door zijn uitstekende en uitermate persoonlijke begeleiding slaagde ik erin om dit doctoraat tot een goed einde te brengen, mijn oprechte dank hiervoor. Verdergaatmijndankuitnaaralleledenvandejury. Ikbesefdathetheelwat inspanning vergtomeen dergelijk werk in eenvrij kortetijdspanne na te lezen en te beoordelen. In het bijzonder dank ik de leden van het leescomit´e: Prof. LucVandendorpe(U.C.L.)forhisflexibilitywhenIwasfixingmyPhDdefense and for his constructive remarks,Prof. BartPreneel en Prof. Michiel Steyaert voor hun constructieve suggesties m.b.t. het proefschrift. Prof. Bart De Moor en Prof. Geert Leus (T.U. Delft) wil ik speciaal bedanken voor hun interesse in mijn onderzoek, voor de verhelderende discussies en voor het zetelen in de jury. Prof. Hugo Van hamme dank ik voor zijn onmiddellijke bereidheid om in laatste instantie mijn jury te vervolledigen. Prof. Pierre Verbaeten ben ik dankbaar voor het opnemen van het voorzitterschapvan de jury. I wouldlike to express my gratitude to Prof. RichardJohnson,Jr. for inviting us to his research group at the Cornell University, USA. It was an enriching experience to share our research ideas with him and with his assistants. I will keep in mind the post-research activities like the BBQ, ‘sherade’, pasta- evening,... that he organized during our relatively short stay. Special thanks toRick,AndyandJohnfortheirhospitality. Inaddition,Iwouldliketothank Prof. Brian Evans (University of Texas at Austin, USA) and his assistants MingandMilosforsharingtheirexpertiseinthefieldofDSL communications. I would like to show my appreciation to Fabio Pisoni and his colleagues from i ii Voorwoord STMicroelectronics. Iwillneverforgetourfruitfulcollaborationandespecially the typical Italian ‘Colomba’ cake that Fabio gave us for Easter. De eerste jaren van mijn doctoraat werden gekenmerkt door een verrijkende en stimulerende samenwerking met Alcatel. Hierbij wil ik in het bijzonder de volgende personen bedanken: Katleen Van Acker, Piet Vandaele, Thierry Pollet, Luc De Clercq, Jan Verlinden, Danny Van Bruyssel, Peter Reusens en Mark Van Bladel. Het IWT wens ik te danken voor de financiering van dit onderzoek. Bij deze gelegenheid wil ik ook mijn bureaugenoten Gert, Koen en Toon be- dankenvoordeaangenamewerksfeer. Talrijkediscussiesensocialeactiviteiten zorgden voor een leuke werkplek. Ook de overige leden van SISTA, met in het bijzonder de leden van de DSP-club Geert, Simon, Ann, Narendra, Hilde, Imad,Raphael,Olivier,Geert,KoenenThomaswilikdankenvoorhundirecte en indirecte hulp bij het totstandkomen van dit doctoraat. Totslotwilikmijnouders,Inge,Riet,KimendefamilieSchoevaertsbedanken voorhunrotsvastvertrouwen. Eenheelspeciaalwoordjevandankgaatuitnaar Ilse voor haar goede zorgen en haar onvoorwaardelijkesteun. Geert Ysebaert, April 2004. Abstract Digital subscriber line (DSL) is a technology to provide broadband communi- cations over the existing twisted pair telephone network. The signals received byaDSLmodemaretypicallycorruptedbychannelinducednoise,background noise, radio frequeny interference (RFI) and undesired echo. In this thesis we focus on the design of digital signal processing algorithms to improve the bit rate and/or the loop reach of current and future DSL systems. Furthermore, in the proposed algorithms we aim at keeping the hardware cost as low as possible. The transmission format of many DSL systems is based on discrete multitone modulation (DMT). To combat channel induced noise, DMT-based receivers perform an equalization step by means of a time domain equalizer (TEQ) and a one-tap frequency domain equalizer (FEQ) per used tone. Despite the vari- ety of TEQ design methods presented in the literature, we show that almost all designs can be formulated as the maximization of a product of general- ized Rayleigh quotients. This unified framework allows us to highlight the subtle differences between the different design methods. Special attention is paid to minimum mean square error (MMSE) TEQ design with three distinct unit-energy constraints. We illustrate that the resulting TEQs haveequalper- formance and can be obtained from a single iterative initialization method. The modem structure can also be extended with receiver windowing to reduce the sensitivity to narrowband RFI. We show how to design a TEQ in com- bination with a time domain window in order to maximize the achievable bit rate. Simulations indicate that equalizer taps can be exchanged for additional windowingcoefficients,resultinginsubstantialcomplexitysavings. Thedesign procedure also allows to design an equalizer and a window for small groups of tones or for each tone separately (per tone equalization). Besidesequalizationandreceiverwindowing,wealsoinvestigatestructuresthat effectively cancel undesired echo. In a first step, we enhance existing mixed time/frequency domain echo cancelers by adding double talk cancellation and byminimizingthecomplexity,independentofthemisalignmentbetweentrans- iii iv Abstract mitted echo symbols and received far end symbols. In a second step, an alter- native structure is proposed, where less transmit power is required to update the echo canceler coefficients. Finally,weproposeanefficientmethodforfastinitializationofareceiverstruc- ture based on an equalizer and an echo canceler for each tone separately (per tone equalization and echo cancellation). We show that the computational complexity and memory requirements can be substantially reduced compared to existing methods. Korte Inhoud Digitale lijnen naar de abonnee (digital subscriber lines of DSL) laten breed- bandcommunicatietoeoverhetbestaande,getwisteparentelefoonnetwerk. De signalen,ontvangendooreenDSL modem, wordentypischaangetastdoorruis t.g.v. het kanaal, achtergrondruis,radiofrequentie-interferentie (RFI) en onge- wenste echo. In dit proefschrift focuseren we ons op het ontwerp van digitale signaalverwerkingsalgoritmenomdebitsnelheidendereikwijdtevanbestaande entoekomstigeDSLsystementeverbeteren. Verderisonsdoelomdehardware kost van de voorgestelde algoritmes zo laag mogelijk te houden. Het zendschema van vele DSL-systemen is gebaseerd op discrete multitoon- modulatie (discrete multitone modulation of DMT). Om ruis t.g.v. het te- lefoonkanaal tegen te gaan, voeren DMT-ontvangers een egalisatie-stap uit d.m.v. een tijdsdomein egalisatiefilter (time domain equalizer of TEQ) en een 1-taps frequentiedomein egalisatiefilter (frequency domain equalizer of FEQ) per gebruikte toon. Ondanks de verscheidenheid aan TEQ-ontwerpmethodes die verschenen zijn in de literatuur, tonen we aan dat bijna alle ontwerpstra- tegie¨en geformuleerd kunnen worden als een maximisatie van een product van veralgemeende Rayleigh quoti¨enten. Dit veralgemeend kader laat ons toe om de subtiele verschillen tussen de verschillende ontwerpmethodes toe te lichten. Speciale aandacht wordt besteed aan het TEQ-ontwerp, waarbij de gemiddel- de kwadratische fout geminimiseerd (minimum mean square error of MMSE) wordt in de aanwezigheid van drie verschillende eenheidsenergiebeperkingen. We tonen aan dat de resulterende TEQs een gelijke performantie vertonen en verkregenkunnen worden via eenzelfde, iteratieve initialisatiemethode. Demodemstructuurkaneveneensuitgebreidwordenmeteenvensterfunctieom degevoeligheidvoorsmalbandigeRFItereduceren. WegevenaanhoeeenTEQ eneenvensterfunctie (in het tijdsdomein) gezamenlijkontworpenkunnenwor- denomdehaalbarebitsnelheidtemaximiseren. Simulatiestonenaandategali- satiefiltertaps uitgewisseld kunnen wordenvoor vensterfunctieco¨effici¨enten, re- sulterend in aanzienlijke complexiteitsbesparingen. De ontwerpprocedure laat ook toe om een egalisatiefilter en een vensterfunctie te ontwerpen voor kleine toongroepen of voor elke toon afzonderlijk (per-toon egalisatie). v vi Korte Inhoud Naast egalisatie en vensterfuncties bestuderen we ook structuren om echo te onderdrukken. In eeneerste stapverbeterenwe bestaande tijds- enfrequentie- domein echo-onderdrukkersdoor dubbelspraakonderdrukkingtoe te voegen en doordecomplexiteitervanteminimiseren,opeenwijzedieonafhankelijkisvan dealigneringtussendeverzondenecho-symbolenendeontvangensymbolendie afkomstigzijnvandeanderezijdevandetelefoonlijn. Ineentweedestapstellen we een alternatieveecho-onderdrukkingsstructuurvoorwaarminder vermogen moetwordenuitgezondenomdeco¨effici¨entenvande echo-onderdrukkeraante passen. Ten slotte stellen we een effici¨ente methode voor om een ontvanger die ge- baseerd is op egalisatie en echo-onderdrukking per toon te initialiseren (per- toon egalisatie en echo-onderdrukking). Er wordt aangetoond in de thesis dat de rekenkundige complexiteit en de geheugenvereisten aanzienlijk gereduceerd kunnen worden in vergelijking met reeds bestaande werkwijzen. Glossary Mathematical Notation IN the set of natural numbers ZZ the set of integer numbers Q the set of rational numbers IR the set of real numbers C the set of complex numbers IRM set of real M–dimensional vectors IRL×M set of real L M–dimensional matrices × CM set of complex M–dimensional vectors CL M set of complex L M–dimensional matrices × × a scalar a a (column) vector a A (column) vector A C with frequency domain ∈ samples, discrete Fourier transform of a A matrix A a[m] m–th element of vector a A[l,m] element on the l–th row and the m–th column of matrix A A[l :m,:] rows l up to m of matrix A A[:,l :m] columns l up to m of matrix A AT transpose of matrix A A complex conjugate of matrix A ∗ AH =(A )T Hermitian transpose of matrix A ∗ A 1 inverse of matrix A − A1/2 Cholesky factor of A A pseudo–inverse of matrix A † A determinant of matrix A | | tr A trace of matrix A { } diag a square diagonal matrix with vector a as diagonal { } e a real part of a C R { } ∈ m a imaginary part of a C I { } ∈ aˆ estimate of a vii viii Glossary a 2–norm of a 2 || || a a N–fold downsampled N ↓ a a N–fold upsampled N ↑ a largest integer smaller than or equal to a IR ⌊ ⌋ ∈ a absolute value of a | | a b a is much smaller than b ≪ a b a is much larger than b ≫ a b a is approximately equal to b ≈ a⋆b linear convolution of a and b A B component wise multiplication of A and B ⊙ statistical expectation operator E{·} σ standard deviation of a a J gradient of J with respect to a a ∇ Fixed Symbols J cost function L channel order (= length of the channel impulse response - 1) N (I)DFT size T number of (P)TEQ taps T number of echo canceler taps E b number of bits f frequency domain variable i tone or subcarrier index j √ 1 − k block time index or symbol index l discrete time index or sample index r bit rate in bits per second z z–domain variable b target impulse response (TIR) c effective channel c=h⋆w e canonical vector: all zero vector except for a one at p the p-th position g gradient of J, g= J ∇ h channel impulse response (CIR) v PTEQ equalizer taps based on difference terms w P(TEQ) equalizer taps w echo canceler taps in the time domain E nk additive noise samples at symbol period k uk transmitted echo time domain samples at symbol period k xk transmitted far–end time domain samples at symbol period k