Radix $r^{k}$ FFTs: Matricial Representation and SDC/SDF Pipeline Implementation

This paper proposes to use the discrete Fourier transform (DFT) matrix factorization based on the Kronecker product to express the family of radix rk single-path delay commutator/single-path delay feedback (SDC/SDF) pipeline fast Fourier transform (FFT) architectures. The matricial expressions of the radix r, r ², r ³, and r ⁴ decimation-in-frequency (DIF) SDC/SDF pipeline architectures are derived. These expressions can be written using a small set of operators, resulting in a compact representation of the algorithms. The derived expressions are general in terms of r and the number of points of the FFT N. Expressions are given where it is not necessary that N is a power of rk. The proposed set of operators can be mapped to equivalent hardware circuits. Thus, the designer can easily go from the matricial representations to their implementations and vice versa. As an example, the mapping of the operators is shown for radix 2, 2², 2³, and 2⁴, and the details of the corresponding SDC/SDF pipeline FFT architectures are presented. Furthermore, a general expression is given for the SDC/SDF radix rk pipeline architectures when k > 4. This general expression helps the designer to efficiently handle a wider design exploration space and select the optimum single-path architecture for a given value of N.