May  2017, 11(2): 329-338. doi: 10.3934/amc.2017025

On the covering radius of some binary cyclic codes

1. 

Department of Computer Science, University of Puerto Rico, Río Piedras, San Juan, PR 00931

2. 

Department of Mathematics, University of Puerto Rico, Río Piedras, San Juan, PR 00931

* Corresponding author

Received  February 2016 Revised  March 2016 Published  May 2017

We compute the covering radius of some families of binary cyclic codes. In particular, we compute the covering radius of cyclic codes with two zeros and minimum distance greater than 3. We also compute the covering radius of some binary primitive BCH codes over $\mathbb{F}_{2^f}$, where $f=7, 8$.

Citation: Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025
References:
[1]

R. Arce-Nazario, F. N. Castro and J. Ortiz-Ubarri, On the covering radius of some binary cyclic codes available at https://franciscastr.files.wordpress.com/2016/01/coverig-radius2016.pdf Google Scholar

[2]

C. Bracken and T. Helleseth, Triple-error-correcting BCH-like codes, in Proc. 2009 IEEE Int. Conf. Symp. Inf. Theory, 2009,1723-1725. Google Scholar

[3]

R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, in Handbook of Coding Theory, North-Holland, Amsterdam, 1998,755-826.  Google Scholar

[4]

C. CarletP. Charpin and V. Zinoviev, Bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Crypt., 15 (1998), 125-155.  doi: 10.1023/A:1008344232130.  Google Scholar

[5]

F. N. Castro, I. Rubio, H. Randriam, O. Moreno and H. F. Mattson, Jr. , An elementary approach to Ax-Katz, McEliece's divisibility and applications to quasi-perfect binary 2-error correcting codes, in Proc. 2006 IEEE Int. Symp. Inf. Theory, Seattle, 2006,1905-1908. Google Scholar

[6]

P. CharpinA. Tietäväinen and V. Zinoviev, On binary cyclic codes with minimum distance d=3, Probl. Inform. Transm., 33 (1997), 287-296.   Google Scholar

[7]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Math. Library, Elsevier.  Google Scholar

[8]

T. Etzion and G. Greenberg, Constructions for perfect mixed codes and other codes, IEEE Trans. Inf. Theory, 39 (1993), 209-214.  doi: 10.1109/18.179360.  Google Scholar

[9]

T. Etzion and B. Mounits, Quasi-perfect codes with small distance, IEEE Trans. Inf. Theory, 51 (2005), 3938-3946.  doi: 10.1109/TIT.2005.856944.  Google Scholar

[10]

E. M. GorensteinW. W. Peterson and N. Zierler, Two-error correcting Bose-Chaudhuri codes are quasi-perfect, Inf. Contr., 3 (1960), 291-294.   Google Scholar

[11] W. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[12]

T. Kasami, Weight distributions of Bose-Chaudhuri-Hocquenghem codes, in Proc. Conf. Combinat. Math. Appl. , Univ. North Carolina, Chapel Hill, 1969,335-357.  Google Scholar

[13]

T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Inf. Control, 18 (1971), 369-394.   Google Scholar

[14]

O. Moreno, Further results on quasi-perfect codes related to the Goppa codes, Congresus Numerant., 40 (1983), 249-256.   Google Scholar

[15]

O. Moreno and F. Castro, Divisibility properties for covering radius of certain cyclic codes, IEEE Trans. Inf. Theory, 49 (2003), 3299-3303.  doi: 10.1109/TIT.2003.820033.  Google Scholar

[16]

O. Moreno and F. Castro, On the covering radius of certain cyclic codes, in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, 2003,129-138. doi: 10.1007/3-540-44828-4_15.  Google Scholar

[17]

O. Moreno and F. Castro, Improvement of Ax-Katz's and Moreno-Moreno's results and applications, Int. J. Pure Appl. Math., 19 (2005), 259-267.   Google Scholar

[18]

O. MorenoF. Castro and H. F. Mattson Jr., Correction, divisibility properties for covering radius for certain cyclic codes, IEEE Trans. Inf. Theory, 52 (2006), 1798-1799.  doi: 10.1109/TIT.2003.820033.  Google Scholar

[19]

O. Moreno and C. J. Moreno, Improvement of the Chevalley-Warning and the Ax-Katz theorems, Amer. J. Math., 117 (1995), 241-244.  doi: 10.2307/2375042.  Google Scholar

[20]

O. MorenoK. ShumF. N. Castro and P. V. Kumar, Tight bounds for Chevalley-Warning-Ax type estimates, with improved applications, Proc. London Math. Soc., 88 (2004), 545-564.  doi: 10.1112/S002461150301462X.  Google Scholar

[21]

T. J. Wagner, A search technique for quasi-perfect, Inf. Control, 9 (1966), 94-99.   Google Scholar

show all references

References:
[1]

R. Arce-Nazario, F. N. Castro and J. Ortiz-Ubarri, On the covering radius of some binary cyclic codes available at https://franciscastr.files.wordpress.com/2016/01/coverig-radius2016.pdf Google Scholar

[2]

C. Bracken and T. Helleseth, Triple-error-correcting BCH-like codes, in Proc. 2009 IEEE Int. Conf. Symp. Inf. Theory, 2009,1723-1725. Google Scholar

[3]

R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, in Handbook of Coding Theory, North-Holland, Amsterdam, 1998,755-826.  Google Scholar

[4]

C. CarletP. Charpin and V. Zinoviev, Bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Crypt., 15 (1998), 125-155.  doi: 10.1023/A:1008344232130.  Google Scholar

[5]

F. N. Castro, I. Rubio, H. Randriam, O. Moreno and H. F. Mattson, Jr. , An elementary approach to Ax-Katz, McEliece's divisibility and applications to quasi-perfect binary 2-error correcting codes, in Proc. 2006 IEEE Int. Symp. Inf. Theory, Seattle, 2006,1905-1908. Google Scholar

[6]

P. CharpinA. Tietäväinen and V. Zinoviev, On binary cyclic codes with minimum distance d=3, Probl. Inform. Transm., 33 (1997), 287-296.   Google Scholar

[7]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Math. Library, Elsevier.  Google Scholar

[8]

T. Etzion and G. Greenberg, Constructions for perfect mixed codes and other codes, IEEE Trans. Inf. Theory, 39 (1993), 209-214.  doi: 10.1109/18.179360.  Google Scholar

[9]

T. Etzion and B. Mounits, Quasi-perfect codes with small distance, IEEE Trans. Inf. Theory, 51 (2005), 3938-3946.  doi: 10.1109/TIT.2005.856944.  Google Scholar

[10]

E. M. GorensteinW. W. Peterson and N. Zierler, Two-error correcting Bose-Chaudhuri codes are quasi-perfect, Inf. Contr., 3 (1960), 291-294.   Google Scholar

[11] W. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[12]

T. Kasami, Weight distributions of Bose-Chaudhuri-Hocquenghem codes, in Proc. Conf. Combinat. Math. Appl. , Univ. North Carolina, Chapel Hill, 1969,335-357.  Google Scholar

[13]

T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Inf. Control, 18 (1971), 369-394.   Google Scholar

[14]

O. Moreno, Further results on quasi-perfect codes related to the Goppa codes, Congresus Numerant., 40 (1983), 249-256.   Google Scholar

[15]

O. Moreno and F. Castro, Divisibility properties for covering radius of certain cyclic codes, IEEE Trans. Inf. Theory, 49 (2003), 3299-3303.  doi: 10.1109/TIT.2003.820033.  Google Scholar

[16]

O. Moreno and F. Castro, On the covering radius of certain cyclic codes, in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, 2003,129-138. doi: 10.1007/3-540-44828-4_15.  Google Scholar

[17]

O. Moreno and F. Castro, Improvement of Ax-Katz's and Moreno-Moreno's results and applications, Int. J. Pure Appl. Math., 19 (2005), 259-267.   Google Scholar

[18]

O. MorenoF. Castro and H. F. Mattson Jr., Correction, divisibility properties for covering radius for certain cyclic codes, IEEE Trans. Inf. Theory, 52 (2006), 1798-1799.  doi: 10.1109/TIT.2003.820033.  Google Scholar

[19]

O. Moreno and C. J. Moreno, Improvement of the Chevalley-Warning and the Ax-Katz theorems, Amer. J. Math., 117 (1995), 241-244.  doi: 10.2307/2375042.  Google Scholar

[20]

O. MorenoK. ShumF. N. Castro and P. V. Kumar, Tight bounds for Chevalley-Warning-Ax type estimates, with improved applications, Proc. London Math. Soc., 88 (2004), 545-564.  doi: 10.1112/S002461150301462X.  Google Scholar

[21]

T. J. Wagner, A search technique for quasi-perfect, Inf. Control, 9 (1966), 94-99.   Google Scholar

Figure 1.  Construction of a solution for $\alpha_1 = 1 \in \mathbb{F}_{2^7}$. By choosing numbers that have an even quantity of 1's for all columns except the least significant, we guarantee that solution $\alpha_1 = 0000001$. The values for $\left(x_1,\ldots,x_5\right)$ are read from the rows
Table 1.  Codes ${\mathcal C}_{1,d}$ with minimum distance $\geq 4$ and covering radius 3
${\mathcal C}_{1,d}/\mathbb{F}_{128}$ ${\mathcal C}_{1,d}/\mathbb{F}_{512}$ ${\mathcal C}_{1,d}/\mathbb{F}_{2048}$
3, 5, 9, 11, 13, 15
21, 23, 27, 29, 43
3, 5, 13, 17, 19, 27
31, 43, 47, 87
3, 5, 9, 11, 13, 17, 25, 33, 35, 37, 43, 47, 49
57, 63, 81, 87, 95,105,121,139,141,143,151
171,187,189,206,221,229,231,249
295,311,315,343,363,365,413,429
${\mathcal C}_{1,d}/\mathbb{F}_{128}$ ${\mathcal C}_{1,d}/\mathbb{F}_{512}$ ${\mathcal C}_{1,d}/\mathbb{F}_{2048}$
3, 5, 9, 11, 13, 15
21, 23, 27, 29, 43
3, 5, 13, 17, 19, 27
31, 43, 47, 87
3, 5, 9, 11, 13, 17, 25, 33, 35, 37, 43, 47, 49
57, 63, 81, 87, 95,105,121,139,141,143,151
171,187,189,206,221,229,231,249
295,311,315,343,363,365,413,429
Table 2.  Codes ${\mathcal C}_{1,d}$ with minimum distance $\geq 4$ and covering radius 3
${\mathcal C}_{1,d}/\mathbb{F}_{2^{13}}$
3, 5, 9, 11, 13, 17, 19, 21, 33, 43, 57, 65, 67, 71, 95, 97,113,127,129,147,161,171,191,205,225,241,287,347,363,367,405,483,485,497,631,635,683,745,747,749,869,911,919,939,949,953,973,1367,1453,1461,1639,1643,1645,1691,1707,2047,2731
${\mathcal C}_{1,d}/\mathbb{F}_{2^{13}}$
3, 5, 9, 11, 13, 17, 19, 21, 33, 43, 57, 65, 67, 71, 95, 97,113,127,129,147,161,171,191,205,225,241,287,347,363,367,405,483,485,497,631,635,683,745,747,749,869,911,919,939,949,953,973,1367,1453,1461,1639,1643,1645,1691,1707,2047,2731
Table 3.  Covering radius of binary primitive $BCH$ codes
$n$ $BCH(e)$Covering Radius
127 $BCH(3)$5
127 $BCH(4)$7
127 $BCH(5)$9
255 $BCH(3)$5
255 $BCH(4)$7
$n$ $BCH(e)$Covering Radius
127 $BCH(3)$5
127 $BCH(4)$7
127 $BCH(5)$9
255 $BCH(3)$5
255 $BCH(4)$7
Table 4.  Covering radius of cyclic codes of type ${\mathcal C}_{1, 2^i+1, 2^{2i}+1}$
$n$ ${\mathcal C}_{1, 2^i+1, 2^{2i}+1}$Covering Radius
31 ${\mathcal C}_{1, 5, 17}$5
127 ${\mathcal C}_{1, 5, 17}$5
127 ${\mathcal C}_{1, 9, 65}$5
255 ${\mathcal C}_{1, 9, 65}$5
$n$ ${\mathcal C}_{1, 2^i+1, 2^{2i}+1}$Covering Radius
31 ${\mathcal C}_{1, 5, 17}$5
127 ${\mathcal C}_{1, 5, 17}$5
127 ${\mathcal C}_{1, 9, 65}$5
255 ${\mathcal C}_{1, 9, 65}$5
[1]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399

[2]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018

[3]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[4]

Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175

[5]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[6]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[7]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[8]

Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035

[9]

Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195

[10]

Cem Güneri, Ferruh Özbudak, Funda ÖzdemIr. On complementary dual additive cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 353-357. doi: 10.3934/amc.2017028

[11]

Nabil Bennenni, Kenza Guenda, Sihem Mesnager. DNA cyclic codes over rings. Advances in Mathematics of Communications, 2017, 11 (1) : 83-98. doi: 10.3934/amc.2017004

[12]

Heide Gluesing-Luerssen, Katherine Morrison, Carolyn Troha. Cyclic orbit codes and stabilizer subfields. Advances in Mathematics of Communications, 2015, 9 (2) : 177-197. doi: 10.3934/amc.2015.9.177

[13]

Joaquim Borges, Ivan Yu. Mogilnykh, Josep Rifà, Faina I. Solov'eva. Structural properties of binary propelinear codes. Advances in Mathematics of Communications, 2012, 6 (3) : 329-346. doi: 10.3934/amc.2012.6.329

[14]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015

[15]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019

[16]

Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273

[17]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[18]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251

[19]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55

[20]

Long Yu, Hongwei Liu. A class of $p$-ary cyclic codes and their weight enumerators. Advances in Mathematics of Communications, 2016, 10 (2) : 437-457. doi: 10.3934/amc.2016017

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (12)
  • HTML views (4)
  • Cited by (0)

[Back to Top]