The systematic design of area efficient VLSI architectures for the discrete Fourier transform

Systematic application of linear projection and scheduling to dependence graph (DG) algorithm representations are used to generate asymptotically optimal discrete Fourier transform layouts in a VLSI computing model. Two-stage prime factor maps are used to generate regular and minimum area period (AP) architectures. Offset parallel multi-projections generate overlapped twin-processing element arrays. Systematic multi-projections of six-dimensional three-factor DGs and eight-dimensional four-factor DGs generate successively faster AT² optimal and regular architectures, but with increasing wire area