期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 69, 期 6, 页码 3663-3673出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2023.3242966
关键词
Boolean functions; Codes; Reed-Muller codes; Upper bound; Computers; Transforms; Hamming weight; Reed-Muller code; covering radius; Index Terms; Boolean function; third-order nonlinearity; affine transformation group
We have proved that the covering radius of the third-order Reed-Muller code RM(3, 7) is 20, narrowing down the previously known range of 20 to 23. This covering radius represents the maximum third-order nonlinearity among all 7-variable Boolean functions. While it has been known that there are 7-variable Boolean functions with a third-order nonlinearity of 20, we have shown that achieving a nonlinearity of 21 is not possible. Additionally, we have classified all 7-variable Boolean functions into 66 types based on the quotient space of RM(6, 6)/RM(3, 6) and provided further insights into their properties.
We prove the covering radius of the third-order Reed-Muller code RM(3, 7) is 20, which was previously known to be between 20 and 23 (inclusive). The covering radius of RM(3, 7) is the maximum third-order nonlinearity among all 7-variable Boolean functions. It was known that there exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. According to the classification of the quotient space of RM(6, 6)/RM(3, 6), we classify all 7-variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove that any function in the remaining 4 types can be transformed into a type (6, 10) function, if its third-order nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve the third-order nonlinearity 21 (with the assistance of computers). By the way, we prove that the affine transformation group over any finite field can be generated by two elements.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据