-1
$\begingroup$

I want to take FFT of my signal and reconstruct it back via IFFT. It seems the real part of odd numbered samples and image part of even numbered samples are multiplied by -1 which can be observed below:

For example if I have

        [995]   (-0.382624, 0.000000)   std::complex<double>
        [996]   (-0.831434, 0.000000)   std::complex<double>
        [997]   (-1.000000, 0.000000)   std::complex<double>
        [998]   (-0.831506, 0.000000)   std::complex<double>
        [999]   (-0.382743, 0.000000)   std::complex<double>

Some of the values(not all) having the negative sign like below

    [995]   (0.382624, 0.000000)    std::complex<double>
    [996]   (-0.831434, -0.000000)  std::complex<double>
    [997]   (1.000000, 0.000000)    std::complex<double>
    [998]   (-0.831506, 0.000000)   std::complex<double>
    [999]   (0.382743, -0.000000)   std::complex<double>

Is there any explanation for this behavior?

I am using FFTW library and I wrap it a bit like below ;

in = sharpFFT(in, true);
in = swapVectorWithIn(in);
in = sharpFFT(in, false);
for ( auto& elem : in)
    elem /= in.size();

using CDataType = std::vector< std::complex<double> > ;

inline
CDataType swapVectorWithIn( const CDataType& in )
{

    auto middlePos = in.begin() + in.size()/2;
    CDataType returnVal( middlePos , in.end() );
    returnVal.insert( returnVal.end(), in.begin(), middlePos);
    return returnVal;
}

inline
CDataType sharpFFT( CDataType& in, bool isForward )
{
    const int N =  in.size() ;

    std::vector< std::complex<double> > out (N);

    fftw_plan my_plan;
    if (!isForward)
      my_plan = fftw_plan_dft_1d(N, reinterpret_cast<fftw_complex*>(&in[0]),
                                             reinterpret_cast<fftw_complex*>(&out[0]), FFTW_BACKWARD, FFTW_ESTIMATE);
    else
      my_plan = fftw_plan_dft_1d(N, reinterpret_cast<fftw_complex*>(&in[0]),
                                               reinterpret_cast<fftw_complex*>(&out[0]), FFTW_FORWARD, FFTW_ESTIMATE);

    fftw_execute(my_plan);
    if (!isForward)
    {
        std::transform(out.begin(), out.end(), out.begin(), [N]( std::complex<double>& elem ){
            return elem / (double)N;
        });
    }
    return out;
}
$\endgroup$
  • $\begingroup$ it is a programming problem rather than DSP. Sometimes values close to zero, which are displayed as 0.00.. can swicth from positive to negative due to roundoff error, but that's it. Anything nonzero should keep its sign. So... you have a bug in your code. $\endgroup$ – Fat32 Mar 1 '16 at 0:06
  • $\begingroup$ It is not only zeros, also value -0.382624 became 0.382624. $\endgroup$ – Kadir Erdem Demir Mar 1 '16 at 5:23
  • 1
    $\begingroup$ @Fat32: No, memory management does not cause this. Memory management doesn't attach a special significance to just that one bit which represents the sign, whereas numerical code does attach a special significance to it. $\endgroup$ – MSalters Mar 1 '16 at 16:23
  • 1
    $\begingroup$ @Fat32: Those are indeed more common symptoms of memory management issues, but that's not the case here ! $\endgroup$ – MSalters Mar 1 '16 at 18:59
  • 1
    $\begingroup$ @KadirErdemDemir: I think you missed std::rotate $\endgroup$ – MSalters Mar 1 '16 at 20:17
2
$\begingroup$

I am not fully sure about your code, but swapVectorWithIn() does shift your input vector by half of its lengths (or in Fourier terms: It shifts the spectrum so that the DC component is in the middle of the spectrum and not on the left side).

The output you show comes from doing an FFT, bringing the DC component to the middle of the spectrum, and doing an inverse FFT, right?

If this is true, than your algorithm works perfectly normal. Have a look at the Fourier-Shift-Theorem: A shift in one domain results in a linear phase in the other domain. Your shift is in the frequency domain, hence you can expect a linear phase variation in the time domain. The sign alternation is a result from a 0°-180°-0°-180°-... modulation, which is correlated to the amout of shifting in the frequency domain. And since 180° corresponds to a multiplication by -1, you get this patterin in your data. Try shifting it not by half of the length, but by a quarter. Then your alternation pattern should be 0°-90°-180°-270°-0° = 1-i-(-1)-(-i)-... multiplication of your input data, if I get that right right now.

$\endgroup$
  • $\begingroup$ The problem if I won't shift , ifft reconstruction is not working, totally unrelated data appearing. $\endgroup$ – Kadir Erdem Demir Mar 1 '16 at 21:50
  • $\begingroup$ Then, I assume, there is some delicate special behavior going with your FFT algorithm, since IFFT(FFT(x)) should be an identity operation. However, the Fourier-Shift-Theorem will also apply, which does not make things easier. Maybe you are confronted with two distinct problems, and right now you assume that there is only one. I'd suggest thorough (re)testing of your FFT algorithm in this case. $\endgroup$ – M529 Mar 1 '16 at 22:33
1
$\begingroup$

Basic Fourier theory: you appear to have multiplied your signal with +1 -1 +1 -1 +1 -1. This is a very high frequency wave, at precisely the Nyquist frequency in fact.

The energy at the Nyquist Frequency is stored in your last FFT bin. And you wouldn't be the first programmer to have a one-off error, especially since the DFT has a rather odd number of bins: A 1024 point real FFT produces 513 (N/2 +1) bins.

I don't spot an immediate cause in your C+ code, but the pattern is mathematically clear at least.

$\endgroup$
  • $\begingroup$ Should I just multiple the real part or also imaginary part as well $\endgroup$ – Kadir Erdem Demir Mar 1 '16 at 20:01
  • $\begingroup$ Actually, I'think M529 is right. What you do with the vector is a convolution in the time domain, which happens to be a multiplication in the frequency domain. And your particular convolution is with a shifted delta, a function whose FFT is a sine. $\endgroup$ – MSalters Mar 1 '16 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.