|
|
from butterfly_processor import ButterflyProcessor
|
|
|
from twiddle_factors import TwiddleFactors
|
|
|
from math import cos, sin, pi
|
|
|
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):
|
|
|
# stage 1
|
|
|
fft_output = range(8)
|
|
|
for i in range(4):
|
|
|
res = self.butterflyProcessor.butterfly( # (Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S)
|
|
|
x[i], 0,
|
|
|
x[i+4], 0,
|
|
|
self.w[i].real,
|
|
|
self.w[i].real + self.w[i].imag,
|
|
|
self.w[i].real - self.w[i].imag,
|
|
|
)
|
|
|
fft_output[i] = res[0]
|
|
|
fft_output[i+4] = res[1]
|
|
|
# stage 2
|
|
|
for twiddle in range(2):
|
|
|
for group in range(2):
|
|
|
res = self.butterflyProcessor.butterfly(
|
|
|
fft_output[twiddle+group*4].real, fft_output[twiddle+group*4].imag,
|
|
|
fft_output[twiddle+group*4+2].real, fft_output[twiddle+group*4+2].imag,
|
|
|
self.w[twiddle*2].real,
|
|
|
self.w[twiddle*2].real + self.w[twiddle*2].imag,
|
|
|
self.w[twiddle*2].real - self.w[twiddle*2].imag
|
|
|
)
|
|
|
fft_output[twiddle+group*4] = res[0]
|
|
|
fft_output[twiddle+group*4+2] = res[1]
|
|
|
# stage 3
|
|
|
for i in range(4):
|
|
|
res = self.butterflyProcessor.butterfly(
|
|
|
fft_output[i*2].real, fft_output[i*2].imag,
|
|
|
fft_output[i*2+1].real, fft_output[i*2+1].imag,
|
|
|
1,
|
|
|
1,
|
|
|
1
|
|
|
)
|
|
|
fft_output[i*2] = res[0]
|
|
|
fft_output[i*2+1] = res[1]
|
|
|
# arrange sequence
|
|
|
self.indexTransformDecimationInFrequency.reverse_order(fft_output)
|
|
|
return fft_output
|
|
|
|
|
|
def dft(self, x):
|
|
|
fft_output = range(8)
|
|
|
for k in range(8):
|
|
|
val = 0
|
|
|
for n in range(8):
|
|
|
teta = - 2 * pi * n * k / self.N
|
|
|
val = val + x[n] * ( cos(teta) + 1j * sin(teta) )
|
|
|
fft_output[k] = val
|
|
|
return fft_output
|
|
|
|
