0.11 Algorithms for data with restrictions

Algorithms for real data

Many applications involve processing real data. It is inefficient to simply use a complex FFT on real data becausearithmetic would be performed on the zero imaginary parts of the input, and, because of symmetries, output values would be calculatedthat are redundant. There are several approaches to developing special algorithms or to modifying complex algorithms for real data.

There are two methods which use a complex FFT in a special way to increase efficiency [link] , [link] . The first method uses a length-N complex FFT to compute two length-N real FFTs byputting the two real data sequences into the real and the imaginary parts of the input to a complex FFT. Because transformsof real data have even real parts and odd imaginary parts, it is possible to separate the transforms of the two inputs with 2N-4extra additions. This method requires, however, that two inputs be available at the same time.

The second method [link] uses the fact that the last stage of a decimation-in-time radix-2 FFT combines two independent transformsof length N/2 to compute a length-N transform. If the data are real, the two half length transforms are calculated by the methoddescribed above and the last stage is carried out to calculate the total length-N FFT of the real data. It should be noted that thehalf-length FFT does not have to be calculated by a radix-2 FFT. In fact, it should be calculated by the most efficient complex-dataalgorithm possible, such as the SRFFT or the PFA. The separation of the two half-length transforms and the computation of the last stagerequires $N-6$ real multiplications and $(5/2)N-6$ real additions [link] .

It is possible to derive more efficient real-data algorithms directly rather than using a complex FFT. The basic idea is fromBergland [link] , [link] and Sande [link] which, at each stage, uses the symmetries of a constant radix Cooley-Tukey FFT to minimizearithmetic and storage. In the usual derivation [link] of the radix-2 FFT, the length-N transform is written as the combination ofthe length-N/2 DFT of the even indexed data and the length-N/2 DFT of the odd indexed data. If the input to each half-length DFT isreal, the output will have Hermitian symmetry. Hence the output of each stage can be arranged so that the results of that stage storesthe complex DFT with the real part located where half of the DFT would have gone, and the imaginary part located where the conjugatewould have gone. This removes most of the redundant calculations and storage but slightly complicates the addressing. The resultingbutterfly structure for this algorithm [link] resembles that for the fast Hartley transform [link] . The complete algorithm has one half the number of multiplications and N-2 fewerthan half the additions of the basic complex FFT. Applying this approach to the split-radix FFT gives a particularly interestingalgorithm [link] , [link] , [link] .

Special versions of both the PFA and WFTA can also be developed for real data. Because the operations in the stages ofthe PFA can be commuted, it is possible to move the combination of the transform of the real part of the input and imaginary part tothe last stage. Because the imaginary part of the input is zero, half of the algorithm is simply omitted. This results in the numberof multiplications required for the real transform being exactly half of that required for complex data and the number of additionsbeing about N less than half that required for the complex case because adding a pure real number to a pure imaginary number doesnot require an actual addition. Unfortunately, the indexing and data transfer becomes somewhat more complicated [link] , [link] . A similar approach can be taken with the WFTA [link] , [link] , [link] .

Special algorithms for input data that is mostly zero, for calculating only a few outputs, or where the sampling is not uniform

In some cases, most of the data to be transformed are zero. It is clearly wasteful to do arithmetic on that zero data. Another specialcase is when only a few DFT values are needed. It is likewise wasteful to calculate outputs that are not needed. We use a processcalled “pruning" to remove the unneeded operations.

In other cases, the data are non-uniform sampling of a continuous time signal [link] .

Algorithms for approximate dfts

There are applications where approximations to the DFT are all that is needed. [link] , [link]