Research and Implementation of Ultra Large Sequences FFT Optimized Algorithm

For the increasing requirements of ultra long sequences FFTs efficient implementation in application systems, an implementation method is proposed to realize ultra long sequences FFT. The method can solve resources limitation of existed processing platforms, which can save mass memory resources by optimizing the twiddle factor store and adopting the way of rows and columns instead of three explicitly matrix transposition to access the two-dimensional matrix. The characteristics of processors hierarchical memory structure is analysed to optimize the rules of matrix partition, which improves the access efficiency. Experiment results show that the performance of execution efficiency of ultra long sequences FFT is improved nearly half of the memory resources.