The main emphasis of this book is the development of algorithms for processing multi-dimensional digital signals, and particularly, algorithms for multi-dimensional Fourier transforms in a form that is convenient for writing highly efficient code on a variety of vector and parallel computers. The rapidly increasing power of computing chips, the increased availability of vector and array processors, and the increasing size of the data sets to be analyzed make writing code that takes all the algorithmic possibilities into account and matches these to the target architecture a difficult task. By emphasizing the unified basis for the various approaches to multidimensional Fourier transforms, the book also clarifies how to exploit the differences in optimizing implementations. This book will be of interest not only to applied mathematicians and computer scientists, but also to seismologists, high-energy physicists, crystallographers, electrical engineers working on image processing, and others. Topics covered include: tensor products and the fast Fourier transform, one dimensional and multi-dimensional; finite Abelian groups and Fourier transforms; Cooley-Tukey and Good-Thomas algorithms; lines and planes; field algorithms; implementation on RISC and parallel architectures.
Author(s): Tolimieri R., et al.
Series: Signal Processing and Digital Filtering
Edition: 2ed
Publisher: Springer
Year: 1997
Language: English
Pages: 199
Tags: Приборостроение;Обработка сигналов;
Cover ......Page 1
Title ......Page 3
Preface ......Page 5
Contents ......Page 9
1.1 Introduction ......Page 13
1.2 Tensor Product ......Page 14
1.3 Stride Permutations ......Page 18
1.4 Algebra of Stride Permutations ......Page 20
1.5 Tensor Product Factorization ......Page 22
1.6 Fast Fourier Transform Algorithms I ......Page 25
1.7 General 1-Dimensional FFT ......Page 28
References ......Page 32
Problems ......Page 35
2.1 Introduction ......Page 37
2.2 Multidimensional Fourier Transform ......Page 38
2.3 2-Dimensional Operations ......Page 40
2.4 2-Dimensional Cooley-Tukey FFT ......Page 44
References ......Page 47
Problems ......Page 48
3.1 Introduction ......Page 49
3.2 Character Group ......Page 51
3.3 Duality ......Page 54
3.4 Chinese Remainder Theorem ......Page 56
3.5 Vector Space L(A) ......Page 60
Problems ......Page 61
4.2 Fourier Transform of T ......Page 63
4.3 Induced Fourier Transform ......Page 65
4.4 Periodic and Decimated Data ......Page 67
4.5 Periodization and Decimation ......Page 69
References ......Page 73
5.1 Introduction ......Page 75
5.2 Good-Thomas FFT ......Page 76
5.3 Abstract Cooley-Tukey FFT ......Page 77
References ......Page 81
6.1 Introduction ......Page 83
6.2 Examples ......Page 84
6.3 Prime Case ......Page 87
6.4.1 Square case ......Page 88
6.4.2 Rectangular case ......Page 93
6.5 General Square Case ......Page 96
6.6 General Rectangular Case ......Page 99
References ......Page 100
Problems ......Page 101
7.1 Automorphism Group ......Page 103
7.2 Dual of Lines ......Page 106
7.3 Planes ......Page 109
7 4 Duality ......Page 111
Problems ......Page 115
8.1 Introduction ......Page 117
8.2 General Structure ......Page 118
8.3 Periodizations ......Page 120
8.4.1 2-Dimensional p x p, p a prime ......Page 123
8.4.2 2-Dimensional p2 x p2, p a prime ......Page 125
8.4.4 2-Dimensional M = pq, p and q distinct primes ......Page 128
8.4.5 3-D RTA ......Page 130
8.5 RTA Permutations ......Page 132
Problems ......Page 135
9.1 Introduction ......Page 137
9.2 Rader Field Algorithm ......Page 138
9.3.2 Examples of finite fields ......Page 140
9.4 Fourier Transform of Finite Fields ......Page 141
9.4.1 Trace map ......Page 142
9.4 2 Evaluation map ......Page 144
9.5 Factorization of Core Matrices ......Page 145
9.6 Auslander-Feig-Winograd DFT ......Page 149
References ......Page 150
Problems ......Page 151
10.1 Introduction ......Page 153
10.2 Algorithms for RISC Architectures ......Page 154
10 2.1 Implementation on model I RISC ......Page 155
10.2.2 Implementation on model II RISC ......Page 159
10.3 Implementation on the IBM RS/6000 ......Page 161
10.4 Implementation on the Intel i860 ......Page 168
References ......Page 171
11.1 Introduction ......Page 173
11.2 Parallel Implementation of FFT ......Page 175
11.3 Parallel Implementation of the RTA ......Page 176
11.3.1 2-dimensional prime case ......Page 177
11.4 Parallel Implementation of FFT ......Page 178
11.5 Hybrid Algorithm ......Page 182
11.6 An Example Program on iPSC/860 ......Page 185
References ......Page 192
Index ......Page 197
