Papers for

digital communication engineers

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.

Chordal construction improves lengths of column-twisted Reed Solomon codes

Chordal Construction of Column-Twisted Reed--Solomon Codes

Abstract: A $[n,k]_q$ Generalized Reed--Solomon (GRS) code can be represented, up to monomial equivalence, by a projective system consisting of $n$ points on a degree $(k-1)$ rational normal curve (RNC) $C_{k-1}$ in PG$(k-1,q)$. We use the term \textit{Column-Twisted Reed--Solomon (CTRS)} codes broadly for $[n,k]_q$ codes whose projective system contains at least $(k+2)$ points on a $C_{k-1}$ of PG$(k-1,q)$. By a chord of $C_{k-1}$, we mean a line which is either a tangent, a real secant, or an imaginary secant of $C_{k-1}$. Roth and Lempel constructed non-GRS MDS $[n,k]_q$ codes by considering projective systems consisting of $(n-1)$ points on $C_{k-1}$ together with a point on a tangent line. More recently, Liu et al. obtained non-GRS $[n, k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of points on a real secant. In the case when $q$ is odd, the length of these codes satisfies $k+4 \leq n \leq (q+3)/2$. In this article, we construct non-GRS $[n,k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of Galois conjugate points on an imaginary secant. For odd $q$, these codes have lengths satisfying $k+4 \le n\le (q+5)/2$, thereby improving both the attainable lengths and dimension ranges of previous TRS and CTRS constructions. In particular, our code attains the length $(q+5)/2$ for every $3\le k\le (q-3)/2$. We use a geometric argument to establish the non-GRS property of CTRS codes for the range $3\le k \le n-4$, while the traditional method of comparison with the Schur square of GRS codes proves the non-GRS property only for the narrower range $3\le k \le n/2$. We also determine the structure of the dual of any CTRS code.

Thu 22 OctInformation Theory
The gist
Certain error-correcting codes called Reed--Solomon codes are important for data transmission and storage but have known limitations in their structure and length. The authors used geometric ideas involving points and lines on specific curves to build new codes that can be longer and still maintain good error correction. These new codes go beyond previously known constructions by adding pairs of special points called Galois conjugates, improving code parameters. They also provided new ways to prove these codes differ from classical ones, expanding the understanding of code properties.
Open → 2610.31257v1

Binary error correcting codes achieve higher data protection limits

Four New Single-Error-Correcting Binary Codes

Abstract: We construct a $(16, 3072, 3)$-code, a $(17,6144,3)$-code, an $(18,12288,3)$-code and a $(19,24576,3)$-code. Consequently, we get four new lower bounds: $A(16,3) \geq 3072$, $A(17,3) \geq 6144$, $A(18,3) \geq 12288$ and $A(19,3) \geq~24576$. Each of the codes consists of a union of cosets of a linear code. The constructions are the result of a computer search executing a tabu search algorithm.

Fri 16 OctInformation Theory
The gist
Finding ways to protect data from mistakes during transmission or storage is important, and error-correcting codes help with this by detecting and fixing errors. This paper presents four new codes that improve the known limits on how many error-free messages can be sent using certain binary codes that fix single errors. The new codes were discovered by the authors using computer-based search methods. These advances help understand the capabilities of error-correcting codes in securing digital information.
Open → 2610.23626v1

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

Complete decoding method revealed for special error-correcting codes

Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes

Abstract: Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages: determining the minimum error weight associated with a syndrome $S$ and constructing an error vector attaining this minimum. We identify the former quantity with the minimum additive length of $S$ with respect to $\mathcal T$ and determine it exactly by the norm and the quadratic character of $\mathbb F_q$. We also determine the complete coset-weight distribution and recover the known covering radius $3$. For the constructive part, we use quadratic-character sums and Weil bounds to construct a coset leader for every syndrome of coset weight three. The resulting procedures give complete maximum-likelihood decoders.

Thu 17 SeptInformation Theory
The gist
The paper studies a particular family of error-correcting codes called Gashkov-Sidel'nikov codes used in digital communication. It shows how to break down the decoding problem into two parts: finding the smallest number of errors that caused a problem, and then fixing those errors exactly. The authors identify mathematical properties that let them do this efficiently and provide a full method for maximum-likelihood decoding, guaranteeing the best possible error correction.
Open → 2609.20402v1

Polynomial-time detection matches optimal threshold for square MIMO systems

Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold

Abstract: We prove that exact block recovery in the square Gaussian binary MIMO model can be achieved in polynomial time at the same first-order SNR threshold as exhaustive maximum-likelihood detection. Specifically, for $y=\sqrt{ρ/N}Hx^\star+w, \; x^\star\in\{\pm1\}^N,$ and independent standard Gaussian $H\in\mathbb R^{N\times N}$ and $w$, rounded linear MMSE followed by steepest single-bit descent recovers $x^\star$ with failure probability tending to zero, uniformly over every transmitted word and every $ρ\ge2\log N$, using $O(N^3)$ unit-cost exact-real arithmetic operations. The model is a special case of Gaussian random linear estimation, for which AMP state evolution and replica/MMSE formulas rigorously characterize fixed-parameter normalized performance. Those results predict the same $2\log N$ scale, but do not by themselves yield an all-coordinate guarantee in the dimension-dependent regime considered here. To the best of our knowledge, no prior work gives polynomial-time exact block recovery at the ML boundary for this setting; the closest prior square-system theorem, for the box relaxation, has first-order threshold $4\log N$. The proof places the rounded LMMSE estimate at sublinear Hamming distance from the truth, and then establishes, uniformly over every error set the local search can visit, that some wrong bit offers a quantified cost decrease while an objective barrier confines the search path. Conversely, if $0<ρ\le2\log N-\log\log N-s_N$ with $s_N\to\infty$ and $s_N=o(\log N)$, then a one-bit neighbor beats the transmitted word with probability tending to one, so even ML detection fails. Therefore, the statistical and polynomial-time exact-recovery thresholds coincide to first order in the stated arithmetic model.

Wed 16 SeptInformation Theory
The gist
Detecting the exact transmitted signals in certain wireless communication systems is often very slow or impossible to do quickly. The authors show that for square multiple-input multiple-output (MIMO) systems with Gaussian noise, it is possible to recover the exact transmitted signal in polynomial time at the same signal strength threshold as the best possible methods. They use a combination of rounding a linear estimate and a smart step-by-step bit flipping to find the original signal efficiently. This means the fastest known method can achieve exact recovery right up to where it becomes statistically possible.
Open → 2609.19405v1