E-Book Content
THE FAST FOURIER TRANSFORM AND ITS APPLICATIONS E. Oran Brigham Avantek, Inc. Prentice Hall Englewood Cliffs, New Jersey 07632 Library of Congress Cataloging-in-Publication Data Brigham, E. Oran The fast Fourier transform and its applications I E. Oran Brigham. p. cm. - (Prentice-Hall signal processing series) Continues: The fast Fourier transform. Bibliography: p. Includes index. ISBN 0-13-307505-2 I. Fourier transformations. I. Title. II. Series QA403.B75 1988 515.7'23-dcI9 Editorial/production supervision and interior design: Gertrude Szyferblatt Cover design: Diane Saxe Manufacturing buyer: Barbara Kittle/Cindy Grant © 1988 by Prentice-Hall, Inc. A Division of Simon & Schuster Englewood Cliffs, New Jersey 07632 All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. Printed in the United States of America 10 9 8 7 6 5 4 3 ISBN 0-13-307505-2 Prentice-Hall International (UK) Limited, LClIldon Prentice-Hall of Australia Pty. Limited, Syd/ley Prentice-Hall Canada Inc., Toronto Prentice-Hall Hispanoamericana, S.A., Mexico Prentice-Hall of India Private Limited, New De/hi Prentice-Hall of Japan, Inc., Tokyo Simon & Schuster Asia Pte. Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro To Cami A very special daughter CONTENTS PREFACE CHAPTER 1 INTRODUCTION 1.1 1.2 1.3 CHAPTER 2 2.5 9 The Fourier Integral 9 The Inverse Fourier Transform II Existence of the Fourier Integral 13 Alternate Fourier Transform Definitions 22 Fourier Transform Pairs 23 FOURIER TRANSFORM PROPERTIES 3.1 3.2 3.3 3.4 1 The Ubiquitous FFT Interpreting the Fourier Transform 4 Digital Fourier Analysis 7 THE FOURIER TRANSFORM 2.1 2.2 2.3 2.4 CHAPTER 3 xiii 30 Linearity 30 Symmetry 32 Time and Frequency Scaling 32 Time and Frequency Shifting 35 vii Contents viii 3.5 3.6 3.7 3.8 3.9 CHAPTER 4 CONVOLUTION AND CORRELATION 4.1 4.2 4.3 4.4 4.5 4.6 4.7 CHAPTER 5 5.3 5.4 6.4 6.5 74 Fourier Series 74 Fourier Series as a Special Case of the Fourier Integral 77 Waveform Sampling 79 Sampling Theorems 83 THE DISCRETE FOURIER TRANSFORM 6.1 6.2 6.3 50 Convolution Integral 50 Graphical Evaluation of the Convolution Integral 51 Alternate Form of the Convolution Integral 54 Convolution Involving Impulse Functions 57 Time-Convolution Theorem 60 Frequency-Convolution Theorem 64 Correlation Theorem 65 FOURIER SERIES AND SAMPLED WAVEFORMS 5.1 5.2 CHAPTER 6 Alternate Inversion Formula 40 Even and Odd Functions 40 Waveform Decomposition 42 Complex Time Functions 44 Summary Table of Fourier Transform Properties 46 A Graphical Development 90 Theoretical Development 92 Discrete Inverse Fourier Transform 97 Relationship Between the Discrete and Continuous Fourier Transform 98 Discrete Fourier Transform Properties 107 89 CHAPTER 7 DISCRETE CONVOLUTION AND CORRELATION 7.1 7.2 7.3 7.4 CHAPTER 8 8.9 8.10 CHAPTER 9 9.5 167 Fourier Transform Applications 167 FFT Data-Weighting Functions 178 FFT Algorithms for Real Data 188 Inverse Fourier Transform Applications 195 Laplace Transform Applications 199 FFT CONVOLUTION AND CORRELATION 10.1 131 Matrix Formulation 131 Intuitive Development 132 Signal Flow Graph 136 Dual Nodes 138 W P Determination 140 Unscrambling the FFT 141 FFT Computation FlowChart 141 FFT BASIC and PASCAL Computer Programs 145 Theoretical Development o