CoreFFT Fast Fourier Transform Synthesis and Simulation Support Product Summary Actel Libero IDE ® ® Synthesis: Synplicity, Synopsys (Design Compiler / Intended Use FPGA Compiler), Exemplar™ • Fast Fourier Transform (FFT) Function for Actel Simulation: OVI-Compliant Verilog Simulators and FPGAs Vital-Compliant VHDL Simulators Contents Key Features Forward and Inverse 32-, 64-, 128-, 256-, 512-, 1,024-, and 2,048-Point Complex FFT General Description ................................................... 1 Decimation–In-Time (DIT) Radix-2 Implementation CoreFFT Device Requirements ................................... 3 Optimized for Actel FPGAs Architecture ................................................................ 4 Selection of Unconditional or Conditional Block Buffering Scheme ....................................................... 5 Floating-Point Scaling FFT Computation ........................................................ 5 Embedded RAM-Block-Based Twiddle Factor Finite Word Length Considerations .......................... 6 Generator CoreFFT Generator Parameters ................................. 7 8- to 16-Bit Configurable Input/Output Data and I/O Signal Description ................................................ 8 Twiddle Coefficients Precision I/O Interface and Timing ............................................ 9 Naturally Ordered Input and Output Data References ................................................................ 11 Two’s-Complement Fixe d-Point Arithmetic A Sample Configuration File ................................... 11 Built-In Memory Buffers Ordering Information .............................................. 11 CoreFFT Provides Register Transfer Level (RTL) Appendix I: Fast Fourier Transform ......................... 12 Code and a Behavioral Testbench List of Changes ......................................................... 14 Datasheet Categories ............................................... 14 Targeted Devices ® ProASIC 3/E PLUS® ProASIC ® Axcelerator General Description RTAX-S CoreFFT is an RTL generator that produces an Actel FPGA–optimized FFT engine. The resulting module computes 32-, 64-, 128-, 256-, 512-, 1,024-, or 2,048-point Core Deliverables complex forward or inverse decimation-in-time (DIT) Full Version FFTs. The input and output data is represented as bb-bit – CoreFFT RTL Generator; Generates User- words comprising b-bit real and imaginary parts Defined FFT Model and Test Harness; Fully (bb = b + b; b = 8 to 16 bits). Both the real and imaginary ® Supported in Actel Libero Integrated Design parts of the input and output data are two’s- Environment (IDE) complement numbers. The FFT module contains all the necessary memory buffers and butterfly and controlEvaluation Version logic, as well as a twiddle factor generator. A dual input – Supports FFT Engine and Test Harness buffer and a single output buffer support simultaneous Generation with Limited Parameters; Fully input of the new data samples with FFT computation and Supported in Actel Libero IDE result output. The module processes frames (bursts) of data with a frame size equal to the transform size of N words. The FFT computational process occurs in a May 2007 v4.0 1 © 2007 Actel Corporation CoreFFT Fast Fourier Transform sequence of stages with the final result obtained at the A negative nreset signal resets the FFT module. After last computational stage. As soon as a final output vector reset (input nreset taken HIGH), the module enters an is ready, the FFT module puts out an N-word frame of FFT initialization state where internal RAM-based lookup results. tables (LUTs) are initialized. Once initialization is complete, the CoreFFT module automatically switches to An FFT-based system (Figure 1) consists of the following: a ready state, prepared to receive data samples to be A host presenting data to the FFT module to be processed. The module input start can be used to bring processed the module to the ready state at any time after The FFT module initialization. A host accepting processed data Note: The CoreFFT module will discard data collected in Note: Signals shown in parentheses are optional. The its input and output buffers when start is taken HIGH by the host. host may use/generate these optional signals if required by the application. (Keep FFT Supplying Data) b-Bit Imaginary d_im load Data b-Bit HOST b-Bit y_im Imaginary Source of d_re Real Data Data Data to Be FFTed Input Data b-Bit d_valid y_re Validity Bit Real Data FFT Result HOST start (Start FFT) y_valid Validity Bit Receiver of FFTed Data nreset (FFT Results y_rdy are available) clk read_y pong (1-Bit Data ID) (output of another FFTed sample) Global Reset Master Clock Figure 1 • FFT Module System Block Diagram The data-source host supplies the FFT engine with the the state of the module signal, load. The CoreFFT data to be transformed. Every complex input data module drives load LOW once N samples (N is a sample (i.e., a pair of b-bit imaginary and real words) is transform size) of the current burst are received into the accompanied with a validity bit. Upon receiving the input buffer. As soon as the dual input buffer is ready for validity bit, the module assumes a valid complex data the next data burst, load is asserted again. The module is sample is present on both b-bit input data busses. then ready to receive the next data burst to be processed. Once the input data buffer is full, CoreFFT automatically starts processing data stored in the buffer. At this time, The data-source host can supply data at a maximum of the host source should stop supplying the data to every clock cycle, or it may skip an arbitrary number of CoreFFT, thus ending a current burst of input data. The "empty" clock periods. The host signals to the module data-source host can do so either by counting the that no data is being transferred for a given clock cycle number of input samples transferred or by monitoring by taking the validity bit d_valid LOW. 2 v4.0 CoreFFT Fast Fourier Transform Once the CoreFFT module has computed the FFT, the CoreFFT Device Requirements results are written to the module’s output memory Table 1 and Table 2 on page 4 provide typical utilization buffer, and signal y_rdy is taken HIGH. Every output and performance data for CoreFFT, which is sample is accompanied by a validity bit, y_valid, to implemented in various Actel devices with the indicate to the receiving host that a valid output sample configurations listed in Table 1 and Table 2 on page 4. is ready to be read from both b-bit output busses. The Device utilization and performance will vary depending receiving host can control the output sample rate using upon the FFT parameters used. The transform size the read_y input of the module. Asserting read_y parameter N primarily impacts the number of RAM indicates to the FFT module that the receiving host is blocks and the time required for transformation. "FFT ready to read samples. Deasserting read_y informs the Computation" on page 5 provides more details on how module that the host is not ready. Any unread samples the FFT time depends on the transform size. are held in the module’s output buffer until the host is ready. Table 1CoreFFT Device Utilization and Performance (bit width b = 16) Cells or Tiles Device Clock FFT FPGA Family and FFT Utilization RAM Speed Rate, Time, Device Points Comb. Seq. Total % Blocks Grade MHz µsec ProASIC3/E A3P1000 256 5,325 2,039 7,364 29.96% 14 –2 100 11 512 6,105 2,062 8,167 33.23% 14 –2 92 26 1,024 6,904 2,126 9,030 36.74% 28 –2 90 58 PLUS ProASIC APA1000 256 6,904 2,026 8,930 15.90% 28 Std 59 19 512 6,901 2,019 8,920 15.80% 28 Std 62 39 1,024 9,091 2,431 11,522 20.50% 56 Std 62 85 Axcelerator AX1000 256 3,398 2,373 5,771 31.81% 7 –2 130 9 512 3,601 2,380 5,981 32.96% 14 –2 120 20 1,024 3,863 2,404 6,267 34.54% 28 –2 105 50 RTAX-S RTAX1000S 256 3,407 2,370 5,777 31.84% 7 –1 107 10 512 3,596 2,381 5,977 32.94% 14 –1 90 27 1,024 3,881 2,397 6,278 34.60% 28 –1 76 69 Notes: 1. Auto-scaling (block floating point) is enabled in all cases. 2. The above data were obtained by typical synthesis and place-and-route methods. Other core parameter settings can result in different utilization and performance values. 3. All memory buffers are RAM-block-based. 4. Timing constraints supplied with CoreFFT were used. 5. Timing-driven layout options were used, effort level 3, with no multiple passes. v4.0 3 CoreFFT Fast Fourier Transform Table 2CoreFFT Device Utilization and Performance (bit width b = 8) Cells or Tiles Device Clock FFT FPGA Family and FFT Utilization RAM Speed Rate, Time, Device Points Comb Seq Total % Blocks Grade MHz µsec ProASIC3/E A3P1000 256 2,126 968 3,094 12.6% 7 –2 114 10 512 2,283 989 3,272 13.3% 7 –2 122 20 1,024 2,509 1,026 3,535 14.4% 14 –2 118 44 PLUS ProASIC APA1000 256 2,386 949 3,335 5.9% 14 Std 87 13 512 2,569 974 3,543 6.3% 14 Std 82 29 1,024 2,759 1,124 3,883 6.9% 28 Std 82 64 Axcelerator AX1000 256 1,317 958 2,275 12.5% 7 –2 170 7 512 1,435 986 2,421 13.3% 7 –2 159 15 1,024 1,620 1,016 2,636 14.5% 14 –2 137 38 RTAX-S RTAX1000S 256 1,317 958 2,275 12.5% 7 –1 132 8 512 1,435 986 2,421 13.3% 7 –1 116 21 1,024 1,611 1,027 2,638 14.5% 14 –1 101 52 Notes: 1. Auto-scaling (block floating point) is enabled in all cases. 2. The above data were obtained by typical synthesis and place-and-route methods. Other core parameter settings can result in different utilization and performance values. 3. All memory buffers are RAM-block-based. 4. Timing constraints supplied with CoreFFT were used. 5. Timing-driven layout options were used, effort level 3, with no multiple passes. The twiddle factors (algorithm coefficients) used by the Architecture FFT processor are generated by CoreFFT and stored in a The CoreFFT module input and output data are stored in RAM-based LUT. on-chip RAM blocks. The input memory buffer is also In addition to the FFT processor, the resulting module used by the FFT processor as working memory where the also contains control logic and a host interface used for FFT engine stores results obtained at any intermediate entering data and reading the FFT results. See Figure 2. FFT stage. This dual memory usage is possible due to the in-place FFT algorithm implemented by the core. Pong Buffer Data Buffer Ping Buffer Radix-2 Butterfly Mem 0 P Mem 0 Complex Complex Input Data FFT Output Q Mem 1 Mem 1 Twiddle Bit-Reversed LUT Write Addr Figure 2CoreFFT Architecture 4 v4.0 Read Switch Write Switch CoreFFT Fast Fourier Transform tree. The switch output samples are then routed to the Buffering Scheme butterfly P and Q inputs. Table 3 shows a 16-point FFT The CoreFFT module has one radix-2 butterfly, two input example of how Read Switch rearranges sample indices memory banks implementing a ping-pong input buffer, coming from the Mem 0 and Mem 1 of the input and one output buffer (Figure 2 on page 4). memory bank. Both of the identical memory banks can store N complex Table 3Sample Indices before and after Read Switch for samples. Each bank consists of two memory blocks, each 16-Point FFT Example of N / 2 complex words, so it can read/write two complex Input From Output samples per clock. Thus, the memory bandwidth is Mem 0 Mem 1 P Q (4 × b)bits per clock cycle. Internal logic controls the ping-pong switching between the banks so a data-source Stage 1 host only sees the buffer ready to accept new data. The 14 15 7 15 buffer not accepting data is used by the in-place FFT 67 6 14 engine as working memory. 12 13 5 13 This ping-pong buffering architecture increases the 45 4 12 efficiency of the FFT engine. While one of the two 10 11 3 11 identical ping-pong input banks is involved in current FFT computation, the other is available for the downloading 23 2 10 of the next frame of input data. As a result, the FFT 89 1 9 engine does not sit idle waiting for fresh data to fill the 01 0 8 input buffer. From the data-source host standpoint, the Stage 2 core is capable of receiving a data burst anywhere within the FFT computational period. When the module has 14 15 11 15 finished processing the current data frame and the input 10 11 10 14 buffer bank has been filled with another data frame, the 12 13 9 13 memory ping-pong banks are swapped, and the data 89 8 12 load and computation continues on the alternate 67 3 7 memory banks. 23 2 6 The last stage of the FFT computation uses an out-of- place scheme—the FFT final results are routed to the 45 1 5 output data buffer. The results appear at the FFT engine 01 0 4 output in bit-reversed order. A bit-reversed write address Stage 3 is used when writing the results to the output buffer to 14 15 13 15 restore the data to normal read address order. The last 12 13 12 14 stage results remain valid until the FFT engine is ready to store the results of the next data frame. 10 11 9 11 The CoreFFT generator also calculates the twiddle factors 89 8 10 required by the FFT algorithm. At power-up, the twiddle 67 5 7 factors generated are written to the twiddle factor 45 4 6 lookup table (Twiddle LUT). 23 1 3 01 0 2 FFT Computation Stage 4 14 15 14 15 An FFT computational cycle starts when input data is stored in the active ping-pong buffer bank and the FFT 12 13 12 13 engine has finished processing the previous N data 10 11 10 11 samples. Each memory bank comprises two bb-bit-wide 89 8 9 memories (Mem 0 and Mem 1), supplying a data 67 6 7 bandwidth of (4 × b) bits per clock cycle (two complex 45 4 5 samples per clock cycle). Even input samples D (i = 0, 2, 4, …, i N – ) are stored in Mem 0, odd samples in Mem 1. 23 2 3 The Read Switch function is used to rearrange the two 01 0 1 sample pairs read from the input bank to match the input sample order required by the DIT FFT algorithm v4.0 5 CoreFFT Fast Fourier Transform [1] The radix-2 butterfly processes the data according to the DIT algorithm, one pair of samples per clock. The Write Switch works similarly to the Read Switch, rearranging the butterfly results prior to being written back to the in-place memory bank. On the last stage of every FFT computational cycle, the results are written into the output memory buffer rather than back to the in-place memory bank. Figure 3 shows the FFT computational sequence. FFT Cycle i FFT Cycle i + 1 FFT Stages FFT Stages 1 2 3 log N 1 2 3 log N 2 2 ... ... Ping-Pong Input Buffer Ping-Pong Input Buffer Ping bank is busy. Ping bank is available for loading input data. Pong bank is available for loading input data. Pong bank is busy. Output Buffer Output Buffer Accepts Accepts Available for reading results of cycle (i – 1) Available for reading results of cycle i FFT result FFT result Figure 3FFT Computational Sequence Every FFT stage takes the minimal read sample rate to avoid FFT engine idle time is (N / 2 + L) clock cycles (N / 2 + L) (log N – 1) / N ≈ (log N – 1) / 2 clock cycles 2 2 EQ 1 EQ 4 to complete, where As a result, the minimal input and output sample rates N/2 = the number of butterflies to be required to avoid FFT engine idle time depend on the performed within a stage transform size N (Table 4). L = an implementation-specific parameter Table 4Minimal Input and Output Sample Rates representing the aggregate latency of the memory bank, switches, and butterfly. L is Transform Size Input Sample Output Sample much less than the number of butterflies N, Points Rate, Clock Cycles Rate, Clock Cycles required (N / 2) and does not depend on 256 4 3 transform size N. 512 4 4 The full FFT cycle takes 1,024 5 4 (N / 2 + L) log N clock cycles. 2 EQ 2 This time is available for the new frame of N data Finite Word Length samples to be loaded into the memory bank not involved Considerations in the current FFT computation. To provide maximum FFT engine utilization (no idle time, FFT engine full loading), The butterfly calculation involves complex multiplication, the minimal input sample rate that the host should addition, and subtraction. These operations can provide is potentially cause the butterfly data width to grow by [1], [2] two bits from input to output. At every stage of the ((N / 2 + L) log N) / N ≈ (log N) / 2 clock cycles 2 2 in-place FFT algorithm, the butterfly takes two samples EQ 3 out of the input buffer and returns two processed The host can read the output buffer during the first samples to the same buffer location. Potentially, log N – 1 stages of the next FFT computational cycle (the returning samples may have a larger data width than the 2 last stage is used to write fresh FFT results). Therefore, 6 v4.0 CoreFFT Fast Fourier Transform samples picked from the memory. Precautions must be shows the total number of bits the data loses because of taken to ensure that there are no data overflows. bit shifting in the FFT calculation. To avoid risk of overflow, one of three methods can be log N – 1 bits 2 employed: EQ 6 Input data scaling Unconditional block floating-point scaling results in the Unconditional block floating-point scaling same number of bits lost as in input data scaling. Conditional block floating-point scaling However, it produces more precise results, as the FFT engine starts with more precise input data. One way to ensure that overflow never occurs is to include enough extra sign bits, called guard bits, in the In conditional block floating-point scaling, data is shifted FFT input data. Data can grow by a maximum factor of only if bit growth actually occurs. If one or more 2.4 from butterfly input to output (two bits of growth). butterfly outputs grow, the entire block of data is shifted However, it is not possible for the data value to grow by to the right. The conditional block floating-point this maximum amount in two consecutive stages. monitor checks every butterfly output for growth. If shifting is necessary, it is performed after the entire stage The number of guard bits necessary to compensate for is complete (at the input of the next stage butterfly). This the maximum possible bit growth for an N-point FFT is technique provides the least amount of distortion (noise) log N + 1 2 caused by finite word length. EQ 5 The CoreFFT module is configured to apply conditional block floating-point scaling by default. In this mode, the For example, each of the input samples of a 256-point FFT should contain nine guard bits, leaving only seven input data is checked as well and, if necessary, downscaled by a factor of two prior to the first stage. bits for actual data. Obviously, the data bit resolution is greatly limited when using the input data scaling The user can optionally select one of the other two technique. scaling modes. To apply unconditional block floating- Another way to compensate for bit growth is to scale the point scaling, the CoreFFT configuration parameter scale needs to be set to 1. To apply input data scaling, the butterfly outputs down by a factor of two after each stage. Consequently, the final FFT results are scaled down scale configuration parameter has to take the default value of 0, and the FFT input data has to contain the by a factor of 1 / N. This approach is called unconditional block floating-point scaling. Initially, two guard bits are proper number of guard bits. Then the conditional block floating-point scaling will take no effect. included in the input data to accommodate the maximum bit growth at the very first stage. In each successive butterfly calculation, the data can grow into these guard bits. To prevent overflow in successive CoreFFT Generator Parameters stages, the guard bits are replaced before the next stage CoreFFT generates RTL code for a few selectable FFT is executed by shifting the entire block of data (all results cores that vary depending on parameters set by the user of the current stage) one bit to the right. The input data when generating the module. The core generator of an unconditional block floating-point FFT can have at supports the variations specified in Table 5. most 14 bits (1 sign bit and 13 magnitude bits). EQ 6 Table 5Core Generator Parameters Parameter Name Description Recommended Selection inv Forward/inverse FFT 0 (FFT) / 1 (IFFT) scale Unconditional block floating-point scaling 0 (conditional block floating-point) / 1 (unconditional block floating-point) points Transform size 32, 64,128, 256, 512, 1024, 2048 bits FFT engine bit width 8 to 16 PLUS fpga_family FPGA family ax (Axcelerator, RTAX-S), apa (ProASIC ), pa3 (ProASIC3) lang RTL code language vhdl, verilog v4.0 7 CoreFFT Fast Fourier Transform I/O Signal Description Figure 4 shows the CoreFFT module pinout. FFT load d_im d_re d_valid pong start y_im read_y y_re y_valid nreset y_rdy clk Figure 4CoreFFT I/O Signals The CoreFFT module I/O signal functionality is listed in Table 6. It is assumed that the module has been configured to compute an N-point FFT/IFFT. Table 6I/O Signal Description Signal Name Direction Description clk Input System clock. Active rising edge. nreset Input System asynchronous reset. Active low. d_im[b – 1:0] Input Input imaginary data bus. The imaginary part of the input complex data should be placed on this bus. Bit b – 1 is the MSB. Data are assumed to be presented in two’s-complement format. The imaginary and real parts should be supplied simultaneously. d_re[b – 1:0] Input Input real data bus. The real part of the input complex data should be placed on this bus. Bit b –1 is the MSB. Data are assumed to be presented in two’s-complement format. The imaginary and real parts should be supplied simultaneously. d_valid Input Input complex word valid. Active high. The bit accompanies valid input samples coming to input busses d_im and d_re. At any system clock interval where d_valid is active, input busses d_im and d_re are considered to present another input complex sample. load Output The FFT module input buffer accepts data. Active high. The signal is active when the input buffer (either of two banks) is ready to accept data. The signal stays active until the buffer is full. start Input FFT start signal. Active high. start is asserted to begin the transform processing or to return the module to the initial ready state. y_rdy Output FFT results ready. Active high. The signal goes active when the FFT results are ready for the host to read. It stays HIGH during host read. y_im[b – 1:0] Output Output imaginary data bus. The imaginary part of the output complex data appears on this bus. Bit b–1 is the MSB. Data are presented in two’s-complement format. The imaginary and real parts appear simultaneously. y_re[b – 1:0] Output Output real data bus. The real part of the output complex data appears on this bus. Bit b –1 is the MSB. Data are presented in two’s-complement format. The imaginary and real parts appear simultaneously. 8 v4.0 CoreFFT Fast Fourier Transform Table 6I/O Signal Description (continued) Signal Name Direction Description y_valid Output Output complex word valid. Active high. The bit accompanies valid output samples on output busses y_im and y_re. At any system clock interval while y_valid is active, a complex sample is available on output busses d_im and d_re. read_y Input Read FFT output. Active high. If the signal is active, the module puts out the FFT results in a single burst, one complex word per clock cycle. The host can insert arbitrary breaks into the burst by deactivating the signal any time during the burst. pong Output Pong bank of the input buffer is being used by the FFT engine as a working memory. I/O Interface and Timing buffer. The CoreFFT module puts out the post-processed Resetting the Module complex samples on the two b-bit busses, y_im and y_re. Upon reset, the module returns to its initial state with Every valid complex sample is accompanied by a y_valid input and output buffer pointers reset to zero. The input bit. In the basic mode where the host does not control buffer is now ready to accept a new data frame; signal the FFT output data rate (signal read_y remains load is asserted, and signals y_rdy and y_valid are permanently active), all N post-processed complex deasserted. Both nreset and start reset the module. samples from a single burst are available consecutively at each rising system clock edge (Figure6 on page10). During this mode, y_valid remains valid for N system Loading Input Data clock cycles. Input data can be loaded once the signal load is The host can control the FFT output sample rate via the asserted; otherwise, the module ignores any activity on read_y signal. The input read_y acts similarly to an the data loading pins. When the host detects an active output clock enable signal: when held HIGH, the module load signal, it may begin writing data via the b-bit will continue generating FFT results at each clock edge; busses d_im and d_re. Every valid complex sample must when held LOW, the module will pause in generating. be accompanied by an active d_valid signal (Figure 5 on An example of a controlled output rate mode is depicted page 10). The module samples d_valid at each rising in Figure 7 on page 10. Every new output sample is valid edge of the system clock. Once an active d_valid signal is for two system clock cycles, as read_y is asserted only detected, the core assumes a new complex sample has every other clock cycle. (Note that there is latency of one been written to the input busses. The module then clock cycle between the signal read_y and a valid sample writes the new sample to the input buffer. By the next output). system clock edge, the module is ready to accept another input sample. The host can control the input sample rate The CoreFFT module design does not place any via d_valid. Once the module has received N complex restrictions on the duty cycle of the read_y signal. samples, the input buffer is now full, and the module However, for the FFT engine to operate at maximum deasserts the signal load. efficiency (i.e., no idle time), the post-processed results must be read out of the output buffer before the engine needs to write the results of the next data frame (this Reading Output Data time is marked as Accept FFT Result in Figure3 on Once the FFT engine completes another FFT page 6). Table 4 on page 6 shows the minimal output computational cycle, it asserts the y_rdy signal. The FFT reading rate that does not impact the efficient use of the results are now available for the host in the output FFT engine. v4.0 9 CoreFFT Fast Fourier Transform clk load d_valid don’t don’t don’t don’t d_im, d_re 0 1 25 3 4 N–4 N–3 N–2 N–1 care care care care samples Figure 5Data Load Timing clk y_rdy read_y y_valid y_im, y_re 4 N–1 0 1 2 3 5 N–4 N–3 N–2 samples Figure 6FFT Results Output clk y_rdy read_y y_valid y_im, y_re 0 2 N–2 1 N–1 N samples Figure 7Host Controls the Output Sample Rate 10 v4.0 CoreFFT Fast Fourier Transform References Ordering Information 1. L. R. Rabiner and B. Gold, Theory and Application of Order CoreFFT through your local Actel sales Digital Signal Processing, Prentice Hall, 1975. representative. Use the following numbering convention when ordering: CoreFFT-XX, where XX is listed in Table 7. 2. Alan V. Oppenheim and Ronald W. Schafer with John R. Buck, Discrete-Time Signal Processing, Second Edition, Table 7Ordering Codes Prentice Hall, 1998. XX Description EV Evaluation version A Sample Configuration File AR RTL for unlimited use on Actel devices The following is an example configuration file: UR RTL for unlimited use and not restricted to Actel devices inv 0 scale 0 points 256 bits 16 fpga_family pa3 lang verilog v4.0 11 CoreFFT Fast Fourier Transform Appendix I: Fast Fourier Transform The FFT is a computationally efficient algorithm for computing a discrete Fourier transform (DFT). The N-point DFT is defined as N1 – () –jnk2π ⁄ N Xk ()≡ xn[]e k = 0, 1, 2, ..., N – 1 ∑ n0 = EQ 7 where N is the transform size, or number of points. The inverse N-point DFT is defined as N1 – 1 () jnk2π ⁄ N ⎛⎞ --- - xn() = Xk[]e k = 1, 2, 3, ..., N – 1 ∑ ⎝⎠ N k0 = EQ 8 It is common practice to call the exponential vector rotating factors above the "twiddle factors." Every twiddle factor contains real and imaginary parts () –jnk2π ⁄ N WW == – jW e r i EQ 9 P = P + jP r i outP = outP + j × outP r i Q = Q + jQ outQ = outQ + j × outQ r i r i -1 W = W + jW r i Figure 8Radix-2 DIT Butterfly The butterfly performs the basic FFT computation By substituting the values from EQ 12 and expressing P according to the following equations: and Q in terms of their real and imaginary parts, EQ 10 and EQ 11 become outP = P + Q × W outP = P + jP + (Q cos X + Q sin X) + j(Q cos X – Q sin X) r i r i i r EQ 10 = (P + Q cos X + Q sin X) + j(P + Q cos X – Q sin X) r r i i i r outP = P – Q × W EQ 13 EQ 11 outQ = P + jP – (Q cos X + Q sin X) – j(Q cos X – Q sin X) r i r i i r The twiddle factor can be expressed as = (P – Q cos X – Q sin X) + j(P – Q cos X + Q sin X) r r i i i r W = cos X – j sin X EQ 14 EQ 12 12 v4.0 CoreFFT Fast Fourier Transform Figure 9 depicts an example of an 8-point FFT algorithm. The tree contains log 8=3 stages with 8 / 2 = 4 butterflies 2 calculated at every stage. xe[0] x[0] x[0] m 0 0 W W xe[1] x[1] x[4] –1 2 1 W W xe[2] x[2] x[2] m 4 W 2 W xe[3] x[3] x[6] –1 6 3 W W xo[0] x[4] x[1] 4 0 W W xo[1] x[5] x[3] –1 2 5 W W xo[2] x[6] x[5] 4 6 W W xo[3] x[7] x[7] –1 6 7 W W Figure 98-Point FFT Using Decimation-in-Time Algorithm v4.0 13 CoreFFT Fast Fourier Transform List of Changes The following table lists critical changes that were made in the current version of the document. Previous Version Changes in Current Version (v4.0) Page v3.0 Fusion was removed from the "Targeted Devices" section. 1 The "Synthesis and Simulation Support" section was updated. 1 FFT size expanded to include 32-, 64-, 128-, and 2,048-point transforms. 1 Input/output data width changed to 8- to 16-bit (configurable). 1 All input and output data widths throughout document now expressed in terms of configurable bit N/A width b = 8 to 16 bits. Table 1 replaced with Table 1 and Table 2. 3–4 EQ 4 was revised. 6 Table 5 updated: removed module_name parameter, added bits parameter, updated points and 7 fpga_family parameters. Updated the sample in the "A Sample Configuration File" section. 11 v2.0 The "Targeted Devices" section was updated to include Fusion. 1 Table 1 (now Table 1 and Table 2) was updated to include Fusion data. 3 Datasheet Categories In order to provide the latest information to designers, some datasheets are published before the data has been fully characterized. Datasheets are designated as "Product Brief," "Advanced," and "Production." The definitions of these categories are as follows: Product Brief The product brief is a summarized version of an advanced or production datasheet containing general product information. This brief summarizes specific device and family information for unreleased products. Advanced This datasheet version contains initial estimated information based on simulation, other products, devices, or speed grades. This information can be used as estimates, but not for production. Unmarked (production) This datasheet version contains information that is considered to be final. 14 v4.0 Actel and the Actel logo are registered trademarks of Actel Corporation. All other trademarks are the property of their owners. www.actel.com Actel Corporation Actel Europe Ltd. Actel Japan Actel Hong Kong www.jp.actel.com www.actel.com.cn 2061 Stierlin Court Dunlop House, Riverside Way EXOS Ebisu Bldg. 4F Suite 2114, Two Pacific Place Mountain View, CA Camberley, Surrey GU15 3YL 1-24-14 Ebisu Shibuya-ku 88 Queensway, Admiralty 94043-4655 USA United Kingdom Tokyo 150 Japan Hong Kong Phone 650.318.4200 Phone +44 (0) 1276 401 450 Phone +81.03.3445.7671 Phone +852 2185 6460 Fax 650.318.4600 Fax +44 (0) 1276 401 490 Fax +81.03.3445.7668 Fax +852 2185 6488 51700058-2/5.07