Properties of the DFT

Eight samples shifted round a ring, one dial per DFT bin. Guess first: if no sample is lost, what happens to each bin’s size?

Shifting on a ring

The DFT (13.2) gave me $N$ numbers $X[k]$ for $N$ samples $x[n]$. The reason those numbers describe a repetition is in Sampling the spectrum (13.1): sampling the spectrum at $\Omega_k=2\pi k/N$ repeats the signal every $N$ samples. So every operation in time happens to that repetition, and I read the result on $n=0$ to $N-1$. This page asks what each operation does to the bins.

I need one new piece of notation. The expression $n\bmod N$ is the remainder after dividing $n$ by $N$, so it always lands in $0$ to $N-1$. For $N=8$, $9\bmod 8=1$ and $(-1)\bmod 8=7$. Walking off one end of the sequence brings you back in at the other end, which is why I call the $N$ positions a ring.

Circular shift by $n_0$ is $x[(n-n_0)\bmod N]$. It is 13.1’s repetition moved $n_0$ places later and read on $0$ to $N-1$. Samples that leave at $n=N-1$ come back in at $n=0$. The word “later” is as in Shifting, reversing and scaling time (2.1): a delay.

The picture at the top of the page shifts $x=5,4,3,2,1,0,0,0$ this way, with $N=8$. At $n_0=1$ every sample moves one place later, and the last one (a 0) comes round to $n=0$. Dial 1 has turned −45° and dial 2 −90°: bin $k$ turns by −45° × $k$, so dial $k$ turns $k$ times as fast as dial 1.

At $n_0=2$ dial 1 is at −90° and dial 2 at −180°, and the sizes under the dials have not changed. At $n_0=4$ the 1 that sat at $n=4$ has wrapped round to $n=0$. Dial 1 has turned half a turn, and dial $k$ $k$ half turns. A circular shift turns bin $k$ by $-2\pi kn_0/N$ and leaves its size alone.

When the clip ends, you can drag the stems sideways to choose $n_0$ from 0 to 7. At $n_0=3$ bin 1 has turned −135°, which is −45° × $k$ × $n_0$. Try $n_0=3$ and then $n_0=7$, and watch the sizes under the dials stay put.

Why the sizes stay and the bins turn

The proof takes three lines. The DFT of the shifted sequence is

Write $m=(n-n_0)\bmod N$. Then $n$ and $m+n_0$ differ by a multiple of $N$, and $e^{-j2\pi kn/N}$ repeats every $N$ in $n$, so I can replace $n$ by $m+n_0$. As $n$ runs over $0$ to $N-1$, so does $m$, and the sum becomes

This is Properties of the DTFT (12.3) with the delay rule $e^{-j\Omega n_0}$ read at $\Omega_k=2\pi k/N$. The factor has size 1, so $\lvert X[k]\rvert$ is unchanged, and it turns bin $k$ by $-2\pi kn_0/N$. For $N=8$ that is −45° × $k$ × $n_0$, which is what the dials showed.

Circular reversal is $x[(-n)\bmod N]$. The sample $x[0]$ stays, $x[1]$ and $x[N-1]$ swap, $x[2]$ and $x[N-2]$ swap, and so on. For $N=8$ and $x=4,3,2,1,0,0,0,0$, the reversed sequence is $4,0,0,0,0,1,2,3$. The same substitution as above, with $m=(-n)\bmod N$, shows that the DFT of the reversed sequence is $X[(-k)\bmod N]$. For a real sequence, bin $N-k$ is the conjugate of bin $k$ (The DFT, 13.2), so this is $X^*[k]$.

Mirror on the ring

Reversal turns $X[k]$ into its conjugate when $x$ is real. A conjugate keeps the real part and flips the sign of the imaginary part (Complex numbers for signals, 3.3). Now think about a sequence that equals its own reversal. Its DFT would have to equal its own conjugate. What kind of number does that? Watch the hatched bars, the imaginary parts, as the clip ends.

Reversed on the ring, 4 stays at $n=0$, and 3, 2, 1 now sit at $n=7$, 6, 5. The real parts are unchanged and the imaginary parts flip sign: $X[k]$ becomes $X^*[k]$. Then the average of $x$ and its mirror equals its own reversal, and all its imaginary parts are 0. A real sequence that equals its own reversal has a real DFT.

A sequence with $x[(-n)\bmod N]=x[n]$ is circular-even. One with $x[(-n)\bmod N]=-x[n]$ is circular-odd. The mirror is about $n=0$, so $x[0]$ is its own partner, and for even $N$ so is $x[N/2]$. Any real sequence splits into the two, as in Decomposing signals (2.3): $x_e=\tfrac12(x+x_\text{rev})$ and $x_o=\tfrac12(x-x_\text{rev})$. Their DFTs are $\tfrac12(X+X^*)=\mathrm{Re}\,X[k]$ and $\tfrac12(X-X^*)=j\,\mathrm{Im}\,X[k]$. The clip showed the first. Its odd partner is $0,1.5,1,0.5,0,-0.5,-1,-1.5$, and its DFT is the imaginary part.

The figure uses $N=8$ and shows both cases at full size. The even sequence $4,3,2,1,0,1,2,3$ has the DFT $16$, $6.83$, $0$, $1.17$, $0$, $1.17$, $0$, $6.83$, with no imaginary part. The odd sequence $0,3,2,1,0,-1,-2,-3$ has an imaginary DFT, $0$, $-9.66j$, $-4j$, $-1.66j$, $0$, $1.66j$, $4j$, $9.66j$, with no real part.

Circular convolution

Convolution in Discrete convolution (5.2) flipped one sequence and slid it along the other. On a ring I do the same, but positions wrap. The circular convolution of two sequences of length $N$ is

Its rule is the one I wanted from the start:

The proof uses the shift rule. Multiply $X[k]$ by $H[k]$ term by term:

The bracket is the DFT of $h$ shifted circularly by $m$. So the sum is the DFT of $\sum_m x[m]\,h[(n-m)\bmod N]$, which is the circular convolution. Inverting gives the rule in the other direction. Circular vs linear convolution (13.4) shows the wrap-around as a picture, and when the result equals the ordinary convolution.

Here is a small case with $N=4$. Take $x=1,2,3,4$ and $h=1,1,1,0$. Their DFTs are $X=10,\,-2+2j,\,-2,\,-2-2j$ and $H=3,\,-j,\,1,\,j$. The products are $30,\,2+2j,\,-2,\,2-2j$, and the inverse DFT of those is $8,7,6,9$. The sum directly gives the same: at $n=0$ it is $x[0]h[0]+x[1]h[3]+x[2]h[2]+x[3]h[1]=1+0+3+4=8$.

The ordinary convolution of the same two sequences is $1,3,6,9,7,4$. The last two values, 7 and 4, wrapped round onto the first two, $1+7=8$ and $3+4=7$.

The same two rules, swapped

Multiplying in time gives a circular convolution in frequency, with a factor $\tfrac1N$: $x[n]h[n]\leftrightarrow\tfrac1N(X\circledast_N H)[k]$. Multiplying by $e^{j2\pi k_0n/N}$ shifts the spectrum, $X[(k-k_0)\bmod N]$. Both are the shift and convolution rules read from the other side. That is duality: applying the DFT twice gives

The reason is the inverse formula $x[m]=\tfrac1N\sum_kX[k]e^{j2\pi km/N}$ evaluated at $m=-n$. For $x=4,3,2,1,0,0,0,0$ the DFT of its DFT is $8\times(4,0,0,0,0,1,2,3)$, that is $32,0,0,0,0,8,16,24$.

Where you’ll meet this

The even and odd rules return in The discrete cosine transform (13.6), where the choice of mirror decides how well a block compacts.

Worked example

Take $x=5,4,3,2,1,0,0,0$ with $N=8$ and shift it by 4, as the clip ended. The shifted sequence is $1,0,0,0,5,4,3,2$. Its bin 1 is the old bin 1 times $e^{-j2\pi\cdot1\cdot4/8}=e^{-j\pi}=-1$, a half turn, and the size is still 9.04. Bin 2 turns by $-2\pi\cdot2\cdot4/8=-2\pi$, a full turn, so bin 2 is unchanged. In general, for $n_0=4$ and $N=8$, odd bins flip sign and even bins stay.

Now reverse $x=4,3,2,1,0,0,0,0$ and read bin 1. The DFT has $X[1]=5.414-4.828j$. The reversed sequence $4,0,0,0,0,1,2,3$ has $5.414+4.828j$, the conjugate, as the rule says.

Reference card