Proof DFT of d/dn x[n] is proportional to jk * (DFT of x[n]) = jk * X[k]

Question

So I'm familiar with how the derivative of an aperiodic, continuous signal can be found by taking its Fourier transform, multiplying by $j \omega$, and then inverse transforming. Great explanation.

I'd like to see the analogous derivation for the DFT, to work with discrete, periodic signals. I gather the answer should be that we multiply by $j \omega_k$ where $\omega_k \in \{\frac{2\pi}{N}k\}, k\in \{0, ... N-1\}$, but, as far as I'm aware, we can no longer do the integration by parts trick in discrete time.

Would we derive the relationship first and then discretize?

Answer 1

I think this is an ill posed question. For continuous signals the derivative is defined as

$$\frac{\partial}{\partial x} f(x) = \lim_{\Delta x \to 0} \frac{f(x+\Delta x)-f(x)}{\Delta x}$$

However this definition doesn't work for discrete signals. $\lim_{\Delta n \to 0}$ is nonsensical if $n \in \mathbb{Z}$. $n$ can be 0 or 1 but it can't be anything in between.

There are various different ways to define a "discrete derivative" but they all have their pros and cons and there is no single "correct" version. Differentiation is an LTI process but it's not bandlimited. It's kind of the opposite since the amplitude rises with frequency. Any discrete implementation of a differentiator needs to manage significant amounts of aliasing.

Answer 2

I think I figured it out.

Say we have a discrete signal of length $N$, $y = [y_0, y_1, ... y_{N-1}]$.

The DFT is:

$$ a_k = \sum_{n=0}^{N-1} y_n e^{-j \frac{2\pi}{N}nk}$$ $$ = y_0 e^{-j \frac{2\pi}{N}0k} + y_1 e^{-j \frac{2\pi}{N}k} + ... + y_{N-1}e^{-j \frac{2\pi}{N}(N-1)k}$$

If I take the derivative w.r.t. $n$ right now, I'll end up multiplying by $-j\frac{2\pi}{N}k$, but this should be equivalent to multiplying by a positive due to periodicity:

We're traveling around the unit circle in the negative direction, but we could travel in the positive direction instead, because $ e^{-j \frac{2\pi}{N} n k} = e^{j \frac{2\pi}{N} (-n) k} = e^{j \frac{2\pi}{N} (-n+N) k} = e^{j (\frac{2\pi}{N} (-n) + 2\pi) k}$, and integer offsets of $2\pi$ don't change the value.

Likewise, the values of $y$ repeat, so $y_0 = y_N = y_{-N}$ and $y_{N-1} = y_{N-1-N} = y_{-1}$.

Therefore:

$$ a_k = y_{-N} e^{-j \frac{2\pi}{N}(-N)k} + y_{1-N} e^{-j \frac{2\pi}{N}(-1+N)k} + ... + y_{-1}e^{-j \frac{2\pi}{N}(-1)k} $$ $$ = y_{-N} e^{+j \frac{2\pi}{N}Nk} + y_{1-N} e^{+j \frac{2\pi}{N}(1-N)k} + ... + y_{-1}e^{+j \frac{2\pi}{N}k} $$ $$ = \sum_{n=1}^{N} y_{-n} e^{j \frac{2\pi}{N}nk}$$

Now I can take the derivative w.r.t. $n$ of this thing to get:

$$ \frac{d}{dn} a_k = \frac{d}{dn} \sum_{n=1}^{N} y_{-n} e^{j \frac{2\pi}{N}nk} = \sum_{n=1}^{N} y_{-n} \frac{d}{dn} e^{j \frac{2\pi}{N}nk} $$

because the $y_n$ are constants to the derivative.

$$ = j \frac{2\pi}{N}k \sum_{n=1}^{N} y_{-n} e^{j \frac{2\pi}{N}nk} = j \frac{2\pi}{N}k \cdot a_k$$