Fast algorithms for signal processing

"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"-- Read more... Content: Cover -- Contents -- Introduction -- 1.1 Introduction to fast algorithms -- 1.2 Applications of fast algorithms -- 1.3 Number systems for computation -- 1.4 Digital signal processing -- 1.5 History of fast signal-processing algorithms -- 2. Introduction to abstract algebra -- 2.1 Groups -- 2.2 Rings -- 2.3 Fields -- 2.4 Vector space -- 2.5 Matrix algebra -- 2.6 The integer ring -- 2.7 Polynomial rings -- 2.8 The Chinese remainder theorem -- 3. Fast algorithms for the discrete Fourier transform -- 3.1 The Cooley8211;Tukey fast Fourier transform -- 3.2 Small-radix Cooley8211;Tukey algorithms -- 3.3 The Good8211;Thomas fast Fourier transform -- 3.4 The Goertzel algorithm -- 3.5 The discrete cosine transform -- 3.6 Fourier transforms computed by using convolutions -- 3.7 The Rader8211;Winograd algorithm -- 3.8 The Winograd small fast Fourier transform -- 4. Fast algorithms based on doubling strategies -- 4.1 Halving and doubling strategies -- 4.2 Data structures -- 4.3 Fast algorithms for sorting -- 4.4 Fast transposition -- 4.5 Matrix multiplication -- 4.6 Computation of trigonometric functions -- 4.7 An accelerated euclidean algorithm for polynomials -- 4.8 A recursive radix-two fast Fourier transform -- 5. Fast algorithms for short convolutions -- 5.1 Cyclic convolution and linear convolution -- 5.2 The Cook8211;Toom algorithm -- 5.3 Winograd short convolution algorithms -- 5.4 Design of short linear convolution algorithms -- 5.5 Polynomial products modulo a polynomial -- 5.6 Design of short cyclic convolution algorithms -- 5.7 Convolution in general fields and rings -- 5.8 Complexity of convolution algorithms -- 6. Architecture of filters and transforms -- 6.1 Convolution by sections -- 6.2 Algorithms for short filter sections -- 6.3 Iterated filter sections -- 6.4 Symmetric and skew-symmetric filters -- 6.5 Decimating and interpolating filters -- 6.6 Construction of transform computers -- 6.7 Limited-range Fourier transforms -- 6.8 Autocorrelation and crosscorrelation -- 7. Fast algorithms for solving Toeplitz systems -- 7.1 The Levinson and Durbin algorithms -- 7.2 The Trench algorithm -- 7.3 Methods based on the euclidean algorithm -- 7.4 The Berlekamp8211;Massey algorithm -- 7.5 An accelerated Berlekamp8211;Massey algorithm -- 8. Fast algorithms for trellis search -- 8.1 Trellis and tree searching -- 8.2 The Viterbi algorithm -- 8.3 Sequential algorithms -- 8.4 The Fano algorithm -- 8.5 The stack algorithm -- 8.6 The Bahl algorithm -- 9. Numbers and fields -- 9.1 Elementary number theory -- 9.2 Fields based on the integer ring -- 9.3 Fields based on polynomial rings -- 9.4 Minimal polynomials and conjugates -- 9.5 Cyclotomic polynomials -- 9.6 Primitive elements -- 9.7 Algebraic integers -- 10. Computation in finite fields and rings -- 10.1 Convolution in surrogate fields -- 10.2 Fermat number transforms -- 10.3 Mersenne number transforms -- 10.4 Arithmetic in a modular integer ring -- 10.5 Convolution algorithms in finite fields -- 10.6 Fourier transform algorithms in finite fields -- 10.7 Complex convolution in surrogate fields -- 10.8 Integer ring transforms -- 10.9 Chevillat number transforms -- 10.10 The Preparata8211;Sarwate algorithm -- 11. Fast algorithms and multidimensional convolutions -- 11.1 Nested convoluti. Abstract: "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" "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"-- Provided by publisher Machine generated contents note: 1. Introduction; 2. Introduction to abstract algebra; 3. Fast algorithms for the discrete Fourier transform; 4. Fast algorithms based on doubling strategies; 5. Fast algorithms for short convolutions; 6. Architecture of filters and transforms; 7. Fast algorithms for solving Toeplitz systems; 8. Fast algorithms for trellis search; 9. Numbers and fields; 10. Computation in finite fields and rings; 11. Fast algorithms and multidimensional convolutions; 12. Fast algorithms and multidimensional transforms; Appendices: A. A collection of cyclic convolution algorithms; B. A collection of Winograd small FFT algorithms.