Approximate Computation of DFT without Performing Any Multiplications: Applications to Radar Signal Processing

Alican Bozkurt, Musa Tunç Arslan, Rasim Akin Sevimli, Cem Emre Akbas, A. Enis ÇetinarXiv 2014 · arXiv · OpenReview

Abstract

In many practical problems, including radar signal processing, it is not always necessary to compute the Discrete Fourier Transform (DFT) perfectly. This paper introduces a new multiplication-free algorithm for the approximate computation of the DFT. By replacing all standard multiplications $(a \times b)$ with a sign-based additive operator $sign(a \times b)(|a| + |b|)$, the computational burden is significantly reduced. This approach is particularly advantageous for algorithms requiring intensive correlations, such as the ambiguity function in radar. Simulation results demonstrate that this nonlinear transform not only reduces complexity but also provides superior robustness in non-Gaussian, heavy-tailed noise environments.

Introduction

The Discrete Fourier Transform (DFT) is a fundamental tool in signal processing, yet its reliance on complex multiplications makes it computationally expensive for real-time hardware. In Passive Bistatic Radar (PBR) systems, the need to constantly compute ambiguity functions—essentially large-scale correlations—creates a significant processing bottleneck. Furthermore, standard DFT methods based on the $l_2$ norm are optimized for Gaussian noise but often fail in real-world scenarios characterized by impulsive or "heavy-tailed" interference. This research proposes a Nonlinear DFT (NDFT) and its fast counterpart (NFFT) to address both computational efficiency and environmental robustness.

The Multiplication-Free Approach

The core innovation of this work is the introduction of a new additive operator ($\otimes$) to replace standard multiplication:

$$a \otimes b = \text{sign}(a \times b)(|a| + |b|)$$

This logic is extended to complex numbers, allowing the standard Cooley-Tukey FFT structure to be redefined. The resulting Nonlinear FFT (NFFT) requires zero multiplications. Instead, an $N$-point NFFT utilizes $4N \log N$ sign computations, $8N \log N$ absolute value operations, and $6N \log N$ additions. By maintaining the traditional divide-and-conquer structure, the NFFT preserves $O(N \log N)$ complexity while becoming highly compatible with simple hardware like FPGAs that prioritize additions over complex multiplications.

Experimental Results

The algorithms were evaluated using simulated baseband stereo FM radio signals (200 kHz bandwidth) in various noise environments, including standard Additive White Gaussian Noise (AWGN) and $\epsilon$-contaminated Gaussian noise to simulate heavy-tailed outliers.

Robustness to Heavy-Tailed Noise

A critical finding is the NFFT's inherent robustness. While standard FFT-based methods rely on the $l_2$ norm, the $\otimes$ operator effectively induces an $l_1$ norm. In statistics, $l_1$-based methods are known for being robust against outliers. In simulations with contaminated Gaussian noise, the standard FFT-based ambiguity function failed to detect targets entirely, as the impulsive noise overwhelmed the signal peaks.

Standard FFT-based ambiguity function failing to detect targets in heavy-tailed noise (Doppler domain).

In contrast, the NFFT-based version successfully located targets and clutters under the same conditions. While the nonlinearity introduces some "scattering" and higher side-lobe levels (e.g., -3.86 dB for NFFT vs -5.98 dB for FFT in clean noise), it preserves the critical location of frequency peaks (Doppler shifts) necessary for detection.

NFFT-based ambiguity function successfully detecting multiple targets in the same heavy-tailed noise environment.

Conclusion

The proposed NFFT offers a compelling alternative for radar signal processing where computational resources are limited or noise environments are non-ideal. By eliminating multiplications, the algorithm simplifies hardware implementation while providing a "robustness feature" against impulsive noise. Future work will focus on optimizing input scaling to further refine detection performance and benchmarking the algorithm on specific FPGA and DSP architectures to quantify power and latency savings.

Summary updated

Abstract

In many practical problems it is not necessary to compute the DFT in a perfect manner including some radar problems. In this article a new multiplication free algorithm for approximate computation of the DFT is introduced. All multiplications $(a\times b)$ in DFT are replaced by an operator which computes $sign(a\times b)(|a|+|b|)$. The new transform is especially useful when the signal processing algorithm requires correlations. Ambiguity function in radar signal processing requires high number of multiplications to compute the correlations. This new additive operator is used to decrease the number of multiplications. Simulation examples involving passive radars are presented.
BibTeX
@misc{bozkurt2014approximate,
  author = {Alican Bozkurt and Musa Tunç Arslan and Rasim Akin Sevimli and Cem Emre Akbas and A. Enis Çetin},
  title = {{Approximate Computation of DFT without Performing Any Multiplications: Applications to Radar Signal Processing}},
  year = {2014},
  eprint = {1402.0532},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.0532},
}
Figure