Fast Convolution Algorithm for Real-Valued Finite Length Sequences

Weiwei Wang; Victor E. DeBrunner; Linda S. DeBrunner

ICASSP 2023accepted0 citations

Fast Convolution Algorithm for Real-Valued Finite Length Sequences

Weiwei Wang, Victor E. DeBrunner, Linda S. DeBrunner

Abstract

The Fast Fourier Transform (FFT)-based convolution is the most popular fast convolution algorithm. In past work, we developed the Discrete Hirschman Transform (DHT)-based convolution. When compared to the FFT-based convolution, our DHT-based convolution can reduce the computational complexity by a third. Recently, we developed a comprehensive DFT algorithm where every calculation is natively real-valued (RV) dot products. In this paper, we first apply the natively real-valued DFT to linear convolution. We call this method the RV-based convolution. The arithmetic analysis reveals that it efficiently reduces the operation counts. The algorithm is fast regardless of length.

BibTeX

@inproceedings{icassp2023_fastconvolutiona,
  title = {Fast Convolution Algorithm for Real-Valued Finite Length Sequences},
  author = {Weiwei Wang and Victor E. DeBrunner and Linda S. DeBrunner},
  booktitle = {ICASSP 2023},
  year = {2023}
}