PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes

Roee Gross, Yitzchak Grunbaum, Matteo Bertuzzo, Eitan Yaakobi, Alberto Ravagnani

arXiv:2610.07370v1cs.ITmath.IT

TL;DR

Coverage depth measures the expected random reads needed to recover stored information, but identifying optimal codes when MDS codes do not exist remains open for many parameter regimes. The paper develops an expectation formula and uses coding-theoretic arguments to establish optimality results and analyze random linear codes. It shows that random linear codes have a bounded additive gap from the MDS benchmark at constant rate.

  • Problem

    The paper asks which linear codes minimize expected random-sampling coverage time, especially in parameter regimes where MDS codes do not exist.

    Source: §I · pp. 1–2

  • Method

    The paper derives a general expectation formula and proves code optimality results, while separately deriving an exact expected coverage-depth expression for random linear codes.

    Source: §V · p. 12, §VI · p. 14, §VII · p. 17

  • Results

    The q-ary simplex, first-order Reed–Muller, and q-ary Hamming codes are shown optimal in their stated settings, while random linear codes have bounded additive gap from MDS at constant rate.

    Source: §V · p. 12, §VI · p. 14, §VII · p. 20

  • Takeaways & Limitations

    Random linear codes' coverage depth approaches the MDS bound at constant rate, while coverage depth and optimality remain open for many other important code families.

    Source: §VIII · p. 21

    Coverage depth and optimality remain undetermined for many other important code families.

    Source: §VIII · p. 21

Abstract

from arXiv · show

DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the $q$-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the $q$-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.

I. Introduction

DNA storage retrieval depends on randomly sampled reads, making coverage depth—the reads needed for recovery—a key efficiency concern. The paper studies optimal code choices beyond MDS regimes and analyzes random linear codes.

I. Introduction

  • For DNA coverage, the goal is to minimize expected reads until all k information strands are retrieved, unlike random-access recovery of one specified strand.The DNA storage pipeline samples strands randomly during readout.Source: §I · pp. 1–2
  • Reducing coverage depth targets a DNA-sequencing bottleneck associated with slow throughput and high costs.Coverage depth is the ratio of sequenced reads to designed DNA strands.Source: §I · p. 1
  • MDS codes minimize expected reads when they exist, while prior work studied closed-form coverage expectations for several non-MDS code families.Prior analyses included q-ary simplex, Hamming, first-order Reed–Muller, and ternary Golay codes.Source: §I · p. 2
  • The paper establishes optimality of q-ary simplex, first-order q-ary Reed–Muller, and q-ary Hamming codes for parameter choices without MDS codes.Kong et al. [30] independently established the simplex-code optimality result during preparation of this manuscript.Source: §I · p. 2
  • For random linear codes, the paper derives an exact expected coverage-depth expression and tightens the constant-rate additive-gap upper bound from [21] by a factor of two.The work also reports the same linear-in-n gap result in the constant-redundancy regime as [21].Source: §I · p. 2

II. Preliminaries

Coverage time is the number of randomly sampled generator-matrix columns needed to span the information space, and coverage depth is its expectation. The section frames the optimization problem and recalls the MDS benchmark and established code-family results.

II. Preliminaries

  • Coverage time is the minimum number of sampled columns needed to span F_q^k, and coverage depth is its expected value.Columns are drawn uniformly at random with repetition.Source: §II · p. 3
  • The optimal coverage-depth problem asks, for given n, k, and q, for the minimum expected coverage time and a code attaining it.In DNA storage, random molecular sampling motivates minimizing the expected samples needed for recovery.Source: §II · p. 3
  • The general lower bound is attained with equality exactly by MDS codes, solving the optimization problem whenever such a code exists.Prior work also established closed-form expectations for several code families, and this paper states simplex- and Hamming-code optimality results.Source: §II · pp. 3–4

III. A General Formula for the Expectation

This section develops an expectation formula by organizing coverage as a chain of dimension-increasing subspaces. It applies the framework to first-order q-ary Reed–Muller codes to obtain a simpler expectation formula than an earlier one.

III. A General Formula for the Expectation

  • The general formula is intended to yield a lower bound and is applied in Section IV to prove simplex-code optimality.Its stated scope is the expected number of reads needed to recover stored information.Source: §III · p. 4
  • A coverage process can be represented as a chain of subspaces whose successive dimension increases correspond to drawing linearly independent columns.The section gives the probability that a particular next subspace is reached from the current one.Source: §III · p. 4
  • Theorem III.2 gives a general expression for the expected number of draws required to span the space.The derivation sums over possible subspace-chain configurations and their waiting times.Source: §III · p. 5
  • Applying the formula to first-order q-ary Reed–Muller codes yields a significantly simpler expectation formula than [29, Theorem 7.3].For the code's column distribution, p_G(V_j) = q^(j−1−m) for the stated nonzero chain subspaces.Source: §III · pp. 6–7

IV. Optimality of the 𝑞-ary Simplex Code

The section proves a general lower bound for expected coverage time and characterizes equality. It then shows that the q-ary simplex code attains the bound, with equality cases corresponding to codes monomially equivalent to it.

IV. Optimality of the 𝑞-ary Simplex Code

  • Theorem IV.1 establishes a general lower bound on expected draws to span the space, with equality exactly when p(0)=0 and the induced distribution on projective points is uniform.This equality characterization is translated into the coding-theory setting to prove simplex-code optimality.Source: §IV · p. 7
  • The q-ary simplex code is optimal for coverage depth because its generator matrix contains exactly one nonzero representative of every one-dimensional subspace.The proof uses the fact that each projective point appears exactly once among its generator-matrix columns.Source: §IV · pp. 11–12
  • Every optimal code with these parameters is monomially equivalent to the q-ary simplex code.The equality conditions force no zero columns and exactly one representative of every projective point.Source: §IV · p. 12

V. Optimality of First-Order 𝑞-ary Reed–Muller Codes

The first-order q-ary Reed–Muller code is coverage-depth optimal. Its proof reduces the process after the first nonzero column to a quotient-space problem one dimension smaller.

V. Optimality of First-Order 𝑞-ary Reed–Muller Codes

  • The first-order q-ary Reed–Muller code attains the coverage-depth lower bound, with E[R] = 1 + n/(n−1)E[S_m].Source: §V · pp. 12–13
  • After the first nonzero column, spanning the full space reduces to spanning a quotient of dimension one less.Source: §V · p. 12
  • For any full-rank matrix, the nonzero projected columns require at least the simplex code's coverage depth E[S_m] to span the quotient.Source: §V · p. 13
  • The Reed–Muller matrix has no zero columns and yields each projected direction once, so its projected process attains the simplex bound.Source: §V · p. 13

VI. Optimality of the 𝑞-ary Hamming Code

The q-ary Hamming code minimizes expected coverage time among linear codes with the same length and dimension. The proof turns the expectation into a dual-code counting problem, then uses a matroid basis polynomial and its log-concavity.

VI. Optimality of the 𝑞-ary Hamming Code

  • The q-ary Hamming code minimizes expected coverage time among linear codes of the same length and dimension.Source: §VI · pp. 14, 16
  • The expectation formula reduces minimization to maximizing independent t-subset counts among columns of the dual code.Source: §VI · p. 14
  • Complete log-concavity and the transitive GL(r,q) action show the polynomial is maximized at uniform multiplicities.Source: §VI · pp. 15–16
  • The basis generating polynomial evaluated at column-direction multiplicities counts independent column subsets; the simplex matrix has uniform multiplicity one.Source: §VI · p. 15

VII. Uniformly Random Codes

The paper characterizes the average coverage depth of uniformly sampled full-rank matrices and compares it with the MDS benchmark. In the constant-rate regime, the ensemble-average additive gap is bounded, with an explicit constant half the one stated in [21].

VII. Uniformly Random Codes

  • The expected coverage depth is characterized exactly for a matrix sampled uniformly from all full-rank k×n matrices.The expectation is over both the matrix choice and the column-sampling process.Source: §VII · pp. 17–18
  • The analysis relates coverage time to the number of distinct sampled column indices, whose waiting time follows a partial coupon-collector process.The first t distinct indices are treated as a uniformly random ordered tuple, using permutation invariance of the matrix distribution.Source: §VII · pp. 17–18
  • The first term in the derived expectation is the coverage depth of an MDS code, providing the benchmark for the additive-gap analysis.The MDS benchmark follows because every k distinct columns of an MDS generator matrix are linearly independent.Source: §VII · pp. 18–19
  • In the constant-rate regime, the random-code ensemble’s average additive gap from the MDS benchmark is bounded, with a constant half the one stated in [21].The result applies to the average over full-rank matrices, rather than only identifying a favorable code.Source: §VII · pp. 20–21

VIII. Summary and Open Problems

The paper establishes optimality of q-ary Simplex and Hamming codes for their respective parameters, beyond the cases where MDS codes exist. It also notes that optimality for many other code families remains open.

VIII. Summary and Open Problems

  • The q-ary Simplex and Hamming codes are optimal for their respective parameters, alongside the known optimality of MDS codes whenever they exist.The paper identifies further code families and parameter regimes whose coverage depth can be determined.Source: §VIII · p. 21
  • In the constant-rate regime, random linear codes’ coverage depth approaches the MDS bound, while optimality for many other important code families remains open.The paper points to characterizing additional structured families and identifying structural conditions for optimality as future directions.Source: §VIII · p. 21
  • A broader characterization of the structural conditions that make codes optimal for coverage depth remains a direction for future work.Source: §VIII · p. 21
Loading 2610.07370v1…