# Trying to understand what FFT returns to me

**URL:** <https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331>\
**Category:** Numerics\
**Tags:** question, fftw\
**Created:** [February 13, 2022, 7:37am UTC](https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331 "2022-02-13T07:37:00Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Abhijit\_Chowdhary](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abhijit_chowdhary/32/29227_2.png) [@Abhijit\_Chowdhary](https://discourse.julialang.org/u/Abhijit_Chowdhary)\
**Post date:** [February 13, 2022, 7:37am UTC](https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331/1 "2022-02-13T07:37:00Z")

</div>

Hello all,

I’ve been working with the FFTW library over the past few days and am struggling to understand what exactly I have when I take the fft of some array. In particular, taking f to be some function defined over [-\pi, \pi], I want to compute the coefficients c\_n such that:

f(x) \approx \sum\_{n=-N+1}^N c\_n \exp(i n x)

From my understanding of the FFTW library and what it returns (based on what the [documentation](https://juliamath.github.io/AbstractFFTs.jl/stable/api/) says), if `c` is the array returned by a fft of said function over a grid of size N, then I should be able to say

f(x) \approx \frac{1}{N} \sum\_{n=1}^N c[n] \exp(i (n-1) x)

For example, take this small code snippet.

```julia
using FFTW
using LaTeXStrings
using Plots

N = 101;
x = LinRange(-pi, pi, N);
sinx = sin.(x);
sinx_h = fft(sinx);

f(z) = real( sum(sinx_h .* exp.(im*(0:N-1)*z)) / N );

plot(xlabel=L"x \in [-\pi,\pi]", legend=:topleft)
plot!(x, sinx, lw=3, label="sin(x)")
plot!(x, f.(x), lw=3, ls=:dash, label="Fourier Representation");
savefig("fourier_test.png")

```

![fourier_test](https://global.discourse-cdn.com/julialang/original/3X/2/8/28a19b6547b3f4f6f5e964f5aa78bf34fa9a0cac.png)

I’d expect both `sinx` and `f.(x)` to be roughly equal, but they’re flipped and off by about a factor of 2. Any ideas as to why this is happening / where my misunderstand of either the math or what FFTW is doing is?

---

<div class="post-metadata">

**Author:** ![Abhijit\_Chowdhary](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abhijit_chowdhary/32/29227_2.png) [@Abhijit\_Chowdhary](https://discourse.julialang.org/u/Abhijit_Chowdhary)\
**Post date:** [February 13, 2022, 8:03am UTC](https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331/2 "2022-02-13T08:03:48Z")

</div>

Hm, In addition tested this with the fourier coefficients computed from a simple for loop as detailed in _Numerical Methods by Dahlquist and Bjorck_ chapter 9.3.1. Something like:

```julia
c = complex.(zeros(size(x)));
for j=1:N
   for i=1:N
     c[j] += sinx[i]*exp(-im*2*pi*(i-1)*(j-1)/N);
   end
end

```

and I see the same result as the (incorrect) Fourier Representation plot above. Perhaps this indicates that the problem isn’t in me misunderstanding the FFTW library, but rather misunderstanding the math here?

---

<div class="post-metadata">

**Author:** ![Abhijit\_Chowdhary](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abhijit_chowdhary/32/29227_2.png) [@Abhijit\_Chowdhary](https://discourse.julialang.org/u/Abhijit_Chowdhary)\
**Post date:** [February 13, 2022, 8:41am UTC](https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331/4 "2022-02-13T08:41:38Z")

</div>

Ah, indeed that works. Indeed, I do (hazily) remember that the fft was sensitive to even/odd grid sizes and endpoints over the period but will need to look up exactly why. Also thank you for the sign convention correction.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [February 13, 2022, 10:00am UTC](https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331/5 "2022-02-13T10:00:28Z")

</div>

@Abhijit_Chowdhary, sorry but I’ve deleted my previous post as the answer was not general. Meanwhile, I am linking [this other post](https://discourse.julialang.org/t/extracting-fourier-coefficients-of-an-arbitrary-periodic-signal/51036/8) where the Fourier coefficients were written more carefully by following their definition.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [February 13, 2022, 4:12pm UTC](https://discourse.julialang.org/t/trying-to-understand-what-fft-returns-to-me/76331/6 "2022-02-13T16:12:18Z")

</div>

The source of confusion might be that with FFT we need to reorder the positive and negative frequency bins with `fftshift()`.

Please check the code below where complex coefficients are used.

```julia
using FFTW, LaTeXStrings, Plots; gr()

function FourierSeries(x, fx, T)
    ck = 1/N * fftshift(fft(fx))
    n = 1 + length(x)÷2
    yr = zero(fx) .+ 0.0im
    for (i, ci) in pairs(ck)
        yr .+= ci * exp.(im*2π*(i-n)/T * x)
    end
    return real(fftshift(yr)), ck
end

N = 100 # use N even
x = LinRange(-π, π, N+1)[1:N]
T = 2π
fx = @. sin(2π*x/T) + cos(2π*4*x/T) 
fsx, ck = FourierSeries(x, fx, T) 

p1 = plot(xlabel=L"x \in [-\pi,\pi]", legend=:topleft)
plot!(x, fx, lw=3, label="f(x)")
plot!(x, fsx, lw=1, lc=:black, ls=:dash, label="Fourier Series")
xp = 2π*(-N÷2:N÷2-1)/T
p2 = plot(xp, real.(ck), st=:stem, lc=:blue, label="Real(ck)")
plot!(xp, imag.(ck), st=:stem, lc=:red, xlabel="k", label="Imag(ck)")
plot(p1,p2)

```

 ![FFT_and_complex_Fourier_coefficients_test](https://global.discourse-cdn.com/julialang/original/3X/6/8/68fd46a60ed55e9b3b21a849e54082df553238fd.png)