Codes with Large Minimum Distance in Product Codes: Explicit Constructions and Bounds
This work provides practical constructions for blockchain data availability sampling, improving error correction in product codes.
The paper presents explicit constructions of subcodes of Reed-Solomon product codes that achieve optimal or near-optimal dimension-distance tradeoff, with field size linear in code length, and establishes a new upper bound on minimum distance for subcodes of product codes.
Products of MDS codes are of major practical importance; for a recent example, they are used in Data Availability Sampling (DAS) in blockchain networks such as Celestia and as part of the Ethereum roadmap. This motivates us to consider subcodes of such codes with the goal of obtaining a larger minimum distance. In this paper, we present explicit constructions of subcodes of Reed--Solomon product codes, along with bounds on their minimum distance. In particular, they achieve an optimal or near-optimal dimension--distance tradeoff. For component codes of dimension $r$, our construction requires a field whose size is bounded linearly by the overall product code length, and attains the maximum possible minimum distance for subcode dimensions $r^2-1$, $r^2-2$, and all dimensions at most $2r-1$. Furthermore, we establish a new upper bound on the minimum distance of subcodes of the product of two codes with identical parameters.