基于多核結構的SIX-STEP FFT算法的研究和實現.pdf

1、在許多科學研究、技術應用領域以及其他相關場合，傅里葉變換常常用于上述問題的簡化和求解。傅里葉分析是信號分析的最基本方法，而離散傅里葉變換是傅里葉分析的核心，離散傅里葉變換在數字信號處理、圖片處理以及許多科學技術領域都有著廣泛的應用。但其具有計算量大，時間復雜度高等缺點，這就極大地限制了傅里葉變換在實際中的應用、難以實時地處理問題，因此引出了快速傅里葉變換(FFT)這一概念。
　　快速傅里葉變換，是離散傅氏變換的快速算法，它是根據離

2、散傅氏變換天然的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進而獲得的。對于大量的輸入數據N，快速傅里葉變換時間復雜度仍然很高，隨著多核CPU技術的日益普及，基于多核的并行計算的研究深入，使得基于多核模型的并行FFT計算成為可能?？筛鶕﨔FT算法自身的并行性，靈活地分解蝶形運算，通過對探究任務數據的分配和嵌套關系對算法加以優(yōu)化，合理地分配線程實現多核CPU的并行執(zhí)行，極大地提高了FFT的計算效率，所以，多核并行系統(tǒng)常被應用于加速快

3、速傅里葉變換的計算。
　　隨后許多專家和學者圍繞著FFT算法進行研究，并提出了多種FFT算法的優(yōu)化方案，其中一種叫Six-step FFT的算法得到了普遍的關注，它的出現較之前的FFT算法大大地降低了所需的硬件成本。
　　六步快速傅里葉變換對一般FFT算法的時間復雜度并沒有提升，或者說并沒有在數學領域有新的突破，但確根據計算機結構的特性、提出一種改進的任務分解方式，以及任務映射方案。
　　但是Six-step FFT算