4.2 Transforms of Real Sequences

It is worth discussing the difference between DComplexFFTServer and DoubleFFTServer. Say you want to transform a real sequence of N points V(j), j=0, ..., N-1. Note that the transform of a real sequence is a complex conjugate-even sequence, that is, a sequence where C(j) = conj(C(-j)) = conj(C(N-j)). How can you calculate the transform? In general, you have two choices:

Convert the real sequence to a complex sequence with imaginary parts set to 0 and transform that;
Take advantage of the fact that the imaginary parts of the sequence are 0 and transform the N-point real sequence as an N/2-point complex sequence.

The DoubleFFTServer uses the second approach. Because the result is a complex conjugate-even sequence, the DoubleFFTServer returns only the lower half of the sequence, which saves considerable time. Here is an example illustrating the two approaches:

#include <rw/dfft.h>
#include <rw/cfft.h>
#include <iostream.h>

const unsigned npts = 12;

main()
{
  // Real sequence to be transformed (a linear ramp):
  RWMathVec<double> V(npts, 0.0, 1.0);

  // Print it out:
  cout << "Original (real) sequence:\n" << V << "\n";

  /***************** Approach 1 **********************/
  RWMathVec<DComplex> Vcomplex(V);         // Convert to complex

  // Construct a complex FFT server:
  DComplexFFTServer dcffts;

  // Vtrans1 will be 12 points long
  // and complex-conjugate even:
  RWMathVec<DComplex> Vtrans1 = dcffts.fourier(Vcomplex);

  /************ An alternative (approach 2) ***********/
  DoubleFFTServer dffts;          // Use a double FFT server

  // Vtrans2 will be 7 points long: the
  // lower half of Vtrans1:
  RWMathVec<DComplex> Vtrans2 = dffts.fourier(V);

  cout << "Transform using approach 1:\n" << Vtrans1;
  cout << endl;
  cout << "Transform using approach 2:\n" << Vtrans2;
  cout << endl;
}

Program output (exact results depend on machine precision):

Original (real) sequence:
[
0 1 2 3 4
5 6 7 8 9
10 11
]
Transform using Approach 1:
[
(66, 0) (-6, 22.3923) (-6, 10.3923) (-6, 6) (-6, 3.4641)
(-6, 1.6077) (-6, 0) (-6, -1.6077) (-6, -3.4641) (-6, -6)
(-6, -10.3923) (-6, -22.3923)
]
Transform using Approach 2:
[
(66, 0) (-6, 22.3923) (-6, 10.3923) (-6, 6) (-6, 3.4641)
(-6, 1.6077) (-6, 0)
]

A close inspection shows that the full transformed sequence using the first approach is complex-conjugate even. The second approach, using the DoubleFFTServer, returns only the lower half of that sequence. The global function expandConjugateEven() can be used to expand it into the full N-point conjugate-even sequence. See the Global Function Reference for more information.