Properties of the DTFT

Multiply a signal by a turning arrow and its spectrum slides round a circle. Watch what slides off at $\pi$ come back at $-\pi$.

The rules that carry over

On the page Properties of the Fourier transform (8.2) you met one rule for each operation on a continuous signal. Most of them carry over to sampled signals with $\Omega$ in place of $\omega$, and each proof is one line. Here $X(e^{j\Omega})$ is the DTFT of $x[n]$, as on the page The DTFT (12.2), and $\Omega$ is the digital frequency in rad/sample.

Linearity holds because the transform is a sum: $ax[n]+by[n]\leftrightarrow aX(e^{j\Omega})+bY(e^{j\Omega})$. For a delay, put $m=n-n_0$ in the sum. The factor $e^{-j\Omega n_0}$ comes out in front:

The size of the spectrum does not change, and the phase turns by $-\Omega n_0$. Reversal, $x[-n]$, replaces $n$ by $-n$ in the sum, which gives $X(e^{-j\Omega})$. Conjugation gives $x^*[n]\leftrightarrow X^*(e^{-j\Omega})$. For a real signal, $x^*=x$, so $X(e^{-j\Omega})=X^*(e^{j\Omega})$: the size is even in $\Omega$ and the phase is odd, as in the 8.2 section “A real signal has a mirrored spectrum”.

The delay rule gives a first check. The centred 5-sample pulse, $1$ for $-2\le n\le 2$, has the transform $\sin(5\Omega/2)/\sin(\Omega/2)$ from 12.2. The causal pulse, $1$ for $0\le n\le 4$, is the same pulse delayed by 2 samples, so its transform is

Two things are new in discrete time, and each gets an instrument. The first is the frequency shift, where the spectrum slides round a circle. The second is the window, where multiplication in time turns into a new kind of convolution in frequency.

Slide the spectrum round the circle

Multiply a signal by $e^{j\Omega_1n}$ and the sum changes to $\sum_n x[n]e^{-j\Omega n}e^{j\Omega_1n}$. Since $e^{j\Omega_1n}e^{-j\Omega n}=e^{-j(\Omega-\Omega_1)n}$, the sum is $X$ evaluated at $\Omega-\Omega_1$. I call this the frequency shift, and $\Omega_1$ is the shift in rad/sample:

It is the mirror of the delay: a delay in time multiplies the spectrum by an arrow, and a shift in frequency multiplies the signal by one. In discrete time there is a new feature. The frequency axis is a circle, as on the page Frequency in discrete time (12.1), so $\pi$ and $-\pi$ are the same point. What slides off the edge at $\pi$ comes back in at $-\pi$, like a horse on a carousel that passes the gate and comes round again.

The picture at the top of the page applies this to $x[n]=0.8^nu[n]$. At $\Omega_1=0$ nothing changes: the size peaks at 0, among the low frequencies, a low-pass shape. At $\Omega_1=0.5\pi$ the peak sits at $0.5\pi$, the same shape, only moved. At $\Omega_1=\pi$, where $e^{j\pi n}=(-1)^n$, what slid off at $\pi$ came back in at $-\pi$, and the peak sits at $\pm\pi$. Flipping every other sample’s sign turned low-pass into high-pass.

After the clip, drag the curve sideways, or its peak marker, to set $\Omega_1$ yourself. Watch the height of the peak: it stays at 5 for every $\Omega_1$.

The height is the size of $1/(1-0.8e^{-j\Omega})$ at its peak, $1/(1-0.8)=5$. A shift moves a curve but does not change its shape, so the peak keeps its height wherever it lands. Look at the end of the clip. The multiplier $e^{j\pi n}$ is $(-1)^n$, so $(-1)^n0.8^nu[n]=(-0.8)^nu[n]$, and its size is 5 at $\Omega=\pi$ and $1/1.8=0.556$ at $\Omega=0$.

Cut a tone short, and its arrows spread

A real recording has a start and an end. Cutting a signal to $N$ samples multiplies it by the window $w[n]$, which is 1 for $0\le n\le N-1$ and 0 elsewhere. It is an envelope, as on the page Operations on amplitude (2.2). The window is a pulse like the one in 12.2, delayed by $(N-1)/2$ samples, so by the delay rule its transform $W(e^{j\Omega})$ is

A cosine is two arrows of half size, $\cos(\Omega_1n)=\tfrac12e^{j\Omega_1n}+\tfrac12e^{-j\Omega_1n}$. By the shift rule, applied to each arrow,

Each arrow of the tone is replaced by a copy of $W$ centred on it. The central lump of $W$ is its main lobe. It runs from the first zero on one side of the centre to the first on the other, and $W$ has its zeros at multiples of $2\pi/N$, so the main lobe is $4\pi/N$ wide.

The next picture cuts the tone $\cos(0.5\pi n)$ to $N$ samples and doubles $N$ three times. Watch the lumps where the tone’s two arrows were.

At $N=4$ one cycle is kept, and each arrow has become a lump $\pi$ wide, reaching from 0 to $\pi$. At $N=8$, two cycles, the lumps are half as wide, $0.5\pi$, with small side lobes between them. At $N=16$ they are $0.25\pi$ wide: the longer the window, the closer each lump comes to the tone’s arrow. At $N=32$ they are $0.125\pi$ wide. Multiplying by the window in time replaced each arrow with a copy of the window’s spectrum: a periodic convolution.

After the clip, drag the cut in the time panel to set $N$ yourself, from 4 to 64.

Notice two things. The lumps narrow as $N$ grows, in step with $4\pi/N$. And their height, relative to $N/2$, stays at 1. The relative axis is the reason: the unscaled lump grows with $N$, since the window adds up $N$ samples, and dividing by $N/2$ shows the shape alone. At $\Omega=0.5\pi$ the size is exactly $N/2$ for each of these lengths, and at $0$ and $\pi$ it is 0.

This is the price of a short look at a signal. A handclap lasts a few samples, and its spectrum is one wide lump with no single pitch. A tone kept for a long time has a spectrum that is nearly a pair of arrows. At $N=8$ the side lobes peak at 0.272 of $N/2$, at $0.134\pi$ and $0.866\pi$. They are the first sign of leakage, which the pages Windowing and spectral leakage (15.1) and Window functions compared (15.2) take on.

Multiplication in time is periodic convolution in frequency

The window example is a case of a general rule. Multiply two signals and the spectrum of the product is

Slide one spectrum past the other and add up the overlap, over one period only. I call this periodic convolution. It is the convolution rule with time and frequency swapped, and the integral runs over $2\pi$ because both spectra repeat every $2\pi$. For the tone, $X$ is two arrows, and the integral picks out one copy of $W$ at each of them.

Convolution becomes multiplication

The rule from 8.2 returns unchanged. For the convolution $x*h$ of the page Discrete convolution (5.2),

The proof is the one from 8.2. The signal $x$ is a sum of arrows. Each arrow goes through a system with impulse response $h$ and comes out multiplied by one number, $H(e^{j\Omega})$, as on the page Properties of LTI systems (5.4). So the output is the same sum of arrows, each scaled by $H$.

Here is a check with two 3-point moving averages in a row, from Difference equations (6.1). One average has $h=(1,1,1)/3$, and its transform is $e^{-j\Omega}(1+2\cos\Omega)/3$, and the factor $e^{-j\Omega}$ does not change the size. The convolution of the average with itself is the triangle $(1,2,3,2,1)/9$. Its size at $\Omega=0$, $\pi/3$, $2\pi/3$ and $\pi$ is 1, 0.444, 0 and 0.111. These are the squares of one average’s sizes, 1, 0.667, 0 and 0.333.

The rest of the table

Three more rules finish the set, and I check each on $x[n]=0.8^nu[n]$, whose transform is $1/(1-0.8e^{-j\Omega})$ from 12.2.

Parseval. The energy of a signal, defined on the page How big is a signal (1.3), is the same in both descriptions:

In time, $\sum_n0.64^n=1/(1-0.64)=2.7778$. Integrating $\lvert X\rvert^2$ numerically over $(-\pi,\pi]$ gives the same value.

Differentiation in frequency. Differentiate $X(e^{j\Omega})=\sum_nx[n]e^{-j\Omega n}$ with respect to $\Omega$. Each term brings down a factor $-jn$, so $nx[n]\leftrightarrow j\,dX/d\Omega$. For $0.8^nu[n]$ this gives

At $\Omega=0$ both sides agree: the sum $\sum_nn\,0.8^n$ is $0.8/0.2^2=20$.

Symmetry. A real $x[n]$ has an even size and an odd phase, as above. If $x[n]$ is also even, $x[n]=x[-n]$, then $X$ is real. This is the even part of Decomposing signals (2.3), and it is why the centred pulse of 12.2, $\sin(5\Omega/2)/\sin(\Omega/2)$, is one real curve with no phase.

Where you’ll meet this

The frequency shift is how a sampled radio signal is moved down to a lower frequency before it is processed, and why $(-1)^n$ turns a low-pass design into a high-pass one. Windowing is behind every spectrum you compute from a finite recording: the peak of a tone is never narrower than the main lobe $4\pi/N$ of the window you used.

The next page, Frequency response of discrete-time systems (12.4), uses the convolution rule to give each system a response $H(e^{j\Omega})$. Windows and leakage follow in 15.1 and 15.2, and linear phase, a pure delay in disguise, in Linear-phase systems (17.3).

Reference card