Stage 0: Input (Bit-Reversed Order)
Input values are reordered using bit-reversal permutation
Watch the Cooley-Tukey butterfly operations in action
Input values are reordered using bit-reversal permutation
The FFT reduces the complexity of computing the Discrete Fourier Transform from O(N²) to O(N log N) by exploiting symmetries in the calculation.
Butterfly Operation: The core of the FFT. Two values are combined using a twiddle factor (W): output₁ = input₁ + W·input₂, output₂ = input₁ - W·input₂
Stages: For N points, there are log₂(N) stages. Each stage performs N/2 butterfly operations.
Bit-Reversal: Input indices are reordered by reversing their binary representation before processing.