Guides/Fourier Transform

While the Fast Fourier Transform is readily available, powerful, and fast, the Fourier Transform itself merits some treatment. (See also John Randall's Fourier Transform and Polynomial Multiplication page.)

The Fourier Transform is a mechanism for converting "sequence domain data" (for example, sounds represented by a sample of some voltage representing speaker position with each sample taken at a uniform time interval) to the "frequency domain" (where, for example, time is not directly represented -- instead, for each frequency of interest we have a measure of the energy available at that frequency).

Fundamentally, the fourier transform is an inner product of some sequence data with a matrix representing the corresponding fundamental frequencies associated with the samples.

In other words:

   basis=: %: %~ 0j2p1&% ^@* */~@i.
   ft=: +/ .* basis@#

The inverse tranform may, of course, be expressed as

   ift=: +/ .* %.@basis@#

However, since the inverse basis is the conjugate transpose of the original basis it may also be expressed as

   ift=: +/ .* +@|:@basis@#

But, also, since this matrix is symmetric, this can be simplified as

   ift=: +/ .* +@basis@#

Some insight can be gained by examining both this transform and the basis.

That said, results might not always be intuitive. For example:

   data=: 1p_0.1 * 2 o. 0.2p1 * i.10
   <.&.(1e12&*)@(1e_14&+) ft data
0 1.41012 0 0 0 0 0 0 0 1.41012

Caution, if you wish to use 'plot' to inspect fourier transform data: as of j6.01, J's plot mechanism uses a different algorithm for data with complex data type than for data with real data type. Remember that you can use +. as a monad to separate real and imaginary components of a complex number. For example, contrast:

   require 'plot'
   plot basis 8
   plot (+ i.@#) 1|:+. basis 8

Finally, note that the basis matrix may be calculated using different operations, which might perhaps result in faster computations on some machines. For example

   basis=: (| */~@i.) { %: %~ 0j2p1&% ^@* i.
   basis=: (| */~@i.) { %: %~ i. r.@o.@+:@% ]