fft_8_decimation_in_frequency.py
51 lines
| 1.8 KiB
| text/x-python
|
PythonLexer
|
r2 | from butterfly_processor import ButterflyProcessor | ||
from twiddle_factors import TwiddleFactors | ||||
|
r3 | from math import cos, sin, pi, log | ||
|
r2 | from index_transform_decimation_in_frequency import IndexTransformDecimationInFrequency | ||
class FFT8DecimationInFrequency(object): | ||||
"""docstring for FFT8DecimationInFrequency""" | ||||
def __init__(self, N, scale): | ||||
super(FFT8DecimationInFrequency, self).__init__() | ||||
self.N = N | ||||
self.butterflyProcessor = ButterflyProcessor(scale) | ||||
twiddleFactors = TwiddleFactors(N) | ||||
self.w = twiddleFactors.build_twiddle_factors() | ||||
self.indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(N) | ||||
def fft(self, x): | ||||
|
r3 | # all stages | ||
fft_output = x[:] | ||||
nb_stages = int( log(len(x), 2) ) | ||||
print 'size of input sequence = ', len(x), ', nb stages = ', nb_stages | ||||
for k in range(nb_stages): | ||||
stage = k + 1 | ||||
step = 2**(nb_stages - stage) | ||||
nb_groups = 2**(stage-1) | ||||
for twiddle in range(step): | ||||
for group in range(nb_groups): | ||||
res = self.butterflyProcessor.butterfly( | ||||
fft_output[twiddle+group*step*2].real, | ||||
fft_output[twiddle+group*step*2].imag, | ||||
fft_output[twiddle+group*step*2+step].real, | ||||
fft_output[twiddle+group*step*2+step].imag, | ||||
self.w[twiddle*nb_groups].real, | ||||
self.w[twiddle*nb_groups].real + self.w[twiddle*nb_groups].imag, | ||||
self.w[twiddle*nb_groups].real - self.w[twiddle*nb_groups].imag | ||||
) | ||||
fft_output[twiddle+group*step*2] = res[0] | ||||
fft_output[twiddle+group*step*2+step] = res[1] | ||||
|
r2 | # arrange sequence | ||
self.indexTransformDecimationInFrequency.reverse_order(fft_output) | ||||
return fft_output | ||||
def dft(self, x): | ||||
|
r3 | N = len(x) | ||
fft_output = x[:] | ||||
for k in range(N): | ||||
|
r2 | val = 0 | ||
|
r3 | for n in range(N): | ||
|
r2 | teta = - 2 * pi * n * k / self.N | ||
val = val + x[n] * ( cos(teta) + 1j * sin(teta) ) | ||||
fft_output[k] = val | ||||
return fft_output | ||||