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.
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.
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