Source-linked AI summary
Three Improved Lower Bounds for Binary Error-Correcting Codes
Kazuki Ota, Takayuki Osa, Tatsuya Harada
TL;DR
For many binary code-packing parameters, a gap remains between the best-known constructions and theoretical upper bounds. The paper constructs explicit binary code sets and exhaustively compares all unordered pairs to verify their minimum distances. The constructions establish A2(22, 9) ≥ 84, A2(24, 9) ≥ 196, and A2(25, 11) ≥ 65; at unchanged block length and minimum distance, they support more messages.
Problem
For many binary code-packing parameters, a gap remains between the best-known constructions and theoretical upper bounds.
Source: §1 · p. 1Method
The paper constructs explicit binary code sets and exhaustively compares all unordered pairs to verify their minimum distances.
Source: §3 · p. 2Results
The constructions establish A2(22, 9) ≥ 84, A2(24, 9) ≥ 196, and A2(25, 11) ≥ 65; at unchanged block length and minimum distance, they support more messages.
Source: §3 · p. 2Takeaways & Limitations
Abstract
from arXiv · showhide
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.
1 Introduction
Error-correcting codes matter for communication and storage, yet many binary code-packing parameters still have gaps between known constructions and upper bounds. This paper improves three lower bounds and provides codewords and a verifier for independent checking.
1 Introduction
- Even small improvements in code construction can have practical implications at scale because codes affect communication and storage reliability and efficiency.Source: §1 · p. 1
- For binary code packing, explicit constructions improve three lower bounds: 84 codewords for (n, d) = (22, 9), 196 for (24, 9), and 65 for (25, 11).The previous lower bounds were 80, 192, and 64, respectively.Source: §1 · p. 1
- A lexicographic construction supplies a 64-codeword bound, which the cited passage dates to 1960; it does not specify the rejected 21-year duration.Source: §1 · p. 1
- At unchanged block length and minimum distance, more codewords represent more messages, and gains compound exponentially across blocks.All codewords and a short exhaustive verifier are provided for independent verification.Source: §1 · p. 1
2 Preliminaries
A binary code is a set of distinct fixed-length words separated by a minimum Hamming distance. This separation determines the guaranteed number of correctable bit errors, while code packing seeks to maximize the number of words.
2 Preliminaries
- A binary (n, M, d) code contains M distinct length-n binary words whose pairwise Hamming distances are at least d.Hamming distance counts coordinates at which two words differ.Source: §2 · p. 1
- For minimum distance d, nearest-neighbor decoding corrects any pattern of up to ⌊(d−1)/2⌋ bit errors.The length-5, four-word example has minimum distance 3, so it corrects any single-bit error; the illustrated two-bit error is decoded incorrectly.Source: §2 · p. 1, Figure 1 · p. 2
- Increasing the number of codewords at fixed length and minimum distance represents more distinct messages without weakening the error-correction guarantee.Source: §2 · p. 1
- The binary code-packing problem seeks the largest set of length-n words with pairwise distances at least d.Source: §2 · p. 2
3 Our Results
The paper establishes three improved lower bounds for binary code sizes using explicit sets whose pairwise distances were exhaustively checked. At unchanged length and minimum distance, these larger sets support more messages, with gains compounding across blocks.
3 Our Results
- A2(22, 9) ≥ 84, A2(24, 9) ≥ 196, and A2(25, 11) ≥ 65.The three complete sets have 84, 196, and 65 distinct words, with minimum distances 9, 9, and 11, respectively.Source: §3 · p. 2
- At unchanged block length and minimum distance, the 22-bit code supports (84/80)^k = 1.05^k times as many message sequences; 100 blocks (2,200 bits) support approximately 131 times as many, correcting any four bit errors per block.Source: §3 · p. 2
- For (22, 9), 100 blocks totaling 2,200 bits support approximately 131 times as many message sequences while guaranteeing correction of any four bit errors per block.For odd d, parity extension and puncturing also give lower bounds 84, 196, and 65 for (23, 10), (25, 10), and (26, 12).Source: §3 · p. 2
4 Verification and Explicit Codes
The paper supplies explicit codeword sets and checks them using exact integer arithmetic. The verifier checks set size, word range, and minimum pairwise distance.
4 Verification and Explicit Codes
- Each code is listed as whitespace-separated decimal integers representing n-bit words, padded with leading zeros and written most-significant bit first.Source: §4 · p. 2
- The Python verifier checks that there are M distinct in-range words and that every pair has distance at least d.It uses exact integer arithmetic and computes pairwise Hamming distances from XOR bit counts.Source: §4 · p. 2