A New Algorithm for Real Data Convolutions With $j$ -Circulants

A new algorithm for efficient linear convolution of real signals is presented. It is shown that the circulant required in traditional overlap-and-save (OLS) and overlap-and-add (OLA) methods can be substituted by a j-circulant, that is, a circulant matrix where the shifted elements are multiplied by the imaginary unit. Such j-circulant can be implemented easily and efficiently with half-length complex Fast Fourier Transforms. The latency remains the same as that of OLS and OLA. This method results in computational savings when compared to OLA and OLS, reducing the total arithmetic operations and particularly the execution time.