New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance
Lingqi Zheng, Weijun Fang, Rongxing Qiu · 2025
Read New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance by Lingqi Zheng, Weijun Fang, Rongxing Qiu (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-11010.txt.
Introduction
Lingqi Zheng, Weijun Fang, and Rongxing Qiu build new families of binary cyclic codes that stay strong in two ways at once. A code's worth is set by how far apart its words sit, which bounds how many flaws it can fix. Its dual, a mate code, has its own such gap. Past builds that raised one gap let the mate's gap fall, a trade this work fights.
Their codes have length one shy of a power of two and size near half the length. For each parity of the power, they give builds whose two gaps beat all past marks. In one case the low gap tops the known square-root bar by a wide edge. At the limit, the pair of gaps can reach twice the length in their product. Save for one famed code set, no past build hits that mark.
Catalog record
| CREATOR | Lingqi Zheng, Weijun Fang, Rongxing Qiu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11010
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance Lingqi Zheng, Weijun Fang, Rongxing Qiu Abstract Binary cyclic codes are worth studying due to their applications and theoretical importance. It is an important problem to construct an infinite family of cyclic codes with large minimum distance d d and dual distance d ⟂ d^{\perp} . In recent years, much research has been devoted to improving the lower bound on d d , some of which have exceeded the square-root bound. The constructions presented recently seem to indicate that when the minimum distance increases, the minimum distance of its dual code decreases. In this paper, we focus on the new constructions of binary cyclic codes with length n = 2 m − 1 n=2^{m}-1 , dimension near n / 2 n/2 and both relatively large minimum distance and dual distance. When m m is even, we construct a family of binary cyclic codes with parameters [ 2 m − 1 , 2 m − 1 ± 1 , d ] [2^{m}-1,2^{m-1}\pm 1,d] , where d ≥ 2 m / 2 − 1 d\geq 2^{m/2}-1 and d ⟂ ≥ 2 m / 2 d^{\perp}\geq 2^{m/2} . Both the minimum distance and the dual distance are significantly better than the previous results. When m m is the product of two distinct primes, we construct some cyclic codes with dimensions k = ( n + 1 ) / 2 k=(n+1)/2 and d > n log 2 n , d>\frac{n}{\log_{2}n}, where the lower bound on the minimum distance is much larger than the square-root bound. When m m is odd, we present two families of binary [ 2 m − 1 , 2 m − 1 , d ] [2^{m}-1,2^{m-1},d] cyclic codes with d ≥ 2 ( m + 1 ) / 2 − 1 d\geq 2^{(m+1)/2}-1 , d ⟂ ≥ 2 ( m + 1 ) / 2 d^{\perp}\geq 2^{(m+1)/2} and d ≥ 2 ( m + 3 ) / 2 − 15 d\geq 2^{(m+3)/2}-15 , d ⟂ ≥ 2 ( m − 1 ) / 2 d^{\perp}\geq 2^{(m-1)/2} respectively, which leads that d ⋅ d ⟂ d\cdot d^{\perp} can reach 2 n 2n asymptotically. To the best of our knowledge, for the binary cyclic codes with length n = 2 m − 1 n=2^{m}-1 and dimension k = ( n ± 1 ) / 2 k=(n\pm 1)/2 , except for the punctured binary Reed-Muller codes, there is no other construction of binary cyclic codes that reaches this bound. I Introduction Let \mathbb{F}_{2}^{n} be the n -dimensional vector space over the finite field \mathbb{F}_{2}=\left\{0,1\right\} . The Hamming weight wt(\bm{a}) of a vector \bm{a}=(a_{0},a_{1},...,a_{n-1})\in\mathbb{F}_{2}^{n} is the cardinality of the set supp(\bm{a})=\left\{0\leq i\leq n-1:a_{i}=1\right\}. The Hamming distance d(\bm{a},\bm{b}) between \bm{a} and \bm{b} is d(\bm{a},\bm{b})=wt(\bm{a}-\bm{b}) . For a code C\subseteq\mathbb{F}_{2}^{n} , the minimum Hamming distance of C is defined as d=\min_{\bm{a}\not=\bm{b}}\left\{d(\bm{a},\bm{b}):\bm{a}\in C,\bm{b}\in C\right\}. An [n,k,d]_{2} linear code C is a k -dimensional linear subspace of \mathbb{F}_{2}^{n} with minimum Hamming distance d . Let \bm{u}=(u_{0},u_{1},...,u_{n-1})\in\mathbb{F}_{2}^{n} and \bm{v}=(v_{0},v_{1},..,v_{n-1})\in\mathbb{F}_{2}^{n} , the Euclidean inner product is defined as \langle\bm{u},\bm{v}\rangle=\sum_{i=0}^{n-1}u_{i}v_{i}, then the Euclidean dual code of C is defined as C^{\perp}=\left\{\bm{x}\in\mathbb{F}_{2}^{n}:\langle\bm{x},\bm{c}\rangle=0,\forall\bm{c}\in C\right\} and we denote the minimum distance of C^{\perp} as d^{\perp} , which is called as the dual distance of C . Cyclic codes were introduced by E. Prange in [ 1 ] . We say that an [n,k] linear code C is cyclic if and only if for any \bm{c}=(c_{0},c_{1},...,c_{n-1})\in C , we have (c_{n-1},c_{0},c_{1},...,c_{n-2})\in C. Let n be an odd integer and let C be a binary cyclic code of length n . A codeword \bm{c}=(c_{0},c_{1},...,c_{n-1}) in C can be identified with the polynomial c(x)=c_{0}+c_{1}x+\cdots+c_{n-1}x^{n-1}\in\mathbb{F}_{2}[x]/\langle x^{n}-1\rangle. It is not hard to prove that the linear code C is cyclic if and only if the set \left\{c(x)=c_{0}+c_{1}x+\cdots+c_{n-1}x^{n-1}:(c_{0},c_{1},...,c_{n-1})\right. \left.\in C\right\} is an ideal in \mathbb{F}_{2}[x]/\langle x^{n}-1\rangle . Meanwhile, we know that every ideal of \mathbb{F}_{2}[x]/\langle x^{n}-1\rangle is principal. Then there is a monic polynomial g(x)\in\mathbb{F}_{2}[x] with the smallest degree among all generators of C . Clearly, g(x) is unique and defined as the generator polynomial. Moreover, the dimension of C {\rm{dim}}(C)=n-{\rm{deg}}(g(x)) . Let h(x)=\frac{x^{n}-1}{g(x)} , then the dual code C^{\perp} of C is generated by g^{\perp}(x)=\frac{x^{{\rm{dim}}(C)}h(x^{-1})}{h(0)}. Obviously, {\rm{dim}}(C)+{\rm{dim}}(C^{\perp})=n. To obtain cyclic codes with improved parameters, many researchers have directed their attention toward BCH codes. This is primarily because they constitute an essential subclass of cyclic codes with excellent algebraic properties, and many BCH codes are known to be optimal linear codes. Binary BCH codes were introduced by Hocquenghem [ 2 ] , Bose and Ray-Chaudhuri [ 3 ] . Let m\geq 2 be a positive integer and n=2^{m}-1 . Let \beta be a primitive element of \mathbb{F}_{2^{m}} . For any integer i , let {\rm{m}}_{\beta^{i}}(x) denote the minimal polynomial of \beta_{i} over \mathbb{F}_{2} , which is the monic polynomial of the smallest degree over \mathbb{F}_{2} having \beta^{i} as a root. For any integer 2\leq\delta\leq n , define g_{(m,b,\delta)}(x)={\rm{lcm}}({\rm{m}}_{\beta^{b}}(x),{\rm{m}}_{\beta^{b+1}}(x),...,{\rm{m}}_{\beta^{b+\delta-2}}(x)), where b is an integer and {\rm{lcm}}(\cdot) denotes the least common multiple of the minimal polynomials {\rm{m}}_{\beta^{i}}(x) with b\leq i\leq b+\delta-2. Let C_{(m,b,\delta)} with generator polynomial g_{(m,b,\delta)}(x) denote the binary BCH code with designed distance \delta . So far, much research has been done on the dimension of BCH codes with some special designed distances( [ 4 ] , [ 5 ] , [ 6 ] ), and the parameters of BCH codes with some special length have also been studied thoroughly( [ 7 ] , [ 4 ] , [ 8 ] , [ 9 ] , [ 10 ] , [ 11 ] , [ 12 ] , [ 13 ] ). However, there are many kinds of BCH codes that still remain to be investigated. I-A Related work Binary cyclic codes have been widely studied for 70 years due to their theoretical importance and practical applications. Many good properties and constructions of binary cyclic codes have been proposed during this time( [ 14 ] , [ 15 ] , [ 16 ] , [ 17 ] , [ 18 ] , [ 19 ] , [ 20 ] ). We say the binary cyclic code is simple-root cyclic if n is odd and repeated-root cyclic if 2|n . When n is odd, constructing an infinite family of binary [n,(n\pm 1)/2,d] cyclic codes with large minimum distance d remains an important and challenging problem. Furthermore, designing a family of binary codes with both a good minimum distance d and a good dual minimum distance d^{\perp} presents an even greater challenge. To the best of our knowledge, the known infinite families of binary cyclic codes with large minimum distances can be summarized as follows: • Binary quadratic residue codes with parameters [n,(n+1)/2,d] and their even-weight subcodes with parameters [n,(n-1)/2,d+1] , where d^{2}\geq n and n\equiv\pm 1\pmod{8} is a prime [ 21 ] . The lower bound of d is defined as the square-root bound. • The punctured binary Reed-Muller codes of order (m-1)/2 with parameters [2^{m}-1,2^{m-1},2^{(m+1)/2}-1] and d^{\perp}\geq 2^{(m+1)/2} , where m is odd [ 22 ] . • Two families of binary cyclic codes with parameters [n_{1}n_{2},(n_{1}n_{2}+1)/2,d], where d>\max\left\{\sqrt{n_{1}},\sqrt{n_{2}}\right\} , n_{1} and n_{2} are two distinct primes such that n_{1}\equiv\pm 1\pmod{8} and n_{2}\equiv\pm