IP Corner: Fast Fourier Transforms (FFTs) in LabVIEW FPGA

Since the release of NI LabVIEW 8.5 software, the new fixed-point numeric data type has opened up an entirely new world of possibilities for signal processing in LabVIEW FPGA. The most recent example is the widely requested IP for performing fast Fourier transforms (FFTs), which is now available on IPNet. This new group of subVIs also introduces an architecture for streaming data between different processing functions using Boolean control lines and FIFOs. In this issue of IP Corner, learn how to use the new FFT IP and take LabVIEW FPGA processing performance into the frequency domain.

FFT algorithms are optimized to turn a 2ⁿ block size of time waveform data into the corresponding frequency data with 2ⁿ frequency bins. The frequency resolution depends on the sample rate and the number of samples in the block. For example, 1024 (or 2¹⁰) samples of a signal sampled at 100 kS/s has a frequency resolution of 97.65625 Hz per bin.

 

100 kHz/1024 = 97.65625 Hz

 

This means that each frequency bin represents the total amount of energy at that particular frequency, and frequencies between those values get spread across multiple bins. The first point corresponds to 0 Hz (DC component), the second point corresponds to 97.65625 Hz, the third point corresponds to 195.3125 Hz and so on.  As we get to the middle values, the 511th point corresponds to 49804.6875 Hz, the 512th point corresponds to 49902.34375 Hz and at the 513th point, we get frequency information at 50 kHz. We know from the Nyquist sampling theorem that sampling at 100 kS/s will only measure frequencies up to 50kHz, so what happens to the 514th point?  Well, all points after the Nyquist frequency begin to represent negative frequency values.  The 514th point corresponds to -49902.34375 Hz, the 515th point corresponds to -49804.6875 Hz and so on.  The final 1024th point, therefore, represents frequency information at -97.65625 Hz.  

The FFT algorithm works for both real or complex input signals, but the resulting frequency data is always complex.  Most real-world signals have no imaginary components, and these purely real signals produce an FFT that is symmetric about the DC component at 0 Hz. This means that values at negative frequencies are exactly the same as their positive counterparts, and those points are considered redundant.  If you took the FFT of a real input signal of 1024 samples, all useful information is really only in the first 513 frequency bins, and the remaining 511 bins are often ignored.

For more information on the fundamentals for FFTs, please see the Using Fast Fourier Transforms tutorial.

 

[+] Enlarge Image

Figure 1. New FFT IP for LabVIEW FPGA

The inherent hardware parallelism you get with field-programmable gate arrays (FPGAs) is ideal for parallel signal processing; however, it also introduces the additional complexity of synchronizing data between operations running at different rates. Various algorithms take a different number of clock cycles to complete, and if a piece of processing IP is expecting data to be available before it’s actually ready, all data can become corrupted without warning. For this reason, the new FFT subVIs include new Boolean control lines that will become the standard way to pass data between different functions and loops on the block diagram. The new Boolean control lines, shown in Figure 1 (bottommost green input and output lines), are called input valid, output valid, and ready for input.

 

[+] Enlarge Image

Figure 2. Example LabVIEW FPGA Block Diagram Using new FFT IP

The top loop in Figure 2 is a basic data acquisition (DAQ) loop that samples Analog Input Channel 1 at a specified rate and passes values directly to a first-in-first-out (FIFO) memory buffer named the DAQ FIFO. LabVIEW FPGA local FIFOs are the best way to pass data between different parts of the block diagram and smooth out transitions between asynchronous loops.

The bottom loop in Figure 2 is the FFT processing loop that executes at 40 MHz. During the first iteration of this loop, the reset control line is asserted and both case structures are initialized to false case. Once the FFT subVI is ready to start accepting data, the ready for input control line becomes TRUE and the left-side case structure switches to the true case (shown in Figure 3).

 

[+] Enlarge Image

Figure 3. FFT Processing Loop with True Case Shown in Left-Side Case Structure

Values acquired in the data acquisition loop are passed from the DAQ FIFO one at a time to the Real Data input of the FFT subVI. As mentioned earlier, most real-world signals have no imaginary components.  Since the samples coming from the data acquisition loop are purely real, a zero value is wired to the Imaginary Data input. Because this sub-VI implements all FFT calculations using fixed-point math, the 16-bit integer values are converted into a 16-element Boolean array, and then into the fixed-point data type.

 

Even though the FFT subVI might be ready to start accepting values, there is still a possibility that the DAQ FIFO is empty because data has yet to be acquired. To account for this, the Timed Out? output from the DAQ FIFO is inverted by a NOT function and wired to the input valid input of the FFT subVI. If the DAQ FIFO is empty, the FIFO times out and input valid is FALSE. The FFT subVI ignores all data inputs unless input valid is TRUE.

 

After the first 1024 points have been acquired and passed to the FFT subVI, it sets ready for input to FALSE and stops reading elements out of DAQ FIFO while it continues to calculate the FFT. Depending on the block size and implementation of the FFT you are calculating, this could take thousands of iterations and the output valid line remains FALSE to ensure that the right-side case structure remains at the False case. As soon as the first frequency domain point is ready to be passed out of the FFT subVI, the output valid line is set to TRUE and the valid frequency data is passed to a DMA FIFO named DMA to Host (shown in Figure 4).

 

[+] Enlarge Image

Figure 4. FFT Processing Loop with True Case Shown in Right-Side Case Structure

After the first 512 points have been calculated and passed from the FFT subVI, it is ready to start accepting the next 1024 points of time-domain waveform data. Figure 5 shows the FFT processing loop with both case structures in the True case.

 

[+] Enlarge Image

Figure 5. FFT Processing Loop with True Case Shown in Both Case Structures

The DMA to Host FIFO takes care of passing data from memory in the FPGA chip directly to random access memory (RAM) on the host computer. It is important to note that if the host computer cannot read data from its RAM buffer fast enough, the DMA FIFO eventually fills up and the DMA to Host FIFO times out. The way this example is written, a time out means that the last element was essentially lost and the entire data set has been corrupted. This is why the Timed Out? output is wired to the stop condition of the FFT processing loop.

FFT is only the beginning of new LabVIEW FPGA signal processing IP that is now possible with the fixed-point data type. This article discussed a single “burst” implementation of FFT (optimized for size and resource usage), but the same approach applies to higher-speed implementations and larger block sizes. In reality, there are thousands of different ways to implement the FFT algorithm, and the greatest benefit of having the LabVIEW FPGA community and IPNet is the ability to share LabVIEW FPGA IP optimized for the thousands of different applications out there.

 

Related Links

IPNet

NI Developer Zone Community

Learn More about FPGA Technology

NI LabVIEW FPGA

 

IP Corner addresses issues and presents technical information on LabVIEW FPGA application reusable functionality, also known as FPGA IP. This article series is designed for those interested in learning, testing, or discussing topics to make FPGA designs better and faster through the reuse of IP.

Reader Comments | Submit a comment »