任意點數快速傅立葉轉換之計算與定址方法

Abstract

本發明藉由分解方程式將長點數離散傅立葉轉換的計算分解為數個短點數的離散傅立葉轉換，並同時將其指標由單一維度映射成多維度指標向量。藉由控制這些指標向量，本發明把原始輸入資料分散存放到數個記憶體裡，使得在不產生記憶體存取衝突的情況下同時達到計算期間的資料置換(in-place policy)與記憶體完整蝴蝶點數一次存取的目的。此外，當資料置換使用在已計算完成的舊資料依序輸出與新資料依序輸入時，為了往後計算期間可以繼續保持資料存取時沒有記憶體衝突，本發明對於新資料的計算採取與先前資料計算時的反序操作來達成目的。此方法，對於任意點數的以記憶體為基礎的離散快速傅立葉轉換處理器設計可以有效的減少處理器面積與所需的操作時脈。本發明並涉及一種使用此方法之以記憶體為基礎之正/逆向快速傅立葉轉換(FFT/IFFT)處理器。