1 | NO CONTENT: new file 100644, binary diff hidden |
|
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 |
|
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 |
|
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 |
|
NO CONTENT: new file 100644, binary diff hidden |
@@ -1,14 +1,52 | |||||
1 | # compute the two scaled butterfly equations |
|
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 | class ButterflyProcessor(object): |
|
16 | class ButterflyProcessor(object): | |
4 | """docstring for ClassName""" |
|
17 | """docstring for ClassName""" | |
5 |
def __init__(self, |
|
18 | def __init__(self, scale): | |
6 | super(ButterflyProcessor, self).__init__() |
|
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): |
|
30 | def butterfly_not_scaled(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S): | |
10 |
|
|
31 | out1_re = ( Are + Bre ) | |
11 |
|
|
32 | out1_im = ( Aim + Bim ) | |
12 |
|
|
33 | tmp_re = ( Are - Bre ) | |
13 |
|
|
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) |
|
3 | N = 8 | |
4 | res = efficientComplexMultiplier.multiply(70, 50, 121, 160, 82) |
|
4 | scale = 0 | |
5 | print res |
|
5 | fft8DecimationInFrequency = FFT8DecimationInFrequency(N, scale) | |
6 | print res[0]/128 |
|
6 | x = range(8) | |
7 | print res[1]/128 No newline at end of file |
|
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