The Fast Fourier Transform $y[k]$ of length $N$ of the length-$N$ sequence $x[n]$ is defined as:

$$y[k] = \sum_{n=0}^{N-1}e^{-2\pi i \frac{k n}{N}}x[n].$$

I want to know how are the $y[k]$ related to the first $N$ fourier coefficients $a_0, a_n, b_n$:

$$x(t) \approx \frac{a_0}{2} + \sum_{n=0}^N\left(a_n\cos\frac{2\pi n t}{L} + b_n\sin\frac{2\pi n t}{L}\right).$$

I appreciate your help. Computationally it is faster to use the discrete fourier transform rather than integrating each $a_n,b_n$.

  • $\begingroup$ The cos-sin expansion is only used for real-valued functions. Is your vector $x$ real? $\endgroup$ – Friedrich Philipp Mar 22 '16 at 23:24
  • $\begingroup$ @FriedrichPhilipp yes, a real function $\endgroup$ – Vladimir Vargas Mar 22 '16 at 23:41

By the inverse discrete Fourier transform, we have $$ x[k] = \frac 1 N\sum_{j=0}^{N-1} y[j]e^{2\pi i\frac{jk}N}. $$ Since $x$ is real, $x[k] = \frac 1 2(x[k] + \overline{x[k]})$. Thus, \begin{align*} x[k] &= \frac 1 {2N}\sum_{j=0}^{N-1}\left(y[j]e^{2\pi i\frac{jk}N} + \overline{y[j]}e^{-2\pi i\frac{jk}N}\right)\\ &= \frac 1 N\sum_{j=0}^{N-1}\left(\operatorname{Re}y[j]\cos\left(2\pi\frac{jk}N\right) - \operatorname{Im}y[j]\sin\left(2\pi\frac{jk}N\right)\right). \end{align*} Hence, if we define $$ x(t) = \frac{y[0]}N + \sum_{j=1}^{N-1}\left(\frac{\operatorname{Re}y[j]}{N}\cos\left(2\pi jt\right) - \frac{\operatorname{Im}y[j]}{N}\sin\left(2\pi jt\right)\right), $$ then $x(k/N) = x[k]$. Hence, the trigonometric polynomial $x(t)$ is an interpolating polynomial of the (equidistant) data $\{(k/N,x[k]) : k=0,\ldots,N-1\}$.

  • $\begingroup$ @Vladimir Vargas Was it that what you were looking for? If yes, please check. $\endgroup$ – Friedrich Philipp Mar 23 '16 at 14:03
  • $\begingroup$ Yes, unfortunately my code implementation does not yield equality between the fourier coefficients and the transformed sample points. $\endgroup$ – Vladimir Vargas Mar 23 '16 at 18:29

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.