Research And Implement Of SIX-STEP FFT Algorithm Based On Multi-Core Structure

In many scientific research, technological applications, and other related applications, Fourier transform is often used to simplify and solve the above problems. Fourier analysis is the most basic method of signal analysis, which is the core of the discrete Fourier transform Fourier analysis, discrete Fourier transform in digital signal processing, image processing, and many scientific and technical fields have a wide range of applications. But having a large amount of calculation time high complexity and other shortcomings, which greatly limits the Fourier transform of the practical application is difficult to deal with the problem in real time, and therefore leads to a fast Fourier transform(FFT) of the concept.Fast Fourier transform algorithm is fast discrete Fourier transform, which is obtained based on the discrete Fourier transform natural odd, even, true, real and other characteristics of the discrete Fourier transform algorithm to make improvements. For a large number of input data N, fast Fourier transform time complexity is still high, with the increasing popularity of multi-core CPU technology, research-based multi-core parallel computing in depth, so that the model based on multi-core parallel FFT computing possible. Their parallelism can flexibly decomposition algorithm based on FFT butterfly operation by the task of exploring the relationship between data distribution and to optimize nesting algorithms, to achieve a reasonable distribution of threads execute in parallel multi-core CPU, which greatly improves the FFT calculation efficiency, so the system is often used in multi-core parallel computing fast Fourier transforms acceleration.Then many experts and scholars around the FFT algorithm, and put forward a number of FFT algorithm optimization program, which called Six-step FFT algorithm has been widespread concern, it has significantly reduced compared to the previous FFT algorithm the cost of hardware required.Six-Step FFT algorithm time complexity in general has not improved, or that do not have a new breakthrough in the field of mathematics, but they do according to the characteristics of computer architecture, an improved task decomposition methods, and tasks mapping scheme.Six-step FFT algorithm but the original task mapping scheme did not play the FFT algorithm inherent parallelism. This article analyzes and summarizes the FFT algorithm for parallel structures and Six-step FFT algorithm. An improved mapping scheme on Six-step FFT algorithm, and the implementation of large amounts of data and analysis on multi-core processor architecture.