PaperlayerView exact revision on arXiv

Source-linked AI summary

On optimal (v,5,3,1) optical orthogonal codes

Laura Johnson, Lorenzo Mella, Anita Pasotti, Emma Smith

arXiv:2610.30003v1math.COcs.ITmath.IT

TL;DR

The paper addresses the problem of bounding the size of (v, 5, 3, 1)-OOCs, where distinct correlation limits make the case worth investigating. It proves a sharp bound and gives constructions, including cyclotomic constructions for prime orders that yield perfect codes under stated conditions.

  • Problem

    The paper asks for a sharp size bound for (v, 5, 3, 1)-OOCs, a case motivated by the role of small, distinct correlation limits in communication and code size.

    Source: §1 · p. 2

  • Method

    The paper proves a bound and develops direct and recursive constructions, including a cyclotomic construction using discrete logarithms and a tiling problem.

    Source: §1 · p. 2, §4 · p. 12

  • Results

    The size bound is either ⌈v/10⌉ or ⌊v/10⌋, and stated cyclotomic conditions yield perfect (p, 5, 3, 1)-OOCs for primes p ≡ 1 (mod 10).

    Source: §1 · p. 2, §2 · p. 5, §4 · p. 16

  • Takeaways & Limitations

    Under the stated cyclotomic conditions, the construction gives prime-order codes whose differences cover all nonidentity elements of Zv.

    Source: §4 · p. 16

    The cyclotomic construction described here is restricted to prime orders p satisfying its stated conditions.

    Source: §4 · p. 12

Abstract

from arXiv · show

In this paper, we establish a tight upper bound for the size of a $(v,5,3,1)$ optical orthogonal code (OOC) and call such a code optimal when it achieves this upper bound. In addition, if an optimal OOC has the property that all non-identity elements of $\mathbb{Z}_v$ are covered by the list of differences of its codeword-sets then it is called perfect. In this paper, we present direct and recursive constructions for infinite classes of optimal and perfect $(v,5,3,1)$-OOCs.

1 Introduction

The paper studies optical orthogonal codes as collections of subsets of a cyclic group, with correlation limits constraining their differences. It focuses on the challenging (v, 5, 3, 1) case, establishing a size bound and constructions for codes that attain it.

1 Introduction

  • A (v, k, λa, λc)-OOC is a collection of k-subsets of Zv whose translates satisfy autocorrelation and cross-correlation limits.The two correlation parameters can differ; when both equal λ, the code is denoted a (v, k, λ)-OOC.Source: §1 · p. 1
  • Low autocorrelation enables correct asynchronous decoding, low cross-correlation prevents user collisions, and larger code size supports more users at a given bandwidth.The paper motivates investigating OOCs with small, distinct correlation parameters.Source: §1 · p. 2
  • Earlier work established sharp size bounds for (v, 4, 2, 1)- and (v, 5, 2, 1)-OOCs, motivating study of the (v, 5, 3, 1) case.The cited bounds are either the ceiling or floor of v/8 and v/12, respectively.Source: §1 · p. 2
  • The paper establishes a sharp size bound for (v, 5, 3, 1)-OOCs and presents direct and recursive constructions for optimal and perfect codes.It also connects optimal codes to graph labellings and difference families over graphs.Source: §1 · p. 2

2 A bound on the maximum possible size of a (v, 5, 3, 1)- OOC

The section proves a sharp size bound by classifying possible difference patterns for 5-subsets of Zv and counting their types. It also identifies small-order optimal codes, including a perfect example at v = 37.

2 A bound on the maximum possible size of a (v, 5, 3, 1)- OOC

  • The bound uses the fact that each codeword-set has type at least 7, with at most one odd-type set and at most two type-8 sets.Type counts are the sizes of difference supports; counting their contributions yields the general size bound.Source: §2 · pp. 3, 5
  • For a (v, 5, 3, 1)-OOC of size s, Theorem 2.5 bounds s by ⌈v/10⌉ when v ≡ 8 (mod 40), 9 (mod 90), 108 (mod 180), or 216 (mod 360), and by ⌊v/10⌋ otherwise.The proof finds at most 3 codeword-sets of type less than 10 and derives 10q + r + 6 ≥ 10s, hence s ≤ q + 1.Source: §2 · p. 5
  • Type-10 codeword-sets are classified into six forms, with conditions on element order or divisibility of v specifying when each form applies.These forms include {0, x, −x, 3x, −3x} for ord(x) ≥ 11 and ord(x) ≠ 12, and {0, x, 2x, 4x, 5x} for ord(x) ≥ 11.Source: §2 · p. 6

2.1 Optimal (v, 5, 3, 1)-OOC of small order

  • Optimal (v, 5, 3, 1)-OOCs exist for v ∈ {12, 13, 14, 15, 16, 17, 18, 19, 29, 37, 39}, using blocks from optimal (v, 5, 2, 1)-OOCs.For these orders, the earlier codes have size ⌊v/12⌋ = ⌊v/10⌋, matching the bound here.Source: §2.1 · p. 8
  • At v = 37, three specified blocks form a perfect (37, 5, 3, 1)-OOC because a code with four blocks cannot exist.Source: §2.1 · p. 8

3 Cycle/bull/tadpole difference families and (v, 5, 3, 1)- OOCs

The section relates optimal (v,5,3,1)-OOCs to good difference families built from cycle, bull, and tadpole graphs. Under stated difference-family conditions, these constructions yield optimal codes, and good cycle difference families also yield perfect codes.

3 Cycle/bull/tadpole difference families and (v, 5, 3, 1)- OOCs

  • The paper describes optimal OOCs through suitable cycle labelings, equivalently bull or tadpole labelings.Source: §3 · p. 9
  • A (mv,m,Γ,1)-difference family consists of Γ-isomorphic blocks whose differences cover each element outside the specified multiples of v exactly once.For m = 1, the definition reduces to a (v,Γ,1)-difference family, with a stated necessary condition v ≡ 1 (mod 2|E(Γ)|).Source: §3 · p. 10
  • For a specified type-10 5-subset, good difference families based on C5, the bull graph, and either tadpole graph are equivalent because their difference lists coincide.The subset given in the passage is {0,x,−x,3x,−3x}.Source: §3 · p. 10
  • A good (mv,m,Γ,1)-difference family with 1 ≤ m ≤ 5 or m = 7, for the listed cycle, bull, or tadpole graphs, yields an optimal (mv,5,3,1)-OOC.The same optimality conclusion holds for the graphs associated with the specified 5-subset in Figure 5.Source: §3 · pp. 10–11
  • A good (v,C5,1)-difference family yields a perfect (v,5,3,1)-OOC.Source: §3 · p. 11

4 Cyclotomic constructions for perfect (p, 5, 3, 1)-OOCs with p prime

This section develops cyclotomic constructions for optimal and perfect (p, 5, 3, 1)-OOCs, using cyclotomic classes and partial tilings and giving conditions for perfect families based on two codeword-set forms. It also identifies, for each of i = 2 and i = 3, the smallest prime p for which such a code can be generated.

Cyclotomic construction

  • A solution to a discrete-log tiling problem yields an OOC by scaling the base codeword-set across cyclotomic classes, with n|T| codewords under Proposition 4.2’s hypotheses.For w = 5, λa = 3, and |S| = 5, an optimal or perfect tiling solution gives an optimal or perfect OOC when nr < 5.Source: §4 · pp. 12–13

Existence conditions

  • For p ≥ 31, no perfect (p, 5, 3, 1)-OOC exists if 5·6^-1 lies in D_5^0, p is not 1 modulo 50, and 144 is not a fifth power modulo p.Proposition 4.7 provides a congruence for the number of codeword-sets of each difference type, which yields this nonexistence criterion.Source: §4 · pp. 14–15

First perfect family

  • For p ≡ 1 (mod 10), Theorem 4.10 gives a perfect OOC when 2 lies in the specified zero cyclotomic class of order 5^i for some i from 1 to r.Here 5^r is the largest power of 5 dividing p − 1; the construction uses codeword-sets of the form {0, u, −u, 3u, −3u}.Source: §4 · pp. 15–16
  • In GF(211), the first family gives a perfect OOC with 21 blocks of the form {0, u, −u, 3u, −3u}.The example uses 2 as a multiplicative generator of GF(211).Source: §4 · p. 16

Second perfect family

  • For the form {0, u, 2u, −2u, 3u}, Theorem 4.13 likewise guarantees a perfect OOC under its stated cyclotomic condition on 2.The finite-field examples with p < 1000 include p = 11, 421, and 701.Source: §4 · p. 17

4 Cyclotomic constructions for perfect (p, 5, 3, 1)-OOCs with p prime

  • For i = 2 and i = 3, the table gives the smallest p for which a (p, 5, 3, 1)-OOC can be generated.Source: §4 · p. 18

5 A recursive construction

The section gives a recursive product construction for optimal or perfect (v, 5, 3, 1)-OOCs, with conditions that yield infinite families of new codes.

Proposition 5.1

  • A perfect (v, 5, 3, 1)-OOC with blocks of one of three specified forms combines with a perfect or optimal (w, 5, 3, 1)-OOC when gcd(w, 30) = 1 to produce a perfect or optimal code of length vw.The output is perfect when the second input is perfect, and optimal when it is optimal.Source: §5 · p. 18

Proof

  • The construction forms C3 from translated blocks Cy and C4 from scaled blocks vB, then takes their union.The block formulas depend on which of the three permitted forms the first input blocks have.Source: §5 · p. 18
  • The construction verifies that differences from C3 avoid the subgroup H containing C4’s supports, separating those two parts of the union.For each Cy, its differences lie in a non-trivial coset of H.Source: §5 · pp. 18–19
  • Differences from distinct C3 blocks are disjoint because the input blocks separate the relevant multiples into distinct cosets of H.When the multiples coincide, equality of differences requires the same y; otherwise the input blocks exclude equality up to sign modulo v.Source: §5 · p. 19

Corollary 5.2

  • A specialized corollary uses blocks of the form {0, x, −x, 3x, −3x} and requires gcd(w, 6) = 1 for the product construction.The second input may be perfect or optimal, yielding the corresponding product code.Source: §5 · p. 19

Examples 5.3

  • The construction gives a perfect (121, 5, 3, 1)-OOC and an optimal (143, 5, 3, 1)-OOC in the stated examples.The examples use the perfect (11, 5, 3, 1)-OOC as a first input, with second inputs of lengths 11 and 13, respectively.Source: §5 · p. 19

Examples 5.4–5.5

  • Further examples produce optimal (539, 5, 3, 1)-OOCs and optimal (847, 5, 3, 1)-OOCs.Their input lengths are 11 × 49 and 11 × 77, respectively.Source: §5 · pp. 20–21

Remark 5.6

  • Combining Proposition 5.1 with previously constructed perfect-code classes ensures an infinite family of new codes.The earlier classes use blocks of the first two forms in Proposition 5.1.Source: §5 · pp. 18, 21
Loading 2610.30003v1…