Fast Algorithms for Signal Processing

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 13
Acknowledgments......Page 15
1.1 Introduction to fast algorithms......Page 17
1.2 Applications of fast algorithms......Page 22
1.3 Number systems for computation......Page 24
1.4 Digital signal processing......Page 25
1.5 History of fast signal-processing algorithms......Page 33
Problems for Chapter 1......Page 34
Notes for Chapter 1......Page 36
2.1 Groups......Page 37
2.2 Rings......Page 42
2.3 Fields......Page 46
2.4 Vector space......Page 50
2.5 Matrix algebra......Page 53
2.6 The integer ring......Page 60
2.7 Polynomial rings......Page 64
2.8 The Chinese remainder theorem......Page 74
Problems for Chapter 2......Page 79
Notes for Chapter 2......Page 83
3.1 The Cooley-Tukey fast Fourier transform......Page 84
3.2 Small-radix Cooley-Tukey algorithms......Page 88
3.3 The Good-Thomas fast Fourier transform......Page 96
3.4 The Goertzel algorithm......Page 99
3.5 The discrete cosine transform......Page 101
3.6 Fourier transforms computed by using convolutions......Page 107
3.7 The Rader-Winograd algorithm......Page 113
3.8 The Winograd small fast Fourier transform......Page 118
Problems for Chapter 3......Page 128
Notes for Chapter 3......Page 130
4.1 Halving and doubling strategies......Page 131
4.2 Data structures......Page 135
4.3 Fast algorithms for sorting......Page 136
4.4 Fast transposition......Page 138
4.5 Matrix multiplication......Page 140
4.6 Computation of trigonometric functions......Page 143
4.7 An accelerated euclidean algorithm for polynomials......Page 146
4.8 A recursive radix-two fast Fourier transform......Page 155
Problems for Chapter 4......Page 159
Notes for Chapter 4......Page 160
5.1 Cyclic convolution and linear convolution......Page 161
5.2 The Cook-Toom algorithm......Page 164
5.3 Winograd short convolution algorithms......Page 171
5.4 Design of short linear convolution algorithms......Page 180
5.5 Polynomial products modulo a polynomial......Page 184
5.6 Design of short cyclic convolution algorithms......Page 187
5.7 Convolution in general fields and rings......Page 192
5.8 Complexity of convolution algorithms......Page 194
Problems for Chapter 5......Page 204
Notes for Chapter 5......Page 209
6.1 Convolution by sections......Page 210
6.2 Algorithms for short filter sections......Page 215
6.3 Iterated filter sections......Page 218
6.4 Symmetric and skew-symmetric filters......Page 223
6.5 Decimating and interpolating filters......Page 229
6.6 Construction of transform computers......Page 232
6.7 Limited-range Fourier transforms......Page 237
6.8 Autocorrelation and crosscorrelation......Page 238
Problems for Chapter 6......Page 244
Notes for Chapter 6......Page 245
7.1 The Levinson and Durbin algorithms......Page 247
7.2 The Trench algorithm......Page 255
7.3 Methods based on the euclidean algorithm......Page 261
7.4 The Berlekamp-Massey algorithm......Page 265
7.5 An accelerated Berlekamp-Massey algorithm......Page 271
Problems for Chapter 7......Page 276
Notes for Chapter 7......Page 277
8.1 Trellis and tree searching......Page 278
8.2 The Viterbi algorithm......Page 283
8.3 Sequential algorithms......Page 286
8.4 The Fano algorithm......Page 290
8.5 The stack algorithm......Page 294
8.6 The Bahl algorithm......Page 296
Notes for Chapter 8......Page 300
9.1 Elementary number theory......Page 302
9.2 Fields based on the integer ring......Page 309
9.3 Fields based on polynomial rings......Page 312
9.4 Minimal polynomials and conjugates......Page 315
9.5 Cyclotomic polynomials......Page 316
9.6 Primitive elements......Page 320
9.7 Algebraic integers......Page 322
Problems for Chapter 9......Page 324
Notes for Chapter 9......Page 325
10.1 Convolution in surrogate fields......Page 327
10.2 Fermat number transforms......Page 330
10.3 Mersenne number transforms......Page 333
10.4 Arithmetic in a modular integer ring......Page 336
10.5 Convolution algorithms in finite fields......Page 340
10.6 Fourier transform algorithms in finite fields......Page 344
10.7 Complex convolution in surrogate fields......Page 347
10.8 Integer ring transforms......Page 352
10.10 The Preparata-Sarwate algorithm......Page 355
Problems for Chapter 10......Page 358
Notes for Chapter 10......Page 359
11.1 Nested convolution algorithms......Page 361
11.2 The Agarwal-Cooley convolution algorithm......Page 366
11.3 Splitting algorithms......Page 373
11.4 Iterated algorithms......Page 378
11.5 Polynomial representation of extension fields......Page 384
11.6 Convolution with polynomial transforms......Page 387
11.7 The Nussbaumer polynomial transforms......Page 388
11.8 Fast convolution of polynomials......Page 392
Problems for Chapter 11......Page 396
Notes for Chapter 11......Page 398
12.1 Small-radix Cooley-Tukey algorithms......Page 400
12.2 The two-dimensional discrete cosine transform......Page 405
12.3 Nested transform algorithms......Page 407
12.4 The Winograd large fast Fourier transform......Page 411
12.5 The Johnson-Burrus fast Fourier transform......Page 415
12.6 Splitting algorithms......Page 419
12.7 An improved Winograd fast Fourier transform......Page 426
12.8 The Nussbaumer-Quandalle permutation algorithm......Page 427
Problems for Chapter 12......Page 439
Notes for Chapter 12......Page 441
Appendix A: A collection of cyclic convolution algorithms......Page 443
Appendix B: A collection of Winograd small FFT algorithms......Page 451
Bibliography......Page 458
Index......Page 465