# How to do simple extrapolation with Fourier transformation?

I have 1024 sample points, and I would like to do really simple extrapolation using Fourier transformation. First I apply Fast fourier transformation on the data. My first intuition was that I just calculate the inverse fourier transformation on a larger interval. The result of the FFT is a collection of sinusoidal waves, so I expected that it's result is continuous at the end of the original interval.

I calculate the result with this formula:

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{\frac{i 2 \pi n k}{N}}$$

The extrapolation at the end of the interval looks like this:

I would like to avoid this "break" in the result.

The python source code is:

import numpy as np
import matplotlib.pyplot as plt

from scipy.fftpack import fft

# generate samples
data = np.zeros(1024)
for k in range(0, 1024):
data[k] = np.sin(k/20 * np.pi*2)

# apply FFT on samples
waves = fft(data)

# calculate the new data points from the FFT result
res = np.zeros(2048)
for k in range(0, 2048):
val = 0.0
for n in range(0, len(waves)):
# https://dsp.stackexchange.com/a/510/25943
val += waves[n]*np.exp(1.j * 2*np.pi * n * k / len(waves)) / len(waves)
res[k] = val.real

#plot the result
plt.plot(res)
plt.show()

• that "break" must be due to circular wrap-around or something, because there an extra spacing of the peaks and valleys of the sinuosoid. it's not just a simple noisey click to fix. in the pitch-shifting biz, we sometimes call a delay mismatch like that a "glitch". to mend that glitch, you need to slide the whole signal on the right over a bit. dunno exactly how Fourier helps unless it's Short-Time Fourier (the STFT). – robert bristow-johnson Oct 29 '17 at 18:20

The method that you use to extend the periodic sequence $\tilde{x}[n]$, of period $N$, outside of its base period $x[n]$ for $0 \leq n <N$ into the range, say, $0 \leq n <2N$ will simply copy the base period $x[n]$ next to itself. Hence unless the last and first elements $x[N-1]$ and $x[0]$ are same (or very close) there will be an apparent mismatch (discontinuity), that you interpret as a glitch, at the boundary.
The base period $x[n]$ and its $N$-point DFT sequence $X[k]$ are periodic by $N$ which means that $x[n+N] = x[n]$ and when extrapolated you should get the exact result. The inverse DFT that you implement is:
$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2 \pi}{N} k n}$$
When evaluated for some $n = n_0 + N$ for the extrapolated samples $x[n_0 + N]$ where $n_0$ is inside the base period $0 \leq n < N$ you will have
$$x[n_0 + N] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2 \pi}{N} k (n_0 + N)} = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2 \pi}{N} kn_0} e^{j \frac{2 \pi}{N} N} = x[n_0]$$