Discrete Fourier Transforms

The Central Idea

Suppose we have a finite sequence of samples

The DFT represents this sequence as a combination of exactly \(N\) discrete complex-frequency modes. Under the convention used in this lesson, the DFT is

The inverse DFT reconstructs the samples:

The numbers \(X_k\) are the DFT coefficients. Together they describe how the original data are distributed among the available discrete frequencies.

From the Fourier Transform to the DFT

The continuous Fourier transform begins with a function \(f(t)\) defined on a continuous variable and produces a continuous frequency function \(\widehat f(\omega)\).

A computer normally sees something different: a finite collection of samples

taken at equally spaced times separated by \(\Delta t\). The DFT replaces the continuous frequency axis by a finite set of frequency bins. Thus the basic progression is

The DFT Basis Functions

For each index \(k\), define the discrete complex exponential

These sequences oscillate at different discrete frequencies. The DFT measures how strongly the data align with each one. In this sense, the DFT is an orthogonal expansion of the data in the basis

This connects the DFT directly to the earlier idea of orthogonal expansions.

Orthogonality of the Discrete Modes

The discrete complex exponentials satisfy an orthogonality relation. For integers \(j\) and \(k\),

This is the finite-dimensional analogue of the orthogonality relationships used in Fourier series. Because the basis modes are orthogonal, the DFT coefficients can isolate the contribution of each discrete frequency.

Roots of Unity

It is common to define

Then

so \(W_N\) is an \(N\)th root of unity. The DFT can be written compactly as

The powers of \(W_N\) move around the unit circle in the complex plane. This geometric structure is one reason the DFT has such regular algebraic and computational properties.

The Inverse DFT

The DFT does not discard information. If all \(N\) complex coefficients are retained, the original samples can be reconstructed exactly by

The factor \(1/N\) appears in the inverse under our convention. Other books and software packages may distribute normalization factors differently, so it is important to check the convention being used before comparing formulas.

DFT and Inverse DFT as a Transform Pair

We can summarize the pair as

The original sequence is often called the time-domain or sample-domain representation, while the coefficients form the frequency-domain representation.

Neither representation is inherently more correct. They emphasize different structures in the same finite dataset.

Example: A Constant Sequence

Let

Here \(N=4\). The zero-frequency coefficient is

The remaining coefficients cancel because their complex phases sum to zero:

Therefore,

A constant sequence contains only the zero-frequency, or DC, component.

The DC Component

When \(k=0\), the exponential factor is always \(1\), so

The sample mean is therefore

Thus the first DFT coefficient records the average or baseline level of the data.

Example: A Single Discrete Impulse

Consider

Only the term \(n=0\) contributes to each DFT coefficient. Since \(e^0=1\),

for every \(k\). Therefore,

A sample localized at one index spreads across every DFT frequency. This is a discrete version of the localization-frequency tradeoff seen in continuous Fourier analysis.

A Pure DFT Frequency

Suppose

for some integer frequency index \(m\). Its DFT is zero at every bin except \(k=m\):

A basis mode therefore appears as one isolated spectral coefficient.

Sampling Rate and Sampling Interval

If samples are separated by \(\Delta t\) seconds, the sampling rate is

The units are samples per second, commonly called hertz when the independent variable is time.

With \(N\) samples, the total observation duration is

Frequency Bins

Each DFT index corresponds to a frequency bin. For the unwrapped indices,

The spacing between neighboring bins is

Longer observation time produces smaller bin spacing and therefore finer frequency resolution.

Positive and Negative Frequencies

The indices near the end of the DFT array are usually interpreted as negative frequencies rather than very large positive frequencies. A common wrapped interpretation is

The Nyquist Frequency

For real-world sampled data, the highest frequency that can be distinguished without ambiguity is the Nyquist frequency:

When \(N\) is even, the DFT bin \(k=N/2\) lies exactly at this frequency. Frequencies above \(f_s/2\) fold into lower frequencies after sampling.

Aliasing

Aliasing occurs when different continuous frequencies produce the same sampled values. Consider a sampled complex exponential

Replacing \(f\) by \(f+m f_s\), where \(m\) is any integer, gives

The samples cannot distinguish these frequencies. Once aliasing has occurred, the original high-frequency information generally cannot be recovered from the samples alone.

The Sampling Principle

A band-limited signal whose highest frequency is \(f_{\max}\) must be sampled fast enough to distinguish its oscillations. The standard threshold is

In practice, systems often sample faster than this minimum and use an anti-aliasing filter before sampling to suppress frequencies above the usable range.

Example: Reading the Frequency Grid

Suppose \(N=1000\) samples are collected at

Then the observation duration is

and the frequency-bin spacing is

The Nyquist frequency is

Thus a peak at bin \(k=75\) represents

Real-Valued Data and Conjugate Symmetry

If all samples \(x_n\) are real, the DFT has the symmetry

for the corresponding positive and negative frequency bins. Therefore,

The negative-frequency half of the spectrum contains no independent magnitude information for real-valued data. This is why real-signal spectra are often displayed using only the nonnegative frequencies.

Cosines Appear in Frequency Pairs

Euler's identity gives

Therefore, for a cosine whose frequency lands exactly on DFT bin \(m\), the spectrum contains a positive-frequency coefficient at \(k=m\) and a matching negative-frequency coefficient at \(k=N-m\).

Away from the DC and Nyquist bins, the ideal coefficients are

for a unit-amplitude cosine with zero phase.

Magnitude and Phase

A DFT coefficient is generally complex:

Its magnitude is

and its phase is

Magnitude tells us how strong a frequency component is, while phase records where that component is positioned relative to the sampling window.

Amplitude Normalization

The raw DFT coefficient scales with the number of samples. For a real sinusoid whose frequency falls exactly on a bin, a common one-sided amplitude convention is

for interior positive-frequency bins. The factor of \(2\) accounts for the matching negative-frequency coefficient.

The DC term is not doubled:

For even \(N\), the Nyquist bin is also not doubled. Different software may report raw coefficients, amplitudes, powers, or power spectral densities, so normalization should always be identified explicitly.

The DFT Assumes Periodic Extension

Although we begin with only \(N\) samples, the DFT basis functions are periodic in the index \(n\). The transform therefore treats the finite data block as one period of a periodically repeated sequence:

This periodic-extension viewpoint explains several important DFT effects, especially spectral leakage and circular convolution.

When a Frequency Fits the Observation Window

A sinusoid fits the DFT grid exactly when the observation window contains an integer number of cycles. If the frequency is

for an integer \(m\), the sinusoid matches one of the discrete basis frequencies. Its energy can concentrate into the corresponding DFT bin or bin pair.

If the frequency lies between bins, the finite observation window does not join smoothly under periodic repetition.

Spectral Leakage

Spectral leakage occurs when energy from one physical frequency spreads across several DFT bins. One common cause is observing a sinusoid that does not complete an integer number of cycles inside the sample window.

The DFT then periodically repeats a data block whose end does not line up with its beginning. The artificial edge discontinuity requires many discrete frequencies to represent it, so the spectrum spreads outward from the true frequency.

Windowing

One way to reduce edge discontinuities is to multiply the samples by a window function before computing the DFT:

Windows such as the Hann, Hamming, and Blackman windows taper the data near the endpoints. This can reduce distant spectral leakage, but it also broadens spectral peaks and changes their amplitudes.

Windowing is therefore a tradeoff, not a universal correction. The appropriate window depends on whether the analysis prioritizes frequency separation, amplitude accuracy, leakage suppression, or some other objective.

Frequency Resolution

The DFT frequency spacing is

This means frequency resolution is fundamentally tied to how long the signal is observed. If two nearby tones need to be separated more clearly, increasing the observation duration is often more useful than merely increasing the sampling rate.

Sampling faster extends the accessible frequency range, while observing longer makes the frequency grid finer.

Zero Padding

Zero padding appends zeros to a finite data block before computing a longer DFT. For example, an \(N\)-sample sequence may be extended to length \(M>N\) by adding zeros.

The longer DFT evaluates the same finite-window spectrum on a denser frequency grid. This can make spectral plots smoother and can help estimate peak locations, but it does not create new measured information or improve the fundamental resolution set by the original observation duration.

Parseval's Identity for the DFT

Under the normalization convention used here, Parseval's identity is

The total squared magnitude of the sequence is preserved, up to the transform normalization, when we move between the sample and frequency domains.

This identity is valuable both conceptually and computationally because it gives an independent way to check a DFT calculation.

Example: Parseval Check

For

we found

In the sample domain,

In the frequency domain,

The two sides agree.

Circular Shifts

Suppose a sequence is shifted circularly by \(n_0\) samples:

Its DFT is

A shift in the sample domain therefore changes phase but not magnitude:

Discrete Modulation

Multiplying a sequence by a discrete complex exponential shifts its spectrum. If

then the DFT coefficients shift circularly:

This is the finite-sequence counterpart of frequency shifting in the continuous Fourier transform.

Circular Convolution

For two length-\(N\) sequences, define their circular convolution by

The DFT converts circular convolution into pointwise multiplication:

This property is one of the main reasons Fourier methods are so useful in filtering and numerical computation.

Linear Convolution with the DFT

Ordinary finite-data filtering usually uses linear convolution rather than circular convolution. If \(x\) has length \(L\) and \(h\) has length \(M\), their linear convolution has length

To compute it using DFT multiplication without wraparound, pad both sequences with zeros to a transform length satisfying

Then multiply the DFTs and apply the inverse DFT.

Filtering in the Frequency Domain

Suppose \(H_k\) is the frequency response of a discrete filter. If the input has DFT \(X_k\), then the filtered spectrum is

The inverse DFT converts \(Y_k\) back to output samples. A low-pass filter makes \(H_k\) small at high frequencies, while a high-pass filter suppresses lower frequencies.

The later lesson on convolution will develop the relationship between impulse responses and frequency responses in greater detail.

The DFT as Matrix Multiplication

The DFT can be written as a matrix-vector product

where the entries of the DFT matrix are

The inverse is

where \(F_N^*\) is the conjugate transpose. Equivalently,

Thus the normalized DFT matrix \(F_N/\sqrt N\) is unitary.

Direct Computation Cost

The DFT formula contains \(N\) output coefficients, and each coefficient uses a sum of \(N\) terms. A straightforward computation therefore requires on the order of

arithmetic operations. We describe this as

For small datasets this is manageable. For large signals, images, and repeated numerical calculations, a faster method is essential.

The Fast Fourier Transform

The fast Fourier transform, or FFT, is not a different transform. It is a family of algorithms for computing the same DFT more efficiently.

Many FFT algorithms reduce the cost from approximately

to approximately

The improvement becomes dramatic for large \(N\). This computational speed is a major reason Fourier analysis is practical in real-time signal processing, scientific computing, communications, imaging, and numerical simulation.

Why the FFT Can Be Fast

The DFT matrix contains repeated powers of roots of unity. FFT algorithms exploit these symmetries instead of recomputing the same structures many times.

For example, when \(N\) is even, a length-\(N\) DFT can be related to smaller DFTs formed from the even-indexed and odd-indexed samples. Repeating this decomposition creates a divide-and-combine computation.

The detailed organization of FFT algorithms belongs to computational transform methods. Here the essential distinction is: the DFT is the mathematical transform; the FFT is an efficient way to calculate it.

DFTs of Two-Dimensional Data

The same idea extends to arrays. For an \(M\times N\) data array \(x_{m,n}\), a two-dimensional DFT analyzes frequencies in two independent directions.

This is especially important for images, spatial measurements, diffraction patterns, and numerical solutions on grids. The transform can be computed by applying one-dimensional DFTs along one array direction and then along the other.

The underlying principle remains unchanged: represent discrete data by orthogonal oscillatory modes.

Common Error: Treating the Bin Index as the Physical Frequency

The index \(k\) is not automatically a frequency in hertz. The physical frequency depends on the sampling rate and transform length:

A peak at \(k=20\) means different physical frequencies for different values of \(f_s\) or \(N\).

Common Error: Ignoring Negative Frequencies

For the raw DFT ordering, bins above the Nyquist region wrap around to negative frequencies. Interpreting every index as a distinct positive physical frequency can lead to incorrect conclusions.

For real signals, conjugate symmetry helps identify the positive-negative frequency pairs.

Common Error: Confusing Sampling Rate with Resolution

The sampling rate determines the accessible frequency range, while the total observation duration determines the bin spacing:

Increasing \(f_s\) while keeping the observation time fixed does not by itself provide arbitrarily fine frequency discrimination.

Common Error: Assuming Zero Padding Creates Resolution

Zero padding gives more frequency samples of the finite-window transform, which can make a graph look smoother. It does not increase the amount of measured time or add independent information.

True separation of very close spectral components generally requires a longer observation interval or additional modeling assumptions.

Common Error: Ignoring Spectral Leakage

A broad cluster of DFT coefficients does not necessarily mean that the physical signal contains many separate tones. A single sinusoid between DFT bins can leak across many coefficients because of the finite observation window.

Always interpret a DFT together with the sampling rate, observation length, window, and expected signal structure.

Common Error: Forgetting Normalization

The raw coefficient \(|X_k|\) is not generally the physical sinusoid amplitude. Its scale depends on \(N\), the transform convention, whether a one-sided or two-sided spectrum is used, and whether windowing has altered the samples.

State the normalization convention before making quantitative amplitude or energy claims.

Common Error: Confusing the DFT with the FFT

The DFT is defined by the transform equations. The FFT is an algorithm for evaluating those equations efficiently.

Saying that an FFT produces a fundamentally different spectrum from a DFT is incorrect. With consistent conventions and numerical precision, they compute the same transform coefficients.

A Reliable DFT Workflow

1. Identify the number of samples \(N\).
2. Determine the sampling interval \(\Delta t\) or sampling rate \(f_s\).
3. Compute the observation duration \(T=N\Delta t\).
4. Find the frequency spacing \(\Delta f=f_s/N=1/T\).
5. Compute the DFT coefficients \(X_k\), normally with an FFT for large data.
6. Map DFT indices to physical frequencies correctly.
7. Use conjugate symmetry when the original samples are real.
8. Apply the appropriate normalization for amplitude, power, or energy.
9. Check for aliasing, leakage, and windowing effects before interpreting peaks.
10. Use the inverse DFT when reconstruction or frequency-domain modification is required.

Example: A Short DFT by Hand

Compute the DFT of

Here \(N=4\). First,

For \(k=1\),

Since \(e^{-i\pi}=-1\),

Similarly,

Therefore,

The real oscillation appears as a conjugate frequency pair.

Example: Reconstructing the Short Sequence

Starting from

the inverse DFT gives

Evaluating at \(n=0,1,2,3\) returns

This demonstrates exact reconstruction when the complete DFT is retained.

Example: Aliasing

Suppose the sampling rate is

A frequency of \(90\text{ Hz}\) sampled at times \(t_n=n/100\) produces

But

so the samples are identical to those from

Thus \(90\text{ Hz}\) aliases to \(-10\text{ Hz}\), which for a real cosine is observed as a \(10\text{ Hz}\) oscillation.

Practice 1: Constant Data

Find the DFT of

Practice 2: Discrete Impulse

Find the DFT of

Practice 3: Sampling Grid

A signal is sampled at \(f_s=800\text{ Hz}\) using \(N=400\) samples. Find:

1. the observation duration \(T\);
2. the frequency spacing \(\Delta f\);
3. the Nyquist frequency;
4. the physical frequency represented by bin \(k=60\).

Practice 4: Negative-Frequency Interpretation

For \(N=16\) and \(f_s=1600\text{ Hz}\), determine the wrapped physical frequency represented by DFT index \(k=14\).

Practice 5: Conjugate Symmetry

A real-valued length-\(10\) sequence has

What is \(X_8\)?

Practice 6: Parseval's Identity

A length-\(4\) sequence has DFT

Use Parseval's identity to find

Practice 7: Circular Shift

If \(x_n\) has DFT \(X_k\), write the DFT of

Practice 8: Linear Convolution Length

A sequence \(x\) has length \(12\) and a filter \(h\) has length \(7\). What minimum DFT length avoids circular wraparound when their linear convolution is computed by zero-padded DFT multiplication?

Practice 9: Zero Padding

Explain why padding a \(1\)-second measurement with zeros to produce a much longer FFT does not create the same true frequency resolution as observing the physical signal for a longer time.

Practice 10: DFT versus FFT

A student says, “The FFT is a more accurate transform than the DFT.” Explain the error.

Practice Answers

Practice 1

The sequence is constant, so only the DC coefficient remains:

Practice 2

Only the \(n=0\) sample is nonzero, so every coefficient equals \(3\):

Practice 3

The observation duration is

The frequency spacing is

The Nyquist frequency is

Bin \(60\) represents

Practice 4

The bin spacing is

Since \(k=14\) lies in the wrapped negative-frequency region,

Therefore,

Practice 5

For a real sequence,

Therefore,

Practice 6

Parseval gives

Hence,

Practice 7

A circular shift by \(3\) samples gives

Practice 8

The linear convolution length is

Therefore the DFT length must satisfy \(N\ge18\). The minimum is

Practice 9

Zero padding adds no new measurements. It evaluates the finite-window spectrum on a denser frequency grid, but the original observation still lasts only one second. The fundamental information about frequency separation is therefore still limited by that one-second observation interval.

Practice 10

The FFT is an algorithm for computing the DFT efficiently. It does not define a different transform and is not inherently more accurate. With the same data, normalization, and adequate numerical precision, direct DFT evaluation and an FFT compute the same DFT coefficients.

What to Remember

The discrete Fourier transform converts \(N\) samples into \(N\) discrete frequency coefficients:

The inverse DFT reconstructs the samples:

• the DFT is an orthogonal expansion in discrete complex exponentials;
• bin spacing is \(\Delta f=f_s/N=1/T\);
• the Nyquist frequency is \(f_s/2\);
• frequencies above the usable sampling range can alias into lower frequencies;
• real-valued data produce conjugate-symmetric spectra;
• magnitude and phase carry different information;
• finite observation can create spectral leakage;
• windowing trades leakage behavior against spectral sharpness;
• zero padding densifies the displayed frequency grid but does not create new data;
• Parseval's identity relates sample-domain and frequency-domain energy;
• DFT multiplication corresponds to circular convolution;
• the FFT computes the DFT efficiently, often in \(O(N\log N)\) operations.

The most important practical habit is to interpret a DFT together with its sampling conditions. A spectrum has meaning only when its sample rate, observation duration, frequency mapping, normalization, and windowing choices are understood.

Where We Go Next

Fourier methods are built around oscillatory complex exponentials and are especially natural for frequency analysis. Another major transform family uses exponential weighting to study growth, decay, initial-value problems, and system behavior in a complex frequency variable.

The next lesson, Laplace Transforms, develops this broader transform framework. It will show how differentiation and initial conditions become algebraic expressions in the transform domain and how many differential equations can be solved by transforming, simplifying, and then inverting.