Top: FFT on an FPGA

# Introduction

I spend a fair bit of time working with GNU Radio which is a framework for creating software-defined radios, in which processing that is typically done on a digital signal processing (DSP) chip is moved to a standard CPU. The hardware I use is a USRP B100 which acts as the interface between GNU Radio and my antenna. The USRP B100 contains a Field-Programmable Gate Array (FPGA) which takes care of some of the signal processing steps that cannot be done on the CPU.

There are occasions where parts of the desired signal processing chain are running too slowly on my computer, and then it makes sense to move these parts onto the FPGA of the USRP.

In this document I will be showing how I moved a particular algorithm (FFT) onto the FPGA of my USRP B100.

A discrete fourier transform (DFT) takes a series of numbers, $$x_n$$, and transforms it into another series of numbers, $$X_k$$. If a value in $$x_n$$ provides information about a signal at a point in time, then a value in $$X_k$$ provides information about a specific frequency in that signal. The DFT is defined as:

\begin{equation*} X_k = \sum_{n=0}^{N-1}{x_n e^{-2 \pi i k n/N}} \end{equation*}

A fast fourier transform (FFT) is an efficient implementation of a DFT. There are many common FFT algorithms used.

Because fourier transforms are so often used in digital signal processing and because the FFT is often a limiting factor, this algorithm is the first that I have attempted to implement in the FPGA of my USRP.

Next: Derivation of FFT algorithm