Motivation
A periodic signal can be described by its values or by the frequencies that combine to produce those values. The second description makes oscillation, filtering, and periodic differential equations easier to study. A computer, however, stores a finite list of samples, not a continuous function. The discrete Fourier transform (DFT) changes coordinates in a finite-dimensional vector space; the fast Fourier transform (FFT) is an efficient algorithm for the same change of coordinates. Neither automatically reconstructs arbitrary information lost between samples.
We choose a sign and normalization convention and keep it throughout. Other software may place the factor in the forward transform or split it symmetrically. The data and mathematical conclusion are unchanged when the inverse is adjusted consistently.
Definitions
Definition 2.1.1
(Continuous and discrete coefficients)
For an integrable -periodic function, its complex Fourier coefficient is . For samples , define
Indices of are understood modulo . The DFT is a finite sum even when no continuous signal is specified.
The samples and coincide for every integer . Thus the index describes a residue class of frequencies. The conjugate symmetry holds for real input; it follows directly by conjugating the sum. It does not hold for an arbitrary complex signal.
Main results
Theorem 2.1.2
(Discrete orthogonality and inversion)
For integer , the sum equals if divides and zero otherwise. Consequently the inverse DFT is
Proof
(A geometric sum of roots of unity)
If divides , every summand is one. Otherwise the ratio is not one but , so the geometric sum is . Substitute the forward formula into the proposed inverse and interchange the finite sums. Orthogonality leaves only the term whose sample index equals modulo , giving .
Theorem 2.1.3
(Circular convolution theorem)
For , define . Its DFT is .
Proof
(Reindexing modulo )
Insert the convolution in the DFT and change variables modulo . As runs through all residues, so does . The exponential splits into , and the two finite sums factor into . The modulo operation is essential: a DFT product computes circular, not automatically ordinary linear, convolution.
Worked examples
Worked example 2.1.4
(A four-point transform)
For , direct substitution gives , , , and . For instance . The inverse at gives . The conjugate pair reflects real input.
Worked example 2.1.5
(Two frequencies with identical samples)
At , the functions and both give . Their eight sampled values are identical, so no algorithm given only those samples can determine which original frequency was present. In a sampled problem the bins and represent the same residue. A band limit or other prior information is needed to identify a continuous frequency uniquely.
Worked example 2.1.6
(Circular versus linear convolution)
Let with . Circular convolution is ; no wraparound occurs because the ordinary product polynomial has degree two. If instead at , circular convolution is , because the degree-two coefficient wraps into index zero. The ordinary linear convolution is . Padding two sequences of lengths and to prevents that wraparound in their nonzero linear-convolution range.
Concept lensAlgebraic
Evaluating a polynomial at the roots of unity
Attach to the samples the polynomial . With , : the DFT evaluates at the distinct th roots of unity, and the inverse DFT interpolates from those values. Because at every node, circular convolution is multiplication of polynomials modulo , which is the convolution theorem; padding sequences of lengths and to leaves the product degree too small to wrap. The radix-two split below is .
Methods and reasoning
Write . The fast algorithm rests on one identity, which splits a transform of even length into two transforms of half the length.
Proposition 2.1.7
(Radix-two splitting and its cost)
Let be even, and let and be the length- DFTs of and . For ,
If , applying the splitting recursively down to length one computes the DFT with complex multiplications by twiddle factors and complex additions.
Proof
(Even–odd split and a counting recurrence)
Since , splitting even and odd indices gives
If and denote the two length- transforms, periodicity and give the butterfly pair and for . No approximation has been introduced by this rearrangement in exact arithmetic.
For the count, let and be the numbers of twiddle multiplications and additions, with , since a length-one DFT is the identity. Each level uses multiplications , each reused for two outputs, and additions or subtractions, so and . By induction on , and : indeed and . Direct evaluation of all sums takes operations.
Proof X-ray
Why each half-length transform is used twice
Correctness uses two facts about roots of unity, at two different places. The identity turns the even-indexed and odd-indexed sums into genuine DFTs of length . The key move is periodicity: and have period in , so and , while flips the sign of the twiddle factor. Hence the same pair produces both and , and this reuse is exactly where the halving of work comes from. The recursion terminates because the length halves at each level, and it closes at length one, where the DFT is the identity. Evenness of is used at every level; for it holds all the way down, which is why the count is clean. For other lengths the split stops at an odd factor and a different factorization is needed.
An in-place implementation must manage index ordering, temporary storage, rounding and normalization. FFT does not designate a different transform, nor is radix two the only available algorithm.
As an application, for with periodic boundary conditions, a smooth periodic solution has coefficients . For , set . At , solvability requires , and remains arbitrary until a mean is specified. This continuous Fourier argument must not be confused with solving an arbitrary finite-difference system: a discrete derivative has its own frequency multiplier. For example, the periodic centered second difference has multiplier for , not exactly .
Basis vectors and energy
For each , define the vector with entries for . Discrete orthogonality says that these vectors are mutually orthogonal in the complex inner product and each has squared norm . There are nonzero orthogonal vectors in , so they form a basis. The inverse DFT expresses the sample vector in this basis, with coefficient . This is the finite-dimensional reason that no sample information is lost by an exact DFT.
The energy identity follows by expanding in the orthogonal basis. Its factor depends on our normalization. If instead both transforms use , the matrix is unitary and the two sums are equal without the factor. Energy conservation applies to the entire complex spectrum, including negative-frequency bins represented by upper indices; discarding half without adjusting for conjugate pairs changes the total.
Sampling a continuous series
Suppose, for a precise interchange of sums, that with . Sample at . Substitution and discrete orthogonality yield
Thus each computed bin adds all continuous coefficients in one congruence class. This is an explicit aliasing formula, not merely a visual artifact. Absolute convergence justifies swapping the infinite and finite sums; without it one needs an appropriate convergence interpretation. A band-limited signal with at most one nonzero coefficient in each class avoids this particular collision, provided its band is known.
For real data with even , bin zero and bin are their own conjugate partners and are real. Other bins occur in pairs and . The sample belongs to the Nyquist bin . At this boundary the positive and negative representatives coincide in the samples; treating them as two separately measured waves double-counts information. The familiar sampling-rate rule depends on the assumed frequency band and endpoint convention, not on the FFT algorithm itself.
An explicit butterfly calculation
For , the even subsequence is and the odd subsequence is . Their two-point transforms are and . Since , the butterfly gives and . The butterfly gives and . The same intermediate transforms provide both members of each pair; this reuse is the source of the speedup.
For non-power-of-two lengths the displayed recursion cannot simply continue to one using only equal halves. Other factorizations, direct small transforms, or different FFT algorithms can handle such lengths. Padding changes the length and the sampled frequency grid; it is a computational choice with a mathematical effect, not a proof that the original sequence had more samples.
Circular shifts and filtering
Let for an integer shift . Reindexing the finite DFT sum gives . Shifting changes phase while leaving unchanged. Consequently magnitude alone cannot generally recover the original sample positions: even a shifted nonconstant sequence has the same magnitudes. In a filter, multiplication of by chosen gains corresponds via the convolution theorem to circular convolution with the inverse DFT of those gains. If the intended operation is linear filtering of a finite record, appropriate padding and boundary treatment must be stated.
For a smooth periodic function, differentiation multiplies its th continuous Fourier coefficient by when the relevant differentiation and integration by parts are justified. Higher frequencies are amplified, so differentiation can magnify high-frequency noise. Conversely integration divides nonzero frequencies by but leaves the mean undetermined; a periodic antiderivative requires the integrand to have zero mean, while the additive constant of the antiderivative is specified separately. These observations motivate Fourier methods but do not eliminate questions about truncation or measurement noise.
Leakage from a finite observation window
A DFT treats the finite sample list as one period of a periodic discrete sequence. If a recorded sinusoid does not complete an integer number of cycles in the observation interval, its periodic extension has a mismatch at the boundary. Its energy then spreads across several frequency bins. This is spectral leakage, not a failure of the transform: the transform exactly represents the finite list it received.
A window multiplies the record by chosen weights before the transform. Its purpose is to control the boundary transition, trading a wider main frequency response for reduced sidelobes. It also changes amplitudes, so amplitude estimates need the window's normalization. There is no universally best window independent of the measurement objective. If two frequencies are close, record duration, noise and the window all matter; an interpolated plot alone cannot establish that they are distinguishable.
Reconstructing from conjugate bins
Let and , giving . Euler's identity expresses the samples as one half of the positive-frequency vector plus one half of its negative-frequency vector. Consequently and the other bins vanish. Reconstructing with the inverse gives
A real cosine therefore appears in two bins under this convention. The value in either bin is not the cosine's amplitude by itself; dividing by gives the complex coefficient , and combining its conjugate partner restores amplitude one. At zero and Nyquist frequencies there is no distinct partner, so the same doubling rule must not be applied blindly.
Filtering and the zero mode
A circular average with weights has frequency response . Its magnitude is . It preserves the mean because , and for even removes the alternating Nyquist component because . It also changes phase, reflecting the asymmetric location of the two weights. This finite example illustrates why an inverse transform of a frequency multiplier describes both the numerical filter and its boundary convention.
Concept lensAlgorithmic
The FFT is a factorization of a linear map
The DFT matrix has entries, but the even–odd identity factors its action into two smaller transforms and a sparse butterfly. At every level, a permutation gathers even and odd samples, the subtransforms operate independently, and paired outputs combine with twiddle factors. The product of these sparse stages equals the original DFT matrix in exact arithmetic. This viewpoint explains the speedup without claiming that the DFT itself has changed, and it identifies where ordering and roundoff enter an implementation.
Common misconceptions
Common mistake
(Reading a bin index as a physical frequency)
A DFT bin is not a physical frequency until the sampling interval is specified. With samples spaced , bin can be represented by cycles per unit time, and for upper bins the negative representative may be the physically meaningful one.
Common mistake
(Doubling every bin to obtain amplitudes)
For real data a cosine of amplitude one in bin appears as in bins and , so one-sided amplitudes double . Bin zero and, for even , bin have no distinct partner: the constant list gives , and doubling would report amplitude two.
Spectral coefficients of a discontinuous periodic extension may decay slowly, and endpoint mismatch produces leakage. Neither a fast computation nor a smooth plot proves that a signal was sufficiently sampled.
Counterexample mode
Zero-padding does not remove aliasing
Claim: padding a sampled record with zeros to a longer length reveals frequencies that the original grid could not distinguish. Take the eight samples of and of at . They are identical, since . Padding both lists with eight zeros gives two identical lists of length sixteen, hence identical sixteen-point transforms. No processing of the padded data can tell the two signals apart. Zero-padding only interpolates the transform of the finite record; separating the two frequencies requires new samples on a finer grid or a known band limit.
Quick check
Quick check
(Compute the DFT of the constant list , , and check the inverse.)
Solution · Answer
By discrete orthogonality, equals for and zero for the other bins. The inverse gives for every .
Exercises
Quick check
(Compute the four-point DFT of using the convention above.)
Solution · Answer
Here , so the four values are . For example .
Quick check
(Show that .)
Solution · Answer
Substitute , expand and sum over . Orthogonality annihilates every cross term with ; the remaining sum is .
Quick check
(At eight equally spaced points, which nonnegative index below eight has the same samples as frequency ? Explain.)
Solution · Answer
The index is , since . At each integer , .
Quick check
(Compute the length-three circular convolution of and , and compare the ordinary linear convolution.)
Solution · Answer
Using indices modulo three gives . Ordinary convolution gives ; its last coefficient wraps to index zero, producing there. The discrepancy illustrates why zero-padding to length at least matters for linear convolution.
Further study
Convergence of Fourier series, discrete cosine transforms, multidimensional FFTs, window selection, nonuniform sampling, and numerical error analysis are separate subjects. The finite identities proved here do not require a claim that every continuous Fourier series converges pointwise to its source function.