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

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

Hello,

its done. -> Low resource FFT core in myhdl
The file (a single file implementation, oh i like them) of the core is  
attached.
Here are basically the specs of the core:


# Description: This Unit does FFT in Hardware, with Fixpoint, it uses 2  
multipliers only
#        + Input data bitwidth is adjustable, Twiddle bitwidth must be the  
same for now
#        + Calculation time:   N*log2(N)+8 clock cycles , N...FFT length
#        + FFT length is setable to: 16,32,64,128,256, ...
#        + Does a complex FFT (real and imaginary values)
#        + With 18 Bit input data and 18 Bit twiddle factor the 128 point  
complex FFT has the following
#        resource usage on a Cyclon II with Quartus: 427 Logic Elements,  
4501 Memory Bits,
#        4 9Bit Multipliers== 2 18Bit Multipliers ,  runs up to 80Mhz on  
Cyclon II EP2C35 speedgrad 8
#        + The FFT core read and writes from/to an external supplied RAM.  
The RAM needs a seperate read-address
#        and write-address.During operation the FFT core needs full read  
and write acces to the RAM. Every
#        clock cycle (when the piplene is filled) one Data is read and one  
is written to/from the RAM.
#        + No Scaling
#        + The Testbench shows the error of Fixpoint FFT vs. Floatingpoint  
FFT pylab reference implementation
#        for a given inputvector-Testdata, or if an overflow occours  
(myhdl built in).
#        +Simple performance evaluation, just add some simple python code  
to the testbench to check whether the
#        fixpoint implementation matches your accuracy needs.
#        + FFT length could be made adjustable during operation in  
Hardware with little effort. e.g for interpolation
#        Note: To do the iFFT, conjungate the data before the start of the  
FFT and after the FFT is finished
#        and dont forget the scaling


All the best,
New year and X-mas greetings
Norbert



Am 26.11.2012, 16:53 Uhr, schrieb 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
>
>
> ------------------------------------------------------------------------------
> Monitor your physical, virtual and cloud infrastructure from a single
> web console. Get in-depth insight into apps, servers, databases, vmware,
> SAP, cloud infrastructure, etc. Download 30-day Free Trial.
> Pricing starts from $795 for 25 servers or applications!
> http://p.sf.net/sfu/zoho_dev2dev_nov


-- 
Erstellt mit Operas revolutionärem E-Mail-Modul: http://www.opera.com/mail/