Lower Bounds for Error Coefficients of Griesmer Optimal Linear Codes via Iteration

Chaofeng Guan, Shitao Li, Gaojun Luo, Zhi Ma, Hong Wang · 2025

Read Lower Bounds for Error Coefficients of Griesmer Optimal Linear Codes via Iteration by Chaofeng Guan, Shitao Li, Gaojun Luo, Zhi Ma, Hong Wang (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-2507-05567.txt.

Introduction

Among codes that all meet the same best-possible length bound, some still fail less often than others. Chaofeng Guan and co-authors study that tiebreaker in a 2025 paper. The measure is the error coefficient, the count of lightest codewords, which sets the error floor on a noisy channel under best decoding.

Proving how small that count can be is hard, and the standard linear programming bound often falls short. The authors build several iterative lower bounds for codes that meet the Griesmer bound. For binary codes of dimension up to five, the bounds are tight in most cases. Where they are not, the gap to the true value stays at two or less.

Catalog record

CREATORChaofeng Guan, Shitao Li, Gaojun Luo, Zhi Ma, Hong Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05567

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower Bounds for Error Coefficients of Griesmer Optimal Linear Codes via Iteration Chaofeng Guan, Shitao Li, Gaojun Luo, Zhi Ma, Hong Wang Abstract The error coefficient of a linear code is defined as the number of minimum-weight codewords. In an additive white Gaussian noise channel, optimal linear codes with the smallest error coefficients achieve the best possible asymptotic frame error rate (AFER) among all optimal linear codes under maximum likelihood decoding. Such codes are referred to as AFER-optimal linear codes. The Griesmer bound is essential for determining the optimality of linear codes. However, establishing tight lower bounds on the error coefficients of Griesmer optimal linear codes is challenging, and the linear programming bound often performs inadequately. In this paper, we propose several iterative lower bounds for the error coefficients of Griesmer optimal linear codes. Specifically, for binary linear codes, our bounds are tight in most cases when the dimension does not exceed 5 5 . To evaluate the performance of our bounds when they are not tight, we also determine the parameters of the remaining 5-dimensional AFER-optimal linear codes. Our final comparison demonstrates that even when our bounds are not tight, they remain very close to the actual values, with a gap of less than or equal to 2 2 . I Introduction Let q be a prime power and \mathbb{F}_{q} denote the finite field of q elements. An [n,k]_{q} linear code C is a k -dimensional linear subspace of \mathbb{F}_{q}^{n} . The vectors in C are called codewords. The Hamming weight of a codeword \mathbf{c}\in C is defined as the number of nonzero coordinates in \mathbf{c} . The minimum Hamming weight of a linear code C is the smallest Hamming weight among all nonzero codewords in C . A linear code C with minimum Hamming weight d is denoted as an [n,k,d]_{q} linear code 1 1 1 For a linear code, its minimum Hamming weight is equal to its minimum Hamming distance. . An [n,k,d]_{q} linear code encodes k information bits into an n -bit codeword. This code can correct up to \left\lfloor(d-1)/2\right\rfloor bit errors. Given n and k , a larger d provides stronger error-correcting capabilities. When n and d are fixed, a larger k results in a higher code rate k/n , thereby improving system efficiency. Due to the interdependent relationships among the three parameters n , k , and d , establishing bounds for linear codes has always been a central issue in classical coding theory. The well-known bounds include the Singleton bound [ 1 ] , the Griesmer bound [ 2 ] , the Plotkin bound [ 3 ] , and the linear programming bound [ 4 ] . These bounds have guided the construction of many optimal linear codes that achieve these limits [ 5 , 6 , 7 , 8 ] . In practice, linear codes with the same parameters n , k , and d may have different frame error rates (FER) denoted by P_{e} . According to [ 9 ] , for the additive white Gaussian noise (AWGN) channel, the FER P_{e} of an [n,k]_{2} linear code C under maximum likelihood (ML) decoding satisfies P_{e}\simeq A_{d}(C)Q\left(\sqrt{\frac{2dkE_{b}}{nN_{0}}}\right),\quad\frac{E_{b}}{N_{0}}\rightarrow\infty, (1) where \simeq denotes asymptotic equality, Q(x)\triangleq\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{t^{2}}{2}}dt , E_{b}/N_{0} is the signal-to-noise ratio (SNR), and A_{d}(C) is the number of minimum-weight codewords in C . If a code C has the largest minimum distance d and the smallest error coefficient A_{d}(C) among all [n,k]_{q} linear codes, then C achieves the lowest asymptotic frame error rate (AFER) among all optimal linear codes under ML decoding. Therefore, the value of A_{d}(C) is also an important parameter for linear codes. An [n,k,d]_{q} linear code with the smallest A_{d}(C) is called AFER-optimal [ 10 ] . In modern coding theory, Arıkan discovered polar codes [ 11 ] in 2009. Due to their excellent performance, polar codes were selected as the coding scheme for the 5G control channel. Subsequently, Arıkan proposed polarization-adjusted convolutional (PAC) codes [ 12 ] , a variant of polar codes. He demonstrated that PAC codes perform remarkably close to the Polyanskiy-Poor-Verdú bound [ 13 ] over the binary input additive white Gaussian noise (AWGN) channel in the low-to-moderate signal-to-noise ratio (SNR) regime. The minimum distances and error coefficients also affect the performance of polar and PAC codes. Many efforts have been made to optimize these parameters to enhance their performance [ 14 , 15 , 16 , 17 , 18 ] . Classical and modern coding theories are interconnected. For example, polar codes are subcodes of Reed-Muller codes [ 19 ] . Lin et al. [ 20 ] demonstrated that binary linear codes can be converted into polar codes. As a result, binary linear codes can also be decoded using polar decoding techniques [ 21 , 22 ] . The MacWilliams formula [ 23 ] uses the weight enumerator to determine bounds on the error coefficients of linear codes through linear programming or polynomial methods. In 2021, Solé et al. [ 24 ] proposed a new linear programming bound for the lower and upper limits of the error coefficients of linear codes. Later in [ 10 , 25 ] , Abdullah and Mow constructed many Griesmer optimal binary linear and PAC codes that achieve Solé’s lower bound. However, the linear programming bound in [ 24 ] often fails to provide tight bounds in many scenarios [ 10 , 25 ] . Moreover, it requires complex calculations and can only compute linear codes for specific parameters. In [ 26 ] , Li et al. established two bounds on the error coefficients of linear codes through shortening and extension, constructed several classes of AFER-optimal binary codes, and resolved conjectures in [ 10 ] . Using the classification in [ 27 ] , they also determined the parameters of all binary AFER-optimal linear codes up to length 13 . For Griesmer optimal cases, the lower bounds on the error coefficients of linear codes are still not well determined. Therefore, more powerful bounds are needed to determine the AFER-optimal property of linear codes . This motivates us to investigate bounds on linear codes regarding n , k , d , and A_{d}(C) . Our Contributions This paper proposes several practical iterative bounds for Griesmer optimal linear codes. We summarize the contributions as follows. 1. Determining the lower bounds on the error coefficients of optimal linear codes is well known to be very difficult. In [ 28 ] , the authors reviewed the currently known methods for computing lower bounds on the error coefficients of linear codes. However, linear programming and polynomial methods tend to perform well only in special cases and often do not meet expectations. For example, Abdullah and Mow [ 25 , 10 ] constructed many binary Griesmer optimal linear codes with small error coefficients. However, their AFER-optimality cannot be determined using the linear programming method. With our bounds, their AFER-optimality can be easily ascertained. Specifically, we propose five lower bounds on the error coefficients of Griesmer optimal linear codes. These bounds are derived by analyzing the spatial relationships between linear codes and their related residual codes, as well as the structure of the codeword space. Together, these five bounds form a strong lower bound for the error

Read the complete text