diff --git a/butterfly_processor.py b/butterfly_processor.py
--- a/butterfly_processor.py
+++ b/butterfly_processor.py
@@ -1,14 +1,52 @@
 # compute the two scaled butterfly equations
+# A o--->----o---->---
+#    \      /
+#     \    /
+#      \  /
+#       \/
+#       /\
+#      /  \
+#     /    \
+#    /      \
+# B o--->----o---->---
+#      (-1)      (W)
+
+from efficient_complex_multiplier import EfficientComplexMultiplier
 
 class ButterflyProcessor(object):
 	"""docstring for ClassName"""
-	def __init__(self, arg):
+	def __init__(self, scale):
 		super(ButterflyProcessor, self).__init__()
-		self.arg = arg
+		self.scale = scale
+		self.efficient_complex_multiplier = EfficientComplexMultiplier(0);
+
+	def butterfly(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S):
+		if self.scale == 1:
+			res = self.butterfly_scaled(Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S)
+		else:
+			res = self.butterfly_not_scaled(Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S)
+		return res
 
-	def butterfly(self):
-		Dre = ( Are + Bre ) / 2
-		Dim = ( Aim + Bim ) / 2
-		Ere = ( Are - Bre ) / 2
-		Eim = ( Aim - Bim ) / 2
+	def butterfly_not_scaled(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S):
+		out1_re = ( Are + Bre )
+		out1_im = ( Aim + Bim )
+		tmp_re = ( Are - Bre )
+		tmp_im = ( Aim - Bim )
+		res = self.efficient_complex_multiplier.multiply(tmp_re, tmp_im, C, C_plus_S, C_minus_S)
+		out2_re = res[0]
+		out2_im = res[1]
+		out1 = out1_re + 1j * out1_im
+		out2 = out2_re + 1j * out2_im
+		return [out1, out2]
 
+	def butterfly_scaled(self, Are, Aim, Bre, Bim, C, C_plus_S, C_minus_S):
+		out1_re = ( Are + Bre ) / 2
+		out1_im = ( Aim + Bim ) / 2
+		tmp_re = ( Are - Bre ) / 2
+		tmp_im = ( Aim - Bim ) / 2
+		res = self.efficient_complex_multiplier.multiply(tmp_re, tmp_im, C, C_plus_S, C_minus_S)
+		out2_re = res[0]
+		out2_im = res[1]
+		out1 = out1_re + 1j * out1_im
+		out2 = out2_re + 1j * out2_im
+		return [out1, out2]	
\ No newline at end of file
diff --git a/butterfly_processor.pyc b/butterfly_processor.pyc
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..6304d3a5fb3986c9a4198882e343dcdd5647c2d0
GIT binary patch
literal 1943
zc$}qF+iuf95FKx>PTMr4_X;79c(D3FM0rI(8<nTFpe;zy7ppi<<zmN?y^*NoNJ!-a
z_zQjyi4TA|6WeJ8LZ$d}ytBKrGjq;*D?b)mYxXzoQGQkUeZg<K&Cut^qL3)E=)@wc
zugF(4u&7_5FGQC_?@ub!uhOwo<LSXqz8s5NW{Y8eFbKTBADUhqjY9v^;W#wGC=C3>
z+~MK9u`zx!2rphIvFE30oRmpmi9IB-!{8HQb1Eka*>GIMRMM#CnVi&+1sZkI(`3?h
z6cBr<NrK_o{Xv}E?}evndUP83p5if;SKGtnE|TWQqKxZObgodHm5J?E$W#&ga%$F)
z&9Q?8jsoQC)Zs2s$0I+{LP3+kb%SAGTz5L=orb=~d~+9d74*2?lpi-L36ixrCOi4z
zK%?PM0V%K>k4*RArFQoZ-yZC~d8NA_3O?OYLFl8=g+_^>JFN?|%a(0<NX_QAS(N{d
zfh#)~y+0~So`}ii@}nrLP*$a^Mp>P*23<C2(xl-7nWO$TCu^2GffEPGNHwOzFw0n|
z>6?{nox|AV0}hhaLNZp^P5kLMh~&GM+k0#yOi#G)xubBLy2r*ABMOFMVPfK^x1>`R
zD~GVf(x&jbXgyR9rpzw!TQ8XX3}!8`vkpEKNLruRdEdsQmG^B-=5htVI`__9;j%`P
zdCKM?&gNu6T8dk3@XJ3yX4A_0WRbE3vD&aYlyOIg&J-(9EqAKOa6#9u@6SadT`P8N
zz7H>)rGj=X0<-{gfO)_Ipbc1rXM-Ugo5wDzQMOqTku4gbyJ!ZH?p$%%x#F?|mul`_
zG<I&g`BBY1c&&&?t^B?x*yj6p!M@G}W4c#oqKQ=sCsrw*ST_++l>$~u0jt*pto}*B
zng|G$Zlt2d5C2c<>16;|(yM?q05sCr<9Y+I3D~0BA4QOOd!|M^zh`PV4Jr@LA)nKH
zaJIyV;{G^<*$|VDb=Q@XO-qsRkkx0I-6B1Zijq^rtXp-<uGtNH{z!hGDX&;mc5(dS
X-1m&Q{7+1&_35;_XAmQWh8^__r6^(7

diff --git a/fft_8_decimation_in_frequency.py b/fft_8_decimation_in_frequency.py
new file mode 100644
--- /dev/null
+++ b/fft_8_decimation_in_frequency.py
@@ -0,0 +1,64 @@
+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
diff --git a/fft_8_decimation_in_frequency.pyc b/fft_8_decimation_in_frequency.pyc
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..3ac644699439065d1e42dd6f28746950639b1829
GIT binary patch
literal 2557
zc$}?O&2HO95S}GP>L<1%$BI=oIV4SiFhx)UIr$)@ZR!XJkh%rs!ia!?P{^fAg+CIx
zO5{R5rRc3d4?XwVcj!B`571}mp+Ijvw4E867Ufv&A)&ado!RBi&o|$${^xq*w`)Jy
zE}T9(wvVx8K6W0y0z!aDz(9Z?S%Xl6NQZ%*%Q}P=hzuAQ5ScJAA*#Zln$J}rtU*+V
zK^<iSWCMHwo(bOoyaISKxCCAm`c@511^?h<2^^^_*gcpkB~w2<{vu6WnPo|u&uw6L
z@G|hcQ1*tdO47_Cj}>)plJS2Q#7e{eagcv=3%f_LCuaxgFwXoWjrOD)L_-xM@uRqx
z%E?s5?y>6Nx?b;K_rlq;1ksic$jTk;Bv4*3)PY8s!niOkm?9cfC^s}P!0uZW`s6m{
zG;uSP2Jz7i^yJ2BdlX6K6p&Bp<0ljgz5?c$J`F}1B~i>-c63k`n4>Be4NxZF6pAN0
z%yk%5X*EsNK-EvDNNkY%ea_Urb%|^kWNkW@scn)-=r~Rg2g-32FSDV5>Dg;A*_`sL
zJQswXqjInuKSzr<cxf92F2Vof!l_f7KN<RV{meyo7)mY(wOkP79e3G1>~@l|+Iifw
zorj-&`S_EA&+Q%GSI(~Eo!P?J9KW#k;rQ65h^b|34EUC)i_2mSn@eR?#kO96f?Oa_
zygbty%zk8%aoBtMJtrSvBnT}+N{0?sMLxn+ZI*BWW7HW{Rtg5RS5Lk3stPBl<C5!O
z6`;OLQl*f{R(H~Y!`Y@F2aVi8U7Q#&`wL2{-{Hh8`HZgtbCWh`wb}4Fjd4zc`&_Ut
z*BXV}2AOM>;#jFz#Qh&jUXOoaxtxb(f4Y-j;BfLY=H!PmXx}b_mZz_<T#}5Ega+En
z^SQ<#)A@S=M6~W4Os8LVC%=kA^1&qH=Cl_0*SCn0`vISrM2UbZG$2w1RGWO1GCPn`
zN78PPST7URUMtv?%3;U@q`{F*6|L4;{X(XhbduDQsYS(ZGsnorOwoqKpJb}WxFs9r
zLpPO~sxG+5J{+aVbo|D2<n3`$leV}|8)<9I$%fbv>*AWYscndDZHsm9i@Rb|+!A-R
zZSkH)n(L_3@mJTbh<CN-g2T0f!{5O<4u8E6_nwAS4p<uq-mG7qcnHWH1QV0c!pdqP
zd@X`ZgR8`#3bWjR4*HK(ho2y@bVl>I)o!(M$H_f7oEK%o{A7@g1;~u=-*`73!_xD|
zN4(13q>fPJgVCnoY)aSyIeVMBc7fq@&gTono}`#7KuI-xJ2-j1+NCX;d~y;_Cbo|F
z0I{-4*GW8#Bwi;C7NW$Ph9p*5#2eCa_z<?QQ+Km)?9ESh@_<@KyPN1+y;isOE#|~l
znI_Ko>_X$q?((9vi>oZZ=_q|@?5joQ84Y#2xZE67+-|EJ%Wp$+D|t4Ou3|6WPQaY)
RZl2%!q6oYxnn;VL_Aj2R_GJJ7

diff --git a/index_transform_decimation_in_frequency.py b/index_transform_decimation_in_frequency.py
new file mode 100644
--- /dev/null
+++ b/index_transform_decimation_in_frequency.py
@@ -0,0 +1,35 @@
+class IndexTransformDecimationInFrequency(object):
+	"""docstring for IndexTransformDecimationInFrequency"""
+	def __init__(self, N):
+		super(IndexTransformDecimationInFrequency, self).__init__()
+		self.N = N
+		self.new_k = range(self.N)
+		self.build_index_vector()
+		print 'new_k = ', self.new_k
+		
+	def reverse_order(self, sequence):
+		for i in (range(len(sequence)/2-1)):
+			i = i+1
+			a = sequence[ i ];
+			b = sequence[ self.new_k[i] ]
+			sequence[ i ] = b
+			sequence[ self.new_k[i] ] = a
+
+	def build_index_vector(self):
+		if self.N == 8:
+			for indice in range(self.N):
+				b = '{:03b}'.format(indice)
+				b = b[::-1]
+				self.new_k[indice] = int(b, 2)
+		else:
+			print'error, value not supported by the index_transform function'
+
+if __name__ == "__main__":
+	indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(8)
+	x = range(8)
+	print 'x ', x
+	indexTransformDecimationInFrequency.reverse_order(x)
+	print 'x rearranged ', x
+	y = x
+	indexTransformDecimationInFrequency.reverse_order(y)
+	print 'y ', y
diff --git a/index_transform_decimation_in_frequency.pyc b/index_transform_decimation_in_frequency.pyc
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..d596b1755a41356fb86bdbe5b13458ae12a7a72d
GIT binary patch
literal 1768
zc$}@2+iuf95Qb;%*lwamsI4fJ3Sq=ekProNSA~j0=|L(%a*HY=A<MBh#c5)v>rF{S
za#eU1-ig=X0bpiqr&4d=B1v{Kd;aH}-8FyLYri&sdLa}a6U!?s*%VC#AOX4pA_3n4
zt^hu@1xN!T1I`UlW02Tq!j*uw39?f97DN@;mlo_FNE3QCpo{GyvdUHq+71+bPTpr@
zpM!k~?(4vDV+jT5M`#X{NRCfbkYwFd4R&Q14+0&h$zigm<i$uP;bbmfV0lCG9|LPg
zxfn#-C?Y_WD4iVEN{$8Iaic<0o>RnWm}wO!XD;sL{?E<^&N2#cZ)uqW(v3d>i15mQ
zo<ZQml<U3;x<XEmNl}Z%RhtK)%6+O4Bh-D|pp{!0p-ALc|J;4)HXK^tqMb%VsXU5W
z(*WO(lUVz{CI&4Yfy&P$dpujOqSqP4{RoF*Wd5ZLb*gw1%?M<_>ro&LC{5Nxvy~3@
z*3q8lzkC1j==I45Z!4d#OEi8oXM;=o-IC7J;lwN9WHnCEny89ZQ4<W#Dhh*((TqDK
zJ3)Mq$8Aj5U37Op@4?J~DIdN&<O!;5%uLA9_PBFnV}^VyMQ?L@qqljn38ze!B(-7^
z5fd=3djvs~*O!S$!Wv{er(~SvaY<$zvklmG7D!CjDRuHvs!aN+ilicP*)rpMi0Eo!
zg#d~I>>S_#4TTECjqYaz<J00GVk1M`ftetJJ)=NeFy+gRSK^0>NDYEOtra@JG@F4o
zFCM^Yf|q-KJZ*-^WXS!t{p>|&7XQHylg+m27AlphC+=m?A4xY!wTtI=m?|wJw=;3|
z7wO(W<90_$NMLgK*NLGmXh5JjM{%O_9GUYR+1wn(q4bs)e2i)7)$2Um66;vj#C?My
z6gMyl1`=;zjVpsR8uh8_a21~x-{;%lQG$8FYk><=S-ye%WZ1$MRj0aCh#Ler+Rw8^
zGRAIJ=RYL_#ZN`#a>vAN<*zSEOglY%C3s<PrF@d(e?N?Q%1FzY<7IcU=zux2W=?vC
S1E(CV-&+>+t%^Dp8|`0`iFgtK

diff --git a/main.py b/main.py
--- a/main.py
+++ b/main.py
@@ -1,7 +1,11 @@
-from efficient_complex_multiplier import EfficientComplexMultiplier
+from fft_8_decimation_in_frequency import FFT8DecimationInFrequency
 
-efficientComplexMultiplier = EfficientComplexMultiplier(0)
-res = efficientComplexMultiplier.multiply(70, 50, 121, 160, 82)
-print res
-print res[0]/128
-print res[1]/128
\ No newline at end of file
+N = 8
+scale = 0
+fft8DecimationInFrequency = FFT8DecimationInFrequency(N, scale)
+x = range(8)
+fft_val = fft8DecimationInFrequency.fft(x)
+dft_val = fft8DecimationInFrequency.dft(x)
+print x
+print "fft ", fft_val
+print "dft ", dft_val
diff --git a/twiddle_factors.py b/twiddle_factors.py
new file mode 100644
--- /dev/null
+++ b/twiddle_factors.py
@@ -0,0 +1,16 @@
+# exp( - j 2 pi k / N ) = W^k_N
+
+from math import exp, cos, sin, pi
+
+class TwiddleFactors(object):
+	"""docstring for TwiddleFactors"""
+	def __init__(self, N):
+		super (TwiddleFactors, self).__init__()
+		self.N = N
+
+	def build_twiddle_factors(self):
+		w = []
+		for k in range( self.N / 2 ):
+			teta = - 2 * pi * k / self.N
+			w.append(  cos ( teta ) + 1j * sin( teta ) )
+		return w
diff --git a/twiddle_factors.pyc b/twiddle_factors.pyc
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..1d8fffcca542623d03beadd36423f1fceef7692e
GIT binary patch
literal 1018
zc$}S6O>fgc5S?AS4g}E)jgYDyA_S68<PStZ`RJ(xu_;1Wf|YA;!Ulg~Z`4*wPT{xk
z>o_2B2WG}GRePf=@9d6t^7g$q8}HZM{=tv$DuM0ra6ZG?j4`D63CI9)0g-@QLL?#g
zAo3vhA@V__63h<F1f(8(1K0q3hyqA`n1(wDVE^C<ecU+$Hs=+uN!jq)*uqI%E9-V~
zIXSawnwg_Gab?~7qa<)Xr|Ka=05L&g$OO6Jok#{*(8dQf4H@@<$d^guYFo^Qv$7su
z!=_v1R_==q+u<i*g)$^8B#99#&b3E3PD5fcY2}c*W?7k9ae51b*0!)tYuA<$yraX$
zWHZ&nO$c3R9%2}kl^Y!&DgEm8yW_)?H)`Zsl6uy%d|X|q01N52jn7ux6A7VH5_Hr*
zVVDD~1)RSn4M=z)$eh7Oz{`(gSW9vUo!(o~<m18G0~ELLh~vtG4Yv?wwfnvM7{u3o
zc#lO>mOQbf$o|HTUci;{^Jy4#p44$MH>_5Xw~h|tsxn2Yh`1sQhErr2TXn|q3wz~^
zi*I0)8(`t-(q^f?c6f(i`s`gG_QgOv68ti^9V_D8V8{BL<Yl_dDD82I4@hfnfZDy%
zz5i?>>Eh=?Pyy1o?N7p9_d4>}eO3f`>CdHe<>|sCjuCEpJqsPT(w^|2gRXcW{{njl
BzM234