Joshi* , Gupta** , and Jaipuriyar**: Implementation of Low Complexity FFT, ADC and DAC Blocks of an OFDM Transmitter Receiver Using Verilog

# Implementation of Low Complexity FFT, ADC and DAC Blocks of an OFDM Transmitter Receiver Using Verilog

Keywords: ADC , DAC , DFT , FFT , OFDM , Verilog

## 1. Introduction

##### 1.2 Fast Fourier Transform

The fast Fourier transform (FFT) and inverse FFT (IFFT) blocks are used for modulation and demodulation in an OFDM system. In this paper, we have implemented the FFT block using Verilog, outputs of which have been compared to the same blocks designed using MATLAB to verify the designs and check the efficiency of the used algorithms.

Discrete Fourier transform (DFT) is a difficult process with a time complexity of an order of O(n2). To implement DFT on hardware is itself a very complex task. FFT has a large range of applications in the telecom domain. Thus, engineers have put in great effort in this field to achieve a real-time hardware implementation of FFT. Different algorithms have been developed in recent years to achieve an efficient implementation of FFT which include split radix algorithm, twisted radix algorithm, parallel FFT, mixed radix algorithm, and vector radix algorithm.

Cooley and Tukey proposed an FFT algorithm which is used to divide the complex DFT into the smaller DFTs with multiplication by twiddle factors. Dividing the DFT in smaller DFTs reduce the time complexity thus increasing efficiency. The general equation for the DFT is given by:

##### (1)
[TeX:] $$Z(k)=\sum_{m=0}^{M-1} z(m) e^{-j\left(\frac{2 \pi}{N}\right) m k}$$

The FFT problem gets decimated by two units in time in radix-2 implementation. Much has been proposed to implement FFT/IFFT efficiently. The main aim was to reduce time, calculations and increase accuracy. A paper published in 2015 [3] a pure design in VHDL was implemented, integrated with IP blocks using XILINX ISE 14.2. The modulator was implemented using 16-QAM in which different bit combinations were converted into corresponding constellation values. In demodulator, care was taken for the values like 2.999 to take it as 3 instead of 2. Fatima [4] designed FFT for 32-point using radix-2 using a smaller number of slices and computations.

In 2010, Merlyn [5] implemented a prototype FFT/IFFT processor which has a variable length to cover different specifications of OFDM applications. In this, they proposed a programmable MDC (mixedradix FFT processor). An extension was made in the binary number while implementing through butterfly structure to avoid overflow danger.

In 2014, a paper published on design of a high-speed OFDM transmitter and receiver [6] analyzed 8- point IFFT/FFT with the radix-2 algorithm. These FFT and IFFT are pass modules, i.e., from Path0 to Path7. Complexity increases as the complex number come to these paths.

Mehta [7] had implemented 512-point IFFT and 512-point FFT blocks using radix-2. In this proposed work, the number of multipliers is reduced using an adder circuit and inter-carrier interface (ICI) selfcancellation techniques which can improve the performance parameters.

A paper issued in 2013, Palekar and Ingole [8] proposed to use efficient multiplication technique to reduce the partial product in FFT/IFFT which used to happen in conventional multiplication technique. A 32-point FFT and IFFT blocks for OFDM by using VEDIC multiplication was coded in VHDL and was synthesized using XILINX ISE software. The speed performance of this design easily satisfies most application requirements. In 2015, Sharma and Singh [9] carry out the same work efficiently using better resource utilization parameter.

To study the effect of various design parameters on the system performance OFDM system using MATLAB program was simulated [10]]. It was observed that the optimum length of FFT/IFFT was 1024 points with the fixed signal-to-noise ratio (SNR) and the best SNR (fixed) was 60 dB and after this value, there was no effect on varying the SNR value.

A significant method to improve radix-2 and radix-4 algorithm was proposed in 2004. It was indexing the output samples again once the output comes from traditional algorithms which save effort while evaluating twiddle factor or accessing lookup table [11]. Later Rao et al. [12] used the same strategy efficiently while calculating 32-point DIT FFT. Mahajan and Chitode [13] implemented novel 16-point DIT FFT using radix-2 based on 8-point FFT. Ramachandran and Vanmathi [14] implemented the design of 32-bit radix-2 DIT in FPGA Spartan 3E using fewer computations as the output of shorter FFTs were used while computing the final output.

Direct computation requires almost 4N multiplications and 4N additions for every value of k. it is computed by implementing:

##### (2)
[TeX:] $$Z(k)=\sum_{m=0}^{M-1} z(m) W_{M}^{k m} \quad k=0,1,2 . . M-1$$

where

##### (3)
[TeX:] $$W_{M}^{m}=e^{-j\left(\frac{2 \pi}{M}\right) m}$$

The same formula has been implemented which shows that this algorithm is slow and requires many computations. Its time complexity is [TeX:] $$O\left(n^{2}\right)$$. Results are shown for 4-point FFT in Fig. 1. In Fig. 1, ‘o_re’ and ‘o_im’ are the real and imaginary outputs of the FFT function, respectively.

Fig. 1.

Simulation result of 4-point FFT on ModelSim (Wave Window).

Table 1.

Comparison of calculations between direct summation method and radix-2 method for 16-point FFT
Number of subtractions 32 -
Number of Multiplications 32 256
Total number of calculations 96 512

It is later implemented using radix-2 algorithms which have better efficiency and time complexity. The comparison has been shown in Table 1.

ADC and DAC is an essential block in OFDM used in receiver and transmitter respectively. DAC is used in OFDM as after the application of IFFT (can apply only on digital data) in transmitter block the signal is transmitted. And the transmission medium is air thus it is required to convert the digital data obtained from the previous block to analog signal. Similarly, the ADC block is used after the FFT block in the receiver.

Many designs were modeled and simulated like Generic ADC and DAC, flash ADC, SAR (successive approximation register ADC), pipelined ADC, etc. Suarez [15] in “Behavioral Modeling of Data Converters using Verilog” had stated that these ADCs are modeled using transistor level modeling which can be useful up to 16-bits but for higher bits the model becomes a lot complex making the design impractical. In generic ADC, there is a mismatch between ADC units which are later removed using dynamic element match (DEM).

Flash ADC is designed using high-speed comparator in a cascade fashion. It can be used up to 8-bit resolution because for higher resolution the design becomes complex and consumes more power, but these are ideal for devices requiring large bandwidth.

An ADC (N bits) requires N comparison periods as it starts the next conversion only after the previous one is complete. Pipelined ADC is most popular ADC architecture with the resolution of fewer bits at faster sample rates and of more bits at the lower rates. Ashraf [16] in 2016 designed an 8-bit SAR ADC with an input voltage of 1.2-V. The SAR control logic was designed asynchronously using Verilog coding. The design was implemented in Cadence Virtuoso using 1.8-nm technology. Designing of low power comparator was achieved which results in overall power consumption of 0.75 mW.

A 10-bit DAC with (6+4) bit segmentation was designed in 2006 by Murali Shanmugasundaram and Shanthi Pavan [17]. The simulations run on full transistor level schematic as well as on the macro design over a range of frequencies. This design uses current controlled current sources which is time-varying in nature and thus reduces the simulation time and increases simulation speed. It was implemented in a 0.35um CMOS process. In 2015, Santhanalakshmi and Yashoda [18] also designed a low power SAR ADC using Verilog-A and proved that bypass window technique is more efficient with a lesser number of transitions, i.e., 3 over 4.

Menzter and Wey [19] developed a mixed signal model of a 10-bit pipelined ADC using Verilog. The overall aim of this project was to identify design flaws based on input/output tests. Implementation of FIR filter was done using onboard ADC-DAC and FPGA.

To optimize design and computations it was also modeled using MATLAB and Simulink [20]. Although transistor level modeling is the most appropriate approach for mixed-signal circuits, but alternate modeling is required to avoid the complexity and long computation time.

The ADC results in a ratiometric value. Analog to digital conversions totally depend on the system voltage. Here the ADC assuming maximum voltage to be 10 V is converted to 1023 and any value less than 10 V will be a ratiometric value correspondingly after quantization.

## 2. Proposed Work

##### 2.1 Fast Fourier Transform

Fig. 2 illustrates the butterfly structures of radix-2 for 16-point. The basic butterfly structure is implemented in the design of 16-point FFT.

Fig. 2.

The radix-2 is computed by dividing the Eq. (2) into odd and even terms as mentioned,

##### (4)
[TeX:] $$Z(k)=\sum_{m=e v e n} z(m) W_{M}^{k n}+\sum_{m=o d d} z(m) W_{M}^{k m}$$

##### (5)
[TeX:] $$=\sum_{m=0}^{M / 2-1} z(2 m) e^{-\frac{2 \pi}{M}(2 m) k}+\sum_{m=0}^{M / 2-1} z(2 m+1) e^{-\frac{2 \pi}{M}(2 m+1) k} ; \quad\left(m=0,1,2, \ldots, \frac{M}{2}-1\right)$$

##### (6)
[TeX:] $$\begin{array}{ll}{\text { Let }} & {f_{1}(m)=z(2 m)} \\ {} & {f_{2}(m)=z(2 m+1)}\end{array}\ \left(m=0,1,2, \ldots, \frac{M}{2}-1\right)$$

But [TeX:] $$W_{M}^{2}=W_{M / 2}$$. Using this substitution, the above equation becomes:

##### (7)
[TeX:] $$Z(k)=\sum_{m=0}^{M / 2-1} f_{1}(m) W_{M / 2}^{k m}+W_{M}^{k} \sum_{m=0}^{M / 2-1} f_{2}(m) W_{M / 2}^{k m}$$

##### (8)
[TeX:] $$Z(k)=F_{1}(k)+W_{M}^{k} F_{2}(k) \quad k=0,1,2 \ldots M-1$$

Where

##### (9)
[TeX:] $$F_{1}(k)=D F T\left\{f_{1}(m)\right\}$$

and

##### (10)
[TeX:] $$F_{1}(k)=D F T\left\{f_{1}(m)\right\}$$

##### (11)
[TeX:] $$F_{1}(k+M / 2)=F_{1}(k)$$

and

##### (12)
[TeX:] $$F_{2}(k+M / 2)=F_{2}(k)$$

It implies F1 (k) and F2 (k) are periodic, with M/2 period.

##### (13)
[TeX:] $$W_{M}^{k+M / 2}=-W_{M}^{k}$$

Hence,

##### (14)
[TeX:] $$Z(k)=F_{1}(k)+W_{M}^{k} F_{2}(k) \quad k=0,1,2 \ldots M-1$$

##### (15)
[TeX:] $$Z\left(k+\frac{M}{2}\right)=F_{1}(k)-W_{M}^{k} F_{2}(k) \quad k=0,1,2 \ldots M-1$$

By using Eqs. (14) and (15) we compute radix-2 in our program.

Since the input values are complex therefore two different arrays one for real and the other for the imaginary part have been used.

The twiddle factors which are used in FFT/IFFT blocks are generated using the CORDIC algorithm. Each time while performing the calculation using butterfly structure the angle which is needed is passed to the CORDIC algorithm which gives the sine and cosine of the angle except that in the last stage. In the last stage, the twiddle factor is 1 always, therefore the direct value is saved for cosine and sine, i.e., sine of the angle is 0 and cosine of the angle is 1.

Saving the value 1 in a variable makes it easy to compute the values in the last stage which reduces time by 4 times while using the CORDIC algorithm in the fourth (last) stage of 16-point FFT. Thus, in the last stage, both the complexity as well as time taken is reduced.

The code for radix-2 written in Verilog is universal, i.e., on varying the number of data and data values the design calculates FFT itself, so this can be used for calculating any point-FFT. The output has been shown in Figs. 3–7. The final output comes at 4015 ns. But extra delays were added just for the sake of proper visibility in Fig. 7.

Fig. 3.

Simulation result of 16-point FFT on ModelSim (Wave Window) [0 ns–1200 ns].

Fig. 4.

Simulation result of 16-point FFT on ModelSim (Wave Window) [1200 ns–2300 ns].

Fig. 5.

Simulation result of 16-point FFT on ModelSim (Wave Window) [2300 ns–3500 ns].

Fig. 6.

Simulation result of 16-point FFT on ModelSim (Wave Window) [3500 ns–4000 ns].

Fig. 7.

Simulation result of 16-point FFT on ModelSim (Wave Window - last stage) [4000 ns–4150 ns].

Figs. 3–7 show the FFT simulation of 16-point input using radix-2 algorithm. The parameter a_re, a_im, b_re, and b_im are the outputs of the radix-2 butterfly structure as shown in Fig. 8.

The output result obtained from this proposed work is compared with MATLAB simulations in Fig. 9 using the same algorithm. The MATLAB simulation is used for verification of results (in Fig. 9, ‘x’ is the input variable and ‘y’ is the output variable).

Fig. 8.

Butterfly structure.

Fig. 9.

Simulation result of 16-point FFT on MATLAB (x is input and y is output).

It has been observed that the result of the design simulated using Verilog on ModelSim is almost the same as the results obtained in MATLAB. The comparisons of results of 16-point FFT using Verilog and MATLAB are mentioned in Table 2.

Table 2.

Comparison of outputs from Verilog with MATLAB for 16-point FFT
Series no. Input values Verilog outputs MATLAB output
Real part Imaginary part Real part Imaginary part
0 1+0j 78 63 78 63
1 2+2j -10.9914 29.8618 -11.1115 29.8472
2 3+5j -33.6733 -23.6722 -33.6777 -23.6777
3 5+7j 1.59562 -9.0683 1.6521 -8.9644
4 7+3j -18.9993 -3.99728 -19 -4
5 4+3j -0.735838 -35.0674 -0.656 -35.1078
6 0+1j 22.7445 -2.12186 22.7487 -2.1213
7 1+5j 15.3225 13.9488 15.1809 14.0125
8 3+4j -1.99931 4.99919 -2 5
9 2+0j -6.31809 2.55834 -6.2022 2.5792
10 9+3j 1.67653 11.6751 1.6777 11.6777
11 18+8j -23.3902 3.0728 -23.4511 2.9644
12 6+4j 10.9993 -19.9977 11 -20
13 8+2j 6.04157 -17.3395 5.9697 -17.3186
14 9+14j -26.741 2.12374 -26.7487 2.1213
15 0+2j 2.46896 -19.9476 2.618 -20.0125

The input signal is analog which takes in values from +10 V to -10 V and converts them to +1023 to - 1023 which comes as output from the digital signal. Any value greater than 10 V will be limited to its maximum valu, i.e., +1023. Similarly, any value lower than -10 V will be limited to -1023. The signal gets modulated using a carrier signal and the signal is quantized at few intervals. And the reverse procedure is used for implementing DAC. The simulation result is shown in Figs. 10 and 11. The simulation contains conversion of analog to digital values and reconstruction of digital values back to analog again.

Fig. 10.

Simulation result of ADC and DAC on ModelSim (Transcript Window).

Fig. 11.

Simulation result of ADC and DAC on ModelSim (Wave Window).

In Fig. 10, the transcript shows the input analog signal (‘analog value’), its converted digital signal (‘digital data’) and finally the reconstructed analog signal (‘reconstructed value’) from digital data. Fig. 11 shows the wave simulation (‘c’ is the input analog signal, ‘result_r’ is converted digital signal and ‘result’ is the reconstructed analog signal.).

## 3. Conclusion and Future Scope

Nowadays OFDM is an important technology that supports the latest standards of wireless communication. To achieve high data rate, we use OFDM in LTE, WiMAX and WLAN, etc. The main modules of an OFDM system, i.e., the FFT and the IFFT, A/D and D/A have been simulated successfully using radix-2 algorithm and reducing the complex mathematics.

This design works better for large N (in N-point FFT) than radix-M (M>2) because the number of multiplications, addition and subtraction is equal to one in radix-2 while the number of multiplications is more in others thus leading to a more complex design. Also, the last stage of the design is much more time efficient than the existing designs (since the time taken is optimized in the last stage).

For A/D and D/A systems, we implemented the architecture using some common algorithms which include simple mathematics reducing its complexity. The proposed FFT design is both speed and time efficient. It is a method in which the resources have been used in an optimized way.

The high data rate requirement in wireless communication has increased exponentially lately. In this paper, we take a review on the traditional concept in terms of its disadvantages and advantages and have tried to improve them. The future networks will continue to rely on OFDM/OFDMA for satisfying its need.

## Biography

##### Alok Joshi
https://orcid.org/0000-0002-5332-0740

He has received B.E. degree in Electronics and Communication Engineering from G.B. Pant Enggineering College (Hemvati Nandan Bahuguna Garhwal University), Uttarakhand, India in 2001 and M.Tech. in Digital Communication from Uttar Pradesh Technical University, Lucknow, India in 2006. He received Ph.D. degree from Jaypee University of Information Technology in 2014, in the area of wireless communications. He has total teaching experience of 15 years in various technical universities in India. Currently he is working with Jaypee Institute of Information Technology, Noida, India. His research interests are MIMO OFDM systems.

## Biography

https://orcid.org/0000-0003-3289-3889

He received his B.Tech. degree in Electronics and Communication Engineering from Jaypee Institute of Information Technology, Noida, India in 2016. He is currently working as a Software Engineer in the Synthesis domain at Cadence Design Systems, Noida. He received his B.Tech. degree in Electronics and Communication Engineering from Jaypee Institute of Information Technology, Noida, India in 2016. His interest areas include frontend optimizations and mapping algorithms. His research interest is mainly in VLSI and EDA domain.

## Biography

##### Pravriti Jaipuriyar
https://orcid.org/0000-0002-8306-9251

She received her B.Tech. degree in Electronics and Communication Engineering from Jaypee Institute of Information Technology, Noida, India in 2016. She is currently working as a Software Engineer in the Formal and IP verification domain at Cadence Design Systems, Noida. She received her B.Tech. degree in Electronics and Communication Engineering from Jaypee Institute of Information Technology, Noida, India in 2016. Her research interest is mainly in IP development and verification. Her research interest is mainly in VLSI, IP and EDA domain.

## References

• 1 M. Mohaisen, "A review of fixed-complexity vector perturbation for MU-MIMO," Journal of Information Processing Systems, vol. 11, no. 3, pp. 354-369, 2015.doi:[[[10.3745/JIPS.03.0035]]]
• 2 A. S. M. M. Rahaman, M. I. Islam, M. R. Amin, "Selection of the best two-hop AF wireless link under multiple antenna schemes over a fading channel," Journal of Information Processing Systems, vol. 11, no. 1, pp. 57-75, 2015.doi:[[[10.3745/JIPS.03.0023]]]
• 3 N. Chide, S. Deshmukh, P. B. Borole, "Implementation of OFDM system using IFFT and FFT," International Journal of Engineering Research and Applications (IJERA), vol. 3, no. 1, pp. 2009-2014, 2013.custom:[[[-]]]
• 4 A. Fatima, "Design and simulation of 32-point FFT using radix-2 algorithm," IOSR Journal of Electrical and Electronics Engineering, vol. 9, no. 1, pp. 42-50, 2014.custom:[[[-]]]
• 5 M. Merlyn, "FPGA implementation Of FFT processor with OFDM transceiver," in Proceedings of 2010 International Conference on Signal and Image Processing, Chennai, India, 2010;pp. 483-489. custom:[[[-]]]
• 6 F. Ahmed, M. L. Ali, M. I. H. B. Asad, "Design of a high speed OFDM transmitter and receiver," in Proceedings of the 8th International Conference on Electrical and Computer Engineering, Dhaka, Bangladesh, 2014;pp. 425-428. custom:[[[-]]]
• 7 K. Mehta, "High performance and area efficient correlation for IEEE 802.16 OFDM using FPGA," International Journal of Advanced Engineering and Research Development, vol. 2, no. 3, pp. 93-97, 2015.doi:[[[10.21090/ijaerd.020314]]]
• 8 A. D. Palekar, D. P. V. Ingole, "OFDM system using FFT and IFFT," International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 12, pp. 675-679, 2013.custom:[[[-]]]
• 9 H. K. Sharma, A. K. Singh, "OFDM system using FFT and IFFT," Global Journal of EngineeringScience & Social Science Studies, pp 202-208, vol. 1, no. 2, 2015.custom:[[[-]]]
• 10 M. A. Mohamed, A. S. Samarah, M. F. Allah, "Implementation of the OFDM physical layer using FPGA," International Journal of Computer Science Issues, vol. 9, no. 2, pp. 612-618, 2012.custom:[[[-]]]
• 11 S. Bouguezel, M. O. Ahmad, M. N. S. Swamy, "Improved radix-4 and radix-8 FFT algorithms," in Proceedings of 2004 IEEE International Symposium on Circuits and Systems (IEEE Cat. No. 04CH37512), V ancouver, Canada, 2004;pp. 561-564. custom:[[[-]]]
• 12 K. M. Rao, V. R. Tejesvi, G. A. Rao, "Verilog implementation of 32 point FFT using Radix-2 algorithm on FPGA technology," IOSR Journal of Electronics and Communication Engineering, vol. 9, no. 2, pp. 40-43, 2014.doi:[[[10.9790/2834-09124043]]]
• 13 N. V. Mahajan, J. S. Chitode, "Simple computation of DIT FFT," International Journal of Advanced Research in Computer Science and Software Engineering, vol. 4, no. 5, pp. 353-356, 2014.custom:[[[-]]]
• 14 R. Ramachandran, K. Vanmathi, "Simulation of radix-2 fast Fourier transform using Xilinx," International Journal of Computer Science Engineering (IJCSE), vol. 3, no. 2, pp. 125-130, 2014.custom:[[[-]]]
• 15 G. Suarez, "Behavioral Modeling of Data Converters using V erilog-A," Department of Electrical and Computer EngineeringUniversity of Puerto Rico, Mayaguez. Puerto Rico, pp. 17-19, 2014.custom:[[[-]]]
• 16 A. Ashraf, S. Ashraf, N. Z. Rizvi, S. A. Dar, "Low power design of asynchronous SAR ADC," in Proceedings of 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), Chennai, India, 2016;pp. 4214-4219. custom:[[[-]]]
• 17 M. Shanmugasundaram, S. Pavan, "Rapid simulation of current steering digital-to-analog converters using V erilog-A," in Proceedings of IEEE Custom Integrated Circuits Conference 2006, San Jose, CA, 2006;pp. 201-204. custom:[[[-]]]
• 18 M. Santhanalakshmi, K. Y asoda, "V erilog-A implementation of energy-efficient SAR ADCs for biomedical application," in Proceedings of 2015 19th International Symposium on VLSI Design and T est, Ahmedabad, India, 2015;pp. 1-6. custom:[[[-]]]
• 19 J. Mentzer, T. Wey, "A Verilog mixed signal model of a 10-bit pipeline analog-to-digital converter," in Proceedings of 2006 IEEE International Behavioral Modeling and Simulation W orkshop, San Jose, CA, 2006;pp. 115-119. custom:[[[-]]]
• 20 S. S. Pujari, P. P. Muduli, A. Panda, R. Badhai, S. Nayak, Y. Sahoo, "Design & implementation of FIR filters using on-board ADC-DAC & FPGA," in Proceedings of International Conference on Information Communication and Embedded Systems (ICICES2014), Chennai, India, pp. 1-6. custom:[[[-]]]