Algorithm of defining 1-D indexing for M-D mixed radix FFT implementation

A novel M-D (multidimensional) to 1-D FFT (fast Fourier transform) signal flow graph mapping is proposed. Thus, the M-D FFT can be efficiently implemented by the unified 1-D indexing, and the address generator design can be simplified. In addition, the matrix transposition is no longer necessary. The addressing sequences can be derived from the factorization of the twiddle factor matrix. The unified indexing concept of the M-D FFT implementation automatically solves the scaling problem of the block floating-point arithmetic. Practical chip design considerations in implementing the algorithm are presented