TPE-FFT: A Novel Two-Phase Execution Fast Fourier Transform for Ultra-Low-Latency Bioinformatics Architecture

Saravanakumar C; Usha Bhanu  N; Subhashini  N; Preethi Sambandam Raju

doi:10.35882/jeeemi.v8i4.1933

Saravanakumar C Department of Electronics and Communication Engineering, SRM Valliammai Engineering College https://orcid.org/0000-0003-2505-1317
Usha Bhanu N Department of Electronics and Communication Engineering, SRM Valliammai Engineering College, Kattankulathur, India https://orcid.org/0000-0001-9244-5119
Subhashini N Department of Electronics and Communication Engineering, SRM Valliammai Engineering College, Kattankulathur, India https://orcid.org/0000-0001-9171-7434
Preethi Sambandam Raju Department of Electronics and Communication Engineering, SRM Valliammai Engineering College, Kattankulathur, India https://orcid.org/0000-0002-3541-0830

DOI: https://doi.org/10.35882/jeeemi.v8i4.1933

Keywords: Two – Phase Execution FFT, Low latency computing, Genomic Signal Processing, Integrated Engineering Systems, Biomedical Signal Processing

Abstract

The Fast Fourier Transform (FFT) is widely employed for frequency-domain analysis of genomic and biomedical signals; however, conventional block-oriented FFT processing generally requires the complete input sequence before the transform can be finalized. When genomic data are acquired sequentially, computations that depend on the final sample may remain unresolved until that sample arrives, resulting in additional post-arrival processing latency. This study presents a Two-Phase Execution Fast Fourier Transform (TPE-FFT), a dependency-aware execution strategy for radix-2 Decimation-in-Time (DIT) FFT processing. The proposed method exploits the linearity of the Discrete Fourier Transform (DFT) to separate the contribution of the final acquired sample from the contributions of the preceding samples. During Phase I, computations independent of the final sample are performed using a temporary zero representation, while the corresponding final-sample contribution is evaluated during Phase II and incorporated through an exact Fourier-domain correction. Variable-length genomic sequences are mapped to a common radix-2 transform length using zero-padding, and the proposed method is evaluated against a conventional radix-2 DIT-FFT implementation under the same computational conditions. A total of 1,075 genomic sequences are evaluated. TPE-FFT achieves positive measured execution-time reduction for 1,053 sequences (97.95%). The cumulative execution time decreases from 225.56469 s for the conventional implementation to 7.80065 s for TPE-FFT, corresponding to a 96.54% aggregate reduction and a 28.92× runtime ratio. For a representative 33,681-sample genomic sequence, execution time decreases from 15.15 s to 0.51 s, corresponding to a 96.63% reduction. The results indicate that dependency-aware scheduling can substantially reduce the computational workload remaining after final-sample arrival while retaining the underlying O(Nlog₂N) FFT complexity. The proposed strategy therefore provides a computational basis for further investigation of low-latency FFT processing in sequential genomic signal-processing applications.

Downloads

Download data is not yet available.

References

P. Duhamel and H. Hollmann, “Split radix FFT algorithm,” Electron. Lett., vol. 20, no. 1, pp. 14–16, Jan. 1984, doi: 10.1049/el:19840011.

G. Bruun, “z-transform DFT filters and FFTs,” IEEE Trans. Acoust., Speech, Signal Process., vol. 26, no. 1, pp. 56–63, Feb. 1978, doi: 10.1109/TASSP.1978.1163096.

C. M. Rader, “Discrete Fourier transforms when the number of data samples is prime,” Proc. IEEE, vol. 56, no. 6, pp. 1107–1108, Jun. 1968, doi: 10.1109/PROC.1968.6458.

L. H. Thomas, “Using a computer to solve problems in physics,” in Applications of Digital Computers, 1963, pp. 44–45.

J. B. Birdsong and N. I. Rummelt, “The hexagonal fast Fourier transform,” in Proc. 2016 IEEE Int. Conf. Image Process. (ICIP), 2016, pp. 1809–1812, doi: 10.1109/ICIP.2016.7532670.

L. I. Bluestein, “A linear filtering approach to the computation of the discrete Fourier transform,” IEEE Trans. Audio Electroacoust., vol. 18, no. 4, pp. 451–455, Dec. 1970, doi: 10.1109/TAU.1970.1162133.

S. Winograd, “On computing the discrete Fourier transform,” Math. Comput., vol. 32, no. 141, pp. 175–199, 1978, doi: 10.1090/S0025-5718-1978-0456761-0.

A. Becoulet and A. Verguet, “A depth-first iterative algorithm for the conjugate pair fast Fourier transform,” IEEE Trans. Signal Process., vol. 69, pp. 1537–1547, 2021, doi: 10.1109/TSP.2021.3060279.

S. Sanjeet, B. D. Sahoo, and K. K. Parhi, “Comparison of real-valued FFT architectures for low-throughput applications using FPGA,” in Proc. IEEE 64th Int. Midwest Symp. Circuits Syst. (MWSCAS), 2021, pp. 112–115, doi: 10.1109/MWSCAS47672.2021.9531878.

D. Krishnegowda and P. Nagaraju, “Design and synthesis of a 256-point radix-2 DIT FFT core with DesignWare library using fixed-point number representation,” in Proc. IEEE Delhi Sect. Conf. (DELCON), 2022, doi: 10.1109/DELCON54057.2022.9753181.

Y. Zhao, H. Lv, J. Li, and L. Zhu, “High performance and resource-efficient FFT processor based on CORDIC algorithm,” EURASIP J. Adv. Signal Process., vol. 2022, no. 1, Art. no. 55, 2022, doi: 10.1186/s13634-022-00855-6.

C. Saravanakumar and N. Usha Bhanu, “A mutated addition-subtraction unit to reduce the complexity of FFT,” Appl. Nanosci., vol. 12, pp. 1–11, Jan. 2022, doi: 10.1007/s13204-021-02278-5.

D. K. J. Rajanediran, C. G. Babu, K. Priyadharsini, and M. Ramkumar, “Hybrid radix-16 Booth encoding and rounding-based approximate Karatsuba multiplier for fast Fourier transform computation in biomedical signal processing application,” Integration, the VLSI J., vol. 98, Art. no. 102215, Sep. 2024, doi: 10.1016/j.vlsi.2024.102215.

F. Ai and V. Lomakin, “Fast Fourier Transform periodic interpolation method for superposition sums in a periodic unit cell,” Comput. Phys. Commun., vol. 304, Art. no. 109291, Nov. 2024, doi: 10.1016/j.cpc.2024.109291.

G. Huang and F. Zhang, “The fast computation of multi-angle discrete fractional Fourier transform,” Signal Process., vol. 218, Art. no. 109365, May 2024, doi: 10.1016/ j.sigpro. 2024. 109365.

M. R. Saad et al., “Fourier transform optimizer: A novel physics-inspired metaheuristic algorithm for optimization problems,” Knowl.-Based Syst., vol. 340, Art. no. 115651, May 2026, doi: 10.1016/j.knosys.2026.115651.

O. Leitersdorf, Y. Boneh, G. Gazit, R. Ronen, and S. Kvatinsky, “FourierPIM: High-throughput in-memory Fast Fourier Transform and polynomial multiplication,” Memories - Mater., Devices, Circuits Syst., vol. 4, Art. no. 100034, 2023, doi: 10.1016/j.memori.2023.100034.

T. Olas, R. Wyrzykowski, M. Olas, M. Palkowski, and M. Gruzewski, “Towards the efficient use of RISC-V architecture in scientific computation,” J. Comput. Sci., vol. 96, Art. no. 102853, 2026, doi: 10.1016/j.jocs.2026.102853.

B. Schmidt and A. Hildebrandt, “From GPUs to AI and quantum: Three waves of acceleration in bioinformatics,” Drug Discovery Today, vol. 29, no. 6, Art. no. 103986, Jun. 2024, doi: 10.1016/j.drudis.2024.103986.

X. Liu, Z. Tan, P. Tang, P. Lu, and X. Lu, “Research on a novel gene sequence prediction and homomorphic encryption method based on Mamba-VMD,” Comput. Biol. Chem., vol. 120, Art. no. 108780, 2026, doi: 10.1016/j.cbac.2026.108780.

M. C. S. Tang, S. S. Teoh, H. Ibrahim, and Z. Embong, “Neovascularization detection and localization in fundus images using deep learning,” Sensors, vol. 21, no. 16, Art. no. 5327, 2021, doi: 10.3390/s21165327.

B. Goutam, M. F. Hashmi, Z. W. Geem, and N. D. Bokde, “A comprehensive review of deep learning strategies in retinal disease diagnosis using fundus images,” IEEE Access, vol. 10, pp. 57796–57823, 2022, doi: 10.1109/ACCESS.2022.3178372.

R. R. Mantovani, G. L. Menezes, and J. R. R. Dórea, “Predicting respiration rate in unrestrained dairy cows using image analysis and fast Fourier transform,” JDS Commun., vol. 5, pp. 310–316, 2024, doi: 10.3168/jdsc.2023-0442.

S. Benarjee and N. K. Vaegae, “Hadamard code based numerical mapping approach for the identification of protein coding regions in genomic sequences using digital filters,” Comput. Biol. Med., vol. 195, Art. no. 110565, 2025, doi: 10.1016/j.compbiomed.2025.110565.

N. K. Vaegae, “Walsh code based numerical mapping method for the identification of protein coding regions in eukaryotes,” Biomed. Signal Process. Control, vol. 58, Art. no. 101859, Apr. 2020.

M. Raman Kumar and V. Naveen Kumar, “A numerical representation method for a DNA sequence using gray code method,” in Soft Computing for Problem Solving: SocProS 2018, vol. 2, 2019, pp. 645–654.

N. A. Kumar et al., “Verification of periodicity of exons in DNA using digital signal processor (TMS320C6748),” Procedia Comput. Sci., vol. 259, pp. 1612–1618, 2025, doi: 10.1016/j.procs.2025.04.116.

E. Ndupuechi and C. Beecks, “Fast Fourier transform gated activation function (FFTGate),” Inf. Fusion, vol. 129, Art. no. 103987, May 2026, doi: 10.1016/j.inffus.2025.103987.

M. Henry, “An ultra-precise fast Fourier transform—Part 2,” Measurement, vol. 270, Art. no. 120779, Apr. 2026, doi: 10.1016/j.measurement.2026.120779.

M. Garrido, “A survey on pipelined FFT hardware architectures,” J. Signal Process. Syst., vol. 94, pp. 1345–1364, 2022, doi: 10.1007/s11265-021-01655-1.

S.-W. Chiu and K. K. Parhi, “Efficient decomposition of multistage composite length FFT for complex and real signals,” IEEE Trans. Signal Process., vol. 74, pp. 892–903, 2026, doi: 10.1109/TSP.2026.3664785.

R. Li, C. Liu, Y. Liang, J. Fu, Q. Zhang, and J. Xuan, “A fast algorithm for the symmetric discrete Fourier transform,” in Proc. 2025 Int. Conf. Equipment Intell. Operation Maintenance (ICEIOM), Urumqi, China, 2025, pp. 401–406, doi: 10.1109/ICEIOM65271.2025.11239746.

Y. Zhou, W. Cao, L. Liu, S. Agaian, and C. L. P. Chen, “Fast Fourier transform using matrix decomposition,” Inf. Sci., vol. 291, pp. 172–183, 2015, doi: 10.1016/j.ins.2014.08.022.

S.-C. Pei and K.-W. Chang, “Fast sparse DFT computation for arbitrary length by circular convolution,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process. (ICASSP), 2025, pp. 1–5, doi: 10.1109/ICASSP49660.2025.10890724.

W. Shi, J. Wu, Y. Yuan, Z. Mo, C. Wu, and J. He, “An area–energy-efficient 64–2048 point FFT with approximate plane-fitting complex multipliers,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2025, doi: 10.1109/TVLSI.2025.3550470.

National Center for Biotechnology Information (NCBI), “GenBank,” [Online]. Available: https://www.ncbi.nlm.nih.gov. Accessed: Apr. 25, 2026.

C. Saravanakumar and N. Usha Bhanu, “A constructive approach to numerical mapping scheme of nucleotides for preprocessing in machine learning,” in Proc. 2022 12th Int. Conf. Cloud Comput., Data Sci. Eng. (Confluence), Noida, India, 2022, pp. 482–486, doi: 10.1109/Confluence52989.2022.9734186.

B. Liu, B. Yan, and Q. Zou, “Optimal time-distributed fast Fourier transform: Application to online iterative learning control—Experimental high-speed nanopositioning example,” Mechatronics, vol. 41, pp. 114–124, 2017, doi: 10.1016/j.mechatronics.2016.11.007.

I. Domuta and T. P. Palade, “Sliding DFT and zero padding,” in Proc. 2019 42nd Int. Conf. Telecommunications Signal Process. (TSP), Budapest, Hungary, 2019, pp. 154–157, doi: 10.1109/TSP.2019.8769076.

T. Zhang et al., “FLASH: An efficient hardware accelerator leveraging approximate and sparse FFT for homomorphic encryption,” in Proc. 2025 Design, Automation Test Europe Conf. (DATE), Lyon, France, 2025, pp. 1–7, doi: 10.23919/DATE64628.2025.10992915.

M. Bharathi, K. Mohanarangam, and Y. J. M. Shirur, “Efficient signal processing: Harnessing distributed arithmetic for high-speed FFT operations,” in Proc. 2025 Int. Conf. Intell. Innov. Technol. Comput., Electr. Electron. (IITCEE), Bangalore, India, 2025, pp. 1–6, doi: 10.1109/IITCEE64140.2025.10915512.