Cover
Vol. 14 No. 2 (2023)

Published: October 19, 2023

Pages: 19-27

Research Paper

Direct Algorithm for Computation of Inverse Real Fast Fourier Transform (IRDFT)

sukaina salih 1 mounir hamood 2
1University of Tikrit
2electrical,engineering,university of tikrit, tikrit, iraq
History
  • Received: August 26, 2023
  • Revised: October 26, 2023
  • Accepted: November 20, 2023
  • Available Online: November 15, 2023
DOI

https://doi.org/10.37649/aengs.2023.142947.1060

Abstract

This paper proposes an efficient algorithm for fast computation of the inverse real-valued discrete Fourier transform (IRDFT) using the decimation in frequency (DIF) approach. The proposed algorithm represents a direct method with a new implementation for fast computing of IRDFT. The algorithm derivation is based on the basic principles of the Cooley-Tukey algorithm with the divide and conquer approach and utilizes the advantage of conjugate symmetric property for the discrete Fourier transform (DFT) to remove all redundancies that appear when DFT deals with real data. The analyses of the proposed algorithm have shown that the arithmetic number has reached a minimum, therefore the structure of the developed algorithm possesses the desired properties such as regularity, simplicity, and in-place computation. The arithmetic complexity of this algorithm has been compared with the inverse FFT algorithm, and it was found that it needs the least number of multiplications and additions. The validity of the developed algorithm has been verified by reducing the peak-to-average power ratio PAPR in optical-OFDM systems compared with complex FFT. The simulation using MATLAB(R2021a) findings show that the RFFT O-OFDM system reduces PAPR more efficiently than the FFT O-OFDM system. The PAPR exhibits a reduction of approximately 2.4 to 2.75 dB when evaluated at a probability of occurrence of 10-1 in the complementary cumulative distribution function (CCDF) plot.

Keywords

References

  1. Takahashi and D. Takahashi, "Fast fourier transform," Fast Fourier Transform Algorithms for Parallel Computers, vol. 2, 2019, pp. 5-13.
  2. Plewa, "A new form of discrete real Fourier transform and its potential applications," Ann Math Phys, vol. 2, no. 5, pp. 160-166, Nov. 2022, doi: 10.17352/amp.000060
  3. Khayyeri and K. Mohammadi, "Cooperative wideband spectrum sensing in cognitive radio based on sparse real‐valued fast fourier transform," IET Communications, vol. 14, no. 8, pp. 1340-1348, May. 2020, doi:10.1049/iet-com.2018.5930
  4. Roienko, V. Lukin, V. Oliinyk, I. Djurović, and M. Simeunović, "An Overview of the Adaptive Robust DFT and It’s Applications," Technological Innovation in Engineering Research, Vol. 4, pp. 68-89, 2022, doi:10.9734/bpi/tier/v4/6314F.
  5. J. Jones, "A Comparison of Two Recent Approaches, Exploiting Pipelined FFT and Memory-Based FHT Architectures, for Resource-Efficient Parallel Computation of Real-Data DFT,", June. 2023 doi: 10.21203/rs.3.rs-3092888/v1
  6. Rajaby and S. M. Sayedi, "A structured review of sparse fast Fourier transform algorithms," Digital Signal Processing, vol. 123, p. 103403, Apr.2022, doi:10.1016/j.dsp.2022.103403.
  7. J. Jones, "Design for Resource-Efficient Parallel Solution to Real-Data Sparse FFT," Jul. 2023, doi:10.21203/rs.3.rs-3133148/v1
  8. A. Naoghare and A. V. Sakhare, "Review on FFT architecture for real valued signals using Radix 25 algorithm," 2015 International Conference on Pervasive Computing (ICPC), Pune, India, 2015, pp. 1-3, doi: 10.1109/PERVASIVE.2015.7087124.
  9. K. Mohanty and P. K. Meher, "Area–Delay–Energy Efficient VLSI Architecture for Scalable In-Place Computation of FFT on Real Data," in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 66, no. 3, pp. 1042-1050, Mar. 2019, doi: 10.1109/TCSI.2018.2873720.
  10. A. Tsonev, "High speed energy efficient incoherent optical wireless communications," University of Edinburgh, 2015.
  11. Park and D. Jeon, "A Modified Serial Commutator Architecture for Real-Valued Fast Fourier Transform," 2020 IEEE Workshop on Signal Processing Systems (SiPS), Coimbra, Portugal, 2020, pp. 1-6, doi: 10.1109/SiPS50750.2020.9195236.
  12. Eleftheriadis and G. Karakonstantis, "Energy-Efficient Fast Fourier Transform for Real-Valued Applications," in IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 69, no. 5, pp. 2458-2462, May. 2022, doi: 10.1109/TCSII.2022.3163280.
  13. Takahashi, "An implementation of parallel 1-D real FFT on Intel Xeon Phi processors," in International Conference on Computational Science and Its Applications, 2017: Springer, pp. 401-410.
  14. Sorensen, D. Jones, M. Heideman and C. Burrus, "Real-valued fast Fourier transform algorithms," in IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 35, no. 6, pp. 849-863, June. 1987, doi: 10.1109/TASSP.1987.1165220.
  15. Lao and K. K. Parhi, "Data-Canonic Real FFT Flow-Graphs for Composite Lengths," 2016 IEEE International Workshop on Signal Processing Systems (SiPS), Dallas, TX, USA, 2016, pp. 189-194, doi: 10.1109/SiPS.2016.41..
  16. Majorkowska-Mech and A. Cariow, "Some FFT Algorithms for Small-Length Real-Valued Sequences," Applied Sciences, vol. 12, no. 9, p. 4700, May. 2022, doi:10.3390/app12094700
  17. G. Kumar, S. K. Sahoo, and P. K. Meher, "50 years of FFT algorithms and applications," Circuits, Systems, and Signal Processing, vol. 38, pp. 5665-5698, May. 2019, doi:10.1007/s00034-019-01136-8
  18. Zhang, Z. Babar, P. Petropoulos, H. Haas and L. Hanzo, "The Evolution of Optical OFDM," in IEEE Communications Surveys & Tutorials, vol. 23, no. 3, pp. 1430-1457, thirdquarter 2021, doi: 10.1109/COMST.2021.3065907
  19. Huang, Q. Wang, S. Lu, R. Hao, S. Mei, and J. Liu, "Evaluating FFT-based Algorithms for Strided Convolutions on ARMv8 Architectures?," ACM SIGMETRICS Performance Evaluation Review, vol. 49, no. 3, pp. 28-29, Mar. 2022, doi:10.1145/3529113.3529122
  20. Wang, Q. Wang, W. Huang, and Z. Xu, Visible light communications: modulation and signal processing. John Wiley & Sons, 2017.
  21. Deng, S. Mardanikorani, G. Zhou and J. -P. M. G. Linnartz, "DC-Bias for Optical OFDM in Visible Light Communications," in IEEE Access, vol. 7, pp. 98319-98330, Jul. 2019, doi: 10.1109/ACCESS.2019.2928944
  22. D. Saied, Orthogonal frequency division multiplexing for indoor visible light communication links. University of Northumbria at Newcastle (United Kingdom), 2018.
  23. Ramadan and M. S. Elbakry, "Performance Improvement for Optical OFDM Systems Using Symbol Time Compression," 2022, doi:10.21203/rs.3.rs-1725212/v1
  24. Mounir, M. I. Youssef, and A. M. Aboshosha, "Low-complexity selective mapping technique for PAPR reduction in downlink power domain OFDM-NOMA," EURASIP Journal on Advances in Signal Processing, vol. 2023, no. 1, p. 10, Jan. 2023, doi:10.1186/s13634-022-00968-y
  25. A. Abdulkafi, M. Y. Alias, Y. S. Hussein, N. Omar and M. K. B. Salleh, "PAPR reduction of DC biased optical OFDM using combined clipping and PTS techniques," 2017 IEEE 13th Malaysia International Conference on Communications (MICC), Johor Bahru, Malaysia, Nov. 2017, pp. 207-212, doi: 10.1109/MICC.2017.8311760.
  26. S. Ahmed, "OFDM base T-transform for wireless communication networks," Newcastle University, 2012.