diff --git a/.hgignore b/.hgignore new file mode 100644 --- /dev/null +++ b/.hgignore @@ -0,0 +1,2 @@ +syntax: glob +*.pyc diff --git a/butterfly_processor.pyc b/butterfly_processor.pyc index 6304d3a5fb3986c9a4198882e343dcdd5647c2d0..a45905ac0d430c6f1c328f3463505695ccf0d6a2 GIT binary patch literal 2141 zc$~FWU2D`p6up`K-nQG-R$E0x!H3|3ODhTmQM+peL90v^v_6D2o0ZgLvm~=%AqztN z0sahsoDYIOK<~MmWLp%`ht0>y+?ly^@0>F;Dg9V!etY{>yOdoeejoCi++-N=V^Kg9 zT6AcUHBjU!8d@|c(PyF)qBn;n8kFh4u5fq%CttS3C3Bf!Z#eW_-y4};6pjP$iHZHu`)k7}zSax+NwVJ$Jy&s?%4XX`=MIwQ$D)+yrRYduc2+93QzBDF z?30;UK{f|A2H5wJuU&<^M4gPiSPKPp2FLM7zHyvco7)dOjsE5e=9SaqxHEp7upmgr z=9ui{1w)O3O*te_7&`G})Cs+T-|zGXp+D;E?LOMQd*{&>aHqSq(}~8W^YpQH_MW|Z zy8H6E?!3zhcg8v6x5mdB96*nxD%7u84a-ID4Swr6Kd%{h>PNC5J}8QBi^+WOqbMy= zTBfu@X_e9%oz!Srr_pukqyE+>trtXsG#kmtbWNLKp0RK@FzaV3N0G@IY$U5i1&pv8 zd$X?}%D0=@UA7UXC*t&+aWF}o1Je+LNfZkmV=q}0-x958!Xi!TLj0lPZ-KrI5T?N5#uZBCn6-R5*DlL)eK?b0c-D>PlEbQ$VhnyyGmaj69XcnhTs zTHlziQo15m3s##_u4vPH#S)c^wJtgx)0yl01JO`d@^zoBu8S6hnt&z1GGGPJ z0<6Nb#t==+mcw!tWtL2I4aca?i+-rvr(CvAxopFwoVn+P?S*Y0O!q2=T^ALb*?m>8 z#rN-uewi!EdR&;RDpsMaScSS`{fok?P`FemTt1_4`A-U0L}AGIPcmy98UH1(UITz7 zeF1P001-7df!+jM0$ipAo_1IyH|KJ-vU@IWj!9vVgP%NmZ??)u=RTjpcpWp)+L=RW?fW?#OeExGXd&Ve8(EpZm}| I!7^#9Uu>P8;s5{u diff --git a/efficient_complex_multiplier.pyc b/efficient_complex_multiplier.pyc index 34cf088e9ee4ce7b13d05873d31a6e060f8c60d2..dcbf20f95a54a74274de52a74ab7d304bdb50c74 GIT binary patch literal 1022 zc$~dc+iKfD5FK5t*n#w=frLEyQBM_twh$<#j^aWfabev;<322^v@#oXL%V_m~1!Y6nf}!W4wyUC2WjcwHtkhLBom@=bzq>dk zJUc%_m zYc3ogt^()>ba~hZaJ1Tk-luyM9j}JaV`2zPch^3*K!k#gpyYSP8^)Nuh-FiBM$YYs z1MH0>Dp)WI#>*Esgw<>^_aw#)*_c=S4F^xdtMFXl@b)<<>#Qp%+~W|Bk(BJMIQVCb oFFMQZyJTpDffG0*f3`kUl&F8+s?-YjZ+h6L4{K*WvM$=}FKM;gn*aa+ diff --git a/fft_8_decimation_in_frequency.py b/fft_8_decimation_in_frequency.py --- a/fft_8_decimation_in_frequency.py +++ b/fft_8_decimation_in_frequency.py @@ -1,6 +1,6 @@ from butterfly_processor import ButterflyProcessor from twiddle_factors import TwiddleFactors -from math import cos, sin, pi +from math import cos, sin, pi, log from index_transform_decimation_in_frequency import IndexTransformDecimationInFrequency class FFT8DecimationInFrequency(object): @@ -14,50 +14,37 @@ class FFT8DecimationInFrequency(object): 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] + # 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): - fft_output = range(8) - for k in range(8): + N = len(x) + fft_output = x[:] + for k in range(N): val = 0 - for n in range(8): + 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 diff --git a/fft_8_decimation_in_frequency.pyc b/fft_8_decimation_in_frequency.pyc index 3ac644699439065d1e42dd6f28746950639b1829..1a9191e63417cd667addb9841019ee88fb51fe1f GIT binary patch literal 2659 zc$~de+iu%N5S`^kl;mq|rH-7U5SjjE*tO*bNZo*Pkw$1i$l^++%8N{{ z5;>62hx7}I{zQME-&LURZD(dh*+Fdh&7!#6*;#UD=bSTZ{HlZ>BP5GwFakNV)G>S<@hx1#91#%qeIyZqK*oZ_(|MM z<@rd)-3wL4dClhO<7>V1bkQddXtix@Bv6)c%WZ@5hWo=LVZx|mQKqP4gWKY0vn|SS z(#=#F#QhpZQoDIQ+JZHM=WBZT1?>g@0w$P70|o{qQ%uIl;2}t z5c;0dpm{xw8h_xGTgY(~=!Q#87V&gQDXmYhlw!M{y&Pe$Z)j z{3wVUNBf8SpM84xh}zwQN4t$=s2We3u6Ok9_fPjvzjGVCp7I`h{yZ4myw}Ua`DA$E zmhiijmTZw3u`WttMJ(doCH_$omvhwq!VP1xKb#sf@Q|W9`N)?y#ta~&%<(c^THo4GpV7$#Q7W9h`#Iy+GH6C*G zkR_%if`4Gaz$V^IiZChB8x{OgWurPMTs!JqGm4!X=4+3`3l-VvK!vB?GT^|*?Njc* zabQ}82{PD*>btA&k;l5uLvih${|?X3f5p2A&*|GG7?fuU68LDg3wF5z3fJjLh##m*WTTD%1+1~UQeURLh`RzzFo3Zlkr0cMk-}j4)A5<7!{aHx zXbI7PmX?ykd|E$EM#D@wm&)SFJj}tT@(x7CE8(P7T4RS+G92+hY@pi8Vi~V>*4_Jf zZQ}Kwcqq1wO|fIFY84h|H>>auT{~w5(a?%CVf>oQsi8Fy0_qF-f!Z3kt~!o@1ZI$Q zE5sqxV1*cC!adX)%8qJq0jgAiSzjn%OquRiHY%jn^Ic?_&5E^P@4SYV3Hn$#VWI^8 z;z4);Z~gxMl1b>UQ&XXa=5q;jX^$@Dh>uYQ->uHQo78-ev+X7Fh)|CiYb90Zj_~t) zilEEZxK1t#2Qe$)T@^csAa8DVzQmnK;`vf$BTD>HNT$Ok9+{rUMc1V>!`;ebzk^aw z5m1;Jg;~JhOU2UWNu4C9)~_no8_thF3P`P7$|pbk^w~%d;9@^tBB)X2+OP$)GtpD| lp?Fht`VgfiIUC5X;!y7>EezV8hUp8Dr)O2HijTyq@jr`KE!zM9 diff --git a/index_transform_decimation_in_frequency.py b/index_transform_decimation_in_frequency.py --- a/index_transform_decimation_in_frequency.py +++ b/index_transform_decimation_in_frequency.py @@ -8,28 +8,49 @@ class IndexTransformDecimationInFrequenc print 'new_k = ', self.new_k def reverse_order(self, sequence): - for i in (range(len(sequence)/2-1)): - i = i+1 + old_sequence = sequence[:] + for i in (range(len(sequence))): a = sequence[ i ]; - b = sequence[ self.new_k[i] ] - sequence[ i ] = b - sequence[ self.new_k[i] ] = a + sequence[ i ] = old_sequence[ self.new_k[i] ] def build_index_vector(self): - if self.N == 8: + if self.N == 8: # 2^3 => 3 bits for indice in range(self.N): b = '{:03b}'.format(indice) b = b[::-1] self.new_k[indice] = int(b, 2) + elif self.N == 16: # 2^4 => 4 bits + for indice in range(self.N): + b = '{:04b}'.format(indice) + b = b[::-1] + self.new_k[indice] = int(b, 2) + elif self.N == 32: # 2^5 => 5 bits + for indice in range(self.N): + b = '{:05b}'.format(indice) + b = b[::-1] + self.new_k[indice] = int(b, 2) + elif self.N == 256: # 2^8 => 8 bits + for indice in range(self.N): + b = '{:08b}'.format(indice) + b = b[::-1] + self.new_k[indice] = int(b, 2) else: - print'error, value not supported by the index_transform function' + print'error, N = ', self.N, ' is not supported by the index_transform function' if __name__ == "__main__": - indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(8) x = range(8) + indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(len(x)) print 'x ', x indexTransformDecimationInFrequency.reverse_order(x) print 'x rearranged ', x y = x indexTransformDecimationInFrequency.reverse_order(y) print 'y ', y + x = range(16) + indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(len(x)) + 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 index d596b1755a41356fb86bdbe5b13458ae12a7a72d..a86539ae1196dac83604575fe8205e949d1a7bf8 GIT binary patch literal 2414 zc$~eJ-EJF26vxl(uGb$;M3qRDQVCdrDojH}69N4I6gJgB1>{mq2r_^! z`rREB!hXGM60%m+2GDOn+14o9LTqbL8%|vRKPEP~tp@D2o47ysCYpyvs_A2!ntYVm z@wOW3aq4tt9-0SM9Zi%O&K7h8e)ovZ+rVg$1~Tedi(7N$Yz%ibP2m2nKi#TRK@xcXD*ylr`ni{(ycfwV6 z$wN*%xbEFH&D_fyXpQLy{ZBr7wDtJYxKjwYid`ZX@K8G$Rrqcm&fa z+JlO07Y$;3ZSKKzqhc(|OSk>x8q9t2k9}C1BV>=kdhD+i^_xdmVUNKwq&CUMG{2+L zfif`(w#mfx3T$4iRkSB%Hi4tn9 zg7-bv5D%bGpxhu~`mHE#DONJUyD%3NAOww}B5A}ZIniLed_!bCfO*75sGHL8J4Rbr`S6wZV|0>8s*FU&#Kh&vmhgG zm_>Y{dc|`~8_5Ry_$=`3@yg=BNoX3=eEcTse}5Sn4Ud~$I2)$0S)AHkX7mP{D{n1{ PC45_&Vi~`X?O**D0r2~2 diff --git a/main.py b/main.py --- a/main.py +++ b/main.py @@ -3,9 +3,17 @@ from fft_8_decimation_in_frequency impor N = 8 scale = 0 fft8DecimationInFrequency = FFT8DecimationInFrequency(N, scale) -x = range(8) +x = range(N) fft_val = fft8DecimationInFrequency.fft(x) dft_val = fft8DecimationInFrequency.dft(x) -print x -print "fft ", fft_val -print "dft ", dft_val +print "fft ", fft_val +print "dft ", dft_val + +N = 256 +scale = 0 +fft16DecimationInFrequency = FFT8DecimationInFrequency(N, scale) +y = range(N) +fft_val = fft16DecimationInFrequency.fft(y) +dft_val = fft16DecimationInFrequency.dft(y) +print "fft ", fft_val +print "dft ", dft_val diff --git a/main_twiddle_factors.py b/main_twiddle_factors.py new file mode 100644 --- /dev/null +++ b/main_twiddle_factors.py @@ -0,0 +1,6 @@ +from twiddle_factors import TwiddleFactors + +N = 8 +twiddleFactors8 = TwiddleFactors(N) +twiddleFactors8.build_twiddle_factors() +twiddleFactors8.twiddle_factors_dot_vhd_generation() diff --git a/twiddle_factors.py b/twiddle_factors.py --- a/twiddle_factors.py +++ b/twiddle_factors.py @@ -7,10 +7,24 @@ class TwiddleFactors(object): def __init__(self, N): super (TwiddleFactors, self).__init__() self.N = N + self.w = [] + self.w_int = [] 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 ) ) + self.w = w[:] return w + + def twiddle_factors_dot_vhd_generation(self): + print 'size of w = ', len(self.w) + nb_bits = 16 + print self.w + for k in range( self.N / 2 ): + w_int_re = int(self.w[k].real * 2**(nb_bits-1)) + w_int_im = int(self.w[k].imag * 2**(nb_bits-1)) + self.w_int.append( w_int_re + 1j * w_int_im ) + print self.w_int + pass diff --git a/twiddle_factors.pyc b/twiddle_factors.pyc index 1d8fffcca542623d03beadd36423f1fceef7692e..20ccf30db0e526f5dae167ce0c96742fab15cab9 GIT binary patch literal 1575 zc$}S7OK;Oa5T3Oi=K%%OHY!vViYkG^g#+S*${X4qN)X#3L{zkL;!V0Cwu8MTElN)1 z#1G+z@GtlmNZf&$aa{FrqJFG*y|c65!(;dNTAF>Ox!^Qgv-q{*9AzlK80Fi*U zfXIQi1Ca}D7a|YZ9*EEZU4ou~(1ou6M*#2JK7<}@H%pkn{Kcc`Vb4-xeK6u@H_7;! znbW2CS7pYjYy1movFLI+V0Mt5JU3^ zKZZj%b^LnVEEk%kLEP8OUXmM@@CKuijzdWlB;}CAjC0CbF=RPEvVKbI)--k z%`jAFCg&*8W!BRd%c3rBiCV5{>7=ILfoo;sSWc8-IcnI@W1mO%jvi**qINkJeVu+*LeR zu$R|yUbt}(X)N3t527U8AJVYQL;SNS#Z@P-QnPfba{s%0z1c^_