Methods for scalable levels of parallelism in radix-2 ffts for fpga synthesis

Abstract

The Fast Fourier Transform (FFT) is the main block in many communication systems and signal processing applications, as it allows the fast computation of the discrete Fouier transform (DFT). The DFT, in turn, is used to obtain the spectrum of any finite discrete signal. Hardware implementations of this operation are highly regarded as they provide improved performance with respect to software-based implementations. The purpose of this work was developing a consistent and scalable procedure of generating the address patterns of permutation for any power-of-2 transform size and any folding factor in FFT cores with addressing schemes. Our approach was, mainly, based in 2 memory blocks, an address generator, and radix-2 butteries. The number of butteries determines the level of parallelism. The expected high performance of this FFT core lies in the fact it does not need dedicated permutation hardware between stages. Instead, the data ow is controlled by an address generator. Using this scheme, the impact on consumed resources is significantly mitigated when the number of points of the core is increased. As a result, we obtained a fully scalable FFT core including parallelism level, number of points, and numeric format using this approach.

La Transformada Rápida de Fourier (FFT por sus siglas en ingles) es el bloque principal en muchos sistemas de comunicación y aplicaciones de procesamiento de señales, ya que permite la rápida computación de la Transformada Discreta de Fourier (DFT por sus siglas en ingles). Por su parte, la DFT es usada para obtener el espectro de cualquier señal discreta finita. Las implementaciones en hardware de esta operación son altamente apreciadas debido a que proveen mayor rendimiento con respecto a las implementaciones basadas en software. El propósito de este trabajo fue el desarrollar un procedimiento consistente y escalable para generar los patrones de direccionamiento de las permutaciones para cualquier tamaño de transformada potencia de 2 y cualquier factor de plegado en núcleos FFT con esquemas de direccionamiento. Nuestro diseño se baso, principalmente, en 2 bloques de memoria, un generador de direcciones y mariposas base 2. El numero de mariposas determina el nivel de paralelismo. El alto rendimiento del núcleo radica en el hecho de que el flujo de datos es controlado por un generador de direcciones, el cual mitiga el consumo de recursos cuando se incrementa el numero de puntos de la FFT. Como resultado, se obtuvo una implementación de FFT enteramente escalable incluyendo el nivel de paralelismo, numero de puntos y formato numérico usando este enfoque.