decimationinfrequency

Decimation in frequency, also known as decimation-in-frequency (DIF), is a method for computing the discrete Fourier transform (DFT) efficiently as part of the fast Fourier transform (FFT) family. It is one of the two canonical forms of the radix-2 Cooley–Tukey FFT, the other being decimation in time (DIT). In DIF, the decimation occurs in the frequency domain, and the computation proceeds by repeatedly splitting the DFT into smaller DFTs through butterfly operations that mix pairs of frequency components with appropriate twiddle factors.

Conceptually, DIF begins by partitioning the input spectrum into two halves. For each pair of frequency indices k and k+N/2 (where N is the transform length), it computes a sum and a difference, with the difference multiplied by a twiddle factor. A common first-stage update is: X'(k) = X(k) + X(k+N/2) and X'(k+N/2) = (X(k) − X(k+N/2)) · W_N^k, where W_N = e^(-j2π/N). The resulting sequence is then treated as two smaller N/2-point DFT problems, and the process is repeated across log2(N) stages. After the final stage, the outputs generally appear in bit-reversed order, requiring a final bit-reversal permutation to obtain the standard ordering.

DIF trades input-ordering and data flow to produce an efficient in-place computation, which can be advantageous for certain hardware architectures and streaming implementations. It is often contrasted with DIT, which decimates in time and yields natural output order. Both forms have equivalent computational complexity, O(N log N), and are widely used in digital signal processing and real-time applications.