1997 • 192 Pages • 15.95 MB • English

Posted April 14, 2020 • Uploaded
by ycrooks

PREVIEW PDF

Page 1

Mathematics of Multidimensional Fourier Transform Algorithms Second Edition Springer Science+Business Media, LLC

Page 2

Richard Tolimieri Myoung A n Chao L u Mathematics of Multidimensional Fourier Transform Algorithms Second Edition C S . Burrus Consulting Editor With 21 Illustrations Springer

Page 3

Signal Processing and Digital Filtering Synthetic Aperture Radar J. P. Fitch Multiplicative Complexity, Convolution and the DFT M.T. Heideman Array Signal Processing S.U. Pillai Maximum Likelihood Deconvolution J.M. Mendel Algorithms for Discrete Fourier Transform and Convolution T. Tolimieri, M. An, and C. Lu Algebraic Methods for Signal Processing and Communications Coding R.E. Blahut Electromagnetic Devices for Motion Control and Signal Processing Y.M. Pulyer Mathematics of Multidimensional Fourier Transform Algorithms, Second Edition R. Tolimieri, M. An, and C. Lu Lectures on Discrete Time Filtering RS. Bucy Distributed Detection and Data Fusion P.K. Varshney

Page 4

Richard Tolimieri Myoung An Department of Electrical Engineering A J . Devaney Associates City College of CUNY 52 Ashford Street New York, NY 10037, USA Allston, M A 02134, USA Chao Lu Department of Computer and Information Sciences Towson State University Towson, MD 21204, USA Consulting Editor Signal Processing and Digital Filtering C S . Burrus Professor and Chairman Department of Electrical and Computer Engineering Rice University Houston, TX 77251-1892, USA Library of Congress Cataloging-in-Publication Data Tolimieri, Richard, 1940- Mathematics of multidimensional Fourier transform algorithms / Richard Tolimieri, Myoung An, Chao Lu. — 2nd ed. p. cm. — (Signal processing and digital filtering) Includes bibliographical references and index. ISBN 978-1-4612-7352-3 ISBN 978-1-4612-1948-4 (eBook) DOI 10.1007/978-1-4612-1948-4 1. Fourier transformations. I. An, Myoung. II. Lu, Chao. m. Title. IV. Series QA403.5.T655 1997 515723—dc21 97-169 Printed on acid-free paper. © 1997 Springer Science+Business Media New York Originally published by Springer-Verlag New York, Inc. in 1997 Softcover reprint o f the hardcover 1st edition 1997 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher, Springer Science+Business Media, L L C except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic ad- aptation, computer software, or by similar or dissimilar methodology now known or hereaf- ter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as un- derstood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Production managed by Steven Pisano; manuiactiiring supervised by Joe Quatela. Photocomposed pages prepared from the authors' LaTeX files. 9 8 7 6 5 4 3 2 1 ISBN 978-1-4612-7352-3

Page 5

Preface The Fourier transform of large multidimensional data sets is an essential computation in many scientific and engineering fields, including seismol- ogy, X-ray crystallography, radar, sonar, and medical imaging. Such fields require multidimensional arrays for complete and faithful modeling. Clas- sically, a set of data is processed one dimension at a time, permitting con- trol over the size of the computation and calling on well-established 1- dimensional programs. The rapidly increasing availability of powerful com- puting chips, vector processors, multinode boards, and parallel machines has provided new tools for carrying out multidimensional computations. Multidimensional processing offers a wider range of possible implementa- tions as compared to I-dimensional processing, due to the greater flexibility of movement in the data indexing set. This increased freedom, along with the massive size data sets typically found in multidimensional applications, places intensive demands on the communication aspects of the computa- tion. The writing of code that takes into account all the algorithmic pos- sibilities and matches these possibilities to the communication capabilities of the target architecture is an extremely time-consuming task. In the first chapter, we will review the tensor product and its role in modeling I-dimensional Fourier transform algorithms. Tensor product for- malism provides powerful tools for keeping track of an algorithm's granu- larity and index calculations. The algebra of the tensor product, especially that of an associated class of permutations, the stride permutations, plays a fundamental role in establishing simple rules, in the form of tensor product identities for modifying the communication requirements of a computation and for greatly simplifying the generation of code, which can take advan-

Page 6

vi Preface tage of computational power and communication bandwidth of a target processor. A large part of code generation.can take place on the level of algebraic manipulation rather than in the more time-consuming and error- prone level of programming manipulation. The second chapter extends the role of tensor product to multidimen- sions. The main idea is that I-dimensional stride permutations have exact analogues in a multidimensional setting. Vector segmentation, which plays such an important role in describing I-dimensional stride permutations, is replaced by array segmentation. In form, I-dimensional FFT is exactly the same as multidimensional FFT except that the interpretation of parallel and vector operations in terms of vector segmentation must now be made in relation to array segmentation. This class of multidimensional FFT was introduced by G.E. Rivard (1977) and D.B. Harris et al. (1977) and goes by the name of Vector-radix FFT. A major goal of this text is to provide an abstract treatment of the Fourier transform that highlights the relatively few basic mathematical principles that underlie a large part of I-dimensional and multidimensional Fourier transform theory and implementation. By emphasizing the unity underlying these algorithms, we can achieve deeper insights into their differ- ences and learn how these differences can be exploited in implementation. In chapter 3, we begin the mathematics required for the abstract defi- nition of Fourier transform. Finite abelian groups will play a central role in this theory. The concept of duality will be introduced. In chapter 4, we define the Fourier transform of a finite abelian group that is canonical in the sense that it is coordinate-free. This approach brings out the role played by duality in Fourier transform theory and implementation. Duality is built into the definition of the Fourier transform. The duality between periodization and decimation will playa fundamental role in the design of Fourier transform algorithms. The results on periodization and decimation unify all additive 1- and multidimensional Fourier transform algorithms, including the Cooley-Tukey FFT, discussed in chapter 5, and the reduced transform algorithm, discussed in chapter 8. The algorithms of chapter 5 and chapter 8 are based on the relationship between the Fourier transform of data indexed by some finite abelian group A and the Fourier transform of data indexed by subgroups and quotient groups of A. Theorems in chapter 4 explicitly describe this relationship in terms of duality and periodization-decimation. In chapters 6 and 7 we distinguish a special collection of subgroups of A called lines and planes and describe their relationship to duality. These results are directly applied to the reduced transform algorithms of chapter 8. However, this is but one of several important applications. In applications where a complete Fourier transform may not be required, these results can be used to compute partial Fourier transforms, Le., the Fourier transform only on some line or plane of the output without having to compute the entire Fourier transform.

Page 7

Preface vii The reduced transform algorithm completes the computation by comput- ing the Fourier transform on a covering set of lines or planes. The general structure of the Cooley-Thkey FFT as described in chapter 5 and that of the reduced transform algorithm are very similar. The first step in the Cooley-Thkey FFT is a collection of generalized periodizations that in- volve complex multiplications, while the first step in the reduced transform algorithm is a collection of periodizations that involve only additions. The generalized periodizations of the Cooley-Thkey FFT can be com- puted by Fourier transforms, but in order to do so full data transposition is required. The periodizations in the reduced transform algorithms greatly increase the number of additions required to carry out the computation. However, in a highly parallel environment, the reduced transform algo- rithm can have the advantage, since these additions can be carried out in parallel during the data-loading process (for some parallel architectures). Depending on the degree of parallelism and transform size, the reduced transform algorithm may avoid data transposition entirely, greatly reduc- ing the need for interprocessor communication, which is typically limited on large multinode processors. The role of these algorithms and hybrids produced by combining the two is still an active research area. In chapter 9, multiplicative DFT algorithms are discussed. We have con- centrated on the case where the indexing set is a field. We bring out the role of the reduced transform algorithm in deriving several well-known multi- plicative multidimensional DFT algorithms due to Nussbaumer-Quandalle and Auslander-Feig-Winograd. Starting from Rader's I-dimensional algo- rithm, we show that a multidimensional field algorithm can be derived using exactly the same approach. In fact, the basic algorithm depends only on the fact that the indexing set is a field. The interpretation of a field algorithm as a multidimensional DFT is a simple consequence of the re- sults in chapter 4. A purely multiplicative derivation of the Auslander et al. result is given in terms of factorizations of skew-circulant matrices. In chapters 10 and 11 we explore the implementation of different DFT algorithms on RISC and parallel architectures. We introduce machine pa- rameters and show how they are related to algorithmic parameters and how to write code based on optimal matching of these parameters. We wish to thank Dr. James W. Cooley for his many valuable discussions on algorithm design and implementation, and DARPA for its support dur- ing the formative years of writing this book. We also wish to thank AFOSR for its support during the last two years, in which time the ideas of this book have been tested and refined in applications to electromagnetics, multispec- tral imaging, and imaging through turbulance. Whatever improvements in this revision are due to the routines written in these applications. Richard Tolimieri Myoung An Chao Lu

Page 8

Contents Preface v 1 Tensor Product 1 1.1 Introduction 1 1.2 Tensor Product ... 2 1.3 Stride Permutations 6 1.4 Algebra of Stride Permutations. 8 1.5 Tensor Product Factorization .. 10 1.6 Fast Fourier Transform Algorithms I 13 1.7 General 1-Dimensional FFT 16 References 20 Problems ............... 23 2 Multidimensional Tensor Product and FFT 25 2.1 Introduction .............. 25 2.2 Multidimensional Fourier Transform. 26 2.3 2-Dimensional Operations ...... 28 2.4 2-Dimensional Cooley-Tukey FFT . 32 References 35 Problems ........ 36 3 Finite Abelian Groups 37 3.1 Introduction .. 37 3.2 Character Group . 39

Page 9

x Contents 3.3 Duality............ 42 3.4 Chinese Remainder Theorem 44 3.5 Vector Space L(A) 48 References 49 Problems . 49 4 Fourier Transform of Finite Abelian Groups 51 4.1 Introduction . 51 4.2 Fourier Transform of A . . . . 51 4.3 Induced Fourier Transform . . 53 4.4 Periodic and Decimated Data 55 4.5 Periodization and Decimation 57 References . 61 5 Cooley-Tukey and Good-Thomas 63 5.1 Introduction . 63 5.2 Good-Thomas FFT . . . . . 64 5.3 Abstract Cooley-Tukey FFT 65 References . 69 6 Lines 71 6.1 Introduction 71 6.2 Examples .. 72 6.3 Prime Case 75 6.4 Prime Power Case 76 6.4.1 Square case. 76 6.4.2 Rectangular case . 81 6.5 General Square Case. . . 84 6.6 General Rectangular Case. 87 References 88 Probkms . . . . . . . . . . . 89 1 Duality of Lines and Planes 91 7.1 Automorphism Group 91 7.2 Dual of Lines 94 7.3 Planes. 97 7.4 Duality 99 References 103 Problems ... 103 8 Reduced Transform Algorithms 105 8.1 Introduction ... 105 8.2 General Structure 106 8.3 Periodizations . 108 8.4 Examples..... 111

Page 10

Contents xi 8.4.1 2-Dimensional p X p, P a prime . III 8.4.2 2-Dimensional p2 x p2, P a prime 113 8.4.3 2-dimensional pR x pR RTA . . . 116 8.4.4 2-Dimensional M = pq, p and q distinct primes 116 8.4.5 3-D RTA . . 118 8.5 RTA Permutations . 120 References 123 Problems . . . . . . . . . . 123 9 Field Algorithm 125 9.1 Introduction...... 125 9.2 Rader Field Algorithm 126 9.3 Finite Fields 128 9.3.1 Properties of finite fields 128 9.3.2 Examples of finite fields. 128 9.4 Fourier Transform of Finite Fields . 129 9.4.1 Trace map 130 9.4.2 Evaluation map . . . . . 132 9.5 Factorization of Core Matrices . 133 9.6 Auslander-Feig-Winograd DFT 137 References 138 Problems . . . . . . . . . . . . . . . . . 139 10 Implementation on mse Architectures 141 10.1 Introduction 141 10.2 Algorithms for RISC Architectures ... 142 10.2.1 Implementation on model I RISC 143 10.2.2 Implementation on model II RISC 147 10.3 Implementation on the IBM RS/6000 149 10.4 Implementation on the Intel i860 . 156 References 159 11 Implementation on Parallel Architectures 161 11.1 Introduction 161 11.2 Parallel Implementation of FFT . . 163 11.3 Parallel Implementation of the RTA . 164 11.3.1 2-dimensional prime case 165 11.4 Parallel Implementation of FFT . . 166 11.5 Hybrid Algorithm . . . . . . . . . . 170 11.6 An Example Program on iPSC/860 173 References 180 Index 185

Fast Algorithms for Selection and Multidimensional Sparse Fourier Transform

2016 • 116 Pages • 1.19 MB

Fast Fourier Transform and Convolution Algorithms

1982 • 285 Pages • 5.43 MB

Fast Fourier Transform and Convolution Algorithms

1981 • 259 Pages • 6.64 MB

Algorithms for Discrete Fourier Transform and Convolution

1989 • 363 Pages • 5.9 MB

Algorithms for Discrete Fourier Transform and Convolution (Signal Processing and Digital Filtering)

1997 • 285 Pages • 2.49 MB

Fourier transform - signal processing

2012 • 366 Pages • 57.71 MB

discrete cosine transform algorithms for fpga devices - Domagoj Babic

2007 • 85 Pages • 1.32 MB

Fourier transform

2008 • 512 Pages • 31.6 MB

Fast Fourier Transform Algorithms with Applications

2016 • 341 Pages • 1.42 MB

Mathematics of the Discrete Fourier Transform

2003 • 247 Pages • 1.47 MB

Mathematics of the Discrete Fourier Transform

2002 • 247 Pages • 1.47 MB

Mathematics of the Discrete Fourier Transform

2003 • 248 Pages • 1.5 MB

Fast Fourier Transform - Algorithms and Applications

2010 • 443 Pages • 5.13 MB

Fast Fourier Transform - Algorithms and Applications

2012 • 443 Pages • 5.79 MB

Fast Fourier Transform - Algorithms and Applications

2010 • 437 Pages • 11.21 MB