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

✍ Scribed by Richard Tolimieri, Myoung An, Chao Lu

• Publisher: Springer
• Year: 1997
• Tongue: English
• Leaves: 280
• Edition: 2nd
• Category: Library

✦ Synopsis

This graduate-level text provides a language for understanding, unifying, and implementing a wide variety of algorithms for digital signal processing - in particular, to provide rules and procedures that can simplify or even automate the task of writing code for the newest parallel and vector machines. It thus bridges the gap between digital signal processing algorithms and their implementation on a variety of computing platforms. The mathematical concept of tensor product is a recurring theme throughout the book, since these formulations highlight the data flow, which is especially important on supercomputers. Because of their importance in many applications, much of the discussion centres on algorithms related to the finite Fourier transform and to multiplicative FFT algorithms.

✦ Table of Contents

Algorithms for Discrete Fourier Transform and Convolution, 2nd Ed......Page 1
Preface......Page 6
Contents......Page 10
1.1 Introduction......Page 14
1.2 The Ring of Integers......Page 15
1.3 The Ring Z/N......Page 18
1.4 Chinese Remainder Theorem (CRT)......Page 20
1.5 Unit Groups......Page 24
1.6 Polynomial Rings......Page 26
1.7 Field Extension......Page 30
1.8 The Ring F[x]/f(x)......Page 31
1.9 CRT for Polynomial Rings......Page 34
Problems......Page 36
2.1 Introduction......Page 40
2.2 Tensor Product......Page 41
2.3 Stride Permutations......Page 46
2.4 Multidimensional Tensor Products......Page 53
2.5 Vector Implementation......Page 57
2.6 Parallel Implementation......Page 63
Problems......Page 66
3.1 Introduction......Page 68
3.2 Basic Properties of FT Matrix......Page 69
3.3 An Example of an FT Algorithm......Page 70
3.4 Cooley-Tukey FFT for N = 2M......Page 72
3.5 Twiddle Factors......Page 74
3.6 FT Factors......Page 76
3.7 Variants of the Cooley-Tukey FFT......Page 77
3.8 Cooley-Tukey FFT for N = ML......Page 79
3.9 Arithmetic Cost......Page 81
References......Page 82
Problems......Page 83
4.1 Introduction......Page 84
4.2 Radix-2 Cooley-Tukey FFT Algorithm......Page 85
4.3 Pease FFT Algorithm......Page 89
4.4 Auto-Sorting FT Algorithm......Page 92
4.5 Mixed Radix Cooley-Tukey FFT......Page 94
4.6 Mixed Radix Agarwal-Cooley FFT......Page 97
4.7 Mixed Radix Auto-Sorting FFT......Page 98
4.8 Summary......Page 100
References......Page 102
Problems......Page 103
5.1 Introduction......Page 104
5.2 Indexing by the CRT......Page 105
5.3 An Example, N = 15......Page 106
5.4 Good-Thomas PFA for the General Case......Page 109
5.5 Self-Sorting PFA......Page 111
References......Page 112
Problems......Page 113
6.1 Definitions......Page 114
6.2 Convolution Theorem......Page 120
6.3 Cook-Toom Algorithm......Page 124
6.4 Winograd Small Convolution Algorithm......Page 132
6.5 Linear and Cyclic Convolutions......Page 138
6.6 Digital Filters......Page 144
References......Page 146
Problems......Page 147
7.1 Two-Dimensional Cyclic Convolution......Page 150
7.2 Agarwal-Cooley Algorithm......Page 155
Problems......Page 158
8 Multiplicative Fourier Transform Algorithm......Page 160
References......Page 166
9.1 The Field Z/p......Page 168
9.2 The Fundamental Factorization......Page 170
9.3 Rader's Algorithm......Page 175
9.4 Reducing Additions......Page 176
9.5 Winograd Small FT Algorithm......Page 180
9.6 Summary......Page 182
Problems......Page 184
10.1 Basic Algebra......Page 186
10.2 Transform Size: 15......Page 188
10.3 Fundamental Factorization: 15......Page 189
10.4 Variants: 15......Page 191
10.5 Transform Size: pq......Page 194
10.6 Fundamental Factorization: pq......Page 196
10.7 Variants......Page 198
10.8 Summary......Page 202
References......Page 203
Problems......Page 204
11.2 Main Theorem......Page 206
11.3 Product of Three Distinct Primes......Page 209
11.4 Variants......Page 210
11.6 Transform Size: 4p, p odd prime......Page 211
11.7 Transform Size: 60......Page 212
Problems......Page 215
12.2 An Example: 9......Page 216
12.3 The General Case: p^2......Page 219
12.4 An Example: 3^3......Page 225
References......Page 227
Problems......Page 228
13.1 Introduction......Page 230
13.2 Periodic and Decimated Data......Page 233
13.3 FT of Periodic and Decimated Data......Page 236
13.4 The Ring Z/p^m......Page 238
Problems......Page 240
14.1 Introduction......Page 242
14.2.1 Periodic Multiplicative Characters......Page 245
14.2.2 Periodization and Decimation......Page 248
14.3 F(p) of Multiplicative Characters......Page 250
14.4.1 Primitive Multiplicative Characters......Page 252
14.4.2 Nonprimitive Multiplicative Characters......Page 253
14.5 Orthogonal Basis Diagonalizing F(p)......Page 255
14.6.1 Orthogonal Basis of W......Page 258
14.6.2 Orthogonal Diagonalizing Basis......Page 259
References......Page 260
Problems......Page 261
15 Rationality......Page 262
15.1 An Example: 7......Page 263
15.2 Prime Case......Page 265
15.3 An Example: 3^2......Page 267
15.4 Transform Size: p^2......Page 269
15.6 Polynomial Product Modulo a Polynomial......Page 273
15.7 An Example: 3^3......Page 275
References......Page 277
Index......Page 278