Patent Document ID: 20140330880
Application ID: 14117192
Patent Flag: 0

Claim One:
1. A method for multi-granularity parallel FFT butterfly computation of input data using a plurality of buffers, wherein a first buffer and a second buffer are configured to buffer data for butterfly computation stages in a parallel FFT butterfly group, a third buffer is configured to buffer twiddle factors for the butterfly computation stages in the parallel FFT butterfly group, and a fourth buffer is configured to buffer result data after completion of computation of the parallel FFT butterfly group, wherein N points of input data are divided and inputted to ┌(log 2 N)/L┐ computation nodes, each comprising ┌N/2 L ┐ butterfly groups, the butterfly group is a basic unit of parallel butterfly computation, wherein ┌ ┐ denotes a ceiling operation, L is a parallel granularity factor and defines that a number of data which can be read in parallel and used independently in butterfly computation is 2 L ; the method in the butterfly group comprises: step 1, setting an initial value of a counter i=L−Rq, Rq indicates that the current butterfly group starts its computation from the Rqth stage; step 2, reading 2 L points of data for the butterfly computation from the first or second buffer via a multiplexer (MUX), dividing the 2 L points of data into 2 L−1 groups, and reading sequentially from the third buffer the twiddle factors for 2 L−1 parallel butterfly computations; step 3, performing a stage of parallel butterfly computations on the 2 L−1 groups of data; step 4, writing results of the butterfly computations into the second buffer, and rearranging the data; step 5, changing the current value i of the count to i=i−1; step 6, determining whether the value i is equal to 0, and proceeding to step 7 if i=0 indicating the computations of the current butterfly group have been completed, otherwise returning to step 2; step 7, writing the data in the second buffer into the fourth buffer, and ending the computation for the butterfly group.