cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
nurulhuda
Adventurer
Adventurer
958 Views
Registered: ‎03-30-2018

Fast Fourier Transform

Jump to solution

Hi, 

I am doing Fast Fourier Transform. I have a C++ code in 1 cpp file and I separate it into 3 files that required by Vivado HLS: header, .cpp, and testbench file. I am not sure that I separate it in the correct way or not but what I did is as in the attachment files.

I have 3 functions in cpp file. However, I am not sure which file I need to choose as a top function? Is it DFT, FFT , or 

Capture_LI.jpg

cpp file

#include "myftt.h"

//======================================================================

void DFT( Complex f[], Complex ftilde[], int N, int step )           // Basic Discrete Fourier Transform
{
    Complex w = polar( 1.0, -2.0 * pi / N );
    Complex wn = 1.0;
    for ( int n = 0; n < N; n++  )
    {
        if ( n > 0 ) wn *= w;
        Complex wm = 1.0;
        ftilde[n] = 0.0;
        for ( int m = 0, mpos = 0; m < N; m++, mpos += step )
        {
            if ( m > 0 ) wm *= wn;
            ftilde[n] += f[mpos] * wm;
        }
    }
}

//======================================================================

void FFT( Complex f[], Complex ftilde[], int N, int step )           // Fast Fourier Transform
{
    if ( N > 2 && N % 2 == 0 )                                        // Recursion if a multiple of 2
    {
        int N2 = N >> 1;
        Complex* g = new Complex[N];
        
        int step2 = step << 1;
        FFT( f       , g     , N2, step2 );
        FFT( f + step, g + N2, N2, step2 );
        
        Complex w = polar( 1.0, -2.0 * pi / N );
        Complex wn = 1.0;
        for ( int n = 0; n < N2; n++ )
        {
            if ( n > 0 ) wn *= w;
            ftilde[n]    = g[n] + wn * g[n+N2];
            ftilde[n+N2] = g[n] - wn * g[n+N2];
        }
        
        delete [] g;
    }
    else                                                              // Otherwise just do a DFT
    {
        DFT( f, ftilde, N, step );
    }
}

//======================================================================

void iFFT( Complex ftilde[], Complex f[], int N )                    // Inverse Fast Fourier Transform
{
    Complex* ftildeConjugate = new Complex[N];
    for ( int m = 0; m < N; m++ ) ftildeConjugate[m] = conj( ftilde[m] );
    
    FFT( ftildeConjugate, f, N );
    
    double factor = 1.0 / N;
    for ( int m = 0; m < N; m++ ) f[m] = conj( f[m] ) * factor;
    
    delete [] ftildeConjugate;
}

//======================================================================


 testbench file:

#include "myftt.h"

int main()
{
    Complex test[] = { 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 };
    int N = sizeof test / sizeof test[0];
    Complex * ft = new Complex[N];
    
    // Output Original
    cout << "Original:" << '\n';
    for ( int i = 0; i < N; i++ )
        cout << test[i] << '\n';
    
    // Forward transform
    FFT( test, ft, N );

    // Output ft
    cout << "Transform:" << '\n';
    for ( int i = 0; i < N; i++ )
        cout << ft[i] << '\n';
    
    // Invert transform
    iFFT( ft, test, N );
    
    // Output test
    cout << "Invert:" << '\n';
    for ( int i = 0; i < N; i++ )
        cout << test[i] << '\n';
    
    delete [] ft;
}

One more thing, do you think that these codes can be synthesized in Vivado HLS?

 

Thank you.

0 Kudos
Reply
1 Solution

Accepted Solutions
gabed
Xilinx Employee
Xilinx Employee
826 Views
Registered: ‎03-21-2018

Hi @nurulhuda 

Recursive functions cannot be synthesized, I should have noticed that from my last reply.


Cheers
------------------------------------------------------------------------------
Don't forget to reply, give kudo and accept as solution
------------------------------------------------------------------------------

View solution in original post

0 Kudos
Reply
3 Replies
gabed
Xilinx Employee
Xilinx Employee
914 Views
Registered: ‎03-21-2018

The top-level function arguments synthesize into RTL I/O ports. Based off your code it looks like FFT() should be set as the top level since it takes-in all function-argument inputs and also calls function DFT(). 

UG902 gives a nice overview of Vivado HLS.


Cheers
------------------------------------------------------------------------------
Don't forget to reply, give kudo and accept as solution
------------------------------------------------------------------------------
0 Kudos
Reply
nurulhuda
Adventurer
Adventurer
875 Views
Registered: ‎03-30-2018

I tried to synthesize this code, however it failed. Is it because Vivado does not support Recursion function at all or because there is something wrong with my code? 

my_fft.cpp file

 

#include "myftt.h"

//======================================================================

void DFT( Complex f[], Complex ftilde[], int N, int step )           // Basic Discrete Fourier Transform
{
    Complex w = polar( 1.0, -2.0 * pi / N );
    Complex wn = 1.0;
    for ( int n = 0; n < N; n++  )
    {
        if ( n > 0 ) wn *= w;
        Complex wm = 1.0;
        ftilde[n] = 0.0;
        for ( int m = 0, mpos = 0; m < N; m++, mpos += step )
        {
            if ( m > 0 ) wm *= wn;
            ftilde[n] += f[mpos] * wm;
        }
    }
}

//======================================================================

void FFT( Complex f[], Complex ftilde[], int N, int step )           // Fast Fourier Transform
{
    if ( N > 2 && N % 2 == 0 )                                        // Recursion if a multiple of 2
    {
        int N2 = N >> 1;
        Complex* g = new Complex[N];
        
        int step2 = step << 1;
        FFT( f       , g     , N2, step2 );
        FFT( f + step, g + N2, N2, step2 );
        
        Complex w = polar( 1.0, -2.0 * pi / N );
        Complex wn = 1.0;
        for ( int n = 0; n < N2; n++ )
        {
            if ( n > 0 ) wn *= w;
            ftilde[n]    = g[n] + wn * g[n+N2];
            ftilde[n+N2] = g[n] - wn * g[n+N2];
        }
        
        delete [] g;
    }
    else                                                              // Otherwise just do a DFT
    {
        DFT( f, ftilde, N, step );
    }
}

//======================================================================

void iFFT( Complex ftilde[], Complex f[], int N )                    // Inverse Fast Fourier Transform
{
    Complex* ftildeConjugate = new Complex[N];
    for ( int m = 0; m < N; m++ ) ftildeConjugate[m] = conj( ftilde[m] );
    
    FFT( ftildeConjugate, f, N );
    
    double factor = 1.0 / N;
    for ( int m = 0; m < N; m++ ) f[m] = conj( f[m] ) * factor;
    
    delete [] ftildeConjugate;
}

//======================================================================


Testbench file: my_fft_tb.cpp

#include "myftt.h"

int main()
{
    Complex test[] = { 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 };
    int N = sizeof test / sizeof test[0];
    Complex * ft = new Complex[N];
    
    // Output Original
    cout << "Original:" << '\n';
    for ( int i = 0; i < N; i++ )
        cout << test[i] << '\n';
    
    // Forward transform
    FFT( test, ft, N );

    // Output ft
    cout << "Transform:" << '\n';
    for ( int i = 0; i < N; i++ )
        cout << ft[i] << '\n';
    
    // Invert transform
    iFFT( ft, test, N );
    
    // Output test
    cout << "Invert:" << '\n';
    for ( int i = 0; i < N; i++ )
        cout << test[i] << '\n';
    
    delete [] ft;
}

This is the error:

error.PNG

 

0 Kudos
Reply
gabed
Xilinx Employee
Xilinx Employee
827 Views
Registered: ‎03-21-2018

Hi @nurulhuda 

Recursive functions cannot be synthesized, I should have noticed that from my last reply.


Cheers
------------------------------------------------------------------------------
Don't forget to reply, give kudo and accept as solution
------------------------------------------------------------------------------

View solution in original post

0 Kudos
Reply