Discrete Fourier Transform

Let N be an integer. The Discrete Fourier Transform (DFT) is a transformation F_N 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:

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

If x is a periodic sequence of period N, defined by the vector x = [x₀, x₁,...x_N-1] then F_N(x) = y is a periodic sequence of period N, defined by:

(F_{N,$\omega_{N}$}(x))_k = y_k = $$\sum_{{j=0}}^{{N-1}}$$x_j$$\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 y_k 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.