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

Salih, Sukaina Khazaal; Hamood, Mounir Taha

doi:10.37649/aengs.2023.142947.1060

	Direct Algorithm for Computation of Inverse Real Fast Fourier Transform (IRDFT)
Anbar Journal of Engineering Sciences
Volume 14, Issue 2, November 2023, Pages 19-27 PDF (636.77 K)
Document Type: Research Paper
DOI: 10.37649/aengs.2023.142947.1060
Authors
sukaina khazaal salih^* ¹; mounir taha hamood²
¹University of Tikrit
²electrical,engineering,university of tikrit, tikrit, iraq
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
Discrete Fourier Transform(DFT); Real-valued DFT(RDFT); Decimation in frequency(DIF); O-OFDM; PAPR

References
Takahashi and D. Takahashi, "Fast fourier transform," Fast Fourier Transform Algorithms for Parallel Computers, vol. 2, 2019, pp. 5-13. 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 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 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. 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 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. J. Jones, "Design for Resource-Efficient Parallel Solution to Real-Data Sparse FFT," Jul. 2023, doi:10.21203/rs.3.rs-3133148/v1 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. 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. A. Tsonev, "High speed energy efficient incoherent optical wireless communications," University of Edinburgh, 2015. 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. 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. 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. 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. 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.. 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 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 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 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 Wang, Q. Wang, W. Huang, and Z. Xu, Visible light communications: modulation and signal processing. John Wiley & Sons, 2017. 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 D. Saied, Orthogonal frequency division multiplexing for indoor visible light communication links. University of Northumbria at Newcastle (United Kingdom), 2018. Ramadan and M. S. Elbakry, "Performance Improvement for Optical OFDM Systems Using Symbol Time Compression," 2022, doi:10.21203/rs.3.rs-1725212/v1 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 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. S. Ahmed, "OFDM base T-transform for wireless communication networks," Newcastle University, 2012.
Statistics Article View: 873 PDF Download: 71