decimationintime

Decimation in time, often abbreviated as DIT, is a method for computing the discrete Fourier transform (DFT) as part of the fast Fourier transform (FFT) family. In DIT, the input sequence is decimated in time, meaning that even- and odd-indexed samples are separated and processed separately. This enables recursive or iterative butterfly computations that combine pairs of complex values with appropriate twiddle factors. DIT reduces the computational burden from O(N^2) to O(N log N) for sequences of length N, typically a power of two, making it a cornerstone of many FFT implementations.

In a radix-2 DIT FFT, the input data are frequently arranged in bit-reversed order before processing, or a corresponding bit-reversal permutation is carried out as part of the first stage. The core operation at each stage is the butterfly, which combines two values using a twiddle factor W_N^k = e^{-2π i k / N}. The final stage yields the frequency-domain samples in natural order, after which no additional reordering may be necessary depending on the implementation. DIT is contrasted with decimation in frequency (DIF), where the decimation occurs in the frequency domain and the bit-reversal ordering is typically applied to the output.

Applications and variants: DIT supports common FFT lengths such as powers of two and can be extended with different radices (e.g., radix-4). It is widely used in digital signal processing hardware and software due to its straightforward data flow and in-place computation capabilities. While highly efficient for many real-time processing tasks, DIT requires careful data arrangement to maintain memory access efficiency.