Papers for

data storage system architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

New codes reduce redundancy in error correction for large alphabets

Nonlinear fixed-distance codes via real lifts of moment configurations

Abstract: Let $A_q(n,d)$ denote the largest size of a code of length $n$ and minimum Hamming distance $d$ over an alphabet of $q$ symbols. For fixed $q\ge2$ and $d\ge4$ we construct codes with redundancy $n-\log_q A_q(n,d)\le(d-3)\log_q n+O(\sqrt{\log n})$ for all large $n$. No algebraic structure is imposed on the alphabet, and the codes are not linear. For $d=4$ and $d=5$ the coefficient of $\log_q n$ matches the Hamming bound, so the redundancy is determined up to lower-order terms. At distance four the codes are provably better than every linear code: by the polynomial-method bound for cap sets, $\mathbb{F}_q$-linear codes with $q>2$ require a strictly larger coefficient in front of $\log_q n$. The construction imposes moment checksums over an auxiliary finite field, as BCH codes do, but one fewer than the distance would normally require. The affine-line theorem from prior work describes the dependencies left by these checks. We exclude them by placing the code positions inside a specially structured subset of the field, built from Behrend's sphere construction with the help of algebraic number theory.

Wed 14 OctInformation TheoryDiscrete Mathematics
The gist
Error-correcting codes help detect and fix mistakes in data transmission or storage. The authors design new error-correcting codes that can handle a fixed minimum number of errors more efficiently, meaning they use fewer extra symbols to do so, especially as the data grows longer. Their codes are not restricted to special algebraic structures and improve on known limits for certain distances. They achieve this by cleverly combining checksums with special arrangements of code positions derived from number theory and geometry.
Open → 2610.19960v1