Improved binary codes enable more robust data transmission
Three Improved Lower Bounds for Binary Error-Correcting Codes
Information Theory
Summary
Error-correcting codes help protect information when it is sent or stored, by allowing errors to be detected and fixed. The authors provide new examples of such codes that can hold more messages than previous known codes of the same length and error-correcting ability. These new codes improve longstanding records, one for the first time in over 60 years and two others after 21 years. Their work means that data can be packed more efficiently for the same level of error protection.
What this means in practice
- •For communication engineers: Design communication systems that transmit more data reliably without increasing code length or reducing error correction.
- •For data storage designers: Create storage solutions that store more information with the same reliability using improved binary codes.
Authors
Kazuki Ota, Takayuki Osa, Tatsuya Harada
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.