Abstract
In digital communications and radar systems, the design of sequences with low cross-correlation is essential for minimizing interference and ensuring signal integrity. This paper provides a rigorous analysis of the cross-correlation between a ternary $m$-sequence of period $3^n - 1$ and its decimated version, where the decimation factor is defined as $d = (3^{2k}+1)^2 / 20$ for $n=4k$. By employing the quadratic form method over finite fields, the authors establish that the cross-correlation magnitude is bounded by $5\cdot 3^{n/2} + 1$. This result provides a theoretical guarantee for signal interference levels in systems utilizing these specific sequence pairs.
Introduction
Maximum length sequences, or $m$-sequences, are fundamental to modern communication technologies, particularly in Code Division Multiple Access (CDMA) and spread-spectrum systems. These sequences are valued for their pseudo-random properties and their nearly ideal auto-correlation. However, in multi-user environments, the cross-correlation between different sequences—or between a sequence and its decimated version—becomes the critical metric. High cross-correlation leads to "crosstalk" and increased bit-error rates.
While the cross-correlation properties of binary $m$-sequences (sequences over $GF(2)$) have been extensively studied, ternary sequences (over $GF(3)$) present a more complex mathematical landscape. This research investigates a specific, mathematically "heavy" decimation factor $d = \frac{(3^{2k}+1)^2}{20}$ in the ternary field $GF(3^n)$, where $n=4k$ and $k$ is an odd integer. The goal is to prove a definitive upper bound on the correlation peaks to ensure these sequences are viable for practical engineering applications.
Methodology: The Quadratic Form Approach
The authors utilize the Quadratic Form Method, a cornerstone of algebraic coding theory, to derive the correlation bounds. The process involves several sophisticated mathematical steps:
- Exponential Sum Representation: The cross-correlation function $C_d(\tau)$ is first expressed as an exponential sum over the finite field $GF(3^n)$.
- Transformation to Quadratic Forms: The problem is reduced to analyzing the properties of two specific quadratic forms, $q_1(x)$ and $q_2(x)$. In this context, a quadratic form is a homogeneous polynomial of degree two.
- Rank Analysis: The magnitude of an exponential sum is inversely related to the "rank" of its underlying quadratic form. A higher rank corresponds to a smaller sum, which translates to lower cross-correlation. The core of the proof lies in determining the possible ranks these forms can take.
- Linearized Polynomials: To calculate the rank, the authors solve for the number of roots of associated linearized polynomials. They demonstrate that while one quadratic form maintains full rank ($n$), the other varies, specifically taking ranks of $n$, $n-2$, or $n-4$.
By applying Lemma 6—a standard result relating the value of exponential sums to the rank of quadratic forms over finite fields—the authors calculate the maximum possible value across these rank variations.
Key Insights
The research reveals that the decimation factor $d = (3^{2k}+1)^2 / 20$ behaves predictably when $k$ is an odd integer, despite its initial complexity. The primary technical breakthrough is the identification of the rank distribution; by proving that the rank of the quadratic form $q_1(x)$ can only drop by 2 or 4, the authors effectively "cap" the maximum possible correlation value.
This work also demonstrates methodological continuity, successfully adapting and extending techniques recently applied to different decimation factors. This suggests that quadratic form analysis remains a robust and versatile tool for characterizing ternary sequence distributions.
Results and Implications
The primary contribution of this paper is the formal proof of the upper bound for the cross-correlation magnitude $|C_d(\tau)|$:
$$\max |C_d(\tau)| \leq 5 \cdot 3^{n/2} + 1$$
where $n = 4k$. In the context of signal processing, a correlation bound proportional to the square root of the sequence period ($\sqrt{3^n}$) is highly desirable. This result confirms that this specific decimation factor produces sequence pairs with manageable interference levels, making them suitable candidates for high-capacity communication systems where low mutual interference is a priority.
Conclusion and Future Directions
While this paper establishes a critical upper bound, several avenues for future research remain. First, the current work provides an upper bound but does not determine if this bound is "tight"—that is, whether there exists a specific shift $\tau$ where the correlation actually reaches $5\cdot 3^{n/2} + 1$. Second, while the maximum magnitude is now known, the full correlation distribution (the exact frequency of every possible correlation value) has yet to be mapped. Finally, future studies could investigate the hardware implementation complexity of generating these decimated sequences to evaluate their practical trade-offs against more traditional sequence choices.
Summary updated