On the properties and construction of Boolean bent and near-bent functions, and their applications to error-correcting codes for NASA deep-space
Abstract
In this investigation, we research the properties of highly nonlinear vectorial Boolean functions in m variables and their connections to good error-correcting codes. We focus on "bent" and "near-bent” functions, which achieve maximum nonlinearity for m even and odd, respectively. These functions f: F2m --> F2k are defined via their Walsh-Hadamard spectrum meeting certain conditions. For the Boolean function cases, Gold (1968), Kasami (1971) and later Dillon (1999) and Dobbertin (1999) have showed properties under which near-bent functions derived from almost-bent functions are near-bent. These are Boolean functions in m variables of the form Tr(xd). We relate the constructed functions to corresponding error-correcting cyclic codes as per Janwa and Wilson's work on "Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes" in 1993. We use the defining set of a cyclic code with “y” roots of the form {1,d1,d2, . . . , dy-1} to construct the codes computationally. The entries of the defining set correspond to the exponents of the Boolean power functions considered. The conditions needed for these functions to be bent and near-bent are similar to the conditions needed to construct two-error-correcting codes through the defining set. The main exponents considered for the construction of these functions are the Gold and Kasami-Welch exponents (2l + 1, 22l – 2l + 1 respectively). We use cyclotomic coset analysis modulo 2m - 1 on the Gold and Kasami-Welch exponents used for these functions. We identify theorems related to the distribution of the Gold and Kasami-Welch exponents in the cyclotomic cosets. These theorems are then used to present a new proof of results by Yoshiara on the enumeration of non CCZ-equivalent Gold and Kasami-Welch trace Boolean near-bent functions. These theorems consider slightly different restrictions on the exponents to the ones considered by Yoshiara.
Furthermore, we analyze and generalize theorems on the Gold and Kasami-Welch bent and near-bent functions. We identify a pattern in the relationship between exponents that led to near-bent/almost-bent (AB) functions. Various authors have studied and generalized the conditions under which Tr(αi xd) is a bent function where d is the Gold exponent . We present a conjecture on the exponents of α that lead to non-bent functions (and consequently, those that do). This is based on computational analysis of bent functions constructed through the algorithms we present. Various algorithms are constructed that generate these functions, and tables are obtained, which are used to establish our theorems and conjectures. Tables with the Gold bent function construction exception cases for up to 24 variables as well as some Kasami-Welch functions in six and 12 variables that support these conjectures are showed.
We also compare the developed functions and codes to well-known theorems and conjectures presented by Ding (2016), McGuire (2004), Calderbank (1984), Goethals (1979), and others on the weight distribution of the dual codes. Three weight dual codes are known to be associated with two-error-correcting codes. The distribution of the weights of the dual of the codes over F2m generated by the method above is conjectured to have the form [2m - 1- a, 2m - 1, 2m - 1 + a] as presented by McGuire. We generated codes for up to 13 variables, and all codes satisfied this weight distribution. Ding compiled a list of theorems on the exact weight distribution of these codes. We algorithmically applied these theorems to the codes constructed and found some codes that do not meet any of the criteria. However, these codes did meet the symmetric weight distribution criteria. An equivalence analysis was done for these codes to identify them with codes from known theorems. We further study and classify cyclic codes in two, three and four roots based on their weight distributions. These are constructed by using combinations of APN/AB and bent exponents. An LDPC Code analysis approach was implemented to codes constructed from the selected functions/codes in the work above. Bayesian belief propagation analysis over networks produced by these codes was done via Tanner graphs constructed from these codes, and analysis was done to determine the generated codes’ coding gain. The high code rates are ideal for very strict bandwidth requirements. We utilize Neal's algorithm to transmit encoded messages by utilizing our proposed codes via bent and near-bent functions. These codes are our unique results, and they show comparable performance to protograph based codes, Quasi-cyclic based codes, Turbo codes, and AR4JA codes. Our codes have improved or competitive performance for the SNR values in the range [0, 0.75] and relative coding gain improvements of over 0.50 dB.
Furthermore, we analyze and generalize theorems on the Gold and Kasami-Welch bent and near-bent functions. We identify a pattern in the relationship between exponents that led to near-bent/almost-bent (AB) functions. Various authors have studied and generalized the conditions under which Tr(αi xd) is a bent function where d is the Gold exponent . We present a conjecture on the exponents of α that lead to non-bent functions (and consequently, those that do). This is based on computational analysis of bent functions constructed through the algorithms we present. Various algorithms are constructed that generate these functions, and tables are obtained, which are used to establish our theorems and conjectures. Tables with the Gold bent function construction exception cases for up to 24 variables as well as some Kasami-Welch functions in six and 12 variables that support these conjectures are showed.
We also compare the developed functions and codes to well-known theorems and conjectures presented by Ding (2016), McGuire (2004), Calderbank (1984), Goethals (1979), and others on the weight distribution of the dual codes. Three weight dual codes are known to be associated with two-error-correcting codes. The distribution of the weights of the dual of the codes over F2m generated by the method above is conjectured to have the form [2m - 1- a, 2m - 1, 2m - 1 + a] as presented by McGuire. We generated codes for up to 13 variables, and all codes satisfied this weight distribution. Ding compiled a list of theorems on the exact weight distribution of these codes. We algorithmically applied these theorems to the codes constructed and found some codes that do not meet any of the criteria. However, these codes did meet the symmetric weight distribution criteria. An equivalence analysis was done for these codes to identify them with codes from known theorems. We further study and classify cyclic codes in two, three and four roots based on their weight distributions. These are constructed by using combinations of APN/AB and bent exponents. An LDPC Code analysis approach was implemented to codes constructed from the selected functions/codes in the work above. Bayesian belief propagation analysis over networks produced by these codes was done via Tanner graphs constructed from these codes, and analysis was done to determine the generated codes’ coding gain. The high code rates are ideal for very strict bandwidth requirements. We utilize Neal's algorithm to transmit encoded messages by utilizing our proposed codes via bent and near-bent functions. These codes are our unique results, and they show comparable performance to protograph based codes, Quasi-cyclic based codes, Turbo codes, and AR4JA codes. Our codes have improved or competitive performance for the SNR values in the range [0, 0.75] and relative coding gain improvements of over 0.50 dB.
Rights
© 2022 Jose W. Velazquez SantiagoCollections
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States