Ring structure and multi-dimensional discrete Fourier transform on a power of 2
Weihong Ma · 2003
An algorithm for computing DFT (2/sup n/; k) is demonstrated based on ring structure. The matrix of DFT (2/sup n/) can be permuted into a block-structured matrix which contains circulant blocks corresponding to the disjoint cosets of kernel group K, being the direct product of a group of order 2 and a cyclic group of order 2/sup n-2/(2/sup k/-1). The circulant blocks can be further permuted into a block-diagonal matrix with identical blocks, each of which is the core of a one-dimensional DFT (discrete Fourier transform), CFT(2/sup i/).>