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

✍ Scribed by Richard Tolimieri, Myoung An, Chao Lu

• Publisher: Springer
• Year: 1997
• Tongue: English
• Leaves: 285
• 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 7
Contents......Page 11
1.1 Introduction......Page 15
1.2 The Ring of Integers......Page 16
1.3 The Ring Z/N......Page 19
1.4 Chinese Remainder Theorem (CRT)......Page 21
1.5 Unit Groups......Page 25
1.6 Polynomial Rings......Page 27
1.7 Field Extension......Page 31
1.8 The Ring F[x]/f(x)......Page 32
1.9 CRT for Polynomial Rings......Page 35
Problems......Page 37
2.1 Introduction......Page 41
2.2 Tensor Product......Page 42
2.3 Stride Permutations......Page 47
2.4 Multidimensional Tensor Products......Page 54
2.5 Vector Implementation......Page 58
2.6 Parallel Implementation......Page 64
Problems......Page 67
3.1 Introduction......Page 69
3.2 Basic Properties of FT Matrix......Page 70
3.3 An Example of an FT Algorithm......Page 71
3.4 Cooley-Tukey FFT for N = 2M......Page 73
3.5 Twiddle Factors......Page 75
3.6 FT Factors......Page 77
3.7 Variants of the Cooley-Tukey FFT......Page 78
3.8 Cooley-Tukey FFT for N = ML......Page 80
3.9 Arithmetic Cost......Page 82
References......Page 83
Problems......Page 84
4.1 Introduction......Page 85
4.2 Radix-2 Cooley-Tukey FFT Algorithm......Page 86
4.3 Pease FFT Algorithm......Page 90
4.4 Auto-Sorting FT Algorithm......Page 93
4.5 Mixed Radix Cooley-Tukey FFT......Page 95
4.6 Mixed Radix Agarwal-Cooley FFT......Page 98
4.7 Mixed Radix Auto-Sorting FFT......Page 99
4.8 Summary......Page 101
References......Page 103
Problems......Page 104
5.1 Introduction......Page 105
5.2 Indexing by the CRT......Page 106
5.3 An Example, N = 15......Page 107
5.4 Good-Thomas PFA for the General Case......Page 110
5.5 Self-Sorting PFA......Page 112
References......Page 113
Problems......Page 114
6.1 Definitions......Page 115
6.2 Convolution Theorem......Page 121
6.3 Cook-Toom Algorithm......Page 125
6.4 Winograd Small Convolution Algorithm......Page 133
6.5 Linear and Cyclic Convolutions......Page 139
6.6 Digital Filters......Page 145
References......Page 147
Problems......Page 148
7.1 Two-Dimensional Cyclic Convolution......Page 151
7.2 Agarwal-Cooley Algorithm......Page 156
Problems......Page 159
8 Multiplicative Fourier Transform Algorithm......Page 161
References......Page 167
9.1 The Field Z/p......Page 169
9.2 The Fundamental Factorization......Page 171
9.3 Rader's Algorithm......Page 176
9.4 Reducing Additions......Page 177
9.5 Winograd Small FT Algorithm......Page 181
9.6 Summary......Page 183
Problems......Page 185
10.1 Basic Algebra......Page 187
10.2 Transform Size: 15......Page 189
10.3 Fundamental Factorization: 15......Page 190
10.4 Variants: 15......Page 192
10.5 Transform Size: pq......Page 195
10.6 Fundamental Factorization: pq......Page 197
10.7 Variants......Page 199
10.8 Summary......Page 203
References......Page 204
Problems......Page 205
11.2 Main Theorem......Page 207
11.3 Product of Three Distinct Primes......Page 210
11.4 Variants......Page 211
11.6 Transform Size: 4p, p odd prime......Page 212
11.7 Transform Size: 60......Page 213
Problems......Page 216
12.2 An Example: 9......Page 217
12.3 The General Case: p^2......Page 220
12.4 An Example: 3^3......Page 226
References......Page 228
Problems......Page 229
13.1 Introduction......Page 231
13.2 Periodic and Decimated Data......Page 234
13.3 FT of Periodic and Decimated Data......Page 237
13.4 The Ring Z/p^m......Page 239
Problems......Page 241
14.1 Introduction......Page 243
14.2.1 Periodic Multiplicative Characters......Page 246
14.2.2 Periodization and Decimation......Page 249
14.3 F(p) of Multiplicative Characters......Page 251
14.4.1 Primitive Multiplicative Characters......Page 253
14.4.2 Nonprimitive Multiplicative Characters......Page 254
14.5 Orthogonal Basis Diagonalizing F(p)......Page 256
14.6.1 Orthogonal Basis of W......Page 259
14.6.2 Orthogonal Diagonalizing Basis......Page 260
References......Page 261
Problems......Page 262
15 Rationality......Page 263
15.1 An Example: 7......Page 264
15.2 Prime Case......Page 266
15.3 An Example: 3^2......Page 268
15.4 Transform Size: p^2......Page 270
15.6 Polynomial Product Modulo a Polynomial......Page 274
15.7 An Example: 3^3......Page 276
References......Page 278
Index......Page 279