** Authors:**
Gregor ROZINAJ

** Abstract: **
The evaluation of discrete Fourier transforms (DFT) in a real time is a
common problem in various technical areas. Nowadays, research in technology
offers more and more powerful tools not only for DFT evaluation, but for
many signal processing algorithms as well. However, many applications
still need either a faster or cheaper solution. In spite of signal processors,
where multiplication is usually a one-cycl-operation, in VLSI design of
signal processing algorithm, the number of multiplications is one of the
important factors for the effective complexity limit of the algorithms. This
paper describes a novel algorithm (Effective Fourier Transform, EFT) for an
approximative computation of a DFT without multiplication. The algorithm is
based on the generation of a discrete harmonic function. Considering some
constraints for the frequency of the signal, an arithmetic shift can be
used instead of the multiplication by \cos(\Omega). Columns of the DFT-
matrix can be approximated by the reorganized samples of the harmonic
generator. Considering addition and arithmetic shifts as basic operations,
EFT is faster than the classical \lq\lq butterfly" fast Fourier transform. An
error analysis of the algorithm depends on the speed limitation. Several
factors, such as the length of the DFT and number of sinusoids in an
analyzed spectrum have an effect on the error analysis. Maximum error cca
2 \% of the spectral magnitude is guarantied for the worst case. For well-
separated sinusoids in the spectrum and for some \lq\lq magic" lengths of
EFT, a maximum error cca 0.1\% can be achieved. For statistical evaluation
of the spectrum EFT is even more suitable, as one part of the algorithm can
be done only once for several EFT computations.

** Keywords: **