Efficient hardware architectures for the computation of the fft and other related signal processing algorithms in real time

Abstract

La presente tesis se centra en el desarrollo de arquitecturas de circuito de altas prestaciones para el cálculo en tiempo real de varios algoritmos de procesado de señal relacionados con la transformada de Fourier. En concreto, se aborda el análisis y diseño de circuitos que permiten obtener la FFT (Fast Fourier Transform), la FFT de entradas reales o RFFT (Real-Valued Fast Fourier Transform), la STFT (Short-Time Fourier Transform) y la FFT bidimensional o 2D-FFT. Para obtener las mayores prestaciones de procesado de señal hay que recurrir a dispositivos hardware como los ASICs (\Application Specific Integrated Circuit) o las FPGAs (Field Programmable Gate Array). En estos dispositivos es posible programar circuitos ad hoc que además funcionen a altas velocidades de reloj. Por ello en la tesis se estudian aquellas arquitecturas circuitales que pueden ser programadas en estos dispositivos. Además, de las arquitecturas existentes se consideran fundamentalmente las denominadas en pipeline, puesto que con ellas se pueden obtener las mayores prestaciones en tiempo real. Con este objetivo se propone un nuevo modelo basado en la teoría de hipercubos y en permutaciones bit-dimensionales de datos que permite relacionar los algoritmos de procesado de señal con sus arquitecturas circuitales. De esta forma es posible determinar aquellas características del algoritmo que la arquitectura debe cumplir. Ello hace que este modelo no sólo sirva para analizar los diseños existentes, sino que también se puede emplear para diseñar nuevas arquitecturas. Entre los diseños propuestos cabe destacar, por una parte, las nuevas arquitecturas para el cálculo de la FFT de cualquier número de muestras de entrada en paralelo. Así, es posible seleccionar arbitrariamente tasa de transferencia del circuito, que crece linealmente con el número de datos en paralelo que procesa. Además, el uso de radix-2^2 en estas arquitecturas permite reducir el número de componentes del circuito respecto a otros valores de radix. Por otra parte, en la tesis se presentan las primeras arquitecturas en pipeline de la RFFT. Con ellas se obtienen altas prestaciones en el cálculo de la RFFT en tiempo real, utilizando a su vez menos recursos que los empleados en otros diseños. Además, las arquitecturas propuestas de la FFT y RFFT se pueden emplear también para calcular la STFT de manera eficiente. Respecto a la FFT bidimensional se ha abordado el problema de transponer una matriz, que normalmente resulta ser el cuello de botella cuando los cálculos se realizan en tiempo real. Así, se ha visto que es posible seguir ciertas estrategias de lectura y escritura que permiten transponer series de matrices utilizando una memoria de tamaño igual al número de muestras de la transformación. Esto hace que no sea necesario recurrir a estrategias como el doble buffer. Por otra parte, se ha propuesto una mejora del algoritmo CORDIC para el cálculo de las rotaciones de la FFT. La mayor ventaja radica en el hecho del que el circuito no requiere el empleo de memoria para las rotaciones, puesto que es posible ir generando los valores de rotación. Esta mejora resulta importante cuando el número de puntos de la FFT es elevado, puesto que el tamaño de la memoria de rotaciones crece normalmente de forma lineal con dicho número. Finalmente, cabe destacar que los algoritmos estudiados son el elemento fundamental en un gran número de aplicaciones de procesado de señal. Además, la evolución de muchas de estas aplicaciones pasa por obtener los resultados en tiempo real. Por lo tanto, la tesis ofrece un gran abanico de soluciones para numerosas aplicaciones actuales, pero también abre las puertas para el desarrollo de aplicaciones futuras.