公开(公告)号：US20040167950A1

公开(公告)日：2004-08-26

申请号：US10727138

申请日：2003-12-03

Applicant: STMicroelectronics Pvt. Ltd.

Inventor： Kaushik Saha ,  Srijib Narayan Maiti

IPC: G06F015/00

CPC classification number: G06F17/142

Abstract: A linear scalable method computes a Fast Fourier Transform (FFT) or Inverse Fast Fourier transform (IFFT) in a multiprocessing system using a decimation in time approach. Linear scalability means, as the number of processor increases by a factor P (for example), the computational cycle reduces by exactly the same factor P. The method includes computing the first two stages of an N-point FFT/IFFT as a single radix-4 butterfly computation operation while implementing the remaining (log2Nnull2) stages as radix-2 operations. Each radix-2 operation employs a single radix-2 butterfly computation loop without employing nested loops. The method also includes distributing the computation of the butterflies in each sage such that each processor computes an equal number of complete butterfly calculations thereby eliminating data interdependency in the stage.

Abstract translation: 线性可伸缩方法在使用时间抽取方法的多处理系统中计算快速傅里叶变换（FFT）或快速傅里叶逆变换（IFFT）。 线性可伸缩性意味着，随着处理器的数量增加因子P（例如），计算周期减少了完全相同的因子P.该方法包括将N点FFT / IFFT的前两个阶段计算为单个基数 -4蝶形计算操作，同时以基数-2操作实现剩余（log2N-2）级。 每个radix-2操作都使用单个2进制蝶形计算循环，而不使用嵌套循环。 该方法还包括在每个鼠标中分配蝴蝶的计算，使得每个处理器计算相等数量的完整蝴蝶计算，从而消除阶段中的数据相互依赖性。