doi: 10.3934/amc.2022047
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators

Universities of Bergen, Norway, and Paris 8, France

Received  March 2022 Revised  May 2022 Early access June 2022

Fund Project: The research of the author is partly supported by the Trond Mohn Foundation and Norwegian Research Council

We consider the algebraic normal form (ANF) of the indicators (i.e. characteristic functions) of linear binary codes, and characterize the minimum distance of such codes in a very simple way by means of this ANF. We extend this characterization to nonlinear binary codes, via another representation, the numerical normal form (NNF). We further extend these characterizations to linear codes over finite fields and (after introducing a generalization of the NNF to functions from $ {\Bbb F}_p^n $ to $ {\Bbb R} $) to unrestricted codes over prime fields. We also study the weight distribution by means of the NNF, and the covering radius of binary codes with the same approach; the latter is more difficult to address, but we obtain some results as well.

Citation: Claude Carlet. Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators. Advances in Mathematics of Communications, doi: 10.3934/amc.2022047
References:
[1]

P. Beelen and G. Leander, A new construction of highly nonlinear S-boxes, Cryptogr. Commun., 4 (2012), 65-77.  doi: 10.1007/s12095-011-0052-4.

[2]

C. Carlet, Handling vectorial functions by means of their graph indicators, IEEE Trans. Inform. Theory, 66 (2020), 6324-6339.  doi: 10.1109/TIT.2020.2981524.

[3] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph Cambridge University Press, 2021. 
[4]

C. CarletP. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156.  doi: 10.1023/A:1008344232130.

[5]

C. CarletC. Ding and J. Yuan, Linear codes from perfect nonlinear mappings and their secret sharing schemes, IEEE Trans. Inform. Theory, 51 (2005), 2089-2102.  doi: 10.1109/TIT.2005.847722.

[6]

P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control, 23 (1973), 407-438. 

[7]

C. Ding, Cyclic Codes from some monomials and trinomials, SIAM J. Discrete Math., 27 (2013), 1977-1994.  doi: 10.1137/120882275.

[8]

C. Ding, A construction of binary linear codes from boolean functions, Discrete Math., 339 (2016), 2288-2303.  doi: 10.1016/j.disc.2016.03.029.

[9]

C. Ding, A sequence construction of cyclic codes over finite fields, Cryptogr. Commun., 10 (2018), 319-341.  doi: 10.1007/s12095-017-0222-0.

[10]

C. DingA. Munemasa and V. D. Tonchev, Bent vectorial functions, codes and designs, IEEE Trans. Inform. Theory, 65 (2019), 7533-7541.  doi: 10.1109/TIT.2019.2922401.

[11]

C. Ding and Z. Zhou, Binary cyclic codes from explicit polynomials over $GF(2^m)$, Discrete Math., 321 (2014), 76-89.  doi: 10.1016/j.disc.2013.12.020.

[12]

A. M. Kerdock, A class of low-rate non linear codes, Information and Control, 20 (1972), 182-187. 

[13]

D. Kleitman, On Dedekind's problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc., 21 (1969), 677-682.  doi: 10.2307/2036446.

[14]

J. LiuS. Mesnager and L. Chen, On the nonlinearity of S-boxes and linear codes, Cryptogr. Commun., 9 (2017), 345-361.  doi: 10.1007/s12095-015-0176-z.

[15]

F. J. MacWilliams and N. J. Sloane, The Theory of Error-correcting Codes, Amsterdam-New York-Oxford, 1977.

[16]

S. Mesnager, Bent vectorial functions and linear codes from o-polynomials, Des. Codes Cryptogr., 77 (2015), 99-116.  doi: 10.1007/s10623-014-9989-6.

[17]

S. Mesnager, "Linear codes from functions", Concise Encyclopedia Coding Theory, CRC Press/Taylor and Francis Group (Publisher), London, New York, 20 (2021), 94 pp.

[18]

D. Popescu, The algebraic degree of perfect binary codes, IEEE Trans. Inform. Theory, 54 (2008), 5198-5202.  doi: 10.1109/TIT.2008.929971.

[19]

D. TangC. Carlet and Z. Zhou, Binary linear codes from vectorial boolean functions and their weight distribution, Discrete Math., 340 (2017), 3055-3072.  doi: 10.1016/j.disc.2017.07.008.

[20]

J. Wolfmann, Bent functions and coding theory, Difference Sets, Sequences and Their Correlation Properties, 542 (1999), 393-4189. 

[21]

J. YuanC. Carlet and C. Ding, The weight distribution of a class of linear codes from perfect nonlinear functions, IEEE Transactions on Information Theory, 52 (2006), 712-717.  doi: 10.1109/TIT.2005.862125.

show all references

References:
[1]

P. Beelen and G. Leander, A new construction of highly nonlinear S-boxes, Cryptogr. Commun., 4 (2012), 65-77.  doi: 10.1007/s12095-011-0052-4.

[2]

C. Carlet, Handling vectorial functions by means of their graph indicators, IEEE Trans. Inform. Theory, 66 (2020), 6324-6339.  doi: 10.1109/TIT.2020.2981524.

[3] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph Cambridge University Press, 2021. 
[4]

C. CarletP. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156.  doi: 10.1023/A:1008344232130.

[5]

C. CarletC. Ding and J. Yuan, Linear codes from perfect nonlinear mappings and their secret sharing schemes, IEEE Trans. Inform. Theory, 51 (2005), 2089-2102.  doi: 10.1109/TIT.2005.847722.

[6]

P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control, 23 (1973), 407-438. 

[7]

C. Ding, Cyclic Codes from some monomials and trinomials, SIAM J. Discrete Math., 27 (2013), 1977-1994.  doi: 10.1137/120882275.

[8]

C. Ding, A construction of binary linear codes from boolean functions, Discrete Math., 339 (2016), 2288-2303.  doi: 10.1016/j.disc.2016.03.029.

[9]

C. Ding, A sequence construction of cyclic codes over finite fields, Cryptogr. Commun., 10 (2018), 319-341.  doi: 10.1007/s12095-017-0222-0.

[10]

C. DingA. Munemasa and V. D. Tonchev, Bent vectorial functions, codes and designs, IEEE Trans. Inform. Theory, 65 (2019), 7533-7541.  doi: 10.1109/TIT.2019.2922401.

[11]

C. Ding and Z. Zhou, Binary cyclic codes from explicit polynomials over $GF(2^m)$, Discrete Math., 321 (2014), 76-89.  doi: 10.1016/j.disc.2013.12.020.

[12]

A. M. Kerdock, A class of low-rate non linear codes, Information and Control, 20 (1972), 182-187. 

[13]

D. Kleitman, On Dedekind's problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc., 21 (1969), 677-682.  doi: 10.2307/2036446.

[14]

J. LiuS. Mesnager and L. Chen, On the nonlinearity of S-boxes and linear codes, Cryptogr. Commun., 9 (2017), 345-361.  doi: 10.1007/s12095-015-0176-z.

[15]

F. J. MacWilliams and N. J. Sloane, The Theory of Error-correcting Codes, Amsterdam-New York-Oxford, 1977.

[16]

S. Mesnager, Bent vectorial functions and linear codes from o-polynomials, Des. Codes Cryptogr., 77 (2015), 99-116.  doi: 10.1007/s10623-014-9989-6.

[17]

S. Mesnager, "Linear codes from functions", Concise Encyclopedia Coding Theory, CRC Press/Taylor and Francis Group (Publisher), London, New York, 20 (2021), 94 pp.

[18]

D. Popescu, The algebraic degree of perfect binary codes, IEEE Trans. Inform. Theory, 54 (2008), 5198-5202.  doi: 10.1109/TIT.2008.929971.

[19]

D. TangC. Carlet and Z. Zhou, Binary linear codes from vectorial boolean functions and their weight distribution, Discrete Math., 340 (2017), 3055-3072.  doi: 10.1016/j.disc.2017.07.008.

[20]

J. Wolfmann, Bent functions and coding theory, Difference Sets, Sequences and Their Correlation Properties, 542 (1999), 393-4189. 

[21]

J. YuanC. Carlet and C. Ding, The weight distribution of a class of linear codes from perfect nonlinear functions, IEEE Transactions on Information Theory, 52 (2006), 712-717.  doi: 10.1109/TIT.2005.862125.

[1]

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

[2]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275

[3]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[4]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[5]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032

[6]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[7]

Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078

[8]

René B. Christensen, Carlos Munuera, Francisco R. F. Pereira, Diego Ruano. An algorithmic approach to entanglement-assisted quantum error-correcting codes from the Hermitian curve. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021072

[9]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[10]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018

[11]

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

[12]

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

[13]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013

[14]

Peter Frolkovič, Karol Mikula, Jozef Urbán. Distance function and extension in normal direction for implicitly defined interfaces. Discrete and Continuous Dynamical Systems - S, 2015, 8 (5) : 871-880. doi: 10.3934/dcdss.2015.8.871

[15]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[16]

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

[17]

Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022  doi: 10.3934/jdg.2022010

[18]

Toshiharu Sawashima, Tatsuya Maruta. Nonexistence of some ternary linear codes with minimum weight -2 modulo 9. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021052

[19]

Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. Upper bounds on the length function for covering codes with covering radius $ R $ and codimension $ tR+1 $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021074

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (92)
  • HTML views (70)
  • Cited by (0)

Other articles
by authors

[Back to Top]