Calculation of the transformed one of discreet Fourier

1) Formulas of the DFT:

for k = 0, 1, … , N-1

for n = 0, 1, … , N-1

 

2) Property of used in order to improve the efficiency of the calculation of the DFT :

 

3) Algorithm of Goertzel  :

where

it is an algorithm that demands 4N real multiplications and 4N real additions in order to gain X(k) for every k.

An improvement of the complexity is obtained by means of the algorithm of modified Goertzel based on the function of transfer.

 

4) Algorithm of FFT based on the decimation in the time:

In short the sequence x(n) comes decomposed in sottosequenze gradually more small in particular to the first step delivers up two sequences ciascuna from N/2 heads, one relative to the pars and the other relative one to the odd number

 

5) Equations of one butterfly in the time :

 

6) Algorithm of FFT based on the decimation in frequency:

In short the X(k) sequence comes decomposed in sottosequenze gradually more small in particular to the first step delivers up two sequences ciascuna from N/2 heads, one relative to the pars and the other relative one to the odd number

 

7) Equations of one butterfly in frequency :

 

8) Algorithm of the Transformed Z Chirp :

It concurs to not only calculate the transformed Z of a generic sequence on the unitary circle but in the points (… con e ) which to varying of k from 0 to M-1 describe a spiral, the transformed one in these points is worth that is introduces as a convoluzione of the sequence can therefore be thought to a Chirp filter with answer the unitary champion , draft of a sequence to infinite duration therefore in order to be estimated the FFT is necessary one its segmentazione.