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