# dft shifting theorem

DFT shifting theorem makes a statement about phase shift.

If $$g[n] = f[n - x mod N]$$ where x is a integer number of samples and N is the total length of the signal, then

$$G[m] = F[m] \cdot e^{-j 2 \pi \frac{m}{N} x}$$

Since $$g$$ is the circular shift of $$f$$, this has implications in the proof for the convolution theorem.

The fraction $$\frac{m}{N}$$ is essentially the frequency of the FFT, which is related to the periodicity of the sequence. In python, this can be computed with np.fft.fftfreq(len(f)). Don't divide by $$N$$ again though, numpy does this internally. Actually, a simple arange will work just as well because of the modular nature of the root of unity, however getting a hermitian sequence is convenient.

If a signal is circularly shifted, magnitude of DFT spectrum is unchanged.

## 2. Proof

We'll begin with a signal, $$x[n]$$ and the signal shifted by d samples, $$x[n - d]$$. Also, for simplicity and because it's not relevant, let $$f$$ be the frequency of the DFT, or $$\frac{m}{N}$$ Now, the DFT of the shifted signal is

$$X_{shift} = \sum_{n=0}^{N-1} x[n-d] \cdot e^{-j*2\pi*f*n}$$

Now, let $$k = n - d$$, and thus also $$n = (k + d)$$. The lower bound of $$n=0$$ becomes $$k = 0 - d = -d$$, and the upper bound of $$N-1$$ becomes $$N - 1 - d$$.

\begin{align*} X_{shift} &= \sum_{k = -d}^{N-1-d} x[k] \cdot e^{-j*2\pi*f*(k + d)} \\ &= \sum_{k = -d}^{N-1-d} x[k] \cdot e^{-j*2\pi*f*k} \cdot e^{-j*2\pi*f*d} \\ &= e^{-j*2\pi*f*d} \cdot \sum_{k = -d}^{N-1-d} x[k] \cdot e^{-j*2\pi*f*k} &&\text{d is constant over sum} \\ &= e^{-j*2\pi*f*d} \cdot X[m] \\ \end{align*}

This comes from the fact that since $$x$$ is $N$-periodic (and so wraps around the edges), it doesn't matter where we start the summation from, it will still compute the same DFT because its still over one period of the waveform.

$$\sum_{n=0}^{N-1} x[n] = \sum_{n=\Delta}^{N-1+\Delta} x[n] \text{when x is N-periodic}$$