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

Cover......Page 1
Series......Page 2
Title page......Page 3
Copyright page......Page 4
Preface......Page 5
Contents......Page 9
1.1 Introduction......Page 13
1.2 The Ring of Integers......Page 14
1.3 The Ring $\\mathfrak{Z}/\\mathfrak{N}$......Page 17
1.4 Chinese Remainder Theorem (CRT)......Page 19
1.5 Unit Groups......Page 23
1.6 Polynomial Rings......Page 25
1.7 Field Extension......Page 29
1.8 The Ring $F\\[x\\]/f(x)$......Page 30
1.9 CRT for Polynomial Rings......Page 33
Problems......Page 35
2.1 Introduction......Page 39
2.2 Tensor Product......Page 40
2.3 Stride Permutations......Page 45
2.4 Multidimensional Tensor Products......Page 52
2.5 Vector Implementation......Page 56
2.6 Parallel Implementation......Page 62
Problems......Page 65
3.1 Introduction......Page 67
3.2 Basic Properties of FT Matrix......Page 68
3.3 An Example of an FT Algorithm......Page 69
3.4 Cooley-Tukey FFT for $N = 2M$......Page 71
3.5 Twiddle Factors......Page 73
3.6 FT Factors......Page 75
3.7 Variants of the Cooley-Tukey FFT......Page 76
3.8 Cooley-Tukey FFT for $N = ML$......Page 78
3.9 Arithmetic Cost......Page 80
References......Page 81
Problems......Page 82
4.1 Introduction......Page 83
4.2 Radix-2 Cooley-Tukey FFT Algorithm......Page 84
4.3 Pease FFT Algorithm......Page 88
4.4 Auto-Sorting FT Algorithm......Page 91
4.5 Mixed Radix Cooley-Tukey FFT......Page 93
4.6 Mixed Radix Agarwal-Cooley FFT......Page 96
4.7 Mixed Radix Auto-Sorting FFT......Page 97
4.8 Summary......Page 99
References......Page 101
Problems......Page 102
5.1 Introduction......Page 103
5.2 Indexing by the CRT......Page 104
5.3 An Example, $N = 15$......Page 105
5.4 Good-Thomas PFA for the General Case......Page 108
5.5 Self-Sorting PFA......Page 110
References......Page 111
Problems......Page 112
6.1 Definitions......Page 113
6.2 Convolution Theorem......Page 119
6.3 Cook-Toom Algorithm......Page 123
6.4 Winograd Small Convolution Algorithm......Page 131
6.5 Linear and Cyclic Convolutions......Page 137
6.6 Digital Filters......Page 143
References......Page 145
Problems......Page 146
7.1 Two-Dimensional Cyclic Convolution......Page 149
7.2 Agarwai-Cooley Algorithm......Page 154
Problems......Page 157
8 Multiplicative Fourier Transform Algorithm......Page 159
References......Page 165
9.1 The Field $Z/p$......Page 167
9.2 The Fundamental Factorization......Page 169
9.3 Rader\'s Algorithm......Page 174
9.4 Reducing Additions......Page 175
9.5 Winograd Small FT Algorithm......Page 179
9.6 Summary......Page 181
Problems......Page 183
10.1 Basic Algebra......Page 185
10.2 Transform Size: 15......Page 187
10.3 Fundamental Factorization: 15......Page 188
10.4 Variants: 15......Page 190
10.5 Transform Size: $pq$......Page 193
10.6 Fundamental Factorization: $pq$......Page 195
10.7 Variants......Page 197
10.8 Summary......Page 201
References......Page 202
Problems......Page 203
11.2 Main Theorem......Page 205
11.3 Product of Three Distinct Primes......Page 208
11.4 Variants......Page 209
11.6 Transform Size: $4p$, $p$ odd prime......Page 210
11.7 Transform Size: 60......Page 211
Problems......Page 214
12.2 An Example: 9......Page 215
12.3 The General Case: $p^2$......Page 218
12.4 An Example: $3^3$......Page 224
References......Page 226
Problems......Page 227
13.1 Introduction......Page 229
13.2 Periodic and Decimated Data......Page 232
13.3 FT of Periodic and Decimated Data......Page 235
13.4 The Ring $\\mathfrak{Z}/p^m$......Page 237
Problems......Page 239
14.1 Introduction......Page 241
14.2.1 Periodic Multiplicative Characters......Page 244
14.2.2 Periodization and Decimation......Page 247
14.3 $F(p)$ of Multiplicative Characters......Page 249
14.4.1 Primitive Multiplicative Characters......Page 251
14.4.2 Nonprimitive Multiplicative Characters......Page 252
14.5 Orthogonal Basis Diagonalizing $F(p)$......Page 254
14.6.1 Orthogonal Basis of $W$......Page 257
14.6.2 Orthogonal Diagonalizing Basis......Page 258
References......Page 259
Problems......Page 260
15 Rationality......Page 261
15.1 An Example: 7......Page 262
15.2 Prime Case......Page 264
15.3 An Example: $3^2$......Page 266
15.4 Transform Size: $p^2$......Page 268
15.6 Polynomial Product Modulo a Polynomial......Page 272
15.7 An Example: 33......Page 274
References......Page 276
Index......Page 277