2009 International Conference on Advances in Recent Technologies in Communication and Computing

VHDL implementation of FFT/IFFT Blocks for OFDM

Harpreet Kaur
VLSI-ES Division, Centre for development of Advanced computing (CDAC),Mohali

Mandeep singh
DEC Division, Centre for development of Advanced computing (CDAC),Mohali

Balwinder Singh
VLSI-ES Division, Centre for development of Advanced computing (CDAC),Mohali balwinder_cdacmohali @yahoo.com

Abstract In many applications high-speed performance is required. For this purpose, conventional multi-carrier techniques are usually chosen, but this results in the lowering of spectrum efficiency. So, the principles of Orthogonal Frequency Division Multiplexing are used in such applications. This paper gives the details of the development of IFFT & FFT algorithms to be used in OFDM systems based on the IEEE 802.11a standard for WLAN. This system consists of separate OFDM transmitter & receiver. Actually, in the entire architecture of OFDM system, all the mathematical manipulations take place in these two blocks only, i.e. IFFT & FFT blocks while rest of the blocks convert the data from one format to another format. In this paper we have implemented FFT and IFFT blocks in VHDL. The speed enhancement is the key contribution of the main processing blocks in OFDM system. KeywordsFFT, IFFT, OFDM VHDL Simulation

synchronisation error is caused by misalignment in subcarrier frequencies owing to fluctuations in transmit receive RF oscillators or channel Doppler frequency. This frequency offset can destroy the subcarrier orthogonality introducing intercarrier-interference (ICI). The time synchronization error refers to the incorrect timing of OFDM blocks at the receiver introducing possible inter-block interference (IBI). Both ICI and IBI degrade the bit-error rate (BER) performance of OFDM systems [7]. The conventional OFDM uses a cyclicprefix (CP) as a guard interval between OFDM blocks. The CP basically absorbs the channel delay-spread and any block timing error at the receiver avoiding IBI and ICI. Also, CPOFDM provides easy per subcarrier equalisation in fading channels II. THEORETICAL INFORMATION

I.

INTRODUCTION

Orthogonal Frequency Division Multiplexing (OFDM) has recently become a key modulation technique for both broadband wireless and wire-line applications [1], [2]. It has been adopted for digital audio broadcasting (DAB) and digital terrestrial television broadcasting (DVB) [3]. OFDM has also been advocated for digital subscriber loop (DSL) and wireless local area network (WLAN) applications [1],[ 4]. OFDM, also known as multicarrier modulation (MCM), incorporates a large number of orthogonally selected carriers to transmit a highdata-rate stream in a parallel form in the frequency domain. The problem of intersymbol- interference (ISI) introduced by a multipath channel (this limits the bit rate of a conventional single carrier system), is significantly reduced in OFDM owing to the parallel, i.e. relatively low rate, data transmission through multiple carriers. Also, the orthogonal nature of the sub carriers in OFDM allows the sub carrier spectra to be densely packed in the frequency domain resulting in a high spectral efficiency. Spectral efficiency and multipath immunity are two major features of OFDM. A major drawback of OFDM is its relatively high sensitivity to frequency and time synchronisation error, compared to a single carrier system [5], [6]. Frequency
978-0-7695-3845-7/09 $26.00 $25.00 2009 IEEE DOI 10.1109/ARTCom.2009.140 186

In this Section, a brief overview of IFFT and FFT algorithms is provided to be efficiently used in OFDM systems. Specific attention is given to the decimation in frequency (DIF) algorithm, which has been used to calculate the outputs of both. Generally, we can use decimation in time (DIT) algorithm also for the calculation. It depends upon the choice of the programmer whether to use DIT or DIF as per his convenience. FFT and IFFT algorithms are based on a specific mathematical equations array. Certain data that are being obtained from a signal are replaced in these equations to count DFTs and owing to these equations; processes are counted very fast than normal DFT equations. A. Fast Fourier Transform The Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT) are derived from the main function, which is called Discrete Fourier Transform (DFT). In DFT, the computation for N-points of the DFT will be calculated one by one for each point. While for FFT/IFFT, the computation is done simultaneously and this method saves quite a lot of time. The equations for FFT/IFFT function can be derived from the general DFT equation 1.

Authorized licensed use limited to: RMIT University. Downloaded on August 03,2010 at 09:08:28 UTC from IEEE Xplore. Restrictions apply.

X(k) =

(1)

twiddle factor value before being processed into the nest stage. This operation is done concurrently and is known as butterfly process. B. Inverse Fast Fourier Transform Inverse Fast Fourier Transform (IFFT) is used to generate OFDM symbols. IFFT converts signals from frequency domain to time domain and is used in transmitter to handle this process of conversion. IFFT is defined as the equation below= 1/N (6)

X(k) represents the DFT frequency output at the k-the spectral point where k ranges from 0 to (N-1). The quantity N represents the number of sample points in the DFT data frame. The quantity x(n) represents the n-th time sample, where n also ranges from 0 to N-1. In general equation, x(n) can be real or complex.The DFT equation can be re-written into: X(k) = The quantity can be defined as : = (3) (2)

For decimation in frequency radix-2, the input is separated into two halves which is: x(0),x(1),x(2)x(N/2-1) and x(N/2),x(N/2+1),.x(N-1) Thus, the DFT also can be separated into two summations and Substituting k = 2k for even and k = 2k + 1 for odd, the equation become asX(2k)= [ + ] (4)

Comparing this equation with the equation (2)., it is clear that the The changes that have been incorporated in the IFFT equation are by adding a scaling factor of 1/N and replacing twiddle factor value with the complex conjugate to the equation (2). With these changes, the same FFT flow graph also can be used for the Inverse fast Fourier Transform. C. Decimation-in-frequency (DIF) FFT algorithm In the decimation-in-frequency algorithm, the output or frequency points are re-grouped or subdivided. X(2r)= X(2r+1)= + + (7) (8)

k = 0,1,2.(N/2-1) and X(2k+1)= [

The above two equations are recognized as (N/2)-point DFT. The (N/2)-point DFT can be subdivided until only two points are left in each DFT. The resulting flow graph for this method for 8-point data is shown in Figure 1. Since the outputs were subdivided to obtain this algorithm, it is referred to as decimation-in-frequency (DIF) FFT algorithm. The table shows reduction in the number of multiplication & addition steps involved in IFFT & FFT as compared to the direct computation of DFT.
TABLE 1 COMPUTATION OF DFT IN DIRECT METHOD AND DECIMATION-INFREQUENCY ALGORITHM

k = 0,1,2.(N/2-1)

(5)

The above equation shows that for FFT decimation in frequency radix 2, the input can be grouped into odd and even number. Thus, graphically the operation can be viewed using FFT flow graph [5].

Figure 1 8-point FFT flow graph using decimation-in-frequency (DIF).

III.

PROPOSED WORK

From this figure 1, the FFT computation is accomplished in three stages. The X(0) until X(7) variables are denoted as the input values for FFT computation and Y(0) until Y(7) are denoted as the outputs. There are two operations to complete the computation in each stage. The upward arrow will execute addition operation while downward arrow will execute subtraction operation. The subtracted value is multiplied with

We discuss the techniques, which are being used for the implementation of the IFFT & FFT algorithms using VHDL. As it is clear from the FFT flow graph that in the stage three, final computation is done and the result is sent to the variable Y(0) to Y(7). Equation in each stage is used to construct scheduling diagram. The figure 2 shows the scheduling diagram of the first stage of IFFT algorithm.

187

Authorized licensed use limited to: RMIT University. Downloaded on August 03,2010 at 09:08:28 UTC from IEEE Xplore. Restrictions apply.

Here, the real value inputs are given to the FFT blocks while all the imaginary input values are zero. We have successfully implemented the 8-point IFFT & FFT algorithms using VHDL to be used in the 802.11a architecture of OFDM transmitter & receiver. The performance of the main processing block of OFDM transceiver is upgraded by reducing the clock cycles in the above work. Following is the table of the device utilization summary of the IFFT & FFT blocksFigure 2 Scheduling Diagram of stage one of IFFT
TABLE

2 -DEVICE UTILIZATION SUMMARY OF THE IFFT & FFT Avail able FFT (% Utilization) IFFT (% Utilization )

For stage one, computation is accomplished in three clock cycles denoted as S0 to S2.The operation is much simpler compared with FFT. This is because FFT processed both real and imaginary value while IFFT only real. The result from IFFT is represented in real and imaginary value because of the multiplication of twiddle factor. Twiddle factor is a constant defined by the number of point used in this transform. This scheduling diagram is derived from the equations obtain in FFT signal flow graph. The rest of the scheduling diagrams can be sketched in the same way as shown in figure 2. Scheduling diagrams are a part of behavioral modeling and Synthesis steps to translate the algorithmic description into RTL (register transfer level) in VHDL design. IV. RESULTS & CONCLUSIONS:

Sr No.

1. 2. 3. 4. 5.

Number of Slices No. of Slice Flip Flops Number of 4 input LUTs Number of bonded IOBs Number of GCLKs

14752 29504 29504 376 24

390 517 696 242 8

2% 1% 2% 64% 33%

552 701 1010 194 6

3% 2% 3% 51% 25%

The simulation results for IFFT & FFT blocks implementations is shown in figure 3 and figure 4 .The number of clock cycles required [5] is reduced and both blocks gives the final outputs as desired.

Also, the accuracy in obtained results has been increased with the help of efficient coding in VHDL. The accuracy in results depends upon the equations obtained from the butterfly diagram and then on the correct drawing of scheduling diagrams based on these equations. V.
[1]

REFERENCES

Figure 3 Response of Fast Fourier Transform Block

Richard D.J.van NeeOFDM for wireless multimedia communicationsArtechHouse,Norwell, MA, 2000 [2] Keller, T., and Hanzo, L.: Adaptive multicarrier modulation: A convenient framework for time-frequency processing in wireless communications, Proc. IEEE, 2000 , vol 88, pp. 611642 [3] Bingham, J.A.C. ADSL, VDSL, and multicarrier modulation John Wiley & Sons, Inc., 2000 [4] Proakis, J.G,Digital Communications McGraw-Hill Series in Electrical and Computer Engineering, 2001 4th edn. [5] Loo Kah Cheng, Design of an OFDM Transmitter and Receiver using FPGA, UTM,thesis 004. [6] Alan V. Oppenheim, Ronald W. Schafer, John R. Buck, Discrete-Time Signal Processing.Prentice Hall, Second edition, pp. 646-652,1999. [7] Peter J. Ashenden, "VHDL Standards," IEEE Design and Test of Computers, vol. 18, no. 5, pp. 122-123, Sep./Oct. 2001, [8] Stefan Sjoholm and Lennart Lindh,VHDL for Designers, Prentice Hall 1997. [9] Lattice semiconducter sponsored white paper "Implementation of an OFDM Wireless Transceiverusing IP Cores on an FPGA" ,FPGA and Programmable Logic Journal,Techfocus Media Inc,2005, pages 1-13 [10] Paul A. Lynn, Wolfgang Fuerst, Introductory Digital Signal Processing with Computer Application, Second Edition, John Wiley & Sons, England, 1999.

Figure 4 Response of Inverse Fast Fourier Transform Block

188

Authorized licensed use limited to: RMIT University. Downloaded on August 03,2010 at 09:08:28 UTC from IEEE Xplore. Restrictions apply.