Abstract
Unimodular sequences with low autocorrelations are desired in many applications, especially in the area of radar and code-division multiple access (CDMA). In this paper, we propose a new algorithm to design unimodular sequences with low integrated sidelobe level (ISL), which is a widely used measure of the goodness of a sequence's correlation property. The algorithm falls into the general framework of majorization-minimization (MM) algorithms and thus shares the monotonic property of such algorithms. In addition, the algorithm can be implemented via fast Fourier transform (FFT) operations and thus is computationally efficient. Furthermore, after some modifications the algorithm can be adapted to incorporate spectral constraints, which makes the design more flexible. Numerical experiments show that the proposed algorithms outperform existing algorithms in terms of both the quality of designed sequences and the computational complexity.
Introduction
In fields like radar and code-division multiple access (CDMA) communications, sequences that mimic noise while remaining deterministic are highly sought after. Ideally, their autocorrelation should exhibit a sharp peak at zero lag and remain near zero elsewhere. High sidelobes in the autocorrelation function can lead to "ghost" targets or significant interference.
Hardware constraints, such as those imposed by power amplifiers, often necessitate that these sequences be unimodular—meaning they possess a constant magnitude with only the phase varying. Designing long unimodular sequences with low Integrated Sidelobe Levels (ISL) is a challenging non-convex optimization problem. Traditional methods like the CAN (Cyclic Algorithm New) algorithm often minimize a proxy for ISL, which can lead to sub-optimal results.
Methodology: The MISL Algorithm
The proposed MISL (Monotonic minimizer for Integrated Sidelobe Level) algorithm addresses the ISL minimization problem directly within the Majorization-Minimization (MM) framework.
The MM Strategy and Double Majorization
Instead of directly minimizing the complex quartic ISL function, the MM approach constructs a simpler "surrogate" function that serves as an upper bound. Minimizing this surrogate ensures a monotonic decrease in the original objective. The authors employ a "double majorization" step to derive a simple, closed-form update rule for the sequence at each iteration.
FFT Implementation and Acceleration
A key advantage of MISL is its computational efficiency. The core mathematical operations in the update rule are equivalent to Discrete Fourier Transforms, allowing the algorithm to run in $O(N \log N)$ time. This makes it feasible for sequences exceeding $10^6$ elements.
To address potential slow convergence inherent in double majorization, the authors introduce acceleration schemes. One such scheme is Accelerated-MISL, which utilizes fixed-point acceleration to speed up convergence while maintaining the monotonic property.
Spectral-MISL
The framework is further extended to Spectral-MISL, allowing for the incorporation of spectral constraints. This is particularly useful for "cognitive radar" applications where sequences must avoid interference with specific frequency bands.
Experimental Evaluation
The algorithm's performance was evaluated through numerical experiments:
- Sequence Lengths: Tests ranged from $N = 32$ to $N = 8192$, with scalability demonstrated up to $N = 10^6$.
- Benchmarks: Results were compared against the state-of-the-art CAN algorithm.
- Initialization: Random unimodular sequences were used as starting points to ensure robustness.
Key Results and Discussion
- Superior Quality: MISL consistently achieves higher Merit Factors (the ratio of main peak energy to total sidelobe energy) compared to CAN by minimizing the actual ISL metric.
- Guaranteed Convergence: Unlike heuristic approaches, MISL is mathematically guaranteed to never increase the ISL, ensuring stable convergence.
- Efficiency: Accelerated-MISL proved to be both more accurate and faster than CAN, particularly as sequence length increased.
- Spectral Suppression: Spectral-MISL successfully suppressed power in specific frequency notches by over 30dB while maintaining low autocorrelation sidelobes.
Conclusion and Future Work
MISL provides a robust and efficient framework for designing unimodular sequences. While it converges to local optima due to the non-convex nature of the problem, initialization with known good sequences can further enhance results. Future work may involve extending this framework to multi-sequence design for MIMO radar systems or exploring non-unit modulus constraints.
Summary updated