Aliasing of discrete Fourier modes 2026-10-14
For integers , adding to a frequency index changes the complex exponential by . Thus different continuous Fourier modes become identical discrete Fourier modes on the sampling grid. This is aliasing, caused by sampling before any discrete Fourier transform is computed.
For , compare the continuous functions and with and , sampled at , . With , both cosines give exactly the first row and both sines give exactly the second:The nine-cycle sine agrees in sign as well as magnitude with the one-cycle sine: the frequency indices differ by , rather than by a sign reversal. Consequently, either cosine produces the same discrete Fourier transform, with all other coefficients zero; either sine produces , , with all other coefficients zero.
One-cycle and nine-cycle cosine and sine waves have exactly the same eight samples
. Details. An observed low frequency therefore does not establish that physical high frequencies are absent. To exclude such alternatives, the Nyquist–Shannon sampling theorem requires a specified class of bandlimited functions. For arbitrary pure sinusoids with frequencies at most , choose sampling rate ; equality needs care because vanishes at every . The finite-energy L2 space version of the Nyquist–Shannon sampling theorem permits equality under its own hypotheses. In either case, exact continuous reconstruction generally requires the entire infinite sample sequence; eight observed samples alone do not supply it. Demanet derives the grid aliasing condition as a difference by an integer multiple of the sampling angular frequency.[ref]
https://math.mit.edu/icg/resources/teaching/18.330/18.330-Mar21.pdf. Laurent Demanet, MIT 18.330 notes, §6.2, Definition 11, p. 57: aliases on a grid, 2012
Bit-reversal permutation 2026-11-05
The bit-reversal permutation of writes each index using exactly binary digits, reverses those digits, and interprets the result as another index. Leading zeros matter. Reversing twice restores the original index, so this permutation is an involution.
For , the index order becomes : for example, maps to . It occurs naturally in radix-two Fast Fourier transform implementations. Repeatedly separating even from odd indices consumes the low-order bits first; traversing the resulting recursion tree reverses the order in which the index bits are read. Some implementations permute inputs, others permute outputs, and other layouts avoid an explicit reversal. The discrete Fourier transform itself is independent of this storage choice.[ref]
Notes on the FFT by C. Sidney Burrus. radix-two decimation and digit-reversed ordering
Cepstrum 2026-11-05
A cepstrum transforms a logarithmic spectrum back to a time-like coordinate. In the real-cepstrum convention for a discrete-time signal with Fourier transform ,The finite-data version uses an inverse discrete Fourier transform of the log-magnitude spectrum. Zeros require suitable assumptions or numerical regularization. Using log power instead of log magnitude changes the scaling, so the convention must be stated.[ref]
Spectral Audio Signal Processing by Julius O. Smith III. Spectral Envelope Extraction, Cepstral Windowing, equation 11.2
The usefulness comes from convolution: if , then the spectra multiply and their log magnitudes add, giving . Multiplicative source-and-filter effects become additive.
For an ideal echo filter , with real , expanding givesOther coefficients vanish. Thus an echo of amplitude delayed by eight samples gives coefficients at and at . Peaks reveal a delay that originally appeared as spectral ripples. The output coordinate is called quefrency. Keeping only its low-quefrency coefficients can smooth a spectral envelope, while retaining high-quefrency structure can expose repetitions.
Circulant matrix Created 2026-09-24 Updated 2026-10-14
A circulant matrix applies the same rule at every position of a finite ring: moving both the input and output indices one step leaves its entries unchanged. Its first column determines the whole matrix. For a length- vector , index rows and columns by and defineThe indices use modular arithmetic. Thus each column is the previous column shifted down one place, with the last entry wrapping around to the top. Multiplication is exactly circular convolution:This makes a circulant matrix a natural model for a periodic finite difference rule or a filter acting on a periodic record. Strang's MIT lecture develops this connection between circulant matrices, circular convolution and the discrete Fourier transform.[ref]
For example, the first column givesHere the indices wrap around modulo four. Each output compares a value with its two neighbors; this is the Graph Laplacian of a four-vertex cycle graph. A constant input gives zero, while an alternating input gives a large response. The Fourier diagonalization of a circulant matrix makes this distinction exact: its four eigenvalues are .
Fourier eigenvectors of the four-point cycle Laplacian
. Details. The plotted discrete Fourier modes are complex vectors, shown through their real and imaginary parts. Each entry has modulus one; the Euclidean norm of each length-four vector is two. In particular, modes and have the same real part but opposite imaginary parts, so they are distinct eigenvectors with the same eigenvalue.
The useful surprise is that every length- circulant matrix shares the same basis of eigenvectors, whatever its first column. One change of basis therefore simplifies an entire family of linear maps, instead of requiring a separate eigenvalue computation for each one. Bamieh's tutorial develops the discrete Fourier transform from precisely this simultaneous diagonalization problem.[ref]
https://arxiv.org/abs/1805.05533. Bamieh, Discovering Transforms: A Tutorial on Circulant Matrices, Circular Convolution, and the Discrete Fourier Transform (2018; revised 2022)
Circular convolution Created 2026-10-14 Updated 2026-10-20
Circular convolution of two length- sequences uses modular arithmetic for their indices. Extending both inputs periodically gives the displayed formula. Equivalently, fold a finite discrete convolution into residue classes modulo by adding entries whose indices are congruent. The discrete Fourier transform of the circular convolution is the product of the two discrete Fourier transforms, with the usual unnormalized forward transform and inverse convention.
Coherent gain of a window 2026-11-05
The coherent gain of a discrete window function is its mean coefficient:It describes the amplitude scaling of a coherent complex tone under the chosen DFT normalization. Window coefficients and their normalization must be specified; a window's name alone does not fix every finite-length convention.[ref]
LabVIEW Analysis Concepts by National Instruments. Printed pages 5-20–5-24, periodic/symmetric windows and coherent-gain scaling
For , multiply by and evaluate the unnormalized discrete Fourier transform at the exact tone bin:Thus recovers when . This result is exact for this complex-tone model. A real cosine also has a negative-frequency component; the usual doubled one-sided amplitude requires that its contribution to the chosen positive-frequency bin be absent or separately accounted for.
A rectangular window has . The periodic Hann window has for . Its coherent bin therefore has half the unwindowed amplitude before correction. The symmetric endpoint convention , for , instead gives . At this is , so blindly multiplying by two is not the exact correction for that convention.
Coherent gain does not correct every amplitude error. An off-bin tone samples the window's frequency response away from its maximum, and a DC-removing window with zero sum has no usable gain correction at all. Coherent sampling, leakage and window normalization are distinct conditions.
Noise uses a different scaling. For independent equal-variance samples, a weighted DFT bin's noise variance is proportional to , not . This motivates equivalent noise bandwidth in bins,which is for a periodic Hann window with . The manufacturer's table lists both coherent gain and noise bandwidth rather than treating one as a substitute for the other.[ref]
Coherent sampling 2026-11-05
Coherent sampling records an integer number of cycles of a periodic signal in the observation interval used for a discrete Fourier transform. For equally spaced samples at sampling rate , a single sinusoidal frequency is coherent whenThis is a frequency-and-record-length condition, not merely starting the acquisition at a particular phase.[ref]
Coherent Sampling vs. Window Sampling by Analog Devices. What Defines Coherent Sampling?, integer-cycle relation
For the complex tone , the unnormalized discrete Fourier transform givesA real cosine has the corresponding positive- and negative-frequency bins. The cancellation follows from a finite geometric sum; arbitrary phase does not spoil it. Periodic continuation means , not that the last stored sample must equal .
For example, and make a tone coherent, while is off the DFT grid. The latter's rectangular window record generally has spectral leakage into multiple bins. The bin spacing remains in both cases: coherence has not changed the grid spacing or increased the record duration.
Choosing relatively prime to can help an analog-to-digital converter test sample more distinct input phases, but it is an additional condition. A -cycle tone in samples is coherent even though its sampled phases repeat after only samples. The manufacturer's application note discusses the irreducible-ratio choice separately from the integer-cycle equation.[ref]
Coherent Sampling vs. Window Sampling by Analog Devices. Figure 1 explanation, cycle count and irreducible ratio
An experiment must also maintain the required ratio over the record. Frequency drift or clock variation can invalidate a nominal setting. If coherence cannot be maintained, a different window function can reduce leakage, with changes to amplitude scaling and spectral spread accounted for through the coherent gain of a window.
Cooley-Tukey FFT algorithm Created 2026-10-14 Updated 2026-10-20
The radix-two Cooley--Tukey algorithm recursively splits a discrete Fourier transform into transforms of the even-indexed and odd-indexed samples. For a power-of-two length this evaluates the transform in arithmetic operations.
The saving comes from reusing the two shorter discrete Fourier transforms for both halves of the output, through an FFT butterfly. For , each level of the even--odd fast Fourier transform recursion needs work proportional to , and there are levels. This gives the time complexity without changing the discrete Fourier transform being computed.
James W. Cooley and John W. Tukey published An Algorithm for the Machine Calculation of Complex Fourier Series in Mathematics of Computation 19 (1965), pp. 297–301. Their original paper factors a composite length as , derives an operation count , and discusses powers of two and in-place storage. Its opening explicitly builds on earlier algorithms by I. J. Good; the 1965 paper is a landmark computational formulation, rather than the invention of the underlying Fourier analysis. Its positive-exponent convention also illustrates why a Fast Fourier transform's exponent sign must be specified.[ref]
https://janmr.com/files/papers/cooley-tukey.pdf. Cooley and Tukey 1965, original paper, pp. 297–300, equations (1)–(12); scan of the published article
Crystal momentum conservation 2026-10-25
A lattice-translation-invariant interaction conserves total crystal momentum modulo a reciprocal lattice vector . On a periodic chain of sites with unit spacing, the discrete Fourier transform supplies . This Fourier orthogonality proves the selection rule directly; it permits transfer by a reciprocal lattice vector rather than requiring equality of unrestricted momenta.
C. Sidney Burrus 2026-11-05
C. Sidney Burrus authored notes on the Fast Fourier transform. The treatment includes the prime-factor algorithm, which exploits coprime transform lengths to reorganize a discrete Fourier transform. A suitable index map separates the calculation into smaller transforms without the interstage twiddle multiplications required by the usual Cooley-Tukey arrangement.[ref]
Cyclic convolution 2026-10-20
For arrays indexed by integers modulo , their cyclic convolution isWhen and count choices with respective residue classes and , the cyclic convolution counts pairs whose sum has residue class . Repeated cyclic convolution therefore counts sums of longer sequences. The discrete Fourier transform converts cyclic convolution into pointwise multiplication.
Digital signal processing 2026-11-05
Digital signal processing transforms or analyzes signals represented by numerical sequences. A physical input commonly passes through signal sampling and quantization before an algorithm filters or transforms it. Sampling chooses times; quantization chooses a finite set of representable values. A discrete-time signal is a sequence indexed by integers, whereas a digital implementation also has finite precision.[ref]
What the Nyquist Criterion Means to Your Sampled Data System Design by Walt Kester. MT-002, introductory sampling chain and sampled spectra
An elementary digital filter averages adjacent samples:For a constant sequence it preserves the value. For an alternating sequence it gives zero. If the input noise samples are independent with variance , the output noise variance is , but neighboring output samples are now correlated because they share an input sample. Smoothing changes both the signal and its noise statistics.
Sampling can also erase distinctions before any algorithm runs. At sampling frequency ,These distinct analog frequencies produce the same samples. An anti-aliasing filter limits unwanted input frequencies before conversion; later computation cannot uniquely recover which of these unrestricted inputs produced the sequence.[ref]
What the Nyquist Criterion Means to Your Sampled Data System Design by Walt Kester. MT-002, Nyquist-zone folding and anti-aliasing discussion
Fourier analysis and the discrete Fourier transform help reveal frequency content, while finite-word arithmetic introduces an additional error budget. The sampling rate, numerical representation and intended physical bandwidth are therefore part of the processing design.
Discrete convolution Created 2026-09-24 Updated 2026-10-14
For sequences indexed by the integers, discrete convolution adds products whose indices sum to the output index:For finite sequences, treat every unspecified entry as zero; the sum then has finitely many nonzero terms. For infinite sequences, a convergence hypothesis is needed, for example absolute summability of both sequences.
Take at indices and at indices . Their convolution is at indices :Equivalently, : add an unshifted and a one-step shifted copy of . This explains the output by superposition, with every index included.
Discrete convolution combines index pairs, shifted copies, polynomial coefficients and outcome counts
. Details. The same products appear in polynomial multiplication and generating functions:A term times contributes to coefficient , precisely the index condition in discrete convolution. In probability, counts the outcomes of two independent fair coin tosses by their number of heads, while counts the outcomes of one more toss. Dividing the output by eight gives the probability mass function of the binomial distribution with and . No new arithmetic is needed to pass from coefficient multiplication to counting independent sums.
The full finite convolution is different from circular convolution, where indices wrap modulo a chosen length. Wrapping this four-term output to length three adds its last entry to its first and gives . When using a discrete Fourier transform to compute the full convolution, zero padding to length at least the sum of the input lengths minus one prevents this wraparound. [ref]
https://ocw.mit.edu/courses/res-6-008-digital-signal-processing-spring-2011/610905d8154ec2bfc090cf78022249a5_MITRES_6_008S11_lec10.pdf. Oppenheim, MIT Digital Signal Processing, Lecture 10, circular convolution and zero padding
Discrete cosine transform from an even-reflected discrete Fourier transform Created 2026-09-24 Updated 2026-11-05
To compute the type-II discrete cosine transform in the conventionreflect the inputs evenly to length : and for . If is the negative-exponent discrete Fourier transform, pairing the two reflected terms givesConsequently . The phase rotation and factor one half are consequences of the half-sample reflection and this normalization. One Fast Fourier transform of length plus extra work therefore computes the discrete cosine transform. Other library conventions can include a factor two or mode-dependent normalization.[ref]
https://www.fftw.org/fftw3_doc/Real_002dto_002dReal-Transform-Kinds.html. FFTW manual, REDFT10: DCT-II and logical transform length 2n
Discrete Fourier conjugate symmetry Created 2026-10-14 Updated 2026-10-18
For real samples, taking the complex conjugate of the forward discrete Fourier transform changes the exponent's sign and proves the displayed symmetry. Hence is real; for even , is also real. In the eight-sample example, and . This is the finite counterpart of conjugate symmetry of trigonometric polynomial coefficients. It reduces storage for real signals and provides a quick consistency check on a computed discrete Fourier transform.
Discrete Fourier transform Created 2026-09-24 Updated 2026-10-18
The discrete Fourier transform turns a finite list of samples into the weights of its discrete Fourier modes. The goal is to reveal a simple oscillatory recipe hidden in complicated-looking data, while retaining enough information to reconstruct every sample exactly. In signal processing, those weights identify sampled frequencies and wave phases; in numerical analysis, they simplify circular convolution and the discrete sine transform Poisson solver.
Start with eight real samples, indexed by :Writing , the actual list isThe discrete Fourier transform recovers the recipe asThe constant contributes ; the cosine contributes ; the half-sized sine contributes and . All other coefficients vanish exactly. The imaginary coefficients carry the sine's wave phase, which a plot of absolute values alone would hide.
Precisely, for a positive integer and a vector , the forward discrete Fourier transform and inverse discrete Fourier transform used here areThus the forward exponent has a minus sign and no scale factor; the inverse exponent has a plus sign and the factor . The coefficients in the reconstruction are , rather than . In the example, , the pair reconstructs the cosine, and the pair reconstructs the half-sized sine. These conventions agree with the scaled Fourier coefficients in MIT's authored notes.[ref]
https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/06d7972059805d20e6a7db3a52ec23f2_MIT6_02F12_chap13.pdf. Hari Balakrishnan, Christopher Terman, and George Verghese, MIT 6.02 notes, Chapter 13, equations (13.15)–(13.16), 2012
The proof idea is orthogonality of roots of unity: for integers ,Distinct discrete Fourier modes cancel in this finite geometric series. Substituting the forward formula into the inverse discrete Fourier transform leaves only the desired sample. The same orthogonality makes the normalized discrete Fourier modes an orthonormal basis and gives the discrete Parseval identity, in the present convention,For the eight-sample example, direct squaring gives , while , so . This identity preserves the squared L2 norm after accounting for normalization. The existing discrete Parseval identity instead scales the forward discrete Fourier transform by , producing a unitary matrix and equal squared L2 norms without the factor .
For real input, discrete Fourier conjugate symmetry pairs positive and negative frequencies. The label is a residue modulo : when represents the same discrete Fourier mode as , since . It therefore represents negative frequency cycles per sample. If samples are seconds apart, the corresponding signed frequency is cycles per second. Similarly, index represents , while index is its own negative modulo .
The discrete Fourier transform is an invertible map between two finite vectors. The continuous Fourier transform instead describes a function on the real line by an integral over a continuous frequency variable. A finite list of samples does not determine the full continuous frequency spectrum: aliasing of discrete Fourier modes already supplies distinct waveforms with identical observations. Applying the inverse formula at arbitrary integer indices gives the periodic extension of a finite sequence, repeating the recorded block every samples. This is a property of that representation, rather than evidence that the physical signal repeats beyond the recording. Laurent Demanet's MIT notes place the discrete Fourier transform alongside the continuous Fourier transform and Fourier series to explain the role of sampling and repetition.[ref]
https://math.mit.edu/icg/resources/teaching/18.330/18.330-Mar21.pdf. Laurent Demanet, Introduction to Numerical Analysis, MIT 18.330, §§6.2–6.3, pp. 57–60, March 22, 2012
The beauty is that a change of basis exposes cancellation and structure without losing data. Direct evaluation needs sums of terms; a Fast Fourier transform computes the same discrete Fourier transform with far less work. Computational speed and the mathematical meaning of the coefficients are separate questions.
Discrete Parseval identity 2026-10-14
With normalization , the discrete Fourier transform is a unitary matrix. Orthogonality of the roots-of-unity vectors gives the displayed identity. Multiplying both sides by the grid spacing gives the corresponding discrete L2 norm. Modal contraction therefore proves grid-norm contraction without a mesh-dependent change-of-basis constant.
Discrete-time Fourier transform 2026-11-05
The discrete-time Fourier transform represents a sequence indexed by integer sample number using a continuous, periodic frequency variable. In cycles per sample, the transform pair isFor an absolutely summable sequence, the sum converges uniformly to a continuous function, and the inverse formula follows by integrating the exponentials term by term. Their integral over one frequency period is one when the integer exponent is zero and zero otherwise. The primary text gives the same pair in angular frequency , where the inverse integral carries a factor .[ref]
Because , . Discrete time therefore does not imply discrete frequency: the DTFT is defined at every frequency in one period. With sampling frequency , a physical frequency corresponds to ; frequencies separated by integer multiples of give identical sampled complex exponentials. This is the basic frequency ambiguity behind aliasing.
An original two-sample example takes and all other entries zero. ThenAt zero frequency its value is one; at its magnitude is with phase ; at it vanishes. As the impulse response of a two-tap moving average, it preserves a constant input and removes an alternating-sign input. SciPy’s frequency-response definition evaluates precisely such sums when its denominator is one; its frequency units depend on the fs parameter.[ref]
For a finite record extended by zero, the unnormalized discrete Fourier transform gives samples of the same continuous function:Zero padding the record to length instead evaluates on a denser grid. It does not change or restore unobserved time samples. The rectangular window and Hann window demonstrate how the selected finite record shapes that continuous response.
Convergence assumptions matter. For when , zero otherwise, and , the geometric sum givesAt , that ordinary convergent-sum argument fails. Square-summable sequences admit an interpretation, while perpetual tones require a generalized interpretation; neither should be treated as an absolutely convergent version of the same series without stating the interpretation.
A useful check of numerical transform conventions is to evaluate a finite sum at arbitrary frequencies, compare its DFT-grid values with the FFT output, and repeat after zero-padding. This tests the exponent sign, normalization and frequency units independently. In a physical acquisition, one must also state sampling rate, record duration and the response before sampling; dense numerical frequency points alone do not validate those experimental inputs.
For periodic indexing let be the unitary forward shift. The operator is . A discrete Fourier transform diagonalizes it with eigenvalue and real part . Consequently for every , uniformly in the grid. Equivalently , proving decay of the discrete energy directly. The result is semidiscrete stability; a further time discretization must also have adequate absolute stability.
Even--odd fast Fourier transform recursion Created 2026-09-24 Updated 2026-11-05
For even length , split the input of a discrete Fourier transform into its even and odd samples, and . Let be their length- discrete Fourier transforms, with negative-exponent convention. Splitting the original sum by the parity of its index gives, for ,The sign change follows from . Thus the same two short transforms supply both halves of the result through an FFT butterfly. For , recursive splitting reaches length one after levels. Each level needs arithmetic operations, so the time complexity is . For example, a length-four transform uses the two length-two transforms of and , then twiddle factors and .[ref]



