|
1 | NO CONTENT: new file 100644, binary diff hidden |
@@ -0,0 +1,64 | |||
|
1 | from butterfly_processor import ButterflyProcessor | |
|
2 | from twiddle_factors import TwiddleFactors | |
|
3 | from math import cos, sin, pi | |
|
4 | from index_transform_decimation_in_frequency import IndexTransformDecimationInFrequency | |
|
5 | ||
|
6 | class FFT8DecimationInFrequency(object): | |
|
7 | """docstring for FFT8DecimationInFrequency""" | |
|
8 | def __init__(self, N, scale): | |
|
9 | super(FFT8DecimationInFrequency, self).__init__() | |
|
10 | self.N = N | |
|
11 | self.butterflyProcessor = ButterflyProcessor(scale) | |
|
12 | twiddleFactors = TwiddleFactors(N) | |
|
13 | self.w = twiddleFactors.build_twiddle_factors() | |
|
14 | self.indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(N) | |
|
15 | ||
|
16 | def fft(self, x): | |
|
17 | # stage 1 | |
|
18 | fft_output = range(8) | |
|
19 | for i in range(4): | |
|
20 | res = self.butterflyProcessor.butterfly( # (Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S) | |
|
21 | x[i], 0, | |
|
22 | x[i+4], 0, | |
|
23 | self.w[i].real, | |
|
24 | self.w[i].real + self.w[i].imag, | |
|
25 | self.w[i].real - self.w[i].imag, | |
|
26 | ) | |
|
27 | fft_output[i] = res[0] | |
|
28 | fft_output[i+4] = res[1] | |
|
29 | # stage 2 | |
|
30 | for twiddle in range(2): | |
|
31 | for group in range(2): | |
|
32 | res = self.butterflyProcessor.butterfly( | |
|
33 | fft_output[twiddle+group*4].real, fft_output[twiddle+group*4].imag, | |
|
34 | fft_output[twiddle+group*4+2].real, fft_output[twiddle+group*4+2].imag, | |
|
35 | self.w[twiddle*2].real, | |
|
36 | self.w[twiddle*2].real + self.w[twiddle*2].imag, | |
|
37 | self.w[twiddle*2].real - self.w[twiddle*2].imag | |
|
38 | ) | |
|
39 | fft_output[twiddle+group*4] = res[0] | |
|
40 | fft_output[twiddle+group*4+2] = res[1] | |
|
41 | # stage 3 | |
|
42 | for i in range(4): | |
|
43 | res = self.butterflyProcessor.butterfly( | |
|
44 | fft_output[i*2].real, fft_output[i*2].imag, | |
|
45 | fft_output[i*2+1].real, fft_output[i*2+1].imag, | |
|
46 | 1, | |
|
47 | 1, | |
|
48 | 1 | |
|
49 | ) | |
|
50 | fft_output[i*2] = res[0] | |
|
51 | fft_output[i*2+1] = res[1] | |
|
52 | # arrange sequence | |
|
53 | self.indexTransformDecimationInFrequency.reverse_order(fft_output) | |
|
54 | return fft_output | |
|
55 | ||
|
56 | def dft(self, x): | |
|
57 | fft_output = range(8) | |
|
58 | for k in range(8): | |
|
59 | val = 0 | |
|
60 | for n in range(8): | |
|
61 | teta = - 2 * pi * n * k / self.N | |
|
62 | val = val + x[n] * ( cos(teta) + 1j * sin(teta) ) | |
|
63 | fft_output[k] = val | |
|
64 | return fft_output |
|
1 | NO CONTENT: new file 100644, binary diff hidden |
@@ -0,0 +1,35 | |||
|
1 | class IndexTransformDecimationInFrequency(object): | |
|
2 | """docstring for IndexTransformDecimationInFrequency""" | |
|
3 | def __init__(self, N): | |
|
4 | super(IndexTransformDecimationInFrequency, self).__init__() | |
|
5 | self.N = N | |
|
6 | self.new_k = range(self.N) | |
|
7 | self.build_index_vector() | |
|
8 | print 'new_k = ', self.new_k | |
|
9 | ||
|
10 | def reverse_order(self, sequence): | |
|
11 | for i in (range(len(sequence)/2-1)): | |
|
12 | i = i+1 | |
|
13 | a = sequence[ i ]; | |
|
14 | b = sequence[ self.new_k[i] ] | |
|
15 | sequence[ i ] = b | |
|
16 | sequence[ self.new_k[i] ] = a | |
|
17 | ||
|
18 | def build_index_vector(self): | |
|
19 | if self.N == 8: | |
|
20 | for indice in range(self.N): | |
|
21 | b = '{:03b}'.format(indice) | |
|
22 | b = b[::-1] | |
|
23 | self.new_k[indice] = int(b, 2) | |
|
24 | else: | |
|
25 | print'error, value not supported by the index_transform function' | |
|
26 | ||
|
27 | if __name__ == "__main__": | |
|
28 | indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(8) | |
|
29 | x = range(8) | |
|
30 | print 'x ', x | |
|
31 | indexTransformDecimationInFrequency.reverse_order(x) | |
|
32 | print 'x rearranged ', x | |
|
33 | y = x | |
|
34 | indexTransformDecimationInFrequency.reverse_order(y) | |
|
35 | print 'y ', y |
|
1 | NO CONTENT: new file 100644, binary diff hidden |
@@ -0,0 +1,16 | |||
|
1 | # exp( - j 2 pi k / N ) = W^k_N | |
|
2 | ||
|
3 | from math import exp, cos, sin, pi | |
|
4 | ||
|
5 | class TwiddleFactors(object): | |
|
6 | """docstring for TwiddleFactors""" | |
|
7 | def __init__(self, N): | |
|
8 | super (TwiddleFactors, self).__init__() | |
|
9 | self.N = N | |
|
10 | ||
|
11 | def build_twiddle_factors(self): | |
|
12 | w = [] | |
|
13 | for k in range( self.N / 2 ): | |
|
14 | teta = - 2 * pi * k / self.N | |
|
15 | w.append( cos ( teta ) + 1j * sin( teta ) ) | |
|
16 | return w |
|
1 | NO CONTENT: new file 100644, binary diff hidden |
@@ -1,14 +1,52 | |||
|
1 | 1 | # compute the two scaled butterfly equations |
|
2 | # A o--->----o---->--- | |
|
3 | # \ / | |
|
4 | # \ / | |
|
5 | # \ / | |
|
6 | # \/ | |
|
7 | # /\ | |
|
8 | # / \ | |
|
9 | # / \ | |
|
10 | # / \ | |
|
11 | # B o--->----o---->--- | |
|
12 | # (-1) (W) | |
|
13 | ||
|
14 | from efficient_complex_multiplier import EfficientComplexMultiplier | |
|
2 | 15 | |
|
3 | 16 | class ButterflyProcessor(object): |
|
4 | 17 | """docstring for ClassName""" |
|
5 |
def __init__(self, |
|
|
18 | def __init__(self, scale): | |
|
6 | 19 | super(ButterflyProcessor, self).__init__() |
|
7 |
self. |
|
|
20 | self.scale = scale | |
|
21 | self.efficient_complex_multiplier = EfficientComplexMultiplier(0); | |
|
22 | ||
|
23 | def butterfly(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S): | |
|
24 | if self.scale == 1: | |
|
25 | res = self.butterfly_scaled(Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S) | |
|
26 | else: | |
|
27 | res = self.butterfly_not_scaled(Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S) | |
|
28 | return res | |
|
8 | 29 | |
|
9 | def butterfly(self): | |
|
10 |
|
|
|
11 |
|
|
|
12 |
|
|
|
13 |
|
|
|
30 | def butterfly_not_scaled(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S): | |
|
31 | out1_re = ( Are + Bre ) | |
|
32 | out1_im = ( Aim + Bim ) | |
|
33 | tmp_re = ( Are - Bre ) | |
|
34 | tmp_im = ( Aim - Bim ) | |
|
35 | res = self.efficient_complex_multiplier.multiply(tmp_re, tmp_im, C, C_plus_S, C_minus_S) | |
|
36 | out2_re = res[0] | |
|
37 | out2_im = res[1] | |
|
38 | out1 = out1_re + 1j * out1_im | |
|
39 | out2 = out2_re + 1j * out2_im | |
|
40 | return [out1, out2] | |
|
14 | 41 | |
|
42 | def butterfly_scaled(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S): | |
|
43 | out1_re = ( Are + Bre ) / 2 | |
|
44 | out1_im = ( Aim + Bim ) / 2 | |
|
45 | tmp_re = ( Are - Bre ) / 2 | |
|
46 | tmp_im = ( Aim - Bim ) / 2 | |
|
47 | res = self.efficient_complex_multiplier.multiply(tmp_re, tmp_im, C, C_plus_S, C_minus_S) | |
|
48 | out2_re = res[0] | |
|
49 | out2_im = res[1] | |
|
50 | out1 = out1_re + 1j * out1_im | |
|
51 | out2 = out2_re + 1j * out2_im | |
|
52 | return [out1, out2] No newline at end of file |
@@ -1,7 +1,11 | |||
|
1 | from efficient_complex_multiplier import EfficientComplexMultiplier | |
|
1 | from fft_8_decimation_in_frequency import FFT8DecimationInFrequency | |
|
2 | 2 | |
|
3 | efficientComplexMultiplier = EfficientComplexMultiplier(0) | |
|
4 | res = efficientComplexMultiplier.multiply(70, 50, 121, 160, 82) | |
|
5 | print res | |
|
6 | print res[0]/128 | |
|
7 | print res[1]/128 No newline at end of file | |
|
3 | N = 8 | |
|
4 | scale = 0 | |
|
5 | fft8DecimationInFrequency = FFT8DecimationInFrequency(N, scale) | |
|
6 | x = range(8) | |
|
7 | fft_val = fft8DecimationInFrequency.fft(x) | |
|
8 | dft_val = fft8DecimationInFrequency.dft(x) | |
|
9 | print x | |
|
10 | print "fft ", fft_val | |
|
11 | print "dft ", dft_val |
General Comments 0
You need to be logged in to leave comments.
Login now