American Institute of Mathematical Sciences

May  2011, 5(2): 333-337. doi: 10.3934/amc.2011.5.333

On the non-minimality of the largest weight codewords in the binary Reed-Muller codes

 1 Department of Mathematics, Ghent University, Krijgslaan 281 - S22, 9000 Ghent, Belgium, Belgium

Received  May 2010 Revised  August 2010 Published  August 2011

The study of minimal codewords in linear codes was motivated by Massey who described how minimal codewords of a linear code define access structures for secret sharing schemes. As a consequence of his article, Borissov, Manev, and Nikova initiated the study of minimal codewords in the binary Reed-Muller codes. They counted the number of non-minimal codewords of weight $2d$ in the binary Reed-Muller codes RM$(r,m)$, and also gave results on the non-minimality of codewords of large weight in the binary Reed-Muller codes RM$(r,m)$. The results of Borissov, Manev, and Nikova regarding the counting of the number of non-minimal codewords of small weight in RM$(r,m)$ were improved by Schillewaert, Storme, and Thas who counted the number of non-minimal codewords of weight smaller than $3d$ in RM$(r,m)$. This article now presents new results on the non-minimality of large weight codewords in RM$(r,m)$.
Citation: Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
References:
 [1] A. Ashikhmin and A. Barg, Minimal vectors in linear codes,, IEEE Trans. Inform. Theory, 44 (1998), 2010.  doi: 10.1109/18.705584.  Google Scholar [2] Y. Borissov, N. L. Manev and S. Nikova, On the non-minimal codewords in binary Reed-Muller codes,, Discrete Appl. Math., 128 (2003), 65.  doi: 10.1016/S0166-218X(02)00436-5.  Google Scholar [3] T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes,, IEEE Trans. Inform. Theory, IT-16 (1970), 752.  doi: 10.1109/TIT.1970.1054545.  Google Scholar [4] T. Kasami, N. Tokura and S. Azumi, On the weight enumeration of weight less than $2.5d$ of Reed-Muller codes,, Rept. of Faculty of Eng. Sci., (1974).   Google Scholar [5] T. Kasami, N. Tokura and S. Azumi, On the weight enumeration of weight less than $2.5d$ of Reed-Muller codes,, Inform. Control, 30 (1976), 380.  doi: 10.1016/S0019-9958(76)90355-7.  Google Scholar [6] F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland, (1977).   Google Scholar [7] J. L. Massey, Minimal codewords and secret sharing,, in, (1993), 276.   Google Scholar [8] J. Schillewaert, L. Storme and J. A. Thas, Minimal codewords in Reed-Muller codes,, Des. Codes Crypt., 54 (2010), 273.  doi: 10.1007/s10623-009-9323-x.  Google Scholar

show all references

References:
 [1] A. Ashikhmin and A. Barg, Minimal vectors in linear codes,, IEEE Trans. Inform. Theory, 44 (1998), 2010.  doi: 10.1109/18.705584.  Google Scholar [2] Y. Borissov, N. L. Manev and S. Nikova, On the non-minimal codewords in binary Reed-Muller codes,, Discrete Appl. Math., 128 (2003), 65.  doi: 10.1016/S0166-218X(02)00436-5.  Google Scholar [3] T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes,, IEEE Trans. Inform. Theory, IT-16 (1970), 752.  doi: 10.1109/TIT.1970.1054545.  Google Scholar [4] T. Kasami, N. Tokura and S. Azumi, On the weight enumeration of weight less than $2.5d$ of Reed-Muller codes,, Rept. of Faculty of Eng. Sci., (1974).   Google Scholar [5] T. Kasami, N. Tokura and S. Azumi, On the weight enumeration of weight less than $2.5d$ of Reed-Muller codes,, Inform. Control, 30 (1976), 380.  doi: 10.1016/S0019-9958(76)90355-7.  Google Scholar [6] F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland, (1977).   Google Scholar [7] J. L. Massey, Minimal codewords and secret sharing,, in, (1993), 276.   Google Scholar [8] J. Schillewaert, L. Storme and J. A. Thas, Minimal codewords in Reed-Muller codes,, Des. Codes Crypt., 54 (2010), 273.  doi: 10.1007/s10623-009-9323-x.  Google Scholar
 [1] Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021 [2] Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010 [3] Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041 [4] Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233 [5] 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 [6] Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057 [7] Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69 [8] Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005 [9] José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467 [10] Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020053 [11] Gérard Cohen, Sihem Mesnager, Hugues Randriam. Yet another variation on minimal linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 53-61. doi: 10.3934/amc.2016.10.53 [12] Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020055 [13] Lluís Alsedà, David Juher, Pere Mumbrú. Minimal dynamics for tree maps. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 511-541. doi: 10.3934/dcds.2008.20.511 [14] Gabriel Ponce, Ali Tahzibi, Régis Varão. Minimal yet measurable foliations. Journal of Modern Dynamics, 2014, 8 (1) : 93-107. doi: 10.3934/jmd.2014.8.93 [15] Virginie Bonnaillie-Noël, Corentin Léna. Spectral minimal partitions of a sector. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 27-53. doi: 10.3934/dcdsb.2014.19.27 [16] Kristian Bjerklöv, Russell Johnson. Minimal subsets of projective flows. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 493-516. doi: 10.3934/dcdsb.2008.9.493 [17] Nancy Guelman, Jorge Iglesias, Aldo Portela. Examples of minimal set for IFSs. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5253-5269. doi: 10.3934/dcds.2017227 [18] Vladimir V. Chepyzhov, Monica Conti, Vittorino Pata. A minimal approach to the theory of global attractors. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 2079-2088. doi: 10.3934/dcds.2012.32.2079 [19] A. Giambruno and M. Zaicev. Minimal varieties of algebras of exponential growth. Electronic Research Announcements, 2000, 6: 40-44. [20] Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036

2018 Impact Factor: 0.879