Design methodology for resource efficient implementation of fast fourier transform cores on field programmable gate arrays

Abstract

This thesis presents an efficient methodology for the hardware implementation of the Pease Fast Fourier Transform (FFT) radix-2 algorithm, in which, structural regularity from the Kronecker formulation is exploited to perform vertical folding of the transform. An address generator approach is proposed for both, data permutation and phase factor scheduling throughout the stages. The steps required for mapping the methodology onto hardware are explained. The scalability of the core structure is demonstrated by being able to scale the transform size and also by offering the possibility to scale in performance using 2 or 4 processing elements simultaneously. A particular implementation on an FPGA is described analysing its resource consumption and computation speed perspectives. A comparison is provided taking as reference the commercial radix-2 burst I/O FFT core from the FPGA manufacturer Xilinx. When a single processing element is used, an improvement of up to 42% is achieved in logic resource consumption (slices) and up to 29% in the computa- tion performance aspect. When 4 processing elements are used, the performance improvement is up to 81%. A conclusion chapter is provided, remarking the main contributions and possible future directions of this work.

Esta tesis presenta una metodología eficiente para la implementación en hardware del algoritmo radix-2 de transformada rápida de Fourier (FFT) propuesto por Pease, en el cual se ha explotado la regularidad de su formulación Kronecker para realizar el doblez vertical de la transformada. Se ha propuesto el uso de generadores de direcciones para el acceso a los datos, así como a los factores de fase a través de las etapas. Los pasos requeridos para trasladar el concepto de la metodología a hardware son explicados. La escalabilidad de la estructura del núcleo es demostrada siendo capaz de variar el tamaño de la transformada y ofreciendo la posibilidad de usar 2 o 4 elementos de procesamiento simultaneamente. Se describe la implementación en un dispositivo arreglo de compuertas programable en campo (FPGA), analizando las perspectivas de rendimiento y uso de recursos. Se provee una comparación tomando como referencia el núcleo FFT radix-2 Burst i/o del fabricante de FPGAs Xilinx. Cuando solo un elemento de procesamiento es usado, se alcanza una mejora de hasta 42% en uso de recursos lógicos y de hasta 29% en rapidez de computo. Cuando 4 elementos de procesamiento son usados, la mejora en rapidez de cómputo llega hasta un 81%. Un capítulo de conclusiones es provisto, en el cual se subrayan las principales aportaciones y posibles direcciones futuras de este trabajo.