Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in $ n $ variables having an algebraic degree bounded from above, without any restriction on $ n $, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths $ 2^n $ and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to $ 2^{21} $), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived.
Citation: Claude Carlet. Identifying codewords in general Reed-Muller codes and determining their weights[J]. AIMS Mathematics, 2024, 9(5): 10609-10637. doi: 10.3934/math.2024518
Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in $ n $ variables having an algebraic degree bounded from above, without any restriction on $ n $, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths $ 2^n $ and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to $ 2^{21} $), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived.
| [1] |
E. Abbe, O. Sberlo, A. Shpilka, M. Ye, Reed-Muller codes, Found. Trends Commun., 20 (2023), 1–156. https://doi.org/10.1561/0100000123 doi: 10.1561/0100000123
|
| [2] |
E. Abbe, A. Shpilka, A. Wigderson, Reed-Muller codes for random erasures and errors, IEEE T. Inform. Theory, 61 (2015), 5229–5252. https://doi.org/10.1109/TIT.2015.2462817 doi: 10.1109/TIT.2015.2462817
|
| [3] |
C. Beierle, A. Biryukov, A. Udovenko, On degree-$d$ zero-sum sets of full rank, Cryptogr. Commun., 12 (2020), 685–710. https://doi.org/10.1007/s12095-019-00415-0 doi: 10.1007/s12095-019-00415-0
|
| [4] |
E. R. Berlekamp, N. J. A. Sloane, Restrictions on the weight distributions of the Reed-Muller codes, Inform. Control, 14 (1969), 442–446. https://doi.org/10.1016/S0019-9958(69)90150-8 doi: 10.1016/S0019-9958(69)90150-8
|
| [5] |
E. R. Berlekamp, N. J. A. Sloane, Weight enumerator for second-order Reed-Muller codes, IEEE T. Inform. Theory, 16 (1970), 745–751. https://doi.org/10.1109/TIT.1970.1054553 doi: 10.1109/TIT.1970.1054553
|
| [6] | Y. L. Borissov, On McEliece's result about divisibility of the weights in the binary Reed-Muller codes, In: Seventh International Workshop on Optimal Codes and Related Topics, 2013, 47–52. Available from: http://www.moi.math.bas.bg/oc2013/a7.pdf. |
| [7] | C. Carlet, A transformation on Boolean functions, its consequences on some problems related to Reed-Muller codes, In: Proceedings of EUROCODE 1990, Lecture Notes in Computer Science, 514 (1991), 42–50. https://doi.org/10.1007/3-540-54303-1_116 |
| [8] | C. Carlet, Boolean functions for cryptography and coding theory, Cambridge University Press, 2021. |
| [9] |
C. Carlet, The weight spectrum of the Reed-Muller codes $RM(m-5, m)$, IEEE T. Inform. Theory, 2024. http://dx.doi.org/10.1109/TIT.2023.3343697 doi: 10.1109/TIT.2023.3343697
|
| [10] |
C. Carlet, P. Méaux, A complete study of two classes of Boolean functions: Direct sums of monomials and threshold functions, IEEE T. Inform. Theory, 68 (2022), 3404–3425. https://doi.org/10.1109/TIT.2021.3139804 doi: 10.1109/TIT.2021.3139804
|
| [11] | C. Carlet, E. Prouff, M. Rivain, T. Roche, Algebraic decomposition for probing security, In: Proceedings of CRYPTO 2015, Lecture Notes in Computer Science, 9215 (2015), 742–763. https://doi.org/10.1007/978-3-662-47989-6_36 |
| [12] |
C. Carlet, P. Solé, The weight spectrum of two families of Reed-Muller codes, Discrete Math., 346 (2023), 113568. https://doi.org/10.1016/j.disc.2023.113568 doi: 10.1016/j.disc.2023.113568
|
| [13] |
C. Ding, C. Li, Y. Xia, Another generalisation of the binary Reed-Muller codes and its applications, Finite Fields Th. Appl., 53 (2018), 144–174. https://doi.org/10.1016/j.ffa.2018.06.006 doi: 10.1016/j.ffa.2018.06.006
|
| [14] | Final report of 3GPP TSG RAN WG1 #87 v1.0.0. Available from: http://www.3gpp.org/ftp/tsg_ran/WG1_RL1/TSGR1_87/Report/. |
| [15] |
T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Inform. Control, 18 (1971), 369–394. https://doi.org/10.1016/S0019-9958(71)90473-6 doi: 10.1016/S0019-9958(71)90473-6
|
| [16] |
T. Kasami, N. Tokura, On the weight structure of the Reed Muller codes, IEEE T. Inform. Theory, 16 (1970), 752–759. https://doi.org/10.1109/TIT.1970.1054545 doi: 10.1109/TIT.1970.1054545
|
| [17] |
T. Kasami, N. Tokura, S. Azumi, On the weight enumeration of weights less than $2.5d$ of Reed-Muller codes, Inform. Control, 30 (1976), 380–395. https://doi.org/10.1016/S0019-9958(76)90355-7 doi: 10.1016/S0019-9958(76)90355-7
|
| [18] |
T. Kaufman, S. Lovett, E. Porat, Weight distribution and list-decoding size of Reed-Muller codes, IEEE T. Inform. Theory, 58 (2012), 2689–2696. https://doi.org/10.1109/TIT.2012.2184841 doi: 10.1109/TIT.2012.2184841
|
| [19] |
A. M. Kerdock, A class of low-rate non linear codes, Inform. Control, 20 (1972), 182–187. https://doi.org/10.1016/S0019-9958(72)90376-2 doi: 10.1016/S0019-9958(72)90376-2
|
| [20] |
S. J. Lin, Y. S. Han, N. Yu, New locally correctable codes based on projective Reed-Muller codes, IEEE T. Inform. Theory, 67 (2019), 3834–3841. https://doi.org/10.1109/TCOMM.2019.2900039 doi: 10.1109/TCOMM.2019.2900039
|
| [21] |
F. J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell. Syst. Tech. J., 42 (1963), 79–94. https://doi.org/10.1002/j.1538-7305.1963.tb04003.x doi: 10.1002/j.1538-7305.1963.tb04003.x
|
| [22] | F. J. MacWilliams, N. J. Sloane, The theory of error-correcting codes, North Holland, 1977. |
| [23] |
R. J. McEliece, Weight congruence for $p$-ary cyclic codes, Discrete Math., 3 (1972), 177–192. https://doi.org/10.1016/0012-365X(72)90032-5 doi: 10.1016/0012-365X(72)90032-5
|
| [24] | M. Mondelli, From polar to Reed-Muller codes, Thesis, EPFL, 2016. |
| [25] |
M. Mondelli, S. H. Hassani, R. L. Urbanke, From polar to Reed-Muller codes: A technique to improve the finite-length performance, IEEE T. Commun., 62 (2014), 3084–3091. https://doi.org/10.1109/TCOMM.2014.2345069 doi: 10.1109/TCOMM.2014.2345069
|
| [26] |
S. Mesnager, A. Oblaukhov, Classification of the codewords of weights 16 and 18 of the Reed-Muller code RM (n-3, n), IEEE T. Inform. Theory, 68 (2021), 940–952. https://doi.org/10.1109/TIT.2021.3128495 doi: 10.1109/TIT.2021.3128495
|
| [27] |
D. E. Muller, Application of boolean algebra to switching circuit design and to error detection, T. IRE Prof. Group Electron. Comput., 3 (1954), 6–12. https://doi.org/10.1109/IREPGELC.1954.6499441 doi: 10.1109/IREPGELC.1954.6499441
|
| [28] | V. S. Pless, W. C. Huffman, R. A. Brualdi, Handbook of coding theory, Elsevier, 1998. |
| [29] |
I. S. Reed, A class of multiple-error-correcting codes and the decoding scheme, T. IRE Prof. Group Electron. Comput., 4 (1954), 38–49. https://doi.org/10.1109/TIT.1954.1057465 doi: 10.1109/TIT.1954.1057465
|
| [30] |
M. Shi, X. Li, A. Neri, P. Solé, How many weights can a cyclic code have? IEEE T. Inform. Theory, 66 (2019), 1449–1459. https://doi.org/10.1109/TIT.2019.2946660 doi: 10.1109/TIT.2019.2946660
|
| [31] | N. J. Sloane, Online encyclopedia of integer sequences, 1999. https://doi.org/10.1515/9780691197944-009 |
Claude Carlet. Identifying codewords in general Reed-Muller codes and determining their weights[J]. AIMS Mathematics, 2024, 9(5): 10609-10637. doi: 10.3934/math.2024518
DownLoad: