3
$\begingroup$

The development of Fast Fourier transform is attributed to Cooley & Tukey, both have written a lot about it is historical development. Both Cooley and Tukey call it a re-discovery rather. However, I am searching for early publications which showed how people made the conversions in discrete frequency axis from time to frequency and vice versa.

For example, if we have $N$ data points, the FFT output also consists of $N$ data points. The specific question is:

Who came up with the equation or the proof that the frequency spacing in discrete Fourier transform is $= k/T$, where $k =0,1,2,3,..., N-1$ and $T$ is the total duration of time for which the signal was acquired? Further searching of older literature I found Cooley's paper of 1967 Application of the fast Fourier transform to computation of Fourier integrals, Fourier series, and convolution integrals. In this paper Cooley shows a theorem as shown in the snippet of his original 1967 paper.

Does anyone know who originated this theorem for discrete data set or was it very well known before the 1960s? I would appreciate a earlier reference, if it exists about the following theorem. Thanks.

$\endgroup$
5
$\begingroup$

I quote from Gauss and the history of the fast Fourier transform (1985) (DFT = Discrete Fourier Transform):

Alexis-Claude Clairaut (1713-1765) published in 1754 [1] what we currently believe to be the earliest explicit formula for the DFT (the computation of series coefficients from equally spaced samples of the function). (...)

Clairaut and later Lagrange were concerned with orbital mechanics and the problem of determining from a finite set of observations the details of an orbit. Consequently, their data was periodic and they used an interpolation approach to orbit determination: in modern terminology and notation, an even periodic function $f(x)$ having a normalized period of one is represented as a finite trigonometric series by $$f(x)=\sum_{k=0}^{N-1} a_k \cos 2\pi kx,$$ and the problem is to find the coefficients $a_k$ from the $N$ values of $f(x)$ for values $x_n=n/N$ with $n=0,1,\ldots, N-1$. By forcing $f(x)$ to equal the observed values at the abscissas $\{x_n\}$, one can easily show that the coefficients $\{a_k\}$ are given by the cosine DFT of the observed values of $f(x)$.

[1] A.-C. Clairaut, Mémoire sur l'Orbite Apparente du Soleil Autour de la Terre, Mémoires de Mathématique et de Physique de l'Académie Royale des Sciences, no. 9, pp. 801-870, 1754.

$\endgroup$
  • 1
    $\begingroup$ Lagrange’s version is in (1759): see the equations at the bottom of p. 80, their solution at the top of p. 89. FFT is Gauss’s algorithm to compute the pre-existing DFT. $\endgroup$ – Francois Ziegler Jul 10 '19 at 7:53
  • $\begingroup$ @FrancoisZiegler, I believe this x-scaling should be valid for any Fourier transform pair or this theorem is valid any transform pair for equally spaced data? $\endgroup$ – M. Farooq Jul 10 '19 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.