10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 1 Development of Complex Curricula for Molecular Bionics and Infobionics Programs within a consortial* framework** Consortium leader PETER PAZMANY CATHOLIC UNIVERSITY Consortium members SEMMELWEIS UNIVERSITY, DIALOG CAMPUS PUBLISHER The Project has been realised with the support of the European Union and has been co-financed by the European Social Fund *** **Molekuláris bionika és Infobionika Szakok tananyagának komplex fejlesztése konzorciumi keretben ***A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg. PETER PAZMANY CATHOLIC UNIVERSITY SEMMELWEIS UNIVERSITY sote_logo.jpg dk_fejlec.gif INFOBLOKK 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 2 Peter Pazmany Catholic University Faculty of Information Technology Adaptive Signal Processing www.itk.ppke.hu (Adaptív Jelfeldolgozás) JánosLevendovszky, AndrásOláh, DávidTisza, GergelyTreplán Digitális-neurális-, éskiloprocesszorosarchitektúrákonalapulójelfeldolgozás Digital-and Neural Based Signal Processing & KiloprocessorArrays Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 3 Outline • Introduction to adaptive signal processing • Motivation and historical review • Applications • Wiener-filtering • The Levinson-Durbin algorithm • The Robinson-Monroe stochastic approximation • The LMS algorithm • Adaptive-predictive coding • Radio channel equalization www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 4 Introduction Digitalsignalprocessingisbecomingmoreandmoreimportantinvariouskindsoffields. Manytypesofsignals,whichwereprocessedformerlybyanalogtechniques,arenowusuallybeingprocessedusingVLSIprocessorssuchasdigitalsignalprocessors. Digitaltelevisionanddigitalmobilecommunicationsarebecomingverypopularowingtothedevelopmentofdigitaltechniques. www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 5 Historical overview (1) • Theory of linear approximation (Galilei-1632, Gauss-1795) • Approximation with minimum mean square error (Wiener-1930, Kolgomorov-1939) • Levinson-Durbin algorithm (1947) • Wiener filter (Norbert Wiener, 1949) • LMS algorithm (Hoff-1960, Widrow-1970) • Digital filter (1960 –1965, J. F. Kaiser 1965) • Kalman filter (Kalman-1960) • Minimax criteria (Zames-1981) www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 6 Historical overview (2) • Firstlineardigitalfilterforsolvingdifferenceequationsinfifties • Digital filter (1960 –1965, J. F. Kaiser 1965), at first, it was called “numerical filter” or “sampled-data filter”. • Tappeddelaylineforequalizationinthedigitalcommunicationtechnologiesintheseventies • FiltersandadaptivearchitecturesimplementedonDSPintheeighties • Arraysignalprocessinginthenineties www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 7 Practical applications of adaptive signal processing (1) • Communicationtechnology:equalization,adaptivemodulation,etc. • Informationandcomputertechnology:encoding,decoding,errorcorrection,datacompression,etc. • Multimediatechnology:stillandmovingimageprocessing,imagecompression,datatransmission,humaninterface,etc. • Mechanicalengineering:vibrationcontrol/analysis,noisecontrol/analysis,mechanicalsystemscontrol/analysis,etc. • Controlengineering:controlofmanykindsofdynamicalsystems www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 8 Practical applications of adaptive signal processing (2) • Systemsengineering:modelingandoptimizationofpracticalsystems • Imagetechnology:imageprocessing,patternrecognition,medicalimaging,remotesensing • Architecturalengineering:architecturalacoustics,vibrationcontrol(forearthquakes),noisecontrol,etc. • Civilengineering:underwaterestimation,floodprediction,fluidcontrol,environmental,dataprocessing,bridgeengineering,soilengineering,etc. www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Wiener filtering 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 9 Motivation Basedonobservedexamples(inputsanddesiredoutputs)learnthedesiredsignaltransformation www.itk.ppke.hu stochastic input signal prescribed, unknown transformation desired output error signal adaptive architecture Optimizing the free parameters of the adaptive architecture output signal - Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 10 Notations and definitions (1) • Input signal: xkweakly stationary process • Expected value:(zero mean process) • Correlation function: • Correlation matrix: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 11 Notations and definitions (2) • Output signal: dkweakly stationary process • Expected value: • Correlation function: • Cross correlation: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 12 Notations and definitions (3) •Adaptive linear architecture (FIR): • Output signal: T T T Adaptation: changing w Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 13 Notations and definitions (4) •Error signal: • Error function: • Empirical error: • Offline-algorithm: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 14 Notations and definitions (5) •Online-algorithm (recursive solution): • Objective (convergence): Signal processing on digital, neural, and kiloprocessor based architectures: Wiener filtering 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 15 Main application classes • System identification and modeling – (E.g.: modeling of unknown channel distortion) • Prediction – (E.g.: adaptive-predictive codingin speech communication) – Linear time series prediction (E.g. financial time series) • Inverse identification – (E.g.: equalization of communication channels) • Noise cancelation www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 16 System identification and modeling Unknown System Adaptive filter Desired output xk dk yk Output signal ek=dk -yk - + Error signal Formore detailsseetheresultsof BAUER, P. –SPAGNUOLO, G. –BOKOR, J (2007). Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 17 Linear time series prediction Adaptive filter - + Error signal Delay Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 18 Inverse identification Unknown System Adaptive filter System input - + Delay Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 19 Noise cancelation with a reference signal Adaptive filter yk - + ek=dk Additive Gaussian Noise Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 20 Some other adaptive filter configurations (1) Channel equalization using training sequence (see later) Transmitter Adaptive filter yk Additive Gaussian Noise - + Channel + + xk dk .k Training phase ek=dk -yk Receiver Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 21 Some other adaptive filter configurations (2) Equalization in decision-directed(decision-feedback/IIR) mode (without training sequence) Adaptive filter yk - + xk ek Threshold detector Receiver Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 22 Some other adaptive filter configurations (3) Time-delayestimator:filtercancelsthedelaybetweenx1kandx2k.ThepeakinwgivestheDdelay,whichistakenasmultipleofthesampleinterval. Adaptive filter yk - + ek Additive Gaussian Noise Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 23 Wiener filter (1) • Autocorrelation function: • Cross correlation function: Objective: constant Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 24 Wiener filter (2) • Properties of the correlation matrix (R): 1. Toeplitz: 2. Symmetric: 3. Hermitian: 4. Positive semi definite: 5. Eigenvectors are orthonormal, non-negative eigenvalues: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 25 Wiener filter (3) • Objective: • Global minimum exists because of Property 4. • Solution: • Wiener-Hopf normal equation: • Problems (why we should go further into adaptive signal processing) : 1. matrix inversion is not cost efficient: 2. statistical features are not known: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 26 The need for recursive and adaptive solutions InthecaseofrealinformationprocessesR(k)andr(k)arenotknown,furthermorearechangingintimebecauseofonlyquasistationerpropertyofdealtprocesses(e.g.:voicecanbetreatedasastationerprocessonlyfora30mstimewindow) Recursivesolution:gradientdescentalgorithm: withoutmatrixinversion. Steadystate: Speed of convergence Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 27 Recursive solution of Wiener filter (1) Eigenvector basis transformation: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 28 Recursive solution of Wiener filter (2) After rewriting the formula without R: Two vector can be only equal, if each of the components are equal: This differential equation has the following homogeneous solution: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 29 Recursive solution of Wiener filter (3) After replacing it into the original formula: Transient component: Wiener solution: Whatistheoptimalstepsizeinordertomaximizethespeedofconvergence? Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 30 Recursive solution of Wiener filter (5) Relaxation: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 31 Recursive solution of Wiener filter (6) The step size can be optimal iff, Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 32 Recursive solution of Wiener filter (7) Problems: shouldbesolved,butduetothecomplexityofeigenvaluedecompositionitisimpossibletobedoneinreal-time! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 33 Recursive solution of Wiener filter (8) Estimation of eigenvalues: Gersgorin circles R(0)canbeobservable!Anearoptimalstepsizecanbeimplemented! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 34 Adaptive filter solution is changing in time T T T Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 35 Adaptive filtering with unknown statistical parameters(1) Problem: Rand rare not given! However a learning set can be known (a set of input-output pairs): Empirical error function: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 36 Unknown statistical parameters(2) Does it converge to the analytical solution? Notations: Application of the projection theorem: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 37 Unknown statistical parameters(3) After re-ordering: Itapproximatestotheoptimalsolution,inthesensethatweusetheconsistentestimationofcorrelationmatrixandvector,respectively! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 38 A recursive solution: LD algorithm(1) We can decompose the correlation matrix for consecutive diadesin time. The matrix diadeinversion lemma states: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 39 A recursive solution: LD algorithm(2) By using the decomposition we can write the optimal recursion, the Levinson-Durbin algorithm: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 40 The RM algorithm The computing complexity of the term is high: Simpler solution with stochastic approximation is a substitution of a monotone decreasing function: Robbins-Monroe algorithm Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 41 The solution yielded by the RM algorithm Solution converges only in mean square, i.e.: TheproofofthisstatementisbasedontheKushner-Clarktheorem(cominglater),firstweonlydemonstratethatinequilibriumindeedtheoptimalsolutionisobtained. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 42 Steady state analysis of the RM algorithm (1) Inordertoanalyzetheequilibrium,onemustfirstkeepinmindthatthisalgorithmisastochastic(random)recursion.Asresult,nochangeswilloccuriftheaverageofisgoingtobezero.Asaresultforreachingtheequilibriumthefollowingsetofequationsmustbesatisfied: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 43 Steady state solution of the RM algorithm (2) which condition can be rewritten as follows: or in vector notation: which is just the solution of the Wiener filtering! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 44 The LMS algorithm Least Mean Squares algorithm: LD algorithm: high computational complexity, optimal convergence RMalgorithm:lowercomplexity,onlyasymptoticconvergencecanbeguaranteed Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 45 LMS algorithm(2) LMSalgorithm:verylowcomplexity,noconvergenceguaranteed,butmostlyitworks!(comparedtotheRMalgorithm) Steepest-descentversionofRMalgorithm. PerformingtheLMSrecursiononlytheobservedsamplesofrandomprocessesandareneededandthealgorithmconvergetotheoptimalsolutionofWienerfilteringwithoutanyaprioriknowledgeonthecorrelationpropertiesoftheprocesses. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 46 Applications of adaptive filtering • Open questions:– What is the optimal degree of the model? J=? – Information theoretical solution (Akaike, Risamen) – VC dimension (Vapnik Chervonenkis) • Thisalgorithmhaswidespreadapplicationsin– datacompression, – adaptivechannelequalization, – noisecancellation. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 47 Linear prediction(1) Past samples of an ergodic and weakly stationary process are given: Let us predict the future: Prediction with linear filter: Optimal linear predictive filter: Task: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 48 Linear prediction (2) ThisoptimizationtaskequalstoaspecialWiener-filteringproblem,where: Note: Model degree is only J(not J+1). If Ris not known, use the RM algorithm: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 49 Implementation in real-life communication systems The source is not stationary, only in time slots, therefore filter parameters should be re-optimized all the time: Optimal filter setting should be resent according to the statistical feature of the learning set! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 50 Applications: adaptive-predictive coding(1) Access Channel Coding Decoding T T T Access Channel Sender Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 51 Applications: adaptive-predictive coding(2) T T T Access Channel Receiver Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 52 Applications: adaptive-predictive coding(3) Real-time implementation: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 53 Applications: adaptive-predictive coding (4) Weareinterestedindatacompressionrate. with the optimal filter coefficients this becomes Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 54 Applications: adaptive-predictive coding (5) Ris hermitian, therefore it has orthonormal eigenvectors only positive eigenvalues: Optimal filter can be represented in the eigenvector space: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 55 Applications: adaptive-predictive coding (6) Theenergyoftheinputsignalismuchhigherthantheenergyofthecompressedsignal,whichyieldsbetterquantizationpossibilities! Theentropyofthepredictedsignalissmallerthantheoriginalone,thussourcecodingcanbemoreefficient! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing figure1_Adaptive_Signal_Processing.jpg www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 56 Applications: adaptive-predictive coding (7) Illustration of the effect of data compression Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 57 Applications: adaptive-predictive coding (8) • The adaptive-predictive coding (or linear predictive coding) is used as a form of voice compression by phone companies (e.g.. in the GSM standard).– GSM coder uses this approach and achieves 6.5 Kbit/s instead of 64 Kbit/s in the case of voice! • It is also used for secure wireless, where voice must be digitized, encrypted and sent over a narrow voice channel (e.g.. Navajo I). • LPC synthesis can be used to construct vocoders where musical instruments are used as excitation signal to the time-varying filter estimated from a singer's speech. • LPC predictors are used in Shorten, MPEG-4 ALS, FLAC, and other lossless audio codecs. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 58 Applications: channel equalization (1) Wirelesschannelimpairments: – Shadowing,large-scalepathloss –MultipathFading,rapidsmall-scalesignalvariations(ISI) –DopplerSpreadduetomotionofmobileunit Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 59 Applications: channel equalization (2) Duetothedistortionoffadingchannel,thesignalpropagatesinamultipathfashionfromthesendertothereceiver!Thisphenomenoncausesseveredistortioninthetransmissioncharacteristicsofthechannel,i.e.thesignalsofthepastgetmixedwithpresentvalues(IntersymbolInterference)whichintroducesmemoryintheITchannelmodel! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 60 Applications: channel equalization (3) Thechannelimpairmentscanleadtosignificantdistortionorattenuationofthereceivedsignal(SNR)whichdegradeBitErrorRate(BER)ofdigitallymodulatedsignal. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 61 Applications: channel equalization (4) • TwotechniquesareusedtoimprovereceivedsignalqualityandlowerBER:– Diversity(expensiveandresourceconsuming):Itrequiresdoubleantennasordoublespectrum. – Equalization(amoreeconomicalapproach):itrequiresonlyDSPandalgorithmicdevelopments. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 62 Applications: channel equalization (5) • Quality of Service (QoS) of a wireless communication system: Spectral efficiency [(bit/sec)/Hz] whichreferstothemaximaldataratethatcanbetransmittedoveragivenbandwidthinaspecificcommunicationsystem.(e.g.InGSM(1991)systemR=0.104Mbit/spercarrier,B=0.2MHzpercarrierSE=R/B=0.52(bit/sec)/Hz,orinanLTE(2009)systemSE=16.32(bit/sec)/Hz,orin802.11gSE=2.7(bit/sec)/Hz) • Spectralefficiencyisdeterminedbythebiterrorrate! • The bit error rate is determined by the channel distortion. • Thus adaptive equalization plays a central role. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 63 Applications: channel equalization (6) • EqualizationalgorithmsaimtotackletheISIbyimplementinglinearfilterstoequalizethechanneldistortionsatthereceiverside! • Challenge:howtodeveloplowcomplexityadaptivesignalprocessingalgorithms,whichare:– real-timeandeasilyimplementable; – yieldlowBitErrorRate; – havelearningcapabilitiestoequalizeunknownchannelsonlybasedoninput-outputsamples. Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 64 Applications: channel equalization (7) Ad hoc Sensor Networks: Detection and channel equalization Applications: channel equalization (8) • Thesimplifiedmodelandnotations: ISI Equivalent filter Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 66 Applications: channel equalization (9) • Signal: • Channel can be represented as a linear filter, which has an impulse response: • Additive Gaussian noise : • Adaptive filter with impulse response: • What is optimal w? Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 67 Applications: channel equalization (10) • What is optimal w?– Optimal filter with given channel: Equalization – Optimal filter with unknown channel: Adaptive equalization – Optimal filter with unknown channel without learning set: Blind adaptive equalization • Tradeoff between noise and ISI cancellation. 1. strategy: Zero Forcing (ZF) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 68 Applications: channel equalization (11) TheZero-Forcingstrategy:weassumerelativelylargesignaltonoiseratio(theeffectofnoisecanbeneglectedandfocusonlyonISIcancellation): Typical application: wired communication The optimal weights: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 69 Applications: channel equalization (12) Problem:J+1freeparametersandJ+L+2equationswhichleadsoverdeterminedequationsystem! Solution:defining a new goal function › Peak Distortion (PD): the maximal value of ISI The optimal weights: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 70 Applications: channel equalization (13) The Peak Distortion : Extremal point: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 71 Applications: channel equalization (14) In the case of unknown H: adaptive Zero Forcing Training set: The algorithm converges if (Kushner Clark theorem): Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 72 Applications: channel equalization (15) The algorithm converges to the ZF solution: adaptive ZF! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 73 Applications: channel equalization (16) Problem:ZeroForcingeliminatesISI,butenhancestheeffectofadditivenoise Energy of the noise component: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 74 Applications: channel equalization (17) What happens in low SNR domain ? Noise energy can be increase too much in case of bad channel! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 75 Applications: channel equalization (18) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 76 Applications: channel equalization (19) Minimum Mean Square Error: Adaptive solution of Wiener-filtering! Applying the Robins-Monroe algorithm: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 77 Applications: channel equalization (20) The correlation matrix: What about the noise in case of MMSE? Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 78 Applications: channel equalization (21) What happens in low SNR domain ? Eigenvectors: Noise energy: ThenoisecanneverbecameinfinitelylargebecauseoftheN0componentinthedenominator! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 79 Applications: channel equalization (22) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 80 Applications: channel equalization (23) Adaptive version of MMSE: Problem:Channel condition is changing in time, therefore a lot of overhead is needed because of the learning set. E.g.: In GSM system 18% of the packet is this overhead! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 81 Applications: channel equalization (24) A solution without learning set (Blind signal processing): Is any guarantee for convergence? If there is, Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 82 Applications: channel equalization (25) which is not the original Wiener solution! Furthermore the probability of bit error is not constant, it depends on the filter: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 83 Applications: channel equalization (26) The service provider is interested in the probability of bit error, because it is the real QoS subject which should be minimized: What is this .(w) function? Recall: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 84 Applications: channel equalization (27) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 85 Applications: channel equalization (28) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 86 Applications: channel equalization (29) Here .(.)denotes the standard normal cdf. and note that Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 87 Applications: channel equalization (30) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 88 Applications: channel equalization (31) The new goal function: Problems: 1. Channel information is needed! 2. Algorithm is too complex: every step needs O(2M-1) evaluation! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 89 Applications: channel equalization (32) Using Monte Carlo methods can be a solution for reducing complexity. Using upper and lower bounds can be an other solution for the problem of complexity. Lemma: If a < b < c, then Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 90 Applications: channel equalization (33) The modified goal function: No more complexity problem! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 91 surf1_0_0 No ISI h=(1, 0.3) surf1_03_0 Simulation Results(1) Surfaces of error probability Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 92 Simulation Results(2) Surfaces of error probability surf1_05_ h=(1, 0.5, 0.3) surf1__05_01 h=(1, -0.5, 0.1) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 93 Simulation Results(3) Bit error probability vs. Mean square error MSE_BEP h=(1, -0.5, 0.1) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 94 Simulation Results(4) Local minimum pointsarepossible! Bit error probability vs. Mean square error BEP MSE Mean square error Bit error probability h=(1, -0.5, 0.1) Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 95 Simulation Results(5) BER vs. SNR Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 96 Questions(1) 1. WhatisWienerfiltering? 2. WhaterrorfunctiontheWienerfilterwillminimize? 3. Whatarethepropertiesofthecorrelationmatrix? 4. GivetwopracticalexamplesfortheuseofWienerfilters? 5. Summarizetheproblemofadaptiveradiochannelequalization!Givetheoptimalsolution! 6. Summarizetheproblemoffirstorderadaptive-predictivecoding!GivetheWienersolution!Showthatthesolutionincreasesthespeedofdatatransmission! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 97 Questions(2) 7. Whatistheproblemofadaptive-predictivecodinginmobilecommunicationsystems?Givetheblockdiagramofthesolution,andexplainthenotations!GivetheRobinson-Monroealgorithmandexplaintheformula! 8. WhatkindofoptimalityisguaranteedsolvingtheWiener-Hopfequation?Proveit! 9. WhatistheZeroForcingsolutioninthecaseofchannelequalization?Whathappenswiththenoise? Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 98 An example of Wiener filtering (1) Problem: HowcanweestimatethecorrelationmatrixRbasedobservation?GiveanexampleofthecorrelationmatrixRifthedimensionis4!Basedonthecorrelationmatrixfindtheoptimal.parameterwhichguaranteesthefastestconvergence! Solution: Bydefinition,thecorrelationmatrixofastochasticprocessis Rij=E{xixj}, whichcanbeestimatedusingtheobservationswith Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 99 An example of Wiener filtering (2) Solution(continued):LetustakethecorrelationmatrixR(b)fromexample1!The.parameterwhichguaranteesthefastestconvergencecanbeobtainedfromtheeigenvaluesofR.TheeigenvaluesofRare fromwhichtheoptimal.is: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 100 Problems (1) 1. Define Rijelement of the correlation matrix! 2. Are any of the following matrices a valid correlation matrix?: Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 101 Problems (2) ThechanneldistortioninawirelesscommunicationsystemistobeequalizedbyanFIRfilterofthirddegree.WeusetheLMSalgorithmtosettheequalizercoefficientswithparameter.=1.Thelearningsetisgivenasfollows: While the initial vector is Give the filter coefficient vector after the first update cycle ! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 102 Problems (3) A random process is to be compressed by a predictor of second degree. The correlation function is given as follows: Calculate the optimal predictor coefficients ! Signal processing on digital, neural, and kiloprocessor based architectures: Adaptive Signal Processing www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 103 Summary • Fundamentalissues:FIRWiener-filter,applicationsofadaptivesignalprocessing:adaptive-predictivecoding,channelequalization. • ProblemofsignalestimationinthepresenceofundesirednoiseorinterferencecanbesolvedbyWienerfilter. • Adaptivitymeansreal-timere-optimizationpossibility. • TheoryofWienerfilterscanbeappliedtosolveITproblemssuchascodingorradiochannelequalization. Next lecture:Introduction to neural processing