Proceedings of the IEEE · 1968 · 538 citations · 2 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationDigital Signal ProcessingFourier AnalysisNumber-theoretic AlgorithmsSignal ProcessingCorrelationData Processing AlgorithmsDiscrete Fourier TransformFast Fourier TransformFourier TransformPrimitive Root Theorem
The discrete Fourier transform of a sequence of N points, where N is a prime number, is shown to be essentially a circular correlation. This can be recognized by rearranging the members of the sequence and the transform according to a rule involving a primitive root of N. This observation permits the discrete Fourier transform to be computed by means of a fast Fourier transform algorithm, with the associated increase in speed, even though N is prime.
2
What is the fast Fourier transform?
W.T. Cochran, J.W. Cooley, D. L. Favin et al. · IEEE Transactions on Audio and Electroacoustics · 1967 · 496 citations
High-speed convolution and correlation
Thomas G. Stockham · 1966 · 316 citations · Full text