Matrix representations for sorting and the fast Fourier transform

The different versions of the fast Fourier transform (FFT) are described here for arbitrary base in terms of the matrix factors of the discrete Fourier transform matrixT_{N}. The Kronecker product notation and the ideal shuffle baserpermutation operator form the basis for a unifying theory through which the various versions of the FFT can be viewed. The properties of the ideal shuffle baserpermutation operator are used to arrive at FFT versions with such desirable properties as in-place computation or identical geometry from stage to stage. The FFT versions previously described in the literature are derived here. At the same time, algorithms for the sorting of FFT data in digit-reversed order are generated. These are explored and new sorting versions amenable to hardware implementation with sequential memory are presented. As an example of how the unifying theory is used, a number of FFT versions with identical geometry from stage to stage are derived. The hardware necessary for these algorithms is described for the base 4 case withN = 1024data points.