3

The Fourier Transform of the derivative of a continuous function f has this property:

$$ \mathcal{F}(f')=i \omega \, \mathcal{F}(f)$$

So is there a similar theorem in the field of Discrete Fourier Transform? So far I have not read of a corresponding theorem in the discrete case.

leonbloy
  • 63,430

3 Answers3

4

Yes, but it's not as cool. Let $f : \mathbb{Z}/n\mathbb{Z} \to \mathbb{C}$ be a function. A discrete analogue of the derivative of $f$ is the finite difference $\Delta f(x) = f(x + 1) - f(x)$. Letting $\widehat{f} : \mathbb{Z}/n\mathbb{Z} \to \mathbb{C}$ denote the discrete Fourier transform, we have

$$\widehat{f(x + 1)} = \zeta_n^y \widehat{f(x)}$$

where $\zeta_n = e^{ \frac{2 \pi i}{n} }$, and so

$$\widehat{\Delta f} = (\zeta_n^y - 1) \widehat{f}.$$

Qiaochu Yuan
  • 419,620
3

Let's considering the DTFT (the DFT is similar), with $x[n] \leftrightarrow \mathcal{F}_x(\omega)$.

Let $y[n]=x[n]-x[n-1]$ (a discrete analogous to the derivative). Then

$$\mathcal{F}_y(\omega)=\mathcal{F}_x(\omega)\left (1- e^{-i \omega} \right) $$

To see the connection, take the first order approximation: $e^{-i \omega} \approx 1 - i \omega$

leonbloy
  • 63,430
2

consider the discrete Fourier transform of a signal $x_n$ $$X_k = \sum_{n=0}^{N-1} x_n e^{-2 i \pi nk / N}$$ if $N$ is even, you get the trigonometric interpolation of $x_n$ as $$x(t) = \frac{1}{N}\sum_{k=-N/2}^{N/2-1} X_k e^{2 i \pi k t/ N}$$

so its derivative is

$$x'(t) = \frac{1}{N}\sum_{k=-N/2}^{N/2-1} \frac{2 i \pi k}{N} X_k e^{2 i \pi k t / N}$$ by sampling it you get $y_n = x'(n)$ whose discrete Fourier transform is

$$Y_k = \sum_{n=-N/2}^{N/2-1} y_n e^{-2 i \pi nk / N} = \left\{\begin{array}{ll}\frac{2 i \pi k}{N} X_k& \text{if } k < N/2 \\ \frac{2 i \pi (k-N)}{N} X_k& \text{otherwise} \end{array}\right.$$

so multiplying a discrete Fourier transform by $$H_k = \left\{\begin{array}{ll}\frac{2 i \pi k}{N} & \text{if } k < N/2 \\ \frac{2 i \pi (k-N)}{N} & \text{otherwise}\end{array}\right.$$ corresponds to taking the derivative of the trigonometric interpolation : $h_n$ the inverse discrete Fourier transform of $H_k$ is said to be a discrete derivative filter.

there are many discrete derivative filters, all with their pros and cons.

  • $[1,-1]$ is among them and has the advantage to be the simplest and the most local,

  • but $h_n$ has the advantage to be ideal if the signal to be differentiated has been sampled from a continuous (periodic) function respecting the Shannon theorem (only its $N/2$ first Fourier series coefficients are non-zeros)

reuns
  • 77,999
  • Thank you very much! Although the calculation looks a bit complicated, the idea is very intuitive. It is strange that the result obtained in this way is different from Qiaochu Yuan's. Since I am not familiar with the details trigonometric interpolation, I don't know for sure what has happened. – user314825 Feb 17 '16 at 16:06
  • @reuns I know this is an old post, but would you mind if I tested this and got back to you in a couple days? I've been trying to work on recovering the Fourier Transform of $x[n]$ using the Fourier Transform of it's derivative for about week now and this looks like what I was looking for. – Researcher R Apr 08 '23 at 20:56