next up previous contents index
suivant: The properties of the monter: Fourier transformation précédent: fourier_cn   Table des matières   Index

Discrete Fourier Transform

Let N be an integer. The Discrete Fourier Transform (DFT) is a transformation FN defined on the set of periodic sequences of period N, it depends on a choice of a primitive N-th root of unity $ \omega_{N}^{}$. If the DFT is defined on sequences with complex coefficients, we take:

$\displaystyle \omega_{N}^{}$ = e$\scriptstyle {\frac{{2 i \pi}}{{N}}}$

If x is a periodic sequence of period N, defined by the vector x = [x0, x1,...xN-1] then FN(x) = y is a periodic sequence of period N, defined by:

(FN,$\scriptstyle \omega_{N}$(x))k = yk = $\displaystyle \sum_{{j=0}}^{{N-1}}$xj$\displaystyle \omega_{N}^{{-k\cdot j}}$, k = 0..N - 1

where $ \omega_{N}^{}$ is a primitive N-th root of unity. The discrete Fourier transform may be computed faster than by computing each yk individually, by the Fast Fourier Transform (FFT). Xcas implements the FFT algorithm to compute the discrete Fourier transform only if N is a power of 2.


giac documentation written by Renée De Graeve and Bernard Parisse