Fast Fourier Transform FFT
Trigonometric Interpolation

Filter experiment : Directly to the input form

Interpolation: Directly to the input form

• The FFT is a special (equidistant) case of trigonometric interpolation. In the general case of arbitrarily distributed abscissae the job becomes one of a linear systems solve with a Vandermonde matrix, although meanwhile there exist also algorithms trying to extend the special efficient technique here to this case. In the equidistant case we are considering here the effort can be broken down to O(n log(n)) with n+1 the number of interpolation points. Only for this reason its application in signal analysis, where n may be as large as 10⁵, becomes feasible. We are using here a software which requires n+1 to have a prime decomposition with the factors 2,3 and 5 solely. The algorithm makes heavy use of the relation
  cos(φ)+sqrt(-1)*sin(φ)= exp(sqrt(-1)*φ)
  expressing the sin(.) and cos(.) terms with powers of the latter. The trigonometric polynomial
  p(x) = a₀ + ∑_i=1,...,m { a_i cos(i*x) + b_isin(i*x) } {+a_m+1cos((m+1)*x)}
  is transformed to a complex one in the variable z=exp(sqrt(-1)*x) by this.
• This simplifies the computation of the interpolating polynomial considerably. Finally, the complex form is retranslated into the real one.
• The type of the polynomial depends on whether n is even or odd, as n+1=2m+1 or n+1=2m+2. The last cos term appears only in the latter case.
• This type of interpolation has a remarkable property: it neither stengthens nor damps the influence of noise (the matrices describing the input/output relation are unitary).
• Here we have prepared a numerical experiment: you specify a (short) trigonometric sum (for practicability we have restricted the number of terms to 7 (m above, named M in the input form)). Then we generate a number of n+1 (possibly much larger than 2M+1 resp.2M+2) of evaluations points (abscissae will be chosen as x_i=2*i*π/(n+1), i=0,..,n). Interpolating the true values should produce back the original sum, hence a lot of zero coefficients if n/2 > > m. The values y_i become perturbed by randomly chosen noise and the perturbed data are interpolated, now by a trigonometric sum with n+1 coefficients. All coefficients with index larger than M now slightly deviate from zero. This simulates noise on a transmission line. The original signal now can be reconstructed using a ''noise filter''. Here we use the simplest one: all coefficients below some ''drop level'' are set to zero. If you have chosen this ''drop level'' correctly (i.e. corresponding to the level of generated noise) you obtain your original polynomial back, slightly shifted in phase and amplitude.
• Alternatively you have the possibility to specify your own data set (x_i,y_i), i=0,...,n. In this case you will get the interpolating trigonometric sum, which will be shown as a plot and as a formula (text).

Input for the filter experiment

• The length m of the original trigonometric sum.
• The number n+1 of evaluation points, n+1=(2^i)*(3^j)*(5^k) for some integer i,j,k!
• The coefficients of the original trigonometric sum, as a₀,a₁,b₁,a₂,b₂,...a_m,b_m.
• A level for the error generation (in percent, for the largest original value) and
• the "droplevel", also in percent.

Output for the filter experiment

• A printed list of original, perturbed and filtered coefficients.
• A plot showing:
  1. The original trigonometric sum.
  2. The perturbed data and their interpolation.
  3. The trigonometric sum after filtering.

Questions ?!

• How must be drop level be chosen to get the original function back qualitatively at least?

To the filter experiment

Input for direct trigonometric interpolation

• The number n+1 of your data points.
• The value of x₀ and the stepsize dx. Attention: The interval corresponding to [0,2*π] is [x₀,x₀+(n+1)*dx]!
• Your data y₀,...,y_n.

Output

• A plot with your data and the interpolating trigonometric polynomial.
• the formula of the interpolating trigonometric polynomial.

To the direct trigonometric interpolation