New Algorithm for Real-Valued Fourier Transform
Article Sidebar
Main Article Content
Abstract
This paper presents a direct algorithm for fast real discrete Fourier transform (RDFT) computing, using the discrete Fourier transform (DFT) conjugate symmetric property to reduce redundancies. In RDFT, all the input and output signals were real, which differed from complex DFT. Therefore, the structure of the proposed algorithm showed only real-data operations. The developed algorithm showed the desired properties, such as in-place computation, regularity, simplicity, and arithmetic operations reduction. The RFFT performance was compared with other related transforms, such as the fast Hartley transform (FHT) for the computation in the radix-2 algorithm. It was found that FHT showed the best performance in terms of arithmetic complexity.
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
THIS IS AN OPEN ACCESS ARTICLE UNDER THE CC BY LICENSE http://creativecommons.org/licenses/by/4.0/
Plaudit
References
Behrendt M, de Angelis M, Comerford L, Zhang Y, Beer M. Projecting Interval Uncertainty through the Discrete Fourier Transform: An Application to Time Signals with Poor Precision. Mechanical Systems and Signal Processing 2022; 172:108920, (1-36). DOI: https://doi.org/10.1016/j.ymssp.2022.108920
Özhan O. (2022). Fast Fourier Transform. In Basic Transforms for Electrical Engineering (pp. 465-494). Cham: Springer International Publishing. DOI: https://doi.org/10.1007/978-3-030-98846-3_8
Takahashi D. (2019). Fast Fourier Transform. Fast Fourier Transform Algorithms for Parallel Computers, 5-13. DOI: https://doi.org/10.1007/978-981-13-9965-7_2
Roienko O, Lukin V, Oliinyk V, Djurović I, Simeunović M. An Overview of the Adaptive Robust DFT and it’s Applications. Technological Innovation in Engineering Research 2022; 4:68-89. DOI: https://doi.org/10.9734/bpi/tier/v4/6314F
Khayyeri M, Mohammadi K. Cooperative Wideband Spectrum Sensing in Cognitive Radio Based on Sparse Real‐Valued Fast Fourier Transform. IET Communications 2020;14(8):1340-1348. DOI: https://doi.org/10.1049/iet-com.2018.5930
Feng Q, Liu Y, Lai Y-K, Yang J, Li K. FOF: Learning Fourier Occupancy Field for Monocular Real-Time Human Reconstruction. Advances in Neural Information Processing Systems 2022;35:7397-7409.
Moryakova O, Johansson H. Frequency -Domain Implementations of Variable Digital FIR Filters Using the Overlap-Save Technique. 2023 24th International Conference on Digital Signal Processing (DSP): IEEE; Rhodes (Rodos), Greece, 2023. pp. 1-5. DOI: https://doi.org/10.1109/DSP58604.2023.10167923
Tang SN, Jan FC, Cheng HW, Lin CK, Wu GZ. Multimode Memory-Based FFT Processor for Wireless Display FD-OCT Medical Systems. IEEE Transactions on Circuits and Systems I: Regular Papers 2014;61(12):3394-3406. DOI: https://doi.org/10.1109/TCSI.2014.2327315
Mohanty BK, Meher PK. Area–Delay–Energy Efficient Vlsi Architecture for Scalable in-Place Computation of FFT on Real Data. IEEE Transactions on Circuits and Systems I: Regular Papers 2018; 66(3):1042-1050. DOI: https://doi.org/10.1109/TCSI.2018.2873720
Ma ZG, Yin XB, Yu F. A Novel Memory-Based FFT Architecture for Real-Valued Signals Based on a Radix-2 Decimation-in-Frequency Algorithm. IEEE Transactions on Circuits and Systems II: Express Briefs 2015; 62(9):876-880. DOI: https://doi.org/10.1109/TCSII.2015.2435522
Hamood MT. Improved FHT Algorithms for Fast Computation of the Discrete Hartley Transform. Tikrit Journal of Engineering Sciences 2013; 20(1):62-69. DOI: https://doi.org/10.25130/tjes.20.1.07
Bouguezel S, Ahmad MO, Swamy M. Binary Discrete Cosine and Hartley Transforms. IEEE Transactions on Circuits and Systems I: Regular Papers 2012; 60(4):989-1002. DOI: https://doi.org/10.1109/TCSI.2012.2224751
Britanak V, Yip PC, Rao KR. Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations: Elsevier; Oxford, UK, 2010.
Sorensen HV, Jones D, Heideman M, Burrus C. Real-Valued Fast Fourier Transform Algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing 1987; 35(6):849-863. DOI: https://doi.org/10.1109/TASSP.1987.1165220
Garrido M, Unnikrishnan NK, Parhi KK. A Serial Commutator Fast Fourier Transform Architecture for Real-Valued Signals. IEEE Transactions on Circuits and Systems II: Express Briefs 2017; 65(11):1693-1697. DOI: https://doi.org/10.1109/TCSII.2017.2753941
Chinnapalanichamy A, Parhi KK. Serial and Interleaved Architectures for Computing Real FFT. 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP): IEEE; South Brisbane, QLD, Australia, 2015. pp. 1066-1070. DOI: https://doi.org/10.1109/ICASSP.2015.7178133
Fang H, Zhang B, Yu F, Zhao B, Ma Z. A Pipelined Algorithm and Area-Efficient Architecture for Serial Real-Valued FFT. IEEE Transactions on Circuits and Systems II: Express Briefs 2022; 69(11):4533-4537. DOI: https://doi.org/10.1109/TCSII.2022.3187096
Sanjeet S, Sahoo BD, Parhi KK. Comparison of Real-Valued FFT Architectures for Low-Throughput Applications Using FPGA. 2021 IEEE International Midwest Symposium on Circuits and Systems (MWSCAS): IEEE; Lansing, MI, USA, 2021. pp. 112-115. DOI: https://doi.org/10.1109/MWSCAS47672.2021.9531878
Garrido M. A Survey on Pipelined FFT Hardware Architectures. Journal of Signal Processing Systems 2022; 94(11):1345-1364. DOI: https://doi.org/10.1007/s11265-021-01655-1
Salehi SA, Amirfattahi R, Parhi KK. Pipelined Architectures for Real-Valued FFT and Hermitian-Symmetric IFFT with Real Datapaths. IEEE Transactions on Circuits and Systems II: Express Briefs 2013; 60(8):507-511. DOI: https://doi.org/10.1109/TCSII.2013.2268411
Ayinala M, Lao Y, Parhi KK. An in-Place FFT Architecture for Real-Valued Signals. IEEE Transactions on Circuits and Systems II: Express Briefs 2013; 60(10):652-656. DOI: https://doi.org/10.1109/TCSII.2013.2273841
Lao Y, Parhi KK. 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: https://doi.org/10.1109/SiPS.2016.41
Yin XB, Yu F, Ma ZG. Resource-Efficient Pipelined Architectures for Radix-2 Real-Valued FFT with Real Datapaths. IEEE Transactions on Circuits and Systems II: Express Briefs 2016; 63(8):803-807. DOI: https://doi.org/10.1109/TCSII.2016.2530862
Kumar GG, Sahoo SK, Meher PK. 50 Years of FFT Algorithms and Applications. Circuits, Systems, and Signal Processing 2019; 38:5665-5698. DOI: https://doi.org/10.1007/s00034-019-01136-8
Park S, Jeon D. A Modified Serial Commutator Architecture for Real-Valued Fast Fourier Transform. In 2020 IEEE Workshop on Signal Processing Systems (SiPS); Coimbra, Portugal, 2020, (pp. 1-6). IEEE. DOI: https://doi.org/10.1109/SiPS50750.2020.9195236
Majorkowska-Mech D, Cariow A. Some FFT Algorithms for Small-Length Real-Valued Sequences. Applied Sciences 2022; 12(9):4700, (1-21). DOI: https://doi.org/10.3390/app12094700
Eleftheriadis C, Karakonstantis G. Energy-Efficient Fast Fourier Transform for Real-Valued Applications. IEEE Transactions on Circuits and Systems II: Express Briefs 2022; 69(5):2458-2462. DOI: https://doi.org/10.1109/TCSII.2022.3163280
Al-Ubaidi SM. Design and Implementation of Sequency-Ordered Fast Walsh-Hadamard Transform (FWHT) in WCDMA. Tikrit Journal of Engineering Sciences 2014; 21(3):26-31. DOI: https://doi.org/10.25130/tjes.21.3.03
Gautam D. Resourceful Fast Discrete Hartley Transform to Replace Discrete Fourier Transform with Implementation of DHT Algorithm for VLSI Architecture. Turkish Journal of Computer and Mathematics Education 2021; 12(10) :5290-5298.
Jones KJ. The Regularized Fast Hartley Transform: Low-Complexity Parallel Computation of the FHT in One and Multiple Dimensions. Springer Nature: 2021; pp. 35-50. DOI: https://doi.org/10.1007/978-3-030-68245-3_3