A Numerical System for Real Time measurements

Before getting in the heart of the main feature of this project, which is an instrument for the phase spectrum analysis using specific FFT algorithms with phase error corrections, the first sections describe the conventional FFT and problems related to it. However, also a conventional FFT algorithm has been implemented in our instrument.

The FFT represents an efficient way to calculate the discrete Fourier transform (DFT) of finite time length and/or periodic data sequences.

A DFT is defined as

5.1

where

5.2

While

The calculation of the harmonics

• The product

• Therefore, for each harmonic, we have 4

The main task of the fast Fourier transform (FFT) algorithms is to reduce as much as possible, the number of operations needed to perform the DFT.

The basic idea behind the FFT is to break up the DFT calculation of an

Table 5.1 shows the most common algorithms and their required number of operations [4]:

Table 5.1.

It is worth to mention, for historical reasons, the Goertzel algorithm [5], which has been the first implemented FFT algorithm: it requires about 2

An improvement can be observed with the Radix-2 algorithm where the number of operations is proportional to

The same principles hold for the Radix 4 and 8 [6,7], where this time

Given a generic number of points

The choice of the algorithm depends on the real time requirements and on the DSP features: when the DSP is able to perform both a multiplication or an addition within the same CPU time, as in our case, it is not necessary to adopt the Rader Brenner solution (see table 5.1.) In fact, in this latter case, the total number of operations is higher than the one for the optimised Radix-2 solution.

In addition, the solution proposed by Winograd [4] has been rejected mainly for two reasons: first because the idea behind the algorithm is to reduce the number of multiplications to the detriment of the number of additions, which grows. This could be useful in case of a typical General Purpose processor (CISC) where generally a multiplication requires more cycles than the sum. On the contrary, looking at the table 5.1, you can see that the total number of operations (additions and products together) obtained with Winegard, is higher than the optimised Radix-2 solution. Second, the Winograd solution uses a recursive structure. This leads to a different memory management not as suitable for our pipelined DSP as for a CISC machine: the frequently function calls could prevent the CPU from a proper and efficient use of the pipeline, and the resulting code could be reach of

We have also rejected the Radix 4 and 8 algorithms because we chose to handle the DSP memory using blocks of 1024 word

An attractive solution is the algorithm that considers a generic number of data, and processes the data in a packed form. Unfortunately, also its structure is strictly dependent on the samples number, resulting in a less general and less flexible solution. It is different the case in which the number of input data is a power of 2; indeed, these algorithms let you to calculate the results on site, that is in the same memory location where the original input data are located without the need to move the data itself.

Somehow, also the optimised Radix 4 algorithm, as suggested by the Bellinger, is not recommended. In fact, even if it is very efficient (about 25% more versus the Radix 2,) nevertheless it requires a considerable space of memory to store the matrices obtained from the Kronekher factorisation. In this case, we would not be able to load these matrices in the ONCHIP memory of the DSP or even elsewhere on the DSP.

Consequently, to the above considerations, we chose to implement the optimised Radix 2 algorithm.

The adopted developing methodology is the Time Decimation.

FFT based on the time decimation have been developed breaking up the DFT calculation into smaller and smaller sub-sequences of the original input one

Fig. 5.2. Flow chart of time decimation FFT algorithm.

The FFT algorithm used for processing in real time the input data has been written in Assembly language.

This implemented algorithm for a real FFT, is based on the Sorensen [8] algorithm: the

Fig. 5.3. Flow Diagram of a real Radix-2 (Sorensen) FFT. The symbol *X* represents the real values, while the symbol *o* the complex ones.
The arches show where the complex conjugate pairs are.
The hatch lines of the butterfly structure, represents where there is no need of any calculation.

Even if this algorithm needs to reorganise the data to calculate the spectrum, the amount of these operations is not as big as the number of operations required in case of an algorithm that processes a complex signal of

Table 5.2 Times required to process the data are in milliseconds.