Tesis:
Efficient hardware architectures for the computation of the FFT and other related signal processing algorithms in real time
- Autor: GARRIDO GALVEZ, Mario
- Título: Efficient hardware architectures for the computation of the FFT and other related signal processing algorithms in real time
- Fecha: 2009
- Materia: Sin materia definida
- Escuela: E.T.S. DE INGENIEROS DE TELECOMUNICACION
- Departamentos: SEÑALES, SISTEMAS Y RADIOCOMUNICACIONES
- Acceso electrónico: http://oa.upm.es/57219/
- Director/a 1º: GRAJAL DE LA FUENTE, Jesús
- Resumen: 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. Por otra parte, para obtener las mayores prestaciones de procesado de señal hay que recurrir a dispositivos programables como las FPGAs (Field Programmable Gate Array). Por ello en la tesis se estudian aquellas arquitecturas circuitales que pueden ser programadas en este tipo de dispositivos. Además, de las arquitecturas existentes se consideran fundamentalmente las denominadas en pipeline, puesto que con ellas se pueden obtener los mejores resultados de 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-22 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 propone la primera arquitectura en pipeline de la RFFT. Con ella 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 de la STFT de manera eficiente. Respecto a la FFT bidimensional se ha abordado el problema de transponer una matriz, que 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 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 con altas prestaciones 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. ----------ABSTRACT---------- The present thesis deals with the development of efficient hardware architectures for the real-time computation of several algorithms related to the Fourier transform. Specifically, it focuses on the analysis and design of hardware circuits that calculate the FFT (Fast Fourier Transform), the RFFT (Real-Valued Fast Fourier Transform), the STFT (Short- Time Fourier Transform) and the 2D-FFT (Bidimensional Fast Fourier Transform). On the other hand, in order to get the highest signal processing performance it is necessary to resort to programmable devices such as FPGAs (Field Programmable Gate Array). Thus, the thesis considers those hardware architectures that are implementable in this kind of devices. Moreover, among the existing architectures, pipelined ones have been mainly considered, because they can achieve the best real-time results. With this goal, a new model based both on the hypercube theory and on bit-dimension permutations is proposed. It links the signal processing algorithms to their hardware architectures. Thus, it permits to determine those features of the algorithm that the architecture must fulfill. This makes the model not only useful for the analysis of existing hardware architectures, but it can also be used for the design of new architectures. Among the proposed designs, the new hardware architectures for the computation of the FFT permit to calculate the transformation over any number of parallel samples. According to this, the throughput of the FFT can be arbitrarily chosen. Moreover, the use of radix-22 in these architectures permits to reduce the number of components with respect to those required by other radices. On the other hand, the thesis proposes the first pipelined hardware architecture for the computation of the RFFT. This architecture achieves high real-time performance by using less hardware resources than those used in other approaches. Moreover, the designs proposed for the FFT and the RFFT can also be used for an efficient computation of the STFT. With regard to the 2D-FFT, the problem of transposing a matrix has been studied, which is the bottleneck of the system when the computations are preformed in real time. Thus, it has been seen that it is possible to use certain strategies for reading and writing in the memory that permit to transpose a series of matrices by using a memory equal to the number of samples of the transformation. This makes it unnecessary to resort to strategies such as the double-buffering. On the other hand, the thesis proposes an improvement of the CORDIC algorithm for the computation of the rotations of the FFT. The main advantage lies in the fact that the circuit does not need any memory for storing the rotations, due to the fact that they can be generated by a simple circuit. This improvement is relevant for large FFTs, since the size of the rotation memory usually increases linearly with the number of points of the FFT. Finally, it is important to remark that the algorithms studied in the thesis are a key element in a large number signal processing applications. Furthermore, the evolution of many of these applications consists in obtaining the results in real time. Consequently, the thesis offers a wide range of solutions for many current applications, as well as opens new possibilities for the development of future applications.