Fast Fourier Series Evaluation for Bandlimited Periodic Signals¶

Theory¶

Let \(\phi: \mathbb{R} \to \mathbb{C}\) be a \(T\)-periodic function of bandwidth \(N_{FS} = 2 N + 1\). Then \(\phi\) is fully characterized by its \(N_{FS}\) Fourier Series coefficients \(\{\phi_{k}^{FS}, k = -N, \ldots, N\}\) such that

(1)¶\[\phi(t) = \sum_{k = -N}^{N} \phi_{k}^{FS} \exp\left( j \frac{2 \pi}{T} k t \right),\]

where \(\{\phi_{k}^{FS}, k = -N, \ldots, N\}\) is defined as

(2)¶\[\phi_{k}^{FS} = \frac{1}{T} \int_{T_{c} - \frac{T}{2}}^{T_{c} + \frac{T}{2}} \phi(t) \exp\left( -j \frac{2 \pi}{T} k t \right) dt,\]

with \(T_{c}\) being one of \(\phi\)’s period mid-points.

Computing the \(\phi_{k}^{FS}\) with (2) can be prohibitive when closed-form solutions are unavailable. However, it is possible to calculate the FS coefficients exactly from \(N_{s} = N_{FS} + Q\) judiciously-placed samples of \(\phi\), where \(Q \in \mathbb{N}\) can be arbitrarily chosen.

\(N_{s} \in 2 \mathbb{N} + 1\)¶

Theorem

Let \(\phi: \mathbb{R} \to \mathbb{C}\) be a \(T\)-periodic function of bandwidth \(N_{FS} = 2 N + 1\), with

\(T_{c}\): mid-point of one period,
\(\{\phi_{k}^{FS}, k = -N, \ldots, N\}\): Fourier Series coefficients of \(\phi\).

Moreover, let \(Q \in 2 \mathbb{N}\) be an arbitrary even integer such that

\(N_{s} = N_{FS} + Q\),
\(M = (N_{s} - 1) / 2\).

Then the following holds:

\[ \begin{align}\begin{aligned}\Phi & = N_{s} \text{iDFT}_{N_{s}}\left\{ \Phi^{FS} \circ B_{1}^{E_{1}} \right\} \circ B_{2}^{N E_{2}},\\\Phi^{FS} & = \frac{1}{N_{s}} \text{DFT}_{N_{s}}\left\{ \Phi \circ B_{2}^{- N E_{2}} \right\} \circ B_{1}^{- E_{1}},\end{aligned}\end{align} \]

where \(\text{(i)DFT}\) is as defined in The Discrete Fourier Transform and

\[ \begin{align}\begin{aligned}\Phi & = \left[ \phi(t[0]), \ldots, \phi(t[M]), \phi(t[-M]), \ldots, \phi(t[-1]) \right] \in \mathbb{C}^{N_{s}},\\\Phi^{FS} & = \left[ \phi_{-N}^{FS}, \ldots, \phi_{N}^{FS}, 0, \ldots, 0 \right] \in \mathbb{C}^{N_{s}},\\E_{1} & = \left[ -N, \ldots, N, 0, \ldots, 0 \right] \in \mathbb{Z}^{N_{s}},\\E_{2} & = \left[ 0, \ldots, M, -M, \ldots, -1 \right] \in \mathbb{Z}^{N_{s}},\\t[n] & = \left( T_{c} + \frac{T}{N_{s}} n \right) 1_{[-M, \ldots, M]}[n],\\B_{1} & = \exp\left( j \frac{2 \pi}{T} T_{c} \right),\\B_{2} & = \exp\left( -j \frac{2 \pi}{N_{s}} \right).\end{aligned}\end{align} \]

\(N_{s} \in 2 \mathbb{N}\)¶

Theorem

Let \(\phi: \mathbb{R} \to \mathbb{C}\) be a \(T\)-periodic function of bandwidth \(N_{FS} = 2 N + 1\), with

\(T_{c}\): mid-point of one period,
\(\{\phi_{k}^{FS}, k = -N, \ldots, N\}\): Fourier Series coefficients of \(\phi\).

Moreover, let \(Q \in 2 \mathbb{N} + 1\) be an arbitrary odd integer such that

\(N_{s} = N_{FS} + Q\),
\(M = N_{s} / 2\).

Then the following holds:

\[ \begin{align}\begin{aligned}\Phi & = N_{s} \; \text{iDFT}_{N_{s}}\left\{ \Phi^{FS} \circ B_{1}^{E_{1}} \right\} \circ B_{2}^{N E_{2}},\\\Phi^{FS} & = \frac{1}{N_{s}} \text{DFT}_{N_{s}}\left\{ \Phi \circ B_{2}^{- N E_{2}} \right\} \circ B_{1}^{- E_{1}},\end{aligned}\end{align} \]

where \(\text{(i)DFT}\) is as defined in The Discrete Fourier Transform and

\[ \begin{align}\begin{aligned}\Phi & = \left[ \phi(t[0]), \ldots, \phi(t[M - 1]), \phi(t[-M]), \ldots, \phi(t[-1]) \right] \in \mathbb{C}^{N_{s}},\\\Phi^{FS} & = \left[ \phi_{-N}^{FS}, \ldots, \phi_{N}^{FS}, 0, \ldots, 0 \right] \in \mathbb{C}^{N_{s}},\\E_{1} & = \left[ -N, \ldots, N, 0, \ldots, 0 \right] \in \mathbb{Z}^{N_{s}},\\E_{2} & = \left[ 0, \ldots, M - 1, -M, \ldots, -1 \right] \in \mathbb{Z}^{N_{s}},\\t[n] & = \left( T_{c} + \frac{T}{N_{s}} \left[ \frac{1}{2} + n \right] \right) 1_{[-M, \ldots, M - 1]}[n],\\B_{1} & = \exp\left( j \frac{2 \pi}{T} \left[ T_{c} + \frac{T}{2 N_{s}} \right] \right),\\B_{2} & = \exp\left( -j \frac{2 \pi}{N_{s}} \right).\end{aligned}\end{align} \]

Proof(s)

Replace \(t[n]\) in (1) and rearrange terms.

Extension to multi-dimensional case¶

For a multi-dimensional signal \(\phi: \mathbb{R}^D \to \mathbb{C}\) that is \([T_1, T_2, \ldots, T_D]\)-periodic and \([N_{FS, 1}, N_{FS, 2}, \ldots, N_{FS, D}]\)-bandlimited, we can obtain its Fourier Series coefficients by applying the above approach along each dimension.

Implementation Notes¶

ffs() and iffs() can be used to obtain Fourier Series coefficients / spatial samples of a function using the algorithms above. Due to the reliance on \(\text{(i)DFT}_{N_{s}}\), it is recommended to choose \(N_{s}\) highly-composite.

ffsn() and iffsn() can be used to obtain Fourier Series coefficients / spatial samples of a \(D\)-dimensional function. In our implementation, we opt for a more efficient approach than applying the above method along each dimension.