Mixed radix FFT

This is the implementation of the mixed radix FFT. It is based on the factorization of a size-N FFT into two stages. The input in is a length N = P*Q vector, where Q contains all the power-of-2 factors. The first stage cuts the vector into P size-Q vectors and performs P size-Q FFTs. Also in the first stage, the FFT results are point-wise multiplied by complex vector twiddle factors. The second stage performs Q size-P DFTs. Throughout the stages, the only computation time required in the five identity transformations is for the three matrix transpose functions (ident1, ident4, and ident5).

This hierarchical function box is used twice in the higher level graph. Once with P and Q both powers-of-2 (middle main branch) and once with Q a power-of-2 and P not (bottom main branch.

The range variables are used in the comments. They are not used for graph instantiation. For further details about their use, see the bracket notation web page.

To see more implementation details double-click on either the first or second hierarchical box.

 A design change can be made by taking the point-wise multiplication out of the first stage, putting it between the two stages. This would make the two stages more balanced in design and concept. The functionality would not change, nor would any options in further optimization. Gedae places no hierarchical boundaries on design optimization schemes.

 It should be noted that some of the transformations can be done differently. Since each identity transformation requires no compute time, the only requirement is to get the data in the form of the matrices for the transposes and vectors for the FFTs. The implementation of the transformations is for graph syntax and data type casting.