CS Paper Radar

Four New Single-Error-Correcting Binary Codes

Moshe Milshtein

cs.IT math.CO ·submitted 2026-10-16 15:33 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Three Improved Lower Bounds for Binary Error-Correcting Codes

cs.IT ·2026-10-08 ·Kazuki Ota, Takayuki Osa, Tatsuya Harada
theory similarity 0.74
Abstract

Error-correcting codes are a foundational technology for representing information robustly against noise in communication and data storage. The binary code packing problem, which seeks to maximize the number of codewords at a fixed code length and minimum distance, is a fundamental problem in coding theory that remains open for many parameter choices. We give explicit binary codes with parameters $(n,M,d)=(22,84,9)$, $(24,196,9)$, and $(25,65,11)$, where $n$, $M$, and $d$ denote the code length, number of codewords, and minimum distance, respectively. These establish the lower bounds $A_2(22,9)\ge84$, $A_2(24,9)\ge196$, and $A_2(25,11)\ge65$, where $A_2(n,d)$ denotes the maximum possible number of codewords, improving the respective lower bounds 80, 192, and 64 in the public table of general binary codes. Most notably, the third result improves the lower bound supplied by a lexicographic construction for the first time in 66 years, while the first two improve bounds that have stood for 21 years. The new codes represent more messages without changing the code length or error-correction guarantees, with gains compounding multiplicatively across blocks. We release all codewords and an exhaustive verifier to enable independent verification.

0.24

New lower bounds for constant-weight codes via seeded bit-swap tabu search

cs.IT math.CO ·2026-08-14 ·William Echols
similarity 0.69
Abstract

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $τ_{32}$, $τ_{33}$, $τ_{34}$, and $τ_{37}$.

0.40

Hamming and Johnson-Type Bounds for Joint Error Correction and Detection

cs.IT ·2026-11-13 ·Yulin Chen, Raymond W. Yeung
similarity 0.68
Abstract · This manuscript is a preliminary draft and is currently being revised. The final version will be posted once the revisions are complete. Com…

We derive upper bounds on the size of codes for joint error correction and detection over classical $q$-ary Hamming spaces. A $(c,c')$ joint error correcting and detecting code corrects every error of weight at most $c$ and detects every error whose weight lies between $c+1$ and $c+c'$. We establish equivalent conditions for this decoding requirement using Hamming balls and Hamming rings, and derive a joint bound that reduces to the Hamming bound when $c'=0$. We introduce joint perfect codes and show that binary repetition codes attain the joint bound whenever $n=2c+c'+1$. For codes satisfying $d_{\min}=2c+c'+1$, we investigate an alternative joint bound based on ring multiplicity and constant-weight code bounds. A further argument using the Cauchy-Schwarz inequality and pairwise ring intersections yields a refined joint bound that is always at least as strong as the original joint bound. We then incorporate an additional outer Hamming shell to obtain a Johnson-type extension. This extension provides a strict improvement for binary codes with $c'=1$, $d_{\min}=2c+2$, $c\geq2$, and $d_{\min}+2\leq n\leq3d_{\min}/2-1$. These results connect sphere-packing bounds with the geometry of joint error correction and detection.

0.13

New lower bounds for binary constant-weight codes from prescribed-automorphism search, and two quantum codes meeting their upper bounds

cs.IT math.CO ·2026-10-16 ·Chris Dzoba
theory similarity 0.66
Abstract · 12 pages. Code word lists, group generators, orbit representatives, two independent checkers, verification outputs, quantum stabilizers and …

We give explicit binary constant-weight codes that raise the lower bounds on $A(n,6,w)$ in eight cells of Brouwer's table, all now listed there. The first round (9 October 2026) gave four values: $A(27,6,11)\ge 19305$, $A(27,6,12)\ge 24453$, $A(28,6,10)\ge 18642$ and $A(28,6,9)\ge 11154$, together with an explicit $A(24,6,12)$ code of 5566 words, now in the table's list of lost codes. The second round (14 October 2026) gave seven values, listed in the table since 15 October 2026: $A(29,6,10)\ge 27183$, $A(29,6,11)\ge 42042$, $A(29,6,9)\ge 14781$, $A(28,6,10)\ge 19110$, $A(27,6,12)\ge 24804$, $A(28,6,9)\ge 11388$ and $A(27,6,13)\ge 27783$, three of which replace first-round values. Every code is a union of orbits of the semilinear affine group $\mathrm{AΓL}(1,27)$, its index-2 subgroup, or $\mathrm{AGL}(1,23)$, acting on all but at most two coordinates. The orbits were chosen by maximum-weight independent set search on the orbit conflict graph: branch and bound in the first round, iterated local search in the second. Each code was checked by two separately written programs over all pairs of words and was regenerated from its generators and orbit representatives. We also report two qubit stabilizer codes, $[[20,11,4]]$ and $[[43,32,4]]$, which raise the lower bounds of 3 listed at codetables.de to the listed upper bound 4.

0.23

Solutions to Three Conjectures and an Open Problem on Binary BCH Codes

cs.IT ·2026-09-01 ·Xiaoqiang Wang, Jiawei He, Boru Yi, Dabin Zheng
theory similarity 0.66
Abstract

BCH codes are among the most important classes of cyclic codes and have played a central role in coding theory and its applications. One of the fundamental problems in the study of BCH codes is to determine their exact minimum distances, which directly govern their error-correcting capability. Although the BCH bound provides a general lower bound, determining the exact minimum distance is often difficult, and many parameter families remain unresolved. In this paper, we investigate three conjectures and an open problem on binary BCH codes proposed by Chen, Xie, and Ding in \cite{Chen59}. We settle these conjectures on the exact minimum distances of three families of binary BCH codes by constructing codewords attaining the BCH bound. Beyond these conjectures, we further study the more difficult family codes and determine its minimum distance for some cases. We further study Open Problem 8.4: affirmative answers are obtained for the first two length families, while for the third family a sufficient condition is established and a counterexample shows that the unrestricted assertion does not hold in general.

0.20

Asymptotically Tight Bounds for Generalized Covering Radii of Binary Primitive BCH Codes at All Higher Orders

cs.IT ·2026-08-24 ·Zeev Vladimir Belinsky, Aryeh Lev Zabokritskiy
theoryhighly cited similarity 0.65
Abstract · 56 pages. Revised version with a componentwise degree bound improving the sufficient field-size threshold for the known common-core support …

We study the generalized covering radii of binary primitive BCH codes, which measure how many parity-check columns suffice to span several prescribed syndromes. For the four-error-correcting family of length $2^m-1$, the second radius is exactly $11$ for $m\geq55$, and it is either $11$ or $12$ for $m\geq16$. For every fixed error parameter at least two, we give an explicit stable bound with two adjacent possible values for the second radius and an arithmetic criterion for exactness. At every higher order, we obtain explicit lower and upper bounds whose additive gap is bounded independently of the order for each fixed error parameter, once explicit field-size conditions hold. The bounds are therefore asymptotically tight as the order grows. The higher-order upper bound retains the common-core support count established by Xiong, Yip, and Zullo; our refinement reduces its sufficient field-size threshold at large order. The refinement combines componentwise mixed degrees with the ordinary degree of a multicone. The upper bounds come from constructing syndrome representations with a common set of parity-check columns.

0.50

Extremal diagonal-coherent binary codes: shortened Hamming cores, deep holes, and the 64 I-Ching hexagrams

cs.DM math.COcs.IT ·2026-10-24 ·Jon-Lark Kim
similarity 0.64
Abstract · 24 pages

Each of the 64 hexagrams of the I-Ching, or Book of Changes, is a stack of six Yin-Yang lines and is therefore a binary vector of length 6; the eight hexagrams formed by repeating a single trigram span a doubled-trigram subspace $Δ$. We ask which binary $[6,3,3]$ codes are compatible with this trigram structure. We show that a $[6,3,3]$ code meets $Δ$ in at most four codewords, that the four are then forced to be the doubled trigrams Earth, Fire, Wind and Lake, and that exactly two codes attain this bound: the shortened Hamming code $\mathcal C_A$ and its dual. Since $\mathcal C_A$ has covering radius 2, its eight codewords, their radius-one balls, and its eight deep holes together reconstruct all 64 hexagrams. In general, we call a binary code of length $2m$ with $d \ge 3$ diagonal-coherent if it contains the half of the diagonal subspace $\{(u,u)\}$ coming from even-weight vectors $u$ -- the largest part of that subspace a single-error-correcting code can contain -- and extremal if its dimension is as large as possible. For $m\ge2$ and $r=\lceil\log_2(2m+1)\rceil$, we determine the number $N(m)$ of extremal diagonal-coherent codes with parameters $[\,2m,\ 2m-r,\ \ge3\,]$, show that diagonal coherence entails no loss of redundancy, and determine their minimum distances. We also put these codes in a normal form, determine their hulls, and show that each has covering radius $2$ with exactly $2^r-1-2m$ deep-hole cosets. Finally we propose three open problems.

0.25

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

cs.IT math.CO ·2026-10-16 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.63
Abstract

We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.

0.07