Discrete Fourier series

In digital signal processing, the term Discrete Fourier series (DFS) is any periodic discrete-time signal comprising harmonically-related (i.e. Fourier) discrete real sinusoids or discrete complex exponentials, combined by a weighted summation. A specific example is the inverse discrete Fourier transform (inverse DFT).

Definition

The general form of a DFS is:

Discrete Fourier series

${\displaystyle {\begin{aligned}x[n]=\sum _{k}X[k]\cdot e^{i2\pi {\frac {k}{N}}n},\quad n\in \mathbb {Z} ,\end{aligned}}}$

(Eq.1)

which are harmonics of a fundamental frequency ${\displaystyle 1/N,}$ for some positive integer ${\displaystyle N.}$ The practical range of ${\displaystyle k,}$ is ${\displaystyle [0,\ N-1],}$ because periodicity causes larger values to be redundant. When the ${\displaystyle X[k]}$ coefficients are derived from an ${\displaystyle N}$-length DFT, and a factor of ${\displaystyle 1/N}$ is inserted, this becomes an inverse DFT. ^{[1] : p.542 (eq 8.4)   [2] : p.77 (eq 4.24)} And in that case, just the coefficients themselves are sometimes referred to as a discrete Fourier series. ^{[3] : p.85 (eq 15a)}

Example

A common practice is to create a sequence of length ${\displaystyle N}$ from a longer ${\displaystyle x[n]}$ sequence by partitioning it into ${\displaystyle N}$-length segments and adding them together, pointwise.(see DTFT § L=N×I) That produces one cycle of the periodic summation :

${\displaystyle x_{_{N}}[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }x[n-mN],\quad n\in \mathbb {Z} .}$

Because of periodicity, ${\displaystyle x_{_{N}}}$can be represented as a DFS with ${\displaystyle N}$ unique coefficients that can be extracted by an ${\displaystyle N}$-length DFT. ^{[1] : p 543 (eq 8.9) : pp 557-558    [2] : p 72 (eq 4.11)}

${\displaystyle {\begin{aligned}&x_{_{N}}[n]={\frac {1}{N}}\sum _{k=0}^{N-1}X_{N}[k]\cdot e^{i2\pi {\tfrac {k}{N}}n};\quad n\in \mathbb {Z} &&{\text{DFS}}\\&X_{N}[k]\triangleq \sum _{n=0}^{N-1}x_{_{N}}[n]\cdot e^{-i2\pi {\tfrac {k}{N}}n};\quad k\in [0,N-1]&&{\text{DFT}}\end{aligned}}}$

The coefficients are useful because they are also samples of the discrete-time Fourier transform (DTFT) of the ${\displaystyle x[n]}$ sequence:

${\displaystyle X_{1/T}(f)\triangleq \sum _{n=-\infty }^{\infty }e^{-i2\pi fnT}\ T\ x(nT)=\sum _{m=-\infty }^{\infty }X\left(f-{\tfrac {m}{T}}\right),\quad f\in \mathbb {R} }$

Here, ${\displaystyle x(nT)}$ represents a sample of a continuous function ${\displaystyle x(t),}$ with a sampling interval of ${\displaystyle T,}$ and ${\displaystyle X(f)}$ is the Fourier transform of ${\displaystyle x(t).}$ The equality is a result of the Poisson summation formula. With definitions ${\displaystyle x[n]\triangleq T\ x(nT)}$ and ${\displaystyle X[k]\triangleq X_{1/T}\left({\tfrac {k}{NT}}\right)}$:

${\displaystyle X[k]=\sum _{n=-\infty }^{\infty }e^{-i2\pi {\tfrac {k}{N}}n}\ x[n];\quad k\in \mathbb {Z} .}$

Due to the ${\displaystyle N}$-periodicity of the ${\displaystyle e^{-i2\pi {\tfrac {k}{N}}n}}$ kernel, the summation can be "folded" as follows:

${\displaystyle {\begin{aligned}X[k]&=\sum _{m=-\infty }^{\infty }\left(\sum _{n=0}^{N-1}e^{-i2\pi {\tfrac {k}{N}}n}\ x[n-mN]\right)\\&=\sum _{n=0}^{N-1}e^{-i2\pi {\tfrac {k}{N}}n}\underbrace {\left(\sum _{m=-\infty }^{\infty }x[n-mN]\right)} _{x_{_{N}}[n]}\\&=X_{N}[k].\end{aligned}}}$

References

1. Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. (1999). "4.2, 8.4". Discrete-time signal processing (2nd ed.). Upper Saddle River, N.J.: Prentice Hall. ISBN   0-13-754920-2. samples of the Fourier transform of an aperiodic sequence x[n] can be thought of as DFS coefficients of a periodic sequence obtained through summing periodic replicas of x[n]. ... The Fourier series coefficients can be interpreted as a sequence of finite length for k=0,...,(N-1), and zero otherwise, or as a periodic sequence defined for all k.
2. Prandoni, Paolo; Vetterli, Martin (2008). Signal Processing for Communications (PDF) (1 ed.). Boca Raton,FL: CRC Press. pp. 72, 76. ISBN   978-1-4200-7046-0 . Retrieved 4 October 2020. the DFS coefficients for the periodized signal are a discrete set of values for its DTFT
3. Nuttall, Albert H. (Feb 1981). "Some Windows with Very Good Sidelobe Behavior". IEEE Transactions on Acoustics, Speech, and Signal Processing. 29 (1): 84–91. doi:10.1109/TASSP.1981.1163506.