DISCRETE FINITE FOURIER TRANSFORMS: A TUTORIAL APPROACH.
NAVAL RESEARCH LAB WASHINGTON D C
Pagination or Media Count:
A discrete, finite time series of N points f sub n n 0, 1, 2,..., N - 1, often arises, for example, in the sampling of continuous data. This time series can be expressed as the finite series f sub n Summation, k 0 to k N - 1, of F sub k e to the power 2 pi i k nN, n 0, 1, 2,..., N - 1, where the coefficients F sub k, to be interpreted as frequency values, are given by F sub k 1N Summation, n 0 to n N - 1, of f sub n e to the power -2 pi i k nN, k 0, 1, 2,..., N - 1. Experimental errors inherent in f sub n will, of course, be reflected in F sub k. Given the original time series f sub n, however, it is exactly i.e., without approximation represented by F sub k at the N points of interest. These formulas are derived from basic principles, and their relationship to digital analysis of data sampled from continuous signals is discussed. In particular, the efficient use of the recently popular algorithms for rapid machine computation of Fourier transforms is explained. Although the results obtained are for the most part well known in the literature, it is felt that the importance of these transforms warrants a complete and notationally consistent exposition. Author
- Numerical Mathematics