An analysis problem, which is equivalent to the DFT:
Given a signal, how to find the amplitude and phase offset of its frequency
components?
A synthesis problem, which is equivalent to the inverse DFT:
Given a set of frequency components and their amplitudes, how can we construct a
signal?
DFT and Inverse DFT in code
The analyze() computes something very close to the DFT, with one difference: The
conventional definition of DFT does not divide by N (highlighted line below):
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| def analyze(ys):
N = len(ys)
M = synthesis_matrix(N)
amps = M.conj().transpose().dot(ys) / N
return amps
def dft(ys): # return same result as np.fft.fft()
N = len(ys)
M = synthesis_matrix(N)
amps = M.conj().transpose().dot(ys)
return amps
def idft(amps): # inverse DFT
N = len(amps)
M = synthesis_matrix(N)
ys = M.dot(amps) / N
return ys # ys: value of the signal at each time step
def synthesis_matrix(N):
ts = np.arange(N) / N # ts: the sequence of times where the signal should be evaluated
fs = np.arange(N) # fs: the list of frequencies
args = np.outer(ts, fs) # args: outer product of ts and fs
M = np.exp(1j * PI2 * args) # PI2 = np.pi * 2
return M
|