Restrictions1
12.1 Algorithms for Real Data
Many applications involve processing real data. It is inefficient to
simply use a complex FFT on real data because arithmetic would
be performed on the zero imaginary parts of the input, and, be-
cause of symmetries, output values would be calculated that are
redundant. There are several approaches to developing special al-
gorithms or to modifying complex algorithms for real data.
There are two methods which use a complex FFT in a special way
to increase efficiency [39], [359]. The first method uses a length-N
complex FFT to compute two length-N real FFTs by putting the
two real data sequences into the real and the imaginary parts of
the input to a complex FFT. Because transforms of real data have
even real parts and odd imaginary parts, it is possible to separate
the transforms of the two inputs with 2N-4 extra additions. This
method requires, however, that two inputs be available at the same
time.
1This content is available online at <http://cnx.org/content/m16338/1.7/>.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
199
CHAPTER 12. ALGORITHMS FOR
200
DATA WITH RESTRICTIONS
The second method [359] uses the fact that the last stage of a
decimation-in-time radix-2 FFT combines two independent trans-
forms of length N/2 to compute a length-N transform.
If the
data are real, the two half length transforms are calculated by the
method described above and the last stage is carried out to calculate
the total length-N FFT of the real data. It should be noted that the
half-length FFT does not have to be calculated by a radix-2 FFT.
In fact, it should be calculated by the most efficient complex-data
algorithm possible, such as the SRFFT or the PFA. The separa-
tion of the two half-length transforms and the computation of the
last stage requires N − 6 real multiplications and (5/2) N − 6 real
additions [359].
It is possible to derive more efficient real-data algorithms directly
rather than using a complex FFT. The basic idea is from Bergland
[21], [22] and Sande [325] which, at each stage, uses the symme-
tries of a constant radix Cooley-Tukey FFT to minimize arithmetic
and storage. In the usual derivation [275] of the radix-2 FFT, the
length-N transform is written as the combination of the 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 is real, the out-
put will have Hermitian symmetry. Hence the output of each stage
can be arranged so that the results of that stage stores the complex
DFT with the real part located where half of the DFT would have
gone, and the imaginary part located where the conjugate would
have gone. This removes most of the redundant calculations and
storage but slightly complicates the addressing. The resulting but-
terfly structure for this algorithm [359] resembles that for the fast
Hartley transform [353]. The complete algorithm has one half the
number of multiplications and N-2 fewer than half the additions of
the basic complex FFT. Applying this approach to the split-radix
FFT gives a particularly interesting algorithm [103], [359], [111].
Special versions of both the PFA and WFTA can also be developed
for real data. Because the operations in the stages of the PFA can be
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
201
commuted, it is possible to move the combination of the transform
of the real part of the input and imaginary part to the last stage. Be-
cause the imaginary part of the input is zero, half of the algorithm
is simply omitted. This results in the number of multiplications
required for the real transform being exactly half of that required
for complex data and the number of additions being about N less
than half that required for the complex case because adding a pure
real number to a pure imaginary number does not require an actual
addition. Unfortunately, the indexing and data transfer becomes
somewhat more complicated [179], [359]. A similar approach can
be taken with the WFTA [179], [359], [284].
12.2 Special Algorithms for input Data that
is mostly Zero, for Calculating only a few
Outputs, or where the Sampling is not Uni-
form
In some cases, most of the data to be transformed are zero. It is
clearly wasteful to do arithmetic on that zero data. Another special
case is when only a few DFT values are needed. It is likewise
wasteful to calculate outputs that are not needed. We use a process
called “pruning" to remove the unneeded operations.
In other cases, the data are non-uniform sampling of a continuous
time signal [13].
12.3 Algorithms for Approximate DFTs
There are applications where approximations to the DFT are all
that is needed.[161], [163]
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 12. ALGORITHMS FOR
202
DATA WITH RESTRICTIONS
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>