Contents Previous Next Subchapters

Two Dimensional Fourier Transform
Syntax fft2d(z)
See Also ifft2d , fft

Description
Returns the complex two-dimensional centered Fourier transform of z, where z is an integer, real, double-precision or complex matrix with an even number of rows and columns. If M is the number of rows in z and N is the number of columns in z, the (m,n)-th element of the return value is equal to

  M      N
-----  -----          {         __ [ (i - M/2 - 1) (m - M/2 - 1) / M ] }
>      >      z    exp{ -2 pi \/-1 [              +                  ] }
-----  -----   i,j    {            [ (j - N/2 - 1) (n - N/2 - 1) / N ] }
i = 1  j = 1

If the only prime factors of M and N are 2, 3, 5, and 7, the transform is done in order (M)(N)[log(N) + log(M)] operations; otherwise the transform is done in order (M)(N)(N + M) operations.

Example
In the following example M is 4, N is 2, and the (4,1)-th and (4,2)-th elements of z are one (the rest of the elements of z are zero). The (m,n)-th element of the transform is therefore equal to
            __                                            __ 
exp{-2 pi \/-1 [(m - 3) / 4 - (n - 2) / 2]} + exp[-2 pi \/-1 (m - 3) / 4]

If you enter
     z = [{0, 0, 0, 1}, {0, 0, 0, 1}]
     fft2d(z)
O-Matrix replies
     {
     [ (0,0) , (-2,0) ]
     [ (0,0) , (0,2) ]
     [ (0,0) , (2,0) ]
     [ (0,0) , (0,-2) ]
     }
Due to numerical limitations, some of the zeros may be output as numbers that are nearly 0.