|
|
from butterfly_processor import ButterflyProcessor
|
|
|
from twiddle_factors import TwiddleFactors
|
|
|
from math import cos, sin, pi, log
|
|
|
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):
|
|
|
# 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]
|
|
|
# arrange sequence
|
|
|
self.indexTransformDecimationInFrequency.reverse_order(fft_output)
|
|
|
return fft_output
|
|
|
|
|
|
def dft(self, x):
|
|
|
N = len(x)
|
|
|
fft_output = x[:]
|
|
|
for k in range(N):
|
|
|
val = 0
|
|
|
for n in range(N):
|
|
|
teta = - 2 * pi * n * k / self.N
|
|
|
val = val + x[n] * ( cos(teta) + 1j * sin(teta) )
|
|
|
fft_output[k] = val
|
|
|
return fft_output
|
|
|
|
