Fast Algorithms for Signal Processing

by Richard E. Blahut

• ISBN13: 9780521190497
• ISBN10: 0521190495
• Format: Hardcover
• Copyright: 2010-08-16
• Publisher: Cambridge University Press

Summary

Efficient signal processing algorithms are important for embedded and power-limited applications since, by reducing the number of computations, power consumption can be reduced significantly. Similarly, efficient algorithms are also critical to very large scale applications such as video processing and four-dimensional medical imaging. This self-contained guide, the only one of its kind, enables engineers to find the optimum fast algorithm for a specific application. It presents a broad range of computationally-efficient algorithms, describes their structure and implementation, and compares their relative strengths for given problems. All the necessary background mathematics is included and theorems are rigorously proved, so all the information needed to learn and apply the techniques is provided in one convenient guide. With this practical reference, researchers and practitioners in electrical engineering, applied mathematics, and computer science can reduce power dissipation for low-end applications of signal processing, and extend the reach of high-end applications.

Table of Contents

Preface	p. xi
Acknowledgments	p. xiii
Introduction	p. 1
Introduction to fast algorithms	p. 1
Applications of fast algorithms	p. 6
Number systems for computation	p. 8
Digital signal processing	p. 9
History of fast signal-processing algorithms	p. 17
Introduction to abstract algebra	p. 21
Groups	p. 21
Rings	p. 26
Fields	p. 30
Vector space	p. 34
Matrix algebra	p. 37
The integer ring	p. 44
Polynomial rings	p. 48
The Chinese remainder theorem	p. 58
Fast algorithms for the discrete Fourier transform	p. 68
The Cooley-Tukey fast Fourier transform	p. 68
Small-radix Cooley-Tukey algorithms	p. 72
The Good-Thomas fast Fourier transform	p. 80
The Goertzel algorithm	p. 83
The discrete cosine transform	p. 85
Fourier transforms computed by using convolutions	p. 91
The Rader-Winograd algorithm	p. 97
The Winograd small fast Fourier transform	p. 102
Fast algorithms based on doubling strategies	p. 115
Halving and doubling strategies	p. 115
Data Structures	p. 119
Fast algorithms for sorting	p. 120
Fast transposition	p. 122
Matrix multiplication	p. 124
Computation of trigonometric functions	p. 127
An accelerated euclidean algorithm for polynomials	p. 130
A recursive radix-two fast Fourier transform	p. 139
Fast algorithms for short convolutions	p. 145
Cyclic convolution and linear convolution	p. 145
The Cook-Toom algorithm	p. 148
Winograd short convolution algorithms	p. 155
Design of short linear convolution algorithms	p. 164
Polynomial products modulo a polynomial	p. 168
Design of short cyclic convolution algorithms	p. 171
Convolution in general fields and rings	p. 176
Complexity of convolution algorithms	p. 178
Architecture of filters and transforms	p. 194
Convolution by sections	p. 194
Algorithms for short filter sections	p. 199
Iterated filter sections	p. 202
Symmetric and skew-symmetric filters	p. 207
Decimating and interpolating filters	p. 213
Construction of transform computers	p. 216
Limited-range Fourier transforms	p. 221
Autocorrelation and crosscorrelation	p. 222
Fast algorithms for solving Toeplitz Systems	p. 231
The Levinson and Durbin algorithms	p. 231
The Trench algorithm	p. 239
Methods based on the euclidean algorithm	p. 245
The Berlekamp-Massey algorithm	p. 249
An accelerated Berlekamp-Massey algorithm	p. 255
Fast algorithms for trellis search	p. 262
Trellis and tree searching	p. 262
The Viterbi algorithm	p. 267
Sequential algorithms	p. 270
The Fano algorithm	p. 274
The stack algorithm	p. 278
The Bahl algorithm	p. 280
Numbers and fields	p. 286
Elementary number theory	p. 286
Fields based on the integer ring	p. 293
Fields based on polynomial rings	p. 296
Minimal polynomials and conjugates	p. 299
Cyclotomic polynomials	p. 300
Primitive elements	p. 304
Algebraic integers	p. 306
Computation in finite fields and rings	p. 311
Convolution in surrogate fields	p. 311
Fermat number transforms	p. 314
Mersenne number transforms	p. 317
Arithmetic in a modular integer ring	p. 320
Convolution algorithms in finite fields	p. 324
Fourier transform algorithms in finite fields	p. 328
Complex convolution in surrogate fields	p. 331
Integer ring transforms	p. 336
Chevillat number transforms	p. 339
The Preparata-Sarwate algorithm	p. 339
Fast algorithms and multidimensional convolutions	p. 345
Nested convolution algorithms	p. 345
The Agarwal-Cooley convolution algorithm	p. 350
Splitting algorithms	p. 357
Iterated algorithms	p. 362
Polynomial representation of extension fields	p. 368
Convolution with polynomial transforms	p. 371
The Nussbaumer polynomial transforms	p. 372
Fast convolution of polynomials	p. 376
Fast algorithms and multidimensional transforms	p. 384
Small-radix Cooley-Tukey algorithms	p. 384
The two-dimensional discrete cosine transform	p. 389
Nested transform algorithms	p. 391
The Winograd large fast Fourier transform	p. 395
The Johnson-Burrus fast Fourier transform	p. 399
Splitting algorithms	p. 403
An improved Winograd fast Fourier transform	p. 410
The Nussbaumer-Quandalle permutation algorithm	p. 411
A collection of cyclic convolution algorithms	p. 427
A collection of Winograd small FFT algorithms	p. 435
Bibliography	p. 442
Index	p. 449
Table of Contents provided by Ingram. All Rights Reserved.