APP REPORT: Implementing Fast Fourier Transform Algorithms of Real-Valued Sequences with the TMS320 DSP Family

In This Issue
   DSP Solutions
Bridging the Gap
Digital Subscriber Line is
   the future of remote
   access technology
ADSL: A visionary architecture
   that meets changing market
   needs
High-speed networking over
   ordinary phone lines
TI acquires software tools
   maker GO DSP
TI's third-party network extends
   design team
App Report: Implementing Fast
   Fourier Transform Algorithms
   of Real-Valued Sequences with
   the TMS320 DSP Family

   Wireless
The next generation
Boom days ahead for the
   wireless market
Symposium maps the future
   of wireless
Sharing the knowledge
Zeroing in on the market
Technical details a few
   keystrokes away

   Mixed-Signal and Analog
Future Electronics becomes
   U.S. TI distributor
PCM codec-filter combo
   support four channels on a
   single chip
10-bit analog-to-digital converter
Gigabit ethernet transceiver

Support from PIC

Trade Shows

APP REPORT

Implementing Fast Fourier Transform Algorithms of Real-Valued Sequences with the TMS320 DSP Family: The Fast Fourier Transform (FFT) is an efficient computation of the Discrete Fourier Transform (DFT) and one of the most important tools used in digital signal processing applications. Some of the applications that take advantage of the computational savings of FFT include Assymetrical Digital Subscriber Line (ADSL) technology, radar applications and medical imaging. Because of its well-structured form, the FFT is a benchmark in assessing digital signal processor (DSP) performance.

The development of FFT algorithms has assumed an input sequence consisting of complex numbers. This is because complex phase factors, or twiddle factors, result in complex variables. Thus, FFT algorithms are designed to perform complex multiplications and additions. However, the input sequence consists of real numbers in a large number of real applications.

This application report discusses the theory and usage of two algorithms used to efficiently compute the DFT of real-valued sequences as implemented on the Texas Instruments TMS320C6x ('C6x). The application report provides C code, which allows easy porting to other TI DSPs.

The first algorithm performs the DFT of two N-point real-valued sequences using one N-point complex DFT and additional computations.

The second algorithm performs the DFT of a 2N-point real-valued sequence using one N-point complex DFT and additional computations. Implementations of these additional computations, referred to as the split operation, are presented both in C and 'C6x assembly language. For implementation on the 'C6x, optimization techniques in both C and assembly are covered.

Comparison of computational complexity for direct computation of the DFT vs. the Radix-2 FFT algorithm

Direct computation Radix-2 FFT

Number
of points Complex multiples Complex additions Complex multiples Complex additions

N
4 N²
16 N²-N
12 (N/2)log₂N
4 Nlog₂N
8

16
64 256
4096 240
4032 32
193 64
384

256
1024 65536
1048576 65280
1047552 1024
5120 2048
10240

This table compares the number of math computations involved in direct computation of the DFT versus the radix-2 FFT algorithm. As you can see, the speed improvement of the FFT increases as N increases.