Prots'ko I. Means of the fast Fourier transform of series with arbitrary dimension.

The thesis is devoted to analysis and synthesis of algorithmic and special-purpose structural means of the fast DFT of series with arbitrary dimension. Many efficient algorithms have been designed for composite transform sizes, such as the Cooley-Tukey FFT algorithm, the Good-Thomas prime factor algorithm, etc. The Good-Tomas prime factor algorithm decomposes the computation of the FFT into small-size FFT's. However, this algorithms use the library of different small- size FFT. The general scheme of the fast calculation DFT of series with arbitrary dimension is derived in this work. The synthesis of FFT algorithm is based on the decomposition of the matrix of powers of discrete exponential basis of DFT with adding matrices of signs sine and cosine functions. Matrines of powers of exponential basis of DFT are analysed and a set of natural numbers of transform dimensions is broken into six subsets. Hankel circular matrines of powers of discrete exponential basis of DFT for cycles from the cycle decomposi tion of substitution are formed. The substitution is determined by the first two rows of matrix of powers. The equivalence of the block-structures matrix of powers of square matrix of exponential basis of DFT and the accordance matrices of signs cosine and sine function is proved. In the results, DFT of series with arbitrary dimension are computed as circular convolutions for sine and cosine parts of discrete exponential basis of DFT. Algorithms of Rader and Winograd use circular convolutions also. Its derivation is complicated data indexihg, especialy Winograd algorithms. The proposed algorithm uses the indexing permutation for the cycle decomposition of substitution. This simplifies the data indexing for series with twice less dimensions and the designing fast algorithms discrete Fourier transform and discrete Hartley transform of series with arbitrary dimension. Operational counts for a first twenty transform sizes of real values data samples with using the Winograd small-size cyclic convolutions is given. The proposed FFT algorithm for prime transform dimensions produce algorithms with minimum multiplicative complexity. In the Appendix, the algorithms for 5,14,15,20 sizes of real-valued series are given as examples. The subclass of the generalized small-size FFT algorithms can be used for prime factor algorithm (PFA) and for others large-size algorithms. The sequence of stage in the general scheme of the fast calculation DFT and special-purpose structural means to perform proposed FFT of series with arbitrary dimension are described.