Code Size Constraints in b b -symbol Read Channels: A Bound Analysis
Gyanendra K. Verma, Nupur Patanker, Abhay Kumar Singh ∗ · 2025
Read Code Size Constraints in b b -symbol Read Channels: A Bound Analysis by Gyanendra K. Verma, Nupur Patanker, Abhay Kumar Singh ∗ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10088.txt.
Introduction
Gyanendra Verma, Nupur Patanker, and Abhay Singh extended code size bounds to reading heads that scan blocks of symbols at once, in a paper published in 2025. Classic codes guard each symbol alone, but real faults hit runs of symbols. Block reading heads model that pattern. The size limit for such codes, by length, distance, and symbol count, is the prize.
Earlier bounds served the two-symbol case. Their work lifts a set of them to any block size of two or more. The set spans linear programming bounds, chain rules, and two named limits. Their new lower bound from a classic method beats the earlier bound in shown cases. They also give a fresh route to two old limits. The work aids code design for storage, networks, and DNA storage, where block faults rule.
Catalog record
| CREATOR | Gyanendra K. Verma, Nupur Patanker, Abhay Kumar Singh ∗ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-10088
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Code Size Constraints in b b -symbol Read Channels: A Bound Analysis Thanks: 2010 Mathematics Subject Classification: 94B05, 11T71. *Corresponding author. Partial work was done while G. K. Verma was affiliated with the Department of Mathematics, Indian Institute of Technology Delhi. G. K. Verma is financially supported by UAEU grant G00004614. N. Patanker was supported in part by an IoE-IISc Postdoctoral Fellowship awarded by the Indian Institute of Science Bangalore, and in part by the grant DST/INT/RUS/RSF/P-41/2021 from the Department of Science & Technology, Govt. of India. Gyanendra K. Verma, Nupur Patanker, Abhay Kumar Singh ∗ Abstract . In classical coding theory, error-correcting codes are designed to protect against errors occurring at individual symbol positions in a codeword. However, in practical storage and communication systems, errors often affect multiple adjacent symbols rather than single symbols independently. To address this, symbol-pair read channels were introduced [ 1 ] , and later generalized to b b -symbol read channels [ 16 ] to better model such error patterns. b b -Symbol read channels generalize symbol-pair read channels to account for clustered errors in modern storage and communication systems. By developing bounds and efficient codes, researchers improve data reliability in applications such as storage devices, wireless networks, and DNA-based storage. Given integers q q , n n , d d , and b ≥ 2 b\geq 2 , let A b ( n , d , q ) A_{b}(n,d,q) denote the largest possible code size for which there exists a q q -ary code of length n n with minimum b b -symbol distance at least d d . In [ 4 ] , various upper and lower bounds on A b ( n , d , q ) A_{b}(n,d,q) are given for b = 2 b=2 . In this paper, we generalize some of these bounds to the b b -symbol read channels for b > 2 b>2 and present several new bounds on A b ( n , d , q ) A_{b}(n,d,q) . In particular, we establish the linear programming bound, a recurrence relation on A b ( n , d , q ) A_{b}(n,d,q) , the Johnson bound (even), the restricted Johnson bound, the Gilbert-Varshamov-type bound, and the Elias bound for the metric of symbols b b , b ≥ 2 b\geq 2 . Furthermore, we provide examples demonstrating that the Gilbert-Varshamov bound we establish offers a stronger lower bound than the one presented in [ 14 ] . Additionally, we introduce an alternative approach to deriving the Sphere-packing and Plotkin bounds. 1. Introduction In coding theory, the function A_{H}(n,d,q) represents the maximum number of codewords in a code of length n over an alphabet of size q with a minimum Hamming distance of at least d . Determining its exact value is a challenging problem, but various upper and lower bounds provide useful estimates. The Singleton Bound establishes a simple upper limit, while the Sphere Packing Bound and Plotkin Bound offer more refined constraints based on geometric considerations. The Linear Programming Bound provides even tighter estimates using optimization techniques. On the lower end, the Gilbert-Varshamov Bound guarantees the existence of codes with a certain minimum size, and the Griesmer Bound helps in understanding the length of linear codes. These bounds play a crucial role in designing efficient error-correcting codes, balancing redundancy and error detection capability to optimize communication systems. The b -symbol distance is a generalization of the Hamming distance that provides a more refined measure of differences between codewords, particularly in scenarios where errors tend to occur in bursts rather than independently at individual positions. In this metric, rather than counting all differing symbols between two codewords, the distance measure considers contiguous blocks of up to b -symbol as single units. Cassuto and Blaum [ 1 ] introduced symbol-pair distance (i.e. 2 -symbol distance) which is further generalized to b -symbol distance for b>2 by Yaakobi et al. [ 16 ] . These generalizations are motivated by the limitations of traditional high-density data storage systems, which do not permit the retrieval of individual symbols from the channel. The b -symbol coding framework enables the simultaneous reading of overlapping b -symbols instead of processing them separately. This innovative approach has garnered significant attention, leading to substantial progress in the study of b -symbol codes (see [ 3 , 6 , 7 , 8 , 12 ] ). Similar to Hamming distance, for the b -symbol distance, we have a quantity A_{b}(n,d,q) that for given integers n and d with 1\leq d\leq n , denotes the maximum number of codewords in a code over an alphabet of size q of length n and b -symbol distance at least d . Similar to its counterparts in the Hamming metric, the quantity A_{b}(n,d,q) plays an important role, and various bounds on its value have been determined. The b -symbol Sphere Packing Bound and Gilbert-Varshamov bound has been determined in [ 1 ] for b=2 and in [ 14 ] , the authors established Sphere Packing Bound and Gilbert–Varshamov Bound for b>2 . The b -symbol Singleton bound has been studied in [ 3 ] for b=2 and in [ 6 ] for b>2 . The Johnson Bound has been determined in [ 8 ] for even minimum pair-distance (binary alphabet) and in [ 4 ] for arbitrary minimum pair-distance. Linear Programming bound for b=2 has been derived in [ 8 ] , providing an optimization-based upper bound on code size. The Griesmer Bound, established in [ 11 ] , offers a lower bound on the length of linear codes given a b -symbol distance. The Sphere-Covering Bound, determined in [ 4 ] , evaluates how efficiently codewords can cover the space while maintaining the required b -symbol distance, while the Plotkin Bound, also derived in [ 4 ] , provides an upper limit on code size when the b -symbol distance is relatively large. Asymptotic Bounds on code size have been studied in [ 1 ] , [ 2 ] , [ 10 ] . Chen [ 5 ] studied covering codes and covering radii over b -symbol read channels. A code is considered optimal if it meets a given bound. In particular, when the minimum b -symbol distance of a code achieves the Singleton bound, it is referred to as a b -symbol maximum distance separable (MDS) code. Various constructions of b -symbol codes attaining specific bounds have been explored in [ 3 , 5 , 6 , 12 , 11 , 16 , 19 ] . In this paper, we extend the study of b -symbol codes by establishing several new upper and lower bounds on A_{b}(n,d,q) . While some of these bounds are entirely new, others serve as generalizations of existing results that were previously known only for the special case of b=2 . By broadening these bounds to arbitrary values of b , we provide a deeper understanding of the structure and limitations of b -symbol codes, which are particularly relevant for coding scenarios where errors tend to occur in bursts rather than independently at individual positions. A brief list of known bounds and the contribution of this paper is listed in Table