Data access method and device for parallel FFT computation

A data access method for parallel FFT computation comprising the steps of:

• dividing initial FFT data of a length N into 2G groups by a parallel granularity 2B, where G=log2N−B, and storing the 2G groups in respective memory rows of 2B memory blocks in a first multi-granularity parallel memory or a second multi-granularity parallel memory, where each of the memory blocks comprises 2G-B groups, and occupies 2G-B memory rows;
• storing sequentially 2B−1 twiddle factors required for computation of each butterfly group in memory rows of a third multi-granularity parallel memory;
• reading data required for FFT butterfly computation stored in the jth memory row of the ith memory block in the first or the second multi-granularity parallel memory with a read granularity of 2B, where i and j each have an initial value of 0, and reading sequentially, from the third multi-granularity parallel memory, the twiddle factors required for FFT butterfly computation with a granularity of 2B in the order of the memory rows;
• performing parallel butterfly computation on the data read from the jth memory row with a granularity of 2B based on the read twiddle factors;
• writing the result data of butterfly computation to the first or the second multi-granularity parallel memory with a granularity of 1, where when the data was read from the first multi-granularity parallel memory, the result data is written to the second multi-granularity parallel memory, and vice versa;
• determining whether an index j of the current memory row satisfies j<2G-B and incrementing j by 1 and returning to the step of reading if it satisfies, otherwise setting j to 0;
• and
• determining whether an index i of the current memory block satisfies i<2B, and incrementing i by 1 and returning to the step of reading if it satisfies, otherwise terminating the method.