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

This paper studies codes (linear or nonlinear) using methods coming from the study of Boolean functions, by considering the Boolean function equal the indicator of the code. It is shown how the main parameters of codes can be linked to the natural parameters of the algebraic and numerical normal forms of their indicators. The algebraic normal form (ANF) is the \(n\)-variable multivariate polynomial representation of any Boolean function \(f: \mathbb{F}_2^n \mapsto \mathbb{F}_2\), which belongs to the algebra \(\mathbb{F}_2\left[x_1, \ldots, x_n\right] /\left(x_1^2 \oplus x_1, \ldots, x_n^2 \oplus x_n\right)\), and hence has the form: \[ f(x)=\bigoplus_{I \subseteq\{1, \ldots, n\}} a_I\left(\prod_{i \in I} x_i\right)=\bigoplus_{I \subseteq\{1, \ldots, n\}} a_I x^I ; a_I \in \mathbb{F}_2, \] where the additions \(\bigoplus\) are in \(\mathbb{F}_2\). The numerical normal form (NNF) is similar to the ANF, which has the form: \[ f(x)=\sum_{I \subseteq\{1, \ldots, n\}} \lambda_I\left(\prod_{i \in I} x_i\right)=\sum_{I \subseteq\{1, \ldots, n\}} \lambda_I x^I ; \lambda_I \in \mathbb{Z}, \] For linear binary codes, this paper characterizes the minimum distance in a very simple way using the ANF. For example, Proposition 1 states that if \(C\) is a binary linear code and \(d\) is the minimum distance, and \(1_C(x)=\) \(\bigoplus_{I \subseteq\{1, \ldots, n\}} a_I x^I, a_I \in \mathbb{F}_2\) is the ANF of its indicator. Then \(d=\min \left\{|I| ; a_I=0\right\}\). This provides a way of searching for binary linear codes with good minimum distance. The author then extends this characterization to nonlinear binary codes via the numerical normal form (Propositions 3,4). After introducing the generalizations of ANF and NNF to functions from \(\mathbb{F}_p^n\) to \(\mathbb{R}\), the last part of the paper further extend these characterizations to linear codes over finite fields and to unrestricted codes over prime fields. Finally, some results on the weight distribution and the covering radius are given.