Irving Olmedo

.

Faculty Mentor: Arvind Mithal

Direct Supervisor: Abhinav Agarwal

Home University: University of Texas, Tyler

Major: Electrical Engineering

 .

Biography

My name is Irving Olmedo. I am a senior in the Electrical Engineering program at the University of Texas at Tyler. I enjoy playing XBOX as well as playing music. I sing, play the guitar, bass guitar, drums, and keyboard. I love going to school and learning new things. I plan to one day be a professor and pass on my knowledge to others. As far as research interests, I am very passionate about computer hardware specifically ways to deal with security problems at the hardware level. This day in age everyone is connected to everyone via different layers of networks. There is not one definitive scheme for system security based on hardware and would like to contribute towards a protocol.

Abstract

Using Bluespec for Rapid Prototyping the Sparse FFT Algorithm

In digital processing, the Fast Fourier Transform (FFT) is used in everything from frequency spectral analysis, data compression, to solving differential equations. In certain cases, for example video signals, most of the frequency coefficients of the transform are negligible or zero. Professor Indyk and Professor Katabi in the Computer Science and Artificial Intelligence Lab (CSAIL) at MIT proposed an algorithm, which takes advantage of such a case where the signal in the frequency domain is sparse, that is most coefficients are zero or close to it, known as the Sparse Fast Fourier Transform (sFFT). The sFFT uses randomized hashing functions along with windowing filters to bin large frequency coefficients into small number of buckets. The sFFT computes the transform only on that subset of buckets decreasing to sub-linear computational times for cases where the signal is sparse. Bluespec Systems Verilog (BSV) is a high-level hardware description language (HDL) that features a powerful compiler with the capability of fully synthesizable designs. The high-level programming schemes along with total atomicity and concurrency make BSV designs easy to modify and experiment with; allowing rapid hardware intellectual property (IP) creation and prototyping. The sFFT shows sub-linear run times in computer simulations and the next step forwards is creating dedicated hardware with BSV. The project starts from the bottom up, focusing on creating hardware implementation of the basic operations of the algorithm. This includes creating specialized modules for complex division, binary fixed point arithmetic, and efficient modulo operation. The hardware prototypes will be synthesized for FPGAs to allow improved performance as compared to the software implementation. This project marks the beginning of the sFFT IP and examines the challenges moving forward.