The Discrete-Time Fourier Transform

Chapter 13 obtained the continuous-time Fourier transform by refusing to abandon the Fourier series. A pulse is not periodic, so we invented a periodic signal that agreed with it over one period, computed the series coefficients of that invention, and then pushed the period to infinity and watched what survived. What survived was an envelope function of frequency that belonged to the pulse alone.

The same manoeuvre works for sequences, and it is worth doing rather than asserting, because the two small differences between the continuous and discrete versions are precisely the two facts that make discrete-time frequency analysis its own subject.

Start with a sequence \(x[n]\) of finite duration, zero outside \(|n| \le N_1\). Build a periodic sequence \(\tilde{x}[n]\) by repeating \(x[n]\) every \(N\) samples, with \(N \gt 2N_1 + 1\) so no copies overlap. Over one period the two agree, and as \(N\) grows the neighbouring copies retreat, so \(\tilde{x}[n] \to x[n]\) for every fixed \(n\). Chapter 10 gave the analysis equation for such a sequence, and over one period \(\tilde{x}\) may be replaced by \(x\), whose tails are zero anyway:

The sum on the right depends on \(k\) and \(N\) only through the single combination \(k\Omega_0\). Give it a name and the pivot of the chapter appears.

Exactly as in Chapter 13, the coefficients of the periodic extension are samples of one fixed function of frequency, spaced \(\Omega_0 = 2\pi/N\) apart and scaled by \(1/N\). Lengthening the period samples the same envelope more finely; it never changes the envelope.

Now run the synthesis equation and take the limit. Substituting \(a_k\) into \(\tilde{x}[n]=\sum_{k=\langle N\rangle}a_k e^{jk\Omega_0 n}\) and writing \(1/N = \Omega_0/2\pi\):

Here the discrete story parts company with the continuous one in a way that is easy to miss. As \(N \to \infty\) the spacing \(\Omega_0\) shrinks and the sum becomes an integral, just as before. But the sum runs over \(N\) consecutive values of \(k\), and \(N\) terms spaced \(2\pi/N\) apart span a total frequency range of exactly \(2\pi\) — no matter how large \(N\) is. The interval of integration therefore does not grow to cover the whole real line. It stays \(2\pi\) wide forever.

Collecting the two results gives the transform pair for sequences. It is universally written with \(e^{j\Omega}\) rather than \(\Omega\) as the argument of \(X\), a notation that looks fussy until Chapter 23 reveals that \(X(e^{j\Omega})\) is the \(z\)-transform evaluated on the unit circle \(z = e^{j\Omega}\); the notation was quietly reserving the seat.

Read the synthesis equation as a statement about building blocks and it says what every Fourier statement in this book says: the sequence \(x[n]\) is a superposition of complex exponentials \(e^{j\Omega n}\), with \(X(e^{j\Omega})\,d\Omega/2\pi\) the amount of each. Because \(\Omega\) is continuous, the exponentials are packed infinitely densely, and because \(\Omega\) is confined to a \(2\pi\) band, the supply of distinct exponentials is finite in extent.

The asymmetry between sum and integral is not an accident of bookkeeping. It reflects a discrete variable on one side and a continuous one on the other. A sequence, being a list of numbers, has a continuous spectrum; a spectrum confined to a band of width \(2\pi\) has, by the mirror-image argument, a discrete time description. Hold that pairing in mind — discrete in one domain forces periodic in the other — because Chapter 20 will use it in reverse to explain sampling, and Chapter 26 will use it in both directions at once to build the DFT.

The periodicity of \(X(e^{j\Omega})\) is not a property of any particular signal. It holds for every sequence without exception, and the proof is one line long.

The consequence is that a discrete-time spectrum need only ever be drawn over one period, and \(-\pi \lt \Omega \le \pi\) is the conventional choice. Everything outside that window is a copy.

It also rearranges the vocabulary. In continuous time, "low frequency" means \(\omega\) near zero and "high frequency" means \(\omega\) large, and the two ends of the axis never meet. In discrete time the axis closes on itself. Low frequency means \(\Omega\) near \(0\) — and therefore also near \(\pm 2\pi\), \(\pm 4\pi\), and every other even multiple of \(\pi\). High frequency means \(\Omega\) near \(\pm\pi\), where the exponential becomes \(e^{\pm j\pi n} = (-1)^n\) and the sequence alternates on every sample, which is as fast as a list of numbers can possibly change. A discrete-time lowpass filter therefore passes the neighbourhoods of \(0\) and \(2\pi\) and stops the neighbourhood of \(\pi\), which looks alarming on a plot until the periodicity is internalised.

The analysis equation is an infinite sum, so it may fail to converge, and the synthesis equation is an integral over a finite interval, which is far better behaved. That asymmetry decides where the fine print lives: for the DTFT, all the convergence anxiety belongs to the forward transform, and essentially none to the inverse. Compare that with Chapter 11, where the continuous-time series needed the Dirichlet conditions and produced Gibbs ringing at every jump.

Two sufficient conditions cover the cases that matter. If \(x[n]\) is absolutely summable, the sum converges uniformly and \(X(e^{j\Omega})\) is a continuous function of \(\Omega\). If \(x[n]\) merely has finite energy, the sum converges in the mean-square sense: the error energy between \(x[n]\) and the partial sums tends to zero, even though the sums may misbehave at isolated frequencies.

Absolute summability is strictly stronger, and it is the condition to check first because it is easy. The geometric sequence \(a^n u[n]\) is absolutely summable precisely when \(|a| \lt 1\), which is why every worked example in this chapter carries that restriction. The sequence \(\sin(\Omega_c n)/\pi n\) is square-summable but not absolutely summable, and its transform — an ideal lowpass characteristic — has jump discontinuities, exactly as the mean-square theory predicts.

Some signals satisfy neither condition and still deserve a spectrum. A constant sequence \(x[n]=1\), or a pure exponential \(e^{j\Omega_0 n}\), fails both sums outright, yet it plainly consists of a single frequency and must have a line spectrum. Chapter 13 solved the same problem in continuous time by admitting impulses into the frequency domain, and the same repair works here, with one modification demanded by Section 16-3: since \(X(e^{j\Omega})\) must be \(2\pi\)-periodic, one impulse is never enough. They come in an infinite periodic train.

Four transforms carry most of the load. Each is a short calculation, and doing them once removes the temptation to memorise a table whose entries you cannot reconstruct.

The unit impulse. The analysis sum has a single non-zero term, at \(n=0\):

An impulse has a flat spectrum, and shifting it in time leaves the magnitude flat while adding a phase that is linear in \(\Omega\) with slope \(-n_0\). That last statement is the whole content of the time-shift property, and it is worth arriving at it this way before meeting it as a rule.

The one-sided geometric sequence. With \(|a| \lt 1\), the sum is geometric with ratio \(ae^{-j\Omega}\), whose modulus \(|a|\) is less than one, so it converges:

Its magnitude follows from \(|1-ae^{-j\Omega}|^2 = (1-a\cos\Omega)^2+(a\sin\Omega)^2 = 1-2a\cos\Omega+a^2\), giving

The sign of \(a\) decides the character completely. For \(0 \lt a \lt 1\) the denominator is smallest at \(\Omega=0\), so the spectrum peaks at DC and falls towards \(\Omega=\pi\): a slowly decaying sequence is a lowpass signal. For \(-1 \lt a \lt 0\) the sequence alternates in sign from sample to sample and the peak moves to \(\Omega=\pi\): a highpass signal. The extreme values are \(1/(1-a)\) and \(1/(1+a)\), and swapping the sign of \(a\) merely exchanges them.

The rectangular pulse. Let \(x[n]=1\) for \(|n| \le N_1\) and zero elsewhere. The sum is finite and geometric; the tidiest route is to factor out the middle term so the result comes out real:

Two checks confirm it. At \(\Omega=0\) both numerator and denominator vanish; expanding each to first order gives \(\Omega(N_1+\tfrac12)\big/(\Omega/2) = 2N_1+1\), which is exactly \(\sum_n x[n]\), the number of samples — the correct DC value. And the zeros occur where the numerator vanishes but the denominator does not, at \(\Omega = 2\pi k/(2N_1+1)\) for \(k\) not a multiple of \(2N_1+1\).

This function goes by several names — the Dirichlet kernel, the periodic sinc, or the aliased sinc. The last name is the most informative: it looks like the \(\sin(\omega \tau/2)/(\omega/2)\) of Chapter 13's rectangular pulse, but the denominator is \(\sin(\Omega/2)\) rather than \(\Omega/2\), and that replacement is exactly what makes it repeat with period \(2\pi\) instead of decaying forever.

The ideal lowpass characteristic, read backwards. Chapter 13 found that a rectangle in time gives a sinc in frequency, and remarked that duality would let the statement be read the other way. Discrete time offers the same trade with the roles exchanged. Take \(X(e^{j\Omega})=1\) for \(|\Omega| \le \Omega_c\) and zero over the rest of the period, and invert:

At \(n=0\) the expression is indeterminate and the limit gives \(x[0]=\Omega_c/\pi\), which is also what the integral returns directly. This sequence is two-sided and infinite, and it decays only as \(1/n\), so it is square-summable but not absolutely summable. Chapter 15 drew the same moral in continuous time: an ideal brick-wall filter is not causal, cannot be truncated without cost, and is a specification rather than a design.

Chapter 14 catalogued the properties of the continuous-time transform, and the discrete-time list is close enough that memorising it separately would be wasted effort. What matters is the handful of places where the two lists differ, and each difference traces back to Section 16-3.

Time shifting and frequency shifting. Replace \(n\) by \(n-n_0\) in the analysis sum and factor the resulting constant:

A delay leaves every magnitude untouched and subtracts \(\Omega n_0\) from every phase. Modulation slides the whole periodic spectrum along the frequency axis — and because the spectrum is periodic, sliding it by \(2\pi\) does nothing at all, which is the frequency-domain restatement of Chapter 3's observation that \(e^{j2\pi n}=1\). The special case \(\Omega_0=\pi\) is worth its own line: multiplying a sequence by \((-1)^n\) shifts its spectrum by half a period, turning a lowpass signal into a highpass one, which is exactly what Section 16-5 observed when the sign of \(a\) was flipped.

Differencing and accumulation. These are the discrete counterparts of differentiation and integration. The first follows immediately from linearity and the shift property; the second is its inverse, and like integration in Chapter 14 it needs a correction term for the DC component that differencing destroys.

Applying accumulation to \(\delta[n]\), whose transform is \(1\) and whose accumulation is \(u[n]\), produces the last row of the table in Section 16-5 without any further work. The impulsive term carries the average value that the running sum builds up and the first difference would erase.

Convolution and multiplication. The convolution property is the reason the whole apparatus exists, and it reads exactly as it did in Chapter 14:

The dual statement is where discrete time asserts itself. Multiplying two sequences convolves their spectra — but two periodic functions cannot be convolved over an infinite range, since the integral would diverge. What appears instead is periodic convolution, an integral over a single period.

Both integrands are \(2\pi\)-periodic, so their product is too, and integrating over one period is well defined and gives a \(2\pi\)-periodic answer — as it must, since the left-hand side is a sequence. This is the property that governs windowing: truncating a long sequence multiplies it by a rectangular window, and therefore smears its spectrum by periodic convolution with the Dirichlet kernel of Section 16-5. Chapter 26 will return to it when finite-length data meets the DFT.

Almost every sequence an engineer measures is real, and reality imposes a strong constraint on the spectrum. Conjugating the analysis sum for real \(x[n]\), and noticing that conjugation only flips the sign of the exponent, gives the conjugate-symmetry statement at once.

Two corollaries are used constantly. If \(x[n]\) is real and even, then \(X(e^{j\Omega})\) is real and even, which is why the Dirichlet kernel and the transform of \(a^{|n|}\) came out with no imaginary part. If \(x[n]\) is real and odd, \(X(e^{j\Omega})\) is purely imaginary and odd. Splitting any real sequence into its even and odd parts therefore splits its transform into real and imaginary parts, a decomposition Chapter 14 used for the same purpose.

The energy statement follows from the multiplication property with \(x_2[n]=x^*[n]\), or directly by substituting the synthesis integral into \(\sum_n x[n]x^*[n]\) and exchanging sum and integral.

The quantity \(|X(e^{j\Omega})|^2\) is the energy density spectrum: integrating it over a band of frequencies, with the \(1/2\pi\), gives the portion of the sequence's energy carried by that band. That interpretation is what turns Parseval from an identity into a tool — it lets you answer "how much of this signal's energy would survive that filter" without ever computing the filtered signal. Worked Example 6 evaluates both sides of the relation for a case where each is independently checkable.

Chapter 15 showed that a continuous-time LTI system is completely described by \(H(j\omega)\), the transform of its impulse response, and the argument never used anything specific to continuous time. It transfers verbatim. Feed \(x[n]=e^{j\Omega n}\) into a system with impulse response \(h[n]\) and evaluate the convolution sum of Chapter 7:

The exponential emerges unchanged in form, scaled by a complex number that depends only on \(\Omega\). Complex exponentials are eigenfunctions of discrete-time LTI systems; \(H(e^{j\Omega})\), the DTFT of the impulse response, is the eigenvalue, and it is called the frequency response. For a real sinusoid the response follows by conjugate symmetry:

The practical route to \(H(e^{j\Omega})\) is not usually through \(h[n]\). Chapter 9 described discrete-time systems by linear constant-coefficient difference equations, and the frequency response can be read off one directly. Take the general form and transform both sides, using linearity and the time-shift property on every term:

A difference equation becomes a ratio of polynomials in \(e^{-j\Omega}\), obtained by inspection: each delay of \(k\) samples contributes a factor \(e^{-j\Omega k}\). No convolution sums, no impulse response, no solving of the recursion. Chapter 9 laboured to find \(h[n]\) for such systems; here the frequency description arrives for free, and \(h[n]\) can be recovered afterwards by expanding \(H\) into partial fractions and reading the table of Section 16-5 backwards.

Two examples that will recur. The first-order recursion \(y[n]-ay[n-1]=x[n]\) gives \(H(e^{j\Omega})=1/(1-ae^{-j\Omega})\), whose impulse response is \(a^n u[n]\) — the pair of Section 16-5, arrived at from the other end. The \(M\)-point moving average \(y[n]=\frac{1}{M}\sum_{k=0}^{M-1}x[n-k]\) has a purely feed-forward structure, so its \(H\) is a finite sum, and Worked Example 5 shows it to be a crude but genuine lowpass filter with exact nulls at \(\Omega = 2\pi k/M\).

It is worth setting the continuous- and discrete-time transforms side by side once, because the differences are few and every one of them is structural rather than cosmetic.

The absence of duality is the entry worth pausing on. In continuous time, the analysis and synthesis equations differ only by a sign and a \(2\pi\), so any theorem can be read in either direction — that is what let Chapter 14 obtain half its property list for free. Here the two equations are a sum and an integral over different kinds of variable, and no such reflection is possible. The compensation is the pairing already noted in Section 16-2: discrete in one domain, periodic in the other. A sequence has a periodic spectrum. A periodic sequence, as Chapter 10 found, has a discrete spectrum — and one that is itself periodic, since it is both. That last case, discrete and periodic in both domains, is the discrete Fourier transform, and Chapter 26 is devoted to it.

Problems 1 to 3 exercise the definition, 4 to 6 the properties, and 7 and 8 the system connection. Sketch one period of every spectrum you compute; the periodicity is easy to state and easy to forget.