Results 1 to 3 of 3

Thread: FFT C++ issue

  1. #1
    Join Date
    May 2017
    Posts
    13
    Qt products
    Qt5
    Platforms
    MacOS X Windows

    Default FFT C++ issue

    Hello,
    I'm tryung to implement Fast Fourier Transformation. And I'm not sure if I understand it correctly.

    As I understand when I transform (for example) simple sine wave by FFT, and than make inversion I should get exactly the same sine wave. Am I right?

    But in some way it doesn't work for me. I found that code with the friend google:

    Qt Code:
    1. #include <complex>
    2. #include <iostream>
    3. #include <valarray>
    4. #include <QVector>
    5. using namespace std;
    6.  
    7. const double PI = 3.141592653589793238460;
    8.  
    9. typedef std::complex<double> Complex;
    10. typedef std::valarray<Complex> CArray;
    11.  
    12. // Cooley–Tukey FFT (in-place, divide-and-conquer)
    13. // Higher memory requirements and redundancy although more intuitive
    14. void fft(CArray& x)
    15. {
    16. const size_t N = x.size();
    17. if (N <= 1) return;
    18.  
    19. // divide
    20. CArray even = x[std::slice(0, N/2, 2)];
    21. CArray odd = x[std::slice(1, N/2, 2)];
    22.  
    23. // conquer
    24. fft(even);
    25. fft(odd);
    26.  
    27. // combine
    28. for (size_t k = 0; k < N/2; ++k)
    29. {
    30. Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k];
    31. x[k ] = even[k] + t;
    32. x[k+N/2] = even[k] - t;
    33. }
    34. }
    35.  
    36. // inverse fft (in-place)
    37. void ifft(CArray& x)
    38. {
    39. // conjugate the complex numbers
    40. x = x.apply(std::conj);
    41.  
    42. // forward fft
    43. fft( x );
    44.  
    45. // conjugate the complex numbers again
    46. x = x.apply(std::conj);
    47.  
    48. // scale the numbers
    49. x /= x.size();
    50. }
    51.  
    52. int main()
    53. {
    54. const Complex test[] = { 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 };
    55. CArray data(test, 8);
    56.  
    57. // forward fft
    58. fft(data);
    59.  
    60. std::cout << "fft" << std::endl;
    61. for (int i = 0; i < 10; ++i)
    62. {
    63. std::cout << data[i] << std::endl;
    64. }
    65.  
    66. // inverse fft
    67. ifft(data);
    68.  
    69. std::cout << std::endl << "ifft" << std::endl;
    70. for (int i = 0; i < 10; ++i)
    71. {
    72. std::cout << data[i] << std::endl;
    73. }
    74. return 0;
    75. }
    To copy to clipboard, switch view to plain text mode 


    So as I understand by ifft(data) I should receive the same as it was on the beggining, but the results are quite different. Can anyone help me?
    For any help thanks in advance.
    Best Regards

  2. #2
    Join Date
    Oct 2009
    Location
    Germany
    Posts
    120
    Thanked 42 Times in 41 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows

    Default Re: FFT C++ issue

    Hello,

    running your program I get the following output (reducing the number of lines to the size of the input data, i.e. 8 instead of 10):
    Qt Code:
    1. fft
    2. (4,0)
    3. (1,-2.41421)
    4. (0,0)
    5. (1,-0.414214)
    6. (0,0)
    7. (1,0.414214)
    8. (0,0)
    9. (1,2.41421)
    10.  
    11. ifft
    12. (1,-0)
    13. (1,-5.55112e-17)
    14. (1,2.4895e-17)
    15. (1,-5.55112e-17)
    16. (5.55112e-17,0)
    17. (5.55112e-17,5.55112e-17)
    18. (0,-2.4895e-17)
    19. (5.55112e-17,5.55112e-17)
    To copy to clipboard, switch view to plain text mode 

    Your input was a vector of 4 ones and 4 zeros (real numbers). And that's (up to rounding errors) "exactly" what you get as output of the ifft call: You get a sequence of complex numbers and you should read the x.yze-17 numbers as 0.

    Compiled with gcc6.

    Best regards
    ars

  3. #3
    Join Date
    May 2017
    Posts
    13
    Qt products
    Qt5
    Platforms
    MacOS X Windows

    Default Re: FFT C++ issue

    Hello,
    thanks for your reply.
    Yes you are right. When I try it with the sine wave, with much more sampling points, the iFFT gives me really close results to the input. I think I understand it now.

Similar Threads

  1. VNC Issue!
    By sanujas in forum Qt for Embedded and Mobile
    Replies: 0
    Last Post: 24th October 2013, 08:22
  2. How to fix this issue?
    By Gokulnathvc in forum Newbie
    Replies: 4
    Last Post: 14th February 2012, 10:19
  3. XML issue
    By jbpvr in forum Qt Programming
    Replies: 1
    Last Post: 25th August 2008, 14:01
  4. UI issue.
    By kaushal_gaurav in forum Qt Programming
    Replies: 2
    Last Post: 13th August 2008, 12:41
  5. qt3 to qt4 - uic issue
    By hvengel in forum Qt Programming
    Replies: 10
    Last Post: 4th March 2007, 03:59

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.