at40k-fft ATMEL Corporation, at40k-fft Datasheet - Page 3

• Manufacturer Part Number: at40k-fft
• Description: Fast Fourier Transform Intellectual Property Core At40k Fpgas
• Manufacturer: ATMEL Corporation

Interfacing requirements are likely to be highly application
specific. The FFT processor has therefore been designed
so that users may readily customize the data IO interface to
meet their requirements. Two examples of likely interfacing
scenarios are depicted in Figure 2 and Figure 3. In the first,
the processor is used to perform transforms on real time
data generated by a pair of ADC’s. This data can either be
buffered with a FIFO, or be fed directly into the processor,
depending on whether “end to end” transforms are required
or not. The results from the FFT processor are then read
out to a microprocessor for further processing. In the sec-
ond scenario both the input and output ports of the FFT
processor are mapped into the memory space of a micro-
processor. In this configuration the FFT processor can be
used as a co-processor to the microprocessor.
The FFT processor uses fractional 12-bit fixed point arith-
metic. To prevent internal overflows occurring the proces-
sor scales all intermediate results by ½, thus for a 256 point
transform the output data is scaled by 1/256. Furthermore,
to ensure that no overflows occur, the input data must
observe the following rules:
or
where Re(Input) and Im(Input) are the real and imaginary
components of the input data.
Detailed Design Description
The architecture of the design is depicted in Figure 1. From
this it can be seen that the design contains the following
components.
• Butterfly
• Twiddle factor ROM
• Data RAM
• Address generators
• Controller
The design of each of these components is discussed in
turn, starting with the butterfly. Following this the design
entry, layout and simulation strategies are described. For
|Re(Input)+jIm(Input)| < 1
-1 Re(Input)<1, Im(Input)=0
further information on the design the reader is referred to
the design source files, especially the schematics.
The reader is assumed to be familiar with the various FFT
algorithms and their classification. General background
information on the FFT algorithm can be found in [1], [2]
and [3]. Information on hardware implementations of the
FFT can be found in [4].
Butterfly
This function implements the radix-2 decimation in fre-
quency butterfly described by the following equations:
where A and B are the complex inputs to the butterfly, A’
and B’ are the complex outputs and W
twiddle factor. The divide by two is not normally found in
the butterfly equation, but is included here to prevent
numeric overflow in the fixed point implementation.
Analysis of this function indicates that it requires the follow-
ing logical operations.
• 2 complex data fetches
• 2 complex data stores
• 1 complex twiddle factor fetch
• 1 complex addition (2 signed adders)
• 1 complex subtraction (2 signed subtracters)
• 1 complex multiply (4 signed multipliers and 3 signed
Unfortunately it is impossible to execute all these functions
in a single cycle for the following two reasons. Firstly, the
dual ported memory bank is incapable of supporting more
than 1 data write and 1 data read per cycle, and secondly
the implementation of 4 medium precision array multipliers
would exceed the logic resources of a single AT40K FPGA.
These problems can be overcome if the butterfly calcula-
tion is performed over two clock cycles. This balances the
memory and butterfly IO requirements and also halves the
number of multipliers required, permitting the design to fit
on a single chip.
adders)
A’=(A+B)/2
B’=(A-B)xW
T
/2
T
is the complex
3