New codes reduce redundancy in error correction for large alphabets
Nonlinear fixed-distance codes via real lifts of moment configurations
Information TheoryDiscrete Mathematics
Summary
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.
What this means in practice
- •For digital communication engineers: Design codes with lower redundancy for systems needing fixed minimum error correction over large alphabets.
- •For data storage system architects: Construct efficient nonlinear codes improving reliability with reduced storage overhead for fixed error thresholds.
A theory result. No direct application yet.
Authors
Sergey Yekhanin
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.