•  
  •  
 

Turkish Journal of Physics

Frequency Acquisition in a Signal with Few Sinusoids Using Effective Fourier Transform

Gregor ROZINAJ

DOI

-

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.

First Page

324

Last Page

330

This document is currently not available here.

Share

COinS