# Obtain Fourier Coefficients from Discrete Fourier Transform

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$.

• The cos-sin expansion is only used for real-valued functions. Is your vector $x$ real? – Friedrich Philipp Mar 22 '16 at 23:24
• @FriedrichPhilipp yes, a real function – 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\}$.