altera corporation 1 implementing fft with on-chip ram in flex 10k devices february 1998, ver. 3 application note 84 a-an-084-03 introduction the fast fourier transform (fft) function forms the fundamental building block in many digital signal processing (dsp) applications, including communications, voice recognition, spectrum analysis, quadrature amplitude modulation (qam), asymmetric digital subscriber line (adsl), radar, and image manipulation. the fft_on_chip reference design implements an fft function using the altera fft megacore a function and on-chip ram. this application note explains how to instantiate and simulate fft in a flex 10k design, using the fft_on_chip reference design and the altera max+plus ii software. the instructions in this application note are valid for both pcs and unix workstations and assume the following: n max+plus ii version 8.1 or higher is located in the default location, c:\maxplus2 directory for pcs and /usr/maxplus2 for unix workstations. n the fft megacore files have been installed to the default location, c:\megacore directory for pcs ; there is no default directory for unix workstations. n your command search path includes the megacore\bin directory. otherwise, you must enter a full pathname to execute twiddle.exe . n you have added the megacore\lib directory as a user library in the max+plus ii software. n you have purchased a license for the fft megacore function or are using the altera opencore a feature. 1 you can use altera?s opencore feature to instantiate, compile, and simulate the fft megacore function. however, you must obtain a license from altera before you can generate programming or configuration files. fft_on_chip the fft_on_chip reference design uses the flex 10k embedded array architecture to provide on-chip ram for storing data and twiddle factors during the data processing stages. two memory blocks store data during read and write transactions and one memory block stores the twiddle factors. each memory block stores both real and imaginary elements that are read in parallel.
2 altera corporation an 84 : implementing fft with on-chip ram in flex 10k d e vices the following discrete fourier transform (dft) equation normally requires n 2 multiplications, where n represents the number of points in the fft. however, by using the decimation in frequency (dif) fft algorithm implemented with fft , the required number of multiplications is reduced to ( n /2)log 2 n . where: k = 0, 1, 2,... (n/2) e 1 n = number of points n = current input data point j = ( w n ) nk = twiddle factor f for more information on fft_on_chip , refer to functional specification 7 (fft_on_chip fast fourier transform) . for more information on the fft megacore function, refer to the fft fast fourier transform data sheet . instantiating fft_on_chip the following steps explain how to instantiate the fft_on_chip reference design using the max+plus ii software. the typical pc installation of max+plus ii creates windows program items so that all required programs can be launched from a windows icon. in a unix environment, you can bring up the max+plus ii graphical user interface by typing maxplus2 at the unix command prompt. 1 for detailed information on how to use the max+plus ii software, refer to max+plus ii help. 1. c r eate an f fttest di r ectory on your computer and then change to this di r ectory by typing the following commands at a dos or unix p r ompt. this di r ectory will be the p r oject di r ector y . mkdir ffttest cd ffttest 2. copy the simulator channel file ( f ft_on_chip_walk.scf ) f r om the fft walkthru di r ectory into your f fttest di r ector y . 1 the walkthu directory is installed to c:\megacore\fft\walkthru . x k ( ) x n ( ) e j 2 p e ( ) n ( ) n k n 0 = n 1 e ? = x n ( ) e j 2 p e ( ) n ( ) n k n 0 = n 1 e ? = x n ( ) w n ( ) n k n 0 = n 1 e ? = 1 e
altera corporation 3 an 84: implementing fft with on-chip ram in flex 10k de vices 3. generate the twiddle factors. in the f fttest dir ectory , type the following command at a dos or unix pr ompt: dos c:\megacore\bin\twiddle 4 8 9 unix /megacore/bin/twiddle 4 8 9 this command generates the tw4_8.mif file, which contains twiddle coefficients. 1 for help on the syntax of twiddle.exe , type twiddle with no arguments at the command prompt. tw4_8.mif is a memory initialization file ( .mif ) in the flex 10k embedded array block (eab) memory format. using any text editor, you can verify the following contents: depth = 8; width = 16; address_radix = dec; data_radix = hex; content begin 0: 8000; 1: 8a31; 2: a55b; 3: cf76; 4: 007f; 5: 3176; 6: 5b5b; 7: 7631; end; the twiddle coefficients start after the begin line. after scaling for the requested bit depth (8 bits in this example), each line lists the twiddle factor in hexadecimal format. the real part of the twiddle number is listed first; then the imaginary part. for example, twiddle number 0 is 8000 hex. this means the real part of the twiddle number is 80 hex, and the imaginary part is 00 hex. for an n -point fft, the twiddle factors are simply exp(j w t) values from the unit circle on the complex number plane. there are n such values equally spaced around the upper half (positive imaginary value) of the unit circle, with the first value on the positive-real axis. 4. start the max+plus ii softwar e. 5. choose new (file menu) to cr eate a new graphic design file ( .gdf ). 2 4 2 8 =
4 altera corporation an 84: implementing fft with on-chip ram in flex 10k de vices 6. double-click in the graphic editor window . in the enter symbol dialog box, double-click on the \megacor e\lib symbol library and then select f ft_on_chip in the symbol files box. when the edit ports/parameters dialog box opens, choose cancel ; you will enter this information at a later stage. if the megacore\lib symbol library does not display, you can add it as a user library with the user libraries command (options menu). 1 you can use a version of the fft_on_chip_walk.gdf file that already contains all the inputs, outputs, and parameters. copy fft_on_chip_walk.gdf from the walkthru directory into your fft directory. if you use this file, skip steps 7 through 10. 7. enter , name, and connect the input and output pin symbols to the fft_on_chip symbol. for the simulation to work, the gdf pin names must match the fft_on_chip symbol port names, as shown in figur e 1 . figure 1. labeling the input & output pins 8. save the t le as f ft_on_chip_walk.gdf in your f fttest dir ectory . 1 do not save the file as fft_on_chip.gdf because it will make the function recursive in the hierarchy tree, resulting in an error. 9. set the parameter values for the fft_on_chip symbol with the edit ports/parameters command (symbol menu). t able 1 shows the parameter values for the design described in this application note. cloc k star t_fft data_in_re[] data_in_im[] load_bank_reset load_bank_enab le unload_bank_reset unload_bank_enab le load_nr un done data_out_re[] data_out_im[] e xponent[] twiddle_file= width_add= width_d a t a= width_exponent= width_twiddle= fft_on_chip clock st ar t_fft d a t a_in_re[7..0] d a t a_in_im[7..0] lo ad_bank_reset lo ad_bank_enable unlo ad_bank_reset unlo ad_bank_enable lo ad_nr un done d a t a_out_re[7..0] d a t a_out_im[7..0] exponent[3..0]
altera corporation 5 an 84: implementing fft with on-chip ram in flex 10k de vices figure 2 shows how the fft_on_chip_walk.gdf file should appear after you set the parameter values. figure 2. fft_on_chip_walk.gdf file 10. save your t le by choosing save (file menu). 1 1. set your pr oject to the curr ent t le by choosing the project\set project to current file command (file menu). 12. set the synthesis options for your design using the device command (assign menu). select flex 10k as the tar get device family and aut o as the tar get device. 13. t o obtain the best synthesis r esults, set the following options in the det ne synthesis style dialog box, which is available fr om the global project logic synthesis dialog box (assign menu). t urn on the use lpm for ahdl operators option and set the style to f ast . 14. save and compile the design. table 1. parameter values parameter value twiddle_file "tw4_8.mif" width_add 4 width_data 8 width_exponent 4 width_twiddle 8 cloc k star t_fft data_in_re[] data_in_im[] load_bank_reset load_bank_enab le unload_bank_reset unload_bank_enab le load_nr un done data_out_re[] data_out_im[] e xponent[] twiddle_file="tw4_8.mif" width_add=4 width_d a t a=8 width_exponent=4 width_twiddle=8 fft_on_chip clock st ar t_fft d a t a_in_re[7..0] d a t a_in_im[7..0] lo ad_bank_reset lo ad_bank_enable unlo ad_bank_reset unlo ad_bank_enable lo ad_nr un done d a t a_out_re[7..0] d a t a_out_im[7..0] exponent[3..0]
6 altera corporation an 84: implementing fft with on-chip ram in flex 10k de vices simulating fft_on_chip the following steps show how to simulate fft_on_chip using the max+plus ii development system. 1. open the max+plus ii simulator . 2. choose inputs/outputs (file menu) and select f ft_on_chip_walk.scf as the t le to simulate. 3. choose the start button to start the simulation. figur e 3 shows the waveforms generated fr om f ft_on_chip_walk.scf . figure 3. simulator channel file fft_on_chip_walk.scf as shown in figure 3 , after done goes high, the processed data appears in the 14 m s to 16 m s range on the fifth rising clock edge after the unload_bank_enable and load_nrun inputs go high. figure 4 shows the figure 3 waveforms in greater detail. figure 4. detailed view of fft_on_chip.scf
altera corporation 7 an 84: implementing fft with on-chip ram in flex 10k de vices t iming analysis the max+plus ii timing analyzer can analyze the timing performance of a project after it has been optimized by the compiler. to begin a timing analysis of fft_on_chip_test , choose registered performance (analysis menu) in the timing analyzer window and then choose the start button. the timing analyzer should show the fft performing at approximately 60 mhz. signal the fft_on_chip_test reference design described in this application note uses a signal of the form: y ( t ) = sin( t ) e (1/3)sin(3 t ). the 16 data points from this signal were plotted in the range [e p , p ], scaled, and then used as input data for the fft_on_chip _test simulation. figure 5 shows the plot of the input signal data. figure 5. input data points figure 6 shows the resulting plot of the magnitude vs. frequency response for the sinusoid in figure 5. figure 6. magnitude response amplitude 150 100 50 0 C50 C100 C150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 time 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 13 magnitude f requency 0 100 200 300 400 500 600 700 800
altera, max, max+plus, max+plus ii, megacore, opencore, flex, and flex 10k are trademarks and/or service marks of altera corporation in the united states and other countries. altera acknowledges the trademarks of other organizations for their respective products or services mentioned in this document. altera products are protected under numerous u.s. and foreign patents and pending applications, maskwork rights, and copyrights. altera warrants performance of its semiconductor products to current specifications in accordance with altera?s standard warranty, but reserves the right to make changes to any products and services at any time without notice. altera assumes no responsibility or liability arising out of the application or use of any information, product, or service described herein except as expressly agreed to in writing by altera corporation. altera customers are advised to obtain the latest version of device specifications before relying on any published information and before placing orders for products or services. copyright 1998 altera corporation. all rights reserved. 101 innovation drive san jose, ca 95134 (408) 544-7000 http://www .altera.com applications hotline: (800) 800-epld customer marketing: (408) 544-7104 literature ser vices: (888) 3-al tera lit_req@altera.com an 84: implementing fft with on-chip ram in flex 10k de vices 8 altera corporation printed on recycled paper. figure 7 shows the phase response for the signal shown in figure 5 . figure 7. phase response conclusion the fft_on_chip reference design instantiates the fft megacore function and also takes advantage of the flex 10k embedded array to provide on-chip ram for storing data and twiddle factors. this application note demonstrates how to implement and simulate the fft_on_chip reference design. arctan(real/mag) 1.5 1.0 0.5 0 C0.5 C1.0 C1.5 (n) C2.0 2.0
|
