INPUT OUTPUT

**Problem:**
The discrete Fourier transform *H* of *h*,
*H_m = \sum_{k=0}^{n-1} h_k e^{2 \pi i k m / n}*, *0 \leq m \leq n-1*.

**Excerpt from**
The Algorithm Design Manual:
Although computer scientists tend to be relatively unfamiliar with Fourier transforms, electrical engineers
and signal processors eat them for breakfast. Functionally, Fourier transforms provide a way to convert
samples of a standard time-series into the ``frequency domain''. This provides a ``dual'' representation of
the function, in which certain operations become easier than in the time domain. Applications of Fourier
transforms include:

*Filtering:*-- Taking the Fourier transform of a function is equivalent to representing it as the sum of sine functions. By eliminating undesirable high- and/or low-frequency components (i.e. dropping some of the sine functions) and taking an inverse Fourier transform to get us back into the time domain, we can filter an image to remove noise and other artifacts. For example, the sharp spike in the figure above describes the period of a single sine function that closely models the input data.*Image Compression*-- A smoothed, filtered image contains less information than a noisy image, while retaining a similar appearance. Thus encoding the smoothed image will require fewer bits to represent than the original image. By eliminating the coefficients of sine functions that contribute relatively little to the image, we can further reduce the size of the image, at little cost in image fidelity.*Convolution and Deconvolution*-- Fourier transforms can be used to efficiently compute convolutions of two sequences. A convolution is the pairwise product of elements from two different sequences, such as in multiplying two*n*-variable polynomials*f*and*g*or multiplying two long integers. Implementing the product directly takes*O(n*, while^{2})*O(n \lg n)*suffices using the fast Fourier transform. Another example comes from image processing. \index{scanner, OCR} Because a scanner measures the darkness of an image patch instead of a single point, the scanned input is always blurred. A reconstruction of the original signal can be obtained by deconvoluting the input signal with a Gaussian point-spread function.

Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky | A Primer on Wavelets and Their Scientific Applications by J. Walker | The Fourier Transform and its Applications by R. Bracewell |

Numerical Recipes in C by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery | The Fast Fourier Transform and Its Applications by E. Oran Brigham |

This page last modified on 2008-07-10 . www.algorist.com