離散フーリエ変換。

fourier.py

# fourier.py
# This source contains below:
#   * Discrete Fourier Transform (DFT)
#   * Fast Fourier Transform (FFT)
#   * Discrete Co-sine Transform Type-II (DCT2)

import math

def dft(samples):
	n = len(samples)
	f = []
	for j in range(n):
		re = 0
		im = 0
		for i in range(n):
			omega = 2 * i * j * math.pi / n
			re += samples[i] * math.cos(omega)
			im += samples[i] * math.sin(omega)
		f.append([re, im])
	return f

def fft(samples):
	# checking number of samples is 2^n
	# and get value of log2(n)
	n = 1
	power = 0
	while n < len(samples):
		n <<= 1
		power += 1
	if n > len(samples):
		return
	# initializing parameter
	x = []
	w = []
	for i in range(n):
		omega = 2 * i * math.pi / n
		w.append([math.cos(omega), math.sin(omega)])
		k = 0;
		for j in range(power):
			k = (k << 1) + (i & 1)
			i >>= 1
		x.append([samples[k], 0])
	# butterfly operation
	for i in range(power):
		xx = []
		for j in range(n):
			a = j & ~(1 << i)
			b = j | (1 << i)
			t = (j << (power - i - 1)) & (n - 1)
			re = x[a][0] + x[b][0] * w[t][0] - x[b][1] * w[t][1]
			im = x[a][1] + x[b][0] * w[t][1] + x[b][1] * w[t][0]
			xx.append([re, im])
		x = xx;
	return x

def dct2(samples):
	n = len(samples)
	f = []
	for j in range(n):
		c = 0
		for i in range(n):
			omega = (i + 0.5) * j * math.pi / n
			c += samples[i] * math.cos(omega)
		f.append(c)
	return f