There are two fast calculation methods of discrete Fourier transform: FFT algorithm based on time extraction and FFT algorithm based on frequency extraction. The former arranges time-domain signal sequences in odd-even order, while the latter arranges frequency-domain signal sequences in odd-even order.
Both rely on two characteristics: first, periodicity; The second is symmetry, and the symbol * represents its yoke. In this way, the calculation of discrete Fourier transform can be divided into several steps, and the calculation efficiency is greatly improved.
Transformation proposal
Fourier is the name of a French mathematician and physicist. His original English name is jean baptiste joseph fourier (1768- 1830). Fourier is very interested in heat transfer. 1807, he published a paper in the French society of science, describing the temperature distribution with sine curve. In the paper, there was a controversial decision at that time: any continuous periodic signal can be used.
At that time, there were two famous mathematicians who reviewed this paper, namely Joseph Louis Lagrange (1736- 18 13) and Laplacian (1749- 1827). When Laplace and other reviewers voted to publish this paper, Lagrange firmly opposed it. For the next six years, Lagrange insisted that Fourier's method could not represent angular signals, such as discontinuous slopes in square waves.
The French scientific society succumbed to Lagrange's prestige and rejected Fourier's work. Fortunately, Fourier has other things to do. He took part in the political movement. After Napoleon's expedition to Egypt, the French Revolution was put to the guillotine, and he has been escaping. This paper was not published until 15 after the death of Lagrange.