View source for DMelt:DSP/1 Fast Fourier Transforms

{{sidebar box|[[DMelt:Start|Table of contents]]}}


= Fast Fourier transforms =
A [[Fast Fourier transform]] (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. There are several packages dealing with the FFT  problem.
We will discuss the fastest one, which uses many threads and the multicore computer architecture. It is based on the ParallelColt 
as implemented by Piotr Wendykier.

In this example we will use  <javadoc sc>cern.colt.matrix.tdcomplex.DComplexFactory2D|DComplexFactory2D</javadoc> factory to create a random
dense matrix (<javadoc sc>cern.colt.matrix.tdcomplex.impl.DenseDComplexMatrix2D|DenseDComplexMatrix2D</javadoc>) and perform FCC.

<jcode lang="python">
dmelt 69026625.py
</jcode>

= Discrete Cosine Transform (DCT) =
 
A [[Discrete cosine transform]] discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequencies. This example is based on the real <javadoc sc>cern.colt.matrix.impl.DenseDoubleMatrix2D | DenseDoubleMatrix2D</javadoc> matrix.

<jcode lang="python">
dmelt 40272075.py
</jcode>

You can also use 3D matrix methods, see <javadoc sc>cern.colt.matrix.impl.DenseDoubleMatrix3D | DenseDoubleMatrix3D</javadoc>

= Discrete Fourier transform (DFT)  =
<wp>Discrete_Fourier_transform</wp> converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform.
This is 1D DFT transform of a complex matrix 1000x1000 using several processing cores:

<jcode lang="python">
dmelt 69026625.py
</jcode>

[[Category:Digital signal processing]]
[[Category:Discrete transforms]]