基于多核結(jié)構(gòu)的SIX-STEP FFT算法的研究和實(shí)現(xiàn).pdf

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

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

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