Study of accuracy and hardware performance in discrete transforms and their fast algorithms

Abstract

Nowadays, during the design of digital arithmetic units, most research efforts are centered in finding algorithms that reduce resource consumption or latency. Efforts to find algorithms that provide higher accuracy are scarce. This thesis presents a study of accuracy and hardware performance of discrete transforms and their fast algorithms. The discrete transforms studied included the Fourier (DFT), the Hartley (DHT), and the cosine (DCT) direct algorithms. The fast DFT treatments were the Cooley-Tukey and Pease. The fast DHT treatments included the Bracewell and Hou. In the case of the DCT the fast treatments evaluated were the Nikara and Translation. This work used approximation and statistical methods for the accuracy analysis. These methods quantify the normwise relative error of the discrete transform treatments and determine significant differences in their accuracy. For the hardware performance analysis, a FPGA synthesis methodology was adopted to quantify resource consumption and latency of the treatments. The results of the study showed that the discrete transforms direct treatment provide higher accuracy, and the highest resource consumption and latency. We observed in the accuracy analysis that as the resolution of the discrete transform computation incremented, the range magnitude of the treatments experimental normwise relative error incremented. But the range magnitude of the fast algorithms treatments incremented at a higher scale.

Actualmente, durante el diseño digital de unidades aritméticas, los esfuerzos se centran en buscar algoritmos que reduzcan el consumo de recursos o latencia. Esfuerzos para encontrar algoritmos que provean mayor exactitud son descuidados. Esta tesis presenta un estudio de exactitud y desempeño hardware de transformadas discretas y sus algoritmos rápidos. Las transformadas discretas estudiadas fueron las formulaciones directas de Fourier (DFT), Hartley (DHT) y coseno (DCT). Los algoritmos rápidos de la DFT fueron Cooley-Tukey y Pease. Para la DHT los algoritmos rápidos fueron Bracewell y Hou. Los algoritmos rápidos de la DCT fueron Nikara y Traslación. Este trabajo utiliza métodos de aproximación y métricas estadísticas para el análisis de exactitud. Los mismos cuantifican el error de los tratamientos y determinan diferencias significativas en su exactitud. Para el análisis de desempeño hardware, se opto por una metodología de síntesis de FPGA. Los resultados mostraron que las formulaciones directas de las transformadas discretas proporcionan mayor exactitud, consumo de recursos y latencia. En el estudio se observo que a medida que aumenta la resolución del computo de una transformada discreta, la magnitud del rango del error relativo normalizado experimental de los tratamientos aumenta. La diferencia significativa entre los tratamientos fue que la escala en que aumenta la magnitud del rango de los tratamientos de algoritmos rápidos es mayor.