6.2. The DFT shifting theorem

We’ve seen that for signals $x$ which are pure sinusoids at an analysis frequency of index $m$, the corresponding DFT component $X[m]$ encodes the signal’s amplitude and phase as a single complex number.

But what can we say about phase for more general signals? In particular, if we have an arbitrary signal $x$ (not necessarily a sinusoid), what happens if we delay it?

Before we continue down this line of thought, we must first establish what it means to delay a signal under our periodicity assumption. This leads us to the notion of a circular shift.

Definition 6.1 (Circular shifting)

Let $x[n]$ be a signal of $N$ samples with DFT series $X[m]$, and define

$$y[n]=x[n-d\mathrm{mod}N]$$

to be the circular shift of $x$ by $d$ samples.

When it is clear from context that shifting is circular, we may drop the “$\mathrm{mod}N$” notation and simply write $y[n]=x[n-d]$.

Circular shifting can seem like a strange thing to do: taking samples from the end of the signal and putting them at the beginning?

However, it is a natural consequence of combining our periodicity assumption with the definition of delay.

Indeed, it can lead to some strange behaviors if $x[n]$ is discontinuous at the repetition boundaries.

Fig. 6.2 A repeating signal $x[n]$ with repetition boundaries (vertical lines) is shifted by 8 samples to produce $y[n]$; three additional repetitions are illustrated in the shaded regions. Because $x[n]$ is discontinuous at the repetition boundary, this discontinuity is shifted to the middle of $y[n]$, appearing as a large vertical gap in the signal.

Given this definition of shifting (delay), we can say the following about its effect on the DFT spectrum of a signal.

Theorem 6.1 (DFT shifting)

Let $x[n]$ be a signal with DFT spectrum $X[m]$, and let $y[n]=x[n-d]$ be the circular shift of $x$ by $d$ samples.

The DFT spectrum of $y[n]$ is given by:

$$Y[m]=X[m]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot d).$$

This says that no matter what delay we use, it’s always possible to exactly predict the spectrum of the delayed signal from the spectrum of the input signal.

The proof of the shifting theorem is purely algebraic, and relies on the periodicity assumption of $x$ to allow a change of variables in the similarity calculation.

Proof. If we have an index $n$, we will introduce a new variable $k=n-d$, and equivalently, $n=k+d$. In this case, $n=0$ corresponds to $k=-d$, and $n=N-1$ corresponds to $k=N-1-d$. Then we can calculate the DFT spectrum as follows

$$\begin{array}{rlr}Y[m]& =\sum _{n=0}^{N-1}y[n]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)& \text{By definition of DFT}\\ & =\sum _{n=0}^{N-1}x[n-d]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)& y[n]=x[n-d]\\ & =\sum _{k=-d}^{N-1-d}x[k]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot (k+d))& k=n-d\\ & =\sum _{k=-d}^{N-1-d}x[k]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot k)\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot d)& e^{a+b}=e^a\cdot e^b\\ & =\exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot d)\cdot (\sum _{k=-d}^{N-1-d}x[k]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot k))& \text{Delay factor is constant over sum}\\ & =\exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot d)\cdot X[m]& \text{by definition of DFT}.\end{array}$$

The last step follows because even though the summation ranges from $k=-d$ to $k=N-1-d$, it still computes the full DFT of $x$, just in a different order.

6.2.1. What does this do?

It’s worth taking some time to understand the shifting theorem. Not only does it say exactly how the spectrum changes, as a signal shifts in time, but the change itself is also interesting.

Note that the argument of the exponential is a purely imaginary number:

$$-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot d.$$

This means that multiplication implements a rotation of $X[m]$ in the complex plane. Its phase can change, but the magnitude must be the same.

Of course, this is exactly what we would hope should happen: delay only changes the horizontal (time) position of a signal, not its amplitude.

A slightly more subtle point is that each DFT component $X[m]$ changes by a different amount: the rotation depends on both $m$ and $d$.

Example 6.1

We can visualize the shifting theorem by examining what happens to each DFT component $X[m]$ as a test signal is circularly shifted by different amounts.

Once Loop Reflect

Fig. 6.3 Top: a test signal $x[n]$ of 16 samples is circularly shifted by successively larger amounts $d=0,1,2,\dots ,15$. Bottom subplots: each DFT component $X[m]$ ($m=0,1,2,\dots ,15$) is plotted in the complex plane. As the test signal is delayed, each DFT component rotates by an angle proportional to both the delay $d$ and frequency index $m$. The DFT components are arranged so that $X[m]$ and $X[N-m]$ can be easily compared.

Fig. 6.3 illustrates several key features of circular shifting. First, observe that the different DFT components rotate at different speeds when the delay $d$ changes. For example, for each full cycle of the $m=1$ component, the $m=2$ component makes two cycles. In each case, we can see that the magnitude of $X[m]$ is preserved, as the distance between $X[m]$ and the origin never changes.

Note also that the motion of each $X[m]$ is equal and opposite to that of $X[N-m]$ (eg, $m=1$ and $m=15$, $m=2$ and $m=14$, etc). Relatedly, the components $X[0]$ (the DC component) and $X[N/2]$ ($m=8$, the Nyquist component for $N=16$) do not seem to rotate at all. In the first case, this is because the rotation is proportional to $m=0$, so no rotation occurs. In the second case, we see that it oscillates between positive and negative real values. These observations are all instances of a general property of conjugate symmetry that we will investigate thoroughly in the next section.

6.2.2. What does this not do?

The shifting theorem implies that if a signal is circularly shifted, its magnitude spectrum is unchanged:

$$y[n]=x[n-d]\Rightarrow |Y[m]|=|X[m]|.$$

However, the converse is not true: two signals with the same magnitude spectrum may not be related by a circular shift of one another.

Example 6.2

Let $x[n]=1,0,0,0,0,\dots$ denote an impulse with $N$ samples, and let $y=-x$ denote its negation. As shown in the previous chapter, an impulse signal has spectrum $X[m]=1$ for all $m$. By DFT linearity, we also know that $y=-x$ implies $Y[m]=-X[m]$. As a result, we have that

$$|Y[m]|=|-X[m]|=|X[m]|=1\text{for }m=0,1,\dots ,N-1$$

so the two signals have the same magnitude spectrum. However, there is no delay $d$ that turns $x$ into $y$.

Fig. 6.4 Left: an impulse (top), a negative impulse (middle), and a 3-step delay (bottom). Center: the DFT spectrum (real and imaginary) components of each signal are distinct. Right: all three signals have identical magnitude spectra $|X[m]|=1$ .

Tip

Phase is important. Having the same magnitude spectrum is not enough to ensure that two signals are the same except for a phase shift.