An Efficient Real-Valued Cross-Correlator via Fast Fourier Transform

Cross-correlation is used to compute temporal correlations of two signals in numerous engineering and scientific applications. Due to its similarity to convolution, cross-correlation can also be computed using the fast Fourier transform (FFT) to reduce computation complexity. FFT (Inverse FFT or IFFT) can be used to compute discrete (inverse discrete) Fourier transform of both complex-valued and real-valued signals, referred to as CFFT (CIFFT) and RFFT (RIFFT), respectively, in this paper. This paper presents a novel cross-correlator for real signals by exploiting efficient RFFT and RIFFT structures. In computing correlation, zeros are padded to one signal and to the flipped version of another signal. In particular, the first stage of the RFFT is simplified to remove computations associated with zero inputs. When N=1024, it achieves significant savings, reducing real-valued multiplications by 56% and real-valued additions by 58% compared to a conventional correlator based on CFFT and CIFFT.