Contents Previous Next Subchapters

Forward Fourier Transform of a Double-Precision Vector
Syntax dbldft(w)
See Also dft , idbldft

Description
Returns the column by column discrete transform of w, where w is a double-precision matrix with an even number of rows. The numbers 2, 3, 5, and 7 must be the only prime factors of the number of rows in w. This routine is faster and uses less memory than the dft function but it only applies to the case where the vector to be transformed has zero imaginary part.

If N is half the number of rows in w, define
     z(kj) = sum_{i=1}^{2 N}
          w(ij) exp[ -2 pi sqrt{-1} (i - 1) (k - 1) / (2 N) ]
Thus z is the column by column discrete Fourier transform of w.

For each j, z(1, j) and z(N + 1, j) have zero imaginary part because w has zero imaginary part. Furthermore for k > N + 1, z(kj) is equal to the complex conjugate of z(2  N + 2 - kj). Thus we only need return that value of z(kj) for k between 1 and N + 1 to specify the entire transform of w.

The return value of the dbldft function has the same type and dimension as w. If c is the return value, for all k between 2 and N, and all j between 1 and the column dimension of w
     c(1, j)       =     the real part of z(1, j)
     c(2, j)       =     the real part of z(N + 1, j)
     c(2 k - 1, j) =     the real part of z(kj)
     c(2 kj)     = the imaginary part of z(kj)

Example
If you enter
     w = double({0, 1, 0, 0})
only the term with i = 2 in the summation defining dbldft(w) is nonzero, and element k of the Fourier transform of w is given by
     z(k) = exp[- pi sqrt{-1} (k - 1) / 2]
which is given by the following table
     z(1)  = 1
     z(2)  = -sqrt{-1}
     z(3)  = -1 
     z(4)  = sqrt{-1}
If you continue this example by entering
     dbldft(w)
O-Matrix will respond
     {
     1
     -1
     0
     -1
     }
the first element of the vector above is equal to the real part of z(1). The second element is equal to the real part of z(3) (note that for this case N + 1 = 3). The third element is equal to the real part of z(2). The fourth element is equal to the imaginary part of z(2).