Papers for

communications protocol developers

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.

MDS codes built on hyperelliptic curves for better error correction

MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves

Abstract: For every fixed genus $g\geq2$ and every $0<ρ<1$, we construct maximum distance separable (MDS) algebraic geometry codes over $\F_q$ for all sufficiently large odd squares $q$. Their parameters are $\bigl[n,\lfloorρn\rfloor,n-\lfloorρn\rfloor+1\bigr]_q$ with $n=\sqrt q+1+O_g(q^{1/4})$. The codes use full Riemann--Roch spaces on genus-$g$ hyperelliptic curves. They are not monomially equivalent to generalized Reed--Solomon (GRS) codes when $q$ is sufficiently large. An infinite subfamily has exact length $n=\sqrt q+2gq^{1/4}+1$.

Sun 1 NovInformation Theory
The gist
The authors developed a special kind of error-correcting code called MDS (maximum distance separable) codes using mathematical objects called hyperelliptic curves. These codes have lengths approximately the square root of the size of the alphabet used, which is unusual compared to existing codes. Their codes achieve optimal error correction parameters and are distinct from traditional Reed–Solomon codes when the alphabet size gets large enough. This work provides new ways to design codes that could improve data transmission and storage reliability.
Open → 2611.01546v1

Bounds for changing codes without full decoding help nonlinear coding

Entropy/Length Profile Bounds for the Conversion of (Non)linear Codes in the Merge Regime

Abstract: Code conversion changes the parameters of encoded data while avoiding complete decoding and re-encoding. Existing general bounds largely rely on the algebraic structure of linear codes. This paper develops an information-theoretic framework for nonlinear code conversion in the merge regime. Using the entropy/length profile (ELP), we derive upper bounds on the number of unchanged symbols and lower bounds on the number of read symbols for arbitrary $(n,M)_q$ codes, without assuming linearity or requiring $\log_q M$ to be an integer. We also obtain joint bounds for multiple initial codes and consequences involving minimum distance. For linear codes, the proposed bounds reduce to the corresponding generalized Hamming weight (GHW) bounds. The construction based on Hamming codes converts Hamming codes of redundancy two into a Hamming code of any larger redundancy and simultaneously attains the general bounds on unchanged and read symbols. The construction based on quasigroups shows that new bounds remain tight for genuinely nonlinear codes of nonintegral dimension and at a nonintegral entropy threshold, which, to the best of our knowledge, is the first construction of convertible codes for nonlinear codes.

Sun 11 OctInformation Theory
The gist
Sometimes when you have encoded (compressed or protected) data, you want to change how it's encoded without fully decoding and re-encoding it. Existing methods mostly work only for special 'linear' codes. This paper by the authors creates a new way to understand and limit how much of the code you need to read or keep the same when changing between arbitrary codes, including nonlinear ones. They also show examples where their limits are as tight as possible, even for nonlinear codes.
Open → 2610.15252v1