Discrete Fourier Series (DFS) Discrete Fourier Series (DFS)
What is the Discrete Fourier Series?
The core idea of the Discrete Fourier Series (DFS) is to represent a periodic discrete-time signal as a sum of complex exponentials. In other words, an $N$-periodic signal $x[n]$ can be expressed as a sum of complex exponentials at harmonic frequencies.
Each complex exponential represents a different frequency component. By combining these components with appropriate magnitudes and phases, we can reconstruct the original periodic signal.
The blue periodic signal is decomposed into three sinusoids of different frequencies.
Harmonic Basis
The basis functions used in the DFS are
\[e^{j\frac{2\pi k}{N}n} \,,\qquad k=0,1,\dots,N-1\]where $2\pi k/N$ is the angular frequency of the $k$-th harmonic.
Since $n$ is integer, $e^{j2\pi n}=1$. Therefore,
\[e^{j\frac{2\pi (k+N)}{N}n} = e^{j\frac{2\pi k}{N}n} \cdot e^{j2\pi n} = e^{j\frac{2\pi k}{N}n}\]Thus, the indices $k$ and $k+N$ correspond to the same complex exponential, which means that there are only $N$ distinct harmonic basis functions.
DFS Representation
The DFS provides a pair of equations that convert between the time-domain representation $\tilde{x}[n]$ and the frequency-domain representation $\tilde{X}[k]$.
\[\tilde{x}[n] \quad\longleftrightarrow\quad \tilde{X}[k]\]Synthesis Equation: Frequency → Time
Suppose we know the frequency-domain representation $\tilde{X}[k]$. We can construct the original periodic signal $\tilde{x}[n]$ by combining the harmonic complex exponentials with appropriate weights. This is described by the DFS synthesis equation:
\[\tilde{x}[n] = \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j\frac{2\pi k}{N}n} \tag{1}\]where $\tilde{X}[k]$ is the Fourier coefficient associated with the $k$-th harmonic. It determines how strongly that harmonic contributes to the original signal, as well as its phase. For example, if $\tilde{X}[2]$ is large, the frequency component corresponding to $k=2$ makes a strong contribution to the original signal.
In other words, rather than treating a complicated periodic signal as a whole, the DFS allows us to view it in terms of which frequency components are present and how strongly each one contributes.
Analysis Equation: Time → Frequency
Conversely, suppose we know the periodic signal $\tilde{x}[n]$ and want to find how much of each harmonic it contains. This is described by the DFS analysis equation:
\[\tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j\frac{2\pi k}{N}n} \tag{2}\]This sum is the inner product of $\tilde{x}[n]$ with the $k$-th harmonic over one period. It measures how much of the $k$-th harmonic is contained in the signal. For example, if $\tilde{x}[n]$ oscillates mostly at the frequency of the $k=2$ harmonic, then $\tilde{X}[2]$ is large while the other coefficients are small.
Why Do the Two Equations Form a Pair?
The synthesis equation $\small(1)$ builds $\tilde{x}[n]$ from the coefficients $\tilde{X}[k]$. The analysis equation $\small(2)$ gets those same coefficients back from $\tilde{x}[n]$. But why does multiplying by $e^{-j(2\pi k/N)n}$ and summing over one period give exactly $\tilde{X}[k]$?
The reason is that different harmonics are orthogonal to one another. This means that if we multiply one harmonic by the conjugate of another and add the products over one period, the result is $0$. (The conjugate of $e^{j\theta}$ is $e^{-j\theta}$, so the conjugate of the $k$-th harmonic is $e^{-j(2\pi k/N)n}$.) It is like two perpendicular vectors, whose dot product is $0$.
Let us check this. Multiply the $r$-th harmonic by the conjugate of the $k$-th harmonic, $e^{-j(2\pi k/N)n}$, and add over one period:
\[\sum_{n=0}^{N-1} e^{j\frac{2\pi(r-k)}{N}n} = \begin{cases} N \,, & r=k \\ 0 \,, & r\not=k \end{cases}\]- If $r=k$, every term is $1$, so the sum is $N$.
- If $r\not=k$, the terms turn around the unit circle in equal steps, so they cancel each other out.
The eight terms for $N=8$. When $r\neq k$ (above), they come back to where they started when added head to tail, so the sum is $0$. When $r=k$ (below), they all point the same way, so the sum is $N$.
Now substitute the synthesis equation $\small(1)$ into the right-hand side of the analysis equation $\small(2)$:
\[\begin{aligned} \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j\frac{2\pi k}{N}n} &= \sum_{n=0}^{N-1} \left( \frac{1}{N} \sum_{r=0}^{N-1} \tilde{X}[r] e^{j\frac{2\pi r}{N}n} \right) e^{-j\frac{2\pi k}{N}n} \\ &= \sum_{r=0}^{N-1} \tilde{X}[r] \left( \frac{1}{N} \sum_{n=0}^{N-1} e^{j\frac{2\pi(r-k)}{N}n} \right) \\ &= \tilde{X}[k] \end{aligned}\]By orthogonality, the term in parentheses is $1$ when $r=k$ and $0$ otherwise, so only the $r=k$ term survives. This is why the harmonic components can be separated without interfering with one another.
Understanding $\tilde{X}[k]$
Time Domain vs. Frequency Domain
The DFS provides two different representations of the same periodic signal. In the time domain, $\tilde{x}[n]$ describes the value of the signal at each discrete-time index $n$. In the frequency domain, $\tilde{X}[k]$ describes the magnitude and phase associated with each harmonic frequency $2\pi k/N$.
In other words, rather than treating a complicated periodic signal as a whole, the DFS allows us to view it in terms of which frequency components are present and how strongly each one contributes. Neither view ontains more information than the other, since the analysis and synthesis equations convert between them without any loss.
The same signal seen from two directions. From the time axis, we see its values over time. From the frequency axis, we see how strongly each frequency is present.
Periodicity in Frequency Index
Since $\tilde{x}[n]$ is $N$-periodic, $\tilde{x}[n+N]=\tilde{x}[n]$. Interestingly, its DFS coefficients are also $N$-periodic with respect to the frequency index $k$:
\[\tilde{X}[k+N]=\tilde{X}[k]\]This does not come from the periodicity of $\tilde{x}[n]$, but from the fact that $n$ is an integer. As shown in the harmonic basis, the indices $k$ and $k+N$ correspond to the same complex exponential, so they must have the same coefficient.
Why is $X[k]$ also $N$-periodic?
Starting from the analysis equation,
\[X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi k}{N}n}\]replace $k$ with $k+N$:
\[X[k+N] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi (k+N)}{N}n}\]Since,
\[e^{-j\frac{2\pi (k+N)}{N}n} = e^{-j\frac{2\pi k}{N}n}\]we obtain
\[X[k+N] = X[k]\]Therefore, only one period of $\tilde{x}[n]$ and $N$ distinct Fourier coefficients $\tilde{X}[0],\dots,\tilde{X}[N-1]$ are needed to completely represent the signal.
This periodicity also tells us how to read the frequency index. Recall from the post on complex exponentials that the frequencies near $\omega=0$ and $\omega=2\pi$ are low, and that the highest frequency is $\omega=\pi$. Since $\omega_k=2\pi k/N$, the indices near $k=0$ and $k=N$ both correspond to low frequencies, and the highest frequency is located in the middle, at $k=N/2$. In particular, $k=0$ is the DC component: $\tilde{X}[0]=\sum_{n=0}^{N-1}\tilde{x}[n]$ is $N$ times the average value of the signal.
Magnitude and Phase
Since $\tilde{X}[k]$ is a complex number, it can be written in polar form:
\[\tilde{X}[k] = \lvert\tilde{X}[k]\rvert \, e^{j\angle\tilde{X}[k]}\]Substituting this into the synthesis equation $\small(1)$, the $k$-th term becomes
\[\frac{1}{N} \lvert\tilde{X}[k]\rvert \, e^{j\left(\frac{2\pi k}{N}n + \angle\tilde{X}[k]\right)}\]Thus, the magnitude $\lvert\tilde{X}[k]\rvert$ determines the amplitude of the $k$-th harmonic, and the phase $\angle\tilde{X}[k]$ determines how far it is shifted. Plotting them against $k$ gives the magnitude spectrum and the phase spectrum.
For example, the amplitude of a sinusoid appears in the magnitude of its coefficients, and its phase shift appears in their phase.
For a real signal, the magnitude spectrum is even and the phase spectrum is odd:
\[\lvert\tilde{X}[N-k]\rvert = \lvert\tilde{X}[k]\rvert \,,\qquad \angle\tilde{X}[N-k] = -\angle\tilde{X}[k]\]Why is the magnitude even and the phase odd?
Take the complex conjugate of the analysis equation. Since $\tilde{x}[n]$ is real, only the exponential changes:
\[\tilde{X}^*[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{j\frac{2\pi k}{N}n} = \tilde{X}[-k] = \tilde{X}[N-k]\]A complex number and its conjugate have the same magnitude and opposite phases.
Example: DFS coefficients of a cosine
Consider a single sinusoid with $0<k_0<N/2$:
\[\tilde{x}[n] = A\cos\left(\frac{2\pi k_0}{N}n + \phi\right) = \frac{A}{2} e^{j\phi} e^{j\frac{2\pi k_0}{N}n} + \frac{A}{2}e^{-j\phi}e^{-j\frac{2\pi k_0}{N}n}\]The signal contains only two harmonics, $k=k_0$ and $k=-k_0$. Since $k=-k_0$ is equivalent to $k=N-k_0$, only two terms of the synthesis equation $\small(1)$ remain:
\[\frac{A}{2}e^{j\phi}e^{j\frac{2\pi k_0}{N}n} + \frac{A}{2}e^{-j\phi}e^{-j\frac{2\pi k_0}{N}n} = \frac{1}{N} \tilde{X}[k_0] e^{j\frac{2\pi k_0}{N}n} + \frac{1}{N} \tilde{X}[N-k_0] e^{j\frac{2\pi (N-k_0)}{N}n}\]Comparing the coefficients of each harmonic,
\[\tilde{X}[k_0] = \frac{NA}{2}e^{j\phi} \,,\qquad \tilde{X}[N-k_0] = \frac{NA}{2}e^{-j\phi}\]and all other coefficients within one period are zero. The amplitude $A$ appears in the magnitude, and the phase shift $\phi$ appears in the phase. Notice also that the two coefficients have the same magnitude and opposite phases.
DFS Properties
Throughout this section, all signals have the same period $N$.
Linearity
The DFS of a sum is the sum of the DFS coefficients:
\[a\tilde{x}_1[n] + b\tilde{x}_2[n] \quad\longleftrightarrow\quad a\tilde{X}_1[k] + b\tilde{X}_2[k]\]This follows directly from the analysis equation $\small(2)$, because a sum can be split term by term. Linearity lets us analyze a complicated signal by breaking it into simple parts.
Time Shift
Shifting a signal in time changes only the phase of its coefficients:
\[\tilde{x}[n-m] \quad\longleftrightarrow\quad e^{-j\frac{2\pi k}{N}m} \tilde{X}[k]\]The factor $e^{-j(2\pi k/N)m}$ has magnitude $1$, so the magnitude spectrum does not change. Only the phase changes, by $-(2\pi k/N)m$. This amount is proportional to $k$: a higher harmonic turns more for the same shift.
Why does a time shift change only the phase?
Apply the analysis equation $\small(2)$ to the shifted signal and let $l=n-m$:
\[\begin{aligned} \sum_{n=0}^{N-1} \tilde{x}[n-m] e^{-j\frac{2\pi k}{N}n} &= \sum_{l=-m}^{N-1-m} \tilde{x}[l] e^{-j\frac{2\pi k}{N}(l+m)} \\ &= e^{-j\frac{2\pi k}{N}m} \sum_{l=-m}^{N-1-m} \tilde{x}[l] e^{-j\frac{2\pi k}{N}l} \end{aligned}\]The terms of the last sum are $N$-periodic in $l$, so a sum over any $N$ consecutive samples gives the same value. Therefore, the last sum is $\tilde{X}[k]$.
Frequency Shift
Multiplying a signal by a harmonic shifts its coefficients:
\[e^{j\frac{2\pi k_0}{N}n} \tilde{x}[n] \quad\longleftrightarrow\quad \tilde{X}[k-k_0]\]This is the counterpart of the time shift. A shift in one domain is a multiplication by a complex exponential in the other.
Why does multiplying by a harmonic shift the coefficients?
Apply the analysis equation $\small(2)$ to the product:
\[\sum_{n=0}^{N-1} e^{j\frac{2\pi k_0}{N}n} \tilde{x}[n] e^{-j\frac{2\pi k}{N}n} = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j\frac{2\pi (k-k_0)}{N}n} = \tilde{X}[k-k_0]\]Convolution
For periodic signals, convolution is taken over one period only. This is called periodic convolution:
\[\tilde{y}[n] = \sum_{m=0}^{N-1} \tilde{x}_1[m] \, \tilde{x}_2[n-m]\]The sum cannot run over all $m$, because a periodic signal never decays and the sum would not converge.
Periodic convolution in time becomes multiplication in frequency:
\[\sum_{m=0}^{N-1} \tilde{x}_1[m] \, \tilde{x}_2[n-m] \quad\longleftrightarrow\quad \tilde{X}_1[k] \, \tilde{X}_2[k]\]Each harmonic of the result is simply the product of the same harmonic of the two signals.
Why does periodic convolution become multiplication?
Apply the analysis equation to $\tilde{y}[n]$ and change the order of the two sums:
\[\begin{aligned} \sum_{n=0}^{N-1} \tilde{y}[n] e^{-j\frac{2\pi k}{N}n} &= \sum_{m=0}^{N-1} \tilde{x}_1[m] \left( \sum_{n=0}^{N-1} \tilde{x}_2[n-m] e^{-j\frac{2\pi k}{N}n} \right) \end{aligned}\]By the time shift property, the sum in parentheses is $e^{-j(2\pi k/N)m}\tilde{X}_2[k]$. Therefore,
\[\sum_{n=0}^{N-1} \tilde{y}[n] e^{-j\frac{2\pi k}{N}n} = \tilde{X}_2[k] \sum_{m=0}^{N-1} \tilde{x}_1[m] e^{-j\frac{2\pi k}{N}m} = \tilde{X}_1[k] \, \tilde{X}_2[k]\]Parseval’s Relation
The energy of one period can be computed in either domain:
\[\sum_{n=0}^{N-1} \lvert\tilde{x}[n]\rvert^2 = \frac{1}{N} \sum_{k=0}^{N-1} \lvert\tilde{X}[k]\rvert^2\]The left side adds the energy of each sample, and the right side adds the energy of each harmonic. Thus, $\lvert\tilde{X}[k]\rvert^2$ tells us how much of the energy of the signal belongs to the $k$-th harmonic.
Why are the two sums equal?
Write $\lvert\tilde{x}[n]\rvert^2=\tilde{x}[n]\,\tilde{x}^{\ast}[n]$ and replace $\tilde{x}^{\ast}[n]$ with the complex conjugate of the synthesis equation:
\[\begin{aligned} \sum_{n=0}^{N-1} \tilde{x}[n] \, \tilde{x}^*[n] &= \sum_{n=0}^{N-1} \tilde{x}[n] \left( \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}^*[k] e^{-j\frac{2\pi k}{N}n} \right) \\ &= \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}^*[k] \left( \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j\frac{2\pi k}{N}n} \right) \\ &= \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}^*[k] \, \tilde{X}[k] \end{aligned}\]Summary
| Property | Time domain | Frequency domain |
|---|---|---|
| Linearity | $a\tilde{x}_1[n]+b\tilde{x}_2[n]$ | $a\tilde{X}_1[k]+b\tilde{X}_2[k]$ |
| Time Shift | $\tilde{x}[n-m]$ | $e^{-j(2\pi k/N)m}\tilde{X}[k]$ |
| Frequency Shift | $e^{j(2\pi k_0/N)n}\tilde{x}[n]$ | $\tilde{X}[k-k_0]$ |
| Periodic Convolution | $\sum_{m=0}^{N-1}\tilde{x}_1[m]\,\tilde{x}_2[n-m]$ | $\tilde{X}_1[k]\,\tilde{X}_2[k]$ |
| Parseval’s Relation | $\sum_{n=0}^{N-1}\lvert\tilde{x}[n]\rvert^2$ | $\frac{1}{N}\sum_{k=0}^{N-1}\lvert\tilde{X}[k]\rvert^2$ |