Notes on Digital Signal Processing: Practical Recipes for Design, Analysis and Implementation

Note 19. FFT: Prime Factor Algorithm

The radix-2 algorithms described in Notes 17 and 18 are very useful, but in certain situations, a DFT block size of 2^k is just not acceptable. The prime factor algorithm (PFA) is a technique for constructing fast transforms of length N, where N can be expressed as a product of mutually prime factors. A DFT of length N = N₁N₂ can be restructured as an N₁ by N₂ two-dimensional DFT:

19.1

where

W₁ = exp(–j2p/N₁)

W₂ = exp(–j2p/N₂)

In order to make use of the restructured transform, the one-dimensional input sequence, x[n], must be mapped into a two-dimensional sequence, x₂[n₁, n₂], using the index transformation ...