www.unicore.co.ua Unicore Systems Ltd. Page 2 of 17
FFT/IFFT 256 IP core
• Overflow detectors of intermediate and resulting data are present.
• Two normalizing shifter stages provide the optimum data magnitude bandwidth.
• Structure can be configured in Xilinx, Altera, Actel, Lattice FPGA devices, and ASIC.
• Can be used in OFDM modems, software defined radio, multichannel coding, wideband
spectrum analysis.
Design features
• FFT is an algorithm for the effective Discrete Fourier Transform calculation
Discrete Fourier Transform (DFT) is a fundamental digital signal processing algorithm used in
many applications, including frequency analysis and frequency domain processing. DFT is the
decomposition of a sampled signal in terms of sinusoidal (complex exponential) components. The
symmetry and periodicity properties of the DFT are exploited to significantly lower its computational
requirements. The resulting algorithms are known as Fast Fourier Transforms (FFTs). An 256-point
DFT computes a sequence x(n) of 256 complex-valued numbers given another sequence of data X(k)
of length 256 according to the formula
X(k) =
=
255
0n
x(n)
e
–j2
π
nk/256
; k = 0 to 255.
To simplify the notation, the complex-valued phase factor
e
–j2
π
nk/256
is usually defined as
W
256
n
where:
W
256
= cos(2
π
/256) – j sin(2π/256).
The FFT algorithms take advantage of the symmetry and
periodicity properties of
W
256
n
to greatly reduce the number of calculations that the DFT requires. In
an FFT implementation the real and imaginary components of
W
n
N
are called twiddle factors.
The basis of the FFT is that a DFT can be divided into smaller DFTs. In the processor
FFT256 a radix-16 FFT algorithm is used. It divides DFT into two smaller DFTs of the length 16, as it
is shown in the formula:
X(k) = X(16r+s) =
=
15
0m
W
16
mr
W
256
ms
=
15
0l
x(16l+m) W
16
sl
, r = 0 to 15, s = 0 to 15,
which shows that 256-point DFT is divided into two smaller 16-point DFTs. This algorithm is illustrated
by the graph which is shown in the Fig.1. The input complex data x(n) are represented by the 2-
dimensional array of data
x(16l+m)
. The columns of this array are computed by 16-point DFTs. The
results of them are multiplied by the twiddle factors
W
256
ms
.
And the resulting array of data
X(16r+s)
is
derived by 16-point DFTs of rows of the intermediate result array.
The 16-point DFT, named as the base FFT operation, is implemented by the Winograd small
point FFT algorithm, which provides the minimum additions and multiplications (only 10 complex