Numerical method of multi-stage discrete Fourier transform of a digital signal

The issues related to the study of the possibilities of mathematical and software modeling of digital algorithms for discrete Fourier transform without algorithmic multiplication operations are considered. The relevance of the study is due to the need to reduce the computational complexity of digital signal processing algorithms. The purpose of the study is to formalize a numerical method for the multi–stage discrete Fourier transform of a digital complex signal. The methods of mathematical and software modeling of numerical methods of digital signal processing were used in the study. The results of the study showed and confirmed the possibility of modeling a numerical method of multi-stage discrete Fourier transform of a digital complex signal based on numerical methods of difference digital filtering with integer difference coefficients of various orders of difference and a numerical method of reducing direct calculations of complex functions to perform simple operations of addition and shift. The concept of a multi-stage discrete Fourier transform and the concept of this transformation are defined and described. Its mathematical model is proposed and the numerical method of such transformation is formalized. It is noted that it allows to reduce the computational complexity of the hardware and software implementation of digital signal processing through the use of numerical methods of differential digital filtering, directed enumeration and comparative analysis of acceptable sets of numerical values of integer coefficients, which provides the possibility of reducing the error of the numerical method of multi-stage discrete Fourier transform. To reduce the computational complexity of his algorithms for isolating the harmonic components of a digital complex signal, the principles of dividing its frequency spectrum into narrow-band spectral components, frequency shifting of these components and their low-frequency difference digital filtering without performing arithmetic multiplication operations are applied.