9
$\begingroup$

I use spectral Fourier methods to numerically solve PDEs and these methods make heavy use of the discrete Fourier transform (DFT). With respect to the DFT I have some issues understanding the discrete time domain effect of phase-shifts in the discrete frequency domain. My question is somewhat related to this post on DSP Stackexchange, but the answers to that post do not really address my questions.

In what follows I'll use the following definitions: Let $t \in \mathbb{R}$ and let $f(t)$ be a real function with periodicity T>0, i.e. $f(t+T) = f(t)$. Sampling one period of $f(t)$ at $N$ equidistant points, say $t_n = n \frac{T}{N}$ where $n=0, 1, \dots N-1$, gives us the data pairs $(t_n, f_n=f(t_n))$ from which we form the sequence $f_n$ of $N$ real numbers. We define the DFT of $f_n$ as another sequence of N complex numbers given by \begin{equation} F_k = \sum_{n=0}^{N-1} f_n e^{-2 \pi i n k / N} \end{equation} where $k=0, 1, \dots N-1$. Further we define the inverse DFT of $F_k$ as \begin{equation} f_n = \frac{1}{N}\sum_{k=0}^{N-1} F_k e^{2 \pi i n k / N} \end{equation} I will refer to $F_k$ as the frequency domain and to $f_n$ as the time domain representation. Further I will use the symbol $f_n \leftrightarrow F_k$ to denote that $f_n$ and $F_k$ are DFT pairs.

Now the shift theorem says (see e.g. Beerends et al., 'Fourier and Laplace Transforms', p.366):

Suppose $f_n \leftrightarrow F_k$. Then for integer $l$ one has $f_{n-l} \leftrightarrow e^{-2 \pi i l k/N}F_k$.

So far so good, I can understand this and follow the proof offered in the above mentioned reference. Also, playing around with some artificially generated $f_n$ and integer phase shifts in frequency domain exhibits the expected behavior, see e.g. example figure with integer phase shift below

My questions now concern the case where the phase shift in frequency domain is done with noninteger $l$. For example, if we take $l=\frac{3}{2}$, multiply $F_k$ by $e^{-2 \pi i \frac{3}{2} k/N}$ and transform to time domain we get back an other sequence $f_n$. In this case $f_n$ is not simply obtained from a circular shift and it seems that the DFT does some kind of interpolation to obtain $f_n$, see e.g. example figure with noninteger shift below My guess is that it uses the trigonometric polynomial of the inverse DFT to interpolate, but I couldn't find a good reference to confirm (or falsify) this guess and characterize the interpolation.

So here are my questions for you:

  1. What does the inverse DFT do to construct $f_n$ in case of a noninteger phase shift in frequency domain?
  2. In case the inverse DFT interpolates, can we somehow estimate or bound the interpolation error?
  3. In case the inverse DFT interpolates, how is this different from zero-padding the frequency domain to interpolate (see e.g. answer to this post)?

Any help is greatly appreciated. If possible, it would be great if you can include pointers to references in your answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.