On the time complexity of digital Fourier transform parallel computing

Modern trend to parallel implementing the discrete Fourier transform (DFT) – the basis of digital signal processing – is analysed. The one-dimensional DFT is demonstrated to have decisive advantages over fast Fourier transform. A calculating model at the many-channel pipeline achitecture (without any crossing data flows) to compute the two-dimensional DFT in the shortest time is proposed. It is shown that all aspirations to achieve an absolut paralleling in computing ttr multy-dimensionai DFT are unfeasible.