Unified Approach to the Development of Fast Algorithms and Parallel Implementation of Discrete Fourier Transform

摘要

A unified group theoretical approach to the development to the development of fast algorithms and parallel implementation of Discrete Fourier Transform is proposed. Methods of decomposition of Discrete Fourier Transform developed within this approach are described. These methods are based on the formation of the decomposition process and are characterized by the rules of such formation. The application of the proposed methods directly leads to the development of a set of fast parallel algorithms for Discrete Fourier Transforms. Common features of the formed algorithms are their lack of decomposition redundancy and structural flexibility, which allows the parameters to be tuned to any degree and mode of parallelism.