The Symmetric Group in Data Permutation, With Applications to High-Bandwidth Pipelined FFT Architectures

We have developed an efficient architecture for permuting data streams in-place based on properties of the symmetric group in abstract algebra. This architecture uses half the memory of a conventional double-buffering architecture with only a modest increase in addressing logic. The flexibility and efficiency of this permuter has enabled the development of an automatic generator of streaming Fast Fourier Transform (FFT) architectures capable of handling a configurable number of time samples in parallel. These architectures achieve 100% multiplier utilization efficiency, and require only 25% more buffering than the theoretical minimum for normal-ordered frequency output. We present parametrized generators of these permutation and FFT architectures in an open-source library targeting field programmable gate arrays.