The Fast Fourier Transform in Hardware: A Tutorial Based ...

1 See discussions, stats, and author profiles for this publication at: Fast Fourier Transform in Hardware: ATutorial Based on an FPGA ImplementationArticle March 2013 CITATION1 READS12,4221 author:Some of the authors of this publication are also working on these related projects:LaRa: Doppler Transponder for Precision Martian LOD measurements View projectReluctance coilguns and linear motors View projectGeorge SladeOrban Microwave Products44 PUBLICATIONS 130 CITATIONS SEE PROFILEAll content following this page was uploaded by George Slade on 20 May user has requested enhancement of the downloaded Fast Fourier Transform in Hardware: ATutorial Based on an FPGA ImplementationG.

2 William SladeAbstractIn digital signal processing (DSP), the fast Fourier Transform (FFT) is one of the most fundamental and usefulsystem building block available to the designer. Whereas the software version of the FFT is readily implemented,the FFT in hardware ( in digital logic, field programmable gate arrays, etc.) is useful for high-speed real-time processing, but is somewhat less straightforward in its implementation. The software version is generallyconstrained to execute instructions serially (one at a time) and is therefore severely constrained by the processorinstruction throughput.

3 The hardware FFT performs many of its processing tasks in parallel, hence can achieveorder-of-magnitude throughput improvements over software FFTs executed in DSP microprocessors. Howeverstraightforward the FFT algorithm, when implementing the FFT in hardware, one needs to make use of a numberof not-so-obvious tricks to keep the size and speed of the logic on a useful, practical scale. We do not presentthis document as an exhaustive study of the hardware fouriertransform. On the other hand, we hope thet readercomes away with an understanding on how to construct a basic,but useful FFT calculator that can be the basisfor deeper study as well as future improvements and this article, we focus on the Cooley-Tukey Radix-2 FFT algorithm [6], which is highly efficient, is theeasiest to implement and is widely used in practice.

4 We review the mathematical basis of the algorithm and itssoftware implementation before launching into the description of the various system blocks needed to implementthe hardware version of the FFT. We then describe how the FFT is instantiated in a field programmable gatearray (FPGA) and used in a real system. It is hoped that by reading this document, the reader will have a goodgrasp on how to implement a hardware FFT of any power-of-two size and can add his own custom improvementsand INTRODUCTIONA. The DFT: Discrete Fourier TransformThe DFT is a linear transformation of the vectorxn(the time domain signal samples) to the vectorXm(theset of coefficients of component sinusoids of time domain signal) usingXm=N 1Xn=0xnwnm,(1)whereNis the size of the vectors,w=e2i /Nare the roots-of-unity (twiddle factors), and0 m < N.

5 Abrute-force summation requires on the order ofN2operations to compute. This rapidly becomes intractible asthe number of samples becomes large. A very useful strategy is to recursively split the summation like this:Xm=N/2 1Xn=0xnwnm+wmN/2N/2 1Xn=0xn+N/2wnm,(2)Author can be reached 21, 2013 DRAFT1or, like this:Xm=N/2 1Xn=0x2nw2nm+wmN/2 1Xn=0x2n+1w2nm.(3)We see immediately that in both cases, that any DFT can be constructed from the sum of two smaller implies that we can attack the problem using the divideand conquer approach. The summation is appliedrecursively to ever-smaller groups of sample data providing us with an algorithm whose computational cost isproportional toNlog2N; a substantial savings in effort!

6 As a result, we must work with vector sizes that arepowers-of-two. (In reality, it is not much of a drawback if we pad unused samples with zeros.)We note that there are different ways to partition the summations. We have shown two of the most popularmethods in (2) and (3). The expression in (2) represents the so-called decimation-in-frequency (DIF) split,whereas (3) is the decimation in time (DIT) split. It is the DIT form of the FFT that we concentrate on in is worth mentioning that other splits and ordering methods exist. The Winograd algorithm, for example,uses a special ordering to reduce the need for complex multiplications [1], [2].

7 Other algorithms rely on theChinese Remainder Theorem (Prime-factor algorithm [4]). The Cyclic Convolution Method [3] can also handleprime or nearly prime vector sizes. Yet another elegant trick for carrying out the Fourier Transform if theChirp-z algorithm [5]. These methods each have their advantages and disadvantages. The mathematical basisof these alternative methods is often very elegant, but the ordering methods are usually not so obvious to thebeginner wishing to implement a Fourier Transform on his/her FPGA demo board. Moreover, it is difficult tobeat the simplicity and speed of the power-of-two divide-and-conquer methods.

8 For this reason, we focus onthe Cooley-Tukey method and refer any interested readers tothe papers in the list of us consider the DFT acting on a vector of size 8 to illustrate how the algorithm is formed. We write outthe summations forXmexpanding the powers ofwin matrix form: X0X1X2X3X4X5X6X7 = 1 1 1111111ww2w3w4w5w6w71w2w4w6w8w10w12w141w 3w6w9w12w15w18w211w4w8w12w16w20w24w281w5 w10w15w20w25w30w351w6w12w18w24w30w36w421 w7w14w21w28w35w42w49 x0x1x2x3x4x5x6x7 (4)Now, let us reorder the matrix according to the DIT split in (3), separating the even and odd index samples,March 21, 2013 DRAFT2viz.

9 : X0X1X2X3X4X5X6X7 = 1 1111 1111w2w4w6ww3w5w71w4w8w12w2w6w10w141w6w1 2w18w3w9w15w211w8w16w24w4w12w20w281w10w2 0w30w5w15w25w351w12w24w36w6w18w30w421w14 w28w42w7w21w35w49 x0x2x4x6x1x3x5x7 (5)Let us do the same reordering confined to each 4x4 block to yield: X0X1X2X3X4X5X6X7 = 1 1111 1111w4w2w6ww5w3w71w8w4w12w2w10w6w141w12w 6w18w3w15w9w211w16w8w24w4w20w12w281w20w1 0w30w5w25w15w351w24w12w36w6w30w18w421w28 w14w42w7w35w21w49 x0x4x2x6x1x5x3x7 (6)We are now closing in on the point where the FFT magic beginsto happen. We now invoke the symmetriesin the powers ofw, the roots-of-unity. Namely,wn=wn+Nk, N= 8, k= 0,1,2, (7)wn= wn+N/2(8)wNk= 1.

10 (9)We now rewrite (6) as X0X1X2X3X4X5X6X7 = 1 11111111 1w2 w2w ww3 w31 1 1 1w2w2 w2 w21 1 w2w2w3 w3w w1 111 1 1 1 11 1w2 w2 ww w3w31 1 1 1 w2 w2w2w21 1 w2w2 w3w3 ww x0x4x2x6x1x5x3x7 (10)After this rearrangement, we notice that we do not need all the powers ofwup to 7. We need store onlyMarch 21, 2013 DRAFT3 TABLE IILLUS TRATI ON OF THE BI T-REVERS ED I NDI reversed indexbinary00000000100141002010201030116 11041001001510151016110301171117111those up to 3, because of the sign symmetry ofw. Furthermore, the DFT of a two point data set is simply X0X1 = 1 11 1 x0x1 .(11)Taking a close look at the ordering if thexvector, we notice that if we represent the indices as binarynumbers, they correspond to thebit reversedrepresentation of the original indices.