Simplified DFT with sorted accumulation of input samples

In practical embedded implementations of the discrete Fourier transform (DFT), used for example in bio-impedance and electrical network analysers, simplification of the solution (to have a low-cost and power-efficient devices) is a vital task. It is shown, that for calculating of few output points of DFT (up to 10-20 points), a modified ldquobasic DFTrdquo can be more efficient than fast and so-called quick Fourier transforms. Such modification can be realised using properties of symmetry and periodicity of sine and cosine waves, and sorting of input samples for every DFT output point.Applying this approach all the input samples are transferred and accumulated at one quarter of the first harmonic (sine or cosine wave). On the other hand, coefficients of sine and cosine waves of integer harmonics, which are used in calculations as base functions, can be approximated using N discrete levels (N>=2). If these levels are chosen symmetrically, only N/2 multiplications are needed to calculate every DFT component in case of proper pre-sorting and accumulating corresponding input samples. Thus remarkable complexity reduction is obtained for small N. Most principal disadvantage of approximated base-functions is that the noise sensitivity from extra harmonics of approximated sine-and cosine waves is increased (other systematic errors can be compensated in one or another way). The influence of this increase has been estimated.