Cooley-Tukey FFT and its Variants - Cooley-Tukey FFT and its Variants - 2026.1 English - XD100

Vitis Tutorials: AI Engine Development (XD100)

Document ID
XD100
Release Date
2026-06-23
Version
2026.1 English

The literature typically refers to the FFT algorithm as the version proposed by Cooley and Tukey. This version usually applies to signals with a number of points equal to a power of two.

The original algorithm decomposes the discrete Fourier transform computation of a function with \(N\) points when \(N\) is a composite number \((N=N_1 \cdot N_2)\). It does this by computing \(N_1\) DFTs of size \(N_2\). You can use this algorithm recursively on functions with a power of 2 points to perform a series of simple few-point DFTs. This achieves a \(O(N\cdot log_2(N))\) computational complexity (also called loglinear).