[myhdl-list] Low resource FFT core in Myhdl, first python Modell

[Norbo <Nor...@gm...>]

The aim was to create a FFT core in Myhdl. The Number of FFT points should  
be adjustable with 2**x.
The upper limit of x should be not limited by the algorithm but just by  
the memory needed.
The following python script should be a good starting point. Note the code  
uses only
multiplication, additions and the lookuptable (i am thinking about  
replacing the lookuptable by a recursive chebyshev cosinus generator so  
that the implementation itself can work quit inplace). It was written with  
the hardware implementation in mind, wherby the input Data can be supplied  
through a Embedded memory block. The memory bandwidth would then create  
the speedlimit. Since only one value would be read and written at a clock  
cycle.
I am not sure if i will finish this. But every comment, critic,  
improvements are welcome.

grettings
Norbo


### Python FFT implementation (for a myhdl implementation reference) ####
Author: Norbert
Date:26.11.2012
#########################################################################

 from pylab import fft,log2,exp,pi,arange
xin=[-7,2,3,4,5,6,7,8,-7,2,7,4,5,2,-7,2]

FFTlength=len(xin)
log2_FFTlength=int(log2(FFTlength))

assert 2**log2_FFTlength==FFTlength

###data reordering ######
Orderlookup=[]
for i in range(FFTlength):
     sst=list(bin(i)[2:].zfill(log2_FFTlength))
     sst.reverse()
     val=int("".join(sst),2)
     Orderlookup.append(val)

FFTdata=[xin[i]  for i in Orderlookup]
######end data reordering ########

lookuptable=exp(-1j*2*pi*arange(0,FFTlength/2,1)/(FFTlength))
count=0
valx=2
sections=FFTlength    #2**(log2_FFTlength-1)
while valx<=FFTlength:
     sections=sections>>1  # FFTlength/valx

     for cur_sec in range(sections):
         for i in range(valx>>1):
             aww=FFTdata[i+valx*cur_sec]
             bww=FFTdata[i+(valx>>1)+valx*cur_sec]*lookuptable[i*sections]   
# exp(-1j*2*pi*i/valx)

             FFTdata[i+valx*cur_sec]=aww+bww
             FFTdata[i+(valx>>1)+valx*cur_sec]=aww-bww
             #count=count+1
     valx=valx<<1

################# check result ##################
fftxin_reference=fft(xin)
Error_allowed=0.0001
for ind,fftval in enumerate(FFTdata):
     print fftval,"=",fftxin_reference[ind]
     assert  
(abs(fftxin_reference[ind])*(1-Error_allowed))<abs(fftval)<(abs(fftxin_reference[ind])*(1+Error_allowed))
     print "-"*50