Patent ID: 8549059

Claim:
A method for calculating an N-point Fast Fourier Transform (FFT) using mixed radix stages with in-place data sample storage, comprising: decomposing N into a product of R sequential mixed radix stages of radix-r(i), where i represents the stage number, such that N=r (0)* r (1)* r (2)* r (3)* . . . * r ( R− 1) wherein the sequential order of the stages determines the order in which they are calculated; storing N data samples partitioned into at least B memory banks of the in-place data sample storage, where r(i) of the memory banks are configured to be read or written concurrently, where B is equal to a largest radix of the R radix stages; calculating for each radix stage at least one radix-r(i) butterfly in each of a sequence of time units, wherein for at least some butterfly calculations, each input data sample to each radix-r(i) butterfly comes from r(i) different memory banks and the output data samples are written to the same memory locations in the r(i) memory banks as the input data samples; determining from which memory bank the input data samples and output data samples of the butterflies for each sequential radix stage are stored based on the radix size and sequential position of the radix stage, and determining the address of the input data samples and the output data samples within each memory bank based on the radix size and sequential position of the radix stage.