Number theory in digital signal processing.

*(English)*Zbl 0553.10001
Prentice-Hall Signal Processing Series. M.I.T. Lincoln Laboratory. Englewood Cliffs, New Jersey: Prentice-Hall, Inc. xii, 276 p. (1979).

The finite Fourier transform which is usually called the discrete Fourier transform (DFT) in electrical engineering sciences is defined according to the prescription
\[
(x_ j)_{0\leq j\leq N-1}\rightsquigarrow (\sum_{0\leq j\leq N-1}\zeta^{kj} x_ j)_{0\leq k\leq N-1}
\]
where \(N\geq 1\) is the block length and \(\zeta =e^{2\pi i/N}\) denotes the primitive \(N\)th root of unity. It forms a valuable tool in many areas from digital signal processing to radar technology and partial differential equations. There is strong incentive for computing the transform quickly and, after two decades of active research in the field of complexity theory, the minimum number of essential multiplications required for the task is known. At present, various algorithms are available which use precisely this number. It does not follow that, in the end, these will be the most desirable techniques, but they are certainly of interest in their own right. Major credit for this work seems to belong to I. J. Good, C. M. Rader, and S. Winograd. This story, and more, is told in an impressive way in the book by collecting a series of important original papers scattered about the literature.

At the heart of these methods lie Winograd’s algorithms for \(N\) point DFT’s, where the block length \(N\) is a small prime. He uses a quick way of forming the product of two polynomials modulo a third one, and that theory, in turn, uses the Chinese remainder theorem. Winograd’s algorithms, for small primes, are just the eigenvalue-eigenvector decomposition of the associated circulant matrices, but written economically and in real arithmetic.

Because digital signal processing is enjoying an explosive growth, the development did not stop since the book under review has become available in 1979. For instance, the survey article by L. Auslander and R. Tolimieri [Is computing with the finite Fourier transform pure or applied mathematics ? Bull. Am. Math. Soc., New Ser. 1, 847–897 (1979; Zbl 0475.42014)] links the DFT with a variety of topics in pure and applied mathematics, and yet no mention is made of the circulants lurking in the background. For a detailed and updated exposition of fast algorithms for digital signal processing, see the recent monograph by R. E. Blahut [Fast algorithms for digital signal processing (Addison-Wesley, Reading, MA 1985; Zbl 0579.94001)]. Also see the reviewer’s survey article [Analog radar signal design and digital signal processing - A Heisenberg nilpotent Lie group approach, in ”Lie methods in optics, Proc. CIFMO-CIO Workshop on January 7-10, 1985, León, México.” (J. Sánchez-Mondragón and K. B. Wolf, editors) Lect. Notes Phys. 250, 1–27 (1986: Zbl 0594.43001)] and M. R. Schroeder’s stimulating monograph [Number theory in science and communication (1984; Zbl 0542.10001)].

[A Russian translation has been published by Radio i Svyaz’ (Moscow) (1983).]

At the heart of these methods lie Winograd’s algorithms for \(N\) point DFT’s, where the block length \(N\) is a small prime. He uses a quick way of forming the product of two polynomials modulo a third one, and that theory, in turn, uses the Chinese remainder theorem. Winograd’s algorithms, for small primes, are just the eigenvalue-eigenvector decomposition of the associated circulant matrices, but written economically and in real arithmetic.

Because digital signal processing is enjoying an explosive growth, the development did not stop since the book under review has become available in 1979. For instance, the survey article by L. Auslander and R. Tolimieri [Is computing with the finite Fourier transform pure or applied mathematics ? Bull. Am. Math. Soc., New Ser. 1, 847–897 (1979; Zbl 0475.42014)] links the DFT with a variety of topics in pure and applied mathematics, and yet no mention is made of the circulants lurking in the background. For a detailed and updated exposition of fast algorithms for digital signal processing, see the recent monograph by R. E. Blahut [Fast algorithms for digital signal processing (Addison-Wesley, Reading, MA 1985; Zbl 0579.94001)]. Also see the reviewer’s survey article [Analog radar signal design and digital signal processing - A Heisenberg nilpotent Lie group approach, in ”Lie methods in optics, Proc. CIFMO-CIO Workshop on January 7-10, 1985, León, México.” (J. Sánchez-Mondragón and K. B. Wolf, editors) Lect. Notes Phys. 250, 1–27 (1986: Zbl 0594.43001)] and M. R. Schroeder’s stimulating monograph [Number theory in science and communication (1984; Zbl 0542.10001)].

[A Russian translation has been published by Radio i Svyaz’ (Moscow) (1983).]

Reviewer: Walter Schempp (Siegen)

##### MSC:

11-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory |

65-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to numerical analysis |

94-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory |

11A07 | Congruences; primitive roots; residue systems |

11T22 | Cyclotomy |

94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |

68W99 | Algorithms in computer science |

65Yxx | Computer aspects of numerical algorithms |

65T40 | Numerical methods for trigonometric approximation and interpolation |

42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |