PaperlayerView exact revision on arXiv

Source-linked AI summary

A class of Niho type four-valued cross-correlation functions between sequences of different periods

Yao Yao, Yufei Wang, Yongbo Xia, Nian Li, Xiangyong Zeng

arXiv:2610.34010v1cs.ITmath.IT

TL;DR

Complete cross-correlation distributions are known for only a few decimations across every shift, although such sequences matter in sequence design. This paper analyzes a family of noncoprime Niho-type decimations and determines the distributions, which are four-valued for each short-period sequence.

  • Problem

    Complete cross-correlation distributions for every shift are known for only a few decimations, despite their importance in sequence design.

    Source: §1 · p. 1

  • Method

    For n=2k, the paper studies a noncoprime Niho-type decimation with 1<s<2k and v2(s)>v2(k), using root counting and double counting to determine frequencies.

    Source: §1 · pp. 3–4

  • Results

    For each of the 2r+1 short-period sequences, the cross-correlation function is four-valued, and its distribution is completely determined, with r=gcd(s,k).

    Source: §3 · p. 25, §4 · p. 26

  • Takeaways & Limitations

    The results include the binary cross-correlation cases in as special cases.

    Source: §4 · p. 26

    The stated parameter range is 1<s<2k with v2(s)>v2(k), which excludes s=k.

    Source: §1 · p. 3

Abstract

from arXiv · show

Determining the cross-correlation distributions between $m$-sequences and their decimated sequences is an important problem in sequence design. For two positive integers $n$ and $k$ with $n=2k$, this paper investigates the cross-correlation function between a binary $m$-sequence $\{u(t)\}$ of period $2^{n}-1$ and its $2^{\gcd(s,k)}+1$ short-period decimated sequences $\{u(dt+l)\}$, where the decimation $d=\frac{2^s}{2^s+1}(2^k-1)+1$ satisfies $1<s<n$ and $v_2(s)>v_2(k)$. The cross-correlation function is proved to be four-valued and its value distribution is completely determined. Several previously known binary cross-correlation functions are included in our result as special cases.

1 Introduction

The introduction frames complete cross-correlation distributions for short-period decimations as a problem with known results for only a few decimations across every shift. This paper treats a unified family of noncoprime Niho-type decimations, determines the distributions, and includes several earlier binary cases as special cases.

1 Introduction

  • Complete distributions for every shift l were known for only a few decimations, despite broader work on cross-correlation distributions for short-period sequences.Low-correlation sequences are used in spread-spectrum communications, CDMA, radar, and stream-cipher systems.Source: §1 · pp. 1–3
  • For n=2k, the paper studies the noncoprime Niho-type decimation under 1<s<2k and v2(s)>v2(k), unifying the two noncoprime branches of (1.1).For the d2 branch, the representation uses parameter s+k.Source: §1 · p. 3
  • The paper completely determines four-valued cross-correlation distributions for its Niho-type decimation and each associated short-period sequence.Its method avoids third- or higher-moment identities by combining root counting, a double-counting identity, and the first two moments.Source: §1 · p. 4
  • The counting method fixes a root, maps remaining roots to solutions of a linearized equation in the trace-one set, and uses double counting to determine a frequency.The remaining frequencies follow from the total frequency and first two moments.Source: §1 · p. 4
  • Results for the decimations in and the binary case of are included as special cases.Their corresponding parameters are s=k+t, s=2k−2, and s=k+1, respectively.Source: §1 · p. 4

2 Preliminaries

The preliminaries define the finite-field and sequence notation used in the analysis, then connect cross-correlation values to sparse-equation solution counts. Auxiliary root-count and finite-field results support the later distribution calculation.

2 Preliminaries

  • The decimated sequences {v_l(t)} have periods dividing L; when gcd(d, 2^n−1)=1, there is one sequence up to cyclic shifts.Its least period is exactly L when L > 1 and the multiplicative order of 2 modulo L is n.Source: §2 · pp. 5–6
  • The cross-correlation values are related to the number of solutions of sparse equations over finite fields.For fixed l, a is fixed while b runs through the nonzero elements of F2^n over a complete period.Source: §2 · p. 6
  • The auxiliary root-count result allows 0, 1, 2, or 2gcd(s,k)+1 distinct roots in S for the stated equation.The equation is x^(2^s+1) + ax^(2^s) + bx + c = 0 over F2^n.Source: §2 · p. 6
  • For δ satisfying the stated trace condition, exactly 2^(k−r)−1 nonzero c values make the referenced equation solvable in F2^k.Here r is introduced as gcd(s,k) in the surrounding notation.Source: §2 · pp. 7, 9

3 Four-valued cross-correlation functions

This section determines the frequencies of the four possible cross-correlation values for the specified decimations. It develops root-counting and direct-counting methods, using the first two moments to determine a key frequency without relying on the overall distribution or a third-moment calculation.

3 Four-valued cross-correlation functions

  • For every a,b ∈ F*_{2n}, Wd(a,b) ∈ {−2k, 0, 2k, 2k+r}.The possible values follow from the equation's having 0, 1, 2, or 2r+1 roots in S.Source: §3 · p. 11
  • For fixed a = α^l, determining the value frequencies reduces to counting b ∈ F*_{2n} by the number of roots N(a,b), which can be 0, 1, 2, or 2r+1.The section organizes these counts as A0(a), A1(a), A2(a), and A2r+1(a).Source: §3 · p. 12
  • When N(a,b) ≥ 1, the non-β roots in S correspond bijectively to solutions in V, reducing the maximal-root count to counting parameters whose associated equation has 2r solutions.For fixed a and β, parameters γ correspond bijectively to b for which β is a root, and the 2r+1-root condition is equivalent to having 2r solutions in V.Source: §3 · pp. 12, 15
  • For a = α^l with 0 ≤ l ≤ 2r, the condition āβ^{2s} + aβ = 0 has 2r+1 solutions β only when l = 0, and none when 1 ≤ l ≤ 2r.This count is used to determine A2r+1(a).Source: §3 · p. 20
  • For n = 2k and r = gcd(s, k), every distribution for 0 ≤ l ≤ 2r has exactly four values, with all four frequencies positive.Theorem 2 gives the value distributions for the l = 0 case and for 1 ≤ l ≤ 2r.Source: §3 · pp. 23–25
  • Theorem 2 includes the binary cross-correlation functions in as special cases with r = 1.The corresponding decimations arise by taking s = k + t, s = 2k − 2, or s = k + 1, respectively.Source: §3 · p. 25
  • When gcd(d, 2^n − 1) > 1, moment identities generally do not determine each fixed-l distribution separately, even if the overall distribution of W_d(a, b) is known.Earlier approaches in use the overall distribution and additional frequency information obtained through different methods.Source: §3 · p. 26
  • The method determines A_{2r+1}(a) directly for each a = α^l by counting admissible (b, β) pairs, then obtains the remaining frequencies from total frequency and the first two moments.It therefore requires neither the overall distribution of W_d(a, b) nor a third-moment calculation.Source: §3 · p. 26

4 Conclusion

The paper determines the cross-correlation distributions for the short-period decimations, establishing four-valued functions whose distributions separate the case l = 0 from 1 ≤ l ≤ 2^r. Its counting method evaluates the needed frequencies without moment identities.

4 Conclusion

  • Each cross-correlation function is four-valued, with one distribution class for l = 0 and another for 1 ≤ l ≤ 2^r.There are 2^r + 1 decimation sequences, each of period (2^n − 1)/(2^r + 1), where r = gcd(s, k).Source: §4 · p. 26
  • The results include previously known binary cross-correlation functions in as special cases.Source: §4 · p. 26
  • For each fixed a = α^l, the method fixes a root β and reduces the remaining root count to solutions of a linearized equation in the trace-one set V.Relating coefficient b to β yields a double-counting identity for admissible pairs (b, β), which determines A_{2^r+1}(a).Source: §4 · p. 27
  • The remaining frequencies follow from the total frequency and the first two moments, while A_1(a) and A_2(a) are also obtained directly and A_0(a) from the total frequency.The paper states that the distributions can be determined without using moment identities.Source: §4 · p. 27
Loading 2610.34010v1…