DSPF_sp_fftSPxSP- Help Needed !

BAS

Hi,

I am trying to implement real FFT given at the following page and used the example program from here: \c674x-dsplib_1_03_00_01\src\DSPF_sp_fftSPxSP

http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input

I have some question about it's implementation, I will be so kind to have your help.

#define N 512

float pCFFT_In[2 * N + 4];
float pCFFT_InvOut[2 * N + 4];
float pCFFT_InOrig[2 * N + 4];

Why the size of all the variables like mentioned above have additional 4 ?

What these two functions are doing ?

fltcmp (const float *y1, const float *y2, int n, float tol)

memcpy (pRFFT_InOrig, pRFFT_In, N * sizeof (float));

N is defined as 512 but N/2 has passed to the function DSPF_sp_fftSPxSP as length of FFT as shown below:

DSPF_sp_fftSPxSP (N / 2, pRFFT_In, twiddle, pTemp, brev, rad, 0, N / 2);

I am wondering what is the actual length of FFT here ? What length will I use in this case to find the Frequency Resolution ?

Waiting for your help.

over 14 years ago

0 BAS over 14 years ago

Expert 2370 points

Hey !

C'mon guys.. reply me.. I am still waitin !

0 Rahul Prabhu over 14 years ago in reply to BAS

TI__Guru** 116020 points

BAS,

Sorry for the delay on the response on this. Let me answer some of your questions regarding the example on the wiki

Why the size of all the variables like mentioned above have additional 4 ?

The memory allocation seems to be done to have a provision for padding 2 zeros on either side of the input sequence. However I do agree that the generation of the input sequence does not take this into account

What are the functions doing

fltcmp function?

That function is a verification function that compares 2 float values with a certain threshold for error. This function is used in the code to ensure that the output obtained from the FFT followed by the IFFT is same as the input

memcpy function?

This DSPF_fftSPxSP function is written in hand assembly to use the input buffer to store intermediate computational values so the input buffer is lost once the function is called which means that you need to store a copy of the input in case you wish to process it later.

N is defined as 512 but N/2 has passed to the function DSPF_sp_fftSPxSP as length of FFT as shown below:

DSPF_sp_fftSPxSP (N / 2, pRFFT_In, twiddle, pTemp, brev, rad, 0, N / 2);

The input as well as the output to the DSPF_sp_fftSPxSP function are expected to be in the complex format but in case of a real input your data does not have a imaginary value.The wiki proposes a efficient solution to compute FFT of a real input array without reformating the input to add zero in the imaginary place such that all odd samples in your input are treated as the real and all your odd samples in the real sequence are treated as a imaginary value while computing the FFT. In short your 512 real samples will appear to the function as 256 complex samples.

Once you compute the 256 point complex FFT, you compute the actual 512 point real FFT using the expression implemented in the fft_split function

X_r(k) = G_r(k)IA_r(k) – G_i(k)IA_i(k) + G_r(N–k)IB_r(k) + Gi(N–k)IB_i(k), for k = 0, 1, ..., N/2–1 and G(N/2) = G(0)
X_i(k) = G_i(k)IA_r(k) + G_r(k)IA_i(k) + G_r(N–k)IB_i(k) – G_i(N–k)IB_r(k)

Please let us know if you have any further questions.

Regards,

Rahul

0 BAS over 14 years ago in reply to Rahul Prabhu

Expert 2370 points

Hi Rahul,

Thanks a lot for your help. I still have confusion.

I am using ADC to get input signal and used [2 * N + 4] size buffer throughout the program. Is that Ok ?

I am not performing any IFFT so I have removed fltcmp function. Is that Ok ?

Following is the flow of my program. Please have a look and kindly tell me if some thing is wrong.

short r_buffer[2 * N + 4];

float pCFFT_In[2 * N + 4];
float pCFFT_Out[2 * N + 4];
float pCFFT_InvOut[2 * N + 4];
float pCFFT_InOrig[2 * N + 4];

float pRFFT_In[2 * N + 4];
float pRFFT_Out[2 * N + 4];
float pRFFT_InvOut[2 * N + 4];
float pRFFT_InOrig[2 * N + 4];
float pTemp[2 * N + 4];

// After getting ADC sample in r_buffer transforming into Real FFT of length N/2.

    for (i = 0; i < N / 2; i++)
    {
        pRFFT_In[2 * i] = ((float)r_buffer[2 * i];          //arrange real input sequence to
        pRFFT_In[2 * i + 1] = (float)r_buffer[2 * i + 1];   //N/2 complex sequence..
    }

    memcpy (pRFFT_InOrig, pRFFT_In, N * sizeof (float)); // Do I need this one ?

    tw_gen (w, N / 2);
    split_gen (A, B, N / 2);
    // Once w(twiddles), A, B Tables are generated they can be saved as .const and need not be generated every time..
    twiddle = (float *) w;

    // Forward FFT Calculation using N/2 complex FFT..
    DSPF_sp_fftSPxSP (N / 2, pRFFT_In, twiddle, pTemp, brev, rad, 0, N / 2);
    // FFT Split call to get complex FFT out of length N..
    FFT_Split (N / 2, pTemp, A, B, pRFFT_Out);

// calculating magnitude
    for(j=0; j < N ; j++)

        {
            fft_mag[j] = magcalculation((double)pRFFT_Out[2*j], (double)pRFFT_Out[2*j+1]);
            fft_mag[0] = 0.0;
        }

If N = 512, it means I am performing 512 point FFT but it considers 256 point because of the real implementation, right ?

Thanks for your couple of minutes.

0 Rahul Prabhu over 14 years ago in reply to BAS

TI__Guru** 116020 points

I am using ADC to get input signal and used [2 * N + 4] size buffer throughout the program. Is that Ok ?

Yes that is Ok. You should be fine even with 2*N.

I am not performing any IFFT so I have removed fltcmp function. Is that Ok ?

Yes, fltcmp is just used as a verification function so you can take it out.

memcpy (pRFFT_InOrig, pRFFT_In, N * sizeof (float)); // Do I need this one ?

You need this only if you wish to preserve the input from the ADC as the input buffer gets overwritten by intermediate FFT values.

If N = 512, it means I am performing 512 point FFT but it considers 256 point because of the real implementation, right ?

That is correct. Once you compute the 256 point FFT, you need to pass it to the fft_split function to compute the complete 512 point real FFT.

Let us know if you have any further questions.

Regards,

Rahul

0 BAS over 14 years ago in reply to Rahul Prabhu

Expert 2370 points

Hi Rahul,

Thanks for your valuable time and help. I really appreciate it.

Regards.

0 BAS over 14 years ago in reply to BAS

Expert 2370 points

Hi Rahul,

There are some more question which I would like to ask.

1. In this real FFT implementation, pInput is generated for N values (N = 512) but the size of pInput is [2 * N + 4]. Does it mean half of the data stored in pInput is garbage ?

2. In the loop given below, N input samples are arranged in N/2 complex sequence for computing reall FFT then why the size of pRFFT_In is [2 * N + 4] ?

// Real FFT of length N/2
    for (i = 0; i < N / 2; i++)
    {
        pRFFT_In[2 * i] = pInput[2 * i];            //arrange real input sequence to
        pRFFT_In[2 * i + 1] = pInput[2 * i + 1];   //N/2 complex sequence..
    }

3. In the same way all the variables used in this example has the same size [2 * N + 4] ?

float pInput[2 * N + 4];

float pCFFT_In[2 * N + 4];
float pCFFT_Out[2 * N + 4];
float pCFFT_InvOut[2 * N + 4];
float pCFFT_InOrig[2 * N + 4];

float pRFFT_In[2 * N + 4];
float pRFFT_Out[2 * N + 4];
float pRFFT_InvOut[2 * N + 4];
float pRFFT_InOrig[2 * N + 4];
float pTemp[2 * N + 4];

I am really confuse due to size of different variables. If N = 512, does it mean that we are dealing with 512 points of input samples and computing 512 points FFT and different sizes of variables are just the way to implement this of REAL FFT algorithm ?

I will really appreciate your quick reply.

Thanks.

0 Rahul Prabhu over 14 years ago in reply to BAS

TI__Guru** 116020 points

BAS,

Sorry to know that you are being confused by the way the code has been written. Perhaps we need to refine the example to clear the confusion being caused. Here are some of the answers to your questions.

pInput need not be defined as pInput[2*N+4]. It can be defined as pInput[N] as it will contain only 512 values. Same is the case with pRFFT_In. However the output arrays for real FFT must contain 2N values as they store N complex ouputs.

You can change the code to define the variables as follows

float pInput[N ];

/* For FFT implementation by formating the input signal as complex */
float pCFFT_In[2 * N ];
float pCFFT_Out[2 * N];
float pCFFT_InvOut[2 * N];
float pCFFT_InOrig[2 * N];

/* For FFT implementation that shows efficient mechanism of computing FFT of a real valued signal without having to format the real input signal as a complex signal*/

float pRFFT_In[ N];
float pRFFT_Out[2 * N];
float pRFFT_InvOut[N];
float pRFFT_InOrig[N];
float pTemp[ N ];

You are right in the example when you define N=512 it means that the you are dealing with a 512 point real valued input samples and computing 512 point FFT(output will be complex). You can correct the different sizes of the arrays as shown above.

Let us know if this helps resolve your confusion regarding the example.

Regards,

Rahul

0 BAS over 14 years ago in reply to Rahul Prabhu

Expert 2370 points

Hi Rahul..

Thanks a million for your quick reply.

Yes, now I understood about different sizes but one thing about twiddle factor, the size of twiddle is [2 * N], it it ok ?

I calculated FFT magnitude for N points and it shows 2 peaks i.e. one real and one immaginary.

Can I take only 256 points from FFT magnitude calculation and divide them by 256 and multiply by 2 to get the scaled magnitude ?

So nice of you for your help.

Thanks.

0 Rahul Prabhu over 14 years ago in reply to BAS

TI__Guru** 116020 points

BAS,

The twiddle factor array has to be of the size 2*N in the example as that array is being reused in the example in the COMPLEX_FFT() and REAL_FFT() functions. The size of twiddle factor array generated for the real FFT is N but the size of the twiddle factor array required to compute the COMPLEX FFT is 2*N hence the definition. If the application that you are creating does not compute complex FFT, you can define the twiddle factor array to contain only N elements.

Regards,

Rahul

0 BAS over 14 years ago in reply to Rahul Prabhu

Expert 2370 points

Thanks Rahul.

I am dealing with real signal and found leakage in the FFT spectrum. Is there any window function like Hann window or Hamming window made by TI so that I could use it with input samples before apply FFT algorithm ?

0 Ido Niv over 14 years ago

Prodigy 10 points

Hi Bas,

Can you please send me the real FFT algorithm you have or another one for c6713?

thanks,

Ido.

Processors

Processors forum

DSPF_sp_fftSPxSP- Help Needed !