ADAPTIVE FILTERING PRIMER with MATLAB ® 7043_C000.fm Page ii Friday, January 13, 2006 4:23 PM ADAPTIVE FILTERING PRIMER with MATLAB ® Alexander D. Ramadan Boca Raton London New York A CRC title, part of the Taylor & Francis imprint, a member of the Taylor & Francis Group, the academic division of T&F Informa plc.fm Page 1 Tuesday, November 29, 2005 2:43 PM Published in 2006 by CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2006 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group No claim to original U. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number-10: 0-8493-7043-4 (Softcover) International Standard Book Number-13: 978-0-8493-7043-4 (Softcover) Library of Congress Card Number 2005055996 This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated.
A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use. No part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.com (http://www.com/) or contact the Copyright Clearance Center, Inc.
(CCC) 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.
Library of Congress Cataloging-in-Publication Data Poularikas, Alexander D., 1933- Adaptive filtering primer with MATLAB / by Alexander D. Poularikas and Zayed M. Includes bibliographical references and index.3815'324--dc22 2005055996 Visit the Taylor & Francis Web site at http://www.com Taylor & Francis Group and the CRC Press Web site at is the Academic Division of Informa plc.fm Page v Friday, January 13, 2006 4:23 PM Dedication To my grandchildren Colton-Alexander and Thatcher-James, who have given us so much pleasure and happiness. To my great mom, Fatima, and lovely wife, Mayson, for their understanding, support, and love.fm Page vi Friday, January 13, 2006 4:23 PM 7043_C000.fm Page vii Friday, January 13, 2006 4:23 PM Preface This book is written for the applied scientist and engineer who wants or needs to learn about a subject but is not an expert in the specific field.
It is also written to accompany a first graduate course in digital signal processing. In this book we have selected the field of adaptive filtering, which is an important part of statistical signal processing. The adaptive filters have found use in many and diverse fields such as communications, control, radar, sonar, seismology, etc. The aim of this book is to present an introduction to optimum filtering as well as to provide an introduction to realizations of linear adaptive filters with finite duration impulse response.
Since the signals involved are ran- dom, an introduction to random variables and stochastic processes are also presented. The book contains all the material necessary for the reader to study its contents. An appendix on matrix computations is also included at the end of the book to provide supporting material. The book includes a number of MATLAB® functions and m-files for practicing and verifying the material in the text.
These programs are designated as Book MATLAB Functions. The book includes many computer experiments to illustrate the underlying the- ory and applications of the Wiener and adaptive filtering. Finally, at the end of each chapter (except the first introductory chapter) numerous problems are provided to help the reader develop a deeper understanding of the material presented. The problems range in difficulty from undemanding exercises to more elaborate problems.
Detailed solutions or hints and sug- gestions for solving all of these problems are also provided. Additional material is available from the CRC Web site, www. Under the menu Electronic Products (located on the left side of the screen), click Downloads & Updates. A list of books in alphabetical order with Web downloads will appear.
Locate this book by a search or scroll down to it. After clicking on the book title, a brief summary of the book will appear. Go to the bottom of this screen and click on the hyperlinked “Download” that is in a zip file. MATLAB® is a registered trademark of The Math Works, Inc.
and is used with permission. The Math Works does not warrant the accuracy of the text or exercises in this book. This book’s use or discussion of MATLAB® software or related products does not constitute endorsement or sponsorship by The 7043_C000.fm Page viii Friday, January 13, 2006 4:23 PM Math Works of a particular pedagogical approach or particular use of the MATLAB® software. For product information, please contact: The Math Works, Inc.
3 Apple Hill Drive Natick, MA 01760-2098 USA Tel: 508-647-7000 Fax: 508-647-7001 E-mail: info@mathworks.com Web: www.fm Page ix Thursday, January 19, 2006 10:01 AM Authors Alexander D. Poularikas received his Ph. from the University of Arkansas and became professor at the University of Rhode Island. He became chairman of the Engineering Department at the University of Denver and then became chairman of the Electrical and Computer Engineering Department at the University of Alabama in Huntsville.
He has published six books and has edited two. Poularikas served as editor-in-chief of the Signal Processing series (1993–1997) with ARTECH HOUSE and is now editor-in-chief of the Electrical Engineering and Applied Signal Processing series as well as the Engi- neering and Science Primers series (1998–present) with Taylor & Francis. He was a Fulbright scholar, is a lifelong senior member of IEEE, and is a member of Tau Beta Pi, Sigma Nu, and Sigma Pi. In 1990 and 1996, he received the Outstanding Educator Award of IEEE, Huntsville Section.
Ramadan received his B. degrees in electrical engineer- ing (EE) from Jordan University of Science and Technology in 1989 and 1992, respectively. He was a full-time lecturer at Applied Science University in Jordan from 1993 to 1999 and worked for the Saudi Telecommunications Company from 1999 to 2001. Ramadan enrolled in the Electrical and Computer Engineering Department at the University of Alabama in Huntsville in 2001, and received a second M.
in 2004 and a Ph. in 2005, both in electrical engineering and both with honors. His main research interests are adaptive filtering and their applications, signal processing for communications, and statistical digital signal processing.fm Page x Friday, January 13, 2006 4:23 PM 7043_C000.fm Page xi Friday, January 13, 2006 4:23 PM Contents Chapter 1 Introduction .3 Outline of the text.2 Chapter 2 Discrete-time signal processing.1 Discrete-time signals .2 Transform-domain representation of discrete-time signals .4 Discrete-time systems.17 Hints-solutions-suggestions .17 Chapter 3 Random variables, sequences, and stochastic processes .1 Random signals and distributions .4 Special random signals and probability density functions .5 Wiener–Khintchin relations.6 Filtering random processes .7 Special types of random processes .8 Nonparametric spectra estimation.9 Parametric methods of power spectral estimations.51 Hints-solutions-suggestions .52 Chapter 4 Wiener filters .1 The mean-square error.2 The FIR Wiener filter.3 The Wiener solution .4 Wiener filtering examples.73 Hints-solutions-suggestions .fm Page xii Friday, January 13, 2006 4:23 PM Chapter 5 Eigenvalues of Rx — properties of the error surface .1 The eigenvalues of the correlation matrix.2 Geometrical properties of the error surface .81 Hints-solutions-suggestions .82 Chapter 6 Newton and steepest-descent method.1 One-dimensional gradient search method .2 Steepest-descent algorithm.96 Hints-solutions-suggestions .97 Chapter 7 The least mean-square (LMS) algorithm .2 Derivation of the LMS algorithm.3 Examples using the LMS algorithm .4 Performance analysis of the LMS algorithm.5 Complex representation of LMS algorithm.129 Hints-solutions-suggestions .130 Chapter 8 Variations of LMS algorithms.1 The sign algorithms.2 Normalized LMS (NLMS) algorithm .3 Variable step-size LMS (VSLMS) algorithm.4 The leaky LMS algorithm.5 Linearly constrained LMS algorithm.6 Self-correcting adaptive filtering (SCAF).7 Transform domain adaptive LMS filtering.8 Error normalized LMS algorithms.167 Hints-solutions-suggestions .167 Chapter 9 Least squares and recursive least-squares signal processing.1 Introduction to least squares.2 Least-square formulation.3 Least-squares approach.6 Least-squares finite impulse response filter .7 Introduction to RLS algorithm .197 Hints-solutions-suggestions .fm Page xiii Monday, January 16, 2006 10:16 AM Abbreviations .205 Appendix — Matrix analysis .3 Matrix operation and formulas .4 Eigen decomposition of matrices .6 Differentiation of a scalar function with respect to a vector .fm Page xiv Friday, January 13, 2006 4:23 PM chapter 1 Introduction 1.1 Signal processing In numerous applications of signal processing and communications we are faced with the necessity to remove noise and distortion from the signals. These phenomena are due to time-varying physical processes, which some- times are unknown.
One of these situations is during the transmission of a signal (message) from one point to another. The medium (wires, fibers, microwave beam, etc.), which is known as the channel, introduces noise and distortion due to the variations of its properties. These variations may be slow varying or fast varying. Since most of the time the variations are unknown, it is the use of adaptive filtering that diminishes and sometimes completely eliminates the signal distortion.
The most common adaptive filters, which are used during the adaptation process, are the finite impulse response filters (FIR) types. These are prefer- able because they are stable, and no special adjustments are needed for their implementation. The adaptation approaches, which we will introduce in this book, are: the Wiener approach, the least-mean-square algorithm (LMS), and the least-squares (LS) approach.2 An example One of the problems that arises in several applications is the identification of a system or, equivalently, finding its input-output response relationship. To succeed in determining the filter coefficients that represent a model of the unknown system, we set a system configuration as shown in Figure 1.
The input signal, {x(n)}, to the unknown system is the same as the one entering the adaptive filter. The output of the unknown system is the desired signal, {d(n)}. From the analysis of linear time-invariant systems (LTI), we know that the output of linear time-invariant systems is the convolution of their input and their impulse response. 1 2 Adaptive filtering primer with MATLAB Unknown d (n) e (n) x(n) + system (filter) _ h Adaptive y (n) filter (system) w e (n) = d (n) − y (n) Figure 1.
Let us assume that the unknown system is time invariant, which indi- cates that the coefficients of its impulse response are constants and of finite extent (FIR). Hence, we write N −1 d(n) = ∑ h x(n − k) k=0 k (1.1) The output of an adaptive FIR filter with the same number of coefficients, N, is given by N −1 y(n) = ∑ w x(n − k) k=0 k (1.2) For these two systems to be equal, the difference e(n) = d(n) − y(n) must be equal to zero. Under these conditions the two sets of coefficients are equal. It is the method of adaptive filtering that will enable us to produce an error, e(n), approximately equal to zero and, therefore, will identify that wk’s ≅ hk’s.3 Outline of the text Our purpose in this text is to present the fundamental aspects of adaptive filtering and to give the reader the understanding of how an algorithm, LMS, works for different types of applications.
These applications include system identification, noise reduction, echo cancellation during telephone conver- sation, inverse system modeling, interference canceling, equalization, spec- trum estimation, and prediction. In order to aid the reader in his or her understanding of the material presented in this book, an extensive number of MATLAB functions were introduced. These functions are identified with the words “Book MATLAB Function.