21.4.4  Discrete Fourier Transform and Fast Fourier Transform

For any integer N, 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 nth root of unity ω_N. For sequences with complex coefficients, we take ω_N=e^2iπ/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 is bijective with inverse

The Fast Fourier Transform (FFT) is an efficient way to compute the discrete Fourier transform; faster than computing each term individually. Xcas implements the FFT algorithm to compute the DFT when the period of the sequence is a power of 2.

The fft command computes the discrete Fourier transform.

• fft takes x, a list or sequence regarded as one period of a periodic sequence.
• fft(x) returns F_N(x), the discrete Fourier transform of x.

  If x has length which is a power of 2, then F_N(x) is computed with the Fast Fourier Transform.

The ifft command computes the inverse discrete Fourier transform.

• ifft takes x, a list or sequence regarded as one period of a periodic sequence.
• ifft(x) returns F_N⁻¹(x), the inverse discrete Fourier transform of x.

  If x has length which is a power of 2, then F_N⁻¹(x) is computed with the Fast Fourier Transform.

Examples

Applications

Value of a polynomial.

Define a polynomial P(x)=∑_j=0^N−1c_jx^j by the vector of its coefficients c:=[c₀,c₁,…,c_N−1], where zeroes may be added so that N is a power of 2 (so the Fast Fourier Transform can be used).

Let us compute the values of P(x) at x=a_k=ω_N^−k=e^−2ikπ/N, k=0,…,N−1. This is just the DFT of c since

For example, let P(x+x²) and x=1,i,−1,−i. Here the coefficients of P are [0,1,1,0], N=4 and ω=e^2iπ/4=i.

Hence P(1)=2, P(−i)=P(ω⁻¹)=−1−i, P(−1)=P(ω⁻²)=0, P(i)=P(ω⁻³)=−1+i.

Let us now compute the values of P(x) at x=b_k=ω_N^k=e^2ikπ/N for k=0,…,N−1. This is the inverse DFT of c since

Use this method to find the values of P(x+x²) at x=1,i,−1,−i. Again, the coefficients of P are [0,1,1,0], N=4 and ω=e^2iπ/4=i.

Hence P(1)=2, P(i)=P(ω¹)=−1+i, P(−1)=P(ω²)=0, P(−i)=P(ω³)=−1−i. You find of course the same values as above.

Trigonometric interpolation.

Let f be periodic function of period 2π and let f_k=f(2kπ/N) for k=0,…,N−1. Find a trigonometric polynomial p that interpolates f at x_k=2kπ/N, that is find p_j for j=0,…,N−1 such that

Replacing x_k by its value in p(x) we get:

In other words, (f_k) is the inverse DFT of (p_k), hence

If the function f is real then p_−k=p_k, hence

For an example, see Section 17.1.4.

Fourier series.

Let f be a periodic function of period 2π and let y_k=f(x_k) where x_k=2kπ/N for k=0,…,N−1. Suppose that the Fourier series of f converges to f (this will be the case if for example f is continuous). If N is large, a good approximation of f will be given by:

Hence we want a numeric approximation of

The numeric value of the integral ∫₀^2πf(t) e^−int dt can be computed by the trapezoidal rule (note that the Romberg algorithm would not work here because the Euler-Maclaurin development has its coefficients equal to zero, since the integrated function is periodic, hence all its derivatives have the same value at 0 and at 2π). If c_n is the numeric value of c_n obtained by the trapezoidal rule, then

Indeed, since x_k=2kπ/N and f(x_k)=y_k:

Hence [c₀,…,c_N/2−1,c_N/2+1,…,c_N−1]= 1/NF_N([y₀,y₁,…,y_(N−1)]), since

• if n≥0, then c_n=y_n.
• if n<0, then c_n=y_n+N.
• ω_N=e^2iπ/N, hence ω_Nⁿ=ω_N^n+N.

Several properties are listed below.

• The coefficients of the trigonometric polynomial that interpolates f at x=2kπ/N are

  pn=cn,    −

  N 2

  ≤ n<

  N 2

  .

• If f is a trigonometric polynomial of degree m≤ N/2, then

  f(t)=

  m−1 ∑ k=−m

  ck e2ikπ t.

  The trigonometric polynomial that interpolates f is f itself, the numeric approximation of the coefficients are in fact exact (c_n=c_n).
• More generally, you can compute c_n−c_n.

  Suppose that f is equal to its Fourier series, i.e. that:

  f(t)=

  +∞ ∑ m=−∞

  cm e2iπ mt,

  +∞ ∑ m=−∞

  |cm|<∞.

  Then:

  f(xk)=f

  ⎛ ⎜ ⎜ ⎝

  2kπ N

  ⎞ ⎟ ⎟ ⎠

  =yk=

  +∞ ∑ m=−∞

  cmωNkm,    cn=

  1 N

  N−1 ∑ k=0

  ykωN−kn.

  Replace y_k by its value in c_n:

  cn=

  1 N

  N−1 ∑ k=0

  +∞ ∑ m=−∞

  cmωNkmωN−kn.

  If m≠ n (mod N ), ω_N^m−n is an nth root of unity different from 1, hence:

  ωN(m−n)N=1,

  N−1 ∑ k=0

  ωN(m−n)k=0.

  Therefore, if m−n is a multiple of N (m=n+l· N) then ∑_k=0^N−1ω_N^k(m−n)=N, otherwise ∑_k=0^N−1ω_N^k(m−n)=0. By reversing the two sums, you get

  cn = 1 N +∞ ∑ m=−∞ cm N−1 ∑ k=0 ωNk(m−n)                      = +∞ ∑ l=−∞ c(n+l· N)                      =⋯ + cn−2 N+cn−N+cn+cn+N+cn+2N+⋯

  Conclusion: if |n|<N/2, then c_n−c_n is a sum of c_j with large indices (at least N/2 in absolute value), hence is small (depending on the rate of convergence of the Fourier series).

For example, input:

Dividing by N=8, you get

Hence b_k=0 and a_k=c_−k+c_k equals 1 for k=1,2 and 0 otherwise.

Convolution Product.

If P(x)=∑_j=0ⁿ⁻¹a_jx^j and Q(x)=∑_j=0^m−1b_jx^j are given by the vectors of their coefficients a=[a₀,a₁,…,a_n−1] and b=[b₀,b₁,…,b_m−1], you can compute the product of these two polynomials using the DFT. The product of polynomials is the convolution product of the periodic sequence of their coefficients if the period is greater or equal to (n+m). Therefore we complete a (resp. b) with m+p (resp. n+p) zeros, where p is chosen such that N=n+m+p is a power of 2. If a=[a₀,a₁,…,a_n−1,0,…,0] and b=[b₀,b₁,…,b_m−1,0,…,0], then:

If you know F_N(a) and F_N(b), then a∗ b=F_N⁻¹(F_N(a)⊙ F_N(b)), where ⊙ denotes the Hadamard (elementwise) product.

Noise removal with spectral subtraction.

We use Xcas to implement a simple algorithm for static noise removal based on the spectral subtraction method¹.

The efficiency of the spectral subtraction method largely depends on a good noise spectrum estimate. Below is the code for a function noiseprof that takes data and wlen as its arguments. These are, respectively, a signal chunk containing only noise and the window length for signal segmentation (the best values are powers of two, such as 256, 512 or 1024). The function returns an estimate of the noise power spectrum obtained by averaging the power spectra of a (not too large) number of distinct chunks of data of length wlen. The Hamming window is applied prior to FFT.

The main function is noisered, which takes three arguments: the input signal data, the noise power spectrum np and the “spectral floor” parameter beta (β, the minimum power level). The function performs subtraction of the noise spectrum in chunks of length wlen (the length of list np) using the overlap-and-add approach with the Hamming window function.

You can test the algorithm on a small speech sample with an audible amount of static noise (you can download the audio from here).

Speech starts after approximately 0.2 seconds of pure noise. You can use that part of the clip for obtaining an estimate of the noise power spectrum with wlen set to 256.

Now call the noisered function with β=0.02:

Observe that the noise level is significantly lower than in the original clip. You could use the playsnd command to compare the input with the output by hearing, which would reveal that the noise is still present but in a lesser degree. The parameter β controls how much noise is left in.